自學(xué)考試-數(shù)據(jù)結(jié)構(gòu)歷年考題綜合(答案)

..2006.101.若結(jié)點(diǎn)的存儲(chǔ)地址與其關(guān)鍵字之間存在某種映射關(guān)系,則稱這種存儲(chǔ)結(jié)構(gòu)為<>A.順序存儲(chǔ)結(jié)構(gòu)B.鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)C.索引存儲(chǔ)結(jié)構(gòu)D.散列存儲(chǔ)結(jié)構(gòu)2.在長(zhǎng)度為n的順序表的第i<1≤i≤n+1>個(gè)位置上插入一個(gè)元素,元素的移動(dòng)次數(shù)為<>A.n-i+1B.n-iC.iD.i-13.對(duì)于只在表的首、尾兩端進(jìn)行插入操作的線性表,宜采用的存儲(chǔ)結(jié)構(gòu)為<>A.順序表B.用頭指針表示的單循環(huán)鏈表C.用尾指針表示的單循環(huán)鏈表D.單鏈表4.若進(jìn)棧序列為a,b,c,則通過入出棧操作可能得到的a,b,c的不同排列個(gè)數(shù)為<>A.4B.5C.6D.75．一棵有16結(jié)點(diǎn)的完全二叉樹,對(duì)它按層編號(hào),則對(duì)編號(hào)為7的結(jié)點(diǎn)X,它的雙親結(jié)點(diǎn)及右孩子結(jié)點(diǎn)的編號(hào)分別為〔A．2,14 B．2,15C．3,14 D．3,156．設(shè)有一5階上三角矩陣A［1..5,1..5］,現(xiàn)將其上三角中的元素按列優(yōu)先順序存放在一堆數(shù)組B［1..15］中。已知B［1］的地址為100,每個(gè)元素占用2個(gè)存儲(chǔ)單元,則A［3,4］的地址為〔A．116 B．118C．120 D．1227．一個(gè)帶權(quán)的無向連通圖的最小生成樹〔A．有一棵或多棵 B．只有一棵C．一定有多棵 D．可能不存在8．下列有關(guān)圖遍歷的說法中不正確的是〔A．連通圖的深度優(yōu)先搜索是一個(gè)遞歸過程B．圖的廣度優(yōu)先搜索中鄰接點(diǎn)的尋找具有"先進(jìn)先出"的特征C．非連通圖不能用深度優(yōu)先搜索法D．圖的遍歷要求每一頂點(diǎn)僅被訪問一次9．某算法的空間花費(fèi)s<n>=2n+n100+nlog2n+n101,則其空間復(fù)雜度為〔。A．O<nlog2n>B.O<n100>C.O<n101>D.O<2n>10.單鏈表中的存儲(chǔ)密度一定〔。A．小于0.5B.等于1C.大于0.1D.小于111．在順序棧中刪除一個(gè)元素,至少要移動(dòng)〔元素。A．0B.1C.n/2D.n12．空串是〔。A．只包含空格符的串B.長(zhǎng)度為0的串C.只包含一個(gè)空格符的串D.不含字母的串13．采用三元組表存儲(chǔ)稀疏矩陣,是為了〔。A．節(jié)省存取時(shí)間B.節(jié)省存儲(chǔ)空間C.提高對(duì)矩陣元素的訪問速度D.提高對(duì)矩陣運(yùn)算的可靠性14．高度為h的二叉樹最多有〔個(gè)節(jié)點(diǎn)。A．2h-1B.2hC.2h-1D.2h-1+115．N個(gè)頂點(diǎn),e條邊的無權(quán)有向圖的鄰接矩陣中非零元素有〔個(gè)。A．nB.n-eC.eD.e+n16．直接選擇排序在最好情況下的時(shí)間復(fù)雜度是〔。A．O<n>B.O<nlog2n>C.O<1>D.O<n2>17．N個(gè)結(jié)點(diǎn)的m階B樹至少包含〔個(gè)關(guān)鍵字。A．<m-1>*nB.nC.<「m/2」-1>*<n-1>+1D.n*「m/2」-1>18．在散列文件中,同一個(gè)桶內(nèi)的所有記錄應(yīng)當(dāng)具有〔。A．相同的關(guān)鍵字B.相同的散列值C.相同的某個(gè)屬性值D.相同的存取頻率19．在最壞的情況下,查找成功時(shí)二叉排序樹的平均查找長(zhǎng)度〔A．小于順序表的平均查找長(zhǎng)度 B．大于順序表的平均查找長(zhǎng)度C．與順序表的平均查找長(zhǎng)度相同 D．無法與順序表的平均查找長(zhǎng)度比較20．散列表中由于散列到同一個(gè)地址而引起的"堆積"現(xiàn)象,是由〔A．同義詞之間發(fā)生沖突引起的B．非同義詞之間發(fā)生沖突引起的C．同義詞之間或非同義詞之間發(fā)生沖突引起的D．散列表"溢出"引起的二、填空題〔每空1.5分,計(jì)15分21．ALV樹是一種平衡的二叉排序樹,樹中任一結(jié)點(diǎn)的<>22．在VSAM文件的控制區(qū)間中,記錄的存儲(chǔ)方式為<>23．單鏈表的存儲(chǔ)密度〔順序表的存儲(chǔ)密度。24．設(shè)SQ是循環(huán)隊(duì)列,存儲(chǔ)在數(shù)組D[M]中,則SQ入隊(duì)操作對(duì)其隊(duì)尾指針rear的修改是〔。25．長(zhǎng)度為n的串s1與長(zhǎng)度為2n的串s2的比較運(yùn)算的時(shí)間復(fù)雜度是〔。26．廣義表<<<a,b,c>,d,e,f>>的長(zhǎng)度是〔。27．N〔n>0個(gè)節(jié)點(diǎn)的哈夫曼樹恰含〔個(gè)度為1的節(jié)點(diǎn)。28．深度為n的二叉樹最少有〔個(gè)結(jié)點(diǎn)。29．N〔n>0個(gè)頂點(diǎn)的連通有向圖至少有〔條邊。30．對(duì)N〔n>0個(gè)記錄進(jìn)行冒泡排序,最少要交換〔記錄。三、簡(jiǎn)答題〔每小題5分,計(jì)30分31．給出下面森林對(duì)應(yīng)的二叉樹及二叉樹的后續(xù)序列。〔圖132．一棵樹有3度節(jié)點(diǎn)100個(gè),2度節(jié)點(diǎn)200個(gè),該樹有葉子節(jié)點(diǎn)多少個(gè),該樹可以有多少個(gè)度為1的節(jié)點(diǎn)？33．設(shè)有廣義表A,A=<<<a,b>,x>,<<a>,<b>>,<c,<d,<y>>>>,寫出由A得到y(tǒng)的對(duì)廣義表A的操作序列。34．畫出用普里姆算法構(gòu)造下面所示帶權(quán)無向圖的最小生成樹的示意圖。35．寫出下列用快排序?qū)ο铝行蛄羞M(jìn)行兩次劃分的過程及結(jié)果。372651487769822117132139551836．畫出對(duì)下面的5階B樹插入關(guān)鍵字37后的結(jié)果。四、理解設(shè)計(jì)題〔每小題5分,計(jì)15分37．設(shè)某帶頭結(jié)頭的單鏈表的結(jié)點(diǎn)結(jié)構(gòu)說明如下： typedefstructnodel{intdata; structnodel*next; }node; 試設(shè)計(jì)一個(gè)算法：voidcopy<node*headl,node*head2>,將以head1為頭指針的單鏈表復(fù)制到一個(gè)不帶有頭結(jié)點(diǎn)且以head2為頭指針的單鏈表中?！?分38.閱讀下列算法,并回答下列問題：<1>該算法采用何種策略進(jìn)行排序?<2>算法中R[n+1]的作用是什么?typedefstruct{KeyTypekey;infoTypeotherinfo;}nodeType;typedefnodeTypeSqList［MAXLEN］;voidsort<SqListR,intn>{//n小于MAXLEN-1intk;i;for<k=n-1;k>=1;k-->if<R[k].key>R[k+1].key>{R[n+1]=R[k];for<i=k+1;R[i].key<R[n+1].key;i++>R[i-1]=R[i];R[i-1]=R[n+1];}}39．下面函數(shù)BinInsert的功能是對(duì)線性表R的前n個(gè)元素實(shí)現(xiàn)二分法插入排序。請(qǐng)?jiān)诳杖碧幪钊脒m當(dāng)?shù)恼Z句,使其能夠正確工作。typedefstructnode{intkey;/*otherInfo*/}Node;typedefNodeSeqlist[100];voidBinInsert<SeqlistR,intn>{intlow,up,mid,i,j;Nodet;for<i=0;i<n;i++>{_____<1>________________;low=0;__________<2>_____________;while<low<up>{mid=<low+up>/2;if<R[mid].key==t.key>{_________<3>__________;break;}if<t.key<R[mid].key>________<4>________;else_______<5>_____;}for<j=i;j>low;j-->R[j]=R[j-1];_________<6>_____________;}}五、算法實(shí)現(xiàn)題〔共10分40.假設(shè)二叉樹T采用如下定義的存儲(chǔ)結(jié)構(gòu)：typedefstructnode{DataTypedata;structnode*lchild,*rchild,*parent;}PBinTree;其中,結(jié)點(diǎn)的lchild域和rchild域已分別填有指向其左、右孩子結(jié)點(diǎn)的指針,而parent域中的值為空指針<擬作為指向雙親結(jié)點(diǎn)的指針域>。請(qǐng)編寫一個(gè)遞歸算法,將該存儲(chǔ)結(jié)構(gòu)中各結(jié)點(diǎn)的parent域的值修改成指向其雙親結(jié)點(diǎn)的指針。2006一．單項(xiàng)選擇題1.D2.B3.C4.B5.D6.C7.B8.D9.D10.D11.A12.B13.B14.A15.C16.A17.C18.B19.C20.B二.填空題21.左右子樹樹高之差的絕對(duì)值不大于123.小于24.sq->rear=<sq->rear+1>%m25.O<n>26.127.028.n29.n30.0三.簡(jiǎn)答題31.GFEDCBJIKHA32、n0=n2+2n3+1=200+2*100+1=40133、Tail<Head<Tail<Head<Tail<Tail<A>>>>>=<y>34、35、182621131721[37]8269774839555136、四.閱讀理解題37、一邊遍歷,一邊申請(qǐng)新結(jié)點(diǎn),鏈接到head2序列中。38、直接插入排序。哨兵。避免邊界檢測(cè),提高程序運(yùn)行效率。39、t=R[i];up=i-1;low=mid+1;up=mid-1;low=mid+1;R[low]=t;20021．某算法的空間花費(fèi)s<n>=2n+n100+nlog2n+n101,則其空間復(fù)雜度為〔。A．O<nlog2n>B.O<n100>C.O<n101>D.O<2n>2．單鏈表中的存儲(chǔ)密度一定〔。A．小于0.5B.等于1C.大于0.1D.小于13．在順序棧中刪除一個(gè)元素,至少要移動(dòng)〔元素。A．0B.1C.n/2D.n4．空串是〔。A．只包含空格符的串B.長(zhǎng)度為0的串C.只包含一個(gè)空格符的串D.不含字母的串5．采用三元組表存儲(chǔ)稀疏矩陣,是為了〔。A．節(jié)省存取時(shí)間B.節(jié)省存儲(chǔ)空間C.提高對(duì)矩陣元素的訪問速度D.提高對(duì)矩陣運(yùn)算的可靠性6．高度為h的二叉樹最多有〔個(gè)節(jié)點(diǎn)。A．2h-1B.2hC.2h-1D.2h-1+17．N個(gè)頂點(diǎn),e條邊的無權(quán)有向圖的鄰接矩陣中非零元素有〔個(gè)。A．nB.n-eC.eD.e+n8．直接選擇排序在最好情況下的時(shí)間復(fù)雜度是〔。A．O<n>B.O<nlog2n>C.O<1>D.O<n2>9．N個(gè)結(jié)點(diǎn)的m階B樹至少包含〔個(gè)關(guān)鍵字。A．<m-1>*nB.nC.<「m/2」-1>*<n-1>+1D.n*「m/2」-1>10．在散列文件中,同一個(gè)桶內(nèi)的所有記錄應(yīng)當(dāng)具有〔。A．相同的關(guān)鍵字B.相同的散列值C.相同的某個(gè)屬性值D.相同的存取頻率11．某算法的時(shí)間花費(fèi)T<n>=0.05n2+100n+10,則該算法的時(shí)間復(fù)雜度為〔。12．單鏈表的存儲(chǔ)密度〔順序表的存儲(chǔ)密度。13．設(shè)SQ是循環(huán)隊(duì)列,存儲(chǔ)在數(shù)組D[M]中,則SQ入隊(duì)操作對(duì)其隊(duì)尾指針rear的修改是〔。14．長(zhǎng)度為n的串s1與長(zhǎng)度為2n的串s2的比較運(yùn)算的時(shí)間復(fù)雜度是〔。15．廣義表<<<a,b,c>,d,e,f>>的長(zhǎng)度是〔。16．N〔n>0個(gè)節(jié)點(diǎn)的哈夫曼樹恰含〔個(gè)度為1的節(jié)點(diǎn)。17．深度為n的二叉樹最少有〔個(gè)結(jié)點(diǎn)。18．N〔n>0個(gè)頂點(diǎn)的連通有向圖至少有〔條邊。19．對(duì)N〔n>0個(gè)記錄進(jìn)行冒泡排序,最少要交換〔記錄。20．倒排文件的每個(gè)倒排表項(xiàng)包含〔和記錄地址。21．給出下面森林對(duì)應(yīng)的二叉樹及二叉樹的后續(xù)序列?！矆D122．一棵樹有3度節(jié)點(diǎn)100個(gè),2度節(jié)點(diǎn)200個(gè),該樹有葉子節(jié)點(diǎn)多少個(gè),該樹可以有多少個(gè)度為1的節(jié)點(diǎn)？23．設(shè)有廣義表A,A=<<<a,b>,x>,<<a>,<b>>,<c,<d,<y>>>>,寫出由A得到y(tǒng)的對(duì)廣義表A的操作序列。24．設(shè)有程序：intf<inta[],intn,intkey>{inti;for<i=0;i<n;i++>if<a[i]==key>returni;return-1;}若key在a[j]<j=0,1,2,…n-1>中的概率為2-<j+1>,key不在a中的概率為2-n,那么查找Key時(shí)平均比較Key的次數(shù)是多少,該算法的時(shí)間復(fù)雜度是多少？25．畫出用普里姆算法構(gòu)造下面所示帶權(quán)無向圖的最小生成樹的示意圖。四、理解題〔每題6分,計(jì)12分26．指出下面函數(shù)GV的功能及其返回值的含義。其中,Tab是存儲(chǔ)稀疏矩陣A的非零元素的長(zhǎng)度為len的三元組表。#include<stdio.h>typedefstruct{introw,col,val;}TriTupleNode;intGV<inti,intj,intlen,TriTupleNodeTab[]>{intk;for<k=0;k<len;k++>if<tab[k].row==i&&tab[k].col==j>returnTab[k].val;return0;}27．設(shè)P1和P2是兩個(gè)單鏈表,他們的元素都遞增有序,指出下面函數(shù)f的功能。typedefintDataType;typedefstructnode{DataTypedata;structnode*next;}ListNode;typedefListNode*LinkList;LinkListf<LinkListp1,LinkListp2>{LinkListh=NULL,p;while<p1&&p2>{if<p1->data<p2->data>{p=p1;p1=p1->next;}else{p=p2;p2=p2->next;}p->next=h;h=p;}while<p1>{p=p1;p1=p1->next;p->next=h;h=p;}while<p2>{p=p2;p2=p2->next;p->next=h;h=p;}returnh;}五、填充題〔每題18分28．下面函數(shù)BinInsert的功能是對(duì)線性表R的前n個(gè)元素實(shí)現(xiàn)二分法插入排序。請(qǐng)?jiān)诳杖碧幪钊脒m當(dāng)?shù)恼Z句,使其能夠正確工作。typedefstructnode{intkey;/*otherInfo*/}Node;typedefNodeSeqlist[100];voidBinInsert<SeqlistR,intn>{intlow,up,mid,i,j;Nodet;for<i=0;i<n;i++>{_____<1>________________;low=0;__________<2>_____________;while<low<up>{mid=<low+up>/2;if<R[mid].key==t.key>{_________<3>__________;break;}if<t.key<R[mid].key>________<4>________;else_______<5>_____;}for<j=i;j>low;j-->R[j]=R[j-1];_________<6>_____________;}}2002D一、單項(xiàng)選擇題1.D2.D3.A4.B5.B6.A7.C8.D9.C10.B二、填空題<每小題2分,共30分>11.O<n2>12.小于13．rear=<rear+1>%m14.O<n>15.116.017.n18.n19.020.次關(guān)鍵字三、簡(jiǎn)答題21、〔見下圖后序序列GFEDCBJIKHA22、葉結(jié)點(diǎn)有401個(gè),度為1的結(jié)點(diǎn)可以有任意多個(gè)。24、平均比較次數(shù)=1*2-<0+1>+2*2-<1+1>+……+n*2-<<n-1>+1>+n*2-n=2-2-<n-1>-n*2-n時(shí)間復(fù)雜度為：O<1>25、見圖。四、理解題26、在三元組表Tab中,查找稀疏矩陣中元素A[I,J]的值,并把此值作為函數(shù)的返回值。27、把兩個(gè)遞增有序的單鏈表合并為一個(gè)遞減有序的單鏈表。五、填充題t=R[i];up=i-1low=mid+1up=mid-1low=mid+1R[low]=t2002-10一、單項(xiàng)選擇題<本大題共15小題,每小題2分,共30分>在每小題列出的四個(gè)選項(xiàng)中只有一個(gè)選項(xiàng)是符合題目要求的,請(qǐng)將正確選項(xiàng)前的字母填在題后的括號(hào)內(nèi)。1.若結(jié)點(diǎn)的存儲(chǔ)地址與其關(guān)鍵字之間存在某種映射關(guān)系,則稱這種存儲(chǔ)結(jié)構(gòu)為<>A.順序存儲(chǔ)結(jié)構(gòu)B.鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)C.索引存儲(chǔ)結(jié)構(gòu)D.散列存儲(chǔ)結(jié)構(gòu)2.在長(zhǎng)度為n的順序表的第i<1≤i≤n+1>個(gè)位置上插入一個(gè)元素,元素的移動(dòng)次數(shù)為<>A.n-i+1B.n-iC.iD.i-13.對(duì)于只在表的首、尾兩端進(jìn)行插入操作的線性表,宜采用的存儲(chǔ)結(jié)構(gòu)為<>A.順序表B.用頭指針表示的單循環(huán)鏈表C.用尾指針表示的單循環(huán)鏈表D.單鏈表4.若進(jìn)棧序列為a,b,c,則通過入出棧操作可能得到的a,b,c的不同排列個(gè)數(shù)為<>A.4B.5C.6D.75.為查找某一特定單詞在文本中出現(xiàn)的位置,可應(yīng)用的串運(yùn)算是<>A.插入B.刪除C.串聯(lián)接D.子串定位6.已知函數(shù)Sub<s,i,j>的功能是返回串s中從第i個(gè)字符起長(zhǎng)度為j的子串,函數(shù)Scopy<s,t>的功能為復(fù)制串t到s。若字符串S=″SCIENCESTUDY″,則調(diào)用函數(shù)Scopy<P,Sub<S,1,7>>后得到<>A.P=″SCIENCE″B.P=″STUDY″C.S=″SCIENCE″D.S=″STUDY″7.三維數(shù)組A[4][5][6]按行優(yōu)先存儲(chǔ)方法存儲(chǔ)在內(nèi)存中,若每個(gè)元素占2個(gè)存儲(chǔ)單元,且數(shù)組中第一個(gè)元素的存儲(chǔ)地址為120,則元素A［３］[4][5]的存儲(chǔ)地址為<>A.356B.358C.360D.3628.如右圖所示廣義表是一種<>A.線性表B.純表C.結(jié)點(diǎn)共享表D.遞歸表9.下列陳述中正確的是<>A.二叉樹是度為2的有序樹B.二叉樹中結(jié)點(diǎn)只有一個(gè)孩子時(shí)無左右之分C.二叉樹中必有度為2的結(jié)點(diǎn)D.二叉樹中最多只有兩棵子樹,并且有左右之分10.n個(gè)頂點(diǎn)的有向完全圖中含有向邊的數(shù)目最多為<>A.n-1B.nC.n<n-1>/2D.n<n-1>11.已知一個(gè)有向圖如右所示,則從頂點(diǎn)a出發(fā)進(jìn)行深度優(yōu)先偏歷,不可能得到的DFS序列為<>A.adbefcB.adcefbC.adcbfeD.adefcb12.在最好和最壞情況下的時(shí)間復(fù)雜度均為O<nlogn>且穩(wěn)定的排序方法是<>A.快速排序B.堆排序C.歸并排序D.基數(shù)排序13.不可能生成右圖所示二叉排序樹的關(guān)鍵字序列是<>A.45312B.42531C.45213D.4231514.ALV樹是一種平衡的二叉排序樹,樹中任一結(jié)點(diǎn)的<>A.左、右子樹的高度均相同B.左、右子樹高度差的絕對(duì)值不超過1C.左子樹的高度均大于右子樹的高度D.左子樹的高度均小于右子樹的高度15.在VSAM文件的控制區(qū)間中,記錄的存儲(chǔ)方式為<>A.無序順序B.有序順序C.無序鏈接D.有序鏈接二、填空題<本大題共10小題,每小題2分,若有兩個(gè)空格,每個(gè)空格1分,共20分>16.若一個(gè)算法中的語句頻度之和為T<n>=3720n+4nlogn,則算法的時(shí)間復(fù)雜度為________。17.在如圖所示的鏈表中,若在指針p所指的結(jié)點(diǎn)之后插入數(shù)據(jù)域值相繼為a和b的兩個(gè)結(jié)點(diǎn),則可用下列兩個(gè)語句實(shí)現(xiàn)該操作,它們依次是________和________。18.假設(shè)以S和X分別表示進(jìn)棧和退棧操作,則對(duì)輸入序列a,b,c,d,e進(jìn)行一系列棧操作SSXSXSSXXX之后,得到的輸出序列為________。19.串S=″Iamaworker″的長(zhǎng)度是________。20.假設(shè)一個(gè)10階的下三角矩陣A按列優(yōu)順序壓縮存儲(chǔ)在一維數(shù)組C中,則C數(shù)組的大小應(yīng)為________。21.在n個(gè)結(jié)點(diǎn)的線索二叉鏈表中,有________個(gè)線索指針。22.若采用鄰接矩陣結(jié)構(gòu)存儲(chǔ)具有n個(gè)頂點(diǎn)的圖,則對(duì)該圖進(jìn)行廣度優(yōu)先遍歷的算法時(shí)間復(fù)雜度為________。23.對(duì)關(guān)鍵字序列<52,80,63,44,48,91>進(jìn)行一趟快速排序之后得到的結(jié)果為________。24.由10000個(gè)結(jié)點(diǎn)構(gòu)成的二叉排序樹,在等概率查找的假設(shè)下,查找成功時(shí)的平均查找長(zhǎng)度的最大值可能達(dá)到________。25.若要找出所有工資低于1500元,職稱是副教授,及所有工資低于2000元,職稱是教授的記錄,則查詢條件是________。三、解答題<本大題共4小題,每小題5分,共20分>26.已知一個(gè)6行5列的稀疏矩陣中非零元的值分別為：-90,41,-76,28,-54,65和-8,它們?cè)诰仃囍械牧刑?hào)依次為：1,4,5,1,2,4和5。當(dāng)以帶行表的三元組表作存儲(chǔ)結(jié)構(gòu)時(shí),其行表RowTab中的值依次為0,0,2,2,3和5。請(qǐng)寫出該稀疏矩陣<注：矩陣元素的行列下標(biāo)均從1開始>。27.已知樹T的先序遍歷序列為ABCDEFGHIJKL,后序遍歷序列為CBEFDJIKLHGA。請(qǐng)畫出樹T。28.對(duì)關(guān)鍵字序列<72,87,61,23,94,16,05,58>進(jìn)行堆排序,使之按關(guān)鍵字遞減次序排列。請(qǐng)寫出排序過程中得到的初始堆和前三趟的序列狀態(tài)。初始堆：________第1趟：________第2趟：________第3趟：________29.在關(guān)鍵字序列<07,12,15,18,27,32,41,92>中用二分查找法查找和給定值92相等的關(guān)鍵字,請(qǐng)寫出查找過程中依次和給定值"92”四、算法閱讀題<本大題共4小題,每小題5分,共20分>30.以下函數(shù)中,h是帶頭結(jié)點(diǎn)的雙向循環(huán)鏈表的頭指針。<1>說明程序的功能；<2>當(dāng)鏈表中結(jié)點(diǎn)數(shù)分別為1和6<不包括頭結(jié)點(diǎn)>時(shí),請(qǐng)寫出程序中while循環(huán)體的執(zhí)行次數(shù)。..intf<DListNode*h>{DListNode*p,*q;intj=1;p=h->next;q=h->prior;while<p!=q&&p->prior!=q>if<p->data==q->data>{p=p->next;q=q->prior;}elsej=0;returnj;}..31.設(shè)棧S=<1,2,3,4,5,6,7>,其中7為棧頂元素。請(qǐng)寫出調(diào)用algo<&s>后棧S的狀態(tài)。voidalgo<Stack*S>{inti=0;QueueQ;StackT;InitQueue<&Q>;InitStack<&T>;while<!StackEmpty<S>>{if<<i=!i>!=0>Push<&T,Pop<&S>>;elseEnQueue<&Q,Pop<&S>>;}while<!QueueEmpty<Q>>Push<&S,DeQueue<&Q>>;while<!StackEmpty<T>>Push<&S,Pop<&T>>；}32.已知帶權(quán)圖的鄰接矩陣表示和鄰接表表示的形式說明分別如下：..#defineMaxNum50//圖的最大頂點(diǎn)數(shù)#defineINFINITYINT_MAX//INT_MAX為最大整數(shù),表示∞typedefstruct{charvexs[MaxNum];//字符類型的頂點(diǎn)表intedges[MaxNum][MaxMum];//權(quán)值為整型的鄰接矩陣intn,e;//圖中當(dāng)前的頂點(diǎn)數(shù)和邊數(shù)}MGraph;//鄰接矩陣結(jié)構(gòu)描述typedefstructnode{intadjvex;//鄰接點(diǎn)域intweight;//邊的權(quán)值structnode*next;//鏈指針域}EdgeNode;//邊表結(jié)點(diǎn)結(jié)構(gòu)描述typedefstruct{charvertex;//頂點(diǎn)域EdgeNode*firstedge;//邊表頭指針}VertexNode;//頂點(diǎn)表結(jié)點(diǎn)結(jié)構(gòu)描述typedefstruct{VertexNodeadjlist[MaxNum];//鄰接表intn,e;//圖中當(dāng)前的頂點(diǎn)數(shù)和邊數(shù)}ALGraph;//鄰接表結(jié)構(gòu)描述..下列算法是根據(jù)一個(gè)帶權(quán)圖的鄰接矩陣存儲(chǔ)結(jié)構(gòu)G1建立該圖的鄰接表存儲(chǔ)結(jié)構(gòu)G2,請(qǐng)?zhí)钊牒线m的內(nèi)容,使其成為一個(gè)完整的算法。..voidconvertM<MGraph*G1,ALGraph*G2>{inti,j;EdgeNode*p;G2->n=G1->n;G2->e=G1->e;for<i=0;i<G1->n;i++>{G2->adjlist[i].vertex=G1->vexs[i];G2->adjlist[i].firstedge=<1>;}for<i=0;i<G1->n;i++>for<j=0;j<G1->n;j++>if<G1->edges[i][j]<INFINITY>{p=<EdgeNode*>malloc<sizeof<EdgeNode>>;p->weight=<2>;p->adjvex=j;p->next=G2->adjlist[i].firstedge;<3>;}}33.閱讀下列算法,并回答下列問題：<1>該算法采用何種策略進(jìn)行排序?<2>算法中R[n+1]的作用是什么?Typedefstruct{KeyTypekey;infoTypeotherinfo;}nodeType;typedefnodeTypeSqList［MAXLEN］;voidsort<SqListR,intn>{//n小于MAXLEN-1intk;i;for<k=n-1;k>=1;k-->if<R[k].key>R[k+1].key>{R[n+1]=R[k];for<i=k+1;R[i].key<R[n+1].key;i++>R[i-1]=R[i];R[i-1]=R[n+1];}}..五、算法設(shè)計(jì)題<本題共10分>34.假設(shè)二叉樹T采用如下定義的存儲(chǔ)結(jié)構(gòu)：typedefstructnode{DataTypedata;structnode*lchild,*rchild,*parent;}PBinTree;其中,結(jié)點(diǎn)的lchild域和rchild域已分別填有指向其左、右孩子結(jié)點(diǎn)的指針,而parent域中的值為空指針<擬作為指向雙親結(jié)點(diǎn)的指針域>。請(qǐng)編寫一個(gè)遞歸算法,將該存儲(chǔ)結(jié)構(gòu)中各結(jié)點(diǎn)的parent域的值修改成指向其雙親結(jié)點(diǎn)的指針。-9041-76285465-8一．單項(xiàng)選擇題1.D2.A3.A4.B5.D6.A7.A8.C9.D10.D11.A12.B13.A14.B15.D二.填空題16.O<nlogn>17.b->next=p->next;p->next=s;18.bceda19.1420.4621.n+122.O〔n223.48,44,82,63,80,9124.<10000+1>/225.職稱="副教授"and工資<1500or職稱="教授"andand工資<2000三.簡(jiǎn)答題26.27.由于樹的后序序列就是等價(jià)二叉樹的中序遍歷序列,因此先得到等價(jià)二叉樹,然后轉(zhuǎn)化為相應(yīng)的樹。28.初始堆：05,23,16,58,94,72,61,87第一趟：16,23,61,58,94,72,87,05第二趟：23,58,61,87,94,72,16,05第三趟：58,72,61,87,94,23,16,0529．18324192四.算法閱讀題30.<1>.檢查循環(huán)鏈表中頭結(jié)點(diǎn)兩端對(duì)應(yīng)位置處的結(jié)點(diǎn)值是否對(duì)稱相等。<2>.當(dāng)結(jié)點(diǎn)個(gè)數(shù)為1時(shí),循環(huán)次數(shù)為0次。當(dāng)結(jié)點(diǎn)個(gè)數(shù)為0時(shí),循環(huán)次數(shù)為3次。..31.7531246〔7為棧頂32.<1>NULL<2>G1->edges[i][j]<3>G2->adjlist[i].firstedge=p33.<1>從右側(cè)進(jìn)行的直接插入排序<2>R[n+1]的作用為哨兵..五.算法設(shè)計(jì)題34.BintreeNode*pre;pre=NULL;voidxiugai<BinTree*T>{if<T>{xiugai<<*T>->lchild>;<*T>->parent=pre;pre=<*T>;xiugai<<*T>->rchild>;}}2003.101．下列說法正確的是〔A．?dāng)?shù)據(jù)是數(shù)據(jù)元素的基本單位B．?dāng)?shù)據(jù)元素是數(shù)據(jù)項(xiàng)中不可分割的最小標(biāo)識(shí)單位C．?dāng)?shù)據(jù)可由若干個(gè)數(shù)據(jù)元素構(gòu)成D．?dāng)?shù)據(jù)項(xiàng)可由若干個(gè)數(shù)據(jù)元素構(gòu)成2．?dāng)?shù)據(jù)結(jié)構(gòu)的基本任務(wù)是〔A．邏輯結(jié)構(gòu)和存儲(chǔ)結(jié)構(gòu)的設(shè)計(jì) B．?dāng)?shù)據(jù)結(jié)構(gòu)的運(yùn)算實(shí)現(xiàn)C．?dāng)?shù)據(jù)結(jié)構(gòu)的評(píng)價(jià)與選擇 D．?dāng)?shù)據(jù)結(jié)構(gòu)的設(shè)計(jì)與實(shí)現(xiàn)3．在一個(gè)具有n個(gè)結(jié)點(diǎn)的有序單鏈表中插入一個(gè)新結(jié)點(diǎn),并使插入后仍然有序,則該操作的時(shí)間復(fù)雜性量級(jí)為〔A．O〔1 B．O〔nC．O〔nlog2n D．O<n2>4．順序存儲(chǔ)的線性表〔a1,a2,…,an,在任一結(jié)點(diǎn)前插入一個(gè)新結(jié)點(diǎn)時(shí)所需移動(dòng)結(jié)點(diǎn)的平均次數(shù)為〔A．n B．n/2C．n+1 D．<n+1>/25．下列樹U′,經(jīng)剪枝運(yùn)算DELETE〔U′,x,2后為〔6．一棵有16結(jié)點(diǎn)的完全二叉樹,對(duì)它按層編號(hào),則對(duì)編號(hào)為7的結(jié)點(diǎn)X,它的雙親結(jié)點(diǎn)及右孩子結(jié)點(diǎn)的編號(hào)分別為〔A．2,14 B．2,15C．3,14 D．3,157．設(shè)有一5階上三角矩陣A［1..5,1..5］,現(xiàn)將其上三角中的元素按列優(yōu)先順序存放在一堆數(shù)組B［1..15］中。已知B［1］的地址為100,每個(gè)元素占用2個(gè)存儲(chǔ)單元,則A［3,4］的地址為〔A．116 B．118C．120 D．1228．一個(gè)帶權(quán)的無向連通圖的最小生成樹〔A．有一棵或多棵 B．只有一棵C．一定有多棵 D．可能不存在9．下列有關(guān)圖遍歷的說法中不正確的是〔A．連通圖的深度優(yōu)先搜索是一個(gè)遞歸過程B．圖的廣度優(yōu)先搜索中鄰接點(diǎn)的尋找具有"先進(jìn)先出"的特征C．非連通圖不能用深度優(yōu)先搜索法D．圖的遍歷要求每一頂點(diǎn)僅被訪問一次10．在最壞的情況下,查找成功時(shí)二叉排序樹的平均查找長(zhǎng)度〔A．小于順序表的平均查找長(zhǎng)度 B．大于順序表的平均查找長(zhǎng)度C．與順序表的平均查找長(zhǎng)度相同 D．無法與順序表的平均查找長(zhǎng)度比較11．閉散列表中由于散列到同一個(gè)地址而引起的"堆積"現(xiàn)象,是由〔A．同義詞之間發(fā)生沖突引起的B．非同義詞之間發(fā)生沖突引起的C．同義詞之間或非同義詞之間發(fā)生沖突引起的D．散列表"溢出"引起的12．從外存設(shè)備的觀點(diǎn)看,存取操作的基本單位是〔A．邏輯記錄 B．?dāng)?shù)據(jù)元素C．文件 D．物理記錄13．對(duì)文件進(jìn)行檢索操作時(shí),每次都要從第一個(gè)記錄開始的文件是〔A．順序文件 B．索引文件C．順序索引文件 D．散列文件14．一組記錄的鍵值為〔46,74,18,53,14,20,40,38,86,65,利用堆排序的方法建立的初始堆為〔A．〔14,18,38,46,65,40,20,53,86,74B．〔14,38,18,46,65,20,40,53,86,74C．〔14,18,20,38,40,46,53,65,74,86D．〔14,86,20,38,40,46,53,65,74,1815．對(duì)序列〔22,86,19,49,12,30,65,35,18進(jìn)行一趟排序后得到的結(jié)果如下：〔18,12,19,22,49,30,65,35,86,則可以認(rèn)為使用的排序方法是〔A．選擇排序 B．冒泡排序C．快速排序 D．插入排序二、填空題〔本大題共13小題,每空2分,共26分 請(qǐng)?jiān)诿啃☆}的空格中填上正確答案。錯(cuò)填、不填均無分。16．表示邏輯關(guān)系的存儲(chǔ)結(jié)構(gòu)可以有四種方式,即順序存儲(chǔ)方式、鏈?zhǔn)酱鎯?chǔ)方式、_______________和散列存儲(chǔ)方式。priordata,next,17．設(shè)某非空雙鏈表,其結(jié)點(diǎn)形式為若要?jiǎng)h除指針q所指向的結(jié)點(diǎn),則需執(zhí)行下述語句段：q->prior->next＝q->next;_______________。18．如圖所示,設(shè)輸入元素的順序是A,B,C,D,通過棧的變換,在輸出端可得到各種排列。若輸出序列的第一個(gè)元素為D,則輸出序列為_______________。19．隊(duì)列中允許進(jìn)行刪除的一端為________________。20．設(shè)一棵二叉樹中度為2的結(jié)點(diǎn)數(shù)為10,則該樹的葉子數(shù)為________________。21．如圖所示的二叉樹,若按后根遍歷,則其輸出序列為________________。22．一個(gè)具有n個(gè)頂點(diǎn)的有向完全圖的弧數(shù)為________________。23．查找表的數(shù)據(jù)結(jié)構(gòu)有別于線性表、樹型結(jié)構(gòu)等,其邏輯結(jié)構(gòu)為________________。24．長(zhǎng)度為L(zhǎng)的順序表,采用設(shè)置崗哨方式順序查找,若查找不成功,其查找長(zhǎng)度為________________。25．在開散列表上查找某元素時(shí),通常分兩步進(jìn)行,首先必須計(jì)算該鍵值的散列地址,然后在地址指針?biāo)竉_______________中查找該結(jié)點(diǎn)。26．文件的檢索有順序存取、________________和按關(guān)鍵字存取三種方式。27．在待排序的n個(gè)記錄中任取一個(gè)記錄,以該記錄的鍵值作為標(biāo)準(zhǔn),將所有記錄分為兩組,使得第一組中各記錄的鍵值均小于或等于該鍵值,第二組中的各記錄的鍵值均大于該鍵值；然后將該記錄排在兩組中間。再對(duì)所分成的兩組分別使用上述方法,直到所有記錄都排在適當(dāng)位置為止。這種排序方法稱為________________。28．在對(duì)一組記錄關(guān)鍵字〔54,38,96,23,15,72,60,45,83進(jìn)行冒泡排序時(shí),整個(gè)冒泡排序過程中需進(jìn)行________________趟才能完成。三、應(yīng)用題〔本大題共5小題,共30分29．設(shè)有一順序隊(duì)列sq,容量為5,初始狀態(tài)時(shí)sq.front=sq.rear=0,畫出做完下列操作后隊(duì)列及其頭尾指針的狀態(tài)變化情況,若不能入隊(duì),請(qǐng)簡(jiǎn)述其理由后停止?！?分d,e,b入隊(duì)d,e出隊(duì)i,j入隊(duì)b出隊(duì)n,o,p入隊(duì)30．已知無向圖G的鄰接矩陣如下,假設(shè)對(duì)其每行元素訪問時(shí)必須從右到左,請(qǐng)寫出從V0開始的深度優(yōu)先搜索的序列?！?分31．畫出下列二叉樹的二叉鏈表表示圖?！?分32．用二分查找法對(duì)一個(gè)長(zhǎng)度為10的有序表進(jìn)行查找,填寫查找每一元素需要的比較次數(shù)。〔8分元素下標(biāo)12345678910比較次數(shù)33．已知序列〔10,18,4,3,6,12,1,9,15,8,請(qǐng)給出采用二路歸并排序法對(duì)該序列進(jìn)行升序排序時(shí)的每一趟結(jié)果?！?分四、設(shè)計(jì)題〔本大題共2小題,共14分34．設(shè)某帶頭結(jié)頭的單鏈表的結(jié)點(diǎn)結(jié)構(gòu)說明如下： typedefstructnodel { intdata; structnodel*next; }node; 試設(shè)計(jì)一個(gè)算法：voidcopy<node*headl,node*head2>,將以head1為頭指針的單鏈表復(fù)制到一個(gè)不帶有頭結(jié)點(diǎn)且以head2為頭指針的單鏈表中。〔6分35．修改冒泡排序法以實(shí)現(xiàn)雙向冒泡排序。雙向冒泡排序指第一次把最大記錄放到表尾,第二次把最小記錄放到表頭,如此反復(fù)進(jìn)行。試編寫修改后的算法：voiddbubble<inta[],intn>?！?分一、單項(xiàng)選擇題1.C2.B3.B4.D5.C6.D7.A8.A9.C10.C11.B12.D13.A14.B15.C二、填空題16．索引存儲(chǔ)方式17.q->next->prior=q->prior;18.DCBA19.隊(duì)首20.1121.DBFHGECA22.N〔N-124.L+125、鏈表中26.隨機(jī)存取27、快排序28、7三、應(yīng)用題：29、圖形略,提示對(duì)于使用順序表的隊(duì)列,一般使用循環(huán)結(jié)構(gòu),否則隨著出隊(duì)入隊(duì)次數(shù)的增多,一定會(huì)出現(xiàn)隊(duì)尾益出順序表的情況。30、V0V2V4V3V132、比較次數(shù)順序?yàn)椋?、2、3、4、1、3、4、2、3、433、第一趟：〔108〔34〔612〔19〔815第二趟：〔34810〔16912〔815在本趟末尾并入剩余的一組,結(jié)果為：〔34810〔16891215第三趟：〔134689101215四、設(shè)計(jì)題：34、voidcopy<node*head1,*head2>{node*p,*q,*r;p=head1->next;if<p==NULL>{printf<"Error">;return;}while<p>{q=<node*>malloc<sizeof<node>>;q->data=p->data;q->next=NULL;if<head2==NULL>{head2=q;r2=q;}else{r2->next=q;r2=q;}}}2004.101．在數(shù)據(jù)結(jié)構(gòu)中,數(shù)據(jù)的邏輯結(jié)構(gòu)可以分成〔A．內(nèi)部結(jié)構(gòu)和外部結(jié)構(gòu) B．線性結(jié)構(gòu)和非線性結(jié)構(gòu)C．緊湊結(jié)構(gòu)和非緊揍結(jié)構(gòu) D．動(dòng)態(tài)結(jié)構(gòu)和靜態(tài)結(jié)構(gòu)2．在以單鏈表為存儲(chǔ)結(jié)構(gòu)的線性表中,數(shù)據(jù)元素之間的邏輯關(guān)系用〔A．?dāng)?shù)據(jù)元素的相鄰地址表示 B．?dāng)?shù)據(jù)元素在表中的序號(hào)表示C．指向后繼元素的指針表示 D．?dāng)?shù)據(jù)元素的值表示3．設(shè)p指向單鏈表中的一個(gè)結(jié)點(diǎn),s指向待插入的結(jié)點(diǎn),則下述程序段的功能是〔s->next=p->next;p->next=s;t=p->data;p->data=s->data;s->data=t;A．結(jié)點(diǎn)*p與結(jié)點(diǎn)*s的數(shù)據(jù)域互換B．在p所指結(jié)點(diǎn)的元素之前插入元素C．在p所指結(jié)點(diǎn)的元素之后插入元素D．在結(jié)點(diǎn)*p之前插入結(jié)點(diǎn)*s4．棧和隊(duì)列都是〔A．限制存取位置的線性結(jié)構(gòu) B．順序存儲(chǔ)的線性結(jié)構(gòu)C．鏈?zhǔn)酱鎯?chǔ)的線性結(jié)構(gòu) D．限制存取位置的非線性結(jié)構(gòu)5．若數(shù)組s[0..n-1]為兩個(gè)棧s1和s2的共用存儲(chǔ)空間,且僅當(dāng)s[0..n-1]全滿時(shí),各棧才不能進(jìn)行進(jìn)棧操作,則為這兩個(gè)棧分配空間的最佳方案是：s1和s2的棧頂指針的初值分別為〔A．1和n+1 B．1和n/2C．－1和n D．－1和n+16．執(zhí)行下列程序段后,串X的值為〔 S=〞abcdefgh〞;T=〞xyzw〞; substr<X,S,2,strlen<T>>; substr<Y,S,stelen<T>,2>; strcat<X,Y>;A．〞cdefgh〞 B．〞cdxyzw〞C．〞cdefxy〞 D．〞cdefef〞7．多維數(shù)組之所以有行優(yōu)先順序和列優(yōu)先順序兩種存儲(chǔ)方式是因?yàn)椤睞．?dāng)?shù)組的元素處在行和列兩個(gè)關(guān)系中 B．?dāng)?shù)組的元素必須從左到右順序排列C．?dāng)?shù)組的元素之間存在次序關(guān)系 D．?dāng)?shù)組是多維結(jié)構(gòu),內(nèi)存是一維結(jié)構(gòu)8．從廣義表LS＝〔<p,q>,r,s中分解出原子q的運(yùn)算是〔A．tail<head<LS>> B．head<tail<head<LS>>>C．head<tail<LS>> D．tail<tail<head<LS>>>9．在具有n個(gè)葉子結(jié)點(diǎn)的嚴(yán)格二叉樹中,結(jié)點(diǎn)總數(shù)為〔A．2n+1 B．2nC．2n-1 D．2n-210．若<vi,vj>是有向圖的一條邊,則稱〔A．vi鄰接于vjB．vj鄰接于viC．vi和vj相互鄰接 D．vi與vj不相鄰接11．在一個(gè)帶權(quán)連通圖G中,權(quán)值最小的邊一定包含在G的〔A．最小生成樹中 B．深度優(yōu)先生成樹中C．廣度優(yōu)先生成樹中 D．深度優(yōu)先生成森林中12．當(dāng)在二叉排序樹中插入一個(gè)新結(jié)點(diǎn)時(shí),若樹中不存在與待插入結(jié)點(diǎn)的關(guān)鍵字相同的結(jié)點(diǎn),且新結(jié)點(diǎn)的關(guān)鍵字小于根結(jié)點(diǎn)的關(guān)鍵字,則新結(jié)點(diǎn)將成為〔A．左子樹的葉子結(jié)點(diǎn) B．左子樹的分支結(jié)點(diǎn)C．右子樹的葉子結(jié)點(diǎn) D．右子樹的分支結(jié)點(diǎn)13．希爾排序的增量序列必須是〔A．遞增的 B．隨機(jī)的C．遞減的 D．非遞減的14．如果在排序過程中,每次均將一個(gè)待排序的記錄按關(guān)鍵字大小加入到前面已經(jīng)有序的子表中的適當(dāng)位置,則該排序方法稱為〔A．插入排序 B．歸并排序C．冒泡排序 D．堆排序15．設(shè)置溢出區(qū)的文件是〔A．索引非順序文件 B．ISAM文件C．VSAM文件 D．順序文件二、填空題〔本大題共10小題,每小題2分,共20分 請(qǐng)?jiān)诿啃☆}的空格中填上正確答案。錯(cuò)填、不填均無分。16．下列程序段的時(shí)間復(fù)雜度為________________。product=1;for<i=n;i>0;i-->for<j=i+1;j<n;j++>product*=j;17．已知指針p指向單鏈表中某個(gè)結(jié)點(diǎn),則語句p->next=p->next->next的作用是________________。18．假設(shè)元素只能按a,b,c,d的順序依次進(jìn)棧,且得到的出棧序列中的第一個(gè)元素為c,則可能得到的出棧序列為________________,不可能得到的出棧序列為________________。19．若鏈串結(jié)點(diǎn)中的指針占4個(gè)字節(jié),每個(gè)字符占1個(gè)字節(jié),則結(jié)點(diǎn)大小為2的鏈串的存儲(chǔ)密度為________________。20．右圖表示的廣義表為________________。21．若一棵滿三叉樹中含有121個(gè)結(jié)點(diǎn),則該樹的深度為________________。22．若以鄰接矩陣表示有向圖,則鄰接矩陣上第i行中非零元素的個(gè)數(shù)即為頂點(diǎn)vi的________________。23．若希望只進(jìn)行8趟排序便能在4800個(gè)元素中找出其中值最小的8個(gè)元素,并且要求排序過程中所進(jìn)行的關(guān)鍵字比較次數(shù)盡可能少,則應(yīng)該選用________________排序方法。24．在含20個(gè)關(guān)鍵字的3階B樹〔2－3樹上查找一個(gè)關(guān)鍵字,至多需要訪問___________次外存。25．文件上的兩類主要操作為________________和________________。三、解答題〔本大題共4小題,每小題5分,共20分26．設(shè)棧S1的入棧序列為1234〔每個(gè)數(shù)字為13個(gè)元素,則不可能得到出棧序列3142。但可通過增設(shè)棧S2來實(shí)現(xiàn)。例如,按下圖中的箭頭指示,依次經(jīng)過棧S1和S2,便可得到序列3142。如果用H1和H2分別表示棧S1和S2的進(jìn)棧操作,用P1和P2分別表示兩個(gè)棧的出棧操作,則得到3142的一個(gè)操作步驟為H1,H1,H1,P1,H2,P2,P1,H2,P1,H2,P2,H1,P1,H2,P2,P2請(qǐng)仿照上例寫出利用兩個(gè)棧從1234得到4132的操作步驟。27．已知樹如右圖所示,〔1寫出該樹的后序序列； 〔2畫出由該樹轉(zhuǎn)換得到的二叉樹。28．為關(guān)鍵字〔17,33,31,40,48構(gòu)造一個(gè)長(zhǎng)度為7的散列表,設(shè)散列函數(shù)為h<key>=key%7,用開放定址法解決沖突的探查序列是hi=<h<key>+i<key%5+1>>%70≤i≤6〔1畫出構(gòu)造所得的散列表；〔2求出在等概率情況下查找成功時(shí)的平均查找長(zhǎng)度。29．已知R［1..8］中的元素依次為〔12,5,9,20,6,31,24,27,寫出按算法MergeSortDC對(duì)R進(jìn)行自頂向下的二路歸并排序過程中,前5次調(diào)用函數(shù)Merge<R,low,mid,high>時(shí)參數(shù)low,mid和high的值。voidMergeSortDC<intR[],intlow,intmid,inthigh>{ intmid; if<low<high> { mid=<low+high>/2; MergeSortDC<R,low,mid>; MergeSortDC<R,mid+1,high>; Merge<R,low,mid,high>; }}//MergeSortDC〔1第一次調(diào)用時(shí)的參數(shù)值；〔2第二次調(diào)用時(shí)的參數(shù)值； 〔3第三次調(diào)用時(shí)的參數(shù)值；〔4第四次調(diào)用時(shí)的參數(shù)值；〔5第五次調(diào)用時(shí)的參數(shù)值；四、算法閱讀題〔本大題共4小題,每小題5分,共20分30．下列函數(shù)的功能是,對(duì)以帶頭結(jié)點(diǎn)的單鏈表作為存儲(chǔ)結(jié)構(gòu)的兩個(gè)遞增有序表〔表中不存在值相同的數(shù)據(jù)元素進(jìn)行如下操作：將所有在Lb表中存在而La表中不存在的結(jié)點(diǎn)插入到La中,其中La和Lb分別為兩個(gè)鏈表的頭指針。請(qǐng)?jiān)诳杖碧幪钊牒线m內(nèi)容,使其成為一個(gè)完整的算法。..voidunion<LinkListLa,LinkListLb> { //本算法的功能是將所有Lb表中存在而La表中不存在的結(jié)點(diǎn)插入到La表中 LinkListpre=La,q; LinkListpa=La->next; LinkListpb=Lb->next; free<Lb>; while<pa&&pd> { if<pa->data<pb->data> {pre=pa;pa=pa->next;} elseif<pa->data>pb->data> {<1>; pre=pb; pb=pb->next;<2>; } else { q=pb;pb=pb->next;free<q>; } } if<pb><3>; }..31．已知串的存儲(chǔ)結(jié)構(gòu)為動(dòng)態(tài)存儲(chǔ)分配的順序串。閱讀下列算法,并回答問題： 〔1寫出執(zhí)行函數(shù)調(diào)用strc<s,r>的返回結(jié)果,其中s=〃aba〃,r=〃abababa〃;〔2簡(jiǎn)述函數(shù)strc的功能。intstrc<HString*sub,HString*str>{inti=0,j,k,count=0;while<i<str->length–sub->length+1>{j=i;k=0;while<k<sub->length&&str->ch[j]==sub->ch[k]>{j++;k++;}if<k==sub->length>{count++;i=j-sub->length+1;}elsei++;}returncount;}32．下列函數(shù)MDFSForest的功能是,對(duì)一個(gè)采用鄰接矩陣作存儲(chǔ)結(jié)構(gòu)的圖進(jìn)行深度優(yōu)先搜索遍歷,輸出所得深度優(yōu)先生成森林中各條邊。請(qǐng)?jiān)诳杖碧幪钊牒线m內(nèi)容,使其成為一個(gè)完整的算法。..#defineMaxMun20//圖的最大頂點(diǎn)數(shù)typedefstruct{ charvexs[MaxNum];//字符類型的頂點(diǎn)表intedges[MaxNum][MaxNum];//鄰接矩陣 intn,e;//圖的頂點(diǎn)數(shù)和邊數(shù)}MGraph;//圖的鄰接矩陣結(jié)構(gòu)描述typedefenum{FALSE,TRUE}Boolean;Booleanvisited[MaxNum];voidMDFSTree<MGraph*G,inti>;voidMDFSForest<MGraph*G>{ inti,k; for<i=0;i<G->n;i++> visited[i]=<1>; for<k=0;k<G->n;k++>if<!visited[k]>MDFSTree<G,k>;}voidMDFSTree<MGraph*G,inti>{ intj; visited[i]=TRUE; for<j=0;j<G->n;j++> { if<<2>> { printf<〃<%c,%c>〃G->vexs[i],G->vexs[j]>;<3>; } }｝..33．已知整形數(shù)組L［1..8］中的元素依次為〔9,8,5,7,6,3,2,1,閱讀下列函數(shù),并寫出執(zhí)行函數(shù)調(diào)用sort<L,8>時(shí),對(duì)L進(jìn)行的頭兩趟〔pass分別為0和1處理結(jié)果。Voidsort<intR[],intn> { intpass=0,k,exchange,x; do{ k=pass%2+1; exchange=0; while<k<n> {if<R[k]>R[k+1]>{ x=R[k];R[k]=R[k+1];R[k+1]=x; exchange=1; }K+=2}pass++; }while<exchange==1||pass<=1>; }第一趟〔pass=0:第二趟〔pass=1:五、算法設(shè)計(jì)題〔本大題共10分34．已知二叉排序樹中結(jié)點(diǎn)的關(guān)鍵字為整數(shù),設(shè)計(jì)遞歸算法按遞增有序性輸出樹中所有大于或等于給定值x的結(jié)點(diǎn),并以函數(shù)的參數(shù)返回輸出的結(jié)點(diǎn)個(gè)數(shù)。假設(shè)以二叉鏈表為存儲(chǔ)結(jié)構(gòu),其結(jié)點(diǎn)結(jié)構(gòu)為：lchildkeyrchild一、單項(xiàng)選擇題1.B2.C3.B4.A5.C6.D12.B13.C14.A15.B二、填空題16．O<n2>17.刪除p所指示的結(jié)點(diǎn)后面的結(jié)點(diǎn)18.可能：cbad或cdba、cbda不可能：cabd、cdab、cadb19.33.3%20.遞歸表21.522.出度23.堆排序24、425、檢索和更新三、解答題：26.H1H1H1H1P1H2P2P1H2P1H2P1H2P2P2H1P2P1H2P227、EBJKFGHICDA,見下圖。28、〔1+1+3+2+4/5=2：找17需1次比較,找33需1次比較,找31需3次比較,找40需2次比較,找48需4次比較。29、<1>R,1,4,8<2>R,1,2,4<3>R,5,6,8<4>R,1,1,2<5>R,3,3,4四、算法閱讀題：30、pre->next=pb;pre->next=pa;pre->next=pb;30、函數(shù)的返回結(jié)果為：3返回sub子串在字符串str中出現(xiàn)的次數(shù)；32、false;G->edges[i][j]!=0&&!visited[j]MDFSTree<G,j>;33、這是一個(gè)奇偶排序的算法。第一趟：89573612第二趟：85937162五、算法題目：假設(shè)BinNode是如圖所示的結(jié)點(diǎn)類型,BinTree是指向樹根的指針類型；inttongji<BintreeT,DataTypex>{intcount1,count2,count;if<T>{count1=tongji<T->lchild,x>;if<T->data>=x>{printf<T->data>;count=1;}count2=tongji<T->rchild,x>;}returncount+count1+count2;elsereturn0;}也可以寫成下面的形式：首先定義全局變量count,并賦初值0。intcount=0;voidtongji<BintreeT,DataTypex>{if<T>{tongji<T->lchild,x>;if<T->data>=x>{printf<T->data>;count++;}tongji<T->rchild,x>;}}2004.1B1．下列數(shù)據(jù)組織形式中,〔的各個(gè)結(jié)點(diǎn)可以任意鄰接。A．集合 B．樹形結(jié)構(gòu)C．線性結(jié)構(gòu) D．圖狀結(jié)構(gòu)2．設(shè)某二維數(shù)組A［1..n,1..n］,則在該數(shù)組中用順序查找法查找一個(gè)元素的時(shí)間復(fù)雜性的量級(jí)為〔A．O〔log2n B．O<n>C．O<nlog2n> D．O<n2>3．在線性表的下列存儲(chǔ)結(jié)構(gòu)中,讀取元素花費(fèi)時(shí)間最少的是〔A．單鏈表 B．雙鏈表C．循環(huán)鏈表 D．順序表4．將一個(gè)頭指針為p的單鏈表中的元素按與原單鏈表相反的次序存放,則下列算法段中的空白處應(yīng)為q=NULL;while<p!=NULL> {〔 } p=q;A．r=q;q=p;p=p->next;q->next=r;B．q=p;r=q;p=p->next;q->next=r;C．r=q;p=p->next;q=p;q->next=r;D．q=p;p=p->next;r=q;q->next=r;5．?dāng)?shù)組通常具有兩種基本運(yùn)算,即〔A．創(chuàng)建和刪除 B．索引和修改C．讀和寫 D．排序和查找6．除根結(jié)點(diǎn)外,樹上每個(gè)結(jié)點(diǎn)〔A．可有任意多個(gè)孩子、任意多個(gè)雙親B．可有任意多個(gè)孩子、一個(gè)雙親C．可有一個(gè)孩子、任意多個(gè)雙親D．只有一個(gè)孩子、一個(gè)雙親7．具有100個(gè)結(jié)點(diǎn)的二叉樹中,若用二叉鏈表存儲(chǔ),其指針域部分用來指向結(jié)點(diǎn)的左、右孩子,其余〔個(gè)指針域?yàn)榭铡．50 B．99C．100 D．1018．鄰接表是圖的一種〔A．順序存儲(chǔ)結(jié)構(gòu) B．鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)C．索引存儲(chǔ)結(jié)構(gòu) D．散列存儲(chǔ)結(jié)構(gòu)9．如果無向圖G必須進(jìn)行二次廣度優(yōu)先搜索才能訪問其所有頂點(diǎn),則下列說法中不正確的是〔A．G肯定不是完全圖 B．G一定不是連通圖C．G中一定有回路 D．G有2個(gè)連通分量10．若構(gòu)造一棵具有n個(gè)結(jié)點(diǎn)的二叉排序樹,最壞的情況下其深度不會(huì)超過〔A．n/2 B．nC．<n+1>/2 D．n+111．若用二分查找法取得的中間位置元素鍵值大于被查找值,說明被查找值位于中間值的前面,下次的查找區(qū)間為從原開始位置至〔A．該中間位置 B．該中間位置－1C．該中間位置＋1 D．該中間位置／212．散列文件不能〔A．隨機(jī)存取 B．索引存取C．按關(guān)鍵字存取 D．直接存取13．若檢索順序文件各個(gè)記錄的概率相同,設(shè)文件占用的頁塊數(shù)為n,則按關(guān)鍵字存取時(shí)的平均訪問外存次數(shù)為〔A．n/2 B．nC．n/4 D．logn14．下列關(guān)鍵碼序列中,屬于堆的是〔A．〔15,30,22,93,52,71 B．〔15,71,30,22,93,52C．〔15,52,22,93,30,71 D．〔93,30,52,22,15,7115．已知10個(gè)數(shù)據(jù)元素為〔54,28,16,34,73,62,95,60,26,43,對(duì)該數(shù)列按從小到大排序,經(jīng)過一趟冒泡排序后的序列為〔A．16,28,34,54,73,62,60,26,43,95B．28,16,34,54,62,73,60,26,43,95C．28,16,34,54,62,60,73,26,43,95D．16,28,34,54,62,60,73,26,43,95二、填空題〔本大題共13小題,每小題2分,共26分 請(qǐng)?jiān)诿啃☆}的空格中填上正確答案。錯(cuò)填、不填均無分。16．下列程序段的時(shí)間復(fù)雜性量級(jí)是_____________。for<i=1;i<n;i++> for<j=1;j<i;j++> t=t+1;17．在順序存儲(chǔ)的線性表〔a1,a2…,an中的第i<1≤i≤n>個(gè)元素之前插入一個(gè)元素,則需向后移動(dòng)_____________個(gè)元素。18．在棧的順序?qū)崿F(xiàn)中,若棧不滿,則進(jìn)棧操作可以用下列算法片斷實(shí)現(xiàn)：_____________；sq->data[sq->top]=x；19．鏈隊(duì)列實(shí)際上是一個(gè)同時(shí)帶有頭指針和尾指針的單鏈表,尾指針指向該單鏈表的_____________。20．設(shè)有k個(gè)結(jié)點(diǎn),在用哈夫曼算法構(gòu)造哈夫曼樹的過程中,若第i次合并時(shí)已找到權(quán)最小的結(jié)點(diǎn)x和權(quán)次小的結(jié)點(diǎn)y,用T［x］.wt表示結(jié)點(diǎn)x的權(quán)值,已知T［x］.wt=m,T［y］.wt=n,則合并成新的二叉樹后給新根結(jié)點(diǎn)的權(quán)值賦值的語句為_____________。21．在下列樹中,結(jié)點(diǎn)H的祖先為_____________。22．頂點(diǎn)數(shù)為n、邊數(shù)為n<n-1>/2的無向圖稱為_____________。23．動(dòng)態(tài)查找表在開散列表上通常采用_____________來解決沖突問題。24．對(duì)于有10個(gè)元素的有序表采用二分查找,需要比較3次方可找到其對(duì)應(yīng)的鍵值,則該元素在有序表中的位置可能是______________。25．查找表的邏輯結(jié)構(gòu)與線性結(jié)構(gòu)、樹型結(jié)構(gòu)等相比,根本區(qū)別在于______________。26．文件的基本運(yùn)算包括______________和修改兩類。27．在排序方法中,依次將每個(gè)記錄插入到一個(gè)有序的子序列中去,即在第i<i≥1>遍整理時(shí),r1,r2,…,ri-1已經(jīng)是排好順序的子序列,取出第i個(gè)元素ri,在已排好序的子序列里為ri找到一個(gè)合適的位置,并把它插到該位置上。這種排序方法被稱為___________。28．快速排序法在待排序數(shù)據(jù)_____________的情況下最不利于發(fā)揮其長(zhǎng)處。三、應(yīng)用題〔本大題共5小題,共30分29．如圖所示,輸入元素為A,B,C,在棧的輸出端得到一個(gè)輸出序列ABC,求出在棧的輸入端所有可能的輸入序列?！?分30．分別寫出下列二叉樹的先根、中根、后根遍歷序列?！?分31．已知無向圖G的鄰接表如下,請(qǐng)寫出其從頂點(diǎn)V2開始的深度優(yōu)先搜索的序列。〔4分32．設(shè)閉散列表容量為7〔散列地址空間0..6,給定表〔30,36,47,52,34,散列函數(shù)H〔k=kmod6,采用線性探測(cè)法解決沖突,要求：〔7分 〔1構(gòu)造散列表； 〔2求查找數(shù)34需要的比較次數(shù)。33．已知序列〔503,87,512,61,908,170,897,275,653,462請(qǐng)給出采用快速排序法作升序排序時(shí)的每一趟的結(jié)果?！?分四、設(shè)計(jì)題〔本大題共2小題,共14分34．設(shè)某頭指針為head的單鏈表的結(jié)點(diǎn)結(jié)構(gòu)說明如下：〔6分typedefstructnode1 { intdata; structnode1*next }node;試設(shè)計(jì)一個(gè)算法voidchange<node*head>,將該單鏈表中的元素按原單鏈表相反的次序重新存放,即第一個(gè)結(jié)點(diǎn)變成最后一個(gè)結(jié)點(diǎn),第二個(gè)結(jié)點(diǎn)變?yōu)榈箶?shù)第二個(gè)結(jié)點(diǎn),如此等等。35．編寫一個(gè)算法v