數(shù)據(jù)結(jié)構(gòu)—試題A答案

1、2008級(jí)計(jì)算機(jī)、軟件、網(wǎng)絡(luò)專業(yè) 2009 2010學(xué)年 第一學(xué)期數(shù)據(jù)結(jié)構(gòu)期末試題答案及評(píng)分標(biāo)準(zhǔn)（A卷）一、填空題（20空X 1分=20分）1 數(shù)據(jù)項(xiàng)、數(shù)據(jù)元素；2. s->next=rear->next; rear->next=s； rear=s； q=rear->next->next; rear->next->next=q->next; delete q； 3棧;4.后進(jìn)先出，先進(jìn)先出，對(duì)插入和刪除操作限定的位置不同；5修改，順序存儲(chǔ)；6. （n 1）/2 , （n -1）/2 ；7前序，棧；8. 1, 7；9. O（nlog2），O（n2）

2、；10. 3， 5。二、選擇題（10題X 2分=20分）1. C； 2. A； 3. B； 4. C； 5. B； 6. B； 7. D； 8. D； 9. A； 10. D。三、判斷題（10題X 1分=10分）1.對(duì)；2.錯(cuò)；3.錯(cuò)；4.錯(cuò)；5.對(duì)；6.對(duì)；7.對(duì)；8.錯(cuò)；9.對(duì)；10.錯(cuò)。四、簡答題（5題X 4分=30分）1.已知二叉樹的中序和后序序列分別為 CBEDAFIGH和CEDBIFHGA，試構(gòu) 造該二叉樹。答：2. 對(duì)給定的一組鍵值 W=（5，2，9，11，8，3，7），試構(gòu)造相應(yīng)的哈夫曼樹, 并計(jì)算它的帶權(quán)路徑長度。答：19915155733o6ba1d3556e62c圖1Q)

3、0©0©(3)6G)b550Q答：按Kruskal算法求最小生成樹的過程如下圖:120。Kruskal算法求其最小生成樹該哈夫曼樹的帶權(quán)路徑長度為 3圖1是一個(gè)無向帶權(quán)圖，用4圖2為帶權(quán)有向圖，求從源點(diǎn)vi到其他各頂點(diǎn)的最短路徑。圖2答：源點(diǎn)Vi到其他頂點(diǎn)的最短路徑源點(diǎn)終占最短路徑最短路徑長度V1V7V1 V77V1V5V1 V511V1V4V1 V7 V413V1V6V1 V7 V4 V616V1V2V1 V7 V222V1V3V1 V7 V4 V6 V3255判斷序列(3, 9, 5, 8, 4, 17, 21, 6)是否為堆，如不是，按照堆排序 思想把它調(diào)整為堆，用圖

4、表示建堆的過程。答：不是堆；調(diào)整為最小堆：3, 4, 5, 6, 9, 17, 21, 8。五、算法設(shè)計(jì)題(2題X 10分=20分)1 以順序表作存儲(chǔ)結(jié)構(gòu)，寫一實(shí)現(xiàn)線性表就地逆置的算法。答：設(shè)順序表的長度為length,具體算法如下：template vclass T>void Reverse(T data, int len gth)for (i=0; i<=le ngth/2; i+)temp=datai;datai=datale ngth-i-1; datale ngth-i-1=temp;2插入排序的基本思想是：每趟從無序區(qū)中取出一個(gè)元素，再按鍵值大小插入到有序區(qū) 中。對(duì)于有

5、序區(qū)，當(dāng)然可以采用折半查找來確定插入位置。具體算法如下：void StraightSort(int r , int n) for (i=2;i<=n ;i+) r0=ri;low=1; high=i-1;flag=1;while(low<=high&&flag) mid=(low+high)/2; if(r0<rmid) high=mid-1;else if(r0>rmid) low=mid+1;else flag=0;for(j=i-1;j>=mid;j-)rj+1=rj;rmid=r0;3設(shè)計(jì)算法按前序次序打印輸出二叉樹中的葉子結(jié)點(diǎn) 答：算法如下：void PreOrder(BiNode *root)if (root) if(!root->lchild && !root->rchil