7套《數據結構》期末試卷答題紙答案.pdf

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