《數(shù)據(jù)結(jié)構(gòu)》全真模擬試題與解答

1、1全真模擬試題全真模擬試題一、單項(xiàng)選擇題（在每個(gè)小題的一、單項(xiàng)選擇題（在每個(gè)小題的4個(gè)備選答案中，選出正確的答案，并將其號(hào)碼填在題個(gè)備選答案中，選出正確的答案，并將其號(hào)碼填在題后的括號(hào)內(nèi)。每小題后的括號(hào)內(nèi)。每小題2分，共分，共2424分）分）1一個(gè)具有n個(gè)頂點(diǎn)的無(wú)向完全圖的邊數(shù)為（）①n(n1)2②n(n1)2③n(n1)④n(n1)2在索引順序表中查找一個(gè)元素，可用的且最快的方法是（）①用順序查找法確定元素所在塊，再用順序查找法在相應(yīng)

2、塊中查找②用順序查找法確定元素所在塊，再用二分查找法在相應(yīng)塊中查找③用二分查找法確定元素所在塊，再用順序查找法在相應(yīng)塊中查找④用二分查找法確定元素所在塊，再用二分查找法在相應(yīng)塊中查找3若某線性表中最常用的操作是在最后一個(gè)元素之后插入一個(gè)元素和刪除最后一個(gè)元素，則采用（）存儲(chǔ)方式最節(jié)省運(yùn)算時(shí)間。①單鏈表②雙鏈表③帶頭結(jié)點(diǎn)的雙循環(huán)鏈表④容量足夠大的順序表4串是（）①一些符號(hào)構(gòu)成的序列②有限個(gè)字母構(gòu)成的序列③一個(gè)以上的字符構(gòu)成的序列④有限個(gè)字

3、符構(gòu)成的序列5堆排序在最壞情況下，其時(shí)間復(fù)雜性為（）①O(nlog2n)②O(n2)③O(log2n2)④O(log2n)6快速排序的記錄移動(dòng)次數(shù)（）比較次數(shù)，其總執(zhí)行時(shí)間為O(nlog2n)。①大于②大于等于③小于等于④小于7一棵二叉樹(shù)有n個(gè)結(jié)點(diǎn)，要按某順序?qū)υ摱鏄?shù)中的結(jié)點(diǎn)編號(hào)，（號(hào)碼為1n），編號(hào)須具有如下性質(zhì)：二叉樹(shù)中任一結(jié)點(diǎn)V，其編號(hào)等于其左子樹(shù)中結(jié)點(diǎn)的最大編號(hào)加1。而其右子樹(shù)中結(jié)點(diǎn)的最小編號(hào)等于V的編號(hào)加1。試問(wèn)應(yīng)按（）遍歷

4、順序編號(hào)。①前根②中根③后根④層次8.3個(gè)結(jié)點(diǎn)可構(gòu)成（）個(gè)不同形態(tài)的二叉樹(shù)。①2②3③4④59對(duì)有n個(gè)記錄的有序表采用二分查找，其平均查找長(zhǎng)度的量級(jí)為（）①O(log2n)②O(nlog2n)③O(n)④O(n2)10對(duì)有n個(gè)記錄的表按記錄鍵值有序的順序建立二叉樹(shù)，在這種情況下，其平均查找長(zhǎng)度的量級(jí)為（）①O(n)②O(nlog2n)③O(1)④(log2n)11棧操作的原則是（）①先進(jìn)先出②后進(jìn)先出③棧頂插入④棧頂刪除12設(shè)矩陣A是一

5、對(duì)稱矩陣(aij=aji1data=xpnext=NULL；＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿；＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿；四、應(yīng)用題（共四、應(yīng)用題（共2626分）分）1有向圖G的鄰接表如下圖所示，若刪去圖G中的邊＜V3，V6＞和＜V4，V5＞，試畫出修改后圖的鄰接表。（4分）V102V213^V346^V403V513^V61^5^1^頂點(diǎn)入度2有向圖如下圖所示，寫出以V1為出發(fā)點(diǎn)對(duì)圖進(jìn)行深度優(yōu)先搜索所得到的所有可能的訪問(wèn)序列。（

6、4分）3125463對(duì)于鍵值序列（4938659776132750），使用堆排序算法完成排序過(guò)程。要求：⑴畫出初始堆（用二叉樹(shù)表示）。⑵畫出分別輸出1327后重建的兩個(gè)堆。（5分）4.一個(gè)深度為d（根的層次號(hào)為1）的滿K叉樹(shù)有如下性質(zhì)：第d層上的結(jié)點(diǎn)都是葉子結(jié)點(diǎn)，其余各層上的每個(gè)結(jié)點(diǎn)都有K棵非空子樹(shù)。如果從根這一層開(kāi)始從左到右順序逐層對(duì)全部結(jié)點(diǎn)編號(hào)，且根結(jié)點(diǎn)的編號(hào)為1，問(wèn)編號(hào)為n的結(jié)點(diǎn)有右兄弟的條件是什么？其右兄弟的編號(hào)是多少？（3分）

7、5給定權(quán)值｛51012153040｝，構(gòu)造相應(yīng)的哈夫曼樹(shù)，要求寫構(gòu)造歩驟。（4分）6已知一表為（JanFebMarAprMayJunJulAugSepOctNovDec）按表中順序依次插入初始為空的二叉排序樹(shù)，要求：⑴畫出建立的二叉排序樹(shù)。（4分）⑵求出在等概率情況下查找成功的平均查找長(zhǎng)度。（2分）五、設(shè)計(jì)題（共五、設(shè)計(jì)題（共1414分）分）1設(shè)有一單鏈表L，結(jié)點(diǎn)結(jié)構(gòu)為data|next，結(jié)點(diǎn)個(gè)數(shù)至少3個(gè)，試畫出鏈表L的結(jié)構(gòu)圖，并編寫算