【正文】 A．8 B．3 C．5 D．99．散列函數(shù)有一個(gè)。當(dāng)前表中已有4個(gè)結(jié)點(diǎn)：addr(15)=4，addr(38)=5，addr(61)=6，addr(84)=7。A．35/12 B．37/12 C．39/12 D．43/12 7．在有序表{1，3，9，12，32，41，62，75，77，82，95，100}上進(jìn)行折半查找關(guān)鍵字為82的數(shù)據(jù)元素需要比較（C）次。A．O(log２n2) B．O(nlog２n) C．O(n) D．O(log２n)5．適用于折半查找的表的存儲方式及元素排列要求為（D）。A．n B．1 C．n+1 D．n13．順序查找適用于存儲結(jié)構(gòu)為（C）的線性表。 v1v3 v2v6v5v45．如圖4所示AOE網(wǎng)：（1）列出各事件的最早、最遲發(fā)生時(shí)間；（2）列出各活動的最早、最遲發(fā)生時(shí)間；（3）找出該AOE網(wǎng)中的關(guān)鍵路徑，并回答完成該工程需要的最短時(shí)間。4．設(shè)有向圖G如圖3所示，試畫出圖G的十字鏈表結(jié)構(gòu)，并寫出圖G的兩個(gè)拓?fù)湫蛄??！窘獯稹浚?）該圖的鄰接矩陣：0 1 1 0 0 0 01 0 1 0 0 0 01 0 0 1 0 0 00 1 1 0 1 1 00 0 0 1 0 0 10 0 0 1 0 0 10 0 0 0 1 1 0（2）該圖的鄰接表：0v10 2 ^3245 ^36 ^12 ^0 2 ^36 ^4 5 ^1v22v33v44v55v66v7（3）該圖的多重鄰接表：v1v2v3v4v5v6v7010 ^2 31 ^32 ^343 ^564 ^6 ^5 ^ （4）從v1出發(fā)的“深度優(yōu)先”遍歷序列：v1v2v4v3v5v7v6（5）從v1出發(fā)的“廣度優(yōu)先”遍歷序列：v1v2v3v4v5v6v73．用鄰接矩陣表示圖時(shí)，矩陣元素的個(gè)數(shù)與頂點(diǎn)個(gè)數(shù)是否相關(guān)？與邊的條數(shù)是否有關(guān)？【解答】設(shè)圖的頂點(diǎn)個(gè)數(shù)為n(n≥0)，則鄰接矩陣元素個(gè)數(shù)為n2，即頂點(diǎn)個(gè)數(shù)的平方。 【解答】（1）每個(gè)頂點(diǎn)的入度和出度：頂點(diǎn)1（2，1）、頂點(diǎn)2（2，2）、頂點(diǎn)3（1，3）、頂點(diǎn)4（3，0）、頂點(diǎn)5（2，3）、頂點(diǎn)6（1，2）。（）15．AOE網(wǎng)中一定只有一條關(guān)鍵路徑。（√）13．用鄰接矩陣A表示圖，判定任意兩個(gè)結(jié)點(diǎn)vi和vj之間是否有長度為m的路徑相連，則只要檢查Am的第i行第j列的元素是否為0即可。（√）11．連通分量是無向圖中的極小連通子圖。（）9．任何無向圖都存在生成樹。（√）7．存儲無向圖的鄰接矩陣是對稱的，故只存儲鄰接矩陣的下(或上)三角部分即可。（）5．任何有向網(wǎng)絡(luò)（AOV網(wǎng)絡(luò)）拓?fù)渑判虻慕Y(jié)果是唯一的。（√）3．用鄰接矩陣法存儲一個(gè)圖時(shí)，在不考慮壓縮存儲的情況下，所占用的存儲空間大小只與圖中結(jié)點(diǎn)個(gè)數(shù)有關(guān)，而與圖的邊數(shù)無關(guān)。A．8 B．9 C．10 D．11 判斷題1．求最小生成樹的Prim算法在邊較少、結(jié)點(diǎn)較多時(shí)效率較高。A．從源點(diǎn)到匯點(diǎn)的最長路徑 B．從源點(diǎn)到匯點(diǎn)的最短路徑 C．最長的回路 D．最短的回路9．下面關(guān)于求關(guān)鍵路徑的說法不正確的是（C）。A．O (nlog2e) B．O (en ) C．O ( elog2n) D．O (n+e)7．含有n個(gè)頂點(diǎn)e條邊的無向連通圖，利用Kruskal算法生成最小生成樹，其時(shí)間復(fù)雜度為（A）。A．v0, v3, v2, v1 B．v0, v1, v2, v3 C．v0, v2, v1, v3 D．v0, v1, v3, v2（2）從頂點(diǎn)V0出發(fā)進(jìn)行廣度優(yōu)先搜索，經(jīng)歷的結(jié)點(diǎn)順序?yàn)椋―）。A．有向圖 B．無向圖 C．AOV網(wǎng) D．AOE網(wǎng)4．最短路徑的生成算法可用（C）。A．n B．2n C．n/2 D．n*n2．n條邊的無向圖的鄰接多重表的存儲中，邊結(jié)點(diǎn)的個(gè)數(shù)有（A）。 } return(maxh) 。 h++。 h=1。i++) { if (t[i].parent==1 ) h=1。 for (i=0 ?！咎崾尽繌拿恳粋€(gè)結(jié)點(diǎn)開始，從下向上搜索至根結(jié)點(diǎn)，記錄結(jié)點(diǎn)的層次數(shù)，其中的最大值就是樹的深度。} return(max+1)。 if(hmax) max=h。p=pnextchild。 /*若根結(jié)點(diǎn)沒有子樹*/else { p=t[i].firstchild?！咎崾尽坎捎眠f歸算法實(shí)現(xiàn)。 /*h2為t的兄弟子樹的深度*/ return(max(h1+1,h2))。 /*若樹為空，返回0*/else { h1=high (tlchild )?！咎崾尽坎捎眠f歸算法實(shí)現(xiàn)。 p=q。 rrchild= rlchild。else { rtag=0。 r=q。 rlchild=p。} /*從右子樹回來*/else { rtag=0。 p=r。ttag==0) { q=rrchild。rrchild==NULL)) { if(ramp。ttag==1amp。ttag==0) || (ramp。 } else { /*上升*/whle((ramp。 r=p。 } else if(prchild) /*下降進(jìn)入右子樹*/{ q=prchild。 r=p。 q=plchild。 r= NULL: while( p) { Visit(p)。 /*p指向當(dāng)前結(jié)點(diǎn)，r指向p的雙親，q指向要訪問的下一結(jié)點(diǎn)*/if(bt==NULL) return。} Bnode, *Btree。 int tag?！咎崾尽坑媚孓D(zhuǎn)鏈的方法遍歷二叉樹，不需要附加的?？臻g，而是在遍歷過程中沿結(jié)點(diǎn)的左右子樹下降時(shí)，臨時(shí)改變結(jié)點(diǎn)lchild或者rchild的值，使之指向雙親，從而為以后的上升提供路徑，上升時(shí)再將結(jié)點(diǎn)的lchild或者rchild恢復(fù)。amp。 !t) return (0)。 t || s amp。else if(!s amp。amp?！咎崾尽績煽每斩鏄浠騼H有根結(jié)點(diǎn)的二叉樹相似；對非空二叉樹，可判左右子樹是否相似，采用遞歸算法。 }11．編寫算法判定兩棵二叉樹是否相似。else Trchild=Create(A,2*i+1)。else Tlchild=Create(A,2*i)。Tdata=A[i]。BiTree Create(dataype A[],int i)/*n個(gè)結(jié)點(diǎn)的完全二叉樹存于一維數(shù)組A中，據(jù)此建立以二叉鏈表表示的完全二叉樹,初始調(diào)用時(shí),i=1*/{ BiTree T。 /*右孩子入隊(duì)列*/}} return(CM)。 /*左孩子入隊(duì)列*/if(prchild==NULL) B=0。 /*CM=0表示不是完全二叉樹*/} else {CM=B。 if(plchild==NULL) { B=0。 if (T!=NULL) { In_Queue(Q,T)。 /*初始化隊(duì)列Q*/ B=1。這里增加一個(gè)標(biāo)志以表示所有已掃描過的結(jié)點(diǎn)均有左、右孩子，將局部判斷結(jié)果存入CM中，CM表示整個(gè)二叉樹是否是完全二叉樹，B為1表示到目前為止所有結(jié)點(diǎn)均有左右孩子?！咎崾尽扛鶕?jù)完全二叉樹的定義可知，對完全二叉樹按照從上到下，從左到右的次序遍歷應(yīng)滿足：①若某結(jié)點(diǎn)沒有左孩子，則一定無右孩子；②若某結(jié)點(diǎn)缺（左或右）孩子，則其所有后繼一定無孩子。 else InPost (in,post,m+1,ir,prir+m,pr1,trchild)。 else InPost ( in, post,il,m1,pl,pl+m1il, tlchild)。 while (in[m]!=post [pr] ) m++。 tdata=post[pr]?！咎崾尽扛鶕?jù)后序遍歷和中序遍歷的特點(diǎn)，采用遞歸算法實(shí)現(xiàn)。 } else return。 } if(!Empty_Stack(S)){ Pop_Stack(S,r)。} else{ Push_Stack(S,p)。 printf(qdata)。 /*初始化空棧*/ p=T。當(dāng)找到值為x的結(jié)點(diǎn)時(shí)，棧中存放的就是其祖先結(jié)點(diǎn)，依次打印各結(jié)點(diǎn)的值。【提示】對二叉樹進(jìn)行先序非遞歸遍歷，查找值為x的結(jié)點(diǎn)。 t=t*2+1。 else { top。 t=t*2。 stack[top]=t。amp。 top=0。 if(n1) return。void PreOrder (datatype data[n+1]) /*0號單元未用*/ { int stack[n] 。對順序存儲結(jié)構(gòu)的二叉樹進(jìn)行先序遍歷，與二叉鏈表存放二叉樹的遍歷策略類似。}}6．一棵具有n個(gè)結(jié)點(diǎn)的完全二叉樹采用順序結(jié)構(gòu)存儲，試設(shè)計(jì)非遞歸算法對其進(jìn)行先序遍歷。 rootlchild=rootrchild。Exchange(rootrchild)。void Exchange(BiTree root) { BiTNode *p。 }}5．給定一棵用二叉鏈表表示的二叉樹，其根指針為root，試寫出將二叉樹中所有結(jié)點(diǎn)的左、右子樹相互交換的算法。fun(rootlchild,n+1)。二叉樹結(jié)點(diǎn)的層次數(shù)＝1 當(dāng)結(jié)點(diǎn)為根結(jié)點(diǎn)其雙親結(jié)點(diǎn)的層次數(shù)＋1 當(dāng)結(jié)點(diǎn)非根結(jié)點(diǎn)void fun (BiTree root, int n){ if (t==NULL) return。} }4．給定一棵用二叉鏈表表示的二叉樹，其根指針為root，試求二叉樹各結(jié)點(diǎn)的層數(shù)。if (hlhr) return (hl+1)。else { hl=Height(rootlchild)。int Height(BiTree root) { int hl,hr。 }3．給定一棵用二叉鏈表表示的二叉樹，其根指針為root，試寫出求二叉樹的深度的算法。 /*中序遍歷右子樹*/prerchild=NULL。 pre=T。 pre=T。amp。 /*全局變量*/LinkList InOrder(BiTree T) /*中序遍歷二叉樹T，將葉子結(jié)點(diǎn)從左到右鏈成一個(gè)單鏈表，表頭指針為head*/{ if(T) { InOrder(Tlchild)。第一個(gè)葉子結(jié)點(diǎn)由指針head指向，遍歷到葉子結(jié)點(diǎn)時(shí)，就將它前驅(qū)的rchild指針指向它，最后葉子結(jié)點(diǎn)的rchild為空。這里使用中序遞歸遍歷。【提示】這是一個(gè)非常典型的基于二叉樹遍歷算法，通過遍歷找到各個(gè)葉子結(jié)點(diǎn)，因?yàn)椴徽撉靶虮闅v、中序遍歷和后序遍歷，訪問葉子結(jié)點(diǎn)的相對順序都是相同的，即都是從左至右。 }2．請?jiān)O(shè)計(jì)一個(gè)算法，要求該算法把二叉樹的葉結(jié)點(diǎn)按從左至右的順序鏈成一個(gè)單鏈表。二叉樹結(jié)點(diǎn)的數(shù)目＝0 當(dāng)二叉樹為空左子樹結(jié)點(diǎn)數(shù)目＋右子樹結(jié)點(diǎn)數(shù)目＋1 當(dāng)二叉樹非空int count(BiTree root){ if (root==NULL) return (0)。等長編碼的平均長度：*3+*3+*3+*3+*3+*3+*3=3哈夫曼編碼：*2+*3+*3+*4+*3+*2+*4=哈夫曼編碼比等長編碼使電文總長壓縮了：1 算法設(shè)計(jì)題1．給定一棵用二叉鏈表表示的二叉樹，其根指針為root，試寫出求二叉樹結(jié)點(diǎn)的數(shù)目的算法。它們在電文中出現(xiàn)的頻度分別為{,},（1）為這7個(gè)字母設(shè)計(jì)哈夫曼編碼。層次序列的特點(diǎn)是：從左到右每個(gè)結(jié)點(diǎn)或是當(dāng)前情況下子樹的根或是葉子。若左子樹不空，層次序列中第二個(gè)結(jié)點(diǎn)左子樹的根；若左子樹為空，則層次序列中第二個(gè)結(jié)點(diǎn)右子樹的根。ABDGCEFHIKJL