【正文】 數(shù)據(jù)結(jié)構(gòu)是指數(shù)據(jù)及其相互之間的______________。 快速排序在最壞情況下的時間復雜度為（ ）。A．行號 B．列號 C．元素值 D．非零元素個數(shù)9. 9. AOV網(wǎng)是一種（ ）。 一個棧的輸入序列為1 2 3，則下列序列中不可能是棧的輸出序列的是( C ) A. 2 3 1 B. 3 2 1 C. 3 1 2 D. 1 2 35. 5. 對線性表，在下列哪種情況下應當采用鏈表表示？( ) 4. 4.3. 3. C. pnext=HL。 A. pnext=HLnext。試題及答案一、其右兄弟的編號是n+1。3. 解答：　略4. 解答：　先序序列：ABDHIEJKCFLG中序序列：HDIBJEKALFCG后序序列：HIDJKEBLFGCA5. 解答：（1）第i層上的結(jié)點數(shù)目是mi1。若沒有結(jié)點n或者該結(jié)點沒有雙親結(jié)點，分別輸出相應的信息；若結(jié)點n有雙親，輸出其雙親的值。 五、算法設計題1. 一棵具有n個結(jié)點的完全二叉樹以一維數(shù)組作為存儲結(jié)構(gòu)，試設計一個對該完全二叉樹進行先序遍歷的算法。5. 一棵深度為H的滿k叉樹有如下性質(zhì)：第H層上的結(jié)點都是葉子結(jié)點，其余各層上每個結(jié)點都有k棵非空子樹，如果按層次自上至下，從左到右順序從1開始對全部結(jié)點編號，回答下列問題：（1）各層的結(jié)點數(shù)目是多少？（2）編號為n的結(jié)點的父結(jié)點如果存在，編號是多少？（3）編號為n的結(jié)點的第i個孩子結(jié)點如果存在，編號是多少？（4）編號為n的結(jié)點有右兄弟的條件是什么？其右兄弟的編號是多少？6. 找出所有滿足下列條件的二叉樹：（1）它們在先序遍歷和中序遍歷時，得到的遍歷序列相同；（2）它們在后序遍歷和中序遍歷時，得到的遍歷序列相同；（3）它們在先序遍歷和后序遍歷時，得到的遍歷序列相同；7. 假設一棵二叉樹的先序序列為EBADCFHGIKJ，中序序列為ABCDEFGHIJK，請寫出該二叉樹的后序遍歷序列。19. 線索鏈表中的rtag域值為_____時，表示該結(jié)點無右孩子，此時______域為指向該結(jié)點后繼線索的指針。15. 空樹是指________________________，最小的樹是指_______________________。11. 一棵含有n個結(jié)點的k叉樹，______形態(tài)達到最大深度，____形態(tài)達到最小深度。7. 在一棵二叉樹中，度為0的結(jié)點個數(shù)為n0，度為2的結(jié)點個數(shù)為n2，則n0=______。3. 對于一個有n個結(jié)點的二叉樹，當它為一棵________二叉樹時具有最小高度，即為_______，當它為一棵單支樹具有_______高度，即為_______。 （?。?. 哈夫曼樹一定是完全二叉樹。 （　）5. 由二叉樹的先序序列和后序序列可以唯一確定一顆二叉樹。A. 是完全二叉樹 B. 不是完全二叉樹C. 是滿二叉樹 D. 不是滿二叉樹二、判斷題1. 二叉樹中每個結(jié)點的度不能超過2，所以二叉樹是一種特殊的樹。A. 三叉鏈表 B. 廣義表 C. 二叉鏈表 D. 順序12. 下面敘述正確的是（ ）。A. 邏輯 B. 邏輯和存儲 C. 物理 D. 線性8. 線索二叉樹中，結(jié)點p沒有左子樹的充要條件是（ ）。A. 3 B. 4 C. 5 D. 64. 在一棵二叉樹上第4層的結(jié)點數(shù)最多為（ ）。（ ）15. 廣義表的組成元素可以是不同形式的元素。（ ）11. 廣義表的表尾一定是一個廣義表。（ ）7. 矩陣不僅是表示多維數(shù)組，而且是表示圖的重要工具。（ ）3. 以行為主序或以列為主序?qū)τ诙嗑S數(shù)組的存儲沒有影響。9. 三維數(shù)組R[c1…d1,c2…d2,c3…d3]共含有______________個元素。 5. 一個nn的對稱矩陣，如果以行為主序或以列為主序存入內(nèi)存，則其容量為______________。 ，后句錯 二、填空題1. 一維數(shù)組的邏輯結(jié)構(gòu)是______________，存儲結(jié)構(gòu)是______________；對于二維或多維數(shù)組，分為______________和______________兩種不同的存儲方式。 13. 若采用三元組壓縮技術(shù)存儲稀疏矩陣，只要把每個元素的行下標和列下標互換，就完成了對該矩陣的轉(zhuǎn)置運算，這種觀點（ ）。=((x,(a,B)),(x,(a,B),y)) =(s,(a,B))=((x,(a,B),y)) =((a,B),(c,(a,B),D)9. 通常對數(shù)組進行的兩種基本操作是（ ）。（設每個元素占d個字節(jié)）A. [(j1)*n +i1]*dB. [(j1)*n +i]*dC．[(j1)*n +i+1]*dD．[(j1)*n +i2]*d5. 設有廣義表D=(a,b,D)，其長度為（ ），深度為（ ）。} //find 習題4一、單項選擇題1. 設二維數(shù)組A[0…m1][0…n1]按行優(yōu)先順序存儲在內(nèi)存中，第一個元素的地址為p，每個元素占k個字節(jié)，則元素aij的地址為（ ）。 if(pt= =NULL)ps=NULL。while(ps!=NULL){ pt=t。設單鏈表類型為LinkList；注意，此時類型 LinkList中的data成分為字符類型。j=s。 for(i=1。2. 設s和t是表示成單鏈表的兩個串，試編寫一個找出s中第1個不在t中出現(xiàn)的字符（假定每個結(jié)點只存放1個字符）的算法。4. 串是指___________________。＞0 B. i≤n ≤i≤n ≤i≤n+19. 字符串采用結(jié)點大小為1的鏈表作為其存儲結(jié)構(gòu)，是指（ ）。 ，并且兩串包含的字符相同，并且對應位置上的字符相同5. 若SUBSTR（S，i，k）表示求S中從第i個字符開始的連續(xù)k個字符組成的子串的操作，則對于S=“Beijing＆Nanjing”，SUBSTR（S，4，5）=（ ）。} 習題3一、單項選擇題1. 空串與空格字符組成的串的區(qū)別在于（ ）。 i) (*L).elem[ i ]=(*L).elem[ i1 ] 。}for ( i=(*L).len 。 //rearnext指向的結(jié)點為循環(huán)鏈隊列的隊頭結(jié)點}8．只要從終端結(jié)點開始往前找到第一個比x大(或相等)的結(jié)點數(shù)據(jù)，在這個位置插入就可以了。 rear=p。if(rear= =NULL) //如為空隊，建立循環(huán)鏈隊列的第一個結(jié)點{ rear=p。free(p)。 p=headnext。 (pdatamax)) p=pnext。 (pdata=min)) { q=p。 if (head!=NULL) { q=head。 } sprior=p。 //q指向由prior域構(gòu)成的鏈表中待比較的結(jié)點 while((q!=NULL) amp。算法描述如下：insert (LinkList *head){ LinkList *p,*s,*q。 }4．定義類型LinkList如下：typedef struct node{ int data。 q=p。操作即可，算法描述如下：void invert(LinkList *head){ //逆置head指針所指向的單循環(huán)鏈表linklist *p, *q, *s?！?}　 return (len)?！?ListList *p。 else { pnext=snext。 s=snext。 s=q。 else if(i= =0) { s=q。算法描述如下：delete(LinkList *q,int i){ //在無頭結(jié)點的單鏈表中刪除第i個結(jié)點 LinkList *p,*s。 第三種：采用循環(huán)隊列方式。 一般地，要解決隊列的上溢現(xiàn)象可有以下幾種方法：（1）可建立一個足夠大的存儲空間以避免溢出，但這樣做往往會造成空間使用率低，浪費存儲空間。若用頭指針來表示該鏈表，則查找終端結(jié)點的時間為O(n)。4．應選用順序存儲結(jié)構(gòu)，因為每個數(shù)據(jù)元素的存儲位置和線性表的起始位置相差一個和數(shù)據(jù)元素在線性表中的序號成正比的常數(shù)。若鏈表中附設頭結(jié)點，則不管線性表是否為空表，頭指針均不為空，否則表示空表的鏈表的頭指針為空。設計一個刪除表中所有值小于max但大于min的元素的算法?，F(xiàn)在所有結(jié)點已經(jīng)由next域連接起來，試編一個算法，利用prior域（此域初值為NULL）把所有結(jié)點按照其值從小到大的順序鏈接起來。2. 在單鏈表上實現(xiàn)線性表的求表長ListLength(L)運算。　　 pnext=q。Lnext){ q=L。7. 什么是隊列的上溢現(xiàn)象？一般有幾種解決方法，試簡述之。15. 無論對于順序存儲還是鏈式存儲的棧和隊列來說，進行插入或刪除運算的時間復雜度均相同為__________。12. 對于一個具有n個結(jié)點的單鏈表，在已知的結(jié)點p后插入一個新結(jié)點的時間復雜度為______，在給定值為x的結(jié)點后插入一個新結(jié)點的時間復雜度為_______。8. 順序表中邏輯上相鄰的元素，物理位置_______相鄰，單鏈表中邏輯上相鄰的元素，物理位置_______相鄰。5. 在線性表的順序存儲中，元素之間的邏輯關(guān)系是通過_______決定的；在線性表的鏈接存儲中，元素之間的邏輯關(guān)系是通過_______決定的。A．front=frontnext 　 B．rear=rearnextC．rear=frontnext 　D．front=rearnext二、填空題1. 線性表是一種典型的_________結(jié)構(gòu)。 hs=hsnext。 hs=s。A．A, B, C, D, E B．B, C, D, E, AC．E, A, B, C, D D．E, D, C, B, A 16. 在一個具有n個單元的順序棧中，假定以地址低端（即0單元）作為棧底，以top作為棧頂指針，當做出棧處理時，top變化為______。A．基地址 B．結(jié)點大小 C．向量大小 D．基地址和結(jié)點大小12. 在等概率情況下，順序表的插入操作要移動______結(jié)點。C．線性表中的每個結(jié)點都有且只有一個直接前趨和直接后繼。 snext=pD．pnext=s。 7. 在一個長度為n的順序表中向第i個元素(0 in+l )之前插入一個新元素時，需向后移動______個元素。A．pnext=pnextnext。 snext=pnext。 pnextprior=s。 snext=pnext。 sprior=p。A．ni B．ni+l C．ni1 D．i3. 線性表采用鏈式存儲時，其地址________。 elsereturn (n*fact(n1))。amp。for(k=0。in。j=ni。2. x=0。in。13. 算法時間復雜度的分析通常有兩種方法，即___________和___________的方法，通常我們對算法求時間復雜度時，采用后一種方法。11. 下面程序段的時間復雜度是__________________。i++)for(j=0。}10. 下面程序段的時間復雜度是__________________。9. 下面程序段的時間復雜度是__________________。in。6. 在圖型結(jié)構(gòu)中，每個結(jié)點的前趨結(jié)點數(shù)和后續(xù)結(jié)點數(shù)可以__________________。2. 數(shù)據(jù)的邏輯結(jié)構(gòu)有四種基本形態(tài)，分別是________________、__________________、__________________和__________________。 8. 數(shù)據(jù)結(jié)構(gòu)作為一門獨立的課程出現(xiàn)是在（ ）年。 j++)x++。for(i=1。}}習題1一、單項選擇題1. 數(shù)據(jù)結(jié)構(gòu)是指（ ）。amp。 。 Llength。 if(i=Llength) return ERROR。L,ElemType x){ int i,j。 qnext=p。試寫出求該二叉樹葉子結(jié)點數(shù)的算法: Status CountLeaves(BinTree amp。設計算法，將棧頂元素出棧并存入e中． base3．設二叉鏈樹的類型定義如下： typedef int Elemtype。L,Elemtype x) {…… }an…a2a12．設順序棧如左圖所示