川大數(shù)據(jù)結構與算法模擬試卷五、六及

模擬試卷五一、單選題（每題2分，共20分）1.棧和隊列的共同特點是()。A.只允許在端點處插入和刪除元素B.都是先進后出C.都是先進先出D.沒有共同點2.用鏈接方式存儲的隊列，在進行插入運算時().A.僅修改頭指針C.僅修改尾指針B.頭、尾指針都要修改D.頭、尾指針可能都要修改3.以下數(shù)據(jù)結構中哪一個是非線性結構？()A.隊列B.棧C.線性表D.二叉樹4.設有一個二維數(shù)組A[m][n]，假設A[0][0]存放位置在644(10)，A[2][2]存放位置在676(10)一個空間，問A[3][3](10)存放在什么位置？腳注(10)表示用10進制表示。，每個元素占A．688B．678C．692)。D．6965.樹最適合用來表示(A.有序數(shù)據(jù)元素B.無序數(shù)據(jù)元素C.元素之間具有分支層次關系的數(shù)據(jù)D.元素之間無聯(lián)系的數(shù)據(jù)6.二叉樹的第k層的結點數(shù)最多為().A．2k-1B.2K+1C.2K-1D.2k-17.若有18個元素的有序表存放在一維數(shù)組A[19]中，第一個元素放A[1]中，現(xiàn)進行二分查找，則查找A［3］的比較序列的下標依次為()A.1，2，3C.9，5，3B.9，5，2，3D.9，4，2，38.對n個記錄的文件進行快速排序，所需要的輔助存儲空間大致為A.O（1）B.O（n）C.O（1og2n）D.O（n2）9.對于線性表（7，34，55，25，64，46，20，10）進行散列存儲時，若選用H（K）=K%9作為散列函數(shù)，則散列地址為1的元素有（）個，A．1B．2C．3D．410.設有6個結點的無向圖，該圖至少應有()條邊才能確保是一個連通圖。A.5B.6C.7D.8二、填空題（每空1分，共26分）1.通常從四個方面評價算法的質(zhì)量：_________、_________、_________和_________。2.一個算法的時間復雜度為(n3+n2log2n+14n)/n2，其數(shù)量級表示為________。3.假定一棵樹的廣義表表示為A（C，D（E，F(xiàn)，G），H（I，J）），則樹中所含的結點數(shù)為__________個，樹的深度為___________，樹的度為_________。4.后綴算式923+-102/-的值為__________。中綴算式（3+4X）-2Y/3對應的后綴算式為_______________________________。5.若用鏈表存儲一棵二叉樹時，每個結點除數(shù)據(jù)域外，還有指向左孩子和右孩子的兩個指針。在這種存儲結構中，n個結點的二叉樹共有________個指針域，其中有________個指針域是存放了地址，有________________個指針是空指針。6.對于一個具有n個頂點和e條邊的有向圖和無向圖，在其對應的鄰接表中，所含邊結點分別有_______個和________個。7.AOV網(wǎng)是一種___________________的圖。8.在一個具有n個頂點的無向完全圖中，包含有________條邊，在一個具有n個頂點的有向完全圖中，包含有________條邊。9.假定一個線性表為(12,23,74,55,63,40)，若按Key%4條件進行劃分，使得同一余數(shù)的元素成為一個子表，則得到的四個子表分別為____________________________、___________________、_______________________和__________________________。10.向一棵B_樹插入元素的過程中，若最終引起樹根結點的分裂，則新樹比原樹的高度___________。11.在堆排序的過程中，對任一分支結點進行篩運算的時間復雜度為________，整個堆排序過程的時間復雜度為________。12.在快速排序、堆排序、歸并排序中，_________排序是穩(wěn)定的。三、運算題（每題6分，共24分）1.在如下數(shù)組A中鏈接存儲了一個線性表，表頭指針為A[0].next，試寫出該線性表。A01234567datanext60550778290034440132.請畫出圖10的鄰接矩陣和鄰接表。3.已知一個圖的頂點集V和邊集E分別為：V={1,2,3,4,5,6,7};E={(1,2)3,(1,3)5,(1,4)8,(2,5)10,(2,3)6,(3,4)15,(3,5)12,(3,6)9,(4,6)4,(4,7)20,(5,6)18,(6,7)25};用克魯斯卡爾算法得到最小生成樹，試寫出在最小生成樹中依次得到的各條邊。4.畫出向小根堆中加入數(shù)據(jù)4,2,5,8,3時，每加入一個數(shù)據(jù)后堆的變化。四、閱讀算法（每題7分，共14分）1.LinkListmynote(LinkListL){//L是不帶頭結點的單鏈表的頭指針if(L&&L->next){q=L；L=L－>next；p=L；S1：S2：}while(p－>next)p=p－>next；p－>next=q；q－>next=NULL；returnL；}請回答下列問題：（1）說明語句S1的功能；（2）說明語句組S2的功能；（3）設鏈表表示的線性表為（a1,a2,…,an）,寫出算法執(zhí)行后的返回值所表示的線性表。2.voidABC(BTNode*BT){ifBT{ABC(BT->left);ABC(BT->right);cout<<BT->data<<'';}}該算法的功能是：五、算法填空（共8分）二叉搜索樹的查找——遞歸算法:boolFind(BTreeNode*BST,ElemType&item){if(BST==NULL)returnfalse;//查找失敗else{if(item==BST->data){item=BST->data;//查找成功return___________;}elseif(item<BST->data)returnFind(______________,item);elsereturnFind(_______________,item);}//if}六、編寫算法（共8分）統(tǒng)計出單鏈表HL中結點的值等于給定值X的結點數(shù)。intCountX(LNode*HL,ElemTypex)模擬試卷五參考答案一、單選題（每題2分，共20分）1.A2.D3.D4.C5.C6.D7.D8.C9.D10.A二、填空題（每空1分，共26分）1.正確性易讀性強壯性高效率2.O(n)3.9334.-134X*+2Y*3/-5.2nn-1n+16.e2e7.有向無回路8.n(n-1)/2n(n-1)9.（12，40）（）（74）（23,55，63）10.增加111.O(log2n)O(nlog2n)12.歸并三、運算題（每題6分，共24分）1.線性表為：（78，50，40，60，34，90）2.鄰接矩陣：鄰接表如圖11所示：圖113.用克魯斯卡爾算法得到的最小生成樹為：(1,2)3,(4,6)4,(1,3)5,(1,4)8,(2,5)10,(4,7)204.見圖122224445552444238823584圖12四、閱讀算法（每題7分，共14分）1.（1）查詢鏈表的尾結點（2）將第一個結點鏈接到鏈表的尾部，作為新的尾結點（3）返回的線性表為（a2,a3,…,an,a1）2.遞歸地后序遍歷鏈式存儲的二叉樹。五、算法填空（每空2分，共8分）trueBST->leftBST->right六、編寫算法（8分）intCountX(LNode*HL,ElemTypex){inti=0;LNode*p=HL;//i為計數(shù)器while(p!=NULL){if(P->data==x)i++;p=p->next;}//while,出循環(huán)時i中的值即為x結點個數(shù)returni;}//CountX模擬試卷六一、單項選擇題（在每小題的四個備選答案中，選出一個正確的答案，并將其號碼填在題干后的括號內(nèi)。每小題1分，共10分）1．下面程序段for(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）ABCDC）ACDBB）DCBAD）DABC3．當求鏈表的直接后繼與求直接前驅(qū)的時間復雜度都相同時，此鏈表應為（）。A）單鏈表B）雙向鏈表D）前面都不正確C）單向循環(huán)鏈表4．已知串s='BBABBABBA'，t='AB'，c='A'，執(zhí)行置換操作REPLACE(s,t,c)后，s應為（）。A）'BBABABA'C）'BBAAA'B）'BBAABA'D）'BBABABBA'5．對于下圖所示的二叉樹，后序遍歷結果序列為（）。A）A，B，C，D，E，F(xiàn)，G，HC）D，F(xiàn)，B，A，C，G，E，H6．下面AOE網(wǎng)中，關鍵路徑長度為（B）A，B，D，F(xiàn)，C，E，G，HD）H，F(xiàn)，D，B，G，E，C，A）。A）16C）10B）13D）97．用Dijkstra算法求從源點到其它各頂點的最短路徑的時間復雜度為（）。A）O(n)B）O(n2)C）O(n3)D）O(nlogn)8．在下列查找方法中，平均查找速度最快的是（）。A）順序查找C）分塊查找B）折半查找D）二叉排序樹查找9．哈希表的地址區(qū)間為0~17，哈希函數(shù)為H(K)=K%17。采用線性探測法處理沖突，并將關鍵字序列26，25，72，38，8，18，59依次存儲到哈希表中。則59存放在哈希表中的地址是()。A）8B）9C）10D）1110．快速排序算法的平均時間復雜度是（）。A）O(n)B）O(n2)D）O(log2n)C）O(nlog2n)二、填空題（每空1分，共15分）1．設有一個記錄r，設其類型為LNode，則r實際所占用的存儲空間的大小為()。2．一個算法的時間復雜度為(5n3-3nlog2n+7n-9)/(6n)，其數(shù)量級表示為()。3．如將n×n的對稱矩陣壓縮存儲于sa[k]中，則k等于（）。4．如一二維數(shù)組A[1..m，1..n]按行排列，設A[1,1]的相對位置為0，每個元素的大小為1，則任一元素A[i，j]的地址為()。5．線性表的順序存儲結構中存取元素的時間復雜度為是（6．隊列的插入操作在()進行，刪除操作在()進行。7．后綴表達式“45*32++”的值為（）。）。8．對于一棵具有n個結點的樹，此樹中所有結點的度數(shù)之和為（的結點數(shù)為n2，則它們之間的關系為（），設葉子結點數(shù)為n0，度為二）。9．在一個無向圖中，所有頂點的度數(shù)之和等于所有邊數(shù)的()倍。10．在一個具有n個頂點的無向完全圖中，包含有(含有()條弧。)條邊；在一個具有n個頂點的有向完全圖中，包11．每次從無序表中取一個最小或最大元素，把它們交換到有序表的一端，此種排序方法稱為()排序。12．一種抽象數(shù)據(jù)類型應包括數(shù)據(jù)和()兩大部分。三、判斷改錯題（判斷正誤，將正確的劃上“√”，錯誤的劃上“×”，每小題1分，共10分）1．從邏輯關系上講，數(shù)據(jù)結構主要分為兩大類：線性結構和非線性結構。（2．數(shù)組可看成線性結構的一種推廣，所以可對數(shù)組進行插入與刪除操作。（3．在刪除鏈表結點時，計算機能自動地將其后繼的各個結點向前移動。（）））4．利用棧求表達式的值時，設立操作數(shù)棧OPND，設OPND只有2個存儲單元，則表達式(A-B)*C+D將不會發(fā)生發(fā)生上溢現(xiàn)象。（）5．串是n個字母的有限序列（n>=0）。（）（6．n階下三角矩陣的非零元素的個數(shù)最多為。）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函數(shù)為H(key)=key%5，采用鏈地址法處理沖突，試構造哈希表。五、算法題（共25分）1．程序填空題(每空2分，共8分)下面程序的功能是二叉樹的中序遍歷的非遞歸算法，其中二叉樹的結點結構為(lchild,data,rchild)，棧的常用方法有：入棧Push，出棧Pop，判空StackEmpty；試將程序補充完整。template<classType>BiTreeNode*BiTree<Type>::GoFarLeft(BiTreeNode<Type>*T,Stack<BiTreeNode<Type>*>&S){if(!T)returnNULL;while(T->lchild){Push(S,T);T=;}returnT;}template<classType>voidBiTree<Type>::Inorder(BiTreeNode<Type>*T,void(*visit)(Type&e)){Stack<BiTreeNode<Type>*>&S;t=GoFarLeft(T,S);//找到最左下的結點while(t){visit(t->data);if(t->rchild)t=GoFarLeft(,S);elseif(!StackEmpty(S))t=;elset=;//?？毡砻鞅闅v結束}//while}//Inorder2．程序填空題(每空2分，共8分)下面程序的功能是用線性探測再散列處理沖突（即Hi=(H(key)+i)%m），哈希函數(shù)為H(key)=key%m，進行哈希表的插入算法。（如表中已存在關鍵字相同的記錄或無插入位置，則不進行插入），試將程序補充完整。typedefenum{SUCCESS,UNSUCCESS,OVERFLOW}Status;template<classType>typedefstruct{Type*elem;intm;}HashTable;template<classType>StatusSerchHashTable(HashTable<Type>H,Typee){inti=0,k=;//i為沖突的次數(shù),k為哈希函數(shù)的值while(i<m&&H.elem[k].key!=NULLKEY&&p->elem.key!=e.key){;p=(p+i)%m;}//whileif(i>=m)returnOVERFLOW;elseif(p->elem.key!=e.key)returnelse{;H.elem[p].elem=returnSUCCESS;}//if;}//SerchHashTable3．（9分）閱讀下面算法，試回答：（1）根據(jù)鄰接表畫出對應的圖；（2）當圖的鄰接表如下時，執(zhí)行算法T(g,1)時，輸出的結果是什么？（3）函數(shù)T的功能是什么？圖的鄰接表為：template<classType>voidAdjGraph<Type>::T(AdjGraph<Type>g;inti){ArcNode<Type>*p;cout<<g[i].vertex;Visited[i]=true;p=g[i].link;while(p){if(!Visited[p->adjvex])T(p->adjvex);p=p->next;}//while}//T六、寫算法（共20分）1．(12分)以單鏈表為存儲結構實現(xiàn)簡單選擇排序，排序的結果是單鏈表按關鍵字值升序排序，試編寫此算法。算法申明如下：template<classType>voidLinkList<Type>::SimpleSelectSort(Lnode<Type>*la)2．(8分)下面是一個二叉樹的中序遍歷的遞歸算法，試改寫此算法，消去第二個遞歸調(diào)用MidOrder(T->rchild,visit)。template<classType>voidBiTree<Type>::PreOrder(BiTreeNode<Type>*T,void(*Visit)(Type&e)){if(T){MidOrder(T->lchild,Visit);Visit(T->data);MidOrder(T->rchild,Visit);}//if}//MidOrder模擬試卷六參考答案_一、單項選擇題（在每小題的四個備選答案中，選出一個正確的答案，并將其號碼填在題干后的括號內(nèi)。每小題1分，共10分）1．B）6．A）2．D）7．B）3．B）8．B）4．A）9．D）5．D）10．C）二、填空題（每空1分，共15分）1．參考答案：sizeof(LNode)2．參考答案：O(n2)3．參考答案：4．參考答案：(i-1)*n+j-15．參考答案：O(1)6．參考答案：隊尾7．參考答案：258．參考答案：n-1隊頭n0=n2-19．參考答案：210．參考答案：n(n-1)/2n(n-1)11．參考答案：選擇（直接選擇排序或堆排序）12．參考答案：操作三、判斷改錯題（判斷正誤，將正確的劃上“√”，錯誤的劃上“×”，每小題1分，共10分）1．參考答案：√2．參考答案：×3．參考答案：×4．參考答案：√5．參考答案：×6．參考答案：√7．參考答案：×8．參考答案：×9．參考答案：×10．參考答案：×四、簡答題（每小題4分，共20分）1．