數(shù)據(jù)結(jié)構(gòu)6章習(xí)題

1、考試學(xué)資學(xué)習(xí)網(wǎng)押題算法與數(shù)據(jù)結(jié)構(gòu)第 1-6 章課堂測(cè)驗(yàn)(雙號(hào))一、選擇題1、已知一個(gè)棧的進(jìn)棧序列是1,2,3,n,其輸出序列是p,p ,p ,若p=n,則121np的值。 ( c ) i (A) i (B) n-i(C) n-i+1(D) 不確定2、設(shè)n個(gè)元素進(jìn)棧序列是1,2,3,n,其輸出序列是p,p,p,若p=3,則p2n恒的值。 ( c )(A) 一定是 2(B) 一定是 1(C) 不可能是 1(D) 以上都不對(duì)3、若一棵二叉樹具有10 個(gè)度為 2 的結(jié)點(diǎn)， 5 個(gè)度為 1 的結(jié)點(diǎn)，則度為 0 的結(jié)點(diǎn)個(gè)數(shù)是( b )A.6B.11C.15 D.不確定4、在下述結(jié)論中，正確的是(d )只有

2、一個(gè)結(jié)點(diǎn)的二叉樹的度為 0;二叉樹的度為 2；二叉樹的左右子樹可任意交換;深度為 K 的完全二叉樹的結(jié)點(diǎn)個(gè)數(shù)小于或等于深度相同的滿二叉樹。A. B. C. D. 5、一棵樹高為K 的完全二叉樹至少有()個(gè)結(jié)點(diǎn)。 ( a )kk-1k-1k D.21B.2+1C.2 A.2-二、簡(jiǎn)答題1 簡(jiǎn)述下列術(shù)語：線性表，順序表，鏈表。2 線性表：最常用且最簡(jiǎn)單的一種數(shù)據(jù)結(jié)構(gòu)。一個(gè)線性表是n 個(gè)數(shù)據(jù)元素的有限序列。順序表：是指用一組連續(xù)的存儲(chǔ)單元一次存儲(chǔ)線性表中的數(shù)據(jù)元素。物理結(jié)構(gòu)和邏輯結(jié)3構(gòu)都相鄰。鏈表：邏輯結(jié)構(gòu)相鄰的數(shù)據(jù)元素物理結(jié)構(gòu)不一定相鄰。采用指針的形式連接起來。 42 何時(shí)選用順序表，何時(shí)選用鏈表

3、作為線性表的存儲(chǔ)結(jié)構(gòu)合適?各自的主要優(yōu)缺點(diǎn)是什么 ?不需要經(jīng)常大量的修改表或需要隨機(jī)存取的情況下可以選用順序表；相反需要經(jīng)常大量的修改表，但不是頻繁的隨機(jī)存取的情況下可選用鏈?zhǔn)奖怼? 鏈表所表示的元素是否有序 ?如有序， 則有序性體現(xiàn)于何處?鏈表所表示的元素是否一定要在物理上是相鄰的 ?有序表的有序性又如何理解?答：有序。有序性體現(xiàn)在通過指針數(shù)據(jù)元素有序的相連。物理上不一定要相鄰。 4 設(shè) A 和 B 是兩個(gè)按元素值遞增有序的單鏈表，寫一算法將A和B歸并為按按元素值遞減有 序的單鏈表C,試分析算法的時(shí)間復(fù)雜度。void ListInsert(SqList A,SqList B,SqList C

4、)ElemType *p,*q,*s;P=&A;q=&B;s=&C;while(p.next!=NULL|q.next!=NULL) if(p.next.data<=q.next.data)if(s.next!=NULL)p.next=s.next;s.next=p.next;p+;elseif(s.next!=NULL)q.next=s.next;s.next=q.next;q+;while(p.next!=NULL)p.next=s.next;s.next=p.next;while(q.next!=NULL)q.next=s.next;s.next=q.nex

5、t;4、例：什么是隊(duì)列的上溢現(xiàn)象和假溢出現(xiàn)象？解決它們有哪些方法？答：在隊(duì)列的順序存儲(chǔ)結(jié)構(gòu)中，設(shè)頭指針為front,隊(duì)尾指針rear,隊(duì)的容量（存儲(chǔ)空間的大小 ）為 MaxSize 。 當(dāng)有元素加入到隊(duì)列時(shí) ,若 rear=MaxSize（ 初始時(shí) rear=0）則發(fā)生隊(duì)列的上溢現(xiàn)象,該元素不能加入隊(duì)列。 特別要注意的是隊(duì)列的假溢出現(xiàn)象 :隊(duì)列中還有剩余空間但元素卻不能進(jìn)入隊(duì)列 ,造成這種現(xiàn)象的原因是由于隊(duì)列的操作方法所致。解決隊(duì)列上溢的方法有以下幾種 :1）建立一個(gè)足夠大的存儲(chǔ)空間,但這樣做會(huì)造成采用平移元素 : 當(dāng)出現(xiàn)假溢出時(shí)可采用以下幾種方法（2） 空間的使用效率降低。的方法 :每當(dāng)隊(duì)列

6、中加入一個(gè)元素時(shí), 隊(duì)列中已有的元素向隊(duì)頭移動(dòng)一個(gè)位置（當(dāng) 然要有空閑的空間可供移動(dòng)）；每當(dāng)刪除一個(gè)隊(duì)頭元素時(shí)，則依次移動(dòng)隊(duì)中的元素 ,始終使 front 指針指向隊(duì)列中的第一個(gè)位置； 采用環(huán)形隊(duì)列方式:把隊(duì)列看成一個(gè)首尾相接的環(huán)形隊(duì)列 ,在環(huán)形隊(duì)列上進(jìn)行插入或刪除運(yùn)算時(shí)仍然遵循“先進(jìn)先出”的原則。 ”5、例：對(duì)于順序隊(duì)列來說, 如果知道隊(duì)首元素的位置和隊(duì)列中元素個(gè)數(shù), 則隊(duì)尾元素所在位置顯然是可以計(jì)算的。也就是說, 可以用隊(duì)列中元素個(gè)數(shù)代替隊(duì)尾指針。編寫出這種循環(huán)順序隊(duì)列的初始化、入隊(duì)、出隊(duì)和判空算法。解 : 當(dāng)已知隊(duì)首元素的位置front 和隊(duì)列中元素個(gè)數(shù)count 后 :隊(duì)空的條件為 :

7、count=0隊(duì)滿的條件為:count=MaxSize計(jì)算隊(duì)尾位置rear:rear=(front+count)%MaxSize對(duì)應(yīng)的算法如下 :typedef struct ElemType dataMaxSize;int front; /* 隊(duì)首指針 */int count; /* 隊(duì)列中元素個(gè)數(shù)*/ QuType; /* 隊(duì)列類型 */void InitQu(QuType *&q)/* 隊(duì)列 q 初始化 */q=(QuType *)malloc(sizeof(QuType);q->front=0;q->count=0;int EnQu(QuType *&q,E

8、lemType x) /* 進(jìn)隊(duì) */ int rear;if (q->count=MaxSize) return 0; /* 隊(duì)滿上溢出 */ else rear=(q->front+q->count+MaxSize)%MaxSize; /*求隊(duì)尾位置*/rear=(rear+1)%MaxSize; /* 隊(duì)尾位置進(jìn)1*/q->datarear=x;q->count+;return 1;int DeQu(QuType *&q,ElemType &x) /* 出隊(duì) */if (q->count=0) /* 隊(duì)空下溢出 */return 0;e

9、lse q->front=(q->front+1)%MaxSize;x=q->dataq->front;q->count-;return 1;int QuEmpty(QuType *q)/* 判空*/return(q->count=0);1設(shè)有一個(gè)棧，元素進(jìn)棧的次序?yàn)?a, b, c。問經(jīng)過棧操作后可以得到哪些輸 出 序列？；bca ； bac； cba； abc； acb2循環(huán)隊(duì)列的優(yōu)點(diǎn)是什么？如何判斷它的空和滿？ 優(yōu)點(diǎn)：可以克服順序隊(duì)列的“假上溢”現(xiàn)象，能夠使存儲(chǔ)隊(duì)列的向量空間得到充分利用。判斷循環(huán)隊(duì)列的空或滿不能以頭尾指針是否相等來確定，一般是通過以下

10、幾種方法：一是另設(shè)一布爾變量來區(qū)別隊(duì)列的空和滿。 二是約定入隊(duì)前，測(cè)試尾指針在循環(huán)意義下加 1后是否等于頭指 針，若相等則認(rèn)為隊(duì)滿。三是設(shè)置一計(jì)數(shù)器記錄隊(duì)列中元素的總數(shù)，不僅可判別空或滿，還可以得到隊(duì)列中元素的個(gè)數(shù)2設(shè)有一個(gè)靜態(tài)順序隊(duì)列，向量大小為MAX判斷隊(duì)列為空的條件是什么？隊(duì)列滿的條件是什么？3 隊(duì)列為空：front=rear。隊(duì)滿：rear=MAX -1 或 front=rear4 （隊(duì)首指針front , 一個(gè)隊(duì)尾指針rear）55設(shè)有一個(gè)靜態(tài)循環(huán)隊(duì)列，向量大小為MAX判斷隊(duì)列為空的條件是什么？隊(duì) 列 滿的條件是什么？6循環(huán)隊(duì)列為空：front=rear 。 循環(huán)隊(duì)列滿：（rear+

11、1）%MAX=front。（隊(duì)首指針front , 一個(gè)隊(duì)尾指針 7 rear）85設(shè)Q0,6是一個(gè)靜態(tài)順序隊(duì)列，初始狀態(tài)為 front=rear=0 ,請(qǐng)畫出做完下列 操作后隊(duì)列的頭尾指針的狀態(tài)變化情況，若不能入對(duì)，請(qǐng)指出其元素，并說明 理由。a, b, c, d 入隊(duì)a, b, c 出隊(duì)入隊(duì) i , j , k , l , md, i出隊(duì)n, o, p, q, r 入隊(duì)，其中l(wèi),m,n,o,p,q,r均由于隊(duì)列假溢出問題無法入隊(duì)6假設(shè)Q0,5是一個(gè)循環(huán)隊(duì)列，初始狀態(tài)為front=rear=0 ,請(qǐng)畫出做完下列操 作后隊(duì)列的頭尾指針的狀態(tài)變化情況，若不能入對(duì)，請(qǐng)指出其元素，并說明理由。d,

12、e, b, g, h 入隊(duì)d, e出隊(duì)i , j , k , l , m 入隊(duì)b出隊(duì)入隊(duì) n, o, p, q, r假設(shè)在樹中，結(jié)點(diǎn)x是結(jié)點(diǎn)y的雙親時(shí)，用(x,y)來表示樹邊。已知一棵樹的 樹邊集合為 (e,i), (b,e), (b,d), (a,b), (g,j), (c,g), (c,f), (h,l), (c,h),(a,c) ,用樹型表示法表示該樹，并回答下列問題： 哪個(gè)是根結(jié)點(diǎn)？哪些是葉子結(jié)點(diǎn)？哪個(gè)是g的雙親？哪些是g的祖先？哪 些是g的孩子？那些是e的子孫？哪些是e的兄弟？哪些是f的兄弟？多少？根節(jié)點(diǎn)：ag的祖先：c , ae的兄弟：db的層次：2b和n的層次各是多少？樹的深度是

13、多少？以結(jié)點(diǎn)c為根的子樹的深度是葉子節(jié)點(diǎn)：i ,d , j, f , lg的雙親節(jié)點(diǎn)：cg的孩子：je的子孫：if的兄弟：g , h樹的深度：4以結(jié)點(diǎn)c為根的子樹的深度：3一棵深度為h的滿k叉樹有如下性質(zhì)：第h層上的結(jié)點(diǎn)都是葉子結(jié)點(diǎn)，其余各 層上每個(gè)結(jié)點(diǎn)都有k棵非空子樹。如果按層次順序(同層自左至右)從1開始對(duì)全 部結(jié)點(diǎn)編號(hào)，問：各層的結(jié)點(diǎn)數(shù)是多少？編號(hào)為i的結(jié)點(diǎn)的雙親結(jié)點(diǎn)(若存在)的編號(hào)是多少？編號(hào)為i的結(jié)點(diǎn)的第j個(gè)孩子結(jié)點(diǎn)(若存在)的編號(hào)是多少？編號(hào)為i的結(jié)點(diǎn)的有右兄弟的條件是什么？其右兄弟的編號(hào)是多少？設(shè)層號(hào)為i的結(jié)點(diǎn)數(shù)目為 m=kA(i-1)(i+k-2)也就是的最大整數(shù)。(i+k-2

14、)/k不大于(i+k-2)/k(的結(jié)點(diǎn)的雙親結(jié)點(diǎn)的編號(hào)是：i編號(hào)為(2)與k整除的結(jié)果.以下/表示整除。(3)編號(hào)為i的結(jié)點(diǎn)的第j個(gè)孩子結(jié)點(diǎn)編號(hào)是：k*(i-1)+1+j;(4)編號(hào)為i的結(jié)點(diǎn)有右兄弟的條件是(i-1)能被k整除右兄弟的編號(hào)是i+1.三、算法理解1、已知P結(jié)點(diǎn)是某雙向鏈表的中間節(jié)點(diǎn)，畫圖并寫出下列操作的語句序列 (1)在P結(jié)點(diǎn)后插入S結(jié)點(diǎn)。(2)刪除P結(jié)點(diǎn)的后繼結(jié)點(diǎn)Q。結(jié)點(diǎn)結(jié)構(gòu)如下：PriorDataNext（其中Prior、Data、Next分別為前驅(qū)節(jié)點(diǎn)指針、數(shù)據(jù)域、后繼節(jié)點(diǎn)指針。） 答：（1） P->Next->Prior=S; S->Next=P-&g

15、t;Next; P->Next=S; S->Prior=P;（2） Q=P->Next; P->Next=P->Next->Next; P->Next->Prior=P; free（Q）;4、假設(shè)一棵二叉樹的前序序列為 EBADCFHGIKJ中序序列為ABCDEFGHIJK請(qǐng)畫出該樹，并寫出后序序列。（要求寫出分析過程）確定二叉樹的結(jié)構(gòu)，只需要采用遞歸的方式確定每棵子樹的根結(jié)點(diǎn)和左、右子樹 的先序、中序序列即可。先序序列的第一個(gè)結(jié)點(diǎn)必然是根結(jié)點(diǎn)，左、右子樹的中 序序列在二叉樹的中序序列中，分別在根結(jié)點(diǎn)的兩邊；他們的先序序列在二叉樹 的先序序列中先

16、后連續(xù)排列。L Q.front -EBFHDAIGCKJ個(gè)字母組成，8這H G F、E、D C、R A假設(shè)用于通訊的電文由）分（8、7. - 0.21 , 0.06, 0.320.03 ,字母在電文中出現(xiàn)的頻率為 0.070.19 , 0.02, 8 個(gè)字母哈夫曼樹并設(shè)計(jì)哈夫曼編碼。0.1 ,畫出這lipar3121732寫出0右1然后根據(jù)左a=1010 b=00 c=10000d=1001 e=11 f=10001g=01設(shè)有如圖6-27所示的二叉樹。分別用順序存儲(chǔ)方法和鏈接存儲(chǔ)方法畫出該二叉樹的存儲(chǔ)結(jié)構(gòu)。寫出該二叉樹的先序、中序、后序遍歷序列。abcdefg00hk00mn順序存儲(chǔ)結(jié)構(gòu):鏈

17、式存儲(chǔ)結(jié)構(gòu).acb?fde ?hmabdehkcfgmn 先序：dbhekafcmgn 中序：dhkebfmngca后序：和ABDGHCEFI已知一棵二叉樹的先序遍歷序歹和中序遍歷序歹分別為ACBFEDIHGGDHBAECIF請(qǐng)畫出這棵二叉樹，然后給出該樹的后序遍歷序列。后序：GHDBEIFCA設(shè)一棵二叉樹的中序遍歷序列和后序遍歷序列分別為BDCEAFHG DECBHGFA請(qǐng)畫出這棵二叉樹，然后給出該樹的先序序列。.AFBGCHDEABCDEFGH先序遍歷：和dgbaekchif已知一棵二叉樹的中序遍歷序列和后序遍歷序列分別為，請(qǐng)畫出這棵二叉樹對(duì)應(yīng)的中序線索樹和后序線索樹。gdbkeihfca

18、二叉樹：中序線索樹：abcdefgkhi后序線索樹：acbfdehgki以二叉鏈表為存儲(chǔ)結(jié)構(gòu)，請(qǐng)分別寫出求二叉樹的結(jié)點(diǎn)總數(shù)及葉子結(jié)點(diǎn)總數(shù)的算法。葉子節(jié)點(diǎn)數(shù)：50MAX_NODE #define*T)int search_leaves( BTNode*StackMAX_NODE ,*p=T; BTNodetop=0, num=0; int(T!=NULL)ifstack+top=p ; while (top>0) p=stacktop-;if (p->Lchild=NULL&&p->Rchild=NULL) num+ ;(p->Rchild!=NULL )

19、 ifstack+top=p->Rchild;(p->Lchild!=NULL ) ifstack+top=p->Lchild;return(num);F所示的二叉樹是森林所對(duì)應(yīng)的二叉樹，請(qǐng)畫出森林。F6-27設(shè)圖：F森林angckbemfhd6-28設(shè)有一棵樹，如圖所示。請(qǐng)分別用雙親表示法、孩子表示法、孩子兄弟表示法給出該樹的存儲(chǔ)結(jié)構(gòu)。請(qǐng)給出該樹的先序遍歷序列和后序遍歷序列。請(qǐng)將這棵樹轉(zhuǎn)換成二叉樹。雙親表示法：-10a0b10c203m14d15e26h2k728g39f310n孩子表示法：？3120a?541b?8762c?10m39?d4?e5?h6?k7?g8?f9

20、?n10孩子兄弟表示法：abcdmehfkngedgkhnfmcba后序： 先序： abdechkgmfn:叉相寸： abcdmehfkng樹，并W10)設(shè)給定權(quán)值集合 w=3,5,7,8,11,12,請(qǐng)構(gòu)造關(guān)于的一棵 huffmanWPL。求其加權(quán)路徑長(zhǎng)度一一 a 753WPL=12*2+3*4+5*4+7*3+8*2+11*2=115中的字符構(gòu)成，(11)假設(shè)用于通信的電文是由字符集a, b, c, d, e, f, g, h0.03, 80.32,個(gè)字符在電文中出現(xiàn)的概率分別為 0.07, 0.19, 0.02, 0.06,這0.21, 0.10。按左子樹根結(jié)點(diǎn)的權(quán)小于等于右子樹根結(jié)點(diǎn)的

21、權(quán)的樹 (請(qǐng)畫出對(duì)應(yīng)的huffman。次序構(gòu)造)求出每個(gè)字符的huffman 編碼。0.320.190.21(e)(b)(g)0.100.060.07(h)(a)(d)0.030.02(c)然后根據(jù)左1寫出0右a=1010b=00c=10000d=1001e=11f=10001g=01h=1011分析其時(shí)間復(fù)雜度。，的算法如下C=A+Bt方陣相加n、求兩個(gè)3.*/#define MAX 20 /*定義最大的方階void MatrixAdd(int n,intAMAXMAX,int BMAXMAX,intCMAXMAX)int i,j;for (i=0;i<n;i+)for (j=0;j&

22、lt;n;j+)Cij=A皿+Bi皿nA2;這條語句執(zhí)行的頻率為答：因?yàn)镃ij=Aij+Bij;。所以其時(shí)間復(fù)雜度為0(nA2)四、算法設(shè)計(jì)題，棧1、請(qǐng)描述隊(duì)列和堆棧的特點(diǎn)，并設(shè)計(jì)一個(gè)算法實(shí)現(xiàn)：用 兩個(gè)棧(棧A B)實(shí)現(xiàn)一個(gè)隊(duì)列，請(qǐng)描述入隊(duì)與出隊(duì)的過程。所以，用兩個(gè)棧 A和答：棧的特點(diǎn)是后進(jìn)先出，隊(duì)列的特點(diǎn)是先進(jìn)先出。 B 模擬一個(gè)隊(duì)列時(shí)， A 作輸入棧，逐個(gè)元素壓棧，以此模擬隊(duì)列元素的入隊(duì)。當(dāng)需要出隊(duì)時(shí)，將棧A 退棧并逐個(gè)壓入棧B 中， A 中最先入棧的元素，在B 中處于棧頂。 B 退棧，相當(dāng)于隊(duì)列的出隊(duì)，實(shí)現(xiàn)了先進(jìn)先出。顯然，只有棧B 為空且 A 也為空，才算是隊(duì)列空。算法：Element

23、Type DeQueue(A)if(Empty(A)printf(Error!);exit(0);elsereturn Pop(A);void EnQueue(A,ElementType x)ElementType t;while(!Empty(A)t=Pop(A);Push(B,t);Push(A,x);while(!Empty(B)t=Pop(B);Push(A,t);2、已知長(zhǎng)度為n 的線性表 A 采用順序存儲(chǔ)結(jié)構(gòu)，設(shè)計(jì)一個(gè)算法刪除線性表A 中所有值為key 的數(shù)據(jù)元素。答：在順序存儲(chǔ)的線性表上刪除元素通常要涉及到一系列元素的移動(dòng)(刪第 i個(gè)元素第i+1 至第n 個(gè)元素要依次前移)本題要

24、求刪除線性表中所有值為 key的數(shù)據(jù)元素并未要求元素間的相對(duì)位置不變, 因此可以考慮設(shè)頭尾兩個(gè)指針(i=1,j=n )從兩端向中間移動(dòng),凡遇到值 item 的數(shù)據(jù)元素時(shí),直接將右端元素左移至值為 key 的數(shù)據(jù)元素位置。具體實(shí)現(xiàn)如下：void Delete ( ElemType A int n )/A是有n個(gè)元素的一維數(shù)組 本算法刪除A中所有值為item的元素i=1; j=n ; /設(shè)置數(shù)組低、高端指針(下標(biāo))while ( i<j )while ( i<j && Ai!=key )i+;/若值不為key左移指針if ( i<j ) while ( i<j && Aj=key )j- ; /若右端元素值為