數(shù)據(jù)結(jié)構(gòu)與算法模擬試卷五、六與參考答案

..模擬試卷五單選題〔每題2分,共20分棧和隊(duì)列的共同特點(diǎn)是<>。A.只允許在端點(diǎn)處插入和刪除元素B.都是先進(jìn)后出C.都是先進(jìn)先出D.沒有共同點(diǎn)用鏈接方式存儲(chǔ)的隊(duì)列,在進(jìn)行插入運(yùn)算時(shí)<>.A.僅修改頭指針B.頭、尾指針都要修改C.僅修改尾指針D.頭、尾指針可能都要修改以下數(shù)據(jù)結(jié)構(gòu)中哪一個(gè)是非線性結(jié)構(gòu)？<>A.隊(duì)列B.棧C.線性表D.二叉樹設(shè)有一個(gè)二維數(shù)組A[m][n],假設(shè)A[0][0]存放位置在644<10>,A[2][2]存放位置在676<10>,每個(gè)元素占一個(gè)空間,問A[3][3]<10>存放在什么位置？腳注<10>表示用10進(jìn)制表示。A．688B．678C．692D．696樹最適合用來表示<>。A.有序數(shù)據(jù)元素B.無序數(shù)據(jù)元素C.元素之間具有分支層次關(guān)系的數(shù)據(jù)D.元素之間無聯(lián)系的數(shù)據(jù)二叉樹的第k層的結(jié)點(diǎn)數(shù)最多為<>.A．2k-1B.2K+1C.2K-1D.2k-1若有18個(gè)元素的有序表存放在一維數(shù)組A[19]中,第一個(gè)元素放A[1]中,現(xiàn)進(jìn)行二分查找,則查找A［3］的比較序列的下標(biāo)依次為<>A.1,2,3 B.9,5,2,3C.9,5,3 D.9,4,2,3對(duì)n個(gè)記錄的文件進(jìn)行快速排序,所需要的輔助存儲(chǔ)空間大致為A.O〔1B.O〔nC.O〔1og2nD.O〔n2對(duì)于線性表〔7,34,55,25,64,46,20,10進(jìn)行散列存儲(chǔ)時(shí),若選用H〔K=K%9作為散列函數(shù),則散列地址為1的元素有〔個(gè),A．1B．2C．3D．4設(shè)有6個(gè)結(jié)點(diǎn)的無向圖,該圖至少應(yīng)有<>條邊才能確保是一個(gè)連通圖。A.5B.6C.7D.8填空題〔每空1分,共26分通常從四個(gè)方面評(píng)價(jià)算法的質(zhì)量：_________、_________、_________和_________。一個(gè)算法的時(shí)間復(fù)雜度為<n3+n2log2n+14n>/n2,其數(shù)量級(jí)表示為________。假定一棵樹的廣義表表示為A〔C,D〔E,F,G,H〔I,J,則樹中所含的結(jié)點(diǎn)數(shù)為__________個(gè),樹的深度為___________,樹的度為_________。后綴算式923+-102/-的值為__________。中綴算式〔3+4X-2Y/3對(duì)應(yīng)的后綴算式為_______________________________。若用鏈表存儲(chǔ)一棵二叉樹時(shí),每個(gè)結(jié)點(diǎn)除數(shù)據(jù)域外,還有指向左孩子和右孩子的兩個(gè)指針。在這種存儲(chǔ)結(jié)構(gòu)中,n個(gè)結(jié)點(diǎn)的二叉樹共有________個(gè)指針域,其中有________個(gè)指針域是存放了地址,有________________個(gè)指針是空指針。對(duì)于一個(gè)具有n個(gè)頂點(diǎn)和e條邊的有向圖和無向圖,在其對(duì)應(yīng)的鄰接表中,所含邊結(jié)點(diǎn)分別有_______個(gè)和________個(gè)。AOV網(wǎng)是一種___________________的圖。在一個(gè)具有n個(gè)頂點(diǎn)的無向完全圖中,包含有________條邊,在一個(gè)具有n個(gè)頂點(diǎn)的有向完全圖中,包含有________條邊。假定一個(gè)線性表為<12,23,74,55,63,40>,若按Key%4條件進(jìn)行劃分,使得同一余數(shù)的元素成為一個(gè)子表,則得到的四個(gè)子表分別為____________________________、___________________、_______________________和__________________________。向一棵B_樹插入元素的過程中,若最終引起樹根結(jié)點(diǎn)的分裂,則新樹比原樹的高度___________。在堆排序的過程中,對(duì)任一分支結(jié)點(diǎn)進(jìn)行篩運(yùn)算的時(shí)間復(fù)雜度為________,整個(gè)堆排序過程的時(shí)間復(fù)雜度為________。在快速排序、堆排序、歸并排序中,_________排序是穩(wěn)定的。運(yùn)算題〔每題6分,共24分在如下數(shù)組A中鏈接存儲(chǔ)了一個(gè)線性表,表頭指針為A[0].next,試寫出該線性表。A01234567data605078903440next3572041圖10請(qǐng)畫出圖10的鄰接矩陣和鄰接表。圖10已知一個(gè)圖的頂點(diǎn)集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};用克魯斯卡爾算法得到最小生成樹,試寫出在最小生成樹中依次得到的各條邊。畫出向小根堆中加入數(shù)據(jù)4,2,5,8,3時(shí),每加入一個(gè)數(shù)據(jù)后堆的變化。閱讀算法〔每題7分,共14分LinkListmynote<LinkListL>{//L是不帶頭結(jié)點(diǎn)的單鏈表的頭指針if<L&&L->next>{q=L；L=L－>next；p=L；S1：while<p－>next>p=p－>next；S2：p－>next=q；q－>next=NULL；}returnL；}請(qǐng)回答下列問題：〔1說明語句S1的功能；〔2說明語句組S2的功能；〔3設(shè)鏈表表示的線性表為〔a1,a2,…,an,寫出算法執(zhí)行后的返回值所表示的線性表。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)計(jì)出單鏈表HL中結(jié)點(diǎn)的值等于給定值X的結(jié)點(diǎn)數(shù)。intCountX<LNode*HL,ElemTypex>模擬試卷五參考答案單選題〔每題2分,共20分1.A2.D3.D4.C5.C6.D7.D8.C9.D10.A填空題〔每空1分,共26分正確性易讀性強(qiáng)壯性高效率O<n>933-134X*+2Y*3/-2nn-1n+1e2e有向無回路n<n-1>/2n<n-1>〔12,40〔〔74〔23,55,63增加1O<log2n>O<nlog2n>歸并運(yùn)算題〔每題6分,共24分線性表為：〔78,50,40,60,34,90鄰接矩陣：鄰接表如圖11所示：圖11用克魯斯卡爾算法得到的最小生成樹為：<1,2>3,<4,6>4,<1,3>5,<1,4>8,<2,5>10,<4,7>20見圖1222244222444555244445552444223883882235835844圖12閱讀算法〔每題7分,共14分〔1查詢鏈表的尾結(jié)點(diǎn)〔2將第一個(gè)結(jié)點(diǎn)鏈接到鏈表的尾部,作為新的尾結(jié)點(diǎn)〔3返回的線性表為〔a2,a3,…,an,a1遞歸地后序遍歷鏈?zhǔn)酱鎯?chǔ)的二叉樹。算法填空〔每空2分,共8分trueBST->leftBST->right編寫算法〔8分intCountX<LNode*HL,ElemTypex>{inti=0;LNode*p=HL;//i為計(jì)數(shù)器while<p!=NULL>{if<P->data==x>i++;p=p->next;}//while,出循環(huán)時(shí)i中的值即為x結(jié)點(diǎn)個(gè)數(shù)returni;}//CountX模擬試卷六一、單項(xiàng)選擇題〔在每小題的四個(gè)備選答案中,選出一個(gè)正確的答案,并將其號(hào)碼填在題干后的括號(hào)內(nèi)。每小題1分,共10分1．下面程序段for<i=1;i<=n;i++>for<j=1;j<=i;j++>x=x+1;的時(shí)間復(fù)雜度為〔。AO<n> BO<n2> CO<n*i> DO<n+i>2．設(shè)一個(gè)棧的入棧序列是ABCD,則借助于一個(gè)棧所得到的出棧序列不可能是〔。AABCD BDCBA CACDB DDABC3．當(dāng)求鏈表的直接后繼與求直接前驅(qū)的時(shí)間復(fù)雜度都相同時(shí),此鏈表應(yīng)為〔。A單鏈表 B雙向鏈表 C單向循環(huán)鏈表 D前面都不正確4．已知串s='BBABBABBA',t='AB',c='A',執(zhí)行置換操作REPLACE<s,t,c>后,s應(yīng)為〔。A'BBABABA' B'BBAABA'C'BBAAA' D'BBABABBA'5．對(duì)于下圖所示的二叉樹,后序遍歷結(jié)果序列為〔。AA,B,C,D,E,F,G,H BA,B,D,F,C,E,G,HCD,F,B,A,C,G,E,H DH,F,D,B,G,E,C,A6．下面AOE網(wǎng)中,關(guān)鍵路徑長(zhǎng)度為〔。A16 B13 C10 D97．用Dijkstra算法求從源點(diǎn)到其它各頂點(diǎn)的最短路徑的時(shí)間復(fù)雜度為〔。AO<n> BO<n2> CO<n3> DO<nlogn>8．在下列查找方法中,平均查找速度最快的是〔。A順序查找 B折半查找 C分塊查找 D二叉排序樹查找9．哈希表的地址區(qū)間為0~17,哈希函數(shù)為H<K>=K%17。采用線性探測(cè)法處理沖突,并將關(guān)鍵字序列26,25,72,38,8,18,59依次存儲(chǔ)到哈希表中。則59存放在哈希表中的地址是<>。A8 B9 C10 D1110．快速排序算法的平均時(shí)間復(fù)雜度是〔。AO<n> BO<n2> CO<nlog2n> DO<log2n>二、填空題〔每空1分,共15分1．設(shè)有一個(gè)記錄r,設(shè)其類型為L(zhǎng)Node,則r實(shí)際所占用的存儲(chǔ)空間的大小為<>。2．一個(gè)算法的時(shí)間復(fù)雜度為<5n3-3nlog2n+7n-9>/<6n>,其數(shù)量級(jí)表示為<>。3．如將n×n的對(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á)式"45*32++"的值為〔。8．對(duì)于一棵具有n個(gè)結(jié)點(diǎn)的樹,此樹中所有結(jié)點(diǎn)的度數(shù)之和為〔,設(shè)葉子結(jié)點(diǎn)數(shù)為n0,度為二的結(jié)點(diǎn)數(shù)為n2,則它們之間的關(guān)系為〔。9．在一個(gè)無向圖中,所有頂點(diǎn)的度數(shù)之和等于所有邊數(shù)的<>倍。10．在一個(gè)具有n個(gè)頂點(diǎn)的無向完全圖中,包含有<>條邊；在一個(gè)具有n個(gè)頂點(diǎn)的有向完全圖中,包含有<>條弧。11．每次從無序表中取一個(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á)式<A-B>*C+D將不會(huì)發(fā)生發(fā)生上溢現(xiàn)象。 〔 5．串是n個(gè)字母的有限序列〔n>=0。 〔 6．n階下三角矩陣的非零元素的個(gè)數(shù)最多為。 〔 7．二叉樹只能采用二叉鏈表來存儲(chǔ)。 〔 8．圖G的某一最小生成樹的代價(jià)一定小于其它生成樹的代價(jià)?！? 9．B+樹是一種特殊的二叉樹?！? 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,試寫出在p所指結(jié)點(diǎn)之前插入元素x的語句序列。2．對(duì)于下圖,用Prim算法從結(jié)點(diǎn)1出發(fā)構(gòu)造出一棵最小生成樹,要求圖示出每一步的變化情況。3．已知一棵二叉樹的先序序列與中序序列分別如下,試畫出此二叉樹。先序序列：ABCDEFGHIJ中序序列：CBEDAGHFJI4．給定一組權(quán)值{3,4,7,14,15,20},試畫出相應(yīng)的哈夫曼樹,并計(jì)算帶樹路徑長(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分>下面程序的功能是二叉樹的中序遍歷的非遞歸算法,其中二叉樹的結(jié)點(diǎn)結(jié)構(gòu)為<lchild,data,rchild>,棧的常用方法有：入棧Push,出棧Pop,判空StackEmpty；試將程序補(bǔ)充完整。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>;//找到最左下的結(jié)點(diǎn)while<t>{visit<t->data>;if<t->rchild>t=GoFarLeft<,S>;elseif<!StackEmpty<S>>t=;elset=;//?？毡砻鞅闅v結(jié)束}//while}//Inorder2．程序填空題<每空2分,共8分>下面程序的功能是用線性探測(cè)再散列處理沖突〔即Hi=<H<key>+i>%m,哈希函數(shù)為H<key>=key%m,進(jìn)行哈希表的插入算法?！踩绫碇幸汛嬖陉P(guān)鍵字相同的記錄或無插入位置,則不進(jìn)行插入,試將程序補(bǔ)充完整。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>return;else{H.elem[p].elem=;returnSUCCESS;}//if}//SerchHashTable3．〔9分閱讀下面算法,試回答：根據(jù)鄰接表畫出對(duì)應(yīng)的圖；〔2當(dāng)圖的鄰接表如下時(shí),執(zhí)行算法T<g,1>時(shí),輸出的結(jié)果是什么？〔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分>以單鏈表為存儲(chǔ)結(jié)構(gòu)實(shí)現(xiàn)簡(jiǎn)單選擇排序,排序的結(jié)果是單鏈表按關(guān)鍵字值升序排序,試編寫此算法。算法申明如下：template<classType>voidLinkList<Type>::SimpleSelectSort<Lnode<Type>*la>2．<8分>下面是一個(gè)二叉樹的中序遍歷的遞歸算法,試改寫此算法,消去第二個(gè)遞歸調(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模擬試卷六參考答案_一、單項(xiàng)選擇題〔在每小題的四個(gè)備選答案中,選出一個(gè)正確的答案,并將其號(hào)碼填在題干后的括號(hào)內(nèi)。每小題1分,共10分1．B2．D3．B 4．A 5．D6．A 7．B 8．B 9．D 10．C二、填空題〔每空1分,共15分1．參考答案：sizeof<LNode>2．參考答案：O<n2>3．參考答案：4．參考答案：<i-1>*n+j-15．參考答案：O<1>6．參考答案：隊(duì)尾 隊(duì)頭7．參考答案：258．參考答案：n-1 n0=n2-19．參考答案：210．參考答案：n<n-1>/2 n<n-1>11．參考答案：選擇〔直接選擇排序或堆排序12．參考答案：操作三、判斷改錯(cuò)題〔判斷正誤,將正確的劃上"√",錯(cuò)誤的劃上"×",每小題1分,共10分1．參考答案：√2．參考答案：×3．參考答案：×4．參考答案：√5．參考答案：×6．參考答案：√7．參考答案：×8．參考答案：×9．參考答案：×10．參考答案：×四、簡(jiǎn)答題〔每小題4分,共20分1．參考答案： s=newlnode; s->data=x; p->prior->next=s; s-prior=p->prior; s-