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