樹(shù)據(jù)結(jié)構(gòu)模擬試卷3套期末考試卷試題帶答案

試卷一一、選擇題（本題共30分,每題2分）1.計(jì)算機(jī)識(shí)別、存儲(chǔ)和加工處理的對(duì)象被統(tǒng)稱為_(kāi)_______。A.數(shù)據(jù)B.數(shù)據(jù)元素C.數(shù)據(jù)結(jié)構(gòu)D.數(shù)據(jù)類型2.已知一棧的進(jìn)棧序列為：1234，則下列哪個(gè)序列為不可能的出棧序列________。A．1234 B．4321C．2143 D．41233.鏈表不具有的特點(diǎn)是________。A.隨機(jī)訪問(wèn)B.不必事先估計(jì)所需存儲(chǔ)空間大小C.插入與刪除時(shí)不必移動(dòng)元素D.所需空間與線性表長(zhǎng)度成正比4.設(shè)InitQueue(Q)、EnQueue(Q,e)、DeQueue(Q,e)分別表示隊(duì)列初始化、入隊(duì)和出隊(duì)的操作。經(jīng)過(guò)以下隊(duì)列操作后，隊(duì)頭的值是________InitQueue(Q);EnQueue(Q,a);EnQueue(Q,b);EnQueue(Q,c);DeQueue(Q,x)A.aB.bC.NULLD.x5.在一個(gè)單鏈表HL中，若要?jiǎng)h除由指針q所指向結(jié)點(diǎn)的后繼結(jié)點(diǎn)，則執(zhí)行________。A．p=q->next;p->next=q->next;free(p);B．p=q->next;q->next=p;free(p);C．p=q->next;q->next=p->next;free(p);D．q->next=q->next->next;q->next=q;free(p);6.一個(gè)順序表第一個(gè)元素的存儲(chǔ)地址是100,每個(gè)元素占2個(gè)存儲(chǔ)單元，則第5個(gè)元素的地址是________。A．110B．108C．100D．1207.在一個(gè)長(zhǎng)度為n的順序存儲(chǔ)的線性表中，在其第i個(gè)位置插入一個(gè)新元素時(shí)，需要移動(dòng)元素的次數(shù)是________。A.n-iB.n-i+1C.n-i-1D.i8．下面關(guān)于線性表的敘述錯(cuò)誤的是________。 A.線性表采用順序存儲(chǔ)必須占用一片連續(xù)的存儲(chǔ)空間 B.線性表采用鏈?zhǔn)酱鎯?chǔ)不必占用一片連續(xù)的存儲(chǔ)空間C.線性表采用鏈?zhǔn)酱鎯?chǔ)便于插入和刪除操作的實(shí)現(xiàn)D.線性表采用順序存儲(chǔ)便于插入和刪除操作的實(shí)現(xiàn)9.Push(e)表示e進(jìn)棧，Pop(e)表示退棧并將棧頂元素存入e。下面的程序段可以將A,B的值交換的操作序列是________。A.Push(A)Push(B)Pop(A)Pop(B)B.Push(A)Push(B)Pop(B)Pop(A)C.Push(A)Pop(B)Push(B)Pop(A)D.Push(B)Pop(A)Push(A)Pop(B)10.下列查找方法中哪一種不適合元素的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)________。A．順序查找B．分塊查找C．二分查找D．散列查找11.下列排序算法中，不能保證每趟排序至少能將一個(gè)元素放到其最終的位置上的算法是________?？焖倥判駼.希爾排序C.堆排序D.冒泡排序12.設(shè)一棵二叉樹(shù)的深度為k，則該二叉樹(shù)中最多有________個(gè)結(jié)點(diǎn)。 A．2k-1 B.2k C.2k-1 D.2k-113.下列四個(gè)選項(xiàng)中，能構(gòu)成堆的是________。A.75,65,30,15,25,45,20,10B.75,65,45,10,30,25,20,15C.75,45,65,30,15,25,20,10D.75,45,65,10,25,30,20,1514.在一個(gè)具有n個(gè)頂點(diǎn)的無(wú)向圖中，要連通全部頂點(diǎn)至少需要多少條邊________。A．n(n-1)/2B．n-1C．nD．n+115.棧和隊(duì)列的共同特點(diǎn)是________。A.都是操作受限的線性表B.都是先進(jìn)后出C.都是后進(jìn)先出D.無(wú)共同點(diǎn)二、填空題（本題共10分，每空1分）若經(jīng)常需要對(duì)線性表進(jìn)行查找操作，則最好采用________存儲(chǔ)結(jié)構(gòu)。某帶頭結(jié)點(diǎn)單鏈表的頭指針為L(zhǎng)，判定該單鏈表非空的條件________________。數(shù)據(jù)的邏輯結(jié)構(gòu)包括集合、________、________和圖狀結(jié)構(gòu)四種類型。圖的兩種遍歷方式為：廣度優(yōu)先遍歷和_______________。線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)中的結(jié)點(diǎn)包含________域和________域。向一棵二叉搜索樹(shù)中插入一個(gè)元素時(shí)，若元素的值小于根結(jié)點(diǎn)的值，則應(yīng)把它插入到根結(jié)點(diǎn)的_______上。下面程序段的功能實(shí)現(xiàn)數(shù)據(jù)x進(jìn)棧，要求在下劃線處填上正確的語(yǔ)句。typedefstruct{intstack[100];inttop;}seqstack;voidpush(seqstack*s,intx){if(s->top==99)printf(“overflow”);else{_____(1)_______________;__(2)_______________;}}三、應(yīng)用題（本題共40分）1．設(shè)散列表長(zhǎng)度為11，散列函數(shù)h(key)=key%11。給定的關(guān)鍵字為1，13，12，34，38，33，2，22。試畫(huà)出用線性探查法解決沖突時(shí)所構(gòu)造的散列表。并計(jì)算在查找成功時(shí)候的平均查找長(zhǎng)度。（6分）2．有一組權(quán)值14、21、32、15、28，畫(huà)出哈夫曼樹(shù)，并計(jì)算其WPL。（6分）3．已知圖G=(V,E)，其中V={1,2,3,4,5},E={(1,2),(1,3),(1,4),(2,3),(2,5),(3,4),(4,5)}。要求完成如下操作：（6分）（1）寫(xiě)出圖的鄰接矩陣（2）寫(xiě)出采用鄰接矩陣存儲(chǔ)時(shí)，從頂點(diǎn)1出發(fā)的廣度優(yōu)先搜索遍歷序列。4．已知序列{503，87，512，61，908，170，897，275，653，462}，分別寫(xiě)出執(zhí)行下列排序算法的各趟排序結(jié)束時(shí)，關(guān)鍵字序列的狀態(tài)：（10分）（1）直接插入排序（2）基數(shù)排序5．對(duì)于下面所示的連通圖，寫(xiě)出由Prim算法生成的最小生成樹(shù)。（5分）6.將下面的樹(shù)轉(zhuǎn)化為一棵二叉樹(shù),并寫(xiě)出對(duì)二叉樹(shù)進(jìn)行層序遍歷的序列。（7分）AABCDEFGH四、算法題（本題共20分）1．完成中序遍歷二叉樹(shù)。Typedefstructnode{Chardata;Structnode*lchild;Structnode*rchild;}BTreeNode,*LinkBtree;VoidInOrder(LinkBtreeBt_pointer){If(Bt_pointer!=NULL){_________(1)_____________;__________(2)_____________;__________(3)____________;}}2.完成二分查找算法：#Definen10typedefintKeyType;typedefstruct{KeyTypekey;}NodeType;TypedefNodeTypeSeqList[n+1];intBinSearch(SeqListR,KeyTypek){intlow=1,high=n,mid;while(_____（4）_______){mid=(low+high)/2;if(R[mid].key==k)returnmid;if(R[mid].key>k)_____（5）_____;else________（6）_______;}return0;}3.編寫(xiě)算法實(shí)現(xiàn)直接插入排序。（8分）參考答案一、選擇題（本題共30分,每題2分）123456789101112131415ADABCBBDACBDCBA二、填空題（本題共10分，每空1分）1）順序2）L->next!=NULL3）線性結(jié)構(gòu)樹(shù)形結(jié)構(gòu)4）深度優(yōu)先遍歷5）數(shù)據(jù)指針6）左子樹(shù)7）s->top++s->stack[s->top]=x三、應(yīng)用題（本題共40分）1、（6分）H(1)=1H(13)=2H(12)=1沖突，H1=2沖突，H2=3H(34)=1沖突，H1=2沖突，H2=3沖突，H3=4H(38)=5H(33)=0H(2)=2沖突，H1=3沖突，H2=4沖突，H3=5沖突，H4=6H(22)=0沖突，H1=1沖突，H2=2沖突，H3=3沖突，H4=4沖突，H5=5沖突，H6=6沖突，H7=7ASL=(1+1+3+4+1+1+5+8)/8=24/8=32、（6分）1101104961212829321415Wpl=2493、圖的鄰接矩陣：（3分）廣度優(yōu)先序列：12345（3分）01110101011101010101010104、1）（503）8751261908170897275653462（5分）（87503）51261908170897275653462（87503512）61908170897275653462（6187503512）908170897275653462（6187503512908）170897275653462（6187170503512908）897275653462（6187170503512897908）275653462（6187170275503512897908）653462（6187170275503512653897908）462（6187170275462503512653897908）2）第一趟：1706151246250365327587897908（5分）第二趟：5039085126536146217027587897第三趟：61871702754625035126538979085、（5分）ABDABDEFGHC層序遍歷序列:ABECFDGH四、算法題（本題共20分）1、（1）InOrder(Bt_pointer->lchild);（2分）(2)printf(“%c”,Bt_pointer->data);（2分）(3)InOrder(Bt_pointer->rchild);（2分）2、（4）low<=high（5）high=mid-1;（6）low=mid+1;（6分）3、voidInsertSort(inta[],intn)（8分）{inti,j;for(i=2;i<=n;i++){a[0]=a[i];j=i-1;while(a[0]<a[j]){a[j+1]=a[j];j--;}a[j+1]=a[0];}}試卷二一、選擇題（本題共20分,每題2分）1.下面程序段的時(shí)間復(fù)雜度為（）。for(i=1;i<=n;i++)for(j=1;j<=n;j++)s++;A.O(n)B.O(n2)C.O(2*n)D.O（i*j）2.線性表采用鏈?zhǔn)酱鎯?chǔ)時(shí)，結(jié)點(diǎn)的存儲(chǔ)地址（）。A．必須是不連續(xù)的B．部分地址必須是連續(xù)的C．連續(xù)與否均可D．和頭結(jié)點(diǎn)的存儲(chǔ)地址相連續(xù)3.若讓元素1，2，3依次進(jìn)棧，則出棧時(shí)的序列不可能出現(xiàn)的是（）。A．3，2，1B．1，2，3C．3，1，2D．2，1，34.下面說(shuō)法不正確的是()A．串S1=“this_is_a_string”的長(zhǎng)度是16。B．串S2=“this”是串S1的子串。C．串S3=“thisis”在串S1中的位置是1。D．串S4=“a”在串S1中的位置是9。5.一個(gè)非空廣義表的表頭（）。A．不可能是子表B．只能是子表C．只能是原子D．可以是子表或原子6.完全二叉樹(shù)()滿二叉樹(shù)A．不一定是B．一定不是C．一定是D．不能確定關(guān)系7.用鏈表表示線性表的優(yōu)點(diǎn)是（）便于隨機(jī)存取便于插入和刪除操作花費(fèi)的存儲(chǔ)空間較順序存儲(chǔ)少元素的物理順序與邏輯順序相同8.在一個(gè)具有n個(gè)頂點(diǎn)的無(wú)向圖中，要連通全部頂點(diǎn)至少需要多少條邊()。A．n(n-1)/2B．n-1C．nD．n+19.下列查找方法中哪一種不適合元素的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)()A．順序查找B．分塊查找C．二分查找D．散列查找10.下面哪種排序方法穩(wěn)定性最好()。A．希爾排序B．冒泡排序C．快速排序D．堆排序二、填空題（本題共20分）1.數(shù)據(jù)的邏輯結(jié)構(gòu)可以分為兩大類：_________和________。2.在二叉樹(shù)的第i層上最多有___________個(gè)結(jié)點(diǎn)。3.無(wú)向圖中恰好有__________條邊，才稱為無(wú)向完全圖。4.用單鏈表方式存儲(chǔ)的線性表，存儲(chǔ)每個(gè)結(jié)點(diǎn)需要有兩個(gè)域，一個(gè)是_________，另一個(gè)是________。5.設(shè)二維數(shù)組A5×6的每個(gè)元素占4個(gè)字節(jié)，已知LOC（a00）=1000，則A一共占用_______字節(jié)。如果按行優(yōu)先存儲(chǔ)時(shí)，a25的起始地址是_________。6.3個(gè)結(jié)點(diǎn)的樹(shù)有_______種形態(tài)，3個(gè)結(jié)點(diǎn)的二叉樹(shù)有________種形態(tài)。7.一個(gè)廣義表為（a，（a，b），d，e，（（i，j），k）），則該廣義表的深度為_(kāi)_______。8.棧的插入操作在_______進(jìn)行，刪除操作在_______進(jìn)行。9.在二叉樹(shù)中，結(jié)點(diǎn)的最大度數(shù)是_______。10.判定一個(gè)有向圖中是否存在回路，即是否含有環(huán)，可以使用_________方法。11.二分查找的效率較高，但是要求查找表中的關(guān)鍵字_______，并且要求表的存儲(chǔ)為_(kāi)_______。12.在構(gòu)造散列表的過(guò)程中，不可避免會(huì)出現(xiàn)沖突，通常解決它的方法有_______和_______。13．從任何一個(gè)結(jié)點(diǎn)開(kāi)始都能成功查找其他結(jié)點(diǎn)的單鏈表是表。三、應(yīng)用題（本題共50分，每題10分）1.一棵二叉樹(shù)如右面的圖所示，要求：（1）寫(xiě)出對(duì)此二叉樹(shù)進(jìn)行中序遍歷時(shí)得到的結(jié)點(diǎn)序列。（2）畫(huà)出由此二叉樹(shù)轉(zhuǎn)換得到的森林。2.已知圖G的鄰接表如下，寫(xiě)出從頂點(diǎn)O出發(fā)的深度優(yōu)先和廣度優(yōu)先遍歷的頂點(diǎn)序列。0021310022030130203.對(duì)于下面所示的連通圖，寫(xiě)出由Prim算法生成的最小生成樹(shù)。4.下圖所示為AOE網(wǎng)，求其關(guān)鍵路徑和關(guān)鍵活動(dòng)。四、算法填空題（本題共10分）下列兩個(gè)算法分別為二分查找算法和冒泡排序算法，閱讀下面程序代碼，填充空白位置，使算法完整。#Definen10typedefintKeyType;typedefstruct{KeyTypekey;}NodeType;typedefNodeTypeSeqList[n+1];1.intBinSearch(SeqListR,KeyTypek){intlow=1,high=n,mid;while(low<=high){mid=(low+high)/2;if(R[mid].key==k)returnmid;if(R[mid].key>k)______1_____;else________2_______;}return0;}2.voidBubbleSort(SeqListR){inti,jBooleanexchange;For(i=1;i<n;i++){exchange=false;for(j=1;j<=n-I;j++)if(R[j+1].key<R[j].key){_______3_____;______4______;R[j]=R[0];________5__________}if(!exchange)return;}}參考答案一、選擇題（本題共20分,每題2分）12345678910BCCCDAbBCB二、填空題（本題共20分,每空1分）1）線性結(jié)構(gòu)，非線性結(jié)構(gòu)2）2i-13）n(n-1)/24）數(shù)據(jù)域，指針域5）1120，10686）2，57）58）棧頂，棧頂9）210）拓?fù)渑判?1）有序，順序存儲(chǔ)12）開(kāi)放定址法，拉鏈法13）單循環(huán)鏈表三、應(yīng)用題（本題共50分）1）DEFBAC--------8分―――――――8分2）深度優(yōu)先遍歷：0231―――――6分廣度優(yōu)先遍歷：0213――――6分3）--------12分4）頂點(diǎn)vevl活動(dòng)ell-eV100a1011V234a2000V322a3341V466a4341V567a5220V688a6253a7660a8671---------6分關(guān)鍵路徑是：V1-V3-V4-V6---------2分關(guān)鍵活動(dòng)是：a2,a5,a7---------2分四、算法填空題（本題共10分,每空2分）1）high=mid-1;---------2分2）low=mid+1;---------2分3）R[0]=R[j+1];---------2分4）R[j+1]=R[j];---------2分5）exchange=true;---------2分試卷三一、單項(xiàng)選擇題(在下列每小題四個(gè)備選答案中選出一個(gè)正確答案，并將其字母標(biāo)號(hào)填入題干的括號(hào)內(nèi)。每小題2分，共30分)1．?dāng)?shù)據(jù)結(jié)構(gòu)可以形式化地定義為（S，△），其中S指某種邏輯結(jié)構(gòu)，△是指（）A.S上的算法 B.S的存儲(chǔ)結(jié)構(gòu)C.在S上的一個(gè)基本運(yùn)算集 D.在S上的所有數(shù)據(jù)元素2．下列說(shuō)法正確的是（）A.線性表的邏輯順序與存儲(chǔ)順序總是一致的B.線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)中，要求內(nèi)存中可用的存儲(chǔ)單元可以是連續(xù)的，也可以不連續(xù)C.線性表的線性存儲(chǔ)結(jié)構(gòu)優(yōu)于鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)D.每種數(shù)據(jù)結(jié)構(gòu)都具有插入、刪除和查找三種基本運(yùn)算3．稀疏矩陣一般采用（）方法壓縮存儲(chǔ)。A.三維數(shù)組 B.單鏈表C.三元組表 D.散列表4.在一個(gè)單鏈表中，若p↑結(jié)點(diǎn)不是最后結(jié)點(diǎn)，在p↑之后插入s↑結(jié)點(diǎn)，則實(shí)行()。A.s↑.next:=p；p↑.next=s;B.s↑.next:=p↑.next;p↑.next:=s；C.s↑.next:=p↑.next;p:=s;D.p↑.next:=s;s↑.next=p;5.某個(gè)向量第一元素的存儲(chǔ)地址為100，每個(gè)元素的長(zhǎng)度為2，則第五個(gè)元素的地址是()。A.110B.108C.100D.1206.下面的二叉樹(shù)中，()不是完全二叉樹(shù)。7.一組記錄的排序碼為(47、78、61、33、39、80)，則利用堆排序的方法建立的初始堆為()。A.78、47、61、33、39、80B.80、78、61、33、39、47C.80、78、61、47、39、33D.80、61、78、39、47、338.假設(shè)left和right為雙向鏈表中指向直接前趨結(jié)點(diǎn)和直接后繼結(jié)點(diǎn)的指針域，現(xiàn)要把一個(gè)指針s所指的新結(jié)點(diǎn)作為非空雙鏈表中q所指地點(diǎn)(中間結(jié)點(diǎn))的直接后繼結(jié)點(diǎn)插入到該雙向鏈表中，則下列算法段能正確完成上述要求的是()A.q->right=s;s->left=q;q->right->left=s;s->right=q->right;B.s->left=q;q->right=s;q->right->left=s;s->right=q->right;C.s->left=q;s->right=q->right;q->right->left=s;q->right=s;D.以上都不對(duì)9.由下列三棵樹(shù)組成轉(zhuǎn)的森林換成一棵二叉樹(shù)為()10.for（i=0；i<m；i++）for（j=0；j<t；j++）c［i］［j］=0；for（i=0；i<m；i++）for（j=0；j<t；j++）for（k=0；k<n；k++）c［i］［j］=c［i］［j］+a［i］［k］*b［k］［j］；上列程序的時(shí)間復(fù)雜度為（）A.O（m+n×t） B.O（m+n+t）C.O（m×n×t） D.O（m×t+n）11.設(shè)循環(huán)隊(duì)列的元素存放在一維數(shù)組Q［0‥30］中，隊(duì)列非空時(shí)，front指示隊(duì)頭元素的前一個(gè)位置，rear指示隊(duì)尾元素。如果隊(duì)列中元素的個(gè)數(shù)為11，front的值為25，則rear應(yīng)指向的元素是（）A.Q［4］ B.Q［5］ C.Q［14］ D.Q［15］12.定義二維數(shù)組A［1‥8，0‥10］，起始地址為L(zhǎng)OC，每個(gè)元素占2L個(gè)存儲(chǔ)單元，在以行序?yàn)橹餍虻拇鎯?chǔ)方式下，某數(shù)據(jù)元素的地址為L(zhǎng)OC+50L，則在以列序?yàn)橹餍虻拇鎯?chǔ)方式下，該元素的存儲(chǔ)地址為（）A.LOC+28L B.LOC+36L C.LOC+50L D.LOC+52L13.采用排序算法對(duì)n個(gè)元素進(jìn)行排序，其排序趟數(shù)肯定為n-1趟的排序方法是（）A.插入和快速 B.冒泡和快速 C.選擇和插入 D.選擇和冒泡14.設(shè)h是指向非空帶表頭結(jié)點(diǎn)的循環(huán)鏈表的頭指針，p是輔助指針。執(zhí)行程序段p=h;while(p->next->next!=h)p=p->next;p->next=h;后（其中，p->next為p指向結(jié)點(diǎn)的指針域），則()A.p->next指針指向鏈尾結(jié)點(diǎn) B.h指向鏈尾結(jié)點(diǎn)C.刪除鏈尾前面的結(jié)點(diǎn) D.刪除鏈尾結(jié)點(diǎn)15.某二叉樹(shù)的先根遍歷序列和后根遍歷序列正好相反，則該二叉樹(shù)具有的特征是()A.高度等于其結(jié)點(diǎn)數(shù) B.任一結(jié)點(diǎn)無(wú)左孩子C.任一結(jié)點(diǎn)無(wú)右孩子 D.空或只有一個(gè)結(jié)點(diǎn)二、填空題(本大題共13小題，每小題2分，共26分)請(qǐng)?jiān)诿啃☆}的空格中填上正確答案。錯(cuò)填、不填均無(wú)分。16.數(shù)據(jù)的邏輯結(jié)構(gòu)通常包括集合、線性結(jié)構(gòu)、____________和圖狀結(jié)構(gòu)。17．給定n個(gè)值構(gòu)造哈夫曼樹(shù)。根據(jù)哈夫曼算法，初始森林中共有n棵二叉樹(shù)，經(jīng)過(guò)次合并后才能使森林中的二叉樹(shù)的數(shù)目由n棵減少到只剩下一棵最終的哈夫曼樹(shù)。18．樹(shù)型結(jié)構(gòu)結(jié)點(diǎn)間通過(guò)“父子”關(guān)系相互關(guān)聯(lián)，這種相互關(guān)聯(lián)構(gòu)成了數(shù)據(jù)間的關(guān)系。19.在一個(gè)具有n個(gè)結(jié)點(diǎn)的單鏈表中查找值為m的某結(jié)點(diǎn)，若查找成功，則需平均比較的結(jié)點(diǎn)數(shù)為_(kāi)___________。20.數(shù)據(jù)表示和________________是程序設(shè)計(jì)者所要考慮的兩項(xiàng)基本任務(wù)。21.在循環(huán)隊(duì)列中，存儲(chǔ)空間為0~n-1。設(shè)隊(duì)頭指針front指向隊(duì)頭元素前一個(gè)空閑元素，隊(duì)尾指針指向隊(duì)尾元素，那么其隊(duì)空標(biāo)志為rear=front，隊(duì)滿標(biāo)志為_(kāi)________。22.深度為k的二叉樹(shù)至多有_________個(gè)結(jié)點(diǎn)，最少有_________個(gè)結(jié)點(diǎn)。23．在堆排序和快速排序中，若原始記錄已基本有序，則較適合選用。24.在一棵二叉排序樹(shù)上按____________遍歷得到的結(jié)點(diǎn)序列是一個(gè)有序序列。25.實(shí)現(xiàn)二分查找的存儲(chǔ)結(jié)構(gòu)僅限于順序存儲(chǔ)結(jié)構(gòu)，且其中元素排列必須是____________的。26.三個(gè)結(jié)點(diǎn)可構(gòu)成________種不同形態(tài)的二叉樹(shù)。27.設(shè)需將一組數(shù)據(jù)按升序排序。在無(wú)序區(qū)中依次比較相鄰兩個(gè)元素ai和ai+1的值，若ai的值大于ai+1的值，則交換ai和ai+1。如此反復(fù)，直到某一趟中沒(méi)有記錄需要交換為止，該排序方法被稱為_(kāi)________。28.對(duì)于一棵具有n個(gè)結(jié)點(diǎn)的二叉樹(shù)，當(dāng)進(jìn)行鏈接存儲(chǔ)時(shí)，其二叉鏈表中的指針域的總數(shù)為2n個(gè)，其中________個(gè)用于鏈接孩子結(jié)點(diǎn)。三、應(yīng)用題（本大題共5小題，每小題6分，共30分）29.已知一棵二叉樹(shù)的前序序列是ABCDEFG，中序序列是CBDAEGF。請(qǐng)構(gòu)造出該二叉樹(shù)，并給出該二叉樹(shù)的后序序列。30．有一字符串序列為5*-x-y/x+2，利用棧的運(yùn)算將其輸出結(jié)果變?yōu)?x-*yx+/-2，試寫(xiě)出該操作的入棧和出棧過(guò)程（采用push(a)表示a入棧，pop(a)表示a出棧）。31.已知某二叉樹(shù)的順序存儲(chǔ)結(jié)構(gòu)如圖所示，試畫(huà)出該二叉樹(shù)，并畫(huà)出其二叉鏈表表示。ABCDEFG32.已知一組鍵值序列為(38，64，73，52，40，37，56，43)，試采用快速排序法對(duì)該組序列作升序排序，并給出每一趟的排序結(jié)果。33.請(qǐng)按照數(shù)列{28，45，33，12，37，20，18，55}的先后插入次序，生成一棵二叉排序樹(shù)。四、算法設(shè)計(jì)題(本大題共3小題，共14分)34.試編寫(xiě)一算法，以完成在帶頭結(jié)點(diǎn)單鏈表L中第i個(gè)位置前插入元素X的操作。（4分）35.某帶頭結(jié)點(diǎn)的單鏈表的結(jié)點(diǎn)結(jié)構(gòu)說(shuō)明如下：（6分）typedefstructnode1{intdata;structnode1*next}node；試設(shè)計(jì)一個(gè)算法intcopy(node*head1,node*head2)，將以head1為頭指針的單鏈表復(fù)制到一個(gè)不帶頭結(jié)點(diǎn)且以head2為頭指針的單鏈表中。36.若二叉樹(shù)存儲(chǔ)結(jié)構(gòu)采用二叉鏈表表示，試編寫(xiě)一算法，計(jì)算一棵二叉樹(shù)的所有結(jié)點(diǎn)數(shù)。（4分）參考答案一、選擇題（本題共30分,每題2分）1、C2、B3、C4、B5、B6、C7、B8、C9、A10、C11、B12、D13、C14、D15、A二、填空題（本題共26分,每小題2分）16、樹(shù)狀結(jié)構(gòu)17、n-118、邏輯19、n/220、數(shù)據(jù)處理21、front==(rear+1)%n22、2k-1，k23、堆排序24、中序25、有序26、527、冒泡排序28、n-1三、應(yīng)用題（本題共30分，每小題6分）29、ABABCDGFEFE30、push(5);pop(5);push(*);push(-);push(x);pop(x);pop(-);pop(*);push(-);push(y);pop(y);push(/);push(x);pop(x);push(+);pop(+);pop(/);pop(-);push(2);pop(2);ACACDEFG第1趟：[37]38[735240645643]第2趟：3738[4352406456]73第3趟：3738[40]43[526456]73第4趟：3738404352[6456]73第5趟：37