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

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

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

4、ile(p.next!=NULL|q.next!=NULL)if(p.next.datafront=0;q-count=0; int EnQu(QuType *&q,ElemType 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,ElemTyp

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

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

7、r 。 循環(huán)隊(duì)列滿：(rear+1)%MAX=front。7 (隊(duì)首指針front ，一個隊(duì)尾指針rear)85設(shè)Q0,6是一個靜態(tài)順序隊(duì)列，初始狀態(tài)為front=rear=0，請畫出做完下列操作后隊(duì)列的頭尾指針的狀態(tài)變化情況，若不能入對，請指出其元素，并說明理由。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ì)列假溢出問題無法入隊(duì)6假設(shè)Q0,5是一個循環(huán)隊(duì)列，初始狀態(tài)為front=rear=0，請畫出做完下列操作后隊(duì)列的頭尾指針的狀態(tài)變化情況，若不能入對，請指出其元素，并說明理由。

8、d, e, b, g, h入隊(duì)d, e出隊(duì)i , j , k , l , m入隊(duì)b出隊(duì)n, o, p, q, r入隊(duì)假設(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) ，用樹型表示法表示該樹，并回答下列問題： 哪個是根結(jié)點(diǎn)? 哪些是葉子結(jié)點(diǎn)? 哪個是g的雙親? 哪些是g的祖先? 哪些是g的孩子? 那些是e的子孫? 哪些是e的兄弟? 哪些是f的兄弟? b和n的層次各是多少? 樹的深度是多少? 以結(jié)點(diǎn)c為根的子樹的深度是多少?根節(jié)

9、點(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 樹的深度：4 以結(jié)點(diǎn)c為根的子樹的深度：3一棵深度為h的滿k叉樹有如下性質(zhì)：第h層上的結(jié)點(diǎn)都是葉子結(jié)點(diǎn)，其余各層上每個結(jié)點(diǎn)都有k棵非空子樹。如果按層次順序(同層自左至右)從1開始對全部結(jié)點(diǎn)編號，問：各層的結(jié)點(diǎn)數(shù)是多少?編號為i的結(jié)點(diǎn)的雙親結(jié)點(diǎn)(若存在)的編號是多少?編號為i的結(jié)點(diǎn)的第j個孩子結(jié)點(diǎn)(若存在)的編號是多少?編號為i的結(jié)點(diǎn)的有右兄弟的條件是什么? 其右兄弟的編號是多少? (1) 設(shè)層號為i的結(jié)點(diǎn)數(shù)目為m=k(i-1

10、) (2) 編號為i的結(jié)點(diǎn)的雙親結(jié)點(diǎn)的編號是：(i+k-2)/k(不大于(i+k-2)/k的最大整數(shù)。也就是(i+k-2)與k整除的結(jié)果.以下/表示整除。 (3) 編號為i的結(jié)點(diǎn)的第j個孩子結(jié)點(diǎn)編號是：k*(i-1)+1+j; (4)編號為i的結(jié)點(diǎn)有右兄弟的條件是(i-1)能被k整除 右兄弟的編號是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-Pri

11、or=S; S-Next=P-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。請畫出該樹，并寫出后序序列。（要求寫出分析過程）確定二叉樹的結(jié)構(gòu)，只需要采用遞歸的方式確定每棵子樹的根結(jié)點(diǎn)和左、右子樹的先序、中序序列即可。先序序列的第一個結(jié)點(diǎn)必然是根結(jié)點(diǎn)，左、右子樹的中序序列在二叉樹的中序序列中，分別在根結(jié)點(diǎn)的兩邊；他們的先序序列在二叉樹的先序序列中先后連續(xù)排列。7、(8分) 假設(shè)用于通訊的電

12、文由A、B、C、D、E、F、G、H這8個字母組成，字母在電文中出現(xiàn)的頻率為 0.07，0.19，0.02，0.06，0.32，0.03，0.21，0.1 ，畫出這8個字母哈夫曼樹并設(shè)計(jì)哈夫曼編碼。然后根據(jù)左0右1寫出a=1010b=00c=10000d=1001e=11f=10001g=01設(shè)有如圖6-27所示的二叉樹。分別用順序存儲方法和鏈接存儲方法畫出該二叉樹的存儲結(jié)構(gòu)。寫出該二叉樹的先序、中序、后序遍歷序列。順序存儲結(jié)構(gòu)：鏈?zhǔn)酱鎯Y(jié)構(gòu)先序：abdehkcfgmn中序：dbhekafcmgn后序：dhkebfmngca已知一棵二叉樹的先序遍歷序列和中序遍歷序列分別為ABDGHCEFI和GD

13、HBAECIF，請畫出這棵二叉樹，然后給出該樹的后序遍歷序列。后序：GHDBEIFCA設(shè)一棵二叉樹的中序遍歷序列和后序遍歷序列分別為BDCEAFHG和DECBHGFA ，請畫出這棵二叉樹，然后給出該樹的先序序列。先序遍歷：ABCDEFGH已知一棵二叉樹的中序遍歷序列和后序遍歷序列分別為dgbaekchif和gdbkeihfca，請畫出這棵二叉樹對應(yīng)的中序線索樹和后序線索樹。二叉樹：中序線索樹：NULLNULL后序線索樹：NULL以二叉鏈表為存儲結(jié)構(gòu)，請分別寫出求二叉樹的結(jié)點(diǎn)總數(shù)及葉子結(jié)點(diǎn)總數(shù)的算法。葉子節(jié)點(diǎn)數(shù)：#define MAX_NODE 50int search_leaves( BTNo

14、de *T) BTNode *StackMAX_NODE ,*p=T;int top=0, num=0;if (T!=NULL) stack+top=p ; while (top0) 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所示的二叉樹是森林F所對應(yīng)的二叉樹，請畫出森林F。森林F：設(shè)有一棵樹，如圖6-28所示。請分別用雙親表示法

15、、孩子表示法、孩子兄弟表示法給出該樹的存儲結(jié)構(gòu)。請給出該樹的先序遍歷序列和后序遍歷序列。請將這棵樹轉(zhuǎn)換成二叉樹。雙親表示法： 孩子表示法：孩子兄弟表示法：先序：abdechkgmfn 后序： edgkhnfmcba二叉樹： 設(shè)給定權(quán)值集合w=3,5,7,8,11,12 ，請構(gòu)造關(guān)于w的一棵huffman樹，并求其加權(quán)路徑長度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個字符在電文中出現(xiàn)的概率分別為0.07, 0.19, 0.02, 0.06, 0.32, 0.03, 0.2

16、1, 0.10 。請畫出對應(yīng)的huffman樹(按左子樹根結(jié)點(diǎn)的權(quán)小于等于右子樹根結(jié)點(diǎn)的權(quán)的次序構(gòu)造)。求出每個字符的huffman編碼。01100101011100 然后根據(jù)左0右1寫出a=1010b=00c=10000d=1001e=11f=10001g=01h=10113、求兩個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;in;i+)for (j=0;jn;j+) Cij=Ai

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

18、ntf(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、已知長度為n的線性表A采用順序存儲結(jié)構(gòu)，設(shè)計(jì)一個算法刪除線性表A中所有值為key的數(shù)據(jù)元素。答：在順序存儲的線性表上刪除元素通常要涉及到一系列元素的移動（刪第i個元素第i+1至第n個元素要依次前移）本題要求刪除線性表中所有值為key的數(shù)據(jù)元素并未要求元素間的相對位置不變,因此可以考慮設(shè)頭尾兩個指針（i=1,j=n）從兩端向中間移動,凡遇到值item的數(shù)據(jù)元素時(shí),直接將右端元素左移至值為 key 的數(shù)據(jù)元素位置。具體實(shí)現(xiàn)如下：void Delete（ElemType A int n）A是有n個元素的一維數(shù)組 本算法刪除A中所有值為item的元素 i=1；j=n；設(shè)置數(shù)組低、高端指針（下標(biāo)） while（ij） while（ij & Ai!=key） i+； 若值不為key 左移指針 if（ij）while（ij & Aj=key） j-；若右端元素值為key指針左移 if（ij） Ai+=Aj-； 3、假設(shè)程序代碼中