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

數(shù)據(jù)結(jié)構(gòu)試卷數(shù)據(jù)結(jié)構(gòu)試卷及參考答案及參考答案 四 四 一 選擇題一 選擇題 每題每題 1 1 分共分共 2020 分分 1 設(shè)一維數(shù)組中有 n 個數(shù)組元素 則讀取第 i 個數(shù)組元素的平均時間復(fù)雜度為 A O n B O nlog2n C O 1 D O n 2 2 設(shè)一棵二叉樹的深度為 k 則該二叉樹中最多有 個結(jié)點(diǎn) A 2k 1 B 2 k C 2 k 1 D 2 k 1 3 設(shè)某無向圖中有 n 個頂點(diǎn) e 條邊 則該無向圖中所有頂點(diǎn)的入度之和為 A n B e C 2n D 2e 4 在二叉排序樹中插入一個結(jié)點(diǎn)的時間復(fù)雜度為 A O 1 B O n C O log2n D O n 2 5 設(shè)某有向圖的鄰接表中有 n 個表頭結(jié)點(diǎn)和 m 個表結(jié)點(diǎn) 則該圖中有 條有向邊 A n B n 1 C m D m 1 6 設(shè)一組初始記錄關(guān)鍵字序列為 345 253 674 924 627 則用基數(shù)排序需要進(jìn)行 趟的分配和回收才能使得初始關(guān)鍵字序列變成有序序列 A 3 B 4 C 5 D 8 7 設(shè)用鏈表作為棧的存儲結(jié)構(gòu)則退棧操作 A 必須判別棧是否為滿 B 必須判別棧是否為空 C 判別棧元素的類型 D 對棧不作任何判別 8 下列四種排序中 的空間復(fù)雜度最大 A 快速排序 B 冒泡排序 C 希爾排序 D 堆 9 設(shè)某二叉樹中度數(shù)為 0 的結(jié)點(diǎn)數(shù)為 N0 度數(shù)為 1 的結(jié)點(diǎn)數(shù)為 Nl 度數(shù)為 2 的結(jié)點(diǎn)數(shù)為 N2 則下列等式成立的是 A N0 N1 1 B N0 Nl N2 C N0 N2 1 D N0 2N1 l 10 設(shè)有序順序表中有 n 個數(shù)據(jù)元素 則利用二分查找法查找數(shù)據(jù)元素 X 的最多比較次數(shù)不 超過 A log2n 1 B log2n 1 C log2n D log2 n 1 二 填空題二 填空題 每空每空 1 1 分共分共 2020 分分 1 設(shè)有 n 個無序的記錄關(guān)鍵字 則直接插入排序的時間復(fù)雜度為 快速排序的平 均時間復(fù)雜度為 2 設(shè)指針變量 p 指向雙向循環(huán)鏈表中的結(jié)點(diǎn) X 則刪除結(jié)點(diǎn) X 需要執(zhí)行的語句序列為 設(shè)結(jié)點(diǎn)中的兩個指 針域分別為 llink 和 rlink 3 根據(jù)初始關(guān)鍵字序列 19 22 01 38 10 建立的二叉排序樹的高度為 4 深度為 k 的完全二叉樹中最少有 個結(jié)點(diǎn) 5 設(shè)初始記錄關(guān)鍵字序列為 K1 K2 Kn 則用篩選法思想建堆必須從第 個元素 開始進(jìn)行篩選 6 設(shè)哈夫曼樹中共有 99 個結(jié)點(diǎn) 則該樹中有 個葉子結(jié)點(diǎn) 若采用二叉鏈表作為 存儲結(jié)構(gòu) 則該樹中有 個空指針域 7 設(shè)有一個順序循環(huán)隊(duì)列中有 M 個存儲單元 則該循環(huán)隊(duì)列中最多能夠存儲 個隊(duì) 列元素 當(dāng)前實(shí)際存儲 個隊(duì)列元素 設(shè)頭指針 F 指向當(dāng)前隊(duì)頭元素的 前一個位置 尾指針指向當(dāng)前隊(duì)尾元素的位置 8 設(shè)順序線性表中有 n 個數(shù)據(jù)元素 則第 i 個位置上插入一個數(shù)據(jù)元素需要移動表中 個數(shù)據(jù)元素 刪除第 i 個位置上的數(shù)據(jù)元素需要移動表中 個元素 9 設(shè)一組初始記錄關(guān)鍵字序列為 20 18 22 16 30 19 則以 20 為中軸的一趟快速 排序結(jié)果為 10 設(shè)一組初始記錄關(guān)鍵字序列為 20 18 22 16 30 19 則根據(jù)這些初始關(guān)鍵字序列 建成的初始堆為 11 設(shè)某無向圖 G 中有 n 個頂點(diǎn) 用鄰接矩陣 A 作為該圖的存儲結(jié)構(gòu) 則頂點(diǎn) i 和頂點(diǎn) j 互為鄰接點(diǎn)的條件是 12 設(shè)無向圖對應(yīng)的鄰接矩陣為 A 則 A 中第 i 上非 0 元素的個數(shù) 第 i 列上非 0 元素的個數(shù) 填等于 大于或小于 13 設(shè)前序遍歷某二叉樹的序列為 ABCD 中序遍歷該二叉樹的序列為 BADC 則后序遍 歷該二叉樹的序列為 14 設(shè)散列函數(shù) H k k mod p 解決沖突的方法為鏈地址法 要求在下列算法劃線處填上正 確的語句完成在散列表 hashtalbe 中查找關(guān)鍵字值等于 k 的結(jié)點(diǎn) 成功時返回指向關(guān)鍵 字的指針 不成功時返回標(biāo)志 0 typedef struct node int key struct node next lklist void createlkhash lklist hashtable int i k lklist s for i 0 i m i for i 0 ikey a i k a i p s next hashtable k 三 計算題三 計算題 每題每題 1010 分 共分 共 3030 分分 1 畫出廣義表 LS e a b c d 的頭尾鏈表存儲結(jié)構(gòu) 2 下圖所示的森林 1 求樹 a 的先根序列和后根序列 2 求森林先序序列和中序序列 3 將此森林轉(zhuǎn)換為相應(yīng)的二叉樹 A BC DE F G H IJ K a b 3 設(shè)散列表的地址范圍是 0 9 散列函數(shù)為 H key key 2 2 MOD 9 并采用鏈 表處理沖突 請畫出元素 7 4 5 3 6 2 8 9 依次插入散列表的存儲結(jié)構(gòu) 四 算法設(shè)計題四 算法設(shè)計題 每題每題 1010 分 共分 共 3030 分分 1 設(shè)單鏈表中有僅三類字符的數(shù)據(jù)元素 大寫字母 數(shù)字和其它字符 要求利用原單鏈表 中結(jié)點(diǎn)空間設(shè)計出三個單鏈表的算法 使每個單鏈表只包含同類字符 2 設(shè)計在鏈?zhǔn)酱鎯Y(jié)構(gòu)上交換二叉樹中所有結(jié)點(diǎn)左右子樹的算法 3 在鏈?zhǔn)酱鎯Y(jié)構(gòu)上建立一棵二叉排序樹 數(shù)據(jù)結(jié)構(gòu)試卷 四 參考答案數(shù)據(jù)結(jié)構(gòu)試卷 四 參考答案 一 選擇題一 選擇題 1 C2 D3 D4 B5 C 6 A7 B8 A9 C10 A 二 填空題二 填空題 1 O n 2 O nlog 2n 2 p llink rlink p rlink p rlink llink p rlink 3 3 4 2 k 1 5 n 2 6 50 51 7 m 1 R F M M 8 n 1 i n i 9 19 18 16 20 30 22 10 16 18 19 20 32 22 11 A i j 1 12 等于 13 BDCA 14 hashtable i 0 hashtable k s 三 計算題三 計算題 1 1 1 11 1 1 1 1 111 00 00 0 ea b c d LS 2 1 ABCDEF BDEFCA 2 ABCDEFGHIJK BDEFCAIJKHG 林轉(zhuǎn)換為相應(yīng)的二叉樹 A G B C D E F H I J K 3 H 4 H 5 0 H 3 H 6 H 9 2 H 8 3 H 2 H 7 6 0 1 2 3 4 5 6 7 8 9 45 369 8 27 四 算法設(shè)計題四 算法設(shè)計題 1 設(shè)單鏈表中有僅三類字符的數(shù)據(jù)元素 大寫字母 數(shù)字和其它字符 要求利用原單鏈表 中結(jié)點(diǎn)空間設(shè)計出三個單鏈表的算法 使每個單鏈表只包含同類字符 typedef char datatype typedef struct node datatype data struct node next lklist void split lklist head lklist ha 0 hb 0 hc 0 for p head p 0 p head head p next p next 0 if p data A ha p else if p data 0 hb p else p next hc hc p 2 設(shè)計在鏈?zhǔn)酱鎯Y(jié)構(gòu)上交換二叉樹中所有結(jié)點(diǎn)左右子樹的算法 typedef struct node int data struct node lchild rchild bitree void swapbitree bitree bt bitree p if bt 0 return swapbitree bt lchild swapbitree bt rchild p bt lchild bt lchild bt rchild bt rchild p 3 在鏈?zhǔn)酱鎯Y(jié)構(gòu)上建立一棵二叉排序樹 define n 10 typedef struct node int key struct node lchild rchild bitree void bstinsert