二級(jí)公共基礎(chǔ)知識(shí)數(shù)據(jù)結(jié)構(gòu)與算法(三)模擬題

1、 模擬模擬 二級(jí)公共基礎(chǔ)知識(shí)數(shù)據(jù)結(jié)構(gòu)與算法二級(jí)公共基礎(chǔ)知識(shí)數(shù)據(jù)結(jié)構(gòu)與算法( (三三) )單項(xiàng)選擇題單項(xiàng)選擇題第 1 題：算法的空間復(fù)雜度是指_。a.算法在執(zhí)行過(guò)程中所需要的計(jì)算機(jī)存儲(chǔ)空間b.算法所處理的數(shù)據(jù)量c.算法程序中的語(yǔ)句或指令條數(shù)d.算法在執(zhí)行過(guò)程中所需要的臨時(shí)工作單元數(shù)參考答案：a一般來(lái)說(shuō)， 一個(gè)算法的空間復(fù)雜度是指執(zhí)行該算法所需的內(nèi)存空間。一個(gè)算法所占用的存儲(chǔ)空間包括算法程序所占的空間、 輸入的初始數(shù)據(jù)所占的存儲(chǔ)空間以及算法執(zhí)行過(guò)程中所需要的額外空間。第 2 題：下列數(shù)據(jù)結(jié)構(gòu)中，屬于非線性結(jié)構(gòu)的是_。a.循環(huán)隊(duì)列b.帶鏈隊(duì)列c.二叉樹(shù)d.帶鏈棧參考答案：c線性結(jié)構(gòu)滿足兩個(gè)條件：有且

2、只有一個(gè)根節(jié)點(diǎn)；每個(gè)節(jié)點(diǎn)最多有一個(gè)前件，也最多有一個(gè)后件。棧、隊(duì)列都屬于線性結(jié)構(gòu)，棧是一種先進(jìn)后出的線性結(jié)構(gòu)，允許在棧頂進(jìn)行插入或刪除運(yùn)算；隊(duì)列則是一種先進(jìn)先出的線性結(jié)構(gòu)，允許在隊(duì)尾進(jìn)行捅入運(yùn)算，而在隊(duì)頭進(jìn)行刪除運(yùn)算。二叉樹(shù)是一種非線性結(jié)構(gòu)，因?yàn)槌~子節(jié)點(diǎn)，每個(gè)節(jié)點(diǎn)都有兩個(gè)后件，不滿足線性結(jié)構(gòu)的條件。第 3 題：下列數(shù)據(jù)結(jié)構(gòu)中，能夠按照“先進(jìn)后出”原則存取數(shù)據(jù)的是_。a.循環(huán)隊(duì)列b.棧c.隊(duì)列d.二叉樹(shù)參考答案：b第 4 題：對(duì)于循環(huán)隊(duì)列，下列敘述中正確的是_。a.隊(duì)頭指針是固定不變的b.隊(duì)頭指針一定大于隊(duì)尾指針c.隊(duì)頭指針一定小于隊(duì)尾指針d.隊(duì)頭指針可以大于隊(duì)尾指針，也可以小于隊(duì)尾指針參考答

3、案：d1第 5 題：下列敘述正確的是_。a.棧是“先進(jìn)先出”的線性表b.隊(duì)列是“后進(jìn)先出”的線性表c.循環(huán)隊(duì)列是非線性結(jié)構(gòu)d.有序線性表既可以采用順序存儲(chǔ)結(jié)構(gòu)，也可以采用鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)參考答案：d棧是“先進(jìn)后出”的線性表，而隊(duì)列是“先進(jìn)先出”的線性表，循環(huán)隊(duì)列自然也是線性結(jié)構(gòu)的， 有序線性表既可以采用順序存儲(chǔ)結(jié)構(gòu)， 也可以采用鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)。第 6 題：下列排序方法中，最壞情況下比較次數(shù)最少的是_。a.冒泡排序b.簡(jiǎn)單選擇排序c.直接插入排序d.堆排序參考答案：d本題考查各種排序方法的時(shí)間復(fù)雜度，冒泡排序、簡(jiǎn)單選擇排序、直接插入排序在最壞的情況下比較次數(shù)都是 o(n2)，而堆排序的時(shí)間復(fù)雜度為 o

4、(nlog2n)，這也是堆排序的最大優(yōu)點(diǎn)。第 7 題：某二叉樹(shù)有 5 個(gè)度為 2 的節(jié)點(diǎn)，則該二叉樹(shù)中的葉了節(jié)點(diǎn)是數(shù)是_。a.10b.8c.6d.4參考答案：c由二叉樹(shù)的性質(zhì)得知，對(duì)于一個(gè)非空的二叉樹(shù)， 葉子節(jié)點(diǎn)數(shù)等于度為 2 的節(jié)點(diǎn)數(shù)目1。第 8 題：支持子程序調(diào)用的數(shù)據(jù)結(jié)構(gòu)是_。a.棧b.樹(shù)c.隊(duì)列d.二叉樹(shù)參考答案：d在題目選項(xiàng)中， 棧是一種只允許在一端進(jìn)行插入和刪除的線性表，它是一種操作受限的線性表； 隊(duì)列是一種只允許在一端進(jìn)行插入，而在另一端進(jìn)行刪除的線性表，它也是一種操作受限的線性表；線性表是最簡(jiǎn)單、最常用的一種數(shù)據(jù)結(jié)構(gòu)，是具有相同數(shù)據(jù)類型的 n(n0)個(gè)數(shù)據(jù)元素組成的有限序列；二

5、叉樹(shù)是個(gè)有限元2素的集合，該集合或者為空、或者由一個(gè)稱為根(root)的元素及兩個(gè)不相交的、被分別稱為左子樹(shù)和右子樹(shù)的二叉樹(shù)組成。 這里僅有二叉樹(shù)是支持子程序調(diào)用的。第 9 題：在長(zhǎng)度為 n 的有序線性表中進(jìn)行二分查找，最壞情況下需要比較的次數(shù)是_。a.o(n)b.o(n2)c.o(log2n)d.o(nlog2n)參考答案：c二分法查找只適用于順序存儲(chǔ)的有序表。二分查找的基本方法是：將被查元素x與線性表的中間項(xiàng)進(jìn)行比較，若中問(wèn)項(xiàng)的值等于 x，則說(shuō)明查到；若小于中間項(xiàng)的值，則在線性表的前半部分以相同的方法進(jìn)行查找；若大于中間項(xiàng)的值，則在線性表的后半部分以相同的方法進(jìn)行查找。在最壞情況下，二分查

6、找需要比較log2n 次。第 10 題：下列敘述中正確的是_。a.順序存儲(chǔ)結(jié)構(gòu)的存儲(chǔ)一定是連續(xù)的，鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)的存儲(chǔ)空間不一定是連續(xù)的b.順序存儲(chǔ)結(jié)構(gòu)只針對(duì)線性結(jié)構(gòu)，鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)只針對(duì)非線性結(jié)構(gòu)c.順序存儲(chǔ)結(jié)構(gòu)能存儲(chǔ)有序表，鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)不能存儲(chǔ)有序表d.鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)比順序存儲(chǔ)結(jié)構(gòu)節(jié)省存儲(chǔ)空間參考答案：a在順序存儲(chǔ)結(jié)構(gòu)中所有元素所占的存儲(chǔ)空間是連續(xù)的，而在鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)中，存儲(chǔ)數(shù)據(jù)結(jié)構(gòu)的存儲(chǔ)空間可以不連續(xù)，因此選項(xiàng) a 是正確的。 線性表在計(jì)算機(jī)中的存放可以采用順序存儲(chǔ)結(jié)構(gòu)，也可采用鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)，順序存儲(chǔ)結(jié)構(gòu)和鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)都是既可用于線性結(jié)構(gòu)， 也可以用于非線性結(jié)構(gòu)， 因此選項(xiàng) b、 c 是錯(cuò)誤的

7、。采用鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)，不僅要存儲(chǔ)元素的值， 元素間的邏輯關(guān)系還需要通過(guò)附設(shè)的指針字段來(lái)表示，因此，鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)需要更多的存儲(chǔ)空間。第 11 題：下列敘述中正確的是_。a.循環(huán)隊(duì)列有隊(duì)頭和隊(duì)尾兩個(gè)指針，因此，循環(huán)隊(duì)列是非線性結(jié)構(gòu)b.在循環(huán)隊(duì)列中，只需要隊(duì)頭指針就能反映隊(duì)列中元素的動(dòng)態(tài)變化情況c.在循環(huán)隊(duì)列中，只需要隊(duì)尾指針就能反映隊(duì)列中元素的動(dòng)態(tài)變化情況d.循環(huán)隊(duì)列中元素的個(gè)數(shù)是由隊(duì)頭指針和隊(duì)尾指針共同決定的參考答案：d循環(huán)隊(duì)列是將隊(duì)列存儲(chǔ)空間的最后一個(gè)位置繞到第一個(gè)位置， 形成邏輯上的環(huán)形空間。循環(huán)隊(duì)列仍然是順序存儲(chǔ)結(jié)構(gòu)，是隊(duì)列常采用的形式，因此選項(xiàng) a 錯(cuò)誤。在循環(huán)隊(duì)列中，用隊(duì)尾指針 rear

8、 指向隊(duì)列中的隊(duì)尾元素，用隊(duì)頭指針 front 指向隊(duì)列排頭元素的前一個(gè)位置。循環(huán)隊(duì)列中的元素是動(dòng)態(tài)變化的，每進(jìn)行一次入隊(duì)運(yùn)算，對(duì)尾指針就進(jìn)一；每進(jìn)行一次出隊(duì)運(yùn)算，隊(duì)頭指針就進(jìn)一?？梢?jiàn)，由隊(duì)3頭指針和隊(duì)尾指針一起反映隊(duì)列中元素的動(dòng)態(tài)變化情況，因此選項(xiàng) b、c 是錯(cuò)誤的。從隊(duì)頭指針 front 指向的后一個(gè)位置直到隊(duì)尾指針 rear 指向的位置之間所有的元素均為隊(duì)列中的元素，因此選項(xiàng) d 是正確的。第 12 題：一個(gè)棧的初始狀態(tài)為空?，F(xiàn)將元素 1、2、3、4、5、a、b、c、d、e 依次入棧，然后再依次出棧，則元素出棧的順序是_。a.12345a2bcdeb.edcba54321c.abcdel

9、2345d.54321edcba參考答案：b棧是按照“先進(jìn)后出”的原則組織數(shù)據(jù)的，入棧的順序?yàn)?2345abcde，1 為棧底元素最后出棧，e 為棧頂元素最先出棧，因此出棧的順序?yàn)?edcba54321。第 13 題：算法的時(shí)間復(fù)雜度取決于_。a.問(wèn)題的規(guī)模b.待處理的數(shù)據(jù)的初始狀態(tài)c.問(wèn)題的困難度d.a 和 b參考答案：d第 14 題：計(jì)算機(jī)算法指的是_。a.計(jì)算方法b.調(diào)度方法c.排序方法d.解決某一問(wèn)題的有限運(yùn)算序列參考答案：d第 15 題：下列敘述中正確的是_。a.一個(gè)邏輯數(shù)據(jù)結(jié)構(gòu)只能有一種存儲(chǔ)結(jié)構(gòu)b.數(shù)據(jù)的邏輯結(jié)構(gòu)屬于線性結(jié)構(gòu)，存儲(chǔ)結(jié)構(gòu)屬于非線性結(jié)構(gòu)c.一個(gè)邏輯數(shù)據(jù)結(jié)構(gòu)可以有多種存儲(chǔ)

10、結(jié)構(gòu)，且各種存儲(chǔ)結(jié)構(gòu)不影響數(shù)據(jù)處理的效率d.一個(gè)邏輯數(shù)據(jù)結(jié)構(gòu)可以有多種存儲(chǔ)結(jié)構(gòu)，且各種存儲(chǔ)結(jié)構(gòu)影響數(shù)據(jù)處理的效率參考答案：d第 16 題：數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)是指_。a.存儲(chǔ)在外存中的數(shù)據(jù)b.數(shù)據(jù)所占的存儲(chǔ)空間量4c.數(shù)據(jù)在計(jì)算機(jī)中的順序存儲(chǔ)方式d.數(shù)據(jù)的邏輯結(jié)構(gòu)在計(jì)算機(jī)中的表示參考答案：d第 17 題：數(shù)據(jù)在計(jì)算機(jī)內(nèi)存中的表示是指_。a.數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)b.數(shù)據(jù)結(jié)構(gòu)c.數(shù)據(jù)的邏輯結(jié)構(gòu)d.數(shù)據(jù)元素之問(wèn)的關(guān)系參考答案：a第 18 題：數(shù)據(jù)的_包括集合、線性結(jié)構(gòu)、樹(shù)型結(jié)構(gòu)和圖形結(jié)構(gòu) 4 種基本類型。a.算法描述b.基本運(yùn)算c.邏輯結(jié)構(gòu)d.存儲(chǔ)結(jié)構(gòu)參考答案：c第 19 題：下列關(guān)于棧的描述正確的是_。a.在

11、棧中只能捅入元素而不能刪除元素b.在棧中只能刪除元素而不能捅入元素c.棧是特殊的線性表，只能在一端捅入或刪除元素d.棧是特殊的線性表，只能在一端插入元素，而在另一端刪除元素參考答案：c第 20 題：下列關(guān)于棧的描述中錯(cuò)誤的是_。a.棧是先進(jìn)后出的線性表b.棧只順序存儲(chǔ)c.棧具有記憶作用d.對(duì)棧的插入與刪除操作中，不需要改變棧底指針參考答案：b第 21 題：假定利用數(shù)組 am 順序存儲(chǔ)一個(gè)棧，利用 top 表示棧頂指針，用 topn1 表示棧空，該數(shù)組所能存儲(chǔ)的棧的最大長(zhǎng)度為 n，則表示棧滿的條件是_。a.top-1b.top0c.top1d.top1參考答案：d5第 22 題：在一個(gè)順序存儲(chǔ)的

12、循環(huán)隊(duì)列中，隊(duì)頭指針指向隊(duì)頭元素的_。a.當(dāng)前位置b.任意位置c.前一個(gè)位置d.后一個(gè)位置參考答案：c第 23 題：在單鏈表中，頭指針的作用是_。a.方便運(yùn)算的實(shí)現(xiàn)b.用于標(biāo)識(shí)單鏈表c.使單鏈表中至少有一個(gè)節(jié)點(diǎn)d.用于標(biāo)識(shí)首節(jié)點(diǎn)位置參考答案：b第 24 題：樹(shù)最適合于表示_。a.有序數(shù)據(jù)元素b.元素之間無(wú)聯(lián)系的數(shù)據(jù)c.無(wú)序數(shù)據(jù)元素d.元素之間具有分支層次關(guān)系的數(shù)據(jù)參考答案：d第 25 題：在用二叉鏈表表示的有 n 個(gè)節(jié)點(diǎn)的二叉樹(shù)中，值為非空的鏈域的個(gè)數(shù)為_(kāi)。a.n-1b.n+1c.2n-1d.2n+1參考答案：a第 26 題：下列數(shù)據(jù)結(jié)構(gòu)中，能用二分法進(jìn)行查找的是_。a.順序存儲(chǔ)的有序線性表b

13、.線性鏈表c.二叉鏈表d.有序線性鏈表參考答案：a第 27 題：對(duì)于長(zhǎng)度為 n 的線性表進(jìn)行順序查找，在最壞情況下所需要的比較次數(shù)為6_。a.log2nb.n/2c.nd.n+1參考答案：c第 28 題：對(duì)于長(zhǎng)度為 n 的線性表，在最壞情況下，下列各排序法所對(duì)應(yīng)的比較次數(shù)中正確的是_。a.冒泡排序?yàn)?n/2b.冒泡排序?yàn)?nc.快速排序?yàn)?nd.快速排序?yàn)?n(n-1)/2參考答案：d填空題第 29 題：描述算法的常用方法有_。參考答案：傳統(tǒng)流程圖、n-s 結(jié)構(gòu)化流程圖和偽碼描述語(yǔ)言第 30 題：一個(gè)算法的時(shí)間復(fù)雜度是_的函數(shù)。參考答案：算法輸入規(guī)模第 31 題：算法復(fù)雜度主要包括時(shí)間復(fù)雜度和

14、_復(fù)雜度。參考答案：空間第 32 題：對(duì)問(wèn)題處理方案的正確而完整的描述稱為_(kāi)。參考答案：算法第 33 題：一個(gè)數(shù)據(jù)結(jié)構(gòu)在計(jì)算機(jī)中的表示(映像)稱為_(kāi)。參考答案：數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)第 34 題：數(shù)據(jù)結(jié)構(gòu)分為邏輯結(jié)構(gòu)和存儲(chǔ)結(jié)構(gòu)，循環(huán)隊(duì)列屬于_結(jié)構(gòu)。參考答案：邏輯第 35 題：在一個(gè)長(zhǎng)度為 n 的順序表中的刪除第 i 個(gè)元素(0in-1)，需要向前移動(dòng)_元素。7參考答案：n-i第 36 題：棧和隊(duì)列的區(qū)別在于_。參考答案：刪除運(yùn)算不同第 37 題：從一個(gè)循環(huán)隊(duì)列中刪除一個(gè)元素，通常的操作是_。參考答案：先取出元素，后移動(dòng)隊(duì)頭指針第 38 題：一棵二叉樹(shù)第 6 層(根節(jié)點(diǎn)為第一層)的節(jié)點(diǎn)數(shù)最多為_(kāi)個(gè)。參考答案：32第 39 題：某二叉樹(shù)中度為 2 的節(jié)點(diǎn)有 18 個(gè)，則該二叉樹(shù)中有_個(gè)葉子節(jié)點(diǎn)。參考答案：19第 40 題：設(shè)一棵 n 個(gè)節(jié)點(diǎn)的完全二叉樹(shù)從根節(jié)點(diǎn)這一層開(kāi)始，每一層上的節(jié)點(diǎn)按從左到右的順序存儲(chǔ)在數(shù)組 a1n中，設(shè)某個(gè)節(jié)點(diǎn)在數(shù)組中的位置為 i(1in)，則其父節(jié)點(diǎn)的位置是_。參考答案：i/2第 41 題：對(duì) n 個(gè)記錄的有序表進(jìn)行二分查找法查找時(shí)，最大的比較次數(shù)是_。參考答案：log2n第 42 題：二分查找法的存儲(chǔ)結(jié)構(gòu)僅限于_，且是有序的。參考答案：順序存儲(chǔ)結(jié)構(gòu)第 43 題：在插入排序和選擇排序中，若原始記錄基本正序，則選擇_，若原始記錄基本反序，則選擇_。參