數(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.常見的結(jié)構(gòu)有 順序 結(jié)構(gòu)， 鏈?zhǔn)?結(jié)構(gòu)等兩種。3.數(shù)據(jù)的基本是_數(shù)據(jù)元素，它在計算機(jī)中是作為一個整體來處理的。4.數(shù)據(jù)結(jié)構(gòu)中的結(jié)構(gòu)是指數(shù)據(jù)間的邏輯關(guān)系，常見的結(jié)構(gòu)可分為兩大類， 線性結(jié)構(gòu)和 非線性結(jié)構(gòu)。2、選擇題1. 算法的計算量的大小稱為計算的（B）。A效率B. 復(fù)雜性C. 現(xiàn)實(shí)性D. 難度2. 算法的時間復(fù)雜度取決于（C ）A問題的規(guī)模對B. 待處理數(shù)據(jù)的初態(tài)C. A 和 BD. 以上都不3.計算機(jī)算法指的是（1）（c），它必須具備（2）（B） 這三個特性。(1) A計算方法調(diào)度方法B.

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

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

4、為2. 在單鏈表中，如果在結(jié)點(diǎn) p 之后（A）s->next=p->next; p->next=s;A。（B）p->next=s;（C）s->next=p;（D）p->next=s;s->next=p->next; p->next=s->next;s->next=p;3.若長度為 n 的線性表采用順序結(jié)構(gòu)，在其第 i 個位置刪除一個元素的算法的平均時間復(fù)雜度為(C)。(1in)C.O(n)DO(n2)AO(0)BO(1)4. 若長度為 n 的線性表采用順序結(jié)構(gòu)，在其第 i 個位置前一個新元素需要移動的元素個數(shù)為(B)。(1in+

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

6、遞增的順序LinkNode *p,*q;/q 指向 p 的前驅(qū)q=h;p=h->next; 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)時，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.消除

7、遞歸不一定需要使用棧，此說法A。A. 正確B. 錯誤2.用單循環(huán)鏈表表示隊(duì)列，正確的說法是 B。(A)可設(shè)一個頭指針使入隊(duì)、出隊(duì)都方便； (B)可設(shè)一個尾指針使入隊(duì)、出隊(duì)都方便；(C) 必須設(shè)頭尾指針才能使入隊(duì)、出隊(duì)都方便；(D) 無論如何,只可能使入隊(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)志位來區(qū)分隊(duì)空或隊(duì)滿的條件。（）第 4 章 串1、選擇題1. 設(shè)有兩個串 p 和 q，求 q 在 p 中首次出現(xiàn)的位置的運(yùn)算

8、稱作（ B）A連接B模式匹配C求子串D求串長2、題1.空串和空格串是同一個概念，二者沒有區(qū)別。（ ×）第 5 章 數(shù)組和廣義表1、填空題1.二維數(shù)組在內(nèi)存中一種是 列優(yōu)先可以有兩種。方式，一種是行 優(yōu)先，2.設(shè)廣義表 L(（），（），（）)。則 head(L)是（）；tail(L)是(（），（）) ；L 的長度是3；L 的深度是3。3.設(shè)廣義表 L(（a），（b），（c）)則 head(L)是 （a） ；tail(L)是 (（b），（c）)_。2、選擇題1.在 C 語言中，如果有數(shù)組定義 intA89；假定每個整型數(shù)據(jù)占 2字節(jié)，則數(shù)組元素 A44的地址是（ A）。A. A+80B.

9、 A+76C.A+82D.以上都不對2.廣義表 A=（a,b,(c,d),(e,(f,g)）,則下面式子的值為(D Head(Tail(Head(Tail(Tail(A)；A（g）B.(d)C.cD.d3、題1.在 C 語言中，數(shù)組的采取的是行優(yōu)先的方式。（ ）2.廣義表在本質(zhì)上也是線性表。（×）3.可以用三元組法來壓縮稀疏矩陣。（ ）4. 已知廣義表 A=(a,b,c),(d,e,f), 從A 中取出原子 e 的運(yùn)算是)head(tail(head(tail(A)。(第 6 章 樹和二叉樹1、填空題1. 一 棵62個 葉 結(jié) 點(diǎn) 的 完全 二 叉 樹 , 最 多 有 (1+2+32

10、)+(62-1)=124個結(jié)點(diǎn)。2.若規(guī)定僅有根的二叉樹的高度為 1，那么高為 h 的完全二叉樹最多有- 2h-1個結(jié)點(diǎn)，最少有2(h-1)個結(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)數(shù)為2k-1，最小結(jié)點(diǎn)數(shù)為k。2、選擇題1.具有 N 個結(jié)點(diǎn)的完全二叉樹的深度是 B。(A) log2N(B) log2N +1(C) log2(2N)(D) log2N -12.設(shè)二叉樹的樹根為第一層，則第 i 層上至多有C結(jié)點(diǎn)。(C)2i-1(A)1(B)

11、2(D)2i-13、題1.二叉樹的左右子樹次序是嚴(yán)格的，不能夠任意改變。（ ）2. 若根為第一層， 則深度為 k 的滿二叉樹的結(jié)點(diǎn)為 2k-1 。（ ）3.二叉樹的三叉鏈表結(jié)構(gòu)可以方便的到雙親結(jié)點(diǎn)。（ ）4、應(yīng)用題1.在一段文字中，共出現(xiàn) a、b、c、d、e、f 六種字符，每種字符出現(xiàn)的頻率分別為 7,9,12,22,23,27。請回答下列問題：（1） 什么是哈夫曼樹？（3 分）（2） 根據(jù)題目所給頻率值，畫出相應(yīng)的哈夫曼樹。（11 分）（3） 給出各個字符對應(yīng)的哈夫曼編碼。（6 分）（4） 該段文過哈夫曼編碼后，長度是多少。（4 分）參考（1）如下：為：帶權(quán)路徑長度最小的二叉樹稱為哈夫曼樹。

12、（3 分）（2）根據(jù)題目所給頻率值，畫出相應(yīng)的哈夫曼樹。（11 分，每個結(jié)點(diǎn) 1 分）01100550145012223272801edf121601c79ab（3）給出各個字符對應(yīng)的哈夫曼編碼。（6 分）a:1110b:1111c:110d:00e:01f:10（4）該段文過哈夫曼編碼后，長度是多少。（4 分）(7+9)*4+12*3+(22+23+27)*2=244或者 100+45+55+28+16=2442. 設(shè)一棵二叉樹的先序遍歷序列為 abcde，中序遍歷序列為 badce，請畫出對應(yīng)的二叉樹，并寫出對應(yīng)后序遍歷序列。（15 分）參考如下：(1)畫出二叉樹（10 分）錯一個結(jié)點(diǎn)扣

13、2 分。abcde（2）后序遍歷序列為：bdeca（5 分）3. 通信報文中出現(xiàn)的字符 A、B、C、D、E，在報文中出現(xiàn)的頻率分別為0.23、0.2、0.32、0.12、0.13，分別給出相應(yīng)字符的哈夫曼編碼（要求畫出哈夫曼樹，并且把權(quán)值小的結(jié)點(diǎn)放在左邊）。（共 14 分）參考如下：為處理方便，關(guān)鍵字都乘以 100，為23，20，32，12，13構(gòu)造哈夫曼樹為：（9 分,每個結(jié)點(diǎn) 1 分）100014357010132202325CAB011213DE所以編碼為：A：01編碼 1 分）B：00C：11 D：100E：101（5 分，每個4.請證明對于任何一棵二叉樹，如果其終端結(jié)點(diǎn)數(shù)為 n0，度

14、為 2 的結(jié)點(diǎn)數(shù)為 n2，則 n0=n2+1。（10 分）證明：令樹中結(jié)點(diǎn)總數(shù)為 N，度為 1 的結(jié)點(diǎn)個數(shù)為 n1。則樹中結(jié)點(diǎn)數(shù)滿足下列公式：n0+n1+n2=N從度的角度來考慮，滿足下列公式：2n2+n1+1=N 從而得證：n0=n2+15.請按照孩子-兄弟表示法，將圖 1 所示樹轉(zhuǎn)化為二叉樹。（共 14 分）ACBDEFG圖 1解：ABCDEFG（每個結(jié)點(diǎn) 2 分）6.已知某二叉樹的前序遍歷序列為：A A F G。請畫出該二叉樹。如下：B CD E F G 和中序遍歷序列為：C B E DABFCDG7. 已知通信聯(lián)絡(luò)中只可能出現(xiàn) A、B、C、D、E、F、G、H 共 8 種字符，其出現(xiàn)次數(shù)

15、分別為 5，28，7，9，14，23，3，11 次。（1） 請畫出赫夫曼樹（權(quán)值小的結(jié)點(diǎn)在左邊）。（15 分）（2） 計算該樹的帶權(quán)路徑長度。（3 分）：（1）赫夫曼樹構(gòu)造如下。樹中結(jié)點(diǎn)位置正確者，每個 1 分，共15 分。2330（2）該樹的帶權(quán)路徑長度為（5+3+7+9）*4+（11+14）*3+（23+28）*2=2733 分5、讀程序?qū)懡Y(jié)果已知二叉樹的結(jié)點(diǎn)結(jié)構(gòu)如下：struct Nodeint data;Node *lchild,*rchild;某棵二叉樹的形態(tài)如右圖：ABCDE根據(jù)要求解答下題：1、 (共 5 分)int fun1(Node *root)if(root=0) retu

16、rn 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ù) fun1 的返回值是多少？(2 分)函數(shù) fun1 的返回值是 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

17、(root->rchild ); return l+r+1;（1） 當(dāng) root 是指向結(jié)點(diǎn) A 的指針時，函數(shù) fun1 的返回值是多少？(2 分)函數(shù) fun1 的返回值是 5。（2） 函數(shù) fun1 的功能是什么？(4 分)函數(shù) fun1 的功能是求二叉樹中所有結(jié)點(diǎn)的個數(shù)第 7 章 圖1、填空題1. 有 n 個頂點(diǎn)的有向連通圖最多有 n(n-1) 條邊，最少有 n條邊。2. 具有 n 個頂點(diǎn)的完全無向圖有n(n-1)/2 條邊，完全有向圖有 n(n-1)條邊。2、選擇題1.B方法可以出一個有向圖中是否有環(huán)（回路）。(A)深度優(yōu)先遍歷 (B)拓?fù)渑判?C)求最短路徑(D)求關(guān)鍵路徑2

18、.關(guān)鍵路徑是指B。(A)從開始到終止路徑長度最短的路徑(B)從開始到終止路徑長度最長的路徑(C)從開始到終止活動最少的路徑(D)從開始到終止活動最多的路徑3、題1.具有 n 個頂點(diǎn)的有向圖最多有 n*(n-1)條邊。（ ）2.在 AOV-網(wǎng)中，不應(yīng)該出現(xiàn)有向環(huán)，因?yàn)榇嬖诃h(huán)就意味著活動可以以為先決條件。（ ）4、應(yīng)用題1、已知某圖的列。(11 分)結(jié)構(gòu)如下，試寫出該圖從頂點(diǎn) A 開始的深度優(yōu)先遍歷序ABCDEFGHIJKABCDEFGHIJK為：ABGCHDIEJFK(對一個 1 分)2. 請給出圖 1 的所有最小生成樹。（10 分）26ab35ef1cd68圖 1011111000000000

19、0010000000000010000000000010000000000010000000000010100000000000100000000000100000000000100000000000100000共兩棵。第一棵為：(5 分)錯一條邊扣 1 分。2ab35ef1cd6第二棵為：(5 分)錯一條邊扣 1 分。26ab35ef1cd63. 已知某圖采取如圖 2 所示的鄰接矩陣表示法，請回答下列問題。（共 12分）0123456123456123456011000100110100011010000011000001000ABCDEF圖 2(1) 請畫出該圖。（6 分）（2）對其從頂點(diǎn)

20、 A 開始進(jìn)行深度優(yōu)先遍歷，寫出遍歷序列。（6 分）（1） 請畫出該圖。（6 分）錯一個結(jié)點(diǎn)扣 1 分。ABCDEF（2）對其從頂點(diǎn) A 開始進(jìn)行深度優(yōu)先遍歷，寫出遍歷序列。（6 分, 個字符扣 1 分）序列為：ABDECF錯一4、（本題總計 7 分）構(gòu)造該圖的最小生成樹。 2gbe222211ad314cfh1圖的最小生成樹如下每條邊 1 分，共 7 分beg22211ad1cfh1第 9 章 查找1、選擇題1.若性表中采用二分查找法查找元素，該線性表應(yīng)該(C)。A元素按值有序B采用順序結(jié)構(gòu)C元素按值有序，且采用順序D元素按值有序，且采用鏈?zhǔn)浇Y(jié)構(gòu)結(jié)構(gòu)2.對二叉排序樹進(jìn)行B遍歷，可以得到該二叉

21、樹所有結(jié)點(diǎn)序序列。的有(A) 前序(B)中序(C)后序(D)按層次3.利用逐點(diǎn)法建立序列(51，71，43，81，74，20，34，45，64，30)對應(yīng)的二叉排序樹以后，查找元素 34 要進(jìn)行(A )元素間的比較。A4 次B5 次C. 7 次D104.對二叉排序樹進(jìn)行遍歷，可以得到該二叉樹所有結(jié)點(diǎn)的有序序列。(A) 前序(B)中序(C)后序(D)按層次5.散列函數(shù)有一個共同性質(zhì)，即函數(shù)值應(yīng)按(C )取其值域的每一個值。D.平均概率A.最大概率B.最小概率C.同等概率6.一個哈希函數(shù)被認(rèn)為是“好的”，如果它滿足條件 A 。 (A)哈希地址分布均勻(B) 保證不產(chǎn)生(C) 所有哈希地址在表長范圍

22、內(nèi)(D)滿足(B)和(C)7.哈希表的平均查找長度是D的函數(shù)。（A）哈希表的長度（C）哈希函數(shù)（B）表中元素的多少（D）哈希表的裝滿程度8.平均查找長度最短的查找方法是C。（A）折半查找（B）順序查找 （C）哈希查找 （4）其他2、題1.在有序表的過程中，設(shè)立“哨兵”的作用是為了提高效率。（）2.對于折半查找，其前提條件是待查找序列只要是有序的即可。（）3、應(yīng)用題1.若一棵排序二叉樹的關(guān)鍵字輸入序列為80，6，10，7，8，25，100，90，請畫出該二叉樹。解：二叉排序樹為： （16 分，每個結(jié)點(diǎn) 2 分）801006901072582.已知一組關(guān)鍵字為1,14,27,29,55,68,10,11,23，則按哈希函數(shù) H(key)=keyMOD 13 和鏈地址法處理來構(gòu)造哈希表。（1）畫出所構(gòu)造的哈希表。（2）在的查找概率相等的前提下，計算該表查找時的平均查找長度。（1）畫出所構(gòu)造的哈希表。9 個結(jié)點(diǎn)，每個 1 分0123456789101112（2）在的查找概率相等的前提下，該表查找時的平均 2 分查找長度，ASL（1×42×33×2）/9=16/94、程序設(shè)計題1.已知整型