南京大學-計算機專業(yè)考研復(fù)習資料-數(shù)據(jù)結(jié)構(gòu)期中 答案

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