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

數(shù)據(jù)結(jié)構(gòu)試卷 六 數(shù)據(jù)結(jié)構(gòu)試卷 六 一 選擇題一 選擇題 30 30 分分 1 設(shè)一組權(quán)值集合 W 2 3 4 5 6 則由該權(quán)值集合構(gòu)造的哈夫曼樹(shù)中帶權(quán)路徑長(zhǎng)度 之和為 A 20 B 30 C 40 D 45 2 執(zhí)行一趟快速排序能夠得到的序列是 A 41 12 34 45 27 55 72 63 B 45 34 12 41 55 72 63 27 C 63 12 34 45 27 55 41 72 D 12 27 45 41 55 34 63 72 3 設(shè)一條單鏈表的頭指針變量為 head 且該鏈表沒(méi)有頭結(jié)點(diǎn) 則其判空條件是 A head 0 B head next 0 C head next head D head 0 4 時(shí)間復(fù)雜度不受數(shù)據(jù)初始狀態(tài)影響而恒為 O nlog2n 的是 A 堆排序 B 冒泡排序 C 希爾排序 D 快速排序 5 設(shè)二叉樹(shù)的先序遍歷序列和后序遍歷序列正好相反 則該二叉樹(shù)滿足的條件是 A 空或只有一個(gè)結(jié)點(diǎn) B 高度等于其結(jié)點(diǎn)數(shù) C 任一結(jié)點(diǎn)無(wú)左孩子 D 任一結(jié)點(diǎn)無(wú)右孩子 6 一趟排序結(jié)束后不一定能夠選出一個(gè)元素放在其最終位置上的是 A 堆排序 B 冒泡排序 C 快速排序 D 希爾排序 7 設(shè)某棵三叉樹(shù)中有 40 個(gè)結(jié)點(diǎn) 則該三叉樹(shù)的最小高度為 A 3 B 4 C 5 D 6 8 順序查找不論在順序線性表中還是在鏈?zhǔn)骄€性表中的時(shí)間復(fù)雜度為 A O n B O n 2 C O n 1 2 D O 1og2n 9 二路歸并排序的時(shí)間復(fù)雜度為 A O n B O n 2 C O nlog2n D O 1og2n 10 深度為 k 的完全二叉樹(shù)中最少有 個(gè)結(jié)點(diǎn) A 2 k 1 1 B 2 k 1 C 2 k 1 1 D 2 k 1 11 設(shè)指針變量 front 表示鏈?zhǔn)疥?duì)列的隊(duì)頭指針 指針變量 rear 表示鏈?zhǔn)疥?duì)列的隊(duì)尾指針 指針變量 s 指向?qū)⒁腙?duì)列的結(jié)點(diǎn) X 則入隊(duì)列的操作序列為 A front next s front s B s next rear rear s C rear next s rear s D s next front front s 12 設(shè)某無(wú)向圖中有 n 個(gè)頂點(diǎn) e 條邊 則建立該圖鄰接表的時(shí)間復(fù)雜度為 A O n e B O n 2 C O ne D O n 3 13 設(shè)某哈夫曼樹(shù)中有 199 個(gè)結(jié)點(diǎn) 則該哈夫曼樹(shù)中有 個(gè)葉子結(jié)點(diǎn) A 99 B 100 C 101 D 102 14 設(shè)二叉排序樹(shù)上有 n 個(gè)結(jié)點(diǎn) 則在二叉排序樹(shù)上查找結(jié)點(diǎn)的平均時(shí)間復(fù)雜度為 A O n B O n 2 C O nlog2n D O 1og2n 15 設(shè)用鄰接矩陣 A 表示有向圖 G 的存儲(chǔ)結(jié)構(gòu) 則有向圖 G 中頂點(diǎn) i 的入度為 A 第 i 行非 0 元素的個(gè)數(shù)之和 B 第 i 列非 0 元素的個(gè)數(shù)之和 C 第 i 行 0 元素的個(gè)數(shù)之和 D 第 i 列 0 元素的個(gè)數(shù)之和 二 判斷題二 判斷題 20 20 分分 1 調(diào)用一次深度優(yōu)先遍歷可以訪問(wèn)到圖中的所有頂點(diǎn) 2 分塊查找的平均查找長(zhǎng)度不僅與索引表的長(zhǎng)度有關(guān) 而且與塊的長(zhǎng)度有關(guān) 3 冒泡排序在初始關(guān)鍵字序列為逆序的情況下執(zhí)行的交換次數(shù)最多 4 滿二叉樹(shù)一定是完全二叉樹(shù) 完全二叉樹(shù)不一定是滿二叉樹(shù) 5 設(shè)一棵二叉樹(shù)的先序序列和后序序列 則能夠唯一確定出該二叉樹(shù)的形狀 6 層次遍歷初始堆可以得到一個(gè)有序的序列 7 設(shè)一棵樹(shù) T 可以轉(zhuǎn)化成二叉樹(shù) BT 則二叉樹(shù) BT 中一定沒(méi)有右子樹(shù) 8 線性表的順序存儲(chǔ)結(jié)構(gòu)比鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)更好 9 中序遍歷二叉排序樹(shù)可以得到一個(gè)有序的序列 10 快速排序是排序算法中平均性能最好的一種排序 三 填空題三 填空題 30 30 分分 1 for i 1 t 1 s 0 i n i t t i s s t 的時(shí)間復(fù)雜度為 2 設(shè)指針變量 p 指向單鏈表中結(jié)點(diǎn) A 指針變量 s 指向被插入的新結(jié)點(diǎn) X 則進(jìn)行插入操作 的語(yǔ)句序列為 設(shè)結(jié)點(diǎn)的指針域?yàn)?next 3 設(shè)有向圖 G 的二元組形式表示為 G D R D 1 2 3 4 5 R r r 則給出該圖的一種拓?fù)渑判蛐蛄?4 設(shè)無(wú)向圖 G 中有 n 個(gè)頂點(diǎn) 則該無(wú)向圖中每個(gè)頂點(diǎn)的度數(shù)最多是 5 設(shè)二叉樹(shù)中度數(shù)為0的結(jié)點(diǎn)數(shù)為50 度數(shù)為1的結(jié)點(diǎn)數(shù)為30 則該二叉樹(shù)中總共有 個(gè)結(jié)點(diǎn)數(shù) 6 設(shè) F 和 R 分別表示順序循環(huán)隊(duì)列的頭指針和尾指針 則判斷該循環(huán)隊(duì)列為空的條件為 7 設(shè)二叉樹(shù)中結(jié)點(diǎn)的兩個(gè)指針域分別為 lchild 和 rchild 則判斷指針變量 p 所指向的結(jié) 點(diǎn)為葉子結(jié)點(diǎn)的條件是 8 簡(jiǎn)單選擇排序和直接插入排序算法的平均時(shí)間復(fù)雜度為 9 快速排序算法的空間復(fù)雜度平均情況下為 最壞的情況下為 10 散列表中解決沖突的兩種方法是 和 四 算法設(shè)計(jì)題四 算法設(shè)計(jì)題 20 20 分分 設(shè)計(jì)在順序有序表中實(shí)現(xiàn)二分查找的算法 設(shè)計(jì)判斷二叉樹(shù)是否為二叉排序樹(shù)的算法 在鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)上設(shè)計(jì)直接插入排序算法 數(shù)據(jù)結(jié)構(gòu)試卷 六 參考答案數(shù)據(jù)結(jié)構(gòu)試卷 六 參考答案 一 選擇題一 選擇題 1 D2 A3 A4 A5 D 6 D7 B8 A9 C10 B 11 C12 A13 B14 D15 B 二 判斷題二 判斷題 1 錯(cuò)2 對(duì)3 對(duì)4 對(duì)5 錯(cuò) 6 錯(cuò)7 對(duì)8 錯(cuò)9 對(duì)10 對(duì) 三 填空題三 填空題 1 O n 2 s next p next p next s 3 1 3 2 4 5 4 n 1 5 129 6 F R 7 p lchild 0 int others int bisearch struct record r int k int low 0 mid high n 1 while lowk high mid 1 else low mid 1 return 0 2 設(shè)計(jì)判斷二叉樹(shù)是否為二叉排序樹(shù)的算法 int minnum 32768 flag 1 typedef struct node int key struct node lchild rchild bitree void inorder bitree bt if bt 0 inorder bt lchild if minnum bt key flag 0 minnum bt key inorder bt rchild 3 在鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)上設(shè)計(jì)直接插入排序算法 void straightinsertsort lklist int t if head 0 head next 0 return else for q head p head next p 0 p q ne