數(shù)據(jù)結(jié)構(gòu)試卷B

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

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