1、第 1 章 緒論1、填空題1.常見的數據結構有集合，_線性 結構， 樹形結構， 圖形 結構等四種。2.常見的結構有 順序 結構， 鏈式 結構等兩種。3.數據的基本是_數據元素，它在計算機中是作為一個整體來處理的。4.數據結構中的結構是指數據間的邏輯關系，常見的結構可分為兩大類， 線性結構和 非線性結構。2、選擇題1. 算法的計算量的大小稱為計算的（B）。A效率B. 復雜性C. 現實性D. 難度2. 算法的時間復雜度取決于（C ）A問題的規模對B. 待處理數據的初態C. A 和 BD. 以上都不3.計算機算法指的是（1）（c），它必須具備（2）（B） 這三個特性。(1) A計算方法調度方法B.

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

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

4、為2. 在單鏈表中，如果在結點 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 的線性表采用順序結構，在其第 i 個位置刪除一個元素的算法的平均時間復雜度為(C)。(1in)C.O(n)DO(n2)AO(0)BO(1)4. 若長度為 n 的線性表采用順序結構，在其第 i 個位置前一個新元素需要移動的元素個數為(B)。(1in+

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

6、遞增的順序LinkNode *p,*q;/q 指向 p 的前驅q=h;p=h->next; while(p)if(p->data>s->data)/尋找到點位置，sq->next=s; s->next=p;return;elseq=p; (1 分)p=p->next; (1 分)/當表中沒有比 s 大的結點時，s->next=q->next; (2 分)q->next=s; (2 分)到表尾第 3 章 棧和隊列1、填空題1. 棧和隊列在本質上都是線性表。2. 棧的操作特點是 后進先出_。隊列的操作特點是_先進先出 。2、選擇題1.消除

7、遞歸不一定需要使用棧，此說法A。A. 正確B. 錯誤2.用單循環鏈表表示隊列，正確的說法是 B。(A)可設一個頭指針使入隊、出隊都方便； (B)可設一個尾指針使入隊、出隊都方便；(C) 必須設頭尾指針才能使入隊、出隊都方便；(D) 無論如何,只可能使入隊方便。3、題1.棧的特點是先進先出。（ ×）2.可以在隊列的任意位置元素。（ ×）3.如果進棧的序列為（1，2，3，4），則（4，2，3，1）不可能是出棧序列。（）4.在用順序表表示的循環隊列中，可用標志位來區分隊空或隊滿的條件。（）第 4 章 串1、選擇題1. 設有兩個串 p 和 q，求 q 在 p 中首次出現的位置的運算

8、稱作（ B）A連接B模式匹配C求子串D求串長2、題1.空串和空格串是同一個概念，二者沒有區別。（ ×）第 5 章 數組和廣義表1、填空題1.二維數組在內存中一種是 列優先可以有兩種。方式，一種是行 優先，2.設廣義表 L(（），（），（）)。則 head(L)是（）；tail(L)是(（），（）) ；L 的長度是3；L 的深度是3。3.設廣義表 L(（a），（b），（c）)則 head(L)是 （a） ；tail(L)是 (（b），（c）)_。2、選擇題1.在 C 語言中，如果有數組定義 intA89；假定每個整型數據占 2字節，則數組元素 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 語言中，數組的采取的是行優先的方式。（ ）2.廣義表在本質上也是線性表。（×）3.可以用三元組法來壓縮稀疏矩陣。（ ）4. 已知廣義表 A=(a,b,c),(d,e,f), 從A 中取出原子 e 的運算是)head(tail(head(tail(A)。(第 6 章 樹和二叉樹1、填空題1. 一 棵62個 葉 結 點 的 完全 二 叉 樹 , 最 多 有 (1+2+32

10、)+(62-1)=124個結點。2.若規定僅有根的二叉樹的高度為 1，那么高為 h 的完全二叉樹最多有- 2h-1個結點，最少有2(h-1)個結點。3. 設只包含有根結點的二叉樹的高度為 0，則高度為 k 的二叉樹的最大結點數為2(k+1)-1，最小結點數為k+1。4. 設僅包含根結點的二叉樹的高度為 1，則高度為 k 的二叉樹的最大結點數為2k-1，最小結點數為k。2、選擇題1.具有 N 個結點的完全二叉樹的深度是 B。(A) log2N(B) log2N +1(C) log2(2N)(D) log2N -12.設二叉樹的樹根為第一層，則第 i 層上至多有C結點。(C)2i-1(A)1(B)

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

12、（3 分）（2）根據題目所給頻率值，畫出相應的哈夫曼樹。（11 分，每個結點 1 分）01100550145012223272801edf121601c79ab（3）給出各個字符對應的哈夫曼編碼。（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. 設一棵二叉樹的先序遍歷序列為 abcde，中序遍歷序列為 badce，請畫出對應的二叉樹，并寫出對應后序遍歷序列。（15 分）參考如下：(1)畫出二叉樹（10 分）錯一個結點扣

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

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

15、分別為 5，28，7，9，14，23，3，11 次。（1） 請畫出赫夫曼樹（權值小的結點在左邊）。（15 分）（2） 計算該樹的帶權路徑長度。（3 分）：（1）赫夫曼樹構造如下。樹中結點位置正確者，每個 1 分，共15 分。2330（2）該樹的帶權路徑長度為（5+3+7+9）*4+（11+14）*3+（23+28）*2=2733 分5、讀程序寫結果已知二叉樹的結點結構如下：struct Nodeint data;Node *lchild,*rchild;某棵二叉樹的形態如右圖：ABCDE根據要求解答下題：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） 當 root 是指向結點 A 的指針時，函數 fun1 的返回值是多少？(2 分)函數 fun1 的返回值是 3。（2） 函數 fun1 的功能是什么？(3 分) 函數 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） 當 root 是指向結點 A 的指針時，函數 fun1 的返回值是多少？(2 分)函數 fun1 的返回值是 5。（2） 函數 fun1 的功能是什么？(4 分)函數 fun1 的功能是求二叉樹中所有結點的個數第 7 章 圖1、填空題1. 有 n 個頂點的有向連通圖最多有 n(n-1) 條邊，最少有 n條邊。2. 具有 n 個頂點的完全無向圖有n(n-1)/2 條邊，完全有向圖有 n(n-1)條邊。2、選擇題1.B方法可以出一個有向圖中是否有環（回路）。(A)深度優先遍歷 (B)拓撲排序(C)求最短路徑(D)求關鍵路徑2

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

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

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

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

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