數(shù)據(jù)結(jié)構(gòu)習(xí)題集和答案

1、第1章 緒論1、填空題1.常見的數(shù)據(jù)結(jié)構(gòu)有集合，_線性_結(jié)構(gòu)，_樹形_結(jié)構(gòu)，_圖形_結(jié)構(gòu)等四種。2.常見的存儲(chǔ)結(jié)構(gòu)有_順序存儲(chǔ)_結(jié)構(gòu)，_鏈?zhǔn)酱鎯?chǔ)_結(jié)構(gòu)等兩種。3.數(shù)據(jù)的基本單位是_數(shù)據(jù)元素_，它在計(jì)算機(jī)中是作為一個(gè)整體來(lái)處理的。4.數(shù)據(jù)結(jié)構(gòu)中的結(jié)構(gòu)是指數(shù)據(jù)間的邏輯關(guān)系，常見的結(jié)構(gòu)可分為兩大類，_線性結(jié)構(gòu)_和_非線性結(jié)構(gòu)_。2、選擇題1. 算法的計(jì)算量的大小稱為計(jì)算的（ B ）。A效率 B. 復(fù)雜性 C. 現(xiàn)實(shí)性 D. 難度2. 算法的時(shí)間復(fù)雜度取決于（C ）A問題的規(guī)模 B. 待處理數(shù)據(jù)的初態(tài) C. A和B D. 以上都不對(duì)3.計(jì)算機(jī)算法指的是（1）（c），它必須具備（2）（B） 這三個(gè)特性。

2、(1) A計(jì)算方法 B. 排序方法 C. 解決問題的步驟序列 D. 調(diào)度方法(2) A可執(zhí)行性、可移植性、可擴(kuò)充性 B. 可執(zhí)行性、確定性、有窮性C. 確定性、有窮性、穩(wěn)定性 D. 易讀性、穩(wěn)定性、安全性 4. 下面關(guān)于算法說(shuō)法錯(cuò)誤的是（ D ）A算法最終必須由計(jì)算機(jī)程序?qū)崿F(xiàn)B.為解決某問題的算法同為該問題編寫的程序含義是相同的C. 算法的可行性是指指令不能有二義性 D. 以上幾個(gè)都是錯(cuò)誤的3、應(yīng)用題1、給出以下算法的時(shí)間復(fù)雜度.void fun(int n)int i=1,k=100;while(i<n)k=k+1;i=i+2; 時(shí)間復(fù)雜度為_O（n）_。2、給出以下算法的時(shí)間復(fù)雜度.

3、void fun2(int n)int i=1,k=100;while(i<n)i=i*10;k=k+1;時(shí)間復(fù)雜度為_O（log n）_。第2章 線性表1、填空題1. 線性表按照存儲(chǔ)結(jié)構(gòu)不同主要有兩種實(shí)現(xiàn)方式，一種是_順序_表，另一種是_鏈_表。2.順序表采用_隨機(jī)_訪問機(jī)制對(duì)數(shù)據(jù)元素進(jìn)行訪問。3.若在單鏈表結(jié)點(diǎn)p的后面插入一個(gè)新的結(jié)點(diǎn)s，則其操作序列為:_s->next=p->next_；_p->next=s_；4.在單向鏈表中，若要?jiǎng)h除某個(gè)結(jié)點(diǎn)p，一般要找到_p的前趨_結(jié)點(diǎn)，才能實(shí)現(xiàn)該操作。2、選擇題1. 將兩個(gè)各有n個(gè)元素的有序表歸并成一個(gè)有序表，其最少的比較次

4、數(shù)是 A 。(A)n    (B)2n1   (C)2n    (D)n-12. 在單鏈表中，如果在結(jié)點(diǎn)p之后插入一個(gè)新結(jié)點(diǎn)s，其操作為 A 。（A）s->next=p->next; p->next=s;（B）p->next=s; s->next=p->next;（C）s->next=p; p->next=s->next;（D）p->next=s; s->next=p;3.若長(zhǎng)度為n的線性表采用順序存儲(chǔ)結(jié)構(gòu)，在其第i個(gè)位置刪除一個(gè)元素的算法

5、的平均時(shí)間復(fù)雜度為(  C  )。(1in)AO(0)    BO(1)    C.O(n)    DO(n2)4. 若長(zhǎng)度為n的線性表采用順序存儲(chǔ)結(jié)構(gòu)，在其第i個(gè)位置前插入一個(gè)新元素需要移動(dòng)的元素個(gè)數(shù)為(  B  )。(1in+1)An-i   Bn-i+1    C. i    Dn-i-13、判斷題1.線性表中每一個(gè)元素都有一個(gè)前驅(qū)和一個(gè)后繼。（ ×

6、）2. 在順序存儲(chǔ)結(jié)構(gòu)中，有時(shí)也存儲(chǔ)數(shù)據(jù)結(jié)構(gòu)中元素之間的關(guān)系。( × )3. 順序存儲(chǔ)方式的優(yōu)點(diǎn)是存儲(chǔ)密度大，插入、刪除運(yùn)算效率高。( × )4、程序設(shè)計(jì)題1、單鏈表的結(jié)點(diǎn)結(jié)構(gòu)定義如下：struct LinkNodeLinkNode *next;int data;請(qǐng)根據(jù)述函數(shù)的功能寫程序。void Insert(LinkNode *h,LinkNode *s)/h指向鏈表的頭結(jié)點(diǎn)（即使鏈表中沒有元素，頭結(jié)點(diǎn)也存在。）/鏈表中元素已經(jīng)遞增有序/函數(shù)功能為將結(jié)點(diǎn)s插入到鏈表h中。插入后鏈表仍然保持遞增的順序LinkNode *p,*q;/q指向p的前驅(qū)q=h;p=h->n

7、ext; while(p)if(p->data>s->data) /尋找到插入點(diǎn)位置，插入sq->next=s; s->next=p; return;elseq=p; (1分)p=p->next; (1分)/當(dāng)表中沒有比s大的結(jié)點(diǎn)時(shí)，插入到表尾s->next=q->next; (2分)q->next=s; (2分)第3章 棧和隊(duì)列1、填空題1.棧和隊(duì)列在本質(zhì)上都是_線性表_。2.棧的操作特點(diǎn)是_后進(jìn)先出_。隊(duì)列的操作特點(diǎn)是_先進(jìn)先出_。2、選擇題1.消除遞歸不一定需要使用棧，此說(shuō)法_A_。 A. 正確    B

8、. 錯(cuò)誤2.用單循環(huán)鏈表表示隊(duì)列，正確的說(shuō)法是 B 。 (A)可設(shè)一個(gè)頭指針使入隊(duì)、出隊(duì)都方便；(B)可設(shè)一個(gè)尾指針使入隊(duì)、出隊(duì)都方便；(C)必須設(shè)頭尾指針才能使入隊(duì)、出隊(duì)都方便；(D)無(wú)論如何,只可能使入隊(duì)方便。3、判斷題1.棧的特點(diǎn)是先進(jìn)先出。（ × ）2.可以在隊(duì)列的任意位置插入元素。（ ×）3.如果進(jìn)棧的序列為（1，2，3，4），則（4，2，3，1）不可能是出棧序列。（） 4.在用順序表表示的循環(huán)隊(duì)列中，可用標(biāo)志位來(lái)區(qū)分隊(duì)空或隊(duì)滿的條件。（） 第4章 串1、選擇題1. 設(shè)有兩個(gè)串p和q，求q在p中首次出現(xiàn)的位置的運(yùn)算稱作（ B ）A連接 B模式匹配 C求子串 D求串

9、長(zhǎng)2、判斷題1.空串和空格串是同一個(gè)概念，二者沒有區(qū)別。（ × ）第5章 數(shù)組和廣義表1、填空題1.二維數(shù)組在內(nèi)存中存儲(chǔ)可以有兩種存儲(chǔ)方式，一種是_行_優(yōu)先存儲(chǔ)，一種是 列 優(yōu)先存儲(chǔ)。2.設(shè)廣義表L(（），（），（）)。則head(L)是  （）   ；tail(L)是  (（），（）) ；L的長(zhǎng)度是  3  ；L的深度是 3 。3.設(shè)廣義表L(（a），（b），（c）)  則head(L)是_（a）_；tail(L)是_(（b），（c）)_。2、選擇題1.在C語(yǔ)言中，如果有數(shù)組定義 i

10、nt A89；假定每個(gè)整型數(shù)據(jù)占2字節(jié)，則數(shù)組元素A44的地址是（ A ）。A. A+80 B. A+76 C.A+82 D.以上都不對(duì)2.廣義表A=（a,b,(c,d),(e,(f,g)）,則下面式子的值為( D   )；    Head(Tail(Head(Tail(Tail(A)A（g）    B.(d)    C.c    D.d3、判斷題1.在C語(yǔ)言中，多維數(shù)組的存儲(chǔ)采取的是行優(yōu)先的方式。（ ）2.廣義表在本質(zhì)上也是線性表。（ 

11、5; ）3.可以用三元組存儲(chǔ)法來(lái)壓縮存儲(chǔ)稀疏矩陣。（ ）4.已知廣義表A=(a,b,c),(d,e,f),從A中取出原子e的運(yùn)算是head(tail(head(tail(A)。 ( )第6章 樹和二叉樹1、填空題1.一棵62個(gè)葉結(jié)點(diǎn)的完全二叉樹,最多有_(1+2+32)+(62-1)=124_個(gè)結(jié)點(diǎn)。2.若規(guī)定僅有根的二叉樹的高度為1，那么高為h的完全二叉樹最多有_2h-1_個(gè)結(jié)點(diǎn)，最少有_2(h-1)_個(gè)結(jié)點(diǎn)。3.設(shè)只包含有根結(jié)點(diǎn)的二叉樹的高度為0，則高度為k的二叉樹的最大結(jié)點(diǎn)數(shù)為_2(k+1)-1_，最小結(jié)點(diǎn)數(shù)為_k+1_。4.設(shè)僅包含根結(jié)點(diǎn)的二叉樹的高度為1，則高度為k的二叉樹的最大結(jié)點(diǎn)

12、數(shù)為_2k-1_，最小結(jié)點(diǎn)數(shù)為_k_。2、選擇題1.具有N個(gè)結(jié)點(diǎn)的完全二叉樹的深度是_B_。(A) log2N (B) log2N +1 (C) log2(2N) (D) log2N -12.設(shè)二叉樹的樹根為第一層，則第i層上至多有_C_結(jié)點(diǎn)。(A)1  (B)2  (C)2i-1  (D)2i-13、判斷題1.二叉樹的左右子樹次序是嚴(yán)格的，不能夠任意改變。（ ）2.若根為第一層，則深度為k的滿二叉樹的結(jié)點(diǎn)為2k-1 。 （ ）3.二叉樹的三叉鏈表存儲(chǔ)結(jié)構(gòu)可以方便的訪問到雙親結(jié)點(diǎn)。 （ ）4、應(yīng)用題1.在一段文字中，共出現(xiàn)a、b、c、d、e、f六種字符，每種字符出

13、現(xiàn)的頻率分別為7,9,12,22,23,27。請(qǐng)回答下列問題：（1）什么是哈夫曼樹？（3分）（2）根據(jù)題目所給頻率值，畫出相應(yīng)的哈夫曼樹。（11分）（3）給出各個(gè)字符對(duì)應(yīng)的哈夫曼編碼。（6分）（4）該段文字經(jīng)過(guò)哈夫曼編碼后，長(zhǎng)度是多少。（4分）參考答案如下：（1）答案為：帶權(quán)路徑長(zhǎng)度最小的二叉樹稱為哈夫曼樹。（3分）（2）根據(jù)題目所給頻率值，畫出相應(yīng)的哈夫曼樹。（11分，每個(gè)結(jié)點(diǎn)1分）fc287912222355162745100abed1000001111（3）給出各個(gè)字符對(duì)應(yīng)的哈夫曼編碼。（6分）a:1110 b:1111 c:110 d:00 e:01 f:10（4）該段文字經(jīng)過(guò)哈夫曼編

14、碼后，長(zhǎng)度是多少。（4分）(7+9)*4+12*3+(22+23+27)*2=244或者100+45+55+28+16=2442. 設(shè)一棵二叉樹的先序遍歷序列為abcde，中序遍歷序列為badce，請(qǐng)畫出對(duì)應(yīng)的二叉樹，并寫出對(duì)應(yīng)后序遍歷序列。（15分）參考答案如下：(1)畫出二叉樹（10分）錯(cuò)一個(gè)結(jié)點(diǎn)扣2分。 abcde（2）后序遍歷序列為：bdeca （5分）3. 通信報(bào)文中出現(xiàn)的字符A、B、C、D、E，在報(bào)文中出現(xiàn)的頻率分別為0.23、0.2、0.32、0.12、0.13，分別給出相應(yīng)字符的哈夫曼編碼（要求畫出哈夫曼樹，并且把權(quán)值小的結(jié)點(diǎn)放在左邊）。（共14分）參考答案如下：為處理方便，關(guān)

15、鍵字都乘以100，為23，20，32，12，13構(gòu)造哈夫曼樹為：（9分,每個(gè)結(jié)點(diǎn)1分）ABDEC010001111004357202325321213所以編碼為：A：01 B：00 C：11 D：100 E：101 （5分，每個(gè)編碼1分）4.請(qǐng)證明對(duì)于任何一棵二叉樹，如果其終端結(jié)點(diǎn)數(shù)為n0，度為2的結(jié)點(diǎn)數(shù)為n2，則n0=n2+1。（10分）證明：令樹中結(jié)點(diǎn)總數(shù)為N，度為1的結(jié)點(diǎn)個(gè)數(shù)為n1。則樹中結(jié)點(diǎn)數(shù)滿足下列公式：n0+n1+n2=N從度的角度來(lái)考慮，滿足下列公式：2n2+n1+1=N從而得證：n0=n2+15.請(qǐng)按照孩子-兄弟表示法，將圖1所示樹轉(zhuǎn)化為二叉樹。（共14分）ACBDEFG圖1&

16、#160;解：ACBDEFG（每個(gè)結(jié)點(diǎn)2分）6.已知某二叉樹的前序遍歷序列為：A B C D E F G和中序遍歷序列為：C B E D A F G。請(qǐng)畫出該二叉樹。答案如下：BCDFGAE7.已知通信聯(lián)絡(luò)中只可能出現(xiàn)A、B、C、D、E、F、G、H共8種字符，其出現(xiàn)次數(shù)分別為5，28，7，9，14，23，3，11次。（1）請(qǐng)畫出赫夫曼樹（權(quán)值小的結(jié)點(diǎn)在左邊）。（15分）（2）計(jì)算該樹的帶權(quán)路徑長(zhǎng)度。（3分）答案：（1）赫夫曼樹構(gòu)造如下。樹中結(jié)點(diǎn)位置正確者，每個(gè)1分，共15分。30141679100422319118355828（2）該樹的帶權(quán)路徑長(zhǎng)度為 （5+3+7+9）*4+（11+14）*

17、3+（23+28）*2=273 3分5、讀程序?qū)懡Y(jié)果ABCDE已知二叉樹的結(jié)點(diǎn)結(jié)構(gòu)如下： struct Nodeint data; Node *lchild,*rchild;某棵二叉樹的形態(tài)如右圖：根據(jù)要求解答下題：1、 (共5分)int fun1(Node *root)if(root=0) return 0; int l,r;l=fun1(root->lchild); r=fun1(root->rchild); if(l>=r) return l+1; else return r+1; （1）當(dāng)root是指向結(jié)點(diǎn)A的指針時(shí)，函數(shù)fun1的返回值是多少？(2分)函數(shù)fun1的

18、返回值是3。（2）函數(shù)fun1的功能是什么？(3分)函數(shù)fun1的功能是求二叉樹的高度。2、 (共6分)int fun2(Node *root)if(root=0) return 0; int l=fun2(root->lchild ); int r=fun2(root->rchild ); return l+r+1; （1）當(dāng)root是指向結(jié)點(diǎn)A的指針時(shí)，函數(shù)fun1的返回值是多少？(2分)函數(shù)fun1的返回值是5。（2）函數(shù)fun1的功能是什么？(4分)函數(shù)fun1的功能是求二叉樹中所有結(jié)點(diǎn)的個(gè)數(shù)第7章 圖1、填空題1. 有n個(gè)頂點(diǎn)的有向連通圖最多有 n(n-1) 條邊，最少有

19、 n 條邊。2.具有n個(gè)頂點(diǎn)的完全無(wú)向圖有_ n(n-1)/2_條邊，完全有向圖有_n(n-1)_條邊。2、選擇題1. _B_方法可以判斷出一個(gè)有向圖中是否有環(huán)（回路）。(A)深度優(yōu)先遍歷 (B)拓?fù)渑判?#160; (C)求最短路徑  (D)求關(guān)鍵路徑2.關(guān)鍵路徑是指_B_。(A)從開始事件到終止事件路徑長(zhǎng)度最短的路徑(B)從開始事件到終止事件路徑長(zhǎng)度最長(zhǎng)的路徑(C)從開始事件到終止事件活動(dòng)最少的路徑   (D)從開始事件到終止事件活動(dòng)最多的路徑 3、判斷題1.具有n個(gè)頂點(diǎn)的有向圖最多有n*(n-1)條邊。 （ ）2.在AOV-網(wǎng)中

20、，不應(yīng)該出現(xiàn)有向環(huán)，因?yàn)榇嬖诃h(huán)就意味著活動(dòng)可以以自己為先決條件。（ ）4、應(yīng)用題1、已知某圖的存儲(chǔ)結(jié)構(gòu)如下，試寫出該圖從頂點(diǎn)A開始的深度優(yōu)先遍歷序列。(11分)ABCDEFGHIJKA01111100000B00000010000C00000001000D00000000100E00000000010F00000000001G01000000000H00100000000I00010000000J00001000000K00000100000答案為：ABGCHDIEJFK (對(duì)一個(gè)1分)2. 請(qǐng)給出圖1的所有最小生成樹。（10分）aebdfc1238665圖1 共兩棵。第一棵為：(5分)錯(cuò)一條

21、邊扣1分。aebdfc12365 第二棵為：(5分)錯(cuò)一條邊扣1分。aebdfc1236653. 已知某圖采取如圖2所示的鄰接矩陣表示法，請(qǐng)回答下列問題。（共12分） 01234561A10110002B21001103C31000114D40100005E50110006F6001000圖2(1) 請(qǐng)畫出該圖。（6分）（2）對(duì)其從頂點(diǎn)A開始進(jìn)行深度優(yōu)先遍歷，寫出遍歷序列。（6分）（1） 請(qǐng)畫出該圖。（6分）錯(cuò)一個(gè)結(jié)點(diǎn)扣1分。ABCEFD（2）對(duì)其從頂點(diǎn)A開始進(jìn)行深度優(yōu)先遍歷，寫出遍歷序列。（6分, 錯(cuò)一個(gè)字符扣1分）序列為：ABDECF4、（本題總計(jì) 7 分）構(gòu)造該圖的最小生成樹。 aefg

22、dbhc21111222243圖的最小生成樹如下 每條邊1分，共7分 aefgdbhc2111122第9章 查找1、選擇題1.若在線性表中采用二分查找法查找元素，該線性表應(yīng)該(  C )。A元素按值有序    B采用順序存儲(chǔ)結(jié)構(gòu)C元素按值有序，且采用順序存儲(chǔ)結(jié)構(gòu)D元素按值有序，且采用鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)2.對(duì)二叉排序樹進(jìn)行_B_遍歷，可以得到該二叉樹所有結(jié)點(diǎn)構(gòu)成的有序序列。(A) 前序   (B)中序   (C)后序   (D)按層次3.利用逐點(diǎn)插入法建立序列(51，71，

23、43，81，74，20，34，45，64，30)對(duì)應(yīng)的二叉排序樹以后，查找元素34要進(jìn)行( A )元素間的比較。 A4次    B5次    C. 7次    D104.對(duì)二叉排序樹進(jìn)行_遍歷，可以得到該二叉樹所有結(jié)點(diǎn)構(gòu)成的有序序列。(A) 前序   (B)中序   (C)后序   (D)按層次5.散列函數(shù)有一個(gè)共同性質(zhì)，即函數(shù)值應(yīng)按(  C )取其值域的每一個(gè)值。A.最大概率 

24、;  B.最小概率   C.同等概率   D.平均概率6.一個(gè)哈希函數(shù)被認(rèn)為是“好的”，如果它滿足條件_A_。(A)哈希地址分布均勻(B)保證不產(chǎn)生沖突(C)所有哈希地址在表長(zhǎng)范圍內(nèi)(D)滿足(B)和(C)7.哈希表的平均查找長(zhǎng)度是_D_的函數(shù)。（A）哈希表的長(zhǎng)度 （B）表中元素的多少（C）哈希函數(shù) （D）哈希表的裝滿程度8.平均查找長(zhǎng)度最短的查找方法是_C_。（A）折半查找 （B）順序查找 （C）哈希查找 （4）其他2、判斷題1.在有序表的查詢過(guò)程中，設(shè)立“哨兵”的作用是為了提高效率。（ ）2.對(duì)于折半查找，其前提條件是待查找序列只要是有序的

25、即可。 （ ）3、應(yīng)用題1.若一棵排序二叉樹的關(guān)鍵字輸入序列為80，6，10，7，8，25，100，90，請(qǐng)畫出該二叉樹。解：二叉排序樹為： （16分，每個(gè)結(jié)點(diǎn)2分）806100901072582.已知一組關(guān)鍵字為1,14,27,29,55,68,10,11,23，則按哈希函數(shù)H(key)=key MOD 13和鏈地址法處理沖突來(lái)構(gòu)造哈希表。（1）畫出所構(gòu)造的哈希表。（2）在記錄的查找概率相等的前提下，計(jì)算該表查找成功時(shí)的平均查找長(zhǎng)度。（1）畫出所構(gòu)造的哈希表。 9個(gè)結(jié)點(diǎn)，每個(gè)1分011142723295568456789101023111112（2）在記錄的查找概率相等的前提下，該表查找成功時(shí)的平均查找長(zhǎng)度，ASL（1×42×33×2）/9=16/9 2分4、程序設(shè)計(jì)題1.已知整型數(shù)組A，從第一個(gè)單元（即A