7套《數(shù)據(jù)結(jié)構(gòu)》期末試卷答題紙答案.pdf

第 1 頁(yè) 共 5 頁(yè) 銅 陵 學(xué) 院 2009 2010 學(xué)年第二學(xué)期 數(shù)據(jù)結(jié)構(gòu) 期末考試試卷 A 卷 適用班級(jí) 08 計(jì)算機(jī)本 1 08 計(jì)算機(jī)本 2 08 信息管理與信息系統(tǒng)本 題號(hào) 一 二 三 四 五 總分 統(tǒng)分人 統(tǒng)分復(fù)核人 得分 說明 以下全部試題答案請(qǐng)書寫在答題紙上 答案寫在試卷上無效說明 以下全部試題答案請(qǐng)書寫在答題紙上 答案寫在試卷上無效 得分 閱卷人 復(fù)核人 一 判斷題一 判斷題 本大題共本大題共 10 小題 每小題小題 每小題 1 分 共分 共 10 分分 下列各題 你認(rèn)為正確的 請(qǐng)?jiān)诿款}前面的括號(hào)內(nèi)打 錯(cuò)誤的打 下列各題 你認(rèn)為正確的 請(qǐng)?jiān)诿款}前面的括號(hào)內(nèi)打 錯(cuò)誤的打 1 數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)是數(shù)據(jù)的邏輯結(jié)構(gòu)的存儲(chǔ)映像 2 從循環(huán)單鏈表的任意一個(gè)結(jié)點(diǎn)出發(fā) 可以訪問到該表中的所有結(jié)點(diǎn) 3 棧是一種先進(jìn)先出的線性表 4 因?yàn)樗惴ê统绦驔]有區(qū)別 所以在數(shù)據(jù)結(jié)構(gòu)中二者是通用的 5 對(duì)任意一個(gè)圖 G 從它的某個(gè)頂點(diǎn) Vi出發(fā)進(jìn)行一次深度優(yōu)先或廣度優(yōu)先 搜索遍歷可以訪問到該圖中每個(gè)頂點(diǎn) 6 若將一棵樹 T轉(zhuǎn)換成對(duì)應(yīng)的二叉樹為 BT 則與 T中樹葉結(jié)點(diǎn)所對(duì)應(yīng)的結(jié) 點(diǎn)在 BT中也一定是樹葉結(jié)點(diǎn) 7 堆排序是一種穩(wěn)定排序 其空間復(fù)雜度為 O 1 8 矩陣壓縮存儲(chǔ)的方法是用三元組表存儲(chǔ)矩陣元素 9 設(shè)有主串 p 和子串 q 子串 q 的定位就是在主串 p 中找到一個(gè)與子串 q 相 等的子串 因此定位也稱作模式匹配 10 散列表的查找效率主要取決于散列建表時(shí)所選取的散列函數(shù)和處理沖突 的方法 得分 閱卷人 復(fù)核人 二 填空題填空題 本大題共本大題共 10 小題 每小題小題 每小題 2 分 共分 共 20 分分 請(qǐng)?jiān)诿啃☆}的空格中填上正確答案 錯(cuò)填 不填均不得分 請(qǐng)?jiān)诿啃☆}的空格中填上正確答案 錯(cuò)填 不填均不得分 11 對(duì)于一個(gè)以順序存儲(chǔ)結(jié)構(gòu)實(shí)現(xiàn)的循環(huán)隊(duì)列 Q 0 m 1 隊(duì)頭 隊(duì)尾指針分 別為 front rear 判斷隊(duì)列為空的條件是 12 二分法查找的效率較高 但要求關(guān)鍵字按關(guān)鍵字有序 并且要求表的存儲(chǔ) 為 13 設(shè)二叉樹的樹葉結(jié)點(diǎn)數(shù)為 n0 2度結(jié)點(diǎn)數(shù)為 n2 則二者之間的關(guān)系可表示 為 14 在廣義表中 假設(shè)取表頭運(yùn)算為 head 取表尾運(yùn)算為 tail 廣義表 A a b c d 則 tail head A 15 在一個(gè)單鏈表中 已知 q 結(jié)點(diǎn)是 p 結(jié)點(diǎn)的前驅(qū)結(jié)點(diǎn) 若在 q 和 p 之間插入 s 結(jié)點(diǎn) 則須執(zhí)行 s next p 16 給定樹葉結(jié)點(diǎn)的權(quán)值分別為 1 3 5 7 可以構(gòu)造出其對(duì)應(yīng)的一棵哈夫曼 樹 則該哈夫曼樹的帶權(quán)路徑長(zhǎng)度為 17 下列程序段的時(shí)間復(fù)雜度為 x n n 1 班級(jí) 姓名 學(xué)號(hào) 第 1 裝 線 第 2 裝 線 第 2 頁(yè) 共 5 頁(yè) y 0 while x y 1 y 1 y 18 設(shè)有一個(gè) 10階的對(duì)稱矩陣 A 行下標(biāo)從 1到 10 列下標(biāo)從 1到 10 采用壓 縮存儲(chǔ)方式 以行序?yàn)橹餍蜻M(jìn)行存儲(chǔ) a11為第一個(gè)元素 其存儲(chǔ)地址為 1 每個(gè)元素占有 1個(gè)存儲(chǔ)地址空間 則 a85的地址為 19 設(shè)有向圖 G 應(yīng)用鄰接矩陣 A 1 m 1 m 對(duì)圖 G 進(jìn)行存儲(chǔ) 則鄰接矩陣 A中第 i 行的所有元素之和等于頂點(diǎn) i 的 20 6 個(gè)頂點(diǎn)的連通圖的廣度優(yōu)先生成樹 T 則 T的邊數(shù)為 得分 閱卷人 復(fù)核人 三 單項(xiàng)選擇題三 單項(xiàng)選擇題 本大題共本大題共 10 小題 每小題小題 每小題 2 分 共分 共 20 分分 在每小題給出的四個(gè)備選項(xiàng)中只有一個(gè)是符合題目要求的 請(qǐng)將其代碼填寫在 題后的括號(hào)內(nèi) 錯(cuò)選 多選或未選均不得分 在每小題給出的四個(gè)備選項(xiàng)中只有一個(gè)是符合題目要求的 請(qǐng)將其代碼填寫在 題后的括號(hào)內(nèi) 錯(cuò)選 多選或未選均不得分 21 在文件局部有序的情況下 最好的內(nèi)部排序應(yīng)該是 A 直接插入排序 B 冒泡排序 C 直接選擇排序 D 快速排 序 22 衡量查找算法效率的主要標(biāo)準(zhǔn)是 A 元素個(gè)數(shù) B 平均查找長(zhǎng)度 ASL C 所需的存儲(chǔ)量 D 算法難 易程度 23 如圖 1 所示的 AOV網(wǎng) 不可能出現(xiàn)的拓?fù)湫蛄袨?A 1 2 4 3 5 B 2 4 1 3 5 C 1 2 3 4 5 D 2 1 4 3 5 24 關(guān)于線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)特性 下列描述中正確的是 A 存儲(chǔ)密度大 B 需要連續(xù)的存 儲(chǔ)空間 C 便于隨機(jī)訪問 D 插入和刪除操作靈 活 25 設(shè)有如下遺產(chǎn)繼承規(guī)則 丈夫和妻子可以互相繼承遺產(chǎn) 子女可以繼承父 親或母親的遺產(chǎn) 子女間不能相互繼承 則表示該遺產(chǎn)繼承關(guān)系的最合適 的數(shù)據(jù)結(jié)構(gòu)應(yīng)該是 A 樹 B 圖 C 線性表 D 數(shù)組或 棧 26 已知圖 G 其中 V表示頂點(diǎn)集 E表示邊集 V n E e 在用鄰接表表示圖 G的情況下 建立圖的算法的時(shí)間復(fù)雜度為 A O n 3 B O n 2 C O n e D O n e 圖1圖1 1 2 1 24 5 3 4 5 3 第 3 頁(yè) 共 5 頁(yè) 27 如果某線性表中最常用的操作是在最后一個(gè)元素之后插入一個(gè)元素和刪除 一個(gè)元素 則采用 存儲(chǔ)方式最節(jié)省運(yùn)算時(shí)間 A 單鏈表 B 僅有頭指針的 單循環(huán)鏈表 C 雙鏈表 D 僅有尾 指針的單循環(huán)鏈表 28 在平衡二叉樹中插入一個(gè)結(jié)點(diǎn)后造成了不平衡 設(shè)最低的不平衡結(jié)點(diǎn)為 A 并已知 A的左孩子結(jié)點(diǎn)的平衡因子為 1 右孩子結(jié)點(diǎn)的平衡因子為 0 則應(yīng)作 型調(diào)整以使其平衡 A RR型 B RL型 C LR型 D LL型 29 已知一個(gè)有序表集合為 13 18 24 35 47 50 62 83 90 115 134 應(yīng)用二分法進(jìn)行查找檢索值為 90的元素時(shí) 需要 次比較可以 檢索成功 A 1 B 2 C 3 D 4 30 具有 2000個(gè)結(jié)點(diǎn)的二叉樹 其高度至少為 A 11 B 10 C 9 D 12 得分 閱卷人 復(fù)核人 四 應(yīng)用題四 應(yīng)用題 本大題共本大題共 5 小題 共小題 共 34 分分 31 6 分 設(shè)有一棵二叉樹 T 對(duì) T進(jìn)行中序遍歷 其遍歷序列為 BADCE 對(duì) T進(jìn)行先序遍歷 其遍歷序列為 ABCDE 請(qǐng)畫出該二叉樹 T 若對(duì) T進(jìn) 行后序遍歷 請(qǐng)寫出其遍歷序列 32 6 分 設(shè)散列函數(shù)為 H k k 7 用拉鏈法解決沖突 若關(guān)鍵字的輸 入順序?yàn)?11 80 65 33 34 89 56 51 28 97 請(qǐng)構(gòu)造散列表 并 求在等概率情況下查找成功的平均查找長(zhǎng)度 ASL 33 6 分 給出帶權(quán)圖 G 如圖 2所示 請(qǐng)寫出其鄰接矩陣 并按照克魯斯 卡爾 Kruskal 算法畫出其最小生成樹 T 34 6 分 若以關(guān)鍵字序列中第一個(gè)關(guān)鍵字作為基準(zhǔn) 對(duì)給定的關(guān)鍵字序列 46 55 13 42 94 05 17 70 進(jìn)行速排序 從小至大 請(qǐng)簡(jiǎn)述快 速排序算法的基本思想 并畫出第一趟快速排序過程具體示意圖 圖2圖2 V V1 1V V2 2V V3 3 V V6 6 V V5 5 V V4 4 5 10 812 611 3 5 10 812 611 3 第 4 頁(yè) 共 5 頁(yè) 35 10 分 如圖 3所示的 AOE網(wǎng) 在該網(wǎng)中 頂點(diǎn)表示事件 邊表示活動(dòng) 邊上的權(quán)值表示活動(dòng)持續(xù)的時(shí)間 求各個(gè)事件 Vj的最早發(fā)生時(shí)間 ve j 和最 遲發(fā)生時(shí)間 vl j 活動(dòng) ai的最早開始時(shí)間 e i 和最遲開始時(shí)間 l i 并求出 所有關(guān)鍵路徑 要求 將下列表格填寫完整 寫出所有關(guān)鍵路徑結(jié)果即 可 表 1 事件 Vj的最早發(fā)生時(shí)間 ve j 和最遲發(fā)生時(shí)間 vl j V1 V2 V3 V4 V5 V6 V7 V8 V9 ve j 0 6 4 5 7 16 18 vl j 6 6 8 7 10 16 14 表 2 活動(dòng) ai的最早開始時(shí)間 e i 和最遲開始時(shí)間 l i a1 a2 a3 a4 a5 a6 a7 a8 a9 a10 a11 e i 0 0 6 4 5 7 7 16 14 l i 0 2 3 6 8 7 10 16 14 得分 閱卷人 復(fù)核人 五 算法設(shè)計(jì)題五 算法設(shè)計(jì)題 本大題共本大題共 3 小題 共小題 共 16 分分 在下列算法描述中 要求在每條橫線上僅填寫適當(dāng)?shù)囊粭l語(yǔ)句或一個(gè)表達(dá)式 將 算法描述補(bǔ)充完整 每空 在下列算法描述中 要求在每條橫線上僅填寫適當(dāng)?shù)囊粭l語(yǔ)句或一個(gè)表達(dá)式 將 算法描述補(bǔ)充完整 每空 2 分 分 36 給定一棵用二叉鏈表表示的二叉樹 其根結(jié)點(diǎn)指針為 t 請(qǐng)?jiān)O(shè)計(jì)一個(gè)算法 求 該二叉樹的樹葉結(jié)點(diǎn)數(shù)目 算法描述如下 typedef struct Node ElemType data struct Node Lchild Rchlid BTree int Leaf BTree t 求二叉樹 t 中樹葉結(jié)點(diǎn)數(shù)目的算法 int n m if t NULL 若二叉樹為空 return 0 else n Leaf t Lchild 求左子樹的樹葉結(jié)點(diǎn)數(shù)目 1 2 Leaf 37 有一個(gè)帶頭結(jié)點(diǎn)的單鏈表 寫出在其值為 x 的結(jié)點(diǎn)之后插入 m個(gè)結(jié)點(diǎn)的算 法 算法描述如下 typedef struct Node 結(jié)點(diǎn)構(gòu)造 a a1 1 6 圖3 6 圖3 V V1 1 V V2 2 V V5 5 V V3 3 V V8 8 V V9 9 V V7 7 V V6 6V V4 4 a a2 2 4 a 4 a4 4 1 a 1 a7 7 9 a 9 a10 10 2 a 2 a11 11 4 a 4 a8 8 7 a 7 a5 5 1 a 1 a6 6 2 a 2 a9 9 4 a 4 a3 3 5 5 第 5 頁(yè) 共 5 頁(yè) ElemType data struct Node next LinkList LinkList Insert LinkList head float x int m LinkList p q s int i float b p head next while p NULL if p NULL printf x not found n x else q p next for i 1 i data b 2 3 4 return head Insert 38 請(qǐng)?jiān)O(shè)計(jì)一個(gè)算法 將數(shù)組 a 0 n 1 中所有奇數(shù)移到所有偶數(shù)之前 要求不 另外增加存儲(chǔ)空間 且時(shí)間復(fù)雜度為 O n 算法描述如下 int OddBefore int a int n int i j temp i 0 初始化 i 1 while i j while a i 2 1 while a j 2 0 if i next s 題 號(hào) 16 17 18 19 20 答 案 答 案 29 O n 33 出度 5 說明 說明 1 第 14 題答案寫成 b 不得分 2 第 12 題答案寫成 順序存儲(chǔ) 第 17 題答案寫成 O n1 2 均不扣分 三 單項(xiàng)選擇題 三 單項(xiàng)選擇題 本大題共本大題共 10 小題 每小題小題 每小題 2 分 共分 共 20 分分 在每小題給出的四個(gè)備選項(xiàng)中只有一個(gè)是符合題目要求的 請(qǐng)將其代碼填 寫在題后的括號(hào)內(nèi) 錯(cuò)選 多選或漏選均不得分 在每小題給出的四個(gè)備選項(xiàng)中只有一個(gè)是符合題目要求的 請(qǐng)將其代碼填 寫在題后的括號(hào)內(nèi) 錯(cuò)選 多選或漏選均不得分 題 號(hào) 21 22 23 24 25 26 27 28 29 30 題 號(hào) 21 22 23 24 25 26 27 28 29 30 答 案 A B C D B D D C B A 答 案 A B C D B D D C B A 四 應(yīng)用題四 應(yīng)用題 本大題共本大題共 5 小題 共小題 共 34 分分 31 本小題滿分 6 分 解 后序遍歷序列為 B D E C A 評(píng)分標(biāo)準(zhǔn) 評(píng)分標(biāo)準(zhǔn) 1 正確繪制出該二叉樹 T 圖 1 得 3分 2 正確寫出后序遍歷 再得 3 分 32 本小題滿分 6 分 解 等概率時(shí)查找成功的平均查 找長(zhǎng)度 ASL 1 6 2 4 10 1 4 A A BC D E 圖1 BC D E 圖1 0 2 3 1 4 5 6 5628 6551 80 11 33 34 0 89 97 圖 2 0 2 3 1 4 5 6 5628 6551 80 11 33 34 0 89 97 圖 2 第 2 頁(yè) 共 2 頁(yè) 評(píng)分標(biāo)準(zhǔn) 評(píng)分標(biāo)準(zhǔn) 1 正確構(gòu)造出該散列表 得 3分 2 正確求出平均查找長(zhǎng)度 再得 3分 33 本小題滿分 6分 鄰接矩陣如下圖 3所示 應(yīng)用克魯斯卡爾 Kruskal 算法畫出其最小 生成樹 T 如圖 4所示 其中圓圈中的數(shù)字表示求解步驟 評(píng)分標(biāo)準(zhǔn) 評(píng)分標(biāo)準(zhǔn) 1 正確構(gòu)造出鄰接矩陣 得 3分 正確畫出其最小生成樹 T 再得 3 分 34 本小題滿分 6分 解 算法基本思想 在當(dāng)前無序區(qū) R 1 到 R n 中任取一個(gè)關(guān)鍵字作為比較的 基準(zhǔn) 不妨設(shè)為 temp 用此基準(zhǔn)將當(dāng)前無序區(qū)劃分成左右兩個(gè)較 小的無序子區(qū) R 1 到 R i 1 和 R i 1 到 R n 且左邊的無序子區(qū)中記錄 的關(guān)鍵字均小于或等于基準(zhǔn) temp 的關(guān)鍵字 右邊的無序子區(qū)中記錄的關(guān) 鍵字均大于或等于基準(zhǔn) temp的關(guān)鍵字 而基準(zhǔn) emp 則位于最終排序的位 置上 即 R 1 到 R i 1 中的關(guān)鍵字 temp key R i 1 到 R n 的關(guān)鍵字 1 i n 第一趟快速排序過程示意圖 如圖 5 所示 評(píng)分標(biāo)準(zhǔn) 評(píng)分標(biāo)準(zhǔn) 1 正確寫出算法基本思想 得 3 分 算法思想描述不完整 酌情扣分 2 正確畫出第一趟快速排序過程示意圖 如圖 5 所示 再得 3 分 35 本小題滿分 10 分 表 1 事件 Vj的最早發(fā)生時(shí)間 ve j 和最遲發(fā)生時(shí)間 vl j V1 V2 V3 V4 V5 V6 V7 V8 V9 ve j 0 6 4 5 7 7 7 16 14 14 18 0113 110610 605 308 108012 5120 圖4 圖4 V V1 1V V2 2V V3 3 V V6 6 V V5 5 V V4 4 5 10 8 6 3 5 10 8 6 3 圖 圖 4655139405421770 4655139405421770 ij 4655139405421770 ij 4655139405421770 ij 1755139405424670 ij 1755139405424670 ij 1746139405425570 ij 1746139405425570 ij 1705139446425570 ij 1705139446425570 ij 1705139446425570 ij 1705139446425570 ij 1705139446425570 ij 1705139446425570 ij 17051346 9442 5570 ij 17051346 9442 5570 i j 圖 5 i j 圖 5 第 3 頁(yè) 共 2 頁(yè) vl j 0 0 6 6 8 7 10 16 14 18 18 表 2 活動(dòng) ai的最早開始時(shí)間 e i 和最遲開始時(shí)間 l i a1 a2 a3 a4 a5 a6 a7 a8 a9 a10 a11 e i 0 0 0 0 6 4 5 7 7 7 7 16 14 l i 0 2 3 6 6 6 8 7 7 7 10 16 14 關(guān)鍵路徑為 1 關(guān)鍵路徑為 1 V1 V2 V5 V7 V9 2 2 V1 V2 V5 V8 V9 評(píng)分標(biāo)準(zhǔn) 1 評(píng)分標(biāo)準(zhǔn) 1 正確填寫兩個(gè)表格 每空 1 分 共 8 分 填錯(cuò)或漏填均不得分 2 2 正確寫出關(guān)鍵路徑 每個(gè) 1 分 共 2 分 寫錯(cuò)不得分 五 算法設(shè)計(jì)題 五 算法設(shè)計(jì)題 本大題共本大題共 3 小題 共小題 共 16 分分 在下列算法描述中 要求在每條橫線上填寫適當(dāng)?shù)囊粭l語(yǔ)句或一個(gè)表達(dá)式 將算 法描述補(bǔ)充完整 每空 在下列算法描述中 要求在每條橫線上填寫適當(dāng)?shù)囊粭l語(yǔ)句或一個(gè)表達(dá)式 將算 法描述補(bǔ)充完整 每空 2 分 分 36 1 m Leaf t Rchild 2 return n m 37 1 p p next 2 p next s 3 p s 4 p next q 38 1 j n 1 2 i j 第 1 頁(yè) 共 5 頁(yè) 銅 陵 學(xué) 院 2009 2010 學(xué)年第二學(xué)期 數(shù)據(jù)結(jié)構(gòu) 期末考試試卷 B 卷 適用班級(jí) 08 計(jì)算機(jī)本 1 08 計(jì)算機(jī)本 2 08 信息管理與信息系統(tǒng)本 題號(hào) 一 二 三 四 五 總分 統(tǒng)分人 統(tǒng)分復(fù)核人 得分 說明 以下全部試題答案請(qǐng)書寫在答題紙上 答案寫在試卷上無效 說明 以下全部試題答案請(qǐng)書寫在答題紙上 答案寫在試卷上無效 得分 閱卷人 復(fù)核人 一 判斷題一 判斷題 本大題共本大題共 10 小題 每小題小題 每小題 1 分 共分 共 10 分分 下列各題 你認(rèn)為正確的 請(qǐng)?jiān)诿款}前面的括號(hào)內(nèi)打 錯(cuò)誤的打 下列各題 你認(rèn)為正確的 請(qǐng)?jiān)诿款}前面的括號(hào)內(nèi)打 錯(cuò)誤的打 1 算法的確定性是指一個(gè)算法必須總是 對(duì)任何合法的輸入值 在執(zhí)行有 窮步之后結(jié)束 且每一步都在有窮時(shí)間內(nèi)完成 2 線性結(jié)構(gòu)中每一個(gè)數(shù)據(jù)元素都有前驅(qū) 3 棧的主要特點(diǎn)是先進(jìn)先出 4 串中任意個(gè)字符組成的子序列稱為該串的子串 5 由二叉樹的先序和中序遍歷序列可惟一確定這棵二叉樹 6 一棵有 n 個(gè)葉子結(jié)點(diǎn)的哈夫曼樹共有 2n 個(gè)結(jié)點(diǎn) 7 圖的深度優(yōu)先搜索遍歷類似于樹的層次遍歷 8 對(duì)于有 n 個(gè)頂點(diǎn)的無向連通圖來說 它的生成樹一定有 n 條邊 9 折半查找只適用于鏈表 且限于順序存儲(chǔ)結(jié)構(gòu) 10 快速排序算法的平均時(shí)間復(fù)雜度是 O nlog2n 它是一種不穩(wěn)定的排序方 法 得分 閱卷人 復(fù)核人 二 填空題填空題 本大題共本大題共 10 小題 每小題小題 每小題 2 分 共分 共 20 分分 請(qǐng)?jiān)诿啃☆}的空格中填上正確答案 錯(cuò)填 不填均不得分 請(qǐng)?jiān)诿啃☆}的空格中填上正確答案 錯(cuò)填 不填均不得分 11 對(duì)于一個(gè)以順序存儲(chǔ)結(jié)構(gòu)實(shí)現(xiàn)的循環(huán)隊(duì)列 Q 0 m 1 隊(duì)頭 隊(duì)尾指針分別 為 front rear 判斷隊(duì)列為空的條件是 12 二分法查找的效率較高 但要求關(guān)鍵字按關(guān)鍵字有序 并且要求表的存儲(chǔ) 為 13 設(shè)二叉樹的樹葉結(jié)點(diǎn)數(shù)為 n0 2度結(jié)點(diǎn)數(shù)為 n2 則二者之間的關(guān)系可表示 為 14 在廣義表中 假設(shè)取表頭運(yùn)算為 head 取表尾運(yùn)算為 tail 廣義表 A a b c d 則 tail head A 15 在一個(gè)單鏈表中 已知 q 結(jié)點(diǎn)是 p 結(jié)點(diǎn)的前驅(qū)結(jié)點(diǎn) 若在 q 和 p 之間插入 s 結(jié)點(diǎn) 則 須執(zhí)行 s next p 16 給定樹葉結(jié)點(diǎn)的權(quán)值分別為 1 3 5 7 可以構(gòu)造出其對(duì)應(yīng)的一棵哈夫曼 樹 則該哈夫 曼樹的帶權(quán)路徑長(zhǎng)度為 班級(jí) 姓名 學(xué)號(hào) 第 1 裝 線 第 2 裝 線 第 2 頁(yè) 共 5 頁(yè) 17 下列程序段的時(shí)間復(fù)雜度為 x n n 1 y 0 while x y 1 y 1 y 18 設(shè)有一個(gè) 10階的對(duì)稱矩陣 A 行下標(biāo)從 1到 10 列下標(biāo)從 1到 10 采用壓 縮存儲(chǔ)方式 以行序?yàn)橹餍蜻M(jìn)行存儲(chǔ) a11為第一個(gè)元素 其存儲(chǔ)地址為 1 每個(gè)元素占有 1 個(gè)存儲(chǔ)地址空 間 則 a85的地址為 19 設(shè)有向圖 G 應(yīng)用鄰接矩陣 A 1 m 1 m 對(duì)圖 G進(jìn)行存儲(chǔ) 則鄰接矩陣 A中 第 i 行的所 有元素之和等于頂點(diǎn) i 的 20 6個(gè)頂點(diǎn)的連通圖的廣度優(yōu)先生成樹 T 則 T的邊數(shù)為 得分 閱卷人 復(fù)核人 三 單項(xiàng)選擇題三 單項(xiàng)選擇題 本大題共本大題共 10 小題 每小題小題 每小題 2 分 共分 共 20 分分 在每小題給出的四個(gè)備選項(xiàng)中只有一個(gè)是符合題目要求的 請(qǐng)將其代碼填寫在 題后的括號(hào)內(nèi) 錯(cuò)選 多選或未選均不得分 在每小題給出的四個(gè)備選項(xiàng)中只有一個(gè)是符合題目要求的 請(qǐng)將其代碼填寫在 題后的括號(hào)內(nèi) 錯(cuò)選 多選或未選均不得分 21 帶頭結(jié)點(diǎn)的單向循環(huán)鏈表 head 為空的判斷條件為 A head next head B head next NULL C head NULL D head NULL 22 數(shù)據(jù)結(jié)構(gòu)在計(jì)算機(jī)中的表示稱為 A 數(shù)據(jù)結(jié)構(gòu) B 數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu) C 數(shù)據(jù)的邏輯結(jié)構(gòu) D 數(shù)據(jù)元素之間的關(guān)系 23 設(shè)一個(gè)棧的輸入序列為 1 2 3 n 輸出序列的第一個(gè)元素是 n 則第 i 個(gè)輸 出元素是 A n i 1 B n i C n i 1 D 不確定 24 下面關(guān)于串的敘述中 哪一個(gè)是不正確的 A 串是字符的有限序列 B 串既可以采用順序存儲(chǔ) 也可以采用 鏈表存儲(chǔ) C 模式匹配是串的一種重要運(yùn)算 D 空串是由空格構(gòu)成的串 25 設(shè)廣義表 L a b c 則 L 的長(zhǎng)度和深度分別為 A 1 和 2 B 1 和 3 C 1 和 1 D 2 和 3 26 一棵三叉樹中 已知度為 3 的結(jié)點(diǎn)數(shù)等于度為 2 的結(jié)點(diǎn)數(shù) 且樹中葉子結(jié)點(diǎn) 的數(shù)目為 13 則度為 2 的結(jié)點(diǎn)數(shù)目為 A 4 B 2 C 3 D 5 27 關(guān)鍵路徑是指 AOE Activity On Edge 網(wǎng)中 A 最長(zhǎng)的回路 B 最短的回路 C 從源點(diǎn)到匯點(diǎn) 結(jié)束頂點(diǎn) 的最長(zhǎng)路徑 D 從源點(diǎn)到匯點(diǎn) 結(jié)束頂點(diǎn) 的最短路徑 28 在一棵 AVL 平衡二叉樹 中 每個(gè)結(jié)點(diǎn)的平衡因子的取值范圍是 A 1 1 B 2 2 C 1 2 D 0 1 29 若查找每個(gè)元素的概率相等 則在長(zhǎng)度為 n 的順序表上查找到表中任一元素 的平均查找長(zhǎng)度為 第 3 頁(yè) 共 5 頁(yè) A n B n 1 C n 1 2 D n 1 2 30 就平均性能而言 最好的排序方法 A 希爾排序 B 快速排序 C 直接插入排序 D 冒泡排序 得分 閱卷人 復(fù)核人 四 應(yīng)用題四 應(yīng)用題 本大題共本大題共 5 小題 共小題 共 34 分分 31 本小題滿分 6分 已知一棵二叉樹的先序 中序和后序序列 其中空缺了 部分 請(qǐng)先填寫空缺的部分 然后畫出該二叉樹 1 填寫空缺的部分 先序遍歷序列 BC EFG IJK 中序遍歷序列 CBED GAJ H L 后序遍歷序列 E FD J L HA 2 畫出該二叉樹 32 本小題滿分 6分 有如下的遞歸過程 void output int w int i if w 0 output w 1 for i 1 ilchild NULL n NodeCount T rchild 求右子樹的結(jié)點(diǎn)個(gè)數(shù) return 2 else NodeCount 第 5 頁(yè) 共 5 頁(yè) 37 有一個(gè)帶頭結(jié)點(diǎn)的單鏈表 寫出在其值為 x的結(jié)點(diǎn)之后插入 m個(gè)結(jié)點(diǎn)的算 法 算法描述如下 typedef struct Node 結(jié)點(diǎn)構(gòu)造 ElemType data struct Node next LinkList LinkList Insert LinkList head float x int m LinkList p q s int i float b p head next while p NULL if p NULL printf x not found n x else q p next for i 1 i data b 2 3 4 return head Insert 38 請(qǐng)?jiān)O(shè)計(jì)一個(gè)算法 將數(shù)組 a 0 n 1 中的元素以 x 為界 將數(shù)組 a 中的數(shù)據(jù)元 素分為兩段 比 x 小的數(shù)據(jù)元素調(diào)整到數(shù)組的低下標(biāo)端 比 x 大或相等的數(shù)據(jù)元素調(diào)整到數(shù)組 的高下標(biāo)端 函數(shù)返回低下標(biāo)端的最后一個(gè)元素在數(shù)組 a 中的位置 下標(biāo) 算法描述如下 int arrange int a int x int n n為數(shù)組 a 中元素的個(gè)數(shù) int i 0 j n 1 temp while 1 while i x j a j 為大于等于 x 的元素 向左掃描 while i j a i 為小于 x 的元素 向右掃描 if inext s 題號(hào) 16 17 18 19 20 題號(hào) 16 17 18 19 20 答案 答案 29 O n 33 出度 5 說明 說明 1 第 14 題答案寫成 b 不得分 2 第 12 題答案寫成 順序存儲(chǔ) 第 17 題答案寫成 O n1 2 均不扣分 三 單項(xiàng)選擇題 三 單項(xiàng)選擇題 本大題共本大題共 10 小題 每小題小題 每小題 2 分 共分 共 20 分分 在每小題給出的四個(gè)備選項(xiàng)中只有一個(gè)是符合題目要求的 請(qǐng)將其代碼填寫在 題后的括號(hào)內(nèi) 錯(cuò)選 多選或未選均不得分 在每小題給出的四個(gè)備選項(xiàng)中只有一個(gè)是符合題目要求的 請(qǐng)將其代碼填寫在 題后的括號(hào)內(nèi) 錯(cuò)選 多選或未選均不得分 題 號(hào) 21 22 23 24 25 26 27 28 29 30 題 號(hào) 21 22 23 24 25 26 27 28 29 30 答 案 答 案 A B C D A A C A D B 四 應(yīng)用題四 應(yīng)用題 本大題共本大題共 5 小題 共小題 共 34 分分 31 本小題滿分 6 分 1 填寫空缺的部分 先序遍歷序列 A BC D EFG H IJK L 中序遍歷序列 CBED F GAJ I H K L 后序遍歷序列 C E G FD B J I L K HA 2 畫出該二叉樹 評(píng)分標(biāo)準(zhǔn) 評(píng)分標(biāo)準(zhǔn) 1 正確填寫每空可得 0 25分 12個(gè)空 共 3分 2 正確畫出二叉樹 可得 3 分 32 本小題滿分 6 分 班級(jí) 姓名 學(xué)號(hào) 第 1 裝 線 第 2 裝 線 第 2 頁(yè) 共 3 頁(yè) 1 2 2 3 3 3 4 4 4 4 5 5 5 5 5 6 6 6 6 6 6 評(píng)分標(biāo)準(zhǔn) 評(píng)分標(biāo)準(zhǔn) 輸出結(jié)果 6行 寫對(duì) 1行的結(jié)果可得 1分 共 6分 33 本小題滿分 6分 1 圖的鄰接矩陣為 0 12 5 12 0 8 10 8 0 3 5 0 6 10 6 0 11 3 11 0 2 圖的最小生成樹為 評(píng)分標(biāo)準(zhǔn) 評(píng)分標(biāo)準(zhǔn) 正確構(gòu)造出鄰接矩陣 得 3分 正確畫出其最小生成樹 T 再得 3 分 34 本小題滿分 6分 初始序列 100 87 52 61 27 170 37 45 61 118 14 88 32 第一趟排序 32 87 52 61 27 88 37 45 61 14 100 118 170 第二趟排序 14 27 32 61 52 88 37 45 61 87 100 118 170 第三趟排序 14 27 32 45 52 37 61 88 61 87 100 118 170 第四趟排序 14 27 32 37 45 52 61 87 61 88 100 118 170 第五趟排序 14 27 32 37 45 52 61 61 87 88 100 118 170 最后結(jié)果 14 27 32 37 45 52 61 61 87 88 100 118 170 評(píng)分標(biāo)準(zhǔn) 評(píng)分標(biāo)準(zhǔn) 正確寫出每趟排序的結(jié)果可得 1 分 共 6 分 35 本小題滿分 10 分 1 二叉排序樹為 在等概率情況下查找成功的平均查找長(zhǎng)度 ASL 1 1 2 2 3 3 4 3 5 2 6 1 12 42 12 2 平衡二叉樹為 第 3 頁(yè) 共 3 頁(yè) 在等概率情況下查找成功的平均查找長(zhǎng)度 ASL 1 1 2 2 3 4 4 4 5 1 12 38 12 評(píng)分標(biāo)準(zhǔn) 評(píng)分標(biāo)準(zhǔn) 1 正確畫出二叉排序樹 可得 3分 正確寫出平均查找長(zhǎng)度 再得 3 分 2 正確畫出平衡二叉樹 可得 3分 正確寫出平均查找長(zhǎng)度 再得 3 分 五 算法設(shè)計(jì)題 五 算法設(shè)計(jì)題 本大題共本大題共 3 小題 共小題 共 16 分分 在下列算法描述中 要求在每條橫線上填寫適當(dāng)?shù)囊粭l語(yǔ)句或一個(gè)表達(dá)式 將算 法描述補(bǔ)充完整 每空 在下列算法描述中 要求在每條橫線上填寫適當(dāng)?shù)囊粭l語(yǔ)句或一個(gè)表達(dá)式 將算 法描述補(bǔ)充完整 每空 2 分 分 36 1 return 1 2 m n 1 37 1 p p next 2 p next s 3 p s 4 p next q 38 1 i j 2 i j 第 1 頁(yè) 共 5 頁(yè) 銅 陵 學(xué) 院 2010 2011 學(xué)年第一學(xué)期 數(shù)據(jù)結(jié)構(gòu) 期末考試試卷 A 卷 適用班級(jí) 09 計(jì)算機(jī)本 1 09 計(jì)算機(jī)本 2 09 信息管理與信息系統(tǒng)本 題號(hào) 一 二 三 四 五 總分 統(tǒng)分人 統(tǒng)分復(fù)核人 得分 說明 以下全部試題答案請(qǐng)書寫在答題紙上 答案寫在試卷上無效說明 以下全部試題答案請(qǐng)書寫在答題紙上 答案寫在試卷上無效 得分 閱卷人 復(fù)核人 一 判斷題一 判斷題 本大題共本大題共 10 小題 每小題小題 每小題 1 分 共分 共 10 分分 下列各題 你認(rèn)為正確的 請(qǐng)?jiān)诿款}前面的括號(hào)內(nèi)打 錯(cuò)誤的打 下列各題 你認(rèn)為正確的 請(qǐng)?jiān)诿款}前面的括號(hào)內(nèi)打 錯(cuò)誤的打 1 算法的確定性是指一個(gè)算法必須總是 對(duì)任何合法的輸入值 在執(zhí)行有 窮步之后結(jié)束 且每一步都在有窮時(shí)間內(nèi)完成 2 線性結(jié)構(gòu)中每一個(gè)數(shù)據(jù)元素都有前驅(qū) 3 棧的主要特點(diǎn)是先進(jìn)先出 4 串中任意個(gè)字符組成的子序列稱為該串的子串 5 由二叉樹的先序和中序遍歷序列可惟一確定這棵二叉樹 6 一棵有 n 個(gè)葉子結(jié)點(diǎn)的哈夫曼樹共有 2n 個(gè)結(jié)點(diǎn) 7 圖的深度優(yōu)先搜索遍歷類似于樹的層次遍歷 8 對(duì)于有 n 個(gè)頂點(diǎn)的無向連通圖來說 它的生成樹一定有 n 條邊 9 折半查找只適用于鏈表 且限于順序存儲(chǔ)結(jié)構(gòu) 10 快速排序算法的平均時(shí)間復(fù)雜度是 O nlog2n 它是一種不穩(wěn)定的排序 方法 得分 閱卷人 復(fù)核人 二 填空題填空題 本大題共本大題共 10 小題 每小題小題 每小題 2 分 共分 共 20 分分 請(qǐng)?jiān)诿啃☆}的空格中填上正確答案 錯(cuò)填 不填均不得分 請(qǐng)?jiān)诿啃☆}的空格中填上正確答案 錯(cuò)填 不填均不得分 11 下列算法的時(shí)間復(fù)雜度為 void func int n int i 0 s 0 while snext p next 和 p next 的操作 13 對(duì)于一個(gè)以順序存儲(chǔ)結(jié)構(gòu)實(shí)現(xiàn)的循環(huán)隊(duì)列 Q 0 m 1 隊(duì)頭 隊(duì)尾指針分 別為 front rear 判斷隊(duì)列為空的條件是 14 兩個(gè)串相等的充分必要條件是 15 對(duì)于廣義表 L a c b d 運(yùn)算 head head tail L 的值 是 班級(jí) 姓名 學(xué)號(hào) 第 1 裝 線 第 2 裝 線 第 2 頁(yè) 共 5 頁(yè) 16 深度為 5 的二叉樹至多有 個(gè)結(jié)點(diǎn) 17 設(shè)有一個(gè) 10階的對(duì)稱矩陣 A 行下標(biāo)從 1到 10 列下標(biāo)從 1到 10 采用壓 縮存儲(chǔ)方式 以行序?yàn)橹餍蜻M(jìn)行存儲(chǔ) a11為第一個(gè)元素 其存儲(chǔ)地址為 1 每 個(gè)元素占有 1個(gè)存儲(chǔ)地址空間 則 a85的地址為 18 在一個(gè)具有 n個(gè)頂點(diǎn)的無向圖中 要連通全部頂點(diǎn)至少需要 條邊 19 高度為 8的平衡二叉樹的結(jié)點(diǎn)數(shù)至少有 個(gè) 20 在對(duì) n個(gè)元素進(jìn)行冒泡排序的過程中 最好情況下的時(shí)間復(fù)雜度 為 得分 閱卷人 復(fù)核人 三 單項(xiàng)選擇題三 單項(xiàng)選擇題 本大題共本大題共 10 小題 每小題小題 每小題 2 分 共分 共 20 分分 在每小題給出的四個(gè)備選項(xiàng)中只有一個(gè)是符合題目要求的 請(qǐng)將其代碼填寫在 題后的括號(hào)內(nèi) 錯(cuò)選 多選或未選均不得分 在每小題給出的四個(gè)備選項(xiàng)中只有一個(gè)是符合題目要求的 請(qǐng)將其代碼填寫在 題后的括號(hào)內(nèi) 錯(cuò)選 多選或未選均不得分 21 數(shù)據(jù)結(jié)構(gòu)在計(jì)算機(jī)內(nèi)存中的表示是指 A 數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu) B 數(shù)據(jù)結(jié)構(gòu) C 數(shù)據(jù)的邏輯結(jié)構(gòu) D 數(shù)據(jù)元素之間的關(guān)系 22 帶頭結(jié)點(diǎn)的單鏈表 L 為空的判定條件是 A L NULL B L next NULL C L next L D L NULL 23 設(shè) n 個(gè)元素進(jìn)棧序列是 p1 p2 p3 pn 其輸出序列是 1 2 3 n 若 p3 3 則 p1 的值 A 可能是 2 B 一定是 2 C 不可能是 1 D 一定 是 1 24 遞歸模型 f n f n 1 n n 1 的遞歸出口是 A f 1 0 B f 1 1 C f 0 1 D f n n 25 設(shè)有兩個(gè)串 p 和 q 求 q 在 p 中首次出現(xiàn)的位置的運(yùn)算稱作 A 連接 B 模式 匹配 C 求子串 D 求串長(zhǎng) 26 對(duì)稀疏矩陣進(jìn)行壓縮的目的是 A 便于進(jìn)行矩陣運(yùn)算 B 便于輸入和輸 出 C 節(jié)省存儲(chǔ)空間 D 降低運(yùn) 算的時(shí)間復(fù)雜度 27 一個(gè)具有 1025 個(gè)結(jié)點(diǎn)的二叉樹的高 h 為 A 11 B 10 C 11 1025 D 12 1024 28 采用鄰接表存儲(chǔ)的圖的廣度優(yōu)先遍歷算法類似于二叉樹的 算法 第 3 頁(yè) 共 5 頁(yè) A 先序遍歷 B 中序遍歷 C 后序遍歷 D 按層遍歷 29 假設(shè)有 k個(gè)關(guān)鍵字互為同義詞 若用線性探查法把這 k個(gè)關(guān)鍵字存入哈希 表中 至少要進(jìn)行 次探查 A k 1 B k C k 1 D k k 1 2 30 將兩個(gè)各有 n個(gè)元素的有序表歸并成一個(gè)有序表 其最少的比較次數(shù)是 A n B 2n 1 C 2n D n 1 得分 閱卷人 復(fù)核人 四 應(yīng)用題四 應(yīng)用題 本大題共本大題共 5 小題 共小題 共 34 分分 31 6 分 已知一棵二叉樹的中序遍歷序列為 cbedahgijf 后序遍歷序列為 cedbhjigfa 畫出該二叉樹的先序線索二叉樹 并寫出該二叉樹的先序遍歷 序列 32 6 分 設(shè)散列函數(shù)為 H k k 7 用拉鏈法解決沖突 若關(guān)鍵字的輸 入順序?yàn)?11 80 65 33 34 89 56 51 28 97 請(qǐng)構(gòu)造散列表 并 求在等概率情況下查找成功的平均查找長(zhǎng)度 ASL 33 6 分 給出帶權(quán)圖 G 如下圖所示 請(qǐng)寫出其鄰接矩陣 并按照克魯斯 卡爾 Kruskal 算法畫出其最小生成樹 T 34 6 分 有如下的遞歸過程 void output int w int i if w 0 output w 1 for i 1 iLchild NULL else num1 Nodes b Lchild 求左子樹的所有結(jié)點(diǎn)數(shù) num2 Nodes b RLchild 求右子樹的所有結(jié)點(diǎn)數(shù) return 2 Nodes 第 5 頁(yè) 共 5 頁(yè) 37 下列算法為采用頭插法建立帶頭結(jié)點(diǎn)的單鏈表 該算法是從一個(gè)空表開始 讀取數(shù)組 a 中的元素 生成新結(jié)點(diǎn) 將讀取的數(shù)據(jù)存放到新結(jié)點(diǎn)的數(shù)據(jù)域 中 然后將新結(jié)點(diǎn)插入到當(dāng)前鏈表的表頭上 直到結(jié)束為止 算法描述如下 typedef struct Node 結(jié)點(diǎn)構(gòu)造 ElemType data struct Node next LinkList void CreateLinkList LinkList L ElemType a int n LinkList s int i L LinkList malloc sizeof LinkList 創(chuàng)建頭結(jié)點(diǎn) L next 1 for i 0 i data a i s next L next 將 s 插在原開始結(jié)點(diǎn)之前 頭結(jié)點(diǎn)之后 L next 2 CreateLinkList 38 下列算法為奇偶交換排序 思想如下 第一趟對(duì)所有奇數(shù)的 i 將 a i 與 a i 1 進(jìn)行比較 第二趟對(duì)所有偶數(shù)的 i 將 a i 與 a i 1 進(jìn)行比較 每次 比較時(shí)若 a i a i 1 將二者交換 以后重復(fù)上述兩趟過程 直至整個(gè)數(shù) 組有序 算法描述如下 void Oesort int a int n int i t flag do flag 0 for i 1 ia i 1 flag 1 t a i 1 a i 1 a i 2 for i 2 ia i 1 4 flag 或 flag 1 0113 110610 605 308 108012 5120 第 1 頁(yè) 共 4 頁(yè) 銅 陵 學(xué) 院 2010 2011 學(xué)年第一學(xué)期 數(shù)據(jù)結(jié)構(gòu) 期末考試試卷 B 卷 適用班級(jí) 09 計(jì)算機(jī)本 1 09 計(jì)算機(jī)本 2 09 信息管理與信息系統(tǒng)本 題號(hào) 一 二 三 四 五 總分 統(tǒng)分人 統(tǒng)分復(fù)核人 得分 說明 以下全部試題答案請(qǐng)書寫在答題紙上 答案寫在試卷上無效說明 以下全部試題答案請(qǐng)書寫在答題紙上 答案寫在試卷上無效 得分 閱卷人 復(fù)核人 一 判斷題一 判斷題 本大題共本大題共 10 小題 每小題小題 每小題 1 分 共分 共 10 分分 下列各題 你認(rèn)為正確的 請(qǐng)?jiān)诿款}前面的括號(hào)內(nèi)打 錯(cuò)誤的打 下列各題 你認(rèn)為正確的 請(qǐng)?jiān)诿款}前面的括號(hào)內(nèi)打 錯(cuò)誤的打 1 算法的優(yōu)劣與算法描述語(yǔ)言無關(guān) 但與所用計(jì)算機(jī)有關(guān) 2 線性表中每個(gè)數(shù)據(jù)元素都有一個(gè)直接前驅(qū)和一個(gè)直接后繼 3 棧底元素是不能刪除的元素 4 空串就是由空格構(gòu)成的串 5 用二叉樹的先序序列和中序序列可以導(dǎo)出二叉樹的后序序列 6 二叉樹就是結(jié)點(diǎn)度為 2 的樹 7 n 個(gè)頂點(diǎn)的無向圖至多有 n n 1 條邊 8 最小生成樹是指邊數(shù)最少的生成樹 9 順序查找方法只能在順序存儲(chǔ)結(jié)構(gòu)上進(jìn)行 10 快速排序算法的平均時(shí)間復(fù)雜度是 O nlog2n 它是一種不穩(wěn)定的排序 方法 得分 閱卷人 復(fù)核人 二 填空題填空題 本大題共本大題共 10 小題 每小題小題 每小題 2 分 共分 共 20 分分 請(qǐng)?jiān)诿啃☆}的空格中填上正確答案 錯(cuò)填 不填均不得分 請(qǐng)?jiān)诿啃☆}的空格中填上正確答案 錯(cuò)填 不填均不得分 11 向一個(gè)長(zhǎng)度為 n 的順序表中的第 i 個(gè)元素 1 i n 之前插入一個(gè)元素時(shí) 需向后移動(dòng) 個(gè)元素 12 設(shè)棧采用順序存儲(chǔ)結(jié)構(gòu) 若已知 i 1個(gè)元素進(jìn)棧 則將第 i 個(gè)元素進(jìn)棧時(shí) 進(jìn) 棧算法的時(shí)間復(fù)雜度為 13 設(shè) s abcd 則執(zhí)行語(yǔ)句 s2 DelStr s 2 2 后 s2 14 設(shè)有一個(gè) 10 階的對(duì)稱矩陣 A 行下標(biāo)從 1 到 10 列下標(biāo)從 1 到 10 采用壓 縮存儲(chǔ)方式 以行序?yàn)橹餍蜻M(jìn)行存儲(chǔ) a11為第一個(gè)元素 其存儲(chǔ)地址為 1 每個(gè)元素占 有 1 個(gè)存儲(chǔ)地址空間 則 a85的地址為 15 對(duì)于廣義表 L a c b d 運(yùn)算 head head tail L 的值 是 16 具有 n 個(gè)結(jié)點(diǎn)的二叉樹采用二叉鏈表存儲(chǔ)結(jié)構(gòu) 共有 個(gè)空指針 域 17 設(shè)有 13 個(gè)值 用它們組成一棵哈夫曼樹 則該哈夫曼樹共有 個(gè)結(jié)點(diǎn) 班級(jí) 姓名 學(xué)號(hào) 第 1 裝 線 第 2 裝 線 第 2 頁(yè) 共 4 頁(yè) 18 圖 G是一個(gè)非連通無向圖 共有 28條邊 則該圖至少有 個(gè)頂 點(diǎn) 19 高度為 5 除葉子層之外 的三階 B 樹至少有 個(gè)結(jié)點(diǎn) 20 每次從無序子表中取出一個(gè)元素 把它插入到有序子表的適當(dāng)位置 此種排 序方法稱 為 得分 閱卷人 復(fù)核人 三 單項(xiàng)選擇題三 單項(xiàng)選擇題 本大題共本大題共 10 小題 每小題小題 每小題 2 分 共分 共 20 分分 在每小題給出的四個(gè)備選項(xiàng)中只有一個(gè)是符合題目要求的 請(qǐng)將其代碼填寫在 題后的括號(hào)內(nèi) 錯(cuò)選 多選或未選均不得分 在每小題給出的四個(gè)備選項(xiàng)中只有一個(gè)是符合題目要求的 請(qǐng)將其代碼填寫在 題后的括號(hào)內(nèi) 錯(cuò)選 多選或未選均不得分 21 在一個(gè)具有 n個(gè)結(jié)點(diǎn)的有序單鏈表中插入一個(gè)新結(jié)點(diǎn)并仍然保持有序的時(shí) 間復(fù)雜度是 A O 1 B O n C O n 2 D O nlog 2n 22 設(shè)一個(gè)棧的輸入序列為 A B C D 則借助一個(gè)棧所得到的輸出序列不 可能是 A A B C D B D C B A C A C D B D D A B C 23 一個(gè)隊(duì)列的入隊(duì)序列為 1234 則隊(duì)列可能的輸出序列是 A 4321 B 1234 C 1432 D 3241 24 設(shè)有兩個(gè)串 p和 q 求 q在 p中首次出現(xiàn)的位置的運(yùn)算稱作 A 連接 B 模式匹配 C 求子串 D 求串長(zhǎng) 25 將遞歸算法轉(zhuǎn)換成對(duì)應(yīng)的非遞歸算法時(shí) 通常需要使用 A 棧 B 隊(duì)列 C 鏈表 D 樹 26 按照二叉樹的定義 具有 3 個(gè)結(jié)點(diǎn)的二叉樹有 種 A 3 B 4 C 5 D 6 27 關(guān)鍵路徑是指 AOE Activity On Edge 網(wǎng)中 A 最長(zhǎng)的回路 B 最短的回路 C 從源點(diǎn)到匯點(diǎn) 結(jié)束頂點(diǎn) 的最長(zhǎng)路徑 D 從源點(diǎn)到匯點(diǎn) 結(jié)束頂點(diǎn) 的最短路徑 28 有一個(gè)長(zhǎng)度為 12 的有序表 按折半查找法對(duì)該表進(jìn)行查找 在表內(nèi)各元素 等概率情況下查找找成功所需的平均比較次數(shù)為 A 35 12 B 37 12 C 39 12 D 43 12 29 如果要求一個(gè)線性表既能較快地查找 又能適應(yīng)動(dòng)態(tài)變化的要求 可以采 用 查 找方法 A 分塊 B 順序 C 折半 D 散列 30 下述幾種排序方法中 要求內(nèi)存量最大的是 A 插入排序 B 選擇排序 C 快速排序 D 歸并排序 得分 閱卷人 復(fù)核人 四 應(yīng)用題四 應(yīng)用題 本大題共本大題共 5 小題 共小題 共 34 分分 第 3 頁(yè) 共 4 頁(yè) 31 本小題滿分 6分 設(shè)輸入元素為 1 2 3 P A 入棧次序?yàn)?123PA 元 素經(jīng)過棧后到達(dá)輸出序列 當(dāng)所有元素均到達(dá)輸出序列后 有哪些序列可 以作為高級(jí)語(yǔ)言的變量名 32 本小題滿分 6分 若一棵度為 4的樹中度為 1 2 3 4的結(jié)點(diǎn)個(gè)數(shù)分別 為 4 3 2 2 則該樹葉子結(jié)點(diǎn)的個(gè)數(shù)是多少 總結(jié)點(diǎn)個(gè)數(shù)是多少 33 本小題滿分 6分 給出帶權(quán)圖 請(qǐng)寫出其鄰接矩陣 并按照克魯斯卡爾 Kruskal 算法畫出其最小生成樹 T 34 本小題滿分 6分 以關(guān)鍵字序列 256 301 751 129 937 863 742 694 76 438 為例 給出歸并排序算法的各趟排序結(jié)束時(shí) 關(guān)鍵字序列的 狀態(tài) 35 本小題滿分 10 分 已知長(zhǎng)度為 12 的表 Jan Feb Mar Apr May June July Aug Sep Oct Nov Dec 1 試按表中的元素的順序依次插入一棵初始為空的二叉排序樹 字符之間以字 典順序比較大小 畫出最終創(chuàng)建的二叉排序樹 并求在等概率的情況下查找成功 的平均查找長(zhǎng)度 ASL 2 按表中元素順序構(gòu)造一棵平衡二叉樹 畫出最終創(chuàng)建的平衡二叉樹 并求其 在等概率的情況下查找成功時(shí)的平均查找長(zhǎng)度 ASL 得分 閱卷人 復(fù)核人 第 4 頁(yè) 共 4 頁(yè) 五 算法設(shè)計(jì)題五 算法設(shè)計(jì)題 本大題共本大題共 3 小題 共小題 共 16 分分 在下列算法描述中 要求在每條橫線上僅填寫適當(dāng)?shù)囊粭l語(yǔ)句或一個(gè)表達(dá)式 將 算法描述補(bǔ)充完整 每空 在下列算法描述中 要求在每條橫線上僅填寫適當(dāng)?shù)囊粭l語(yǔ)句或一個(gè)表達(dá)式 將 算法描述補(bǔ)充完整 每空 2 分 分 36 給定一棵用二叉鏈表表示的二叉樹 請(qǐng)?jiān)O(shè)計(jì)一個(gè)算法 求該二叉樹高度的算 法 算法描述如下 typedef struct Node ElemType data struct Node lchild rchlid BiTree int BTNodeDepth BiTree b 返回指針 b 所指二叉樹中所有結(jié)點(diǎn)個(gè)數(shù) int lchilddep rchilddep if b NULL return 0 若二叉樹為空 空樹的高度為 0 else lchilddep BTNodeDepth b lchild 求左子樹的高度 lchilddep rchilddep BTNodeDepth 1 求右子樹的高度 rchilddep if lchilddep rchilddep return lchilddep 1 else return 2 else BTNodeDepth 37 設(shè)計(jì)一個(gè)雙向冒泡排序的算法 即在排序過程中交替改變掃描方向 每 一趟通過每?jī)蓚€(gè)相鄰的關(guān)鍵字進(jìn)行比較 產(chǎn)生最小和最大的元素 算法描述如下 void DBubble SqList R int m 對(duì) R 0 n 1 按遞增序列進(jìn)行雙向冒泡排 序 int i j SqList temp int exchange 1 exchange標(biāo)識(shí)本趟是否進(jìn)行了記錄交換 i 0 while 1 exchange 0 for j n i 1 j i j if 2 由底向上 exchange 1 temp R j R j R j 1 R j 1 te