1、 福建農林大學考試試卷評分標準 （a）卷2007 2008 學年 第 一 學期課程名稱： 數據結構 考試時間： 120分鐘 專業 年級 班 學號 姓名 題號一二三四五總得分得分評卷人簽字復核人簽字得分一、選擇題（每小題1分，共20分）1、用鏈表表示線性表的優點是（c）。a. 便于隨機存取 b. 存儲的密度較高c. 便于元素的插入和刪除操作 d. 元素的物理順序與邏輯順序一致2、在長度為n的順序表中，向第k個元素（1kn+1）之前插入一個新元素時，需向后移動（b）個元素。a. n-1 b. n-k+1 c. n-k-1 d. k3、設用一維數組s存儲一個棧，令sn-1為棧底，變量top表示當前棧

2、頂的位置（下標），即stop為棧頂元素。則，元素出棧后top應做如下（b）的修改。a. top-; b. top+;c. top = n-1; d. top = -1;4、上一題中，棧滿的條件表達式應為（c）。a. top=n b. top=n-1c. top=0 d. top=-15、設棧s和隊列q的初始狀態為空，元素e1,e2,e3,e4,e5,e6先后進入棧s，一個元素出棧后即進入隊列q，若6個元素的出隊順序是e2,e4,e3,e6,e5,e1，則棧s至少可以容納（a）個元素。a. 3 b. 4 c. 5 d. 66、設有一個大小為m的數組queue表示循環隊列，若f表示當前隊頭元素在數

3、組中的位置，r表示隊尾元素的后一位置（按順時針方向），則計算隊列中元素個數的表達式為（d）。a. r-f b. (m-f-r) % mc. (m+f-r) % m d. (m+r-f) % m7、深度為5的二叉樹至多有（b）個結點。a. 30 b. 31 c. 32 d. 638、設二叉樹中任一結點的值大于它的左子樹中每個結點的值，而小于右子樹中每個結點的值，即是一個二叉排序樹。若要獲取該二叉樹中所有結點的值的遞增序列，應采用下列（b）的方法遍歷二叉樹。a. 先序遍歷 b. 中序遍歷c. 后序遍歷 d. 層序遍歷9、由3個結點可以構成（c）棵形態不同的二叉樹。a. 3 b. 4 c. 5 d.

4、 610、某二叉樹如圖所示，對該二叉樹進行先序遍歷，結點的訪問序列為（b）。a. 1, 2, 3, 4, 5, 6, 7b. 1, 2, 4, 6, 7, 3, 5c. 2, 6, 4, 7, 1, 5, 3d. 6, 7, 4, 2, 5, 3, 111、對于一個具有n個頂點的圖，若采用鄰接矩陣表示，則矩陣中元素的個數為（d）。a. n b. (n-1)2c. (n+1)2 d. n212、對圖所示的無向圖g，從頂點a開始，深度優先遍歷，可能的頂點訪問順序為（d）。a. a, b, e, c, d, fb. a, c, f, e, b, dc. a, b, c, d, e, fd. a, c

5、, f, d, e, b13、對上一題的圖g，從頂點a開始，廣度優先遍歷，則可能的頂點訪問順序為（a）。a. a, b, e, c, d, f b. a, c, b, d, e, fc. a, b, c, d, e, f d. a, c, f, e, b, d14、有向圖g有n個頂點，其鄰接矩陣為a（二維數組），g中第k個頂點的度為（c）。a. b. c. d. +15、設檢索表（a1,a2,a3,.,a32）中有32條記錄，且已按關鍵字遞增有序排列，采用二分法檢索一個與給定的鍵值k相等的記錄，若a1.key<k<a2.key，則檢索過程中k與記錄關鍵字的比較次數為（c）。a. 3

6、 b. 4 c. 5 d. 616、設有一個用線性探測法解決沖突得到的散列表（散列函數：h(key) = key % 11）： 0 1 2 3 4 5 6 7 8 9 101325801617614若要檢索關鍵字值為14的記錄，探測（比較）的次數是（b）。a. 1 b. 6 c. 7 d. 817、用直接插入排序法對下面4個序列進行遞增（由小到大）排序，元素比較次數最少的是（c）。a. 94, 32, 40, 90, 80, 46, 21, 69 b. 32, 40, 21, 46, 69, 94, 90, 80c. 21, 32, 46, 40, 80, 69, 90, 94 d. 90,

7、69, 80, 46, 21, 32, 94, 4018、對10個記錄的序列：48, 37, 65, 93, 72, 16, 27, 50, 9, 53進行排序，采用初始間隔為5的希爾排序，一趟之后序列的次序是（d）。a. 37, 48, 65, 93, 16, 72, 27, 50, 9, 53 b. 37, 48, 65, 16, 72, 27, 50, 9, 53, 93c. 9, 37, 27, 16, 48, 72, 93, 50, 65, 53 d. 16, 27, 50, 9, 53, 48, 37, 65, 93, 7219、以下4種排序算法中，時間復雜度最高的是（a）。a.

8、直接插入排序 b. 歸并排序c. 快速排序 d. 堆排序20、以下4種排序算法中，需要附加的內存空間最大的是（d）。a. 插入排序 b. 選擇排序c. 快速排序 d. 歸并排序得分二、判斷題（每小題2分，共20分。正確的在括號內打“”，錯誤的打“×”）1、線性表的鏈式存儲結構優于順序存儲結構。 （×）2、一個n維數組可以視為其數據元素是n-1維的線性表。 （）3、空棧就是所有元素都為0的棧。 （×）4、二叉樹中，有兩個孩子的結點，在中序遍歷序列中，其后繼結點最多只有一個。 （×）5、順序存儲結構不僅能用于表示完全二叉樹，也能表示一般的二叉樹。 （）6、鄰

9、接表只能用于有向圖的存儲。 （×）7、有向圖不能進行深度優先搜索。無向圖不能進行廣度優先搜索。 （×）8、運用折半檢索時，檢索表中的元素必需以關鍵字遞增（由小到大）有序排列。 （×）9、散列表中若不存在地址沖突或同義詞，則其成功檢索的平均檢索長度等于1。 （）10、對n個元素的集合進行堆排序時，需要的輔助存儲空間為o(n)。 （×）得分三、填空題（每個填空2分，共30分）1、在一個單鏈表中，在指針p所指向的結點之后插入指針s所指向的結點時，應執行如下操作：s->next= p->next ; p->next= s ;2、 棧 作為實現函

10、數遞歸調用的數據結構。 隊列 作為打印緩沖區的數據結構。3、n個結點的循環隊列中，front指示當前隊頭的前一個位置（下標），rear指示當前隊尾的位置。那么，在元素入隊前，要執行 rear = (rear+1) % n 語句；在元素出隊前，要執行 front = (front+1) % n 語句。4、樹與二叉樹之間的主要區別是：二叉樹各結點的子樹區分為 左子樹 和 右子樹 。5、在具有n個頂點的無向完全圖中，共有 n(n-1)/2 條邊；而它的生成樹中，有 n-1 條邊。6、一棵深度為6的滿二叉樹中，葉子結點的個數為 32 ，分支結點的個數為 31 。7、有由1000個數據元素組成的順序表，

11、假設一次比較表中關鍵字所需的時間為0.5毫秒。則在機會均等的情況下順序檢索，成功檢索一個元素的平均用時為 250.25 毫秒。8、快速排序算法在一般情況下的時間復雜度為o(nlog2n) ；最壞情況下為 o(n2) 。 / 第2小題填 棧存儲結構 和 隊列存儲結構 得一半分 / 第8小題填 nlog2n 和 n2 得一半分得分四、應用題（每小題5分，共15分）1、試分別畫出下面二叉樹的二叉鏈表和靜態二叉鏈表。 datal-childr-child0a1-11b232c-1-13d-144e-1-1二叉鏈表表示正確得2.5，其中，指針表示錯誤扣1分，空指針未表達扣0.5分，缺少1個結點扣0.5分

12、；靜態二叉鏈表表達正確得2.5分，其中，每個結點占0.5分，未表示元素存儲位置扣1分。2、有向圖g如圖所示，頂點的次序依次為a, b, c, d, e，試寫出該圖的鄰接矩陣。 或： 矩陣5行5列，每行正確各得1分，共5分。3、已知順序表中存儲的序列19, 14, 22, 1, 66, 21, 83, 27, 56, 13，將元素按其在表中的次序依次插入到一棵初始為空的二叉排序樹中，畫出插入完成后的二叉排序樹。根結點正確得1分；左子樹包含14, 1, 13，或包含22, 66, 21, 83, 27, 56得1分；右子樹包含22, 66, 21, 83, 27, 56，或包含14, 1, 13得

13、1分；葉子結點包含13, 21, 56, 83得1分；其它關系正確得1分。得分五、設計題（每小題5分，共15分）1、有一個帶頭結點的單鏈表，已知指向頭結點的指針hp，試寫出在元素值為a的結點（假設該結點存在）之后插入元素值為b的結點（該結點未建立）的算法過程。結點類型node已經定義，含有存放元素的data域（elemtp類型）和指向后繼結點的指針域next。void insert(node *hp, elemtp a, elemtp b) / 1分 node *p, *q; / 0.5分 p=hp->next; / 0.5分 while(p->data!=a) p = p->

14、;next; / 1分 q = new node; / 0.5分 q->data=b; / 0.5分 q->next=p->next; / 0.5分 p->next=q; / 0.5分2、以二叉鏈表為存儲結構，寫出求二叉樹中葉子結點數的算法的遞歸函數。int leafnumber(bitree *bt); / 1分 if (bt=null) return 0; / 1分 if (bt->lp=nulll)&&(bt->rp=null) return 1; / 1分 return leftnumber(bt->lp)+leftnumber(bt->rp); / 2分3、以鏈地址法處理沖突建立開散列表，設散列函數為：h(key)=key%13。試編寫在此開散列表上實現動態檢索（即，給定記錄鍵值k，若檢索成功則返回結點地址；否則以拉鏈法插入新結點，并返回新結點的地址）算法的函數。設同義詞單鏈表結點的數據類型定義如下：typedef struct node elemtp data; / 記錄 keytp key; / 關鍵字 struct node *next; / 后繼指針listnode;listnode *hashlist_search(listnode *h, keytp k, ele