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

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

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

3、?不需要經(jīng)常大量的修改表或需要隨機(jī)存取的情況下可以選用順序表；相反需要經(jīng)常大量的修改表，但不是頻繁的隨機(jī)存取的情況下可選用鏈?zhǔn)奖怼?鏈表所表示的元素是否有序?如有序，則有序性體現(xiàn)于何處?鏈表所表示的元素是否一定要在物理上是相鄰的?有序表的有序性又如何理解?答：有序。有序性體現(xiàn)在通過(guò)指針數(shù)據(jù)元素有序的相連。物理上不一定要相鄰。4設(shè)A和B是兩個(gè)按元素值遞增有序的單鏈表，寫(xiě)一算法將A和B歸并為按按元素值遞減有序的單鏈表C，試分析算法的時(shí)間復(fù)雜度。void ListInsert(SqList A,SqList B,SqList C)ElemType *p,*q,*s;P=&A;q=&B

4、;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.next;4、例：什么是隊(duì)列的上溢現(xiàn)象和假溢出現(xiàn)象？解決它們有哪些方法？答：在隊(duì)

5、列的順序存儲(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ì)造成空間的使用效率降低。(2)當(dāng)出現(xiàn)假溢出時(shí)可采用以下幾種方法: 采用平移元素的方法:每當(dāng)隊(duì)列中加入一個(gè)元素時(shí),隊(duì)列中已有的元素向隊(duì)頭移動(dòng)一個(gè)位置(當(dāng)然要有空閑的空間可供移動(dòng))；每當(dāng)刪除一個(gè)隊(duì)頭元

6、素時(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)先出”的原則?！?、例：對(duì)于順序隊(duì)列來(lái)說(shuō),如果知道隊(duì)首元素的位置和隊(duì)列中元素個(gè)數(shù),則隊(duì)尾元素所在位置顯然是可以計(jì)算的。也就是說(shuō),可以用隊(duì)列中元素個(gè)數(shù)代替隊(duì)尾指針。編寫(xiě)出這種循環(huán)順序隊(duì)列的初始化、入隊(duì)、出隊(duì)和判空算法。 解: 當(dāng)已知隊(duì)首元素的位置front和隊(duì)列中元素個(gè)數(shù)count后:隊(duì)空的條件為:count=0隊(duì)滿(mǎn)的條件為:count=MaxSize計(jì)算隊(duì)尾位置rear: rear=(front+count)%MaxSize

7、 對(duì)應(yīng)的算法如下: typedef struct ElemType dataMaxSize;int front;/*隊(duì)首指針*/int count;/*隊(duì)列中元素個(gè)數(shù)*/ QuType;/*隊(duì)列類(lèi)型*/ void InitQu(QuType *&q) /*隊(duì)列q初始化*/ q=(QuType *)malloc(sizeof(QuType);q->front=0;q->count=0; int EnQu(QuType *&q,ElemType x)/*進(jìn)隊(duì)*/ int rear;if (q->count=MaxSize) return 0; /*隊(duì)滿(mǎn)上溢出*/e

8、lse 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;else q->front=(q->front+1)%MaxSize; x=q->dataq->front; q->count-

9、; return 1;int QuEmpty(QuType *q)/*判空*/ return(q->count=0);1 設(shè)有一個(gè)棧，元素進(jìn)棧的次序?yàn)閍, b, c。問(wèn)經(jīng)過(guò)棧操作后可以得到哪些輸出序列？cba； abc； acb；bac； bca；2循環(huán)隊(duì)列的優(yōu)點(diǎn)是什么?如何判斷它的空和滿(mǎn)?優(yōu)點(diǎn)：可以克服順序隊(duì)列的“假上溢”現(xiàn)象，能夠使存儲(chǔ)隊(duì)列的向量空間得到充分利用。判斷循環(huán)隊(duì)列的空或滿(mǎn)不能以頭尾指針是否相等來(lái)確定，一般是通過(guò)以下幾種方法：一是另設(shè)一布爾變量來(lái)區(qū)別隊(duì)列的空和滿(mǎn)。二是約定入隊(duì)前，測(cè)試尾指針在循環(huán)意義下加1后是否等于頭指針，若相等則認(rèn)為隊(duì)滿(mǎn)。三是設(shè)置一計(jì)數(shù)器記錄隊(duì)列中元素的總

10、數(shù)，不僅可判別空或滿(mǎn)，還可以得到隊(duì)列中元素的個(gè)數(shù)2 設(shè)有一個(gè)靜態(tài)順序隊(duì)列，向量大小為MAX，判斷隊(duì)列為空的條件是什么？隊(duì)列滿(mǎn)的條件是什么？3 隊(duì)列為空：front=rear。隊(duì)滿(mǎn)：rear=MAX -1或front=rear4 (隊(duì)首指針front ，一個(gè)隊(duì)尾指針rear)55 設(shè)有一個(gè)靜態(tài)循環(huán)隊(duì)列，向量大小為MAX，判斷隊(duì)列為空的條件是什么？隊(duì)列滿(mǎn)的條件是什么？6 循環(huán)隊(duì)列為空：front=rear 。 循環(huán)隊(duì)列滿(mǎn)：(rear+1)%MAX=front。7 (隊(duì)首指針front ，一個(gè)隊(duì)尾指針rear)85設(shè)Q0,6是一個(gè)靜態(tài)順序隊(duì)列，初始狀態(tài)為front=rear=0，請(qǐng)畫(huà)出做完下列操作后

11、隊(duì)列的頭尾指針的狀態(tài)變化情況，若不能入對(duì)，請(qǐng)指出其元素，并說(shuō)明理由。a, b, c, d入隊(duì)a, b, c出隊(duì)i , j , k , l , m入隊(duì)d, i出隊(duì)n, o, p, q, r入隊(duì)其中l(wèi),m,n,o,p,q,r均由于隊(duì)列假溢出問(wèn)題無(wú)法入隊(duì)6假設(shè)Q0,5是一個(gè)循環(huán)隊(duì)列，初始狀態(tài)為front=rear=0，請(qǐng)畫(huà)出做完下列操作后隊(duì)列的頭尾指針的狀態(tài)變化情況，若不能入對(duì)，請(qǐng)指出其元素，并說(shuō)明理由。d, e, b, g, h入隊(duì)d, e出隊(duì)i , j , k , l , m入隊(duì)b出隊(duì)n, o, p, q, r入隊(duì)假設(shè)在樹(shù)中，結(jié)點(diǎn)x是結(jié)點(diǎn)y的雙親時(shí)，用(x,y)來(lái)表示樹(shù)邊。已知一棵樹(shù)的樹(shù)邊集合為

12、 (e,i), (b,e), (b,d), (a,b), (g,j), (c,g), (c,f), (h,l), (c,h), (a,c) ，用樹(shù)型表示法表示該樹(shù)，并回答下列問(wèn)題： 哪個(gè)是根結(jié)點(diǎn)? 哪些是葉子結(jié)點(diǎn)? 哪個(gè)是g的雙親? 哪些是g的祖先? 哪些是g的孩子? 那些是e的子孫? 哪些是e的兄弟? 哪些是f的兄弟? b和n的層次各是多少? 樹(shù)的深度是多少? 以結(jié)點(diǎn)c為根的子樹(shù)的深度是多少?根節(jié)點(diǎn)：a 葉子節(jié)點(diǎn)：i ,d , j, f , l g 的雙親節(jié)點(diǎn):c g 的祖先：c , a g 的孩子：j e 的子孫：ie的兄弟：d f的兄弟：g , hb的層次：2 樹(shù)的深度：4 以結(jié)點(diǎn)c為根

13、的子樹(shù)的深度：3一棵深度為h的滿(mǎn)k叉樹(shù)有如下性質(zhì)：第h層上的結(jié)點(diǎn)都是葉子結(jié)點(diǎn)，其余各層上每個(gè)結(jié)點(diǎn)都有k棵非空子樹(shù)。如果按層次順序(同層自左至右)從1開(kāi)始對(duì)全部結(jié)點(diǎn)編號(hào)，問(wèn)：各層的結(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)是多少? (1) 設(shè)層號(hào)為i的結(jié)點(diǎn)數(shù)目為m=k(i-1) (2) 編號(hào)為i的結(jié)點(diǎn)的雙親結(jié)點(diǎn)的編號(hào)是：(i+k-2)/k(不大于(i+k-2)/k的最大整數(shù)。也就是(i+k-2)與k整除的結(jié)果.以下/表示整除。 (3) 編號(hào)為i的結(jié)點(diǎn)的第j個(gè)孩子結(jié)點(diǎn)編號(hào)

14、是：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)，畫(huà)圖并寫(xiě)出下列操作的語(yǔ)句序列。（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->Next; P->Next=S; S->Prior=P;(2) Q=P->Next; P->Next=P->

15、;Next->Next; P->Next->Prior=P; free(Q);4、假設(shè)一棵二叉樹(shù)的前序序列為EBADCFHGIKJ，中序序列為ABCDEFGHIJK。請(qǐng)畫(huà)出該樹(shù)，并寫(xiě)出后序序列。（要求寫(xiě)出分析過(guò)程）確定二叉樹(shù)的結(jié)構(gòu)，只需要采用遞歸的方式確定每棵子樹(shù)的根結(jié)點(diǎn)和左、右子樹(shù)的先序、中序序列即可。先序序列的第一個(gè)結(jié)點(diǎn)必然是根結(jié)點(diǎn)，左、右子樹(shù)的中序序列在二叉樹(shù)的中序序列中，分別在根結(jié)點(diǎn)的兩邊；他們的先序序列在二叉樹(shù)的先序序列中先后連續(xù)排列。7、(8分) 假設(shè)用于通訊的電文由A、B、C、D、E、F、G、H這8個(gè)字母組成，字母在電文中出現(xiàn)的頻率為 0.07，0.19，0.0

16、2，0.06，0.32，0.03，0.21，0.1 ，畫(huà)出這8個(gè)字母哈夫曼樹(shù)并設(shè)計(jì)哈夫曼編碼。然后根據(jù)左0右1寫(xiě)出a=1010b=00c=10000d=1001e=11f=10001g=01設(shè)有如圖6-27所示的二叉樹(shù)。分別用順序存儲(chǔ)方法和鏈接存儲(chǔ)方法畫(huà)出該二叉樹(shù)的存儲(chǔ)結(jié)構(gòu)。寫(xiě)出該二叉樹(shù)的先序、中序、后序遍歷序列。順序存儲(chǔ)結(jié)構(gòu)：鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)先序：abdehkcfgmn中序：dbhekafcmgn后序：dhkebfmngca已知一棵二叉樹(shù)的先序遍歷序列和中序遍歷序列分別為ABDGHCEFI和GDHBAECIF，請(qǐng)畫(huà)出這棵二叉樹(shù)，然后給出該樹(shù)的后序遍歷序列。后序：GHDBEIFCA設(shè)一棵二叉樹(shù)的中

17、序遍歷序列和后序遍歷序列分別為BDCEAFHG和DECBHGFA ，請(qǐng)畫(huà)出這棵二叉樹(shù)，然后給出該樹(shù)的先序序列。先序遍歷：ABCDEFGH已知一棵二叉樹(shù)的中序遍歷序列和后序遍歷序列分別為dgbaekchif和gdbkeihfca，請(qǐng)畫(huà)出這棵二叉樹(shù)對(duì)應(yīng)的中序線(xiàn)索樹(shù)和后序線(xiàn)索樹(shù)。二叉樹(shù)：中序線(xiàn)索樹(shù)：NULLNULL后序線(xiàn)索樹(shù)：NULL以二叉鏈表為存儲(chǔ)結(jié)構(gòu)，請(qǐng)分別寫(xiě)出求二叉樹(shù)的結(jié)點(diǎn)總數(shù)及葉子結(jié)點(diǎn)總數(shù)的算法。葉子節(jié)點(diǎn)數(shù)：#define MAX_NODE 50int search_leaves( BTNode *T) BTNode *StackMAX_NODE ,*p=T;int top=0, num=0

18、;if (T!=NULL) stack+top=p ; while (top>0) p=stacktop- ; if (p->Lchild=NULL&&p->Rchild=NULL) num+ ; if (p->Rchild!=NULL ) stack+top=p->Rchild; if (p->Lchild!=NULL ) stack+top=p->Lchild; return(num) ;設(shè)圖6-27所示的二叉樹(shù)是森林F所對(duì)應(yīng)的二叉樹(shù)，請(qǐng)畫(huà)出森林F。森林F：設(shè)有一棵樹(shù)，如圖6-28所示。請(qǐng)分別用雙親表示法、孩子表示法、孩子兄弟表示法

19、給出該樹(shù)的存儲(chǔ)結(jié)構(gòu)。請(qǐng)給出該樹(shù)的先序遍歷序列和后序遍歷序列。請(qǐng)將這棵樹(shù)轉(zhuǎn)換成二叉樹(shù)。雙親表示法： 孩子表示法：孩子兄弟表示法：先序：abdechkgmfn 后序： edgkhnfmcba二叉樹(shù)： 設(shè)給定權(quán)值集合w=3,5,7,8,11,12 ，請(qǐng)構(gòu)造關(guān)于w的一棵huffman樹(shù)，并求其加權(quán)路徑長(zhǎng)度WPL 。WPL=12*2+3*4+5*4+7*3+8*2+11*2=115假設(shè)用于通信的電文是由字符集a, b, c, d, e, f, g, h中的字符構(gòu)成，這8個(gè)字符在電文中出現(xiàn)的概率分別為0.07, 0.19, 0.02, 0.06, 0.32, 0.03, 0.21, 0.10 。請(qǐng)畫(huà)出對(duì)應(yīng)

20、的huffman樹(shù)(按左子樹(shù)根結(jié)點(diǎn)的權(quán)小于等于右子樹(shù)根結(jié)點(diǎn)的權(quán)的次序構(gòu)造)。求出每個(gè)字符的huffman編碼。01100101011100 然后根據(jù)左0右1寫(xiě)出a=1010b=00c=10000d=1001e=11f=10001g=01h=10113、求兩個(gè)n階方陣相加C=A+B的算法如下,分析其時(shí)間復(fù)雜度。 #define MAX 20 /*定義最大的方階*/ void MatrixAdd(int n,int AMAXMAX,int BMAXMAX,int CMAXMAX) int i,j;for (i=0;i<n;i+)for (j=0;j<n;j+) Cij=Aij+Bij;

21、 答：因?yàn)?Cij=Aij+Bij;這條語(yǔ)句執(zhí)行的頻率為n2;所以其時(shí)間復(fù)雜度為0(n2)。四、算法設(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ì)的過(guò)程。答：棧的特點(diǎn)是后進(jìn)先出，隊(duì)列的特點(diǎn)是先進(jìn)先出。所以，用兩個(gè)棧A和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ì)列空。算法：ElementType DeQueue(A)if(Empty(A)printf(&q

22、uot;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的線(xiàn)性表A采用順序存儲(chǔ)結(jié)構(gòu)，設(shè)計(jì)一個(gè)算法刪除線(xiàn)性表A中所有值為key的數(shù)據(jù)元素。答：在順序存儲(chǔ)的線(xiàn)性表上刪除元素通常要涉及到一系列元素的移動(dòng)（刪第i個(gè)元素第i+1至第n個(gè)元素要依次前移）本題要求刪除線(xiàn)性表中所有值為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 &a