《數(shù)據(jù)結(jié)構(gòu)Ⅱ》在線平時(shí)作業(yè)3答卷

1、數(shù)據(jù)結(jié)構(gòu)在線平時(shí)作業(yè)3-00001試卷總分:100 得分:100一、單選題 (共 20 道試題,共 100 分)1.在待排關(guān)鍵字序列基本有序的前提下，效率最高的排序方法是A.直接插入排序B.快速排序C.直接選擇排序D.歸并排序答案:A2.一個(gè)具有1025個(gè)結(jié)點(diǎn)的二叉樹的高h(yuǎn)為A.11B.10C.11至1025之間D.10至1024之間答案:C3.已知含10個(gè)結(jié)點(diǎn)的二叉排序樹是一棵完全二叉樹，則該二叉排序樹在等概率情況下查找成功的平均查找長度等于A.1.0B.2.9C.3.4D.5.5答案:B4.一棵樹高為K的完全二叉樹至少的結(jié)點(diǎn)是A.2k 1B.2k-1 1C.2k-1D.2k答案:C5.在線

2、性表的下列運(yùn)算中，不改變數(shù)據(jù)元素之間結(jié)構(gòu)關(guān)系的運(yùn)算是A.插入B.刪除C.排序D.查找答案:D6.有關(guān)二叉樹下列說法正確的是A.二叉樹的度為2B.一棵二叉樹的度可以小于2C.二叉樹中至少有一個(gè)結(jié)點(diǎn)的度為2D.二叉樹中任何一個(gè)結(jié)點(diǎn)的度都為2答案:B7.若要在O(1)的時(shí)間復(fù)雜度上實(shí)現(xiàn)兩個(gè)循環(huán)鏈表頭尾相接，則應(yīng)對兩個(gè)循環(huán)鏈表各設(shè)置一個(gè)指針，分別指向A.各自的頭結(jié)點(diǎn)B.各自的尾結(jié)點(diǎn)C.各自的第一個(gè)元素結(jié)點(diǎn)D.一個(gè)表的頭結(jié)點(diǎn)，另一個(gè)表的尾結(jié)點(diǎn)答案:B8.對長度為n的關(guān)鍵字序列進(jìn)行堆排序的空間復(fù)雜度為A.O（log2n）B.O（1）C.O（n）D.O（n*log2n）答案:B9.多維數(shù)組之所以有行優(yōu)先順序

3、和列優(yōu)先順序兩種存儲(chǔ)方式是因?yàn)锳.數(shù)組的元素處在行和列兩個(gè)關(guān)系中B.數(shù)組的元素必須從左到右順序排列C.數(shù)組的元素之間存在次序關(guān)系D.數(shù)組是多維結(jié)構(gòu)，內(nèi)存是一維結(jié)構(gòu)答案:D10.對n個(gè)關(guān)鍵字的序列進(jìn)行快速排序，平均情況下的空間復(fù)雜度為A.O(1)B.O(logn)C.O(n)D.O(n logn)答案:B11.在一個(gè)單鏈表中，若刪除*p結(jié)點(diǎn)的后繼結(jié)點(diǎn)，則執(zhí)行操作A.q=p-next;p-next=q-next;free(q);B.p=p-next;p-next=p-next-next;free(p);C.p-next=q-next;free(p-next);D.p=p-next-next;fre

4、e(p-next);答案:A12.為便于判別有向圖中是否存在回路，可借助于A.廣度優(yōu)先搜索算法B.最小生成樹算法C.最短路徑算法D.拓?fù)渑判蛩惴ù鸢?D13.連通圖是指圖中任意兩個(gè)頂點(diǎn)之間A.都連通的無向圖B.都不連通的無向圖C.都連通的有向圖D.都不連通的有向圖答案:A14.能進(jìn)行二分查找的線性表,必須以A.順序方式存儲(chǔ),且元素按關(guān)鍵字有序B.鏈?zhǔn)椒绞酱鎯?chǔ),且元素按關(guān)鍵字有序C.順序方式存儲(chǔ),且元素按關(guān)鍵字分塊有序D.鏈?zhǔn)椒绞酱鎯?chǔ),且元素按關(guān)鍵字分塊有序答案:A15.二維數(shù)組A的每個(gè)元素是由6個(gè)字符組成的串，其行下標(biāo)i=0，l，8，列下標(biāo)為j=1，210。設(shè)每個(gè)字符占一個(gè)字節(jié),若按行先存儲(chǔ)，

5、元素A8，5的起始地址與A按列存儲(chǔ)時(shí)起始地址相同的元素是A.A8，5B.A3，10C.A5，8D.A0，9答案:B16.下面的說法中正確的是 (1)任何一棵二叉樹的葉子節(jié)點(diǎn)在三種遍歷中的相對次序不變。 (2)按二叉樹定義，具有三個(gè)節(jié)點(diǎn)的二叉樹共有6種。A.(1)，(2)B.(1)C.(2)D.(1)，(2)都錯(cuò)答案:B17.以下與數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)無關(guān)的術(shù)語是A.循環(huán)隊(duì)列B.鏈表C.哈希表D.棧答案:D18.如果求一個(gè)連通圖中以某個(gè)頂點(diǎn)為根的高度最小的生成樹，應(yīng)采用A.深度優(yōu)先搜索算法B.廣度優(yōu)先搜索算法C.求最小生成樹的prim算法D.拓?fù)渑判蛩惴ù鸢?B19.若長度為n的線性表采用順序存儲(chǔ)結(jié)構(gòu)，在其第i個(gè)位置插入一個(gè)新元素的算法的時(shí)間復(fù)雜度為A.O(0)B.O(1)C.O(n)D.