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

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

2、棧底，變量top表示當(dāng)前棧頂?shù)奈恢茫ㄏ聵?biāo)），即Stop為棧頂元素。則，元素出棧后top應(yīng)做如下（B）的修改。A. top-; B. top+;C. top = n-1; D. top = -1;4、上一題中，棧滿的條件表達(dá)式應(yīng)為（C）。A. top=n B. top=n-1C. top=0 D. top=-15、設(shè)棧S和隊(duì)列Q的初始狀態(tài)為空，元素e1,e2,e3,e4,e5,e6先后進(jìn)入棧S，一個(gè)元素出棧后即進(jìn)入隊(duì)列Q，若6個(gè)元素的出隊(duì)順序是e2,e4,e3,e6,e5,e1，則棧S至少可以容納（A）個(gè)元素。A. 3 B. 4 C. 5 D. 66、設(shè)有一個(gè)大小為m的數(shù)組queue表示循環(huán)隊(duì)列

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

4、 B. 4 C. 5 D. 610、某二叉樹如圖所示，對(duì)該二叉樹進(jìn)行先序遍歷，結(jié)點(diǎn)的訪問序列為（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、對(duì)于一個(gè)具有n個(gè)頂點(diǎn)的圖，若采用鄰接矩陣表示，則矩陣中元素的個(gè)數(shù)為（D）。A. n B. (n-1)2C. (n+1)2 D. n212、對(duì)圖所示的無向圖G，從頂點(diǎn)A開始，深度優(yōu)先遍歷，可能的頂點(diǎn)訪問順序?yàn)椋―）。A. A, B, E, C, D, FB. A, C, F, E, B, DC. A, B, C, D

5、, E, FD. A, C, F, D, E, B13、對(duì)上一題的圖G，從頂點(diǎn)A開始，廣度優(yōu)先遍歷，則可能的頂點(diǎn)訪問順序?yàn)椋ˋ）。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個(gè)頂點(diǎn)，其鄰接矩陣為A（二維數(shù)組），G中第k個(gè)頂點(diǎn)的度為（C）。A. B. C. D. +15、設(shè)檢索表（a1,a2,a3,.,a32）中有32條記錄，且已按關(guān)鍵字遞增有序排列，采用二分法檢索一個(gè)與給定的鍵值K相等的記錄，若a1.key<K<a2.key，則檢索過程中K與記錄關(guān)鍵字的

6、比較次數(shù)為（C）。A. 3 B. 4 C. 5 D. 616、設(shè)有一個(gè)用線性探測法解決沖突得到的散列表（散列函數(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、用直接插入排序法對(duì)下面4個(gè)序列進(jìn)行遞增（由小到大）排序，元素比較次數(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, 9

7、0, 94 D. 90, 69, 80, 46, 21, 32, 94, 4018、對(duì)10個(gè)記錄的序列：48, 37, 65, 93, 72, 16, 27, 50, 9, 53進(jìn)行排序，采用初始間隔為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種排序算法中，時(shí)間復(fù)

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

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

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

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

12、分，缺少1個(gè)結(jié)點(diǎn)扣0.5分；靜態(tài)二叉鏈表表達(dá)正確得2.5分，其中，每個(gè)結(jié)點(diǎn)占0.5分，未表示元素存儲(chǔ)位置扣1分。2、有向圖G如圖所示，頂點(diǎn)的次序依次為A, B, C, D, E，試寫出該圖的鄰接矩陣。 或： 矩陣5行5列，每行正確各得1分，共5分。3、已知順序表中存儲(chǔ)的序列19, 14, 22, 1, 66, 21, 83, 27, 56, 13，將元素按其在表中的次序依次插入到一棵初始為空的二叉排序樹中，畫出插入完成后的二叉排序樹。根結(jié)點(diǎn)正確得1分；左子樹包含14, 1, 13，或包含22, 66, 21, 83, 27, 56得1分；右子樹包含22, 66, 21, 83, 27, 56，

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

14、=a) p = p->next; / 1分 q = new node; / 0.5分 q->data=b; / 0.5分 q->next=p->next; / 0.5分 p->next=q; / 0.5分2、以二叉鏈表為存儲(chǔ)結(jié)構(gòu)，寫出求二叉樹中葉子結(jié)點(diǎn)數(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->l

15、p)+LeftNumber(bt->rp); / 2分3、以鏈地址法處理沖突建立開散列表，設(shè)散列函數(shù)為：H(key)=key%13。試編寫在此開散列表上實(shí)現(xiàn)動(dòng)態(tài)檢索（即，給定記錄鍵值K，若檢索成功則返回結(jié)點(diǎn)地址；否則以拉鏈法插入新結(jié)點(diǎn)，并返回新結(jié)點(diǎn)的地址）算法的函數(shù)。設(shè)同義詞單鏈表結(jié)點(diǎn)的數(shù)據(jù)類型定義如下：typedef struct node elemtp data; / 記錄 keytp key; / 關(guān)鍵字 struct node *next; / 后繼指針listnode;listnode *hashlist_search(listnode *h, keytp K, elemtp D)