數(shù)據(jù)結(jié)構(gòu)2007試卷及答案

1、精選優(yōu)質(zhì)文檔-傾情為你奉上 上 裝 訂 線(xiàn) 院（系）名： 班級(jí)： 姓名： 學(xué)號(hào)： 考生類(lèi)別： 考試日期： 下 裝 訂 線(xiàn) 陜西師范大學(xué)20062007學(xué)年第二學(xué)期期末考試計(jì)算機(jī)科學(xué)學(xué)院2005級(jí)計(jì)算機(jī)科學(xué)專(zhuān)業(yè)數(shù)據(jù)結(jié)構(gòu)題號(hào)一二三四總分分?jǐn)?shù)答卷注意事項(xiàng)： 1、學(xué)生必須用藍(lán)色（或黑色）鋼筆、圓珠筆或簽字筆直接在試題卷上答題。2、答卷前請(qǐng)將密封線(xiàn)內(nèi)的項(xiàng)目填寫(xiě)清楚。 3、字跡要清楚、工整，不宜過(guò)大，以防試卷不夠使用。 4、本卷共 4 大題，總分為100分。得分評(píng)卷人一、選擇題（每題2分 ，共10分）1. 下面程序段的時(shí)間復(fù)雜度為(C)。 for(int i=0;i<m;i+) for(int j=

2、0;j<n;j+) aij=i*j; A、O(m2) B、O(n2) C、O(m×n) D、O(m+n) 2. 一個(gè)棧的輸入序列為1，2，3，4，下面哪一個(gè)序列不可能是這個(gè)棧的輸出序列( C ). A、 1，3，2，4 B、2，3，4，1 C、 4，3，1，2 D、3，4，2，13. 假定一個(gè)順序隊(duì)列的隊(duì)首和隊(duì)尾指針?lè)謩e為1和r，則判斷隊(duì)空的條件為（ D ）A、 f十1= =r B、 r1= =fC、 f= =0 D、 f= =r4. 廣義表( (A , B, E, F , G)的表尾是( B )。A、(B, E , F, G) B、( ) C、（A，B， E，F(xiàn)，G） D、不

3、存在5. 設(shè)有一個(gè)N×N的對(duì)稱(chēng)矩陣A，將其下三角部分以行為主序存入一個(gè)一維數(shù)組B中，A00存入B0中，那么第i行的對(duì)角元素Aii存入于B中的（ A ）處。A、（i+3）×i/2 B、(i+1)×i/2 C、(2N-i+1)×i/2 D、(2N-i-1)×i/2 得分評(píng)卷人二、填空題（每題2分，共10分）1.一棵深度為6的滿(mǎn)二叉樹(shù)中的結(jié)點(diǎn)數(shù)為 63 個(gè)，一棵深度為4的滿(mǎn)四叉樹(shù)中的結(jié)點(diǎn)數(shù)為 85 個(gè)。2. 設(shè)Q0n-1為循環(huán)隊(duì)列，front,rear分別為隊(duì)列的頭，尾，則隊(duì)列中的元素個(gè)數(shù)為 (rear-front+n) MOD n 。3. 已知一棵

4、度為5的樹(shù)中，2度、3度、4度、5度結(jié)點(diǎn)的個(gè)數(shù)依次為1，2，3，4個(gè)，則葉子個(gè)數(shù)為 11 。4. 棧又稱(chēng)為 后進(jìn)先出 表，隊(duì)列又稱(chēng)為 先進(jìn)先出 表。5. 二維數(shù)組A的行下標(biāo)從1到8，列下標(biāo)從1到10，若每個(gè)元素占3個(gè)單元，則該數(shù)組按“以列序?yàn)橹餍颉贝娣艜r(shí)，A58的起始位置是 180 。得分評(píng)卷人三、綜合題（題1-10，每題4分，題11-14，每題6分，共10×4+4×6=64分）1.試寫(xiě)出對(duì)右邊的樹(shù)進(jìn)行先根遍歷、后根遍歷和層次遍歷時(shí)的訪(fǎng)問(wèn)次序。（4分）答案：先根遍歷時(shí)頂點(diǎn)的訪(fǎng)問(wèn)次序：A B E F C D G H I J K后根遍歷時(shí)頂點(diǎn)的訪(fǎng)問(wèn)次序：E F B C I J

5、K H G D A層次遍歷時(shí)頂點(diǎn)的訪(fǎng)問(wèn)次序：A B C D E F G H I J K2. 給定權(quán)值w=(1,3,5,7)，試構(gòu)造一棵哈夫曼樹(shù)。（4分）答案：3. 已知一組關(guān)鍵字為 3，1，2，5，4 ，按表中的元素順序依次插入到一棵初始為空的二叉排序樹(shù)中，畫(huà)出該二叉排序樹(shù)，并求在等概率的情況下查找成功的平均查找長(zhǎng)度。（4分）答案：ASL =（1+2+3+2+3）/ 5= 2.24.試將右圖中的二叉樹(shù)進(jìn)行中序線(xiàn)索化。（4分）答案：5.試分別寫(xiě)出右邊有向圖的深度優(yōu)先搜索遍歷及廣度優(yōu)先搜索遍歷的次序。(假設(shè)從頂點(diǎn)A出發(fā)進(jìn)行搜索) （4分）答案：深度優(yōu)先搜索遍歷的次序：A B C F E或 A E

6、C F B廣度優(yōu)先搜索遍歷的次序：A B E C F或 A E B C F6.已知一棵二叉樹(shù)，其先序序列為a b c d e f g，中序序列為c b d a e g f，試畫(huà)出此棵二叉樹(shù)。（4分）答案：7. 構(gòu)造右邊網(wǎng)的一棵最小生成樹(shù)。（4分）答案：8.請(qǐng)寫(xiě)出下面關(guān)鍵字序列的第一趟和第二趟快速排序(排序是從小到大)后的序列。（4分）49 38 65 97 76 13 27 23答案：23 38 27 13 49 76 97 6523 38 27 13 49 76 97 65 13 23 27 38 49 65 76 979.試將右邊的森林轉(zhuǎn)化為二叉樹(shù)。（4分）答案：10.試畫(huà)出右邊有向圖的鄰

7、接表及逆鄰接表。（4分）答案：鄰接表: 逆鄰接表11.試求AOV-網(wǎng)的關(guān)鍵路徑。（要求給出各事件和活動(dòng)的最早發(fā)生時(shí)間及最晚發(fā)生時(shí)間）（6分）答案：12.已知如下12個(gè)數(shù)據(jù)元素的有序表，現(xiàn)用折半查找的方法查找關(guān)鍵字65的數(shù)據(jù)元素，試畫(huà)出low指針、high指針和mid指針的指向位置。（假設(shè)low指示待查找區(qū)間的下界；high 指示待查找區(qū)間的上界；mid批示區(qū)間的中間位置）（6分）答案：13. 輸入關(guān)鍵字序列16,3,7,11,9,26，給出構(gòu)造一棵平衡二叉樹(shù)的步驟。（6分）答案：14. 假設(shè)哈希表長(zhǎng)度m=11，采用除留余數(shù)法哈希函數(shù)建立如下關(guān)鍵字集合的哈希表： 19, 01, 23, 14,

8、55, 68, 11, 82, 36 （要求采用線(xiàn)性探測(cè)再散列處理沖突），并求在等概率的情況下查找成功的平均查找長(zhǎng)度。（6分）答案：ASL =（4×1+2×2+3×1+5×1+6×1）/9= 22/9得分評(píng)卷人四、算法實(shí)現(xiàn)（每題8分，共16分）1. 試用遞歸算法寫(xiě)出求二叉樹(shù)T的深度算法。（8分）答案：int Depth (BiTree T ) / 返回二叉樹(shù)的深度 if ( !T ) depthval = 0; else depthLeft = Depth( T->lchild ); depthRight= Depth( T->rc

9、hild ); depthval = 1 + (depthLeft > depthRight?depthLeft:depthRight); return depthval;2. 設(shè)C=a1,b1,a2,b2,an,bn為一線(xiàn)性表,采用帶頭結(jié)點(diǎn)的hc單鏈表存放，編寫(xiě)一個(gè)算法，將其拆分為兩個(gè)線(xiàn)性表，使得：A=a1,a2,an，B=b1,b2,bn。（8分）答案：解:設(shè)拆分后的兩個(gè)線(xiàn)性表都用帶頭結(jié)點(diǎn)的單鏈表存放。先建立兩個(gè)頭結(jié)點(diǎn)*ha和*hb，它們用于存放拆分后的線(xiàn)性表A和B,ra和rb分別指向這兩個(gè)單鏈表的表尾，用p指針掃描單鏈表hc，將當(dāng)前結(jié)點(diǎn)*p鏈到ha未尾，p沿next域下移一個(gè)結(jié)點(diǎn)，

10、若不為空，則當(dāng)前結(jié)點(diǎn)*p鏈到hb未尾，p沿next域下移一個(gè)結(jié)點(diǎn)，如此這樣，直到p為空。最后將兩個(gè)尾結(jié)點(diǎn)的next域置空。對(duì)應(yīng)算法如下：void fun(LinkList *hc, LinkList *&ha, LinkList *&hb) LinkList *p=hc->next,*ra,*rb; ha=hc; /*ha的頭結(jié)點(diǎn)利用hc的頭結(jié)點(diǎn)*/ ra=ha; /*ra始終指向ha的末尾結(jié)點(diǎn)*/ hb=(LinkList *)malloc(sizeof(LinkList); /*創(chuàng)建hb頭結(jié)點(diǎn)*/ rb=hb; /*rb始終指向hb的末尾結(jié)點(diǎn)*/while (p!=NULL) ra->next=p