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