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