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

2、(1) A計算方法 B. 排序方法 C. 解決問題的步驟序列 D. 調度方法(2) A可執行性、可移植性、可擴充性 B. 可執行性、確定性、有窮性C. 確定性、有窮性、穩定性 D. 易讀性、穩定性、安全性 4. 下面關于算法說法錯誤的是（ D ）A算法最終必須由計算機程序實現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、給出以下算法的時間復雜度.

3、void fun2(int n)int i=1,k=100;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個元素的有序表歸并成一個有序表，其最少的比較次

4、數是 A 。(A)n    (B)2n1   (C)2n    (D)n-12. 在單鏈表中，如果在結點p之后插入一個新結點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.若長度為n的線性表采用順序存儲結構，在其第i個位置刪除一個元素的算法

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

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

7、ext; 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.消除遞歸不一定需要使用棧，此說法_A_。 A. 正確    B

8、. 錯誤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中首次出現的位置的運算稱作（ B ）A連接 B模式匹配 C求子串 D求串

9、長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語言中，如果有數組定義 i

10、nt A89；假定每個整型數據占2字節，則數組元素A44的地址是（ A ）。A. A+80 B. A+76 C.A+82 D.以上都不對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語言中，多維數組的存儲采取的是行優先的方式。（ ）2.廣義表在本質上也是線性表。（ 

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

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

13、現的頻率分別為7,9,12,22,23,27。請回答下列問題：（1）什么是哈夫曼樹？（3分）（2）根據題目所給頻率值，畫出相應的哈夫曼樹。（11分）（3）給出各個字符對應的哈夫曼編碼。（6分）（4）該段文字經過哈夫曼編碼后，長度是多少。（4分）參考答案如下：（1）答案為：帶權路徑長度最小的二叉樹稱為哈夫曼樹。（3分）（2）根據題目所給頻率值，畫出相應的哈夫曼樹。（11分，每個結點1分）fc287912222355162745100abed1000001111（3）給出各個字符對應的哈夫曼編碼。（6分）a:1110 b:1111 c:110 d:00 e:01 f:10（4）該段文字經過哈夫曼編

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

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

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

17、3+（23+28）*2=273 3分5、讀程序寫結果ABCDE已知二叉樹的結點結構如下： struct Nodeint data; Node *lchild,*rchild;某棵二叉樹的形態如右圖：根據要求解答下題：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）當root是指向結點A的指針時，函數fun1的返回值是多少？(2分)函數fun1的

18、返回值是3。（2）函數fun1的功能是什么？(3分)函數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）當root是指向結點A的指針時，函數fun1的返回值是多少？(2分)函數fun1的返回值是5。（2）函數fun1的功能是什么？(4分)函數fun1的功能是求二叉樹中所有結點的個數第7章 圖1、填空題1. 有n個頂點的有向連通圖最多有 n(n-1) 條邊，最少有

19、 n 條邊。2.具有n個頂點的完全無向圖有_ n(n-1)/2_條邊，完全有向圖有_n(n-1)_條邊。2、選擇題1. _B_方法可以判斷出一個有向圖中是否有環（回路）。(A)深度優先遍歷 (B)拓撲排序  (C)求最短路徑  (D)求關鍵路徑2.關鍵路徑是指_B_。(A)從開始事件到終止事件路徑長度最短的路徑(B)從開始事件到終止事件路徑長度最長的路徑(C)從開始事件到終止事件活動最少的路徑   (D)從開始事件到終止事件活動最多的路徑 3、判斷題1.具有n個頂點的有向圖最多有n*(n-1)條邊。 （ ）2.在AOV-網中

20、，不應該出現有向環，因為存在環就意味著活動可以以自己為先決條件。（ ）4、應用題1、已知某圖的存儲結構如下，試寫出該圖從頂點A開始的深度優先遍歷序列。(11分)ABCDEFGHIJKA01111100000B00000010000C00000001000D00000000100E00000000010F00000000001G01000000000H00100000000I00010000000J00001000000K00000100000答案為：ABGCHDIEJFK (對一個1分)2. 請給出圖1的所有最小生成樹。（10分）aebdfc1238665圖1 共兩棵。第一棵為：(5分)錯一條

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

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

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

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

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