




版權(quán)說明:本文檔由用戶提供并上傳,收益歸屬內(nèi)容提供方,若內(nèi)容存在侵權(quán),請進行舉報或認領(lǐng)
文檔簡介
1、班級: 學(xué)號: 姓名: 裝 訂 線 杭州師范大學(xué)國際服務(wù)工程學(xué)院2008-2009學(xué)年第二學(xué)期期末考試數(shù)據(jù)結(jié)構(gòu)與算法分析試卷(A)題號一二三四五總分得分 注意:請將答案填寫在答題紙上。得分一、選擇(共30分,每小題3分,把最恰當(dāng)?shù)拇鸢割}號填到答題卷上)1. 對于具有n個頂點的連通圖(連通的無向圖), 其最少的邊數(shù)目為 ( ).A. n B. n ( n 1) / 2 C. n + 1 D. n 1 2. 給定某二叉樹的先序遍歷序列為 ABDCEFHG,中序遍歷序列為 BDAFHEGC, 則該二叉樹的后序遍歷序列為 ( ).A. DBAHFGCE B. BDHFGECA C. DBHFGECA
2、D. DBCFHEGA3. 給定某整數(shù)序列為 1,2,3,4,5,9,8,6,7. 現(xiàn)要對其遞增排序,則最快的排序算法為( ), 附助存儲空間要求最多的排序算法為 ( ).A. 直接插入排序 B. 堆排序 C. 歸并排序 D. 起泡排序4. 將m個元素存儲在具有s個單元的哈希表中,則其裝填因子為 ( ).A. s + m B. m / s C. m * s D. m s5. 圖的廣度優(yōu)先搜索與二叉樹的 ( )相類似.A. 先序遍歷 B. 中序遍歷 C. 后序遍歷 D.層次遍歷6. 在下列三種二叉樹中, 對( )中的元素進行中序遍歷結(jié)果得到的序列是有順序的。.A. 堆(heap) B. 二叉搜索
3、樹(binary search tree) C.完全二叉樹 7下列各整數(shù)序列中( )不是堆.A. 100, 85, 98, 77, 80, 60, 82, 40, 20, 10, 66 B. 100, 98, 85, 82, 80, 77, 66, 60, 40, 20, 10C. 10, 20, 40, 60, 66, 77, 80, 82, 85, 98, 100 D. 100, 85, 40, 77, 80, 60, 66, 98, 82, 10, 208. 如果一個棧中的進棧次序為1,2,3,4,n,第一個輸出的元素為n,則第i個輸出的元素為( ).A. n i + 1 B. n i
4、C. i D. 無法確定9一個深度為k的二叉樹的最多的元素個數(shù)為( ).A. 2k + 1 1 B. 2k - 1 C. 2k-1 1 D. 2k +110. 下列( )方法不是哈希表中用于處理沖突的方法.A. 線性探測 B. 鏈地址法 C. 折半查找 D. 二次探測得分二、問答題(共10分,請將答案填到答題卷上)1. 給定某英文文本為“this_is_an_ideal_string”, 采用等長編碼時的總編碼長度為_位, 采用哈夫曼編碼方法時的總編碼長度為_位.(6 分)2. 給定某整數(shù)序列為25, 84, 21, 47, 15, 27, 68, 35, 20, 步長為3的第一輪希爾排序后得
5、到的序列為( 3-sort): 數(shù)據(jù)結(jié)構(gòu)與算法分析試題(第1頁 共3頁)_.(4 分)得分三、問答題(共38分,請將答案填到答題卷上)1. 對于給定的某有向圖(如右圖所示),要求: 寫出每個頂點的入度和出度(2 分) 畫出其鄰接矩陣表示的示意圖; (3 分) 畫出其鄰接表表示的示意圖; (3 分) 畫出其十字鏈表表示的示意圖; (3 分) 畫出其強連通分量; (3 分) 給出從頂點“1”出發(fā)的DFS(深度優(yōu)先搜索)結(jié)果; (2 分) 給出從頂點“2”出發(fā)的BFS(廣度優(yōu)先搜索)結(jié)果. (2 分)2.給定一整數(shù)序列為40, 30, 20, 50, 60, 45, 25, 55, 35, 38.將
6、其依次插入到初始為空的二叉搜索樹(BST: Binary Search Tree)中. 請畫出每個元素插入后的BST示意圖. (10 分)3. 將關(guān)鍵字序列11,5, 29, 20, 0, 27 ,18依次插入表長為9的初始為空的哈希表中,其哈希函數(shù)為hash(k) = k % 9,處理沖突的方法為開放定址法中的線性探測(即di = i).請畫出該哈希表, 并計算查找成功時的平均查找長度(ASL: Average Search Time).(10 分)三、完善程序 (共8分,每空格2分, 將答案填寫在答題卷的相應(yīng)位置)請完成下列圖的深度優(yōu)先搜索算法,在空白處填寫正確的語句。#define MA
7、X_VERTEX_NUM 20typedef struct ArcNodeint adjvex; /該弧所指向的頂點的位置struct ArcNode *nextarc; /指向下一條弧的指針ArcNode;typedef struct VNodeVertexType data; /頂點信息ArcNode *firstarc; /指向第一條依附該頂點的弧的指針VNode,AdjListMAX_VERTEX_NUM;typedef struct AdjList vertices; /圖的當(dāng)前頂點數(shù)和弧數(shù) int vexnum,arcnum; /圖的種類標(biāo)志 int kind;ALGraph;vo
8、id DFSTraverse(ALGraph G) /對圖G作深度優(yōu)先遍歷 for (v = 0;v < G.vexnum;+v) visitedv = _A_; /訪問標(biāo)志數(shù)組初始化 for (v = 0;v < G.vexnum;+v)數(shù)據(jù)結(jié)構(gòu)與算法分析試題(第2頁 共3頁) if (!visitedv) DFS(G,v); /對尚未訪問的頂點調(diào)用DFSvoid DFS(Graph G,int v) visitedv = TRUE; printf("V%d->",G.verticesv.data); for (w = FirstAdjVex(G,v);
9、w;w=NextAdjVex(G,v,w) if (!visitedw) _B_; /對v的尚未訪問的鄰接頂點w遞歸調(diào)用DFSint NextAdjVex(ALGraph G,int v,int w) ArcNode *p; p = G.verticesv.firstarc; while (_C_) p = p->nextarc; if (!(p->nextarc) return -1; else return p->nextarc->adjvex;int FirstAdjVex(ALGraph G,int v)if (!G.verticesv.firstarc)ret
10、urn -1;else return _D_;得分五、編程(14分)假設(shè)某大型網(wǎng)站年終時要產(chǎn)生年度十佳運動員,結(jié)果由網(wǎng)民投票產(chǎn)生。假設(shè)有n個候選運動員(n > 10),有m個網(wǎng)民參加投票,每人一張選票,每張選票選一個且只選一人,每個運動員用兩位十進制數(shù)的號碼表示。請編寫選年度十佳運動員(得票最多者)的程序,并按運動員的得票順序輸出結(jié)果。該程序的輸入是兩個文本文件,其一為保存有n個整數(shù)的文本文件“athlete.txt”,該文件表示n個候選運動員;另一為保存有m個整數(shù)的文本文件“input.txt”,該文件表示m張選票。班級: 學(xué)號: 姓名: 裝 訂 線 杭州師范大學(xué)國際服務(wù)工程學(xué)院200
11、8-2009學(xué)年第二學(xué)期期末考試數(shù)據(jù)結(jié)構(gòu)與算法分析答題卷(A)題號總分得分 得分一、選擇(共30分,每小題3分)1. D2. C3. A C4. B5. D6. A7. D8. A9. B10. C得分二、填空(10 分)(1) _ _位; (2 分) _79_位. (4 分)(2) 3-sort后的整數(shù)序列為: _25,15,20,47,35,21,68,84,27_. (4 分)得分三、問答(38 分)(1) -01234out-degree13121In-degree21302 1 0 2 4 2 1 0 4(2) (3). 0 1 2 3 4 5 6 7 8keys0271129205
12、18ST1212317ASL = (1 + 2 + 1 + 2 + 3 + 1 + 7) / 7 = 17 / 7得分四、完善程序 (8 分) A._FALSE_ B. _DFS(G,w)_C. _p->adjvex != w_ D. _G.verticesv.firstarc->adjvex _得分五、編程 (14 分)#include "stdio.h"#include "stdlib.h"#define MAX_NUMBER 100typedef struct node *pointer_node;typedef struct node
13、 pointer_node llink; int no; int vote; pointer_node rlink;void selectbestsportsman(int n,int m);void selectbestsportsman(int n,int m) pointer_node head = NULL,pre,current; int i,j,votenumber; /用雙向鏈表作為存儲結(jié)構(gòu) /建立雙向鏈表的頭結(jié)點,各運動員的編號從1開始 pre = (pointer_node) malloc(sizeof(node); pre->llink = NULL; pre->
14、;rlink = NULL; pre->no = 0; pre->vote = MAX_NUMBER; head = pre; /分別為每個運動員建立結(jié)點 for (i = 1 ; i <= n;i+) current = (pointer_node) malloc(sizeof(node); current->no = i; current->vote = 0; current->llink = pre; current->rlink = NULL; pre->rlink = current; pre = current; pre = head
15、->rlink; /統(tǒng)計各運動員的得票數(shù),并按運動員的得票數(shù)從高到低進行調(diào)整 printf("請輸入%d張選票n",m); printf("請輸入各選票號碼!(1<=i<=%d)n",n); for (i = 1; i <= m;i+) printf("第%d張選票: ",i); scanf("%d",&votenumber); /判斷選票是否有效 while (votenumber < 1) | (votenumber > n) printf("該選票無效!請
16、重新輸入第%d張選票: ",i); scanf("%d",&votenumber); /找到該運動員的結(jié)點 pre = head->rlink; while (pre) && (pre->no != votenumber) pre = pre->rlink; pre->vote+; /按各運動員的所得票數(shù)從高到你進行調(diào)整 current = pre; pre = current->llink; while (pre != head)&&(pre->vote < current->vote) pre = pre->llink; if (pre->rlink != current) /刪除current結(jié)點 current->rlink->llink = current->llink; current->llink->rlink = current->rlink; /把current結(jié)點插入到pre結(jié)點后 current->rlink = pre->rlink; current->llink = pre;
溫馨提示
- 1. 本站所有資源如無特殊說明,都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請下載最新的WinRAR軟件解壓。
- 2. 本站的文檔不包含任何第三方提供的附件圖紙等,如果需要附件,請聯(lián)系上傳者。文件的所有權(quán)益歸上傳用戶所有。
- 3. 本站RAR壓縮包中若帶圖紙,網(wǎng)頁內(nèi)容里面會有圖紙預(yù)覽,若沒有圖紙預(yù)覽就沒有圖紙。
- 4. 未經(jīng)權(quán)益所有人同意不得將文件中的內(nèi)容挪作商業(yè)或盈利用途。
- 5. 人人文庫網(wǎng)僅提供信息存儲空間,僅對用戶上傳內(nèi)容的表現(xiàn)方式做保護處理,對用戶上傳分享的文檔內(nèi)容本身不做任何修改或編輯,并不能對任何下載內(nèi)容負責(zé)。
- 6. 下載文件中如有侵權(quán)或不適當(dāng)內(nèi)容,請與我們聯(lián)系,我們立即糾正。
- 7. 本站不保證下載資源的準確性、安全性和完整性, 同時也不承擔(dān)用戶因使用這些下載資源對自己和他人造成任何形式的傷害或損失。
最新文檔
- 水城小學(xué)讀書節(jié)活動方案
- 河堤河堤撿垃圾活動方案
- 母嬰問答游戲活動方案
- 畢業(yè)焦慮教育活動方案
- 植樹啟動儀式活動方案
- 武漢奶茶活動方案
- 沙灘晚餐活動方案
- 水電公司成立策劃方案
- 漢中市全民健身活動方案
- 沙龍創(chuàng)意活動方案
- 地下室頂板行車與堆載驗算與加固方案
- 四年級閱讀訓(xùn)練概括文章主要內(nèi)容(完美)
- YY/T 0995-2015人類輔助生殖技術(shù)用醫(yī)療器械術(shù)語和定義
- GB/T 37234-2018文件鑒定通用規(guī)范
- 高中英語讀后續(xù)寫教學(xué)策略的探究
- 2023年鹽城市阜寧縣人民醫(yī)院醫(yī)護人員招聘筆試題庫及答案解析
- 2022年動畫制作行業(yè)分析及未來五至十年行業(yè)發(fā)展報告
- 畢業(yè)論文答辯
- 染缸操作規(guī)范
- 可下載打印的公司章程
- 1p120新產(chǎn)品制造可行性報告
評論
0/150
提交評論