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

數(shù)據(jù)結(jié)構(gòu)導(dǎo)論模擬試卷(二)一、單項(xiàng)選擇題(在每小題的4個(gè)備選答案中.選出1個(gè)正確的答案，并將其號(hào)碼填在題干后的括號(hào)內(nèi)。每小題2分，共30分)一個(gè)具有n個(gè)頂點(diǎn)的無向完全圖的邊數(shù)為()。n(n+1)n(n一1)A)2B)2C)n(n一1) D)n(n+1)在索引順序表中查找一個(gè)元素，可用的且最快的方法是()人)用順序查找法確定元素所在塊，再用順序查找法在相應(yīng)塊中查找8)用順序查找法確定元素所在塊，再用二分查找法在相應(yīng)塊中查技c)用二分查找法確定元素所在塊，再用順序查找法在相應(yīng)塊中查我D)用二分查找法確定元素所在塊，再用二分查找法在相應(yīng)塊中查找若某線性表中最常用的操作是在最后一個(gè)元素之后插入一個(gè)元素和刪除最后一個(gè)元素，則采用()存儲(chǔ)方式最節(jié)省運(yùn)算時(shí)間。A)單鏈表 B)雙鏈表C)帶頭結(jié)點(diǎn)的雙循環(huán)鏈表 D)容量足夠大的順序表串是()。A)一些符號(hào)構(gòu)成的序列 B)有限個(gè)字母構(gòu)成的序列C)一個(gè)以上的字符構(gòu)成的序列 D)有限個(gè)字符構(gòu)成的序列堆排序在最壞情況下，其時(shí)間復(fù)雜性為()。A)O(nlogn) B)O(n2) C)O(logn2) D)O(logn)快速排序的記錄移動(dòng)次數(shù)()比較次數(shù).其總執(zhí)行時(shí)間為O(nlog2n)。A)大于 B)大于等于 C)小于等于 D)小于一棵二叉樹有n個(gè)結(jié)點(diǎn)，要按某順序?qū)υ摱鏄渲械慕Y(jié)點(diǎn)編號(hào)(號(hào)碼為l?n)，編號(hào)須具有如下性質(zhì)：二叉樹中任一結(jié)點(diǎn)V，其編號(hào)等于其左子樹中結(jié)點(diǎn)的最大編號(hào)加l，而其右子樹中結(jié)點(diǎn)的最小編號(hào)等于V的編號(hào)加l。試問應(yīng)按( )遍歷順序編號(hào)。A)前根 8)中根 C)后根 D)層次3個(gè)結(jié)點(diǎn)可構(gòu)成()個(gè)不同形態(tài)的二叉樹。A)2 B)3 C)4 D)5對(duì)有n個(gè)記錄的有序表采用二分查找其平均查找長度的量級(jí)為()。A)O(logn) B)O(nlogn) C)O(n) D)O(n2)對(duì)有n個(gè)記錄的表按記錄鍵值有序的順序建立二叉排序樹，在這種情況下.其平均查找長度的量級(jí)為()。A)O(n) B)O(nlogn) C)O(1) D)O(logn)棧操作的原則是（）。A）先進(jìn)先出 8）后進(jìn)先出 C）棧頂插入 D）棧頂刪除設(shè)矩陣A是一對(duì)稱矩陣（a=a,1<i,j<8），若每個(gè)矩陣元素占3個(gè)單元，將其上三角部分（包括對(duì)角線）按行序?yàn)橹餍虼娣旁跀?shù)組B中，B的首址為1000,則矩陣元素a67的地址為（）。A）1031 B）1093 C）1096 D）1032鏈表適用于順序查找，但在鏈表中進(jìn)行（ ）操作的效率比在順序存儲(chǔ)結(jié)構(gòu)中進(jìn)行同樣操作的效率高。A）順序查找 B）二分法查找 C）快速查找 。插入任何一個(gè)無向連通圖的最小生成樹（）。A）只有一棵B）有一棵或多棵c）一定有多棵 D）可能不存在以下有關(guān)數(shù)據(jù)結(jié)構(gòu)的敘述，（）是正確的。A） 線性表的線性存儲(chǔ)結(jié)構(gòu)優(yōu)于鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)B） 二叉樹的第i層上有2巨個(gè)結(jié)點(diǎn)，深度為K的二叉樹上有2k-1個(gè)結(jié)點(diǎn)c）二維數(shù)組是其數(shù)據(jù)元素為線性表的線性表D）棧的操作方式是先進(jìn)先出。二、填空題侮空2分，共28分）在帶有頭結(jié)點(diǎn)的單鏈表L中，若要?jiǎng)h除第一個(gè)結(jié)點(diǎn)，則需執(zhí)行下列三條語句:；L->next=U->next；free（U）；有一個(gè)長度為20的有序表采用二分查找方法進(jìn)行查找，共有—個(gè)元素的查找長度為3。采用冒泡排序?qū)τ衝個(gè)記錄的表A按鍵值遞增排序，若L的初始狀態(tài)是按鍵值遞增，則排序過程中記錄的比較次數(shù)為。若A初始狀態(tài)為遞減排列，則記錄的交換次數(shù)為。在無頭結(jié)點(diǎn)的雙鏈表中，指針P所指結(jié)點(diǎn)是第一個(gè)結(jié)點(diǎn)的條件是。G為無向圖，如果從G的某個(gè)頂點(diǎn)出發(fā)，進(jìn)行一次廣度優(yōu)先搜索.即可訪問圖的每個(gè)頂點(diǎn)，則該圖一定是 圖。如果一個(gè)有向圖中沒有，則該圖的全部頂點(diǎn)可以排成一個(gè)拓?fù)湫蛄小Ｉ疃葹?（根的層次號(hào)為1）的滿二叉樹有 個(gè)葉子結(jié)點(diǎn)。將一棵有100個(gè)結(jié)點(diǎn)的完全二叉樹按層編號(hào)，則編號(hào)為49的結(jié)點(diǎn)X，其雙親PARENT（X）的編號(hào)為。分別采用堆排序、快速排序、冒泡排序和歸并排序算法，對(duì)初始狀態(tài)為遞增序列的表按遞增順序排序，最省時(shí)的時(shí)算法，最費(fèi)時(shí)間的是 樹算法設(shè)有一個(gè)鏈隊(duì)，結(jié)點(diǎn)結(jié)構(gòu)為"僉I址”*'，front為隊(duì)頭指針.rear為隊(duì)尾指針，當(dāng)執(zhí)行入隊(duì)操作時(shí)需執(zhí)行下列語句：malloc（p）；p->data=x；p->next=NUlLL;11.有向圖G用鄰接矩陣A[l..n，l..n]存儲(chǔ)，其第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的鄰接表對(duì)下列有向圖12,寫出以頂點(diǎn)1為出發(fā)點(diǎn)對(duì)圖進(jìn)行深度優(yōu)先搜索所得到的所有可能的訪問序列。（4分）對(duì)于鍵值序列（49,38,65,97,76,13,27,50），使用堆排序算法完成排序過程。要求：1） 畫出初始堆（用二叉樹表示）。（2分）2） 畫出分別輸出13,27后重建的兩個(gè)堆。（4分）一個(gè)深度為d（根的層次號(hào)為1）的滿K叉樹有如下性質(zhì)：第d層上的結(jié)點(diǎn)都是葉子結(jié)點(diǎn)，其余各層上的每個(gè)結(jié)點(diǎn)都有K棵非空子樹。如果從根這一層開始按從左到右順序逐層對(duì)全部結(jié)點(diǎn)編號(hào)，且根結(jié)點(diǎn)的編號(hào)為1,問編號(hào)為n的結(jié)點(diǎn)有右兄弟的條件是什么?其右兄弟的編號(hào)是多少?（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)個(gè)數(shù)至少3個(gè)，試畫出鏈表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è)一棵二叉樹以二叉鏈表作為存儲(chǔ)結(jié)構(gòu)，結(jié)點(diǎn)結(jié)構(gòu)為出皿 ”壺些」，其中data域中存放一個(gè)字符，設(shè)計(jì)一個(gè)算法按先序遍歷順序僅打印出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上刪除第一個(gè)結(jié)點(diǎn)，需依次執(zhí)行以下三條語句：U=L->next；L->next=U->next；free(U)答案：U=L->next。分析：二分查找的過程可以用一棵有序樹來表示，該樹第三層上有4個(gè)結(jié)點(diǎn)，表示經(jīng)過三次比較查找成功的元素個(gè)數(shù)為4。答案：4。分析：采用冒泡排序時(shí)，若初始時(shí)已經(jīng)自然有序，那么經(jīng)過一趟n-1次比比較后，算法就自動(dòng)終止了。若初始狀態(tài)為遞減排列，希望排序成遞增排列，則排序過程中比較一次、交換一次，總的比較、交換次數(shù)為n(n-1)/2,其中n-1為趟數(shù)，n/2為平均每趟的比較交換次數(shù)。答案：n(n-1)/2。答案：p->prior=NULL。分析：對(duì)無向圖來講，不管是對(duì)它進(jìn)行一次探度優(yōu)先搜索還是廣度優(yōu)先搜索，如果都能訪問到圖的每個(gè)頂點(diǎn)，則該圖一定是個(gè)連通圖。答案：連通。分析：一個(gè)有向圖存在拓?fù)湫蛄械臈l件之一是有向圖中不存在回路或環(huán)。答案：回路或環(huán)。答案：28-1=27=128。分析：完全二叉樹按層編號(hào)后，編號(hào)為m的結(jié)點(diǎn)，其雙親結(jié)點(diǎn)的編號(hào)為-。故當(dāng)m=49時(shí)，其雙親編號(hào)為49=24。2答案：24。答案：冒泡排序、快速排序。答案：rear一〉next=p,rear=p。答案：入度三、應(yīng)用題分析：在圖11所示的有向圖的鄰接表上刪除一條邊時(shí).不僅要在對(duì)應(yīng)的出邊表中刪除一個(gè)結(jié)點(diǎn)，而且還要修改對(duì)應(yīng)頂點(diǎn)的入度值。答案：修改后的有向圖G的鄰接表如圖13所示。頂點(diǎn)入度圖13修改后的有向圖G的鄰接表答案：共有3個(gè)訪問序列：1,2,5,4.3,61,3,6,4,5,21.3,5,4,6,2分析：建堆過程參見前述（8.1節(jié)的有關(guān)說明）。在排序過程中，每輸出一次根結(jié)點(diǎn)的鍵值，都要對(duì)二叉樹調(diào)整一次，使其成為一個(gè)新的堆。答案：1）初始堆如圖14所示。""圖14初始堆2）輸出13后重建的堆如圖15所示。13圖15輸出13后重建的堆3）輸出27后重建的堆如圖16所示。13975076654927139750766549274.分析：在滿k叉樹中，個(gè)共同的雙親。比如：圖164.分析：在滿k叉樹中，個(gè)共同的雙親。比如：除編號(hào)為1的根結(jié)點(diǎn)外，其余結(jié)點(diǎn)依次為每k個(gè)結(jié)點(diǎn)擁有一第2號(hào)?第k+l號(hào)結(jié)點(diǎn)的雙親是第l號(hào)結(jié)點(diǎn);第k+2號(hào)?第2k+l號(hào)結(jié)點(diǎn)的雙親是第2號(hào)結(jié)點(diǎn);第2k+1號(hào)?第3k+1號(hào)結(jié)點(diǎn)的雙親是第3號(hào)結(jié)點(diǎn);從中可以看出，若編號(hào)為n,那么當(dāng)(n-1)%k=0時(shí)，它一定是某個(gè)結(jié)點(diǎn)的最右邊的孩子，即它的右邊不會(huì)再有兄弟了。反之，當(dāng)(n-1)%k70時(shí)，它的右邊一定還有兄弟。答案：編號(hào)為n的結(jié)點(diǎn)有右兄弟的條件是(n—1)%k尹0，該結(jié)點(diǎn)的右兄弟的編號(hào)是n+l。分析：哈夫曼樹的構(gòu)造過程參見4.1節(jié)中的有關(guān)說明。答案：哈夫曼樹的構(gòu)造過程如圖17所示1510(a)初始時(shí)森林中有6顆樹將去掉的兩顆權(quán)值最小的樹合并為一顆權(quán)值為151510(a)初始時(shí)森林中有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)的過程。每插入一個(gè)結(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.分析：先求出前兩個(gè)結(jié)點(diǎn)值的差b,然后再設(shè)置兩個(gè)指針，從表的第2個(gè)結(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(