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

1、頁(yè)眉內(nèi)容姓名班級(jí)對(duì)應(yīng)模式串的123456789100112112343ADABBADADAnext j 演示程序亦驗(yàn)證了結(jié)果:nextj=034.已知一棵二叉樹(shù)的前序序列和中序序列分別為：ABDEGCFH 和DBGEACHF ,則該二叉樹(shù)的后序序列是什么？答：法1:先畫(huà)樹(shù)而得后序序列;A（DBGE）（CHF）BCD （GE）（HF）EFGH結(jié)論：DGEBHFCA法2:直接推出后序序列step1:(DBGE) (CHF) Astep2:D(GE) B(HF) CAstep3:DGE B HF CA5.請(qǐng)證明：用二叉鏈表法（Lchild-Rchild ）存儲(chǔ)包含 n個(gè)結(jié)點(diǎn)的二叉樹(shù)，必有n+1個(gè)指針

2、域?yàn)榭?。?shù)據(jù)結(jié)構(gòu)試題參考答案（開(kāi)卷）（電信系本科2001級(jí)2002年12月）一、回答下列問(wèn)題（每題4分，共36分）1 .某完全二叉樹(shù)共有15381個(gè)結(jié)點(diǎn)，請(qǐng)問(wèn)其樹(shù)葉有多少個(gè)？答：n2=n/2=15381/2=7691（個(gè)）2 .假設(shè)有二維數(shù)組A7X9,每個(gè)元素用相鄰的6個(gè)字節(jié)存儲(chǔ)，存儲(chǔ)器按字節(jié)編址。已知A的起始存儲(chǔ)位置（基地址）為1000,末尾元素A68的第一個(gè)字節(jié)地址為多少？若按列存儲(chǔ)時(shí)，元素A47的第一個(gè)字節(jié)地址為多少？答：末尾元素A68的第一個(gè)字節(jié)地址=1000+（7行X9列一1）X6B=1000+62X6=1372按列存儲(chǔ)時(shí)，元素A47的第一個(gè)字節(jié)地址=1000+（7列X7行+4）X6

3、B=1000+53X6=13183 .在KMP算法中，已知模式串為ADABBADADA,請(qǐng)寫(xiě)出模式串的nextj函數(shù)值。答：根據(jù)0當(dāng)j=1時(shí)nextj=maxk1<k<j且'I-Tk-1'=卜（心）tj-1'1其他情況1答：因?yàn)椋河枚骀湵泶鎯?chǔ)包含n個(gè)結(jié)點(diǎn)的二叉樹(shù)，結(jié)點(diǎn)共有2n個(gè)鏈域;頁(yè)眉內(nèi)容又因?yàn)椋憾鏄?shù)中除根結(jié)點(diǎn)外，每一個(gè)結(jié)點(diǎn)有且僅有一個(gè)雙親，這就意味著只有n-1個(gè)結(jié)點(diǎn)的鏈域存放指向非空子女結(jié)點(diǎn)的指針(換句話(huà)說(shuō)，有后繼孩子鏈接的指針僅n-1個(gè))；所以，空指針數(shù)目=全部指針數(shù)2n所有非空指針數(shù)(n-1)=所有空指針數(shù)=n+1,證畢。6 .設(shè)二叉排序樹(shù)中關(guān)鍵

4、字互不相同，則其中最小元素必?zé)o左孩子，最大元素必?zé)o右孩子。此命題是否正確？最大元素和最小元素一定是葉子嗎？一個(gè)新的結(jié)點(diǎn)總是插在二叉排序樹(shù)的某葉子上嗎？請(qǐng)解釋理由。答：設(shè)二叉排序樹(shù)中關(guān)鍵字互不相同，則其中最小元必?zé)o左孩子，最大元必?zé)o右孩子。此命題正確。解釋?zhuān)杭僭O(shè)最小元為min,若最小元min有左孩子min',根據(jù)二叉排序樹(shù)的定義應(yīng)該有：min'<min,與min是最小元矛盾，由此可反證出最小元必?zé)o左孩子；同理可反證出最大元必?zé)o右孩子。最大元和最小元不一定是葉子；解釋?zhuān)弘m然最小元必?zé)o左孩子，最大元必?zé)o右孩子，但最小元可有右孩子，最大元可有左孩子。如下圖A和B所示。所以最大元和

5、最小元不一定是葉子。一個(gè)新的結(jié)點(diǎn)不一定總是插在二叉排序樹(shù)的某葉子上。解釋?zhuān)豪缑P(guān)鍵字A,B,C，以B、A、C的次序插入一空的二叉排序樹(shù)中，過(guò)程如下圖C所示。當(dāng)再插入C時(shí)，C作為B的右孩子，插入后如圖D所示，彳1此時(shí)B已有左孩子A,元矛盾，由此可反證出最小元必?zé)o左孩子；同理可反證出最大元必?zé)o右孩子。7 .假設(shè)一有序表中有23個(gè)元素，現(xiàn)進(jìn)行折半查找，則平均查找長(zhǎng)度是多少？答：顯然，平均查找長(zhǎng)度=O(log2n)<5次(25)。但具體是多少次，則不能按照公式ASL工10g2(n1)1來(lái)計(jì)算(即24/23(log224)-1骰785次并不正確！)。n因?yàn)檫@是在假設(shè)n=2m-1的情況下推導(dǎo)出來(lái)

6、的公式。應(yīng)當(dāng)用窮舉法羅列：全部元素的查找次數(shù)為=(1+2X2+4>3+8>4+8X5)=89;ASL=89/23=3.878 .已知輸入序列的入棧次序?yàn)閄、Y、Z,請(qǐng)列出出棧的所有可能序列。答：共5種可能的序列。(1) X、Y、Z全入Z、Y、X出棧(2) X、Y先入棧Y、X、Z出棧Y、Z、X出棧X先入棧X、Y、Z出棧X、Z、Y出棧9.若初始記錄基本有序，則選用哪些排序方法比較適合？若初始記錄基本無(wú)序，則最好選用哪些排序方法？請(qǐng)解釋理由（排序方法各列舉兩種即可）答：基本有序時(shí)可選用直接插入、簡(jiǎn)單選擇、堆排序、錦標(biāo)賽排序、冒泡排序、歸并排序、（希爾排序）等方法，其中插入排序和冒泡應(yīng)該是

7、最快的。因?yàn)橹挥斜容^動(dòng)作，無(wú)需移動(dòng)元素。此時(shí)平均時(shí)間復(fù)雜度為O（n）；無(wú)序的情況下最好選用快速排序、希爾排序、簡(jiǎn)單選擇排序等，這些算法的共同特點(diǎn)是，通過(guò)“振蕩”讓數(shù)值相差不大但位置差異很大的元素盡快到位。二、綜合題（每題7分，共28分）1.設(shè)某一通信系統(tǒng)由09十種字符組成，其出現(xiàn)的概率為：=0.20,0.11,0.06,0.03,0.12,0.06,0.19,0.01,0.13,0.09,現(xiàn)用Huffman方法進(jìn)行編碼，請(qǐng)畫(huà)出對(duì)應(yīng)的Huffman樹(shù)，并計(jì)算平均碼長(zhǎng)WPL答：可以先擴(kuò)大100倍，以方便構(gòu)造哈夫曼樹(shù)。也可以直接構(gòu)造。=0.20,0.11,0.06,0.03,0.12,0.06,0.

8、19平均碼長(zhǎng)是WPL(而不是ASL)WPL=5(0.03+0.01)十+4(0.06+0.06+0.09)十+3(0.11+0.12+0.13+0.19)+2(0.20)=0.2+0.84+1.65+0.4=3.092.欲將無(wú)序序列（23,78,12,35,69,95,11,09,35*,48,99,26）中的關(guān)鍵碼按升序重新排列，請(qǐng)寫(xiě)出快速排序第一趟排序的結(jié)果序列。另外請(qǐng)畫(huà)出堆排序（小根堆）的初始堆。答：快速排序第一趟排序的結(jié)果序列為:09,11,12,23,69,95,35,78,35*,48,99,26（注意要按振蕩式逼近算法實(shí)現(xiàn)）堆排序的初始堆如下，注意要從排無(wú)序堆開(kāi)始，從最后一個(gè)非終

9、端結(jié)點(diǎn)開(kāi)始，自下而上調(diào)整，而且要排成小根堆！初始堆序列為：09,23,11,78,48,26,12,35,35*,69,99,953. 已知一組關(guān)鍵字為(10,24,32,17,31,30,46,47,40,63,49),設(shè)哈希函數(shù)H(key)=keyMOD7。請(qǐng)給出以下解答：(1) 畫(huà)出用鏈地址法處理沖突構(gòu)造所得的哈希表；(2) 若查找關(guān)鍵字17,需要依次與哪些關(guān)鍵字進(jìn)行比較？(3) 若查找關(guān)鍵字60,需要依次與哪些關(guān)鍵字比較？(4) 假定每個(gè)關(guān)鍵字的查找概率相等，求查找成功時(shí)的平均查找長(zhǎng)度。解:(1)哈希表如下:636450123301032472446A40A1731(2)若查找關(guān)鍵字3

10、1,需要依次與哪些關(guān)鍵字進(jìn)行比較?10、24、17 和 31(3)若查找關(guān)鍵字60,需要依次與哪些關(guān)鍵字比較?先查4單元，與32、46比較，再查指針為空則返回。(4)假定每個(gè)關(guān)鍵字的查找概率相等，求查找成功時(shí)的平均查找長(zhǎng)度。11個(gè)元素中，有5個(gè)需比較1次，有4個(gè)需比較2次，有1個(gè)需比較3次，有1個(gè)需要比較4次，所以:ASL=(5X1+4X2+1X3+1X4)/11=20/11引1.824.某無(wú)向圖G的鄰接表如下圖所示。要求：請(qǐng)畫(huà)出該圖G的邏輯結(jié)構(gòu)圖；(設(shè)訪問(wèn)起點(diǎn)為V3)；根據(jù)鄰接表寫(xiě)出其深度優(yōu)先遍歷序列和廣度優(yōu)先遍歷序列根據(jù)遍歷結(jié)果，畫(huà)出圖G的深度優(yōu)先和廣度優(yōu)先生成樹(shù)。V0V1V2V3V4V5

11、V6V7012345641 272.665>230304450解：該無(wú)向圖G的邏輯結(jié)構(gòu)圖如右圖所示:根據(jù)鄰接表寫(xiě)出其深度優(yōu)先遍歷序列和廣度優(yōu)先遍歷序列(設(shè)訪問(wèn)起點(diǎn)為V3)；深度優(yōu)先遍歷序列=3-2-7-1-0-4-6-5廣度優(yōu)先遍歷序列=3-2-0-7-1-4-6-5根據(jù)遍歷結(jié)果，畫(huà)出圖G的深度優(yōu)先和廣度優(yōu)先生成樹(shù)如下(注意到訪問(wèn)起點(diǎn)為V3)o頁(yè)眉內(nèi)容V3/Xv2vo/v7V1v4三、算法設(shè)計(jì)題(4小題，共36分)1 .試用C或類(lèi)C語(yǔ)言編寫(xiě)一個(gè)算法，將一循環(huán)單鏈表就地逆置。(9分)解：要想讓an指向an-1,a2指向al,至少有兩種算法：法1:用插入法，掃描alan,將每個(gè)ai插入到鏈表

12、首部即可(實(shí)際上是鏈棧的概念);法2：用替換法：掃描alan,將每個(gè)ai1的指針域送入ai+1的指針域。法1的核心部分為:q=head; p=head->next; while(p!=q) r=p->next;p->next=head;head=p;p=r; q->next=head;法2的核心部分為:q=head;p=head->next;while(p!=head)r=p->next;p->next=q;q=p;p=r;p->next=q;head=q;2 .定義二叉樹(shù)的寬度為二叉樹(shù)一層中結(jié)點(diǎn)個(gè)數(shù)的最大值，試編寫(xiě)一算法求二叉樹(shù)的寬度。(9分)

13、解：要用層次遍歷以及隊(duì)列來(lái)處理，并一定要設(shè)立一個(gè)寬度計(jì)數(shù)器和一個(gè)temp,在統(tǒng)計(jì)完每一層的結(jié)點(diǎn)個(gè)數(shù)之后就要與計(jì)數(shù)器中前一層的值比較，保留大值。可參見(jiàn)嚴(yán)題集【6.52】。參考程序如下：typedefstructBTNodenode;intlayer;intlayer;BTNRecord;/包含結(jié)點(diǎn)所在層次的記錄類(lèi)型intFanMao(BitreeT)求一棵二叉樹(shù)的"繁茂度"intcountd;/count數(shù)組存放每一層的結(jié)點(diǎn)數(shù)InitQueue(Q);Q的元素為BTNRecord類(lèi)型EnQueue(Q,T,0);while(!QueueEmpty(Q)DeQueue(Q,r)

14、;countr.layer+;if(r.node->lchild)EnQueue(Q,r.node->lchild,r.layer+1);5法1的核心部分為：for(i=1; i<=10; i+ )tag=1;while( tag= =1)tag=0;for(j=1; j<=10000-1; j+)if(aj<aj+1) tag=1;temp=aj;aj=aj+1;aj+1=temp; return(OK); /STOP最好情況：天然遞減序列，n-1次即可;最壞情況：無(wú)序，做滿(mǎn) 10次，共比較：(n-1)+(n-2)+(n-10) =10n-55 次一般情況下要詳

15、細(xì)推導(dǎo)計(jì)算： 共x種初始情況，每種情況花費(fèi)時(shí)間？ 然后才能取平均。頁(yè)眉內(nèi)容if(r.node->rchild)EnQueue(Q,r.node->rchild,r.layer+1);/利用層序遍歷來(lái)統(tǒng)計(jì)各層的結(jié)點(diǎn)數(shù)h=r.layer;最后一個(gè)隊(duì)列元素所在層就是樹(shù)的高度f(wàn)or(maxn=count0,i=1;hcounti;i+)if(counti>maxn)maxn=counti;/求層最大結(jié)點(diǎn)數(shù)return(h*maxn);/FanMao分析：如果不允許使用輔助數(shù)組，就必須在遍歷的同時(shí)求出層最大結(jié)點(diǎn)數(shù)，形式上會(huì)復(fù)雜一些。3 .試用C或類(lèi)C語(yǔ)言編寫(xiě)一個(gè)算法：(A、B兩題任選其

16、一，9分)A.統(tǒng)計(jì)二叉樹(shù)的總結(jié)點(diǎn)數(shù)和葉子結(jié)點(diǎn)數(shù)。B.對(duì)于一個(gè)有10000個(gè)記錄的線性表，希望用盡可能快的速度挑選出前10個(gè)最小的記錄。解：A容易，將遍歷函數(shù)中Visit()細(xì)化即可，設(shè)立兩個(gè)計(jì)數(shù)器，一個(gè)每次都+,一個(gè)是遇見(jiàn)葉子才+?；蛘?，可參考【嚴(yán)題集6.42】編寫(xiě)遞歸算法(計(jì)算二叉樹(shù)中葉子結(jié)點(diǎn)的數(shù)目)。至于總結(jié)點(diǎn)數(shù)就更容易添加了。思路：用任何一種遍歷遞歸算法，凡是左右指針均空者，則為葉子，將其用sum2計(jì)數(shù)。至于總結(jié)點(diǎn)數(shù)，無(wú)論是否葉子都累計(jì)到sum中即可。法一：核心部分為：初始化：sum=sum2=0;DLR(liuyu*root)中序遍歷的遞歸函數(shù)if(root!=NULL)if(root

17、->lchild=NULL)&&(root->rchild=NULL)sum2+;統(tǒng)計(jì)葉子結(jié)點(diǎn)數(shù)sum+;統(tǒng)計(jì)總結(jié)點(diǎn)數(shù)DLR(root->lchild);DLR(root->rchild);return(0);B稍難，用冒泡排序加標(biāo)志會(huì)在有序的情況下很快；但用錦標(biāo)賽排序會(huì)在一般情況下更有優(yōu)勢(shì)，快得多。冒泡是O(n2),錦標(biāo)賽是O(n+910g2n)解：用冒泡排序的核心算法：法2的設(shè)計(jì)思路為：完全仿照錦標(biāo)賽程序或堆排序求最小值用了n-1次；但求后9個(gè)次小值時(shí)，只需比較log2n次；最好、最壞和平均情況相同：都是(n-1)+9log2n次。頁(yè)眉內(nèi)容4 .編寫(xiě)

18、一個(gè)算法：(A、B兩題任選其一，9分)A. 以二叉鏈表為存儲(chǔ)結(jié)構(gòu)，判斷給定的二叉樹(shù)是否為二叉排序樹(shù)。B. 在已經(jīng)生成的中序線索二叉樹(shù)中，求給定元素p的直接后繼。(劉注：A容易錯(cuò)，即不能只判斷左右孩子的情況，還要判斷左右孩子與雙親甚至根結(jié)點(diǎn)的比值也要遵循(左小右大)原則，課練有提示，網(wǎng)上有程序答案)。A解：注意仔細(xì)研究二叉排序樹(shù)的定義。易犯的典型錯(cuò)誤是按下述思路進(jìn)行判別：“若一棵非空的二叉樹(shù)其左、右子樹(shù)均為二叉排序樹(shù)，且左子樹(shù)的根的值小于根結(jié)點(diǎn)的值，又根結(jié)點(diǎn)的值不大于右子樹(shù)的根的值，則是二叉排序樹(shù)”若要采用遞歸算法，建議您采用如下的函數(shù)首部：boolBisortTree(BiTreeT,BiTr

19、ee&PRE)，其中PRE為指向當(dāng)前訪問(wèn)結(jié)點(diǎn)的前驅(qū)的指針。(或者直接存儲(chǔ)前驅(qū)的數(shù)值，隨時(shí)與當(dāng)前根結(jié)點(diǎn)比較)一個(gè)漂亮的算法設(shè)計(jì)如下：intlast=0,flag=1;/last是全局變量，用來(lái)記錄前驅(qū)結(jié)點(diǎn)值，只要每個(gè)結(jié)點(diǎn)都比前驅(qū)大就行。intIs_BSTree(BitreeT)/判斷二叉樹(shù)T是否二叉排序樹(shù)，是則返回1，否則返回0if(T->lchild&&flag)Is_BSTree(T->lchild);if(T->data<last)flag=0;/與其中序前驅(qū)相比較,flag=0表示當(dāng)前結(jié)點(diǎn)比直接前驅(qū)小，則很快會(huì)返回last=T->data;if(T->rchild&&flag)Is_BSTree(T->rchild);returnflag;/