二級公共基礎知識數(shù)據(jù)結構與算法(三)模擬題

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

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

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

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

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

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

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

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

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

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

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

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

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

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