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

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