數(shù)據(jù)結(jié)構(gòu)試卷及參考答案(三).pdf

數(shù)據(jù)結(jié)構(gòu)試卷數(shù)據(jù)結(jié)構(gòu)試卷及參考答案及參考答案 三 三 一 選擇題一 選擇題 每題每題 1 1 分 共分 共 2020 分分 1 設(shè)某數(shù)據(jù)結(jié)構(gòu)的二元組形式表示為 A D R D 01 02 03 04 05 06 07 08 09 R r r 則數(shù)據(jù)結(jié)構(gòu) A 是 A 線性結(jié)構(gòu) B 樹(shù)型結(jié)構(gòu) C 物理結(jié)構(gòu) D 圖型結(jié)構(gòu) 2 下面程序的時(shí)間復(fù)雜為 for i 1 s 0 i n i t 1 for j 1 jnext p data q data p next q next free q B q p next q data p data p next q next free q C q p next p next q next free q D q p next p data q data free q 4 設(shè)有 n 個(gè)待排序的記錄關(guān)鍵字 則在堆排序中需要 個(gè)輔助記錄單元 A 1 B n C nlog2n D n 2 5 設(shè)一組初始關(guān)鍵字記錄關(guān)鍵字為 20 15 14 18 21 36 40 10 則以 20 為基準(zhǔn)記 錄的一趟快速排序結(jié)束后的結(jié)果為 A 10 15 14 18 20 36 40 21 B 10 15 14 18 20 40 36 21 C 10 15 14 20 18 40 36 2l D 15 10 14 18 20 36 40 21 6 設(shè)二叉排序樹(shù)中有 n 個(gè)結(jié)點(diǎn) 則在二叉排序樹(shù)的平均平均查找長(zhǎng)度為 A O 1 B O log2n C D O n 2 7 設(shè)無(wú)向圖 G 中有 n 個(gè)頂點(diǎn) e 條邊 則其對(duì)應(yīng)的鄰接表中的表頭結(jié)點(diǎn)和表結(jié)點(diǎn)的個(gè)數(shù)分別 為 A n e B e n C 2n e D n 2e 8 設(shè)某強(qiáng)連通圖中有 n 個(gè)頂點(diǎn) 則該強(qiáng)連通圖中至少有 條邊 A n n 1 B n 1 C n D n n 1 9 設(shè)有 5000 個(gè)待排序的記錄關(guān)鍵字 如果需要用最快的方法選出其中最小的 10 個(gè)記錄關(guān) 鍵字 則用下列 方法可以達(dá)到此目的 A 快速排序 B 堆排序 C 歸并排序 D 插入排序 10 下列四種排序中 的空間復(fù)雜度最大 A 插入排序 B 冒泡排序 C 堆排序 D 歸并排序 二 填空殖二 填空殖 每空每空 1 1 分分 共共 2020 分分 1 數(shù)據(jù)的物理結(jié)構(gòu)主要包括 和 兩種情況 2 設(shè)一棵完全二叉樹(shù)中有 500 個(gè)結(jié)點(diǎn) 則該二叉樹(shù)的深度為 若用二叉鏈表作 為該完全二叉樹(shù)的存儲(chǔ)結(jié)構(gòu) 則共有 個(gè)空指針域 3 設(shè)輸入序列為 1 2 3 則經(jīng)過(guò)棧的作用后可以得到 種不同的輸出序列 4 設(shè)有向圖 G 用鄰接矩陣 A n n 作為存儲(chǔ)結(jié)構(gòu) 則該鄰接矩陣中第 i 行上所有元素之和 等于頂點(diǎn) i 的 第 i 列上所有元素之和等于頂點(diǎn) i 的 5 設(shè)哈夫曼樹(shù)中共有 n 個(gè)結(jié)點(diǎn) 則該哈夫曼樹(shù)中有 個(gè)度數(shù)為 1 的結(jié)點(diǎn) 6 設(shè)有向圖 G 中有 n 個(gè)頂點(diǎn) e 條有向邊 所有的頂點(diǎn)入度數(shù)之和為 d 則 e 和 d 的關(guān)系為 7 遍歷二叉排序樹(shù)中的結(jié)點(diǎn)可以得到一個(gè)遞增的關(guān)鍵字序列 填先序 中序或 后序 8 設(shè)查找表中有 100 個(gè)元素 如果用二分法查找方法查找數(shù)據(jù)元素 X 則最多需要比較 次就可以斷定數(shù)據(jù)元素 X 是否在查找表中 9 不論是順序存儲(chǔ)結(jié)構(gòu)的棧還是鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)的棧 其入棧和出棧操作的時(shí)間復(fù)雜度均為 10 設(shè)有 n 個(gè)結(jié)點(diǎn)的完全二叉樹(shù) 如果按照從自上到下 從左到右從 1 開(kāi)始順序編號(hào) 則第 i 個(gè)結(jié)點(diǎn)的雙親結(jié)點(diǎn)編號(hào)為 右孩子結(jié)點(diǎn)的編號(hào)為 11 設(shè)一組初始記錄關(guān)鍵字為 72 73 71 23 94 16 5 則以記錄關(guān)鍵字 72 為基準(zhǔn)的 一趟快速排序結(jié)果為 12 設(shè)有向圖 G 中有向邊的集合 E 則該圖 的一種拓?fù)湫蛄袨?13 下列算法實(shí)現(xiàn)在順序散列表中查找值為 x 的關(guān)鍵字 請(qǐng)?jiān)谙聞澗€處填上正確的語(yǔ)句 struct record int key int others int hashsqsearch struct record hashtable int k int i j j i k p while hashtable j key k if i j return 1 if return j else return 1 14 下列算法實(shí)現(xiàn)在二叉排序樹(shù)上查找關(guān)鍵值 k 請(qǐng)?jiān)谙聞澗€處填上正確的語(yǔ)句 typedef struct node int key struct node lchild struct node rchild bitree bitree bstsearch bitree t intk if t 0 return 0 elsewhile t 0 if t key k else if t key k t t lchild else 三 計(jì)算題三 計(jì)算題 每題每題 1010 分 共分 共 3030 分分 1 已知二叉樹(shù)的前序遍歷序列是 AEFBGCDHIKJ 中序遍歷序列是 EFAGBCHKIJD 畫(huà)出此 二叉樹(shù) 并畫(huà)出它的后序線索二叉樹(shù) 2 已知待散列的線性表為 36 15 40 63 22 散列用的一維地址空間為 0 6 假定 選用的散列函數(shù)是 H K K mod 7 若發(fā)生沖突采用線性探查法處理 試 1 計(jì)算出每一個(gè)元素的散列地址并在下圖中填寫(xiě)出散列表 0123456 2 求出在查找每一個(gè)元素概率相等情況下的平均查找長(zhǎng)度 3 已知序列 10 18 4 3 6 12 1 9 18 8 請(qǐng)用快速排序?qū)懗雒恳惶伺判虻慕Y(jié)果 四 算法設(shè)計(jì)題四 算法設(shè)計(jì)題 每題每題 1515 分 共分 共 3030 分分 1 設(shè)計(jì)在單鏈表中刪除值相同的多余結(jié)點(diǎn)的算法 2 設(shè)計(jì)一個(gè)求結(jié)點(diǎn) x 在二叉樹(shù)中的雙親結(jié)點(diǎn)算法 數(shù)據(jù)結(jié)構(gòu)試卷 三 參考答案數(shù)據(jù)結(jié)構(gòu)試卷 三 參考答案 一 選擇題一 選擇題 1 B2 B3 A4 A5 A 6 B7 D8 C9 B10 D 第 3 小題分析 首先用指針變量 q 指向結(jié)點(diǎn) A 的后繼結(jié)點(diǎn) B 然后將結(jié)點(diǎn) B 的值復(fù)制到 結(jié)點(diǎn) A 中 最后刪除結(jié)點(diǎn) B 第 9 小題分析 9 快速排序 歸并排序和插入排序必須等到整個(gè)排序結(jié)束后才能夠求出 最小的 10 個(gè)數(shù) 而堆排序只需要在初始堆的基礎(chǔ)上再進(jìn)行 10 次篩選即可 每次篩選的時(shí)間 復(fù)雜度為 O log2n 二 填空題二 填空題 1 順序存儲(chǔ)結(jié)構(gòu) 鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu) 2 9 501 3 5 4 出度 入度 5 0 6 e d 7 中序 8 7 9 O 1 10 i 2 2i 1 11 5 16 71 23 72 94 73 12 1 4 3 2 13 j 1 hashtable j key k 14 return t t t rchild 第 8 小題分析 二分查找的過(guò)程可以用一棵二叉樹(shù)來(lái)描述 該二叉樹(shù)稱為二叉判定樹(shù) 在有序表上進(jìn)行二分查找時(shí)的查找長(zhǎng)度不超過(guò)二叉判定樹(shù)的高度 1 log2n 三 計(jì)算題三 計(jì)算題 1 A E B FG C D H F K J NULL 2 H 36 36 mod 7 1 H 22 1 1 mod 7 2 沖突 H 15 15 mod 7 1 沖突H2 22 2 1 mod 7 3 H 15 1 1 mod 7 2 H 40 40 mod 7 5 H 63 63 mod 7 0 H 22 22 mod 7 1 沖突 1 0123456 6336152240 2 ASL 6 1 5 31121 3 8 9 4 3 6 1 10 12 18 18 1 6 4 3 8 9 10 12 18 18 1 3 4 6 8 9 10 12 18 18 1 3 4 6 8 9 10 12 18 18 1 3 4 6 8 9 10 12 18 18 四 算法設(shè)計(jì)題四 算法設(shè)計(jì)題 1 設(shè)計(jì)在單鏈表中刪除值相同的多余結(jié)點(diǎn)的算法 typedef int datatype typedef struct node datatype data struct node next lklist void delredundant lklist for p head p 0 p p next for q p next s q q 0 if q data p data s next q next free q q s next else s q q q next 2 設(shè)計(jì)一個(gè)求結(jié)點(diǎn) x 在二叉樹(shù)中的雙親結(jié)點(diǎn)算法 typedef struct node datatype data struct node lchild rchild bitree bitree q 20 int r 0 f 0 flag 0 void preorder bitree bt char x if bt 0 return else r r 1 20 q r bt preorder bt lc