【正文】 對鄰接表只能用于存儲有向圖，而鄰接矩陣則可存儲有向圖和無向圖。答案：將鄰接矩陣的第i行元素全部置為0. 若以鄰接矩陣表示有向圖，則鄰接矩陣上第i行中非零元素的個數(shù)即為頂點vi的 。答案：1判定一個有向圖是否存在回路，可以利用 。答案：n1條一個連通圖的生成樹是一個 ，它包含圖中所有頂點，但只有足以構(gòu)成一棵樹的n1條邊。12345324524^^^^^A. v1,v2,v3,v4,v5 B. v1,v3,v2,v4,v5 C. v1,v2,v3,v5,v4 D. v1,v4,v3,v5,v22對于一個有向圖，若一個頂點的入度為k1,、出度為k2，則對應(yīng)鄰接表中該頂點單鏈表中的結(jié)點數(shù)為（ B ）。A. n B. e C. 2e D. n*e2設(shè)圖的鄰接矩陣為，則該圖為（ A ）。A. n(n1)/2 B. n(n1) C. n(n+1)/2 D. n22已知一個有向圖的鄰接表存儲結(jié)構(gòu)如圖所示，根據(jù)深度優(yōu)先遍歷算法，從頂點v1出發(fā)，所得到的頂點序列是（ C ）。的元素之和 C. 第i行非165。A. 1/2 B. 1 C. 2 D. 41下列關(guān)于圖遍歷的說法不正確的是（ C ）。E2則稱（ A ）。A. 125634　 B. 516234 C. 123456 D. 5216431在無向圖中定義頂點vi與vj之間的路徑為從vi到vj的一個（ A ）。A. 中序遍歷 B. 先序遍歷 C. 后序遍歷 D. 按層次遍歷無向圖的鄰接矩陣是一個（ A ）。A. 完全圖 B. 連通圖 C. 有回路 D. 一棵樹關(guān)鍵路徑是事件結(jié)點網(wǎng)絡(luò)中（ A ）。count_preorder(tlchild)。答案：1如下所示的二叉樹，請寫出先序、中序、后序遍歷的序列。答案：一份電文中有6種字符：A,B,C,D,E,F，它們的出現(xiàn)頻率依次為16，5，9，3，30，1，完成問題：（1）設(shè)計一棵哈夫曼樹；（畫出其樹結(jié)構(gòu)）（2）計算其帶權(quán)路徑長度WPL；答案：(1)樹形態(tài)： (2)帶權(quán)路徑長度：WPL=30*1+16*2+9*3+5*4+(1+3)*5=30+32+27+20+20=129已知某森林的二叉樹如下所示，試畫出它所表示的森林。答案：二叉樹形態(tài) 試用權(quán)集合{12,4,5,6,1,2}構(gòu)造哈夫曼樹，并計算哈夫曼樹的帶權(quán)路徑長度。}}答案：二叉樹后序遍歷遞歸算法五、綜合題假設(shè)以有序?qū),c表示從雙親結(jié)點到孩子結(jié)點的一條邊，若已知樹中邊的集合為{a,b,a,d,a,c,c,e,c,f,c,g,c,h,e,i,e,j,g,k},請回答下列問題：（1）哪個結(jié)點是根結(jié)點？ a（2）哪些結(jié)點是葉子結(jié)點？ b,d,i,j,f,k,h（3）哪些結(jié)點是k的祖先？ g,c,a（4）哪些結(jié)點是j的兄弟？ i（5）樹的深度是多少？ 4假設(shè)一棵二叉樹的先序序列為EBADCFHGIKJ，中序序列為ABCDEFGHIJK，請畫出該二叉樹。 }答案：交換二叉樹結(jié)點左右子樹的遞歸算法寫出下面算法的功能。 t2=function(btright)。 if(bt==NULL) t=NULL。 if( hlhr ) return hl+1。 } }函數(shù)depth實現(xiàn)返回二叉樹的高度，請在空格處將算法補充完整。四、代碼填空題函數(shù)InOrderTraverse(Bitree bt)實現(xiàn)二叉樹的中序遍歷，請在空格處將算法補充完整。+1 。＋1。（ 對 ）對于任意非空二叉樹，要設(shè)計其后序遍歷的非遞歸算法而不使用堆棧結(jié)構(gòu)，最適合的方法是對該二叉樹采用三叉鏈表。A. 先序序列 B. 中序序列 C. 后序序列 D. 層序序列 2按照二叉樹的定義，具有3個結(jié)點的二叉樹有（ C ）種。 A. 15 B. 16 C. 17 D. 471在下列情況中，可稱為二叉樹的是（ C ）。A. tleft==NULL　 B. tltag==1 C. tltag==1amp。A. abcd+　 B. abc+*d C. abc*+d D. +*abcd1對某二叉樹進行先序遍歷的結(jié)果為ABDEFC，中序遍歷的結(jié)果為DBFEAC，則后序遍歷的結(jié)果是（ B ）。A. 能 B. 不能【解析：二叉樹的前序和中序遍歷序列可以唯一確定一顆二叉樹；二叉樹的中序和后序遍歷序列可以唯一確定一顆二叉樹；而二叉樹的前序和后序遍歷序列不能惟一確定一棵二叉樹】某二叉樹的中序序列為ABCDEFG，后序序列為BDCAFGE，則其左子樹中結(jié)點數(shù)目為（ C ）。A. R[2i1] B. R[2i+1] C. R[2i] D. R[2/i]設(shè)a,b為一棵二叉樹上的兩個結(jié)點，在中序遍歷時，a在b前面的條件是（ B ）。稀疏矩陣的壓縮存儲方式有： 三元組表 和 十字鏈表法 。（ 對 ）廣義表是一種多層次的數(shù)據(jù)結(jié)構(gòu)，其元素可以是單原子也可以是子表。A. 的 B. e C. (e) D. （e,f）二、判斷題（ 錯 ）廣義表中原子個數(shù)即為廣義表的長度。A. a B. (a) C. b D. ((a))1稀疏矩陣一般的壓縮存儲方法有兩種，即（ C ）。A. 建立和刪除 B. 索引和修改 C. 查找和修改 D. 查找與索引對一些特殊矩陣采用壓縮存儲的目的主要是為了（ D ）。A. 1175 B. 1180 C. 1205 D. 1210廣義表G=(a,b(c,d,(e,f)),g)的長度是（ A ）。A. 1和1 B. 1和3 C. 1和2 D. 2和3廣義表((a),a)的表尾是（ B ）。j=0。amp。 return s1lengths2length。is1lengthamp。 else return 1。j++。int index_bf(sqstring*s,sqstring *t,int start){ int i=start1,j=0。 } else j= next[j] 。 while(islenamp。答案：模式匹配 設(shè)s=’I︺AM︺A︺TEACHER’,其長度是 。N’二、判斷題（ 對 ）造成簡單模式匹配算法BF算法執(zhí)行效率低的原因是有回溯存在。 A. 通常以串整體作為操作對象 B. 需要更多的輔助空間 C. 算法的時間復(fù)雜度較高 D. 涉及移動的元素更多設(shè)SUBSTR(S,i,k)是求S中從第i個字符開始的連續(xù)k個字符組成的子串的操作，則對于S=’Beijingamp。A. 0123 B. 1123 C. 1231 D. 1211串與普通的線性表相比較，它的特殊性體現(xiàn)在（ C ）。 enQueue(Queue q, ElemType x)。 makeEmpty(SqStack s)。 判斷?？贞犃械腁DT函數(shù)有：void enQueue(Queue q,ElemType e)。棧的ADT函數(shù)有：void makeEmpty(SqStack s)。 rearnext=new。 New=(Lnode *)malloc(sizeof(Lnode))。 f2(Q)。寫出執(zhí)行算法f2后的隊列Q。 *e=Qbase[Qfront]。e)。N)。//入棧 int Pop(SqStack *S,ElemType *e)。錯以鏈表作為棧的存儲結(jié)構(gòu)，出棧操作必須判別棧空的情況。答案：n1設(shè)循環(huán)隊列的容量為70，現(xiàn)經(jīng)過一系列的入隊和出隊操作后，front為20，rear為11，則隊列中元素的個數(shù)為 。A. front=frontnext B. rear= rearnext C. rearnext=front D. frontnext=rear2隊和棧的主要區(qū)別是（ D ）。該緩沖區(qū)應(yīng)該是一個（ B ）結(jié)構(gòu)。】2隊列的刪除操作是在（ A ）。A. top不變 B. top=0 C. top=top+1 D. top=top11判斷一個循環(huán)隊列Q（空間大小為M）為空的條件是（ A ）。front=s。A. front=frontnext B. snext=rear。A. 隊列 B. 棧 C. 鏈表 D. 樹1棧的插入和刪除操作在（ B ）。*Stop=e。A. front==rear B. front==0 C. rear==0 D. front=rear+1一個順序棧S，其棧頂指針為top，則將元素e入棧的操作是（ A ）。A. 1243 B. 2134 C. 1432 D. 4312 E. 3214若用一個大小為6的數(shù)組來實現(xiàn)循環(huán)隊列，且當rear和front的值分別為0，3。A. a,b,c,d,e B. d,e,c,b,a C. d,c,e,a,b D. e,d,c,b,a判斷一個循環(huán)隊列Q（最多n個元素）為滿的條件是（ C ）。} while(j Blength) { Celem[k]= Belem[j]。 k++。 i++。 Clength= Alength+ Blength。typedef struct { ElemType *elem。p=qnext。 p=head。amp。 if(!headnext) return ERROR。 p=pnext。 }else{qnext=pnext。if(p==head){head=pnext。 q=p。試寫一算法，刪除表中所有大于x且小于y的元素（若表中存在這樣的元素）同時釋放被刪除結(jié)點空間。 if(j==k){ if(k!=i)Ldata[k]=Ldata[i]。jk amp。k=0。 }/*if*/ return head。 } else { s=(Link)malloc(sizeof(struct Linknode))。 if (!pointernext) { s=(Link)malloc(sizeof(struct Linknode))。 pointer= head。 Link pointer,s。 struct Linknode *next 。va[i]=x。while(xva[i]) i++。答案：void Insert_sq(Sqlist va[], ElemType x) {int i, j, n。Adata[Alength ++]=pdata。閱讀以下程序段，并回答問題：（1）寫出執(zhí)行下列程序段后的順序表A中的數(shù)據(jù)元素；（2）簡要敘述該程序段的功能。while(pnext!=NULL)p=pnext。 } }編寫算法,將一個頭指針為head不帶頭結(jié)點的單鏈表改造為一個單向循環(huán)鏈表，并分析算法的時間復(fù)雜度。 p=pnext。 p=r。 while(q){r=q。答案：void assending(Lnode *head) {Lnode *p,*q , *r, *s。while(qnext!=L2)q=qnext。 Lelem [Llength i1]=t。 for(i=0。 int length。 p=q。 pnext =NULL。答案：void invent(Lnode *head) {Lnode *p,*q,*r。 while(p!=NULL) { p=pnext。int L(head){ node * head。 *s=qdata。j++。j=0。}答案：（1）Lslist[k+1] （2） LLength 函數(shù)實現(xiàn)單鏈表的刪除算法，請在空格處將算法補充完整。kLlength1。}/*ListInsert*/答案：(1)snext=pnext (2)pnext=s函數(shù)ListDelete_sq實現(xiàn)順序表刪除算法，請在空格處將算法補充完整。 sdata=e。(ji1