【正文】 i=1。i=n。i++) for(j=1。j=i。j++) x=x+1。的時(shí)間復(fù)雜度為（ ）。A）O(n) B）O(n2) C）O(n*i) D）O(n+i)2．設(shè)一個(gè)棧的入棧序列是ABCD，則借助于一個(gè)棧所得到的出棧序列不可能是（ ）。A）ABCD B）DCBA C）ACDB D）DABC3．當(dāng)求鏈表的直接后繼與求直接前驅(qū)的時(shí)間復(fù)雜度都相同時(shí)，此鏈表應(yīng)為（ ）。A）單鏈表 B）雙向鏈表 C）單向循環(huán)鏈表 D）前面都不正確4．已知串s=39。BBABBABBA39。，t=39。AB39。，c=39。A39。，執(zhí)行置換操作REPLACE(s,t,c)后，s應(yīng)為（ ）。A）39。BBABABA39。 B）39。BBAABA39。C）39。BBAAA39。 D）39。BBABABBA39。5．對(duì)于下圖所示的二叉樹(shù)，后序遍歷結(jié)果序列為（ ）。A）A，B，C，D，E，F(xiàn)，G，H B）A，B，D，F(xiàn)，C，E，G，HC）D，F(xiàn)，B，A，C，G，E，H D）H，F(xiàn)，D，B，G，E，C，A6．下面AOE網(wǎng)中，關(guān)鍵路徑長(zhǎng)度為（ ）。A）16 B）13 C）10 D）97．用Dijkstra算法求從源點(diǎn)到其它各頂點(diǎn)的最短路徑的時(shí)間復(fù)雜度為（ ）。A）O(n) B）O(n2) C）O(n3) D）O(nlogn)8．在下列查找方法中，平均查找速度最快的是（ ）。A）順序查找 B）折半查找 C）分塊查找 D）二叉排序樹(shù)查找9．哈希表的地址區(qū)間為0~17，哈希函數(shù)為H(K)=K % 17。采用線性探測(cè)法處理沖突，并將關(guān)鍵字序列26，25，72，38，8，18，59依次存儲(chǔ)到哈希表中。則59存放在哈希表中的地址是( )。A）8 B）9 C）10 D）1110．快速排序算法的平均時(shí)間復(fù)雜度是（ ）。A）O(n) B）O(n2) C）O(nlog2n) D）O(log2n)二、填空題（每空1分，共15分）1．設(shè)有一個(gè)記錄r，設(shè)其類型為L(zhǎng)Node，則r實(shí)際所占用的存儲(chǔ)空間的大小為( )。2．一個(gè)算法的時(shí)間復(fù)雜度為(5n33nlog2n+7n9)/(6n)，其數(shù)量級(jí)表示為( )。3．如將nn的對(duì)稱矩陣壓縮存儲(chǔ)于sa[k]中，則k等于（ ）。4．如一二維數(shù)組A[1..m，1..n]按行排列，設(shè)A[1,1]的相對(duì)位置為0，每個(gè)元素的大小為1，則任一元素A[i，j]的地址為( )。5．線性表的順序存儲(chǔ)結(jié)構(gòu)中存取元素的時(shí)間復(fù)雜度為是（ ）。6．隊(duì)列的插入操作在( )進(jìn)行，刪除操作在( )進(jìn)行。7．后綴表達(dá)式“4 5 * 3 2 + +”的值為（ ）。8．對(duì)于一棵具有n個(gè)結(jié)點(diǎn)的樹(shù)，此樹(shù)中所有結(jié)點(diǎn)的度數(shù)之和為（ ），設(shè)葉子結(jié)點(diǎn)數(shù)為n0，度為二的結(jié)點(diǎn)數(shù)為n2，則它們之間的關(guān)系為（ ）。9．在一個(gè)無(wú)向圖中，所有頂點(diǎn)的度數(shù)之和等于所有邊數(shù)的( )倍。10．在一個(gè)具有n個(gè)頂點(diǎn)的無(wú)向完全圖中，包含有( )條邊；在一個(gè)具有n個(gè)頂點(diǎn)的有向完全圖中，包含有( )條弧。11．每次從無(wú)序表中取一個(gè)最小或最大元素，把它們交換到有序表的一端，此種排序方法稱為( )排序。12．一種抽象數(shù)據(jù)類型應(yīng)包括數(shù)據(jù)和( )兩大部分。三、判斷改錯(cuò)題（判斷正誤，將正確的劃上“√”，錯(cuò)誤的劃上“”，每小題1分，共10分）1．從邏輯關(guān)系上講，數(shù)據(jù)結(jié)構(gòu)主要分為兩大類：線性結(jié)構(gòu)和非線性結(jié)構(gòu)。 （ ）2．?dāng)?shù)組可看成線性結(jié)構(gòu)的一種推廣，所以可對(duì)數(shù)組進(jìn)行插入與刪除操作。 （ ）3．在刪除鏈表結(jié)點(diǎn)時(shí)，計(jì)算機(jī)能自動(dòng)地將其后繼的各個(gè)結(jié)點(diǎn)向前移動(dòng)。 （ ）4．利用棧求表達(dá)式的值時(shí)，設(shè)立操作數(shù)棧OPND，設(shè)OPND只有2個(gè)存儲(chǔ)單元，則表達(dá)式(AB)*C+D將不會(huì)發(fā)生發(fā)生上溢現(xiàn)象。 （ ）5．串是n個(gè)字母的有限序列（n=0）。 （ ）6．n階下三角矩陣的非零元素的個(gè)數(shù)最多為。 （ ）7．二叉樹(shù)只能采用二叉鏈表來(lái)存儲(chǔ)。 （ ）8．圖G的某一最小生成樹(shù)的代價(jià)一定小于其它生成樹(shù)的代價(jià)。 （ ）9．B+樹(shù)是一種特殊的二叉樹(shù)。 （ ）10．所有的簡(jiǎn)單排序（即時(shí)間復(fù)雜度為O(n2)的排序）都是穩(wěn)定排序。 （ ）四、簡(jiǎn)答題（每小題4分，共20分）1．對(duì)于下列雙向鏈表，設(shè)結(jié)構(gòu)為(prior,data,next)，結(jié)點(diǎn)類型為lnode，試寫(xiě)出在p所指結(jié)點(diǎn)之前插入元素x的語(yǔ)句序列。2．對(duì)于下圖，用Prim算法從結(jié)點(diǎn)1出發(fā)構(gòu)造出一棵最小生成樹(shù)，要求圖示出每一步的變化情況。3．已知一棵二叉樹(shù)的先序序列與中序序列分別如下，試畫(huà)出此二叉樹(shù)。先序序列：ABCDEFGHIJ中序序列：CBEDAGHFJI4．給定一組權(quán)值{3，4，7，14，15，20}，試畫(huà)出相應(yīng)的哈夫曼樹(shù)，并計(jì)算帶樹(shù)路徑長(zhǎng)度WPL的值。5．有關(guān)鍵字序列{7,23,6,9,17,19,21,22,5}，Hash函數(shù)為H(key)=key % 5，采用鏈地址法處理沖突，試構(gòu)造哈希表。五、算法題（共25分）1．程序填空題(每空2分，共8分)下面程序的功能是二叉樹(shù)的中序遍歷的非遞歸算法，其中二叉樹(shù)的結(jié)點(diǎn)結(jié)構(gòu)為(lchild,data,rchild)，棧的常用方法有：入棧Push，出棧Pop，判空StackEmpty；試將程序補(bǔ)充完整。templateclass TypeBiTreeNode *BiTreeType::GoFarLeft(BiTreeNodeType *T, Stack BiTreeNodeType *amp。 S){ if (!T ) return NULL。 while (Tlchild ){ Push(S, T)。 T = 。 } return T。}templateclass Typevoid BiTreeType::Inorder(BiTreeNodeType *T, void (*visit)(Type amp。 e)){ Stack BiTreeNodeType *amp。 S。 t = GoFarLeft(T, S)。 // 找到最左下的結(jié)點(diǎn) while(t){ visit(tdata)。 if (trchild) t = GoFarLeft( , S)。 else if ( !StackEmpty(S )) t = 。 else t = 。 // ?？毡砻鞅闅v結(jié)束 } // while}// Inorder 2．程序填空題(每空2分，共8分)下面程序的功能是用線性探測(cè)再散列處理沖突（即Hi=(H(key)+i)%m），哈希函數(shù)為H(key)=key % m，進(jìn)行哈希表的插入算法。（如表中已存在關(guān)鍵字相同的記錄或無(wú)插入位置，則不進(jìn)行插入），試將程序補(bǔ)充完整。typedef enum{SUCCESS,UNSUCCESS,OVERFLOW}Status。templateclass Typetypedef struct{ Type *elem。 int m。}HashTable。templateclass TypeStatus SerchHashTable(HashTableType H,Type e){ int i=0,k= 。 // i為沖突的次數(shù),k為哈希函數(shù)的值 while(im amp。amp。 [k].key!=NULLKEY amp。amp。 p!=){ 。 p=(p+i)%m。 }//while if(i=m)return OVERFLOW。 else if(p!=)return 。 else{ [p].elem= 。 return SUCCESS。 }//if} //SerchHashTable3．（9分）閱讀下面算法，試回答：（1） 根據(jù)鄰接表畫(huà)出對(duì)應(yīng)的圖； （2）當(dāng)圖的鄰接表如下時(shí)，執(zhí)行算法T(g,1)時(shí)，輸出的結(jié)果是什么？（3）函數(shù)T的功能是什么？圖的鄰接表為：templateclass Typevoid AdjGraphType::T(AdjGraphType g。int i){ ArcNodeType *p。 coutg[i].vertex。 Visited[i]=true。 p=g[i].link。 while(p){ if(!Visited[padjvex]) T(padjvex)。 p=pnext。 }//while}//T六、寫(xiě)算法（共20分）1．(12分)以單鏈表為存儲(chǔ)結(jié)構(gòu)實(shí)現(xiàn)簡(jiǎn)單選擇排序，排序的結(jié)果是單鏈表按關(guān)鍵字值升序排序，試編寫(xiě)此算法。算法申明如下：templateclass Typevoid LinkListType:: SimpleSelectSort (LnodeType *la)2．(8分)下面是一個(gè)二叉樹(shù)的中序遍歷的遞歸算法，試改寫(xiě)此算法，消去第二個(gè)遞歸調(diào)用MidOrder(Trchild,visit)。templateclass Typevoid BiTreeType::PreOrder(BiTreeNodeType *T, void (*Visit)(Typeamp。 e)){ if(T){ MidOrder(Tlchild, Visit)。 Visit(Tdata)。 MidOrder(Trchild, Visit)。 }//if}//MidOrder 模擬試卷六參考答案_一、單項(xiàng)選擇題（在每小題的四個(gè)備選答案中，選出一個(gè)正確的答案，并將其號(hào)碼填在題干后的括號(hào)內(nèi)。每小題1分，共10分）1．B） 2．D） 3．B） 4．A） 5．D）6．A） 7．B） 8．B） 9．D） 10．C）二、填空題（每空1分，共15分）1．參考答案：sizeof(LNode)2．參考答案：O(n2)3．參考答案：4．參考答案：(i1)*n+j15．參考答案：O(1)6．參考答案：隊(duì)尾 隊(duì)頭7．參考答案：258．參考答案：n1 n0= n219．參考答案：210．參考答案：n(n1)/2 n(n1)11．參考答案：選擇（直接選擇排序或堆排序）12．參考答案：操作三、判斷改錯(cuò)題（判斷正誤，將正確的劃上“√”，錯(cuò)誤的劃上“”，每小題1分，共10分）1．參考答案：√2．參考答案：3．參考答案：4．參考答案：√5．參考答案：6．參考答案：√7．參考答案：8．參考答案：9．參考答案：10．參考答案：四、簡(jiǎn)答題（每小題4分，共20分）1．參考答案： s=new lnode。 sdata=x。 ppriornext=s。 sprior=pprior。 snext=p。 pprior=s。2．參考答案：本題用Prim算法構(gòu)造出最小生成樹(shù)共需四步，具每一步的變化情況如如：3．參考答案：4．參考答案：哈夫曼樹(shù)如下圖所示：WPL=20*2+15*2+14*2+7*3+3*4+4*4=1475．參考答案：哈希表如下圖所示：五、算法題（共25分）1．參考答案：Tlchild trchild Pop(S) NULL2．參考答案： % m ++i UNSUCCESS e3．(1)參考答案：（2）參考答案：V1 V2 V4 V3（3）參考答案：從頂點(diǎn)Vi出發(fā)進(jìn)行深度優(yōu)先搜索圖。六、寫(xiě)算法（共20分）1．參考答案：templateclass Typevoid LinkListType:: SimpleSelectSort (LnodeType *la) //用單鏈表為存儲(chǔ)結(jié)構(gòu)實(shí)現(xiàn)選擇排序 LnodeType *p,q。 Type x。 if(lanext){ p=lanext。 while(pnext){ minp=p。 q=pnext。 while(q){ if(mi