1、 福建農(nóng)林大學(xué)考試試卷評(píng)分標(biāo)準(zhǔn) （a）卷2007 2008 學(xué)年 第 一 學(xué)期課程名稱(chēng)： 數(shù)據(jù)結(jié)構(gòu) 考試時(shí)間： 120分鐘 專(zhuān)業(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、在長(zhǎng)度為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為棧底，變量top表示當(dāng)前棧

2、頂?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ì)列，若f表示當(dāng)前隊(duì)頭元素在數(shù)

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

4、 610、某二叉樹(shù)如圖所示，對(duì)該二叉樹(shù)進(jìn)行先序遍歷，結(jié)點(diǎn)的訪問(wè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ì)圖所示的無(wú)向圖g，從頂點(diǎn)a開(kāi)始，深度優(yōu)先遍歷，可能的頂點(diǎn)訪問(wèn)順序?yàn)椋╠）。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、對(duì)上一題的圖g，從頂點(diǎn)a開(kāi)始，廣度優(yōu)先遍歷，則可能的頂點(diǎn)訪問(wè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，則檢索過(guò)程中k與記錄關(guān)鍵字的比較次數(shù)為（c）。a. 3

6、 b. 4 c. 5 d. 616、設(shè)有一個(gè)用線性探測(cè)法解決沖突得到的散列表（散列函數(shù)：h(key) = key % 11）： 0 1 2 3 4 5 6 7 8 9 101325801617614若要檢索關(guān)鍵字值為14的記錄，探測(cè)（比較）的次數(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, 90, 94 d. 90,

7、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ù)雜度最高的是（a）。a.

8、直接插入排序 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、二叉樹(shù)中，有兩個(gè)孩子的結(jié)點(diǎn)，在中序遍歷序列中，其后繼結(jié)點(diǎn)最多只有一個(gè)。 （×）5、順序存儲(chǔ)結(jié)構(gòu)不僅能用于表示完全二叉樹(shù)，也能表示一般的二叉樹(shù)。 （）6、鄰

9、接表只能用于有向圖的存儲(chǔ)。 （×）7、有向圖不能進(jìn)行深度優(yōu)先搜索。無(wú)向圖不能進(jìn)行廣度優(yōu)先搜索。 （×）8、運(yùn)用折半檢索時(shí)，檢索表中的元素必需以關(guān)鍵字遞增（由小到大）有序排列。 （×）9、散列表中若不存在地址沖突或同義詞，則其成功檢索的平均檢索長(zhǎng)度等于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= s ;2、 棧 作為實(shí)現(xiàn)函

10、數(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 語(yǔ)句；在元素出隊(duì)前，要執(zhí)行 front = (front+1) % n 語(yǔ)句。4、樹(shù)與二叉樹(shù)之間的主要區(qū)別是：二叉樹(shù)各結(jié)點(diǎn)的子樹(shù)區(qū)分為 左子樹(shù) 和 右子樹(shù) 。5、在具有n個(gè)頂點(diǎn)的無(wú)向完全圖中，共有 n(n-1)/2 條邊；而它的生成樹(shù)中，有 n-1 條邊。6、一棵深度為6的滿二叉樹(shù)中，葉子結(jié)點(diǎn)的個(gè)數(shù)為 32 ，分支結(jié)點(diǎn)的個(gè)數(shù)為 31 。7、有由1000個(gè)數(shù)據(jù)元素組成的順序表，

11、假設(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、試分別畫(huà)出下面二叉樹(shù)的二叉鏈表和靜態(tài)二叉鏈表。 datal-childr-child0a1-11b232c-1-13d-144e-1-1二叉鏈表表示正確得2.5，其中，指針表示錯(cuò)誤扣1分，空指針未表達(dá)扣0.5分，缺少1個(gè)結(jié)點(diǎn)扣0.5分

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

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，試寫(xiě)出在元素值為a的結(jié)點(diǎn)（假設(shè)該結(jié)點(diǎn)存在）之后插入元素值為b的結(jié)點(diǎn)（該結(jié)點(diǎn)未建立）的算法過(guò)程。結(jié)點(diǎn)類(lèi)型node已經(jīng)定義，含有存放元素的data域（elemtp類(lèi)型）和指向后繼結(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!=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、以二叉鏈表為存儲(chǔ)結(jié)構(gòu)，寫(xiě)出求二叉樹(shù)中葉子結(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->lp)+leftnumber(bt->rp); / 2分3、以鏈地址法處理沖突建立開(kāi)散列表，設(shè)散列函數(shù)為：h(key)=key%13。試編寫(xiě)在此開(kāi)散列表上實(shí)現(xiàn)動(dòng)態(tài)檢索（即，給定記錄鍵值k，若檢索成功則返回結(jié)點(diǎn)地址；否則以拉鏈法插入新結(jié)點(diǎn)，并返回新結(jié)點(diǎn)的地址）算法的函數(shù)。設(shè)同義詞單鏈表結(jié)點(diǎn)的數(shù)據(jù)類(lèi)型定義如下：typedef struct node elemtp data; / 記錄 keytp key; / 關(guān)鍵字 struct node *next; / 后繼指針listnode;listnode *hashlist_search(listnode *h, keytp k, ele