數據結構導論模擬試卷(二)一、單項選擇題(在每小題的4個備選答案中.選出1個正確的答案，并將其號碼填在題干后的括號內。每小題2分，共30分)一個具有n個頂點的無向完全圖的邊數為()。n(n+1)n(n一1)A)2B)2C)n(n一1) D)n(n+1)在索引順序表中查找一個元素，可用的且最快的方法是()人)用順序查找法確定元素所在塊，再用順序查找法在相應塊中查找8)用順序查找法確定元素所在塊，再用二分查找法在相應塊中查技c)用二分查找法確定元素所在塊，再用順序查找法在相應塊中查我D)用二分查找法確定元素所在塊，再用二分查找法在相應塊中查找若某線性表中最常用的操作是在最后一個元素之后插入一個元素和刪除最后一個元素，則采用()存儲方式最節省運算時間。A)單鏈表 B)雙鏈表C)帶頭結點的雙循環鏈表 D)容量足夠大的順序表串是()。A)一些符號構成的序列 B)有限個字母構成的序列C)一個以上的字符構成的序列 D)有限個字符構成的序列堆排序在最壞情況下，其時間復雜性為()。A)O(nlogn) B)O(n2) C)O(logn2) D)O(logn)快速排序的記錄移動次數()比較次數.其總執行時間為O(nlog2n)。A)大于 B)大于等于 C)小于等于 D)小于一棵二叉樹有n個結點，要按某順序對該二叉樹中的結點編號(號碼為l?n)，編號須具有如下性質：二叉樹中任一結點V，其編號等于其左子樹中結點的最大編號加l，而其右子樹中結點的最小編號等于V的編號加l。試問應按( )遍歷順序編號。A)前根 8)中根 C)后根 D)層次3個結點可構成()個不同形態的二叉樹。A)2 B)3 C)4 D)5對有n個記錄的有序表采用二分查找其平均查找長度的量級為()。A)O(logn) B)O(nlogn) C)O(n) D)O(n2)對有n個記錄的表按記錄鍵值有序的順序建立二叉排序樹，在這種情況下.其平均查找長度的量級為()。A)O(n) B)O(nlogn) C)O(1) D)O(logn)棧操作的原則是（）。A）先進先出 8）后進先出 C）棧頂插入 D）棧頂刪除設矩陣A是一對稱矩陣（a=a,1<i,j<8），若每個矩陣元素占3個單元，將其上三角部分（包括對角線）按行序為主序存放在數組B中，B的首址為1000,則矩陣元素a67的地址為（）。A）1031 B）1093 C）1096 D）1032鏈表適用于順序查找，但在鏈表中進行（ ）操作的效率比在順序存儲結構中進行同樣操作的效率高。A）順序查找 B）二分法查找 C）快速查找 。插入任何一個無向連通圖的最小生成樹（）。A）只有一棵B）有一棵或多棵c）一定有多棵 D）可能不存在以下有關數據結構的敘述，（）是正確的。A） 線性表的線性存儲結構優于鏈式存儲結構B） 二叉樹的第i層上有2巨個結點，深度為K的二叉樹上有2k-1個結點c）二維數組是其數據元素為線性表的線性表D）棧的操作方式是先進先出。二、填空題侮空2分，共28分）在帶有頭結點的單鏈表L中，若要刪除第一個結點，則需執行下列三條語句:；L->next=U->next；free（U）；有一個長度為20的有序表采用二分查找方法進行查找，共有—個元素的查找長度為3。采用冒泡排序對有n個記錄的表A按鍵值遞增排序，若L的初始狀態是按鍵值遞增，則排序過程中記錄的比較次數為。若A初始狀態為遞減排列，則記錄的交換次數為。在無頭結點的雙鏈表中，指針P所指結點是第一個結點的條件是。G為無向圖，如果從G的某個頂點出發，進行一次廣度優先搜索.即可訪問圖的每個頂點，則該圖一定是 圖。如果一個有向圖中沒有，則該圖的全部頂點可以排成一個拓撲序列。深度為8（根的層次號為1）的滿二叉樹有 個葉子結點。將一棵有100個結點的完全二叉樹按層編號，則編號為49的結點X，其雙親PARENT（X）的編號為。分別采用堆排序、快速排序、冒泡排序和歸并排序算法，對初始狀態為遞增序列的表按遞增順序排序，最省時的時算法，最費時間的是 樹算法設有一個鏈隊，結點結構為"僉I址”*'，front為隊頭指針.rear為隊尾指針，當執行入隊操作時需執行下列語句：malloc（p）；p->data=x；p->next=NUlLL;11.有向圖G用鄰接矩陣A[l..n，l..n]存儲，其第i列的所有元素之和等于頂點i的。

三、應用題（共28分）1.有向圖G的鄰接表如圖11所示，若刪去圖G中的邊＜V3,V6＞和（V4,V5）,試畫出修改后圖的鄰接表。（4分）頂點入度V021A1V21—3AV34—6AV40 h3 h5AV13A5V1A圖11圖G的鄰接表對下列有向圖12,寫出以頂點1為出發點對圖進行深度優先搜索所得到的所有可能的訪問序列。（4分）對于鍵值序列（49,38,65,97,76,13,27,50），使用堆排序算法完成排序過程。要求：1） 畫出初始堆（用二叉樹表示）。（2分）2） 畫出分別輸出13,27后重建的兩個堆。（4分）一個深度為d（根的層次號為1）的滿K叉樹有如下性質：第d層上的結點都是葉子結點，其余各層上的每個結點都有K棵非空子樹。如果從根這一層開始按從左到右順序逐層對全部結點編號，且根結點的編號為1,問編號為n的結點有右兄弟的條件是什么?其右兄弟的編號是多少?（4分）給定權值｛5,10,12,15,30,40｝，構造相應的赫夫曼樹，要求寫出構造步驟。（4分）已知一表為（Jan,Feb,Mar,Apr,May,Jun,Jul,Aug,Sep,Oct,Nov,Dec）。按表中順序依次插入初始為空的二叉排序樹，要求：1） 畫出建立的二叉排序樹。（4分）2） 求出在等概率情況下查找成功的平均查找長度。（2分）四、設計題供14分）設有一單鏈表L,結點結構為"血|，結點個數至少3個，試畫出鏈表l的結構圖，并編寫算法判斷該單鏈表L中的元素是否成等差關系，即：設各元素值依次為ai，a，a，…，a，判斷a-a.=a.-a是否成立，其中i滿足2WiWn-l。（8分）2 3 n i+1iii-1設一棵二叉樹以二叉鏈表作為存儲結構，結點結構為出皿 ”壺些」，其中data域中存放一個字符，設計一個算法按先序遍歷順序僅打印出dam域為數字的字符（即'0'WdataW'9'）。（6分）數據結構導論模擬試卷(二)分析與解答一、單項選擇題B.2,C.3,D.4,D.5,A.6,C.7,B.8,D.9,A.10,A.B.12,B.13,D.14,B.15,C.二、填空題分析：在帶有頭結點的單鏈表L上刪除第一個結點，需依次執行以下三條語句：U=L->next；L->next=U->next；free(U)答案：U=L->next。分析：二分查找的過程可以用一棵有序樹來表示，該樹第三層上有4個結點，表示經過三次比較查找成功的元素個數為4。答案：4。分析：采用冒泡排序時，若初始時已經自然有序，那么經過一趟n-1次比比較后，算法就自動終止了。若初始狀態為遞減排列，希望排序成遞增排列，則排序過程中比較一次、交換一次，總的比較、交換次數為n(n-1)/2,其中n-1為趟數，n/2為平均每趟的比較交換次數。答案：n(n-1)/2。答案：p->prior=NULL。分析：對無向圖來講，不管是對它進行一次探度優先搜索還是廣度優先搜索，如果都能訪問到圖的每個頂點，則該圖一定是個連通圖。答案：連通。分析：一個有向圖存在拓撲序列的條件之一是有向圖中不存在回路或環。答案：回路或環。答案：28-1=27=128。分析：完全二叉樹按層編號后，編號為m的結點，其雙親結點的編號為-。故當m=49時，其雙親編號為49=24。2答案：24。答案：冒泡排序、快速排序。答案：rear一〉next=p,rear=p。答案：入度三、應用題分析：在圖11所示的有向圖的鄰接表上刪除一條邊時.不僅要在對應的出邊表中刪除一個結點，而且還要修改對應頂點的入度值。答案：修改后的有向圖G的鄰接表如圖13所示。頂點入度圖13修改后的有向圖G的鄰接表答案：共有3個訪問序列：1,2,5,4.3,61,3,6,4,5,21.3,5,4,6,2分析：建堆過程參見前述（8.1節的有關說明）。在排序過程中，每輸出一次根結點的鍵值，都要對二叉樹調整一次，使其成為一個新的堆。答案：1）初始堆如圖14所示。""圖14初始堆2）輸出13后重建的堆如圖15所示。13圖15輸出13后重建的堆3）輸出27后重建的堆如圖16所示。13975076654927139750766549274.分析：在滿k叉樹中，個共同的雙親。比如：圖164.分析：在滿k叉樹中，個共同的雙親。比如：除編號為1的根結點外，其余結點依次為每k個結點擁有一第2號?第k+l號結點的雙親是第l號結點;第k+2號?第2k+l號結點的雙親是第2號結點;第2k+1號?第3k+1號結點的雙親是第3號結點;從中可以看出，若編號為n,那么當(n-1)%k=0時，它一定是某個結點的最右邊的孩子，即它的右邊不會再有兄弟了。反之，當(n-1)%k70時，它的右邊一定還有兄弟。答案：編號為n的結點有右兄弟的條件是(n—1)%k尹0，該結點的右兄弟的編號是n+l。分析：哈夫曼樹的構造過程參見4.1節中的有關說明。答案：哈夫曼樹的構造過程如圖17所示1510(a)初始時森林中有6顆樹將去掉的兩顆權值最小的樹合并為一顆權值為151510(a)初始時森林中有6顆樹將去掉的兩顆權值最小的樹合并為一顆權值為15的樹將去掉的兩顆權值最小的樹合并為一顆權值為27的樹將去掉的兩顆權值最小的樹合并為一顆權值為42的樹將去掉的兩顆權值最小的樹合并為一顆權值為70的樹最終得到的哈夫曼樹圖17哈夫曼樹的構造過程分析：二叉排序樹的建立過程就是在二叉排序樹上不斷插入新結點的過程。每插入一個結點，都是拿結點的值與根結點的值比較.若小于根結點的值，則往左子樹上插；若大于根結點的值，則往右子樹上插；若等于根結點的值.表示該結點已存在。在左、右子樹中，再重復上述步驟，直到找到合適的插入位置。答案：1)建立的二叉排序樹如圖18所示。2)在等概率情況下，查找成功的平均查找長度為(1*l+2*2+3*3+4*3+5*2+6*1)=竺=7=3.5。12 2Nov圖18建立的二叉排序樹四、設計題1.分析：先求出前兩個結點值的差b,然后再設置兩個指針，從表的第2個結點開始，依次比較相鄰兩結點值的差是否等于b。如果都等于b,則返回真值True，否則返回假值False。答案：單鏈表的結構圖如圖19所示。圖19單鏈表結構圖算法：intisrise(lktlstL)(p=L->next；b=p->data-L->data；while(p->next!=NULL){q=p->next；if(q->data-p->data!=b)return(