【正文】 A. O(n) B. O(1) C. O(log2n) D. O(n2)A．低于鏈接法處理沖突 B. 高于鏈接法處理沖突 C．與鏈接法處理沖突相同 D．高于二分查找7. 7. B. pnext=HL。 對一個算法的評價，不包括如下（B ）方面的內(nèi)容。7. 解答：后序序列：ACDBGJKIHFE8. 解答：先序序列：ABCDGEIHFJK9. 解答：先根遍歷：ABCDEFGHIJKLMNO后根遍歷：BDEFCAHJIGKNOML森林轉(zhuǎn)換成二叉樹如圖516所示。其中根結(jié)點(diǎn)為a；葉子結(jié)點(diǎn)有：d、m、n、j、k、f、l；c是結(jié)點(diǎn)g的雙親；a、c是結(jié)點(diǎn)g的祖先；j、k是結(jié)點(diǎn)g的孩子；m、n是結(jié)點(diǎn)e的子孫；e是結(jié)點(diǎn)d的兄弟；g、h是結(jié)點(diǎn)f的兄弟；結(jié)點(diǎn)b和n的層次號分別是2和5；樹的深度為5。9. 給出如圖514所示的森林的先根、后根遍歷結(jié)點(diǎn)序列，然后畫出該森林對應(yīng)的二叉樹。17. 三叉鏈表比二叉鏈表多一個指向______________的指針域。9. 由三個結(jié)點(diǎn)構(gòu)成的二叉樹，共有____種不同的形態(tài)。 （?。┤?、填空題1. 假定一棵樹的廣義表表示為A（B（E），C（F（H，I，J），G），D），則該樹的度為_____，樹的深度為_____，終端結(jié)點(diǎn)的個數(shù)為______，單分支結(jié)點(diǎn)的個數(shù)為______，雙分支結(jié)點(diǎn)的個數(shù)為______，三分支結(jié)點(diǎn)的個數(shù)為_______，C結(jié)點(diǎn)的雙親結(jié)點(diǎn)為_______，其孩子結(jié)點(diǎn)為_______和_______結(jié)點(diǎn)。 （　）3. 線索二叉樹是一種邏輯結(jié)構(gòu)。A. n在m右方 B. n在m 左方 C. n是m的祖先 D. n是m的子孫10. 如果F是由有序樹T轉(zhuǎn)換而來的二叉樹，那么T中結(jié)點(diǎn)的前序就是F中結(jié)點(diǎn)的（ ）。A. 4 B. 5 C. 6 D. 72. 假設(shè)在一棵二叉樹中，雙分支結(jié)點(diǎn)數(shù)為15，單分支結(jié)點(diǎn)數(shù)為30個，則葉子結(jié)點(diǎn)數(shù)為（ ）個。（ ）9. 矩陣中的行列數(shù)往往是不相等的。三、判斷題1. 數(shù)組可看作基本線性表的一種推廣，因此與線性表一樣，可以對它進(jìn)行插入、刪除等操作。3. 一個廣義表為(a,(a,b),d,e,((i,j),k))，則該廣義表的長度為_____，深度為_____。 11. 數(shù)組A中，每個元素的長度為3個字節(jié)，行下標(biāo)i從1到8，列下標(biāo)j從1到10，從首地址SA開始連續(xù)存放在存儲器內(nèi)，該數(shù)組按行存放時，元素A[8][5]的起始地址為（ ）。 3. 若數(shù)組A[0…m][0…n]按列優(yōu)先順序存儲，則aij地址為（ ）。amp。return (1)。int s,t,m。2. 兩個字符串相等的充要條件是_____________________和___________________。3. 下面的說法中，只有（ ）是正確的。amp。if(rearnext= =rear) //隊中只有一個結(jié)點(diǎn)rear=NULL。} }7．本題是對一個循環(huán)鏈隊列做插入和刪除運(yùn)算，假設(shè)不需要保留被刪結(jié)點(diǎn)的值和不需要回收結(jié)點(diǎn)，算法描述如下：（1）插入（即入隊）算法：insert(LinkList *rear, elemtype x){ //設(shè)循環(huán)鏈隊列的隊尾指針為rear,x為待插入的元素 LinkList *p。　}}6．算法描述如下：delete(LinkList *head, int max, int min){ LinkList *p,*q。 while((p!=NULL) amp。 (pdataqdata)) //查找插入結(jié)點(diǎn)p的合適的插入位置{ s=q。}LinkList。 p=headnext?！?while ( pnext!=NULL ){ p=pnext。}if (s= =NULL) printf(Cant39。 free(s)。8．該算法的功能是：將開始結(jié)點(diǎn)摘下鏈接到終端結(jié)點(diǎn)之后成為新的終端結(jié)點(diǎn)，而原來的第二個結(jié)點(diǎn)成為新的開始結(jié)點(diǎn)，返回新鏈表的頭指針。當(dāng)有元素要加入隊列（即入隊）時，若rear=maxnum，則會發(fā)生隊列的上溢現(xiàn)象，此時就不能將該元素加入隊列。線性表的順序存儲結(jié)構(gòu)可以直接存取數(shù)據(jù)元素，方便靈活、效率高，但插入、刪除操作時將會引起元素的大量移動，因而降低效率：而在鏈接存儲結(jié)構(gòu)中內(nèi)存采用動態(tài)分配，利用率高，但需增設(shè)指示結(jié)點(diǎn)之間關(guān)系的指針域，存取數(shù)據(jù)元素不如順序存儲方便，但結(jié)點(diǎn)的插入、刪除操作較簡單。試編寫一個刪除表中所有值大于min且小于max的元素（若表中存在這樣的元素）的算法?！　　　return (L)。if(Lamp。為了增加內(nèi)存空間的利用率和減少發(fā)生上溢的可能性，由兩個棧共享一片連續(xù)的內(nèi)存空間時，應(yīng)將兩棧的_______分別設(shè)在這片內(nèi)存空間的兩端，這樣只有當(dāng)_______時才產(chǎn)生上溢。7. 當(dāng)對一個線性表經(jīng)常進(jìn)行存取操作，而很少進(jìn)行插入和刪除操作時，則采用_______存儲結(jié)構(gòu)為宜。A．rear％n= = front B．（front+l）％n= = rearC．rear％n 1= = front D．(rear+l)％n= = front 19. 在具有n個單元的順序存儲的循環(huán)隊列中，假定front和rear分別為隊頭指針和隊尾指針，則判斷隊空的條件為________。A．hsnext=s。10. 線性表的順序存儲結(jié)構(gòu)是一種_______的存儲結(jié)構(gòu)。 pnext=sB．qnext=s。 pnext=s。 pnextprior=s。A．n/2 B．n C．（n+1）/2 D．（n1）/2 5. 在雙向循環(huán)鏈表中，在p所指的結(jié)點(diǎn)之后插入s指針?biāo)傅慕Y(jié)點(diǎn)，其操作是____。return (i)。j=n。in。1. x=0。j++)s+=B[i][j]。while(sn){ i++。8. 下面程序段的時間復(fù)雜度是__________________。 ，后半句錯 ，后半句對10. 計算機(jī)內(nèi)部數(shù)據(jù)處理的基本單位是（ ）。 i++)for(j=i。 CountLeaves (Tlchild,n)。S,Elemtype amp。iLlength。n) {//n is the number of leaves…… }答案：選擇題（每題1分）C D A D C D A B C C 一、 填空題1． 設(shè)計、實(shí)現(xiàn)2． 特殊、棧頂3． LOC（a1）+(i1)*L4． pnext=qnext。 //棧底指針Elemtype *top。（6分）三、 設(shè)計題（30分，每題10分,用C語言寫出算法，做在答題紙上）1． 已知線性表（a1,a2,…,an）以順序存儲結(jié)構(gòu)為存儲結(jié)構(gòu)，其類型定義如下： define LIST_INIT_SIZE 100 //順序表初始分配容量 typedef struct { Elemtype *elem。并指出具有n個元素的插入排序的時間復(fù)雜度是多少？(5分)5． 已知一網(wǎng)絡(luò)的鄰接矩陣如下，求從頂點(diǎn)A開始的最小生成樹。7．已知二叉樹的中序遍歷序列為BCA，后序遍歷序列為CBA，則該二叉樹的先序遍歷序列為 ，層序遍歷序列為 。 pnext= next。（A）、有序順序表 （B）、有序單鏈表（C）、有序順序表和有序單鏈表都可以 （D）、無限制4．順序存儲結(jié)構(gòu)的優(yōu)勢是（ ）。 （A）、利于插入操作 （B）、利于刪除操作 （C）、利于順序訪問 （D）、利于隨機(jī)訪問5．深度為k的完全二叉樹，其葉子結(jié)點(diǎn)必在第（ ）層上。 （D）、p=Qnext。三、應(yīng)用題1． 設(shè)散列函數(shù)H(k)=k % 13,設(shè)關(guān)鍵字系列為{22,12,24,6,45,7,8,13,21},要求用線性探測法處理沖突。(8分，要有過程) A B C D E F（1）求從頂點(diǎn)A開始的最小生成樹。 //順序存儲空間基址 int length。 //棧頂指針 }Stack。qnextprior=p。i++)if(Lelem[i]==x) break。e){ if(==) return ERROR。 CountLeaves (Trchild,n)。 j=n。 二、填空題1. 數(shù)據(jù)結(jié)構(gòu)按邏輯結(jié)構(gòu)可分為兩大類，分別是____________?__和_________________。for(i=0。 s+=i。sum=s。for(i=1。i++)for(j=1。j++) { c[i][j]=0。5. fact(n){ if(n=1)return (1)。A． pnext=s。C． pnext=s。 6. 設(shè)單鏈表中指針p指向結(jié)點(diǎn)m，若要刪除m之后的結(jié)點(diǎn)（若存在），則需修改指針的操作為________。 snext=pC．pnext=snext。 A．隨機(jī)存取 B．順序存取 C．索引存取 D．散列存取11. 在順序表中，只要知道_______，就可在相同時間內(nèi)求出任一結(jié)點(diǎn)的存儲地址。 B．snext=hs。A．rear％n= = front B．front+l= rearC．rear= = front D．(rear+l)％n= front20. 在一個鏈隊列中，假定front和rear分別為隊首和隊尾指針，則刪除一個結(jié)點(diǎn)的操作為________。相反，當(dāng)經(jīng)常進(jìn)行的是插入和刪除操作時，則采用_______存儲結(jié)構(gòu)為宜。14. 設(shè)有一空棧，現(xiàn)有輸入序列1，2，3，4，5，經(jīng)過push, push, pop, push, pop, push, push后，輸出序列是_________。amp。}四、算法設(shè)計題1. 設(shè)計在無頭結(jié)點(diǎn)的單鏈表中刪除第i個結(jié)點(diǎn)的算法。6. 已知線性表的元素是無序的，且以帶頭結(jié)點(diǎn)的單鏈表作為存儲結(jié)構(gòu)。3．應(yīng)選用鏈接存儲結(jié)構(gòu)，因?yàn)殒準(zhǔn)酱鎯Y(jié)構(gòu)是用一組任意的存儲單元依次存儲線性表中的各元素，這里存儲單元可以是連續(xù)的，也可以是不連續(xù)的：這種存儲結(jié)構(gòu)對于元素的刪除或插入運(yùn)算是不需要移動元素的，只需修改指針即可，所以很容易實(shí)現(xiàn)表的容量的擴(kuò)充。對于隊列，還有一種“假溢出”現(xiàn)象，隊列中尚余有足夠的空間，但元素卻不能入隊，一般是由于隊列的存儲結(jié)構(gòu)或操作方式的選擇不當(dāng)所致，可以用循環(huán)隊列解決。四、算法設(shè)計題 1．算法思想為：（1）應(yīng)判斷刪除位置的合法性，當(dāng)i0或in1時，不允許進(jìn)行刪除操作；（2）當(dāng)i=0時，刪除第一個結(jié)點(diǎn)：（3）當(dāng)０in時，允許進(jìn)行刪除操作，但在查找被刪除結(jié)點(diǎn)時，須用指針記住該結(jié)點(diǎn)的前趨結(jié)點(diǎn)。 }else { j=0。t delete)?！　　en++。 while (p!=head) //當(dāng)表不為空時，逐個結(jié)點(diǎn)逆置 { s=q。此題可采用插入排序的方法，設(shè)p指向待插入的結(jié)點(diǎn)，用q搜索已由prior域鏈接的有序表找到合適位置將p結(jié)點(diǎn)鏈入。 q=qprior。amp。 q=head。p=(LinkList *)malloc(sizeof(LinkList))。elserearnext=rearnextnext。 (*L).elem[ i1 ] x 。，則T一定是S的一個子串4. 兩個字符串相等的條件是（ ）。3. 設(shè)字符串S1= “ABCDEF”，S2= “PQRS”，則運(yùn)算S=CONCAT（SUB（S1，2，LEN（S2）），SUB（S1，LEN（S2），2））后的串值為___________________。{ int i,j。} //delete2．算法思想為：（1）鏈表s中取出一個字符；將該字符與單鏈表t中的字符依次比較；（2）當(dāng)t中有與從s中取出的這個字符相等的字符，則從t中取下一個字符重復(fù)以上比較；（3）當(dāng)t中沒有與從s中取出的這個字符相等的字符，則算法結(jié)束。(psdata!=ptdata)) pt=ptnext。(a00)+[j*m+i] B. LOC(a00)+[j*n+i](a00)+[(j1)*n+i1] D. LOC(a00)+[(j1)*m+i1]4. 若下三角矩陣Ann，按列順序壓縮存儲在數(shù)組Sa[0…(n+1)n/2]中，則非零元素aij的地址為（ ）。+141 +144 +222 +22512. 稀疏矩陣一般的壓縮存儲方法有兩種，即（ ）。4. 一個稀疏矩陣為 ，則對應(yīng)的三元組線性表為_____________。（ ）2. 多維數(shù)組可以看作數(shù)據(jù)元素也是基本線性表的基本線性表。（ ）10. 廣義表