【正文】 11．D 12．B 13．C 14．B 15．C 16．C 17．B 18．D 19．C 20．A二、填空題1．線性 2．ni+1 3．相鄰 4．前移，前，后5．物理存儲(chǔ)位置，鏈域的指針值 6．前趨，后繼7．順序，鏈接 8．一定，不一定9．線性，任何，棧頂，隊(duì)尾，隊(duì)頭10．單鏈表，雙鏈表，非循環(huán)鏈表，循環(huán)鏈表11．使空表和非空表統(tǒng)一；算法處理一致12．O(1)，O(n)13．棧滿，?？?，m，棧底，兩個(gè)棧的棧頂在棧空間的某一位置相遇14．315．O(1)三、簡答題1．頭指針是指向鏈表中第一個(gè)結(jié)點(diǎn)（即表頭結(jié)點(diǎn)）的指針；在表頭結(jié)點(diǎn)之前附設(shè)的結(jié)點(diǎn)稱為頭結(jié)點(diǎn)；表頭結(jié)點(diǎn)為鏈表中存儲(chǔ)線性表中第一個(gè)數(shù)據(jù)元素的結(jié)點(diǎn)。其中data為整型數(shù)域，next和prior均為指針域。　　　while (pnext) p=pnext。5. 在單循環(huán)鏈表中設(shè)置尾指針比設(shè)置頭指針好嗎？為什么?6. 假定有四個(gè)元素A, B, C, D依次進(jìn)棧，進(jìn)棧過程中允許出棧，試寫出所有可能的出棧序列。11. 在單鏈表中設(shè)置頭結(jié)點(diǎn)的作用是________。4. 要從一個(gè)順序表刪除一個(gè)元素時(shí)，被刪除元素之后的所有元素均需_______一個(gè)位置，移動(dòng)過程是從_______向_______依次移動(dòng)每一個(gè)元素。 D．snext=hs。C．O(n2) D．O(log2n)15. 設(shè)有一個(gè)棧，元素的進(jìn)棧次序?yàn)锳, B, C, D, E,下列是不可能的出棧序列__________。 10. 線性表的順序存儲(chǔ)結(jié)構(gòu)是一種_______的存儲(chǔ)結(jié)構(gòu)。 snext=pC．pnext=snext。 6. 設(shè)單鏈表中指針p指向結(jié)點(diǎn)m，若要?jiǎng)h除m之后的結(jié)點(diǎn)（若存在），則需修改指針的操作為________。C． pnext=s。A． pnext=s。5. fact(n){ if(n=1) return (1)。j++) { c[i][j]=0。i++)for(j=1。for(i=1。sum=s。 s+=i。for(i=0。 二、填空題 1. 數(shù)據(jù)結(jié)構(gòu)按邏輯結(jié)構(gòu)可分為兩大類，分別是__線性結(jié)構(gòu) 和___非線性結(jié)構(gòu)______________。 j=n。習(xí)題1一、單項(xiàng)選擇題1. 數(shù)據(jù)結(jié)構(gòu)是指（A ）。 j++)x++。2. 數(shù)據(jù)的邏輯結(jié)構(gòu)有四種基本形態(tài)，分別是___集合_____________、_____線性_____________、_____樹_____________和______圖____________。in。}10. 下面程序段的時(shí)間復(fù)雜度是__________________。11. 下面程序段的時(shí)間復(fù)雜度是__________________。in。j=ni。for(k=0。 else return (n*fact(n1))。 sprior=p。 pnextprior=s。A．pnext=pnextnext。 snext=pD．pnext=s。 A．插入 A．A, B, C, D, E B．B, C, D, E, AC．E, A, B, C, D D．E, D, C, B, A 16. 在一個(gè)具有n個(gè)單元的順序棧中，假定以地址低端（即0單元）作為棧底，以top作為棧頂指針，當(dāng)做出棧處理時(shí)，top變化為______。 hs=hsnext。5. 在線性表的順序存儲(chǔ)中，元素之間的邏輯關(guān)系是通過_______決定的；在線性表的鏈接存儲(chǔ)中，元素之間的邏輯關(guān)系是通過_______決定的。12. 對(duì)于一個(gè)具有n個(gè)結(jié)點(diǎn)的單鏈表，在已知的結(jié)點(diǎn)p后插入一個(gè)新結(jié)點(diǎn)的時(shí)間復(fù)雜度為______，在給定值為x的結(jié)點(diǎn)后插入一個(gè)新結(jié)點(diǎn)的時(shí)間復(fù)雜度為_______。7. 什么是隊(duì)列的上溢現(xiàn)象？一般有幾種解決方法，試簡述之?！　? pnext=q?，F(xiàn)在所有結(jié)點(diǎn)已經(jīng)由next域連接起來，試編一個(gè)算法，利用prior域（此域初值為NULL）把所有結(jié)點(diǎn)按照其值從小到大的順序鏈接起來。若鏈表中附設(shè)頭結(jié)點(diǎn)，則不管線性表是否為空表，頭指針均不為空，否則表示空表的鏈表的頭指針為空。若用頭指針來表示該鏈表，則查找終端結(jié)點(diǎn)的時(shí)間為O(n)。 第三種：采用循環(huán)隊(duì)列方式。 else if(i= =0) { s=q。 s=snext?！?ListList *p。操作即可，算法描述如下：void invert(LinkList *head){ //逆置head指針?biāo)赶虻膯窝h(huán)鏈表linklist *p, *q, *s。 } 4．定義類型LinkList如下：typedef struct node{ int data。 //q指向由prior域構(gòu)成的鏈表中待比較的結(jié)點(diǎn) while((q!=NULL) amp。 if (head!=NULL) { q=head。 (pdatamax)) p=pnext。free(p)。 rear=p。}for ( i=(*L).len 。}習(xí)題3一、單項(xiàng)選擇題1. 空串與空格字符組成的串的區(qū)別在于（ ）。＞0 B. i≤n ≤i≤n ≤i≤n+19. 字符串采用結(jié)點(diǎn)大小為1的鏈表作為其存儲(chǔ)結(jié)構(gòu)，是指（ ）。2. 設(shè)s和t是表示成單鏈表的兩個(gè)串，試編寫一個(gè)找出s中第1個(gè)不在t中出現(xiàn)的字符（假定每個(gè)結(jié)點(diǎn)只存放1個(gè)字符）的算法。j=s。while(ps!=NULL){ pt=t。} //find習(xí)題4一、單項(xiàng)選擇題1. 設(shè)二維數(shù)組A[0…m1][0…n1]按行優(yōu)先順序存儲(chǔ)在內(nèi)存中，第一個(gè)元素的地址為p，每個(gè)元素占k個(gè)字節(jié)，則元素aij的地址為（ ）。=((x,(a,B)),(x,(a,B),y)) =(s,(a,B))=((x,(a,B),y)) =((a,B),(c,(a,B),D)9. 通常對(duì)數(shù)組進(jìn)行的兩種基本操作是（ ）。 ，后句錯(cuò) 二、填空題1. 一維數(shù)組的邏輯結(jié)構(gòu)是______________，存儲(chǔ)結(jié)構(gòu)是______________；對(duì)于二維或多維數(shù)組，分為______________和______________兩種不同的存儲(chǔ)方式。9. 三維數(shù)組R[c1…d1,c2…d2,c3…d3]共含有______________個(gè)元素。（ ）7. 矩陣不僅是表示多維數(shù)組，而且是表示圖的重要工具。（ ）15. 廣義表的組成元素可以是不同形式的元素。A. 邏輯 B. 邏輯和存儲(chǔ) C. 物理 D. 線性8. 線索二叉樹中，結(jié)點(diǎn)p沒有左子樹的充要條件是（ ）。A. 是完全二叉樹 B. 不是完全二叉樹C. 是滿二叉樹 D. 不是滿二叉樹二、判斷題1. 二叉樹中每個(gè)結(jié)點(diǎn)的度不能超過2，所以二叉樹是一種特殊的樹。 （　）9. 哈夫曼樹一定是完全二叉樹。7. 在一棵二叉樹中，度為0的結(jié)點(diǎn)個(gè)數(shù)為n0，度為2的結(jié)點(diǎn)個(gè)數(shù)為n2，則n0=______。15. 空樹是指________________________，最小的樹是指_______________________。5. 一棵深度為H的滿k叉樹有如下性質(zhì)：第H層上的結(jié)點(diǎn)都是葉子結(jié)點(diǎn)，其余各層上每個(gè)結(jié)點(diǎn)都有k棵非空子樹，如果按層次自上至下，從左到右順序從1開始對(duì)全部結(jié)點(diǎn)編號(hào)，回答下列問題：（1）各層的結(jié)點(diǎn)數(shù)目是多少？（2）編號(hào)為n的結(jié)點(diǎn)的父結(jié)點(diǎn)如果存在，編號(hào)是多少？（3）編號(hào)為n的結(jié)點(diǎn)的第i個(gè)孩子結(jié)點(diǎn)如果存在，編號(hào)是多少？（4）編號(hào)為n的結(jié)點(diǎn)有右兄弟的條件是什么？其右兄弟的編號(hào)是多少？6. 找出所有滿足下列條件的二叉樹：（1）它們?cè)谙刃虮闅v和中序遍歷時(shí)，得到的遍歷序列相同；（2）它們?cè)诤笮虮闅v和中序遍歷時(shí)，得到的遍歷序列相同；（3）它們?cè)谙刃虮闅v和后序遍歷時(shí)，得到的遍歷序列相同；7. 假設(shè)一棵二叉樹的先序序列為EBADCFHGIKJ，中序序列為ABCDEFGHIJK，請(qǐng)寫出該二叉樹的后序遍歷序列。若沒有結(jié)點(diǎn)n或者該結(jié)點(diǎn)沒有雙親結(jié)點(diǎn)，分別輸出相應(yīng)的信息；若結(jié)點(diǎn)n有雙親，輸出其雙親的值。其右兄弟的編號(hào)是n+1。 //s為一個(gè)指針棧，類型為seqstack，其中包含top域和數(shù)組datastop= 1。} if (stop1) //棧非空訪問，遍歷右子樹 { root=sdata[stop]*2+1。que[1]=t。}}while (rear= =front)。}else{ q=prchild。算法中的front為隊(duì)頭指針，rear為隊(duì)尾指針，若當(dāng)前隊(duì)頭結(jié)點(diǎn)的左、右子樹的根結(jié)點(diǎn)不是所求結(jié)點(diǎn)，則將兩子樹的根結(jié)點(diǎn)入隊(duì)，否則，隊(duì)頭指針?biāo)附Y(jié)點(diǎn)即為結(jié)點(diǎn)的雙親。 //n是根結(jié)點(diǎn)，無雙親else{ front=0。} else { if (tlchild!=NULL) //左子樹的根結(jié)點(diǎn)入隊(duì) { rear=rear%maxsize+1。A. s B. s1 C. s+1 D. 2s 3. 在一個(gè)具有n個(gè)頂點(diǎn)的無向圖中，若具有e條邊，則所有頂點(diǎn)的度數(shù)之和為(　　)。A. n B. n180。e 13. 在一個(gè)具有n個(gè)頂點(diǎn)和e條邊的有向圖的鄰接表中，保存頂點(diǎn)單鏈表的表頭指針向量的大小至少為( )。A. A,B,C,D,E,F B. A,B,C,F,D,EC. A,B,D,C,E,F D. A,C,B,F,D,E 21. 若一個(gè)圖的邊集為{1,2,1,4,2,5,3,1,3,5,4,3}，則從頂點(diǎn)1開始對(duì)該圖進(jìn)行深度優(yōu)先搜索，得到的頂點(diǎn)序列可能為( )。 4. 在一個(gè)具有n個(gè)頂點(diǎn)的無向圖中，要連通所有頂點(diǎn)則至少需要________條邊。 11. 在有向圖的鄰接表和逆鄰接表表示中，每個(gè)頂點(diǎn)鄰接表分別鏈接著該頂點(diǎn)的所有________和________結(jié)點(diǎn)。 19. 根據(jù)圖的存儲(chǔ)結(jié)構(gòu)進(jìn)行某種次序的遍歷，得到的頂點(diǎn)序列是__（唯一/不唯一）的。 5. 已知圖613所示的一個(gè)網(wǎng)，按照Prim方法，從頂點(diǎn)1 出發(fā)，求該網(wǎng)的最小生成樹的產(chǎn)生過程。7. 圖614所示為一個(gè)有向網(wǎng)圖及其帶權(quán)鄰接矩陣，要求對(duì)有向圖采用Dijkstra算法，求從V0 到其余各頂點(diǎn)的最短路徑。三、應(yīng)用題1. 對(duì)于一個(gè)無向圖611(a)，假定采用鄰接矩陣表示，試分別寫出從頂點(diǎn)0出發(fā)按深度優(yōu)先搜索遍歷得到的頂點(diǎn)序列和按廣度優(yōu)先搜索遍歷得到的頂點(diǎn)序列。 13. 假定一個(gè)圖具有n個(gè)頂點(diǎn)和e條邊，則采用鄰接矩陣和鄰接表表示時(shí)，其相應(yīng)的空間復(fù)雜度分別為________和________。 6. 在一個(gè)連通圖中存在著________個(gè)連通分量。A. 1,2,3,4,5 B. 1,2,4,3,5C. 1,2,4,5,3 D. 1,4,2,5,3 23. 由一個(gè)具有n個(gè)頂點(diǎn)的連通圖生成的最小生成樹中，具有( )條邊。A. 1 B. 2 C. 3 D. 4 15. 對(duì)于一個(gè)有向圖，若一個(gè)頂點(diǎn)的度為k1，出度為k2，則對(duì)應(yīng)鄰接表中該頂點(diǎn)單鏈表中的邊結(jié)點(diǎn)數(shù)為( )。e 11. 在一個(gè)具有n個(gè)頂點(diǎn)和e條邊的有向圖的鄰接矩陣中，表示邊存在的元素個(gè)數(shù)為( )。A. n B. n(n1) C. n(n1)/2 D. n(n+1)/2 5. 在一個(gè)具有n個(gè)頂點(diǎn)的有向完全圖中，所含的邊數(shù)為( )。} if (trchild!=NULL) //右子樹的根結(jié)點(diǎn)入隊(duì) { rear=rear%maxsize+1。 que[1]=t。int n。qlchild=prchild。insert(p, s) //將s結(jié)點(diǎn)作為p的右子樹插入BiThrNode *p,*s。 //出隊(duì) t=que[front]。}}}2. 解答：考慮用一個(gè)順序隊(duì)que來保存遍歷過程中的各個(gè)結(jié)點(diǎn)，由于二叉樹以二叉鏈表存儲(chǔ)，所以可設(shè)que為一個(gè)指向數(shù)據(jù)類型為bitree的指針數(shù)組，最大容量為maxnum，下標(biāo)從1開始，同層結(jié)點(diǎn)從左到右存放。while ((root=n) amp。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