數(shù)據(jù)結(jié)構(gòu)試卷及答案[稻谷書苑]

1、選擇題（查找排序不考）1下面關(guān)于線性表的敘述錯(cuò)誤的是（ D ）。(A) 線性表采用順序存儲(chǔ)必須占用一片連續(xù)的存儲(chǔ)空間(B) 線性表采用鏈?zhǔn)酱鎯?chǔ)不必占用一片連續(xù)的存儲(chǔ)空間(C) 線性表采用鏈?zhǔn)酱鎯?chǔ)便于插入和刪除操作的實(shí)現(xiàn)(D) 線性表采用順序存儲(chǔ)便于插入和刪除操作的實(shí)現(xiàn)2設(shè)哈夫曼樹(shù)中的葉子結(jié)點(diǎn)總數(shù)為m，若用二叉鏈表作為存儲(chǔ)結(jié)構(gòu)，則該哈夫曼樹(shù)中總共有（ B ）個(gè)空指針域。(A) 2m-1(B) 2m(C) 2m+1(D) 4m3設(shè)順序循環(huán)隊(duì)列Q0：M-1的頭指針和尾指針?lè)謩e為F和R，頭指針F總是指向隊(duì)頭元素的前一位置，尾指針R總是指向隊(duì)尾元素的當(dāng)前位置，則該循環(huán)隊(duì)列中的元素個(gè)數(shù)為（ C ）。(A)

2、 R-F(B) F-R(C) (R-F+M)M(D) (F-R+M)M4設(shè)某棵二叉樹(shù)的中序遍歷序列為ABCD，前序遍歷序列為CABD，則后序遍歷該二叉樹(shù)得到序列為（ A ）。(A) BADC(B) BCDA(C) CDAB(D) CBDA5設(shè)某完全無(wú)向圖中有n個(gè)頂點(diǎn)，則該完全無(wú)向圖中有（ A ）條邊。(A) n(n-1)/2(B) n(n-1)(C) n2 (D) n2-16設(shè)某棵二叉樹(shù)中有2000個(gè)結(jié)點(diǎn)，則該二叉樹(shù)的最小高度為（ C ）。(A) 9(B) 10(C) 11(D) 127設(shè)某有向圖中有n個(gè)頂點(diǎn)，則該有向圖對(duì)應(yīng)的鄰接表中有（ B）個(gè)表頭結(jié)點(diǎn)。(A) n-1(B) n(C) n+1

3、(D) 2n-18設(shè)一組初始記錄關(guān)鍵字序列(5，2，6，3，8)，以第一個(gè)記錄關(guān)鍵字5為基準(zhǔn)進(jìn)行一趟快速排序的結(jié)果為（ C ）。(A) 2，3，5，8，6(B) 3，2，5，8，6(C) 3，2，5，6，8(D) 2，3，6，5，81.D2.B3.C4.A5.A6.C7.B8.C1設(shè)某數(shù)據(jù)結(jié)構(gòu)的二元組形式表示為A=(D，R)，D=01，02，03，04，05，06，07，08，09，R=r，r=，則數(shù)據(jù)結(jié)構(gòu)A是（ B）。(A) 線性結(jié)構(gòu)(B) 樹(shù)型結(jié)構(gòu)(C) 物理結(jié)構(gòu)(D) 圖型結(jié)構(gòu)2下面程序的時(shí)間復(fù)雜為（B ）for（i=1，s=0； i=n； i+）t=1；for(j=1；jnext；p-

4、data=q-data；p-next=q-next；free(q)；(B) q=p-next；q-data=p-data；p-next=q-next；free(q)；(C) q=p-next；p-next=q-next；free(q)；(D) q=p-next；p-data=q-data；free(q)；4設(shè)有n個(gè)待排序的記錄關(guān)鍵字，則在堆排序中需要（ A ）個(gè)輔助記錄單元。(A) 1(B) n(C) nlog2n(D) n25設(shè)一組初始關(guān)鍵字記錄關(guān)鍵字為(20，15，14，18，21，36，40，10)，則以20為基準(zhǔn)記錄的一趟快速排序結(jié)束后的結(jié)果為( A)。(A) 10，15，14，18，

5、20，36，40，21(B) 10，15，14，18，20，40，36，21(C) 10，15，14，20，18，40，36，2l(D) 15，10，14，18，20，36，40，216設(shè)二叉排序樹(shù)中有n個(gè)結(jié)點(diǎn)，則在二叉排序樹(shù)的平均平均查找長(zhǎng)度為（ B ）。(A) O(1)(B) O(log2n)(C)O(n)(D) O(n2)7設(shè)無(wú)向圖G中有n個(gè)頂點(diǎn)e條邊，則其對(duì)應(yīng)的鄰接表中的表頭結(jié)點(diǎn)和表結(jié)點(diǎn)的個(gè)數(shù)分別為（ D ）。(A) n，e(B) e，n(C) 2n，e(D) n，2e8. 設(shè)某強(qiáng)連通圖中有n個(gè)頂點(diǎn)，則該強(qiáng)連通圖中至少有（ C ）條邊。(A) n(n-1)(B) n+1(C) n(D)

6、 n(n+1)9設(shè)有5000個(gè)待排序的記錄關(guān)鍵字，如果需要用最快的方法選出其中最小的10個(gè)記錄關(guān)鍵字，則用下列（ B ）方法可以達(dá)到此目的。(A) 快速排序(B) 堆排序(C) 歸并排序(D) 插入排序10.下列四種排序中（ D ）的空間復(fù)雜度最大。(A) 插入排序(B) 冒泡排序(C) 堆排序(D) 歸并排序1.B2.B3.A4.A5.A6.B7.D8.C9.B10.D1設(shè)一維數(shù)組中有n個(gè)數(shù)組元素，則讀取第i個(gè)數(shù)組元素的平均時(shí)間復(fù)雜度為（ C）。(A) O(n)(B) O(nlog2n)(C) O(1)(D) O(n2)2設(shè)一棵二叉樹(shù)的深度為k，則該二叉樹(shù)中最多有（ D ）個(gè)結(jié)點(diǎn)。(A) 2

7、k+1(B) 2k(C) 2k-1(D) 2k-13設(shè)某無(wú)向圖中有n個(gè)頂點(diǎn)e條邊，則該無(wú)向圖中所有頂點(diǎn)的入度之和為（ D）。(A) n(B) e(C) 2n(D) 2e4在二叉排序樹(shù)中插入一個(gè)結(jié)點(diǎn)的時(shí)間復(fù)雜度為（ B ）。(A) O(1)(B) O(n)(C) O(log2n)(D) O(n2)5設(shè)某有向圖的鄰接表中有n個(gè)表頭結(jié)點(diǎn)和m個(gè)表結(jié)點(diǎn)，則該圖中有（ C）條有向邊。(A) n(B) n-1(C) m(D) m-16設(shè)一組初始記錄關(guān)鍵字序列為(345，253，674，924，627)，則用基數(shù)排序需要進(jìn)行（A）趟的分配和回收才能使得初始關(guān)鍵字序列變成有序序列。(A) 3(B) 4(C) 5

8、(D) 87設(shè)用鏈表作為棧的存儲(chǔ)結(jié)構(gòu)則退棧操作（B ）。(A) 必須判別棧是否為滿(B) 必須判別棧是否為空(C) 判別棧元素的類型(D) 對(duì)棧不作任何判別8下列四種排序中（A）的空間復(fù)雜度最大。(A) 快速排序(B) 冒泡排序(C) 希爾排序(D) 堆9設(shè)某二叉樹(shù)中度數(shù)為0的結(jié)點(diǎn)數(shù)為N0，度數(shù)為1的結(jié)點(diǎn)數(shù)為Nl，度數(shù)為2的結(jié)點(diǎn)數(shù)為N2，則下列等式成立的是（C）。(A) N0=N1+1(B) N0=Nl+N2(C) N0=N2+1(D) N0=2N1+l10.設(shè)有序順序表中有n個(gè)數(shù)據(jù)元素，則利用二分查找法查找數(shù)據(jù)元素X的最多比較次數(shù)不超過(guò)（ A）。(A) log2n+1(B) log2n-1(

9、C) log2n(D) log2(n+1)1C2D3D4B5C 6A7B8A9C10A1數(shù)據(jù)的最小單位是（A ）。(A) 數(shù)據(jù)項(xiàng)(B) 數(shù)據(jù)類型(C) 數(shù)據(jù)元素(D) 數(shù)據(jù)變量2設(shè)一組初始記錄關(guān)鍵字序列為(50，40，95，20，15，70，60，45)，則以增量d=4的一趟希爾排序結(jié)束后前4條記錄關(guān)鍵字為（ B ）。(A) 40，50，20，95(B) 15，40，60，20(C) 15，20，40，45(D) 45，40，15，203設(shè)一組初始記錄關(guān)鍵字序列為(25，50，15，35，80，85，20，40，36，70)，其中含有5個(gè)長(zhǎng)度為2的有序子表，則用歸并排序的方法對(duì)該記錄關(guān)鍵字序列

10、進(jìn)行一趟歸并后的結(jié)果為（ A ）。(A) 15，25，35，50，20，40，80，85，36，70(B) 15，25，35，50，80，20，85，40，70，36(C) 15，25，35，50，80，85，20，36，40，70(D) 15，25，35，50，80，20，36，40，70，854函數(shù)substr(“DATASTRUCTURE”，5，9)的返回值為（A ）。(A) “STRUCTURE”(B) “DATA”(C) “ASTRUCTUR”(D) “DATASTRUCTURE”5設(shè)一個(gè)有序的單鏈表中有n個(gè)結(jié)點(diǎn)，現(xiàn)要求插入一個(gè)新結(jié)點(diǎn)后使得單鏈表仍然保持有序，則該操作的時(shí)間復(fù)雜度為（

11、D）。(A) O(log2n)(B) O(1)(C) O(n2)(D) O(n)6設(shè)一棵m叉樹(shù)中度數(shù)為0的結(jié)點(diǎn)數(shù)為N0，度數(shù)為1的結(jié)點(diǎn)數(shù)為Nl，度數(shù)為m的結(jié)點(diǎn)數(shù)為Nm，則N0=（B ）。(A) Nl+N2+Nm(B) l+N2+2N3+3N4+(m-1)Nm(C) N2+2N3+3N4+(m-1)Nm(D) 2Nl+3N2+(m+1)Nm7設(shè)有序表中有1000個(gè)元素，則用二分查找查找元素X最多需要比較（ B）次。(A) 25(B) 10(C) 7(D) 18設(shè)連通圖G中的邊集E=(a，b)，(a，e)，(a，c)，(b，e)，(e，d)，(d，f)，(f，c)，則從頂點(diǎn)a出發(fā)可以得到一種深度優(yōu)

12、先遍歷的頂點(diǎn)序列為（ B）。(A) abedfc(B) acfebd(C) aebdfc(D) aedfcb9設(shè)輸入序列是1、2、3、n，經(jīng)過(guò)棧的作用后輸出序列的第一個(gè)元素是n，則輸出序列中第i個(gè)輸出元素是（C ）。(A) n-i(B) n-1-i(C) n+1-i(D) 不能確定10. 設(shè)一組初始記錄關(guān)鍵字序列為(45，80，55，40，42，85)，則以第一個(gè)記錄關(guān)鍵字45為基準(zhǔn)而得到一趟快速排序的結(jié)果是（C）。(A) 40，42，45，55，80，83(B) 42，40，45，80，85，88(C) 42，40，45，55，80，85(D) 42，40，45，85，55，801A2B3A

13、4A5D 6B7B8B9C10C1 設(shè)一組權(quán)值集合W=2，3，4，5，6，則由該權(quán)值集合構(gòu)造的哈夫曼樹(shù)中帶權(quán)路徑長(zhǎng)度之和為（D ）。(A) 20(B) 30(C) 40(D) 452執(zhí)行一趟快速排序能夠得到的序列是（A ）。(A) 41，12，34，45，27 55 72，63(B) 45，34，12，41 55 72，63，27(C) 63，12，34，45，27 55 41，72(D) 12，27，45，41 55 34，63，723設(shè)一條單鏈表的頭指針變量為head且該鏈表沒(méi)有頭結(jié)點(diǎn)，則其判空條件是（A）。(A) head=0(B) head-next=0(C) head-next=he

14、ad(D) head!=04時(shí)間復(fù)雜度不受數(shù)據(jù)初始狀態(tài)影響而恒為O(nlog2n)的是（A ）。(A) 堆排序(B) 冒泡排序(C) 希爾排序(D) 快速排序5設(shè)二叉樹(shù)的先序遍歷序列和后序遍歷序列正好相反，則該二叉樹(shù)滿足的條件是（D）。(A) 空或只有一個(gè)結(jié)點(diǎn)(B) 高度等于其結(jié)點(diǎn)數(shù)(C) 任一結(jié)點(diǎn)無(wú)左孩子(D) 任一結(jié)點(diǎn)無(wú)右孩子6一趟排序結(jié)束后不一定能夠選出一個(gè)元素放在其最終位置上的是（ D）。(A) 堆排序(B) 冒泡排序(C) 快速排序(D) 希爾排序7設(shè)某棵三叉樹(shù)中有40個(gè)結(jié)點(diǎn)，則該三叉樹(shù)的最小高度為（ B）。(A) 3(B) 4(C) 5(D) 68順序查找不論在順序線性表中還是在鏈

15、式線性表中的時(shí)間復(fù)雜度為（A）。(A) O(n)(B) O(n2)(C) O(n1/2)(D) O(1og2n)9二路歸并排序的時(shí)間復(fù)雜度為（C）。(A) O(n)(B) O(n2)(C) O(nlog2n)(D) O(1og2n)10. 深度為k的完全二叉樹(shù)中最少有（B）個(gè)結(jié)點(diǎn)。(A) 2k-1-1(B) 2k-1(C) 2k-1+1(D) 2k-111.設(shè)指針變量front表示鏈?zhǔn)疥?duì)列的隊(duì)頭指針，指針變量rear表示鏈?zhǔn)疥?duì)列的隊(duì)尾指針，指針變量s指向?qū)⒁腙?duì)列的結(jié)點(diǎn)X，則入隊(duì)列的操作序列為（C ）。(A) front-next=s；front=s；(B) s-next=rear；rear=

16、s；(C) rear-next=s；rear=s；(D) s-next=front；front=s；12.設(shè)某無(wú)向圖中有n個(gè)頂點(diǎn)e條邊，則建立該圖鄰接表的時(shí)間復(fù)雜度為（ A）。(A) O(n+e)(B) O(n2)(C) O(ne)(D) O(n3)13.設(shè)某哈夫曼樹(shù)中有199個(gè)結(jié)點(diǎn)，則該哈夫曼樹(shù)中有（ B）個(gè)葉子結(jié)點(diǎn)。(A) 99(B) 100(C) 101(D) 10214.設(shè)二叉排序樹(shù)上有n個(gè)結(jié)點(diǎn)，則在二叉排序樹(shù)上查找結(jié)點(diǎn)的平均時(shí)間復(fù)雜度為（D）。(A) O(n)(B) O(n2)(C) O(nlog2n)(D) O(1og2n)15.設(shè)用鄰接矩陣A表示有向圖G的存儲(chǔ)結(jié)構(gòu)，則有向圖G中頂

17、點(diǎn)i的入度為（B）。(A) 第i行非0元素的個(gè)數(shù)之和(B) 第i列非0元素的個(gè)數(shù)之和(C) 第i行0元素的個(gè)數(shù)之和(D) 第i列0元素的個(gè)數(shù)之和1D2A3A4A5D 6D7B8A9C10B 11C12A13B14D15B1設(shè)某無(wú)向圖有n個(gè)頂點(diǎn)，則該無(wú)向圖的鄰接表中有（B ）個(gè)表頭結(jié)點(diǎn)。(A) 2n(B) n(C) n/2(D) n(n-1)2設(shè)無(wú)向圖G中有n個(gè)頂點(diǎn)，則該無(wú)向圖的最小生成樹(shù)上有（B）條邊。(A) n(B) n-1(C) 2n(D) 2n-13設(shè)一組初始記錄關(guān)鍵字序列為(60，80，55，40，42，85)，則以第一個(gè)關(guān)鍵字45為基準(zhǔn)而得到的一趟快速排序結(jié)果是（ C）。(A) 40

18、，42，60，55，80，85(B) 42，45，55，60，85，80(C) 42，40，55，60，80，85(D) 42，40，60，85，55，804（ B）二叉排序樹(shù)可以得到一個(gè)從小到大的有序序列。(A) 先序遍歷(B) 中序遍歷(C) 后序遍歷(D) 層次遍歷5設(shè)按照從上到下、從左到右的順序從1開(kāi)始對(duì)完全二叉樹(shù)進(jìn)行順序編號(hào)，則編號(hào)為i結(jié)點(diǎn)的左孩子結(jié)點(diǎn)的編號(hào)為（B）。(A) 2i+1(B) 2i(C) i/2(D) 2i-16程序段s=i=0；do i=i+1； s=s+i；while(inext=0(C) head-next=head(D) head!=08設(shè)某棵二叉樹(shù)的高度為10

19、，則該二叉樹(shù)上葉子結(jié)點(diǎn)最多有（ C）。(A) 20(B) 256(C) 512(D) 10249設(shè)一組初始記錄關(guān)鍵字序列為(13，18，24，35，47，50，62，83，90，115，134),則利用二分法查找關(guān)鍵字90需要比較的關(guān)鍵字個(gè)數(shù)為（B ）。(A) 1(B) 2(C) 3(D) 410.設(shè)指針變量top指向當(dāng)前鏈?zhǔn)綏５臈ｍ?，則刪除棧頂元素的操作序列為（D）。(A) top=top+1;(B) top=top-1;(C) top-next=top;(D) top=top-next;1B2B3C4B5B6A7C8C9B10D1. 字符串的長(zhǎng)度是指（C ）。(A) 串中不同字符的個(gè)數(shù)(B

20、) 串中不同字母的個(gè)數(shù)(C) 串中所含字符的個(gè)數(shù)(D) 串中不同數(shù)字的個(gè)數(shù)2. 建立一個(gè)長(zhǎng)度為n的有序單鏈表的時(shí)間復(fù)雜度為（C）(A) O(n)(B) O(1)(C) O(n2)(D) O(log2n)3. 兩個(gè)字符串相等的充要條件是（ C）。(A) 兩個(gè)字符串的長(zhǎng)度相等(B) 兩個(gè)字符串中對(duì)應(yīng)位置上的字符相等(C) 同時(shí)具備(A)和(B)兩個(gè)條件(D) 以上答案都不對(duì)4. 設(shè)某散列表的長(zhǎng)度為100，散列函數(shù)H(k)=k % P，則P通常情況下最好選擇（B ）。(A) 99(B) 97(C) 91(D) 935. 在二叉排序樹(shù)中插入一個(gè)關(guān)鍵字值的平均時(shí)間復(fù)雜度為（B）。(A) O(n)(B)

21、O(1og2n)(C) O(nlog2n)(D) O(n2)6. 設(shè)一個(gè)順序有序表A1:14中有14個(gè)元素，則采用二分法查找元素A4的過(guò)程中比較元素的順序?yàn)?C)。(A) A1，A2，A3，A4(B) A1，A14，A7，A4(C) A7，A3，A5，A4(D) A7，A5 ，A3，A47. 設(shè)一棵完全二叉樹(shù)中有65個(gè)結(jié)點(diǎn)，則該完全二叉樹(shù)的深度為（B）。(A) 8(B) 7(C) 6(D) 58. 設(shè)一棵三叉樹(shù)中有2個(gè)度數(shù)為1的結(jié)點(diǎn)，2個(gè)度數(shù)為2的結(jié)點(diǎn)，2個(gè)度數(shù)為3的結(jié)點(diǎn)，則該三叉鏈權(quán)中有（C）個(gè)度數(shù)為0的結(jié)點(diǎn)。(A) 5(B) 6(C) 7(D) 89. 設(shè)無(wú)向圖G中的邊的集合E=(a，b)

22、，(a，e)，(a，c)，(b，e)，(e，d)，(d，f)，(f，c)，則從頂點(diǎn)a出發(fā)進(jìn)行深度優(yōu)先遍歷可以得到的一種頂點(diǎn)序列為（A）。(A) aedfcb(B) acfebd(C) aebcfd(D) aedfbc10. 隊(duì)列是一種（A）的線性表。(A) 先進(jìn)先出(B) 先進(jìn)后出(C) 只能插入(D) 只能刪除 1C2C3C4B5B6C7B8C9A10A1. 棧和隊(duì)列的共同特點(diǎn)是( A )。A.只允許在端點(diǎn)處插入和刪除元素B.都是先進(jìn)后出 C.都是先進(jìn)先出D.沒(méi)有共同點(diǎn) 2. 用鏈接方式存儲(chǔ)的隊(duì)列，在進(jìn)行插入運(yùn)算時(shí)( D ).A. 僅修改頭指針 B. 頭、尾指針都要修改C. 僅修改尾指針 D

23、.頭、尾指針可能都要修改3. 以下數(shù)據(jù)結(jié)構(gòu)中哪一個(gè)是非線性結(jié)構(gòu)？(D )A. 隊(duì)列 B. 棧 C. 線性表 D. 二叉樹(shù)4. 設(shè)有一個(gè)二維數(shù)組Amn，假設(shè)A00存放位置在644(10)，A22存放位置在676(10)，每個(gè)元素占一個(gè)空間，問(wèn)A33(10)存放在什么（C）位置？腳注(10)表示用10進(jìn)制表示。A688 B678 C692 D6965. 樹(shù)最適合用來(lái)表示( C )。A.有序數(shù)據(jù)元素 B.無(wú)序數(shù)據(jù)元素C.元素之間具有分支層次關(guān)系的數(shù)據(jù) D.元素之間無(wú)聯(lián)系的數(shù)據(jù)6. 二叉樹(shù)的第k層的結(jié)點(diǎn)數(shù)最多為(D ).A2k+1 B.2K+1 C.2K-1 D. 2k-17. 若有18個(gè)元素的有序表

24、存放在一維數(shù)組A19中，第一個(gè)元素放A1中，現(xiàn)進(jìn)行二分查找，則查找A3的比較序列的下標(biāo)依次為( D )A. 1，2，3B. 9，5，2，3C. 9，5，3D. 9，4，2，38. 對(duì)n個(gè)記錄的文件進(jìn)行快速排序，所需要的輔助存儲(chǔ)空間大致為（C）A. O（1） B. O（n） C. O（1og2n） D. O（n2）9. 對(duì)于線性表（7，34，55，25，64，46，20，10）進(jìn)行散列存儲(chǔ)時(shí)，若選用H（K）=K %9作為散列函數(shù)，則散列地址為1的元素有（ D）個(gè)，A1 B2 C3 D410. 設(shè)有6個(gè)結(jié)點(diǎn)的無(wú)向圖，該圖至少應(yīng)有( A )條邊才能確保是一個(gè)連通圖。A.5 B.6 C.7 D.81.

25、A 2.D 3.D 4.C 5.C 6.D 7.D 8.C 9.D 10.A 1下列程序段的時(shí)間復(fù)雜度為（A ）。for(i=0； im； i+)for(j=0； jt； j+) cij=0；for(i=0； im； i+)for(j=0； jt； j+)for(k=0； kright=s； s-left=p； p-right-left=s； s-right=p-right；(B) s-left=p；s-right=p-right；p-right=s； p-right-left=s；(C) p-right=s； p-right-left=s； s-left=p； s-right=p-right

26、；(D) s-left=p；s-right=p-right；p-right-left=s； p-right=s；6下列各種排序算法中平均時(shí)間復(fù)雜度為O(n2)是（ D ）。(A) 快速排序(B) 堆排序(C) 歸并排序(D) 冒泡排序7設(shè)輸入序列1、2、3、n經(jīng)過(guò)棧作用后，輸出序列中的第一個(gè)元素是n，則輸出序列中的第i個(gè)輸出元素是（C ）。(A) n-i(B) n-1-i(C) n+l -i(D) 不能確定8設(shè)散列表中有m個(gè)存儲(chǔ)單元，散列函數(shù)H(key)= key % p，則p最好選擇（B）。(A) 小于等于m的最大奇數(shù)(B) 小于等于m的最大素?cái)?shù)(C) 小于等于m的最大偶數(shù)(D) 小于等于m

27、的最大合數(shù)9設(shè)在一棵度數(shù)為3的樹(shù)中，度數(shù)為3的結(jié)點(diǎn)數(shù)有2個(gè)，度數(shù)為2的結(jié)點(diǎn)數(shù)有1個(gè)，度數(shù)為1的結(jié)點(diǎn)數(shù)有2個(gè)，那么度數(shù)為0的結(jié)點(diǎn)數(shù)有（C）個(gè)。(A) 4(B) 5(C) 6(D) 710.設(shè)完全無(wú)向圖中有n個(gè)頂點(diǎn)，則該完全無(wú)向圖中有（A）條邊。 (A) n(n-1)/2(B) n(n-1)(C) n(n+1)/2(D) (n-1)/211.設(shè)順序表的長(zhǎng)度為n，則順序查找的平均比較次數(shù)為（C）。(A) n(B) n/2(C) (n+1)/2(D) (n-1)/212.設(shè)有序表中的元素為(13，18，24，35，47，50，62)，則在其中利用二分法查找值為24的元素需要經(jīng)過(guò)（C）次比較。(A) 1

28、(B) 2(C) 3(D) 413.設(shè)順序線性表的長(zhǎng)度為30，分成5塊，每塊6個(gè)元素，如果采用分塊查找，則其平均查找長(zhǎng)度為（D ）。(A) 6(B) 11(C) 5(D) 6.514.設(shè)有向無(wú)環(huán)圖G中的有向邊集合E=，則下列屬于該有向圖G的一種拓?fù)渑判蛐蛄械氖牵ˋ）。(A) 1，2，3，4(B) 2，3，4，1(C) 1，4，2，3(D) 1，2，4，315.設(shè)有一組初始記錄關(guān)鍵字序列為(34，76，45，18，26，54，92)，則由這組記錄關(guān)鍵字生成的二叉排序樹(shù)的深度為（A）。(A) 4(B) 5(C) 6(D) 71A2A3A4C5D6D7C8B9C10A11C12C13D14A15A1

29、下列程序段的時(shí)間復(fù)雜度為（ A）。i=0，s=0；while (snext=p-next；p-next=-s；(B) q-next=s； s-next=p；(C) p-next=s-next；s-next=p；(D) p-next=s；s-next=q；4設(shè)輸入序列為1、2、3、4、5、6，則通過(guò)棧的作用后可以得到的輸出序列為（B）。(A) 5，3，4，6，1，2(B) 3，2，5，6，4，1(C) 3，1，2，5，4，6(D) 1，5，4，6，2，35設(shè)有一個(gè)10階的下三角矩陣A（包括對(duì)角線），按照從上到下、從左到右的順序存儲(chǔ)到連續(xù)的55個(gè)存儲(chǔ)單元中，每個(gè)數(shù)組元素占1個(gè)字節(jié)的存儲(chǔ)空間，則A5

30、4地址與A00的地址之差為（B）。(A) 10(B) 19(C) 28(D) 556設(shè)一棵m叉樹(shù)中有N1個(gè)度數(shù)為1的結(jié)點(diǎn)，N2個(gè)度數(shù)為2的結(jié)點(diǎn)，Nm個(gè)度數(shù)為m的結(jié)點(diǎn)，則該樹(shù)中共有（D ）個(gè)葉子結(jié)點(diǎn)。(A) (B) (C) (D) 7. 二叉排序樹(shù)中左子樹(shù)上所有結(jié)點(diǎn)的值均（A）根結(jié)點(diǎn)的值。(A) (C) =(D) !=8. 設(shè)一組權(quán)值集合W=(15，3，14，2，6，9，16，17)，要求根據(jù)這些權(quán)值集合構(gòu)造一棵哈夫曼樹(shù)，則這棵哈夫曼樹(shù)的帶權(quán)路徑長(zhǎng)度為（D）。(A) 129(B) 219(C) 189(D) 2299. 設(shè)有n個(gè)關(guān)鍵字具有相同的Hash函數(shù)值，則用線性探測(cè)法把這n個(gè)關(guān)鍵字映射到H

31、ASH表中需要做（D）次線性探測(cè)。(A) n2 (B) n(n+1)(C) n(n+1)/2(D) n(n-1)/210.設(shè)某棵二叉樹(shù)中只有度數(shù)為0和度數(shù)為2的結(jié)點(diǎn)且度數(shù)為0的結(jié)點(diǎn)數(shù)為n，則這棵二叉中共有（C ）個(gè)結(jié)點(diǎn)。(A) 2n(B) n+l(C) 2n-1(D) 2n+l 11.設(shè)一組初始記錄關(guān)鍵字的長(zhǎng)度為8，則最多經(jīng)過(guò)（B）趟插入排序可以得到有序序列。(A) 6(B) 7(C) 8(D) 912.設(shè)一組初始記錄關(guān)鍵字序列為(Q，H，C，Y，P，A，M，S，R，D，F(xiàn)，X)，則按字母升序的第一趟冒泡排序結(jié)束后的結(jié)果是（D ）。(A) F，H，C，D，P，A，M，Q，R，S，Y，X(B)

32、P，A，C，S，Q，D，F(xiàn)，X，R，H，M，Y(C) A，D，C，R，F(xiàn)，Q，M，S，Y，P，H，X(D) H，C，Q，P，A，M，S，R，D，F(xiàn)，X，Y1A2D3B4B5B6D7A8D9D10C11B12D1組成數(shù)據(jù)的基本單位是（C）。 (A) 數(shù)據(jù)項(xiàng) (B) 數(shù)據(jù)類型 (C) 數(shù)據(jù)元素 (D) 數(shù)據(jù)變量2設(shè)數(shù)據(jù)結(jié)構(gòu)A=(D，R)，其中D=1，2，3，4，R=r，r=，則數(shù)據(jù)結(jié)構(gòu)A是（C ）。 (A) 線性結(jié)構(gòu) (B) 樹(shù)型結(jié)構(gòu) (C) 圖型結(jié)構(gòu) (D) 集合3數(shù)組的邏輯結(jié)構(gòu)不同于下列（D）的邏輯結(jié)構(gòu)。 (A) 線性表 (B) 棧 (C) 隊(duì)列 (D) 樹(shù)4二叉樹(shù)中第i(i1)層上的結(jié)點(diǎn)數(shù)最

33、多有（C）個(gè)。 (A) 2i (B) 2i (C) 2i-1 (D) 2i-15設(shè)指針變量p指向單鏈表結(jié)點(diǎn)A，則刪除結(jié)點(diǎn)A的后繼結(jié)點(diǎn)B需要的操作為（A ）。 (A) p-next=p-next-next (B) p=p-next (C) p=p-next-next (D) p-next=p6設(shè)棧S和隊(duì)列Q的初始狀態(tài)為空，元素E1、E2、E3、E4、E5和E6依次通過(guò)棧S，一個(gè)元素出棧后即進(jìn)入隊(duì)列Q，若6個(gè)元素出列的順序?yàn)镋2、E4、E3、E6、E5和E1，則棧S的容量至少應(yīng)該是（C）。 (A) 6 (B) 4 (C) 3 (D) 27將10階對(duì)稱矩陣壓縮存儲(chǔ)到一維數(shù)組A中，則數(shù)組A的長(zhǎng)度最少為

34、（C）。 (A) 100 (B) 40 (C) 55 (D) 808設(shè)結(jié)點(diǎn)A有3個(gè)兄弟結(jié)點(diǎn)且結(jié)點(diǎn)B為結(jié)點(diǎn)A的雙親結(jié)點(diǎn)，則結(jié)點(diǎn)B的度數(shù)數(shù)為（B）。 (A) 3 (B) 4 (C) 5 (D) 19根據(jù)二叉樹(shù)的定義可知二叉樹(shù)共有（B ）種不同的形態(tài)。 (A) 4 (B) 5 (C) 6 (D) 710.設(shè)有以下四種排序方法，則（B）的空間復(fù)雜度最大。 (A) 冒泡排序 (B) 快速排序 (C) 堆排序 (D) 希爾排序1.C 2.C 3.D 4.C 5.A6.C 7.C 8.B 9.B 10.B1下面關(guān)于線性表的敘述錯(cuò)誤的是（D）。 (A) 線性表采用順序存儲(chǔ)必須占用一片連續(xù)的存儲(chǔ)空間(B) 線性

35、表采用鏈?zhǔn)酱鎯?chǔ)不必占用一片連續(xù)的存儲(chǔ)空間(C) 線性表采用鏈?zhǔn)酱鎯?chǔ)便于插入和刪除操作的實(shí)現(xiàn)(D) 線性表采用順序存儲(chǔ)便于插入和刪除操作的實(shí)現(xiàn)2設(shè)哈夫曼樹(shù)中的葉子結(jié)點(diǎn)總數(shù)為m，若用二叉鏈表作為存儲(chǔ)結(jié)構(gòu)，則該哈夫曼樹(shù)中總共有（B）個(gè)空指針域。 (A) 2m-1 (B) 2m (C) 2m+1 (D) 4m3設(shè)順序循環(huán)隊(duì)列Q0：M-1的頭指針和尾指針?lè)謩e為F和R，頭指針F總是指向隊(duì)頭元素的前一位置，尾指針R總是指向隊(duì)尾元素的當(dāng)前位置，則該循環(huán)隊(duì)列中的元素個(gè)數(shù)為（C）。 (A) R-F (B) F-R (C) (R-F+M)M (D) (F-R+M)M4設(shè)某棵二叉樹(shù)的中序遍歷序列為ABCD，前序遍歷序

36、列為CABD，則后序遍歷該二叉樹(shù)得到序列為（A）。 (A) BADC (B) BCDA (C) CDAB (D) CBDA5設(shè)某完全無(wú)向圖中有n個(gè)頂點(diǎn)，則該完全無(wú)向圖中有（A）條邊。 (A) n(n-1)/2 (B) n(n-1) (C) n2 (D) n2-16設(shè)某棵二叉樹(shù)中有2000個(gè)結(jié)點(diǎn)，則該二叉樹(shù)的最小高度為（C）。 (A) 9 (B) 10 (C) 11 (D) 127設(shè)某有向圖中有n個(gè)頂點(diǎn)，則該有向圖對(duì)應(yīng)的鄰接表中有（B）個(gè)表頭結(jié)點(diǎn)。 (A) n-1 (B) n (C) n+1 (D) 2n-18設(shè)一組初始記錄關(guān)鍵字序列(5，2，6，3，8)，以第一個(gè)記錄關(guān)鍵字5為基準(zhǔn)進(jìn)行一趟快速

37、排序的結(jié)果為（C）。 (A) 2，3，5，8，6 (B) 3，2，5，8，6 (C) 3，2，5，6，8 (D) 2，3，6，5，81.D 2.B 3.C 4.A 5.A 6.C 7.B 8.C1設(shè)某數(shù)據(jù)結(jié)構(gòu)的二元組形式表示為A=(D，R)，D=01，02，03，04，05，06，07，08，09，R=r，r=，則數(shù)據(jù)結(jié)構(gòu)A是（B）。 (A) 線性結(jié)構(gòu) (B) 樹(shù)型結(jié)構(gòu) (C) 物理結(jié)構(gòu) (D) 圖型結(jié)構(gòu)2下面程序的時(shí)間復(fù)雜為（B）for（i=1，s=0； i=n； i+）t=1；for(j=1；jnext；p-data=q-data；p-next=q-next；free(q)；(B) q=p

38、-next；q-data=p-data；p-next=q-next；free(q)； (C) q=p-next；p-next=q-next；free(q)； (D) q=p-next；p-data=q-data；free(q)；4設(shè)一組初始關(guān)鍵字記錄關(guān)鍵字為(20，15，14，18，21，36，40，10)，則以20為基準(zhǔn)記錄的一趟快速排序結(jié)束后的結(jié)果為(A)。(A) 10，15，14，18，20，36，40，21 (B) 10，15，14，18，20，40，36，21 (C) 10，15，14，20，18，40，36，2l (D) 15，10，14，18，20，36，40，215設(shè)二叉排序樹(shù)

39、中有n個(gè)結(jié)點(diǎn)，則在二叉排序樹(shù)的平均平均查找長(zhǎng)度為（B）。 (A) O(1) (B) O(log2n) (C) (D) O(n2)6設(shè)無(wú)向圖G中有n個(gè)頂點(diǎn)e條邊，則其對(duì)應(yīng)的鄰接表中的表頭結(jié)點(diǎn)和表結(jié)點(diǎn)的個(gè)數(shù)分別為（D）。 (A) n，e (B) e，n (C) 2n，e (D) n，2e7. 設(shè)某強(qiáng)連通圖中有n個(gè)頂點(diǎn)，則該強(qiáng)連通圖中至少有（C）條邊。 (A) n(n-1) (B) n+1 (C) n (D) n(n+1)8設(shè)有5000個(gè)待排序的記錄關(guān)鍵字，如果需要用最快的方法選出其中最小的10個(gè)記錄關(guān)鍵字，則用下列（B）方法可以達(dá)到此目的。 (A) 快速排序 (B) 堆排序 (C) 歸并排序 (D

40、) 插入排序9.下列四種排序中（D）的空間復(fù)雜度最大。 (A) 插入排序 (B) 冒泡排序 (C) 堆排序 (D) 歸并排序1.B 2.B 3.A4.A5.B 6.D 7.C 8.B 9.D判斷題1調(diào)用一次深度優(yōu)先遍歷可以訪問(wèn)到圖中的所有頂點(diǎn)。（ -）2分塊查找的平均查找長(zhǎng)度不僅與索引表的長(zhǎng)度有關(guān)，而且與塊的長(zhǎng)度有關(guān)。（ / ）3冒泡排序在初始關(guān)鍵字序列為逆序的情況下執(zhí)行的交換次數(shù)最多。（ /）4滿二叉樹(shù)一定是完全二叉樹(shù)，完全二叉樹(shù)不一定是滿二叉樹(shù)。（/ ）5設(shè)一棵二叉樹(shù)的先序序列和后序序列，則能夠唯一確定出該二叉樹(shù)的形狀。（ -）6層次遍歷初始堆可以得到一個(gè)有序的序列。（ - ）7設(shè)一棵樹(shù)T

41、可以轉(zhuǎn)化成二叉樹(shù)BT，則二叉樹(shù)BT中一定沒(méi)有右子樹(shù)。（ /）8線性表的順序存儲(chǔ)結(jié)構(gòu)比鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)更好。（ - ）9中序遍歷二叉排序樹(shù)可以得到一個(gè)有序的序列。（ /）10.快速排序是排序算法中平均性能最好的一種排序。（ /）11不論是入隊(duì)列操作還是入棧操作，在順序存儲(chǔ)結(jié)構(gòu)上都需要考慮“溢出”情況。（ / ）12當(dāng)向二叉排序樹(shù)中插入一個(gè)結(jié)點(diǎn)，則該結(jié)點(diǎn)一定成為葉子結(jié)點(diǎn)。（ /）13設(shè)某堆中有n個(gè)結(jié)點(diǎn)，則在該堆中插入一個(gè)新結(jié)點(diǎn)的時(shí)間復(fù)雜度為O(log2n)。（ / ）14完全二叉樹(shù)中的葉子結(jié)點(diǎn)只可能在最后兩層中出現(xiàn)。（ /）15哈夫曼樹(shù)中沒(méi)有度數(shù)為1的結(jié)點(diǎn)。（/ ）16對(duì)連通圖進(jìn)行深度優(yōu)先遍歷可以訪問(wèn)

42、到該圖中的所有頂點(diǎn)。（ /）17先序遍歷一棵二叉排序樹(shù)得到的結(jié)點(diǎn)序列不一定是有序的序列。（/ ）18由樹(shù)轉(zhuǎn)化成二叉樹(shù)，該二叉樹(shù)的右子樹(shù)不一定為空。（ - ）19線性表中的所有元素都有一個(gè)前驅(qū)元素和后繼元素。（ - ）20.帶權(quán)無(wú)向圖的最小生成樹(shù)是唯一的。（ - ）21. 如果兩個(gè)關(guān)鍵字的值不等但哈希函數(shù)值相等，則稱這兩個(gè)關(guān)鍵字為同義詞。（ / ）22. 設(shè)初始記錄關(guān)鍵字基本有序，則快速排序算法的時(shí)間復(fù)雜度為O(nlog2n)。（ - ）23. 分塊查找的基本思想是首先在索引表中進(jìn)行查找，以便確定給定的關(guān)鍵字可能存在的塊號(hào)，然后再在相應(yīng)的塊內(nèi)進(jìn)行順序查找。（ / ）24. 二維數(shù)組和多維數(shù)組均不

43、是特殊的線性結(jié)構(gòu)。（ - ）25. 向二叉排序樹(shù)中插入一個(gè)結(jié)點(diǎn)需要比較的次數(shù)可能大于該二叉樹(shù)的高度。（ - ）26. 如果某個(gè)有向圖的鄰接表中第i條單鏈表為空，則第i個(gè)頂點(diǎn)的出度為零。（/ ）27. 非空的雙向循環(huán)鏈表中任何結(jié)點(diǎn)的前驅(qū)指針均不為空。（ / ）28. 不論線性表采用順序存儲(chǔ)結(jié)構(gòu)還是鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)，刪除值為X的結(jié)點(diǎn)的時(shí)間復(fù)雜度均為O(n)。（ /）29. 圖的深度優(yōu)先遍歷算法中需要設(shè)置一個(gè)標(biāo)志數(shù)組，以便區(qū)分圖中的每個(gè)頂點(diǎn)是否被訪問(wèn)過(guò)。（/ ）30. 稀疏矩陣的壓縮存儲(chǔ)可以用一個(gè)三元組表來(lái)表示稀疏矩陣中的非0元素。（/ ）31. 有向圖的鄰接表和逆鄰接表中表結(jié)點(diǎn)的個(gè)數(shù)不一定相等。( -

44、 )32. 對(duì)鏈表進(jìn)行插入和刪除操作時(shí)不必移動(dòng)鏈表中結(jié)點(diǎn)。( /)33. 子串“ABC”在主串“AABCABCD”中的位置為2。( / )34. 若一個(gè)葉子結(jié)點(diǎn)是某二叉樹(shù)的中序遍歷序列的最后一個(gè)結(jié)點(diǎn)，則它必是該二叉樹(shù)的先序遍歷序列中的最后一個(gè)結(jié)點(diǎn)。( / )35. 希爾排序算法的時(shí)間復(fù)雜度為O(n2)。( -)36. 用鄰接矩陣作為圖的存儲(chǔ)結(jié)構(gòu)時(shí)，則其所占用的存儲(chǔ)空間與圖中頂點(diǎn)數(shù)無(wú)關(guān)而與圖中邊數(shù)有關(guān)。( -)37. 中序遍歷一棵二叉排序樹(shù)可以得到一個(gè)有序的序列。( / )38. 入棧操作和入隊(duì)列操作在鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)上實(shí)現(xiàn)時(shí)不需要考慮棧溢出的情況。(/ )39. 順序表查找指的是在順序存儲(chǔ)結(jié)構(gòu)上進(jìn)

45、行查找。（- ）40. 堆是完全二叉樹(shù)，完全二叉樹(shù)不一定是堆。（ / ）1錯(cuò)2對(duì)3對(duì)4對(duì)5錯(cuò)6錯(cuò)7對(duì)8錯(cuò)9對(duì)10對(duì)11對(duì)12對(duì)13對(duì)14對(duì)15對(duì)16對(duì)17對(duì)18錯(cuò)19錯(cuò)20錯(cuò)21對(duì)22錯(cuò)23對(duì)24錯(cuò)25錯(cuò)26對(duì)27對(duì)28對(duì)29對(duì)30對(duì)31錯(cuò)32對(duì)33對(duì)34對(duì)35錯(cuò)36錯(cuò)37對(duì)38對(duì)39錯(cuò)40對(duì)填空題1. 了能有效地應(yīng)用HASH查找技術(shù)，必須解決的兩個(gè)問(wèn)題是【構(gòu)造一個(gè)好的HASH函數(shù)】和【確定解決沖突的方法】。2. 序段的功能實(shí)現(xiàn)數(shù)據(jù)x進(jìn)棧，要求在下劃線處填上正確的語(yǔ)句。typedef struct int s100;int top; sqstack;void push(sqstack &sta

46、ck,int x)if (stack.top=m-1) printf(“overflow”);else 【stack.top+】;【stack.sstack.top=x】;3. 中序遍歷二叉排序樹(shù)所得到的序列是【有序】序列（填有序或無(wú)序）。4. 快速排序的最壞時(shí)間復(fù)雜度為【O(n2)】，平均時(shí)間復(fù)雜度為【O(nlog2n)】。5. 設(shè)某棵二叉樹(shù)中度數(shù)為0的結(jié)點(diǎn)數(shù)為N0，度數(shù)為1的結(jié)點(diǎn)數(shù)為N1，則該二叉樹(shù)中度數(shù)為2的結(jié)點(diǎn)數(shù)為【N0-1】；若采用二叉鏈表作為該二叉樹(shù)的存儲(chǔ)結(jié)構(gòu)，則該二叉樹(shù)中共有【2N0+N1】個(gè)空指針域。6. 設(shè)某無(wú)向圖中頂點(diǎn)數(shù)和邊數(shù)分別為n和e，所有頂點(diǎn)的度數(shù)之和為d，則e=【 d/2】。7. 設(shè)一組初始記錄關(guān)鍵字序列為(55，63，44，38，75，80，31，56)，則利用篩選法建立的初始堆為【(31，38，54，56，75，80，55，63)】。8 已知一有向圖的鄰接表存儲(chǔ)結(jié)構(gòu)如下：從頂點(diǎn)1出發(fā)，DFS遍歷的輸出序列是【(1，3，4，5，2)】，BFS遍歷的輸出序列是【(1，3，2，4，5)】。9. 通常從四個(gè)方面評(píng)價(jià)算法的質(zhì)量：【正確性】、【易讀性】、【強(qiáng)壯性】和【高效率】。10.