09數(shù)據(jù)結(jié)構(gòu)期中答案

《數(shù)據(jù)結(jié)構(gòu)》期中試卷（2009級(jí)）2010-2011學(xué)年第一學(xué)期姓名：學(xué)號(hào)：成績(jī)：選擇題：（每小題2分，共20分）1.有六個(gè)元素6，5，4，3，2，1的順序進(jìn)棧，下列哪一個(gè)不是合法的出棧序列？（）A.543612B.453126C.346521D.2341562.在一個(gè)有125個(gè)元素的順序表中插入一個(gè)新元素并保持原來(lái)順序不變，平均要移動(dòng)（）個(gè)元素。A．8B.62.5C.62D.73.已知廣義表A＝((a,b,c),(d,e,f),(h,(i,j)),g)，從A表中取出原子項(xiàng)e的運(yùn)算是：()A.head(tail(A))B.head(tail(tail(A)))C.head(head(tail(tail(A))))D.head(tail(head(tail(A))))4.循環(huán)隊(duì)列存儲(chǔ)在數(shù)組A[0..m]中，設(shè)front和rear分別為隊(duì)列的頭指針和尾指針，則入隊(duì)時(shí)的操作為（）。A.front=(front+1)mod(m+1)B.rear=(rear+1)mod(m+1)C.front=(front+1)modmD.rear=(rear+1)modm5.在雙向循環(huán)鏈表中,在p指針?biāo)赶虻慕Y(jié)點(diǎn)前插入一個(gè)指針q所指向的新結(jié)點(diǎn),其修改指針的操作是()(假設(shè)雙向循環(huán)鏈表的結(jié)點(diǎn)結(jié)構(gòu)為(llink,data,rlink)。A．p->llink=q；q->rlink=p；p->llink->rlink=q；q->llink=q；B．p->llink=q；p->llink->rlink=q；q->rlink=p；q->llink=p->llink；C．q->rlink=p；q->llink=p->llink；p->llink->rlink=q;p->llink=q;D．q->llink=p->llink；q->rlink=p；p->llink=q；p->llink=q；6.一棵完全二叉樹上有1001個(gè)結(jié)點(diǎn)，其中葉子結(jié)點(diǎn)的個(gè)數(shù)是（）。A．250B．500C．254D．以上答案都不對(duì)7.已知一棵二叉樹的前序遍歷結(jié)果為ABCDEF,中序遍歷結(jié)果為CBAEDF,則后序遍歷的結(jié)果為（）。A．CBEFDAB．FEDCBAC．CBEDFAD．不定8.利用二叉鏈表存儲(chǔ)樹時(shí)，則根結(jié)點(diǎn)的右指針是（）。A．指向最左孩子B．指向最右孩子C．空D．非空9.設(shè)有二維數(shù)組A[0..9,0..19],其中每個(gè)元素占兩個(gè)字節(jié)，第一個(gè)元素的存儲(chǔ)地址為100，若按列優(yōu)先順序存儲(chǔ)，則元素A[6,6]存儲(chǔ)地址為()。A.252B.132C.352D.23210.引入二叉線索樹的目的是（）A．加快查找結(jié)點(diǎn)的前驅(qū)或后繼的速度B．為了能在二叉樹中方便的進(jìn)行插入與刪除C．為了能方便的找到雙親D．使二叉樹的遍歷結(jié)果唯一填空題：（每小題2分，共20分）1.下面程序段中劃線部分的執(zhí)行次數(shù)為。inti=0,s=0;while(++i<=n){intp=1;for(intj=1;j<=i;j++)p*=j;s=s+p;}2.向一個(gè)棧頂指針為H的鏈棧中插入一個(gè)s所指結(jié)點(diǎn)時(shí),執(zhí)行的語(yǔ)句是。3.如果一棵Huffman樹T有n0個(gè)葉子結(jié)點(diǎn)，那么樹T中共有個(gè)結(jié)點(diǎn)。4.在帶有一個(gè)頭結(jié)點(diǎn)的鏈隊(duì)列front中，判定只有一個(gè)結(jié)點(diǎn)的條件是。5.對(duì)于一個(gè)具有n個(gè)結(jié)點(diǎn)的單鏈表，在已知p所指向結(jié)點(diǎn)后插入一個(gè)新結(jié)點(diǎn)的時(shí)間復(fù)雜度是；在給定值為x的結(jié)點(diǎn)后插入一個(gè)新結(jié)點(diǎn)的時(shí)間復(fù)雜度是。6.一棵有n（n>0）個(gè)結(jié)點(diǎn)的滿二叉樹共有個(gè)葉子和非終端結(jié)點(diǎn)。7.有一個(gè)100*90的稀疏矩陣（元素類型為整型），非0元素有10個(gè)，設(shè)每個(gè)整型數(shù)占2字節(jié)，則用三元組表示該矩陣時(shí)，所需的字節(jié)數(shù)是。8.樹的后根遍歷序列等同于對(duì)該樹對(duì)應(yīng)的二叉樹進(jìn)行()遍歷的序列。9．具有256個(gè)結(jié)點(diǎn)的完全二叉樹的深度為______。（假設(shè)根結(jié)點(diǎn)的深度為0）10.循環(huán)隊(duì)列用數(shù)組P用（0,…,123）共n個(gè)元素表示，f為當(dāng)前隊(duì)列元素的前一位置，r為隊(duì)尾元素的實(shí)際位置，當(dāng)前隊(duì)列f和r的值分別為100和32,假定隊(duì)列中元素個(gè)數(shù)總小于124,則隊(duì)列中元素個(gè)數(shù)為。判斷題：（每題1分，共10分）1.（）線性表若采用鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)時(shí)，占用內(nèi)存中存儲(chǔ)單元的地址一定不連續(xù)。2.（）線性表中每個(gè)元素都有一個(gè)前驅(qū)和一個(gè)后繼。3.（）廣義表的長(zhǎng)度就是廣義表中的原子個(gè)數(shù)。4.（）任意一棵二叉樹中的結(jié)點(diǎn)的度都不大于2。5.（）判斷線索二叉樹中由P所指結(jié)點(diǎn)是葉子結(jié)點(diǎn)的條件是(P->Lchild==NULL)&&(P->Rchild==NULL)。6.（）采用三元組表方式對(duì)稀疏矩陣進(jìn)行壓縮存儲(chǔ)時(shí)，三元組表中元素個(gè)數(shù)與矩陣中非零元素個(gè)數(shù)相同。7.（）隊(duì)列是一種運(yùn)算受限的線性表。8.（）二叉樹的先序序列中的最后一個(gè)結(jié)點(diǎn)一定是葉子結(jié)點(diǎn)。9.（）完全二叉樹中，若一個(gè)結(jié)點(diǎn)沒(méi)有左孩子，則它必是葉子結(jié)點(diǎn)。10.（）兩個(gè)棧共享一片連續(xù)內(nèi)存空間時(shí)，為提高內(nèi)存利用率，減少溢出機(jī)會(huì)，應(yīng)把兩個(gè)棧的棧底分別設(shè)在這片內(nèi)存空間的兩端。四、簡(jiǎn)答題:(每題5分，共20分)1.設(shè)二叉樹T的存儲(chǔ)結(jié)構(gòu)如下:12345678910Lchild00237580101DataJHFDBACEGIRchild0009400000其中BT為樹根結(jié)點(diǎn)的指針，其值為L(zhǎng)child,Rchild分別為結(jié)點(diǎn)的左、右孩子指針域,data為結(jié)點(diǎn)的數(shù)據(jù)域。（l）畫出二叉樹T的邏輯結(jié)構(gòu)；（2）畫出二叉樹的后序線索樹。2.用下面數(shù)據(jù)逐步建成堆。要求畫出每加入一個(gè)關(guān)鍵碼后堆的變化。（251122345447661100314120）3.已知關(guān)鍵字集合W={11,8,2,3,15,9}，以集合中的關(guān)鍵字作為葉子結(jié)點(diǎn)的權(quán)值而構(gòu)造哈夫曼樹（huffmanTree），畫出構(gòu)造的過(guò)程。4.設(shè)有一字符串P=”3*y-a/y↑2”,試寫出利用棧將P改為”3y*ay2↑/-”的操作步驟。（請(qǐng)用X代表掃描該字符串過(guò)程中順序取一字符進(jìn)棧的操作，用S代表從棧中取出一字符加入到新字符串尾的出棧操作。例如，要使”ABC”變?yōu)椤盉CA”，則操作步驟為XXSXSS）。算法設(shè)計(jì)題：（每題10分，共30分）1.已知L是帶表頭結(jié)點(diǎn)的單鏈表(表中元素個(gè)數(shù)>=2)，P指向某結(jié)點(diǎn)（非第一結(jié)點(diǎn)），刪除P結(jié)點(diǎn)的直接前驅(qū)語(yǔ)句是：2.下面的算法是將整型數(shù)組A[0..n-1]中的元素劃分為兩部分，使得左邊的所有元素均為奇數(shù)，右邊的所有元素均為偶數(shù)，補(bǔ)充完成A,B,C,D四個(gè)空（每處空并非僅有一條語(yǔ)句）：voidPartition(intA[]){i=0;j=n-1;while(A){