福建農(nóng)林大學(xué)數(shù)據(jù)結(jié)構(gòu)考試試卷3(附答案)

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

2、頂?shù)奈恢茫ㄏ聵?biāo)），即stop為棧頂元素。則，元素出棧后top應(yīng)做如下（b）的修改。a. top-; b. top+;c. top = n-1; d. top = -1;4、上一題中，棧滿的條件表達式應(yīng)為（c）。a. top=n b. top=n-1c. top=0 d. top=-15、設(shè)棧s和隊列q的初始狀態(tài)為空，元素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、設(shè)有一個大小為m的數(shù)組queue表示循環(huán)隊列，若f表示當(dāng)前隊頭元素在數(shù)

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

4、 610、某二叉樹如圖所示，對該二叉樹進行先序遍歷，結(jié)點的訪問序列為（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個頂點的圖，若采用鄰接矩陣表示，則矩陣中元素的個數(shù)為（d）。a. n b. (n-1)2c. (n+1)2 d. n212、對圖所示的無向圖g，從頂點a開始，深度優(yōu)先遍歷，可能的頂點訪問順序為（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開始，廣度優(yōu)先遍歷，則可能的頂點訪問順序為（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（二維數(shù)組），g中第k個頂點的度為（c）。a. b. c. d. +15、設(shè)檢索表（a1,a2,a3,.,a32）中有32條記錄，且已按關(guān)鍵字遞增有序排列，采用二分法檢索一個與給定的鍵值k相等的記錄，若a1.key<k<a2.key，則檢索過程中k與記錄關(guān)鍵字的比較次數(shù)為（c）。a. 3

6、 b. 4 c. 5 d. 616、設(shè)有一個用線性探測法解決沖突得到的散列表（散列函數(shù)：h(key) = key % 11）： 0 1 2 3 4 5 6 7 8 9 101325801617614若要檢索關(guān)鍵字值為14的記錄，探測（比較）的次數(shù)是（b）。a. 1 b. 6 c. 7 d. 817、用直接插入排序法對下面4個序列進行遞增（由小到大）排序，元素比較次數(shù)最少的是（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種排序算法中，時間復(fù)雜度最高的是（a）。a.

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

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

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

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

12、；靜態(tài)二叉鏈表表達正確得2.5分，其中，每個結(jié)點占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，將元素按其在表中的次序依次插入到一棵初始為空的二叉排序樹中，畫出插入完成后的二叉排序樹。根結(jié)點正確得1分；左子樹包含14, 1, 13，或包含22, 66, 21, 83, 27, 56得1分；右子樹包含22, 66, 21, 83, 27, 56，或包含14, 1, 13得

13、1分；葉子結(jié)點包含13, 21, 56, 83得1分；其它關(guān)系正確得1分。得分五、設(shè)計題（每小題5分，共15分）1、有一個帶頭結(jié)點的單鏈表，已知指向頭結(jié)點的指針hp，試寫出在元素值為a的結(jié)點（假設(shè)該結(jié)點存在）之后插入元素值為b的結(jié)點（該結(jié)點未建立）的算法過程。結(jié)點類型node已經(jīng)定義，含有存放元素的data域（elemtp類型）和指向后繼結(jié)點的指針域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、以二叉鏈表為存儲結(jié)構(gòu)，寫出求二叉樹中葉子結(jié)點數(shù)的算法的遞歸函數(shù)。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、以鏈地址法處理沖突建立開散列表，設(shè)散列函數(shù)為：h(key)=key%13。試編寫在此開散列表上實現(xiàn)動態(tài)檢索（即，給定記錄鍵值k，若檢索成功則返回結(jié)點地址；否則以拉鏈法插入新結(jié)點，并返回新結(jié)點的地址）算法的函數(shù)。設(shè)同義詞單鏈表結(jié)點的數(shù)據(jù)類型定義如下：typedef struct node elemtp data; / 記錄 keytp key; / 關(guān)鍵字 struct node *next; / 后繼指針listnode;listnode *hashlist_search(listnode *h, keytp k, ele