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

數(shù)據(jù)結(jié)構(gòu)導(dǎo)論模擬試卷(二)一、單項(xiàng)選擇題(在每小題的4個備選答案中.選出1個正確的答案，并將其號碼填在題干后的括號內(nèi)。每小題2分，共30分)一個具有n個頂點(diǎ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é)省運(yùn)算時間。A)單鏈表 B)雙鏈表C)帶頭結(jié)點(diǎn)的雙循環(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é)點(diǎn)，要按某順序?qū)υ摱鏄渲械慕Y(jié)點(diǎn)編號(號碼為l?n)，編號須具有如下性質(zhì)：二叉樹中任一結(jié)點(diǎn)V，其編號等于其左子樹中結(jié)點(diǎn)的最大編號加l，而其右子樹中結(jié)點(diǎn)的最小編號等于V的編號加l。試問應(yīng)按( )遍歷順序編號。A)前根 8)中根 C)后根 D)層次3個結(jié)點(diǎn)可構(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個單元，將其上三角部分（包括對角線）按行序?yàn)橹餍虼娣旁跀?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é)點(diǎn)，深度為K的二叉樹上有2k-1個結(jié)點(diǎn)c）二維數(shù)組是其數(shù)據(jù)元素為線性表的線性表D）棧的操作方式是先進(jìn)先出。二、填空題侮空2分，共28分）在帶有頭結(jié)點(diǎn)的單鏈表L中，若要刪除第一個結(jié)點(diǎn)，則需執(zhí)行下列三條語句:；L->next=U->next；free（U）；有一個長度為20的有序表采用二分查找方法進(jìn)行查找，共有—個元素的查找長度為3。采用冒泡排序?qū)τ衝個記錄的表A按鍵值遞增排序，若L的初始狀態(tài)是按鍵值遞增，則排序過程中記錄的比較次數(shù)為。若A初始狀態(tài)為遞減排列，則記錄的交換次數(shù)為。在無頭結(jié)點(diǎn)的雙鏈表中，指針P所指結(jié)點(diǎn)是第一個結(jié)點(diǎn)的條件是。G為無向圖，如果從G的某個頂點(diǎn)出發(fā)，進(jìn)行一次廣度優(yōu)先搜索.即可訪問圖的每個頂點(diǎn)，則該圖一定是 圖。如果一個有向圖中沒有，則該圖的全部頂點(diǎn)可以排成一個拓?fù)湫蛄?。深度?（根的層次號為1）的滿二叉樹有 個葉子結(jié)點(diǎn)。將一棵有100個結(jié)點(diǎn)的完全二叉樹按層編號，則編號為49的結(jié)點(diǎn)X，其雙親PARENT（X）的編號為。分別采用堆排序、快速排序、冒泡排序和歸并排序算法，對初始狀態(tài)為遞增序列的表按遞增順序排序，最省時的時算法，最費(fèi)時間的是 樹算法設(shè)有一個鏈隊(duì)，結(jié)點(diǎn)結(jié)構(gòu)為"僉I址”*'，front為隊(duì)頭指針.rear為隊(duì)尾指針，當(dāng)執(zhí)行入隊(duì)操作時需執(zhí)行下列語句：malloc（p）；p->data=x；p->next=NUlLL;11.有向圖G用鄰接矩陣A[l..n，l..n]存儲，其第i列的所有元素之和等于頂點(diǎn)i的。

三、應(yīng)用題（共28分）1.有向圖G的鄰接表如圖11所示，若刪去圖G中的邊＜V3,V6＞和（V4,V5）,試畫出修改后圖的鄰接表。（4分）頂點(diǎn)入度V021A1V21—3AV34—6AV40 h3 h5AV13A5V1A圖11圖G的鄰接表對下列有向圖12,寫出以頂點(diǎn)1為出發(fā)點(diǎn)對圖進(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é)點(diǎn)都是葉子結(jié)點(diǎn)，其余各層上的每個結(jié)點(diǎn)都有K棵非空子樹。如果從根這一層開始按從左到右順序逐層對全部結(jié)點(diǎn)編號，且根結(jié)點(diǎn)的編號為1,問編號為n的結(jié)點(diǎn)有右兄弟的條件是什么?其右兄弟的編號是多少?（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è)計(jì)題供14分）設(shè)有一單鏈表L,結(jié)點(diǎn)結(jié)構(gòu)為"血|，結(jié)點(diǎn)個數(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é)點(diǎn)結(jié)構(gòu)為出皿 ”壺些」，其中data域中存放一個字符，設(shè)計(jì)一個算法按先序遍歷順序僅打印出dam域?yàn)閿?shù)字的字符（即'0'WdataW'9'）。（6分）數(shù)據(jù)結(jié)構(gòu)導(dǎo)論模擬試卷(二)分析與解答一、單項(xiàng)選擇題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é)點(diǎn)的單鏈表L上刪除第一個結(jié)點(diǎn)，需依次執(zhí)行以下三條語句：U=L->next；L->next=U->next；free(U)答案：U=L->next。分析：二分查找的過程可以用一棵有序樹來表示，該樹第三層上有4個結(jié)點(diǎn)，表示經(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)先搜索，如果都能訪問到圖的每個頂點(diǎn)，則該圖一定是個連通圖。答案：連通。分析：一個有向圖存在拓?fù)湫蛄械臈l件之一是有向圖中不存在回路或環(huán)。答案：回路或環(huán)。答案：28-1=27=128。分析：完全二叉樹按層編號后，編號為m的結(jié)點(diǎn)，其雙親結(jié)點(diǎn)的編號為-。故當(dāng)m=49時，其雙親編號為49=24。2答案：24。答案：冒泡排序、快速排序。答案：rear一〉next=p,rear=p。答案：入度三、應(yīng)用題分析：在圖11所示的有向圖的鄰接表上刪除一條邊時.不僅要在對應(yīng)的出邊表中刪除一個結(jié)點(diǎn)，而且還要修改對應(yīng)頂點(diǎn)的入度值。答案：修改后的有向圖G的鄰接表如圖13所示。頂點(diǎn)入度圖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ǎn)的鍵值，都要對二叉樹調(diào)整一次，使其成為一個新的堆。答案：1）初始堆如圖14所示。""圖14初始堆2）輸出13后重建的堆如圖15所示。13圖15輸出13后重建的堆3）輸出27后重建的堆如圖16所示。13975076654927139750766549274.分析：在滿k叉樹中，個共同的雙親。比如：圖164.分析：在滿k叉樹中，個共同的雙親。比如：除編號為1的根結(jié)點(diǎn)外，其余結(jié)點(diǎn)依次為每k個結(jié)點(diǎn)擁有一第2號?第k+l號結(jié)點(diǎn)的雙親是第l號結(jié)點(diǎn);第k+2號?第2k+l號結(jié)點(diǎn)的雙親是第2號結(jié)點(diǎn);第2k+1號?第3k+1號結(jié)點(diǎn)的雙親是第3號結(jié)點(diǎn);從中可以看出，若編號為n,那么當(dāng)(n-1)%k=0時，它一定是某個結(jié)點(diǎn)的最右邊的孩子，即它的右邊不會再有兄弟了。反之，當(dāng)(n-1)%k70時，它的右邊一定還有兄弟。答案：編號為n的結(jié)點(diǎn)有右兄弟的條件是(n—1)%k尹0，該結(jié)點(diǎn)的右兄弟的編號是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é)點(diǎn)的過程。每插入一個結(jié)點(diǎn)，都是拿結(jié)點(diǎn)的值與根結(jié)點(diǎn)的值比較.若小于根結(jié)點(diǎn)的值，則往左子樹上插；若大于根結(jié)點(diǎn)的值，則往右子樹上插；若等于根結(jié)點(diǎn)的值.表示該結(jié)點(diǎn)已存在。在左、右子樹中，再重復(fù)上述步驟，直到找到合適的插入位置。答案：1)建立的二叉排序樹如圖18所示。2)在等概率情況下，查找成功的平均查找長度為(1*l+2*2+3*3+4*3+5*2+6*1)=竺=7=3.5。12 2Nov圖18建立的二叉排序樹四、設(shè)計(jì)題1.分析：先求出前兩個結(jié)點(diǎn)值的差b,然后再設(shè)置兩個指針，從表的第2個結(jié)點(diǎn)開始，依次比較相鄰兩結(jié)點(diǎn)值的差是否等于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(