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

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

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

3、符構成的序列5堆排序在最壞情況下，其時間復雜性為（）①O(nlog2n)②O(n2)③O(log2n2)④O(log2n)6快速排序的記錄移動次數(shù)（）比較次數(shù)，其總執(zhí)行時間為O(nlog2n)。①大于②大于等于③小于等于④小于7一棵二叉樹有n個結點，要按某順序對該二叉樹中的結點編號，（號碼為1n），編號須具有如下性質(zhì)：二叉樹中任一結點V，其編號等于其左子樹中結點的最大編號加1。而其右子樹中結點的最小編號等于V的編號加1。試問應按（）遍歷

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

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

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

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