在每小題列出的四個備選項中只有一個是符合題目要求的，請將其代碼填寫在題后的括號內(nèi)。錯選、下列程序段的時間復雜度為()9A.O(1)B.O(n)C.O(2n)D.O(n2)鏈表的頭指針為head，則判定該表為空表的條件是()22head.棧是一種操作受限的線性結構，其操作的主要特征是()32A.先進先出B.后進先出C.進優(yōu)于出D.出優(yōu)于進4.假設以數(shù)組A[n]存放循環(huán)隊列的元素，其頭、尾指針分別為front和rear。若設定尾指針指向隊列中的隊尾元素，頭指針指向隊列中隊頭元素的前一個位置，則當前存于隊列中的元素個數(shù)為()n5.判斷兩個串大小的基本準則是()52A.兩個串長度的大小B.兩個串中首字符的大小C.兩個串中大寫字母的多少D.對應的第一個不等字符的大小A.1012B.1017C.1034D.1036a00a01a02a03a04 A.16B.17 C.31D.32A.5B.8C.11D.18.下列所示各圖中是中序線索化二叉樹的是(A)81A10.已知含6個頂點(v，v，v，v，v，v)的無向圖的鄰接矩陣如圖所示，則從頂點v出發(fā)進行深度優(yōu)先0123450頂點訪問序列為()108012543012345015234014523是()A.ABCDEFB.FCBEADC.FEDCBAEBCF))172BBHkeykey則下一個插入)206 A.記錄組成的集合B.字符組成的集合 C.數(shù)據(jù)項組成的集合D.數(shù)據(jù)結構組成的集合請在每小題的空格中填上正確答案。錯填、不填均無分。_________。26.假設有一個形如若將上述矩陣中次對角線及其以下的元素按行優(yōu)先壓縮存儲在一維數(shù)組B中，請回答下列問題：(2)若a存儲在B[0]中，a存儲在B[k]中，則k值為多少?1856(1)(1+8)*8/2=36存放次對角線以上的零為37；第一趟劃分過程223159687112359687112357689112356789第二趟劃分過程2231596877768912355678969592136930.假設以帶頭結點的單鏈表表示線性表，單鏈表的類型定義如下：typedefintDataType;typedefstructnode{DataTypedata;structnode*next;}LinkNode,*LinkList;閱讀下列算法，并回答問題：(1)已知初始鏈表如圖所示，畫出執(zhí)行f30(head)之后的鏈表；fLinkListheadif(head->next){rheadnextprnextextNULLwhile(p){ppnextif(s->data%2==0){head->next=s;}else{r->next=s;}}}}以二叉鏈表表示二叉樹，其類型定義如下：typedefstructnode{DataTypedatatructnodelchildrchild}*BinTree;Td=f31(T->lchild)+f31(T->rchild);returnd+1;returnd;向圖鄰接表定義如下：typedefstruct{VertexNodeadjlist[MaxVertexNum];voidDFS(ALGraph*G,inti){dgeNodepvisited[i]=TRUE;NULLprintf("%c",G->adjlist[i].vertex)；else{pGadjlist[i].firstedge;while(p!=NULL){adjvexDFS(G,p->adjvex);ppnext}}}voidf32(ALGraph*G){for(i=0;i<G->n;i++)visited[i]=FALSE;for(i=0;i<G->n;i++)if(!visited[i])DFS(G,i);}ABECD交換將關鍵字最小的記錄移動至前端，如此反復進行，直#defineMAXLEN100typedefstruct{ypekey}NodeType;defNodeTypeSqListMAXLENvoidfSqListRintn)NodeTypet;while(i<j){for(1))k=i;k<j;k++if(R[k].key>R[k+l].key){R[k]=R[k+1];R[k+1]=t;}for(k=j;k>i;k--) if((2)){R[k].key<R[k-l].key R[k]=R[k-1];R[k-1]=t;} }}34.假設以帶頭結點的單鏈表表示線性表，單鏈表的類型定義如下：typedefintDataType;typedefstructnode{DataTypedata;structnode*next;}LinkNode,*LinkList;編寫算法，刪除線性表中最大元素(假設最大值唯一存在)。函數(shù)原型為：voidf34(LinkListhead){kNodepmaxqheadnextmax=head->next;whileP){next}ta}}intj;}一、單項選擇題(本大題共15小題，每小題2分，共30分)在每小題列出的四個備選項選、多選或未選均1.按值可否分解，數(shù)據(jù)類型通常可分為兩類，它們是(c)A.靜態(tài)類型和動態(tài)類型B.原子類型和表類型A.Af(n)是0(g(n))B.Bg(n)是0(f(n))hnn3.指針p、q和r依次指向某循環(huán)鏈表中三個相鄰的結點，交換結點*q和結點*r在表中次序的程A.p->next=r；q->next=r->next；r->next=q；B.p->next=r；r->next=q；q->next=r->next；nextqqnextrnextpnextrD.r->next=q；p->next=r；q->next=r->next；A.3B.5D.75.假設以數(shù)組A[n]存放循環(huán)隊列的元素，其頭指針front指向隊頭元素的前一個位置、尾指rear存儲位置，則在少用一個元素空間的前提下，隊列滿的判定條件為()A.rear==frontontA.3B.4D.67.二維數(shù)組A[10][6]采用行優(yōu)先的存儲方法，若每個元素占4個存儲單元，已知元素A[3][4]的存儲地址為1000，則元素A[4][3]的存儲地址為()A.1020B.1024D1240D.(a)A.FEDCBAB.ABCDEFC.FDECBAD.FBDCEAA.2B.3D.11GGA.7B.8D.22A.塊內(nèi)有序B.塊間有序15.便于進行布爾查詢的文件組織方式是()A.順序文件B.索引文件D二、填空題(本大題共10小題，每小題2分，若有兩個空格，每個空格1分，共20分)請1.數(shù)據(jù)的鏈式存儲結構的特點是借助_指針__表示數(shù)據(jù)元素之間的邏輯關系。2.如果需要對線性表頻繁進行_插入__或__刪除_操作，則不宜采用順序存儲結構。toptopn滿”的判定條件是_top1>top2(或top2=top1-1或toptop+1)。5.廣義表L=(a，(b，()))的深度為_3__。8.在5階B樹中，每個結點至多含4個關鍵字，除根結點之外，其他結點至少含_2__個關鍵字。9.若序列中關鍵字相同的記錄在排序前后的相對次序不變，則稱該排序算法是_穩(wěn)定__的。，共20分)1.答答案：0100，初始堆：第1趟：第2趟：fG#defineMaxNum20intvisited[MaxNum]；/*從頂點vi出發(fā)進行深度優(yōu)先搜索，訪問頂點vj時置visited[j]為1*/intf0(Graph*g)visited[i]=0；if(visited[i]==0)}returnk；}答案：(1)3(3分) (2)返回無向圖g中連通分量的個數(shù)。(2分)2.假設學生成績按學號增序存儲在帶頭結點的單鏈表中，類型定義如下：typedefstructNode{enextvoidf31(LinkListA,LinkListB)while(p&&q)core}}}答案：是一維整型數(shù)組，寫出算法值；intf32(char*s,char*t,intpos[])do{{pos[k++]=i+j;}leiitisj}答案：(1)2；pos[0]=0,pos[1]=8(說明：每個值1分)(3分) (2)返回串t在s中出現(xiàn)的次數(shù)，并將每次出現(xiàn)的位置依次存放在數(shù)組pos中。(2分)存儲結構定義為以下類型：typedefintKeyType;typedefstructnode{KeyTypekey/childrchildodeBSTreeefBSTreeTKeyTypexLLildxTildx}答案：(1)10(2分) (2)T是空樹或T中所有結點的關鍵字均不大于給定值x時，返回空指針。(2分) (3)如果二叉排序樹T中存在含有關鍵字大于給定值x的結點，則返回指針指向它們中關鍵字最小的結點，否則返回空指針。(1分)五、算法設計題(本題10分)1.假設線性表采用順序存儲結構，其類型定義如下：#defineListSize100typedefstruct{intdata[ListSize];答案：參考答案一：Llength{while(i<j&&L->data[i]%2)(1分)while(i<j&&L->data[j]%2==0)(1分)j--;L->data[i]=L->data[j];L->data[j]=t;j--;}}二：L->data[i]=L->data[j];L->data[j]=t;j++;(1分)}四個備選項中只有一個是符合題目要求的，請將其代碼填寫在題后的括號內(nèi)。1．若一個算法的時間復雜度用T(n)表示，其中n的含義是(A)2．具有線性結構的數(shù)據(jù)結構是(C)線性結構有：順序表、棧和隊列、串ABA．O(1)B．O(m)C．O(n)D．O(m+n)4．在帶頭結點的雙向循環(huán)鏈表中插入一個新結點，需要修改的指針域數(shù)量是(C)ppNULLDListNodesmallocsizeofListNodesdataxspriorppriorsnextpppriornexts⑤p->prior=s;}⑥的尾指針值為(B)A．3B．37C0D．97對于循環(huán)向量中的循環(huán)隊列，寫出通過隊頭隊尾指針表示的隊列長度公式。(front指向?qū)嶋H隊頭，rear指向?qū)嶋H隊尾的下一元素位置。)當rear≥front時，隊列長度L=rear-front；當rear<front6．若棧采用鏈式存儲結構，則下列說法中正確的是(B)A．8B．9C．36D．371000，每個元素占一個地址單元，則a的地址為(C)85在n階方陣A這個下三角矩陣中，第i(i從0開始)行(0≤i<n)有i+1個元素，元素總數(shù)為：9．允許結點共享的廣義表稱為(D)10．下列數(shù)據(jù)結構中，不屬于二叉樹的是(A)11．對下面有向圖給出了四種可能的拓撲序列，其中錯誤的是(C)12．以v1為起始結點對下圖進行深度優(yōu)先遍歷，正確的遍歷序列是(D)深度優(yōu)先遍歷類似于樹的前序遍歷。其特點是盡可能先對縱深方向進行搜索。13．下列排序算法中不穩(wěn)定的是(A)穩(wěn)定：直接插入、冒泡、歸并、基數(shù)不穩(wěn)定：直接選擇、希爾、快速、堆A．2B．3C．4D．8ISAM式屬于(D)___O(n)______。typedefstruct{DataTypedata[100]；DataTypef18(SeqStack*S)Error(”Stackisempty”)；returnS->data[S->top]；}_42,13,94,55,05,46,17。一顆m(m≥3)階的B-樹，每個非根結點中所包含的關鍵字個數(shù)j滿足：┌m/2┐-1≤j≤m-1。即每個非根結點至少應有┌m/2┐-1個關鍵字，至多有m-1個關鍵字。 (注：┌m/2┐是指不小于(即大于等于)m/2的最小整數(shù)。)一顆高度為h的m階B-樹中最少可容納的關鍵字總數(shù)為：┌m/2┐h-1，最少可容納的結點總數(shù)為┌m/2┐h-1┌m/2┐-1vertexfirstedgeadjvexnextA01301B124031240C12512D0143014E14551455F242邊表頂邊表361636163618i=2，不調(diào)整i=1，調(diào)整6060231238554536678910606031238545678910161612186015361418258516121818153614602585i=5，不調(diào)整i=5，不調(diào)整151400560123780925123780925518163612345671816361616121418153618602585小根堆初始建堆后的序列小根堆初始建堆后的序列請回答下列問題：Typedefstructnode{DataTypedatavoidf30(LinkListLs)if(q&&q->next){Lsnextqnextwhile(p->next)ppnextp>next=q;回答下列問題：}回答下列問題：的值為零，則條件表達式的值等于0。k=n-l；whilek0){jijx=A[j]；A[j]=A[j+l]；A[j+1]=x；k=j；ofifreturn；}回答下列問題：kj句defstructKeyTypekey；infoListNwhile((1)low<=high){mid=(1ow+high)／2；))returnmid；high=mid-1；}returnO；。ElmTypedata；Tree}一、單項選擇題(本大題共15小題，每小題2分，共30分))A、索引存儲結構和散列存儲結構C一對一存儲結構、一對多存儲結構和多對多存儲結構使操作時間最少，下列選項中，應選擇的存儲結構是()A頭結點的單向鏈表B.帶頭結點的單向鏈表C.帶頭結點的雙循環(huán)鏈表D.帶頭結點的單循環(huán)鏈表()A.n-iB.n-i+lCniD.無法確定5.串匹配算法的本質(zhì)是()CD.子串鏈接CD.407.若一棵二叉樹的前序遍歷序列與后序遍歷序列相同，則該二叉樹可能的形狀是()A.樹中沒有度為2的結點B.樹中只有一個根結點CD結點均只有右子樹A.n.B.G兩個結點之間的最短路徑可以采用的算法是()A.迪杰斯特拉(Dijkstra)算法B.克魯斯卡爾(Kruskal)算法()A不穩(wěn)定的B.穩(wěn)定的C.基于交換的D.基于選擇的表，用拉鏈法解決沖突，散列地址為1的鏈中記錄個數(shù)為()A.1B.2CD.414.已知二叉樹結點關鍵字類型為字符，下列二叉樹中符合二叉排序樹性質(zhì)的是(D))A.順序文件B.索引文件CD.倒排文件二、填空題(本大題共10小題，每小題2分，共20分)chardata[16]；r三、解答題(本大題共4小題，每小題5分，共20分)A=(B,y)：四、算法閱讀題(本大題共4小題，每小題5分，共20分)xxwhile(a[m]<0&&m<n)while(k<n){while(a[k]>=0&&k<n)if(k<n){temp=a[k]；a[k]=a[m]；}}}{while(len>0&&*s)}}{chart[100];ens}}intkey;Infootherinfo;voidInsertSort(SeqListR[],intn){/*待排序列保存在R[1..n]中*/for(i=2；i<=n；i++){hi=i-l;while(lo<=hi){if((2))break;if(R[mi].key>x.key)hi=mi-l;}if(mi=lo)k=i-mi;for(j=0；j<k；j++) R[i-j]=x；}}}*LinkList;voidf33(LinkListhead,intA,intB){LinkListp=NULL;adNULL{}if(p!=NULL)}五、算法設計題(本題10分)tdata}*Bitptr；編寫遞歸算法求二叉樹的高度。函數(shù)原型為：intf34(Bitptrt)；中只有一個是符合題目要求的，請將其代碼填寫在題后的括號內(nèi)。錯1.下列選項中與數(shù)據(jù)存儲結構無關的術語是()A.順序表B.鏈表C.鏈隊列D.棧2.將兩個各有n個元素的有序表歸并成一個有序表，最少的比較次數(shù)是()下一個位置，則向隊列中插入新元素時，修改指針的操作是()4.遞歸實現(xiàn)或函數(shù)調(diào)用時，處理參數(shù)及返回地址，應采用的數(shù)據(jù)結構是()A.堆棧B.多維數(shù)組CD.線性表pqq是p的子串，則求q在p中首次出現(xiàn)位置的算法稱為()AB串聯(lián)接6.對于廣義表A，若head(A)等于tail(A)，則表A為()A.()B.(())7.若一棵具有n(n>0)個結點的二叉樹的先序序列與后序序列正好相反，則該二叉樹一定是()A.結點均無左孩子的二叉樹B.結點均無右孩子的二叉樹C.高度為n的二叉樹D.存在度為2的結點的二叉樹 ()AB.5CD.89.下列敘述中錯誤的是()11.平均時間復雜度為O(nlogn)的穩(wěn)定排序算法是()A.快速排序B.堆排序關鍵字序列是()順序查找，則在等概率情況下，分塊查找成功的平均查找長度是()AB.79D14.在含有10個關鍵字的3階B-樹中進行查找，至多訪問的結點個數(shù)為()A2B.3CD.515.ISAM文件系統(tǒng)中采用多級索引的目的是()A.提高檢索效率B.提高存儲效率CD.方便文件的修改，運行26.已知一棵二叉排序樹(結點值大小按字母順序)的前序遍歷序列為EBACDFHG，下列問題：(1)畫出堆排序的初始堆(大根堆)；堆。voidf30(intA[]，intn){inti,j,m;for(i=1；i<n；i++)for(j=0；j<i；j++){m=A[i*n+j]；A[i*n+j]=A[j*n+i]；A[j*n+i]=m；}}}*BinTree；{{whilewhile(T){}{}}}voidf32(intA[],intn){inti,j,m=l,t；for(i=0;i<n-l&&m;i++){for(j=1;j<n-i;j++)if(A[j-1]>A[j]){t=A[j-l];A[j-1]=A[j]；A[j]=t；}}}Intf33(SqListR，NodeTypeX,intp,intq){intm;if(p>q)return-1;if(R[m].key==X.key)returnm;ml}列問題：性表，單鏈表的類型定義如下：floatf34(LinkListhead):1、在數(shù)據(jù)的邏輯結構中，樹結構和圖結構都是()A.非線性結構2.在一個長度為n的順序表中插入一個元素的算法的時間復雜度為()A.O(1)B.O(logn)單循環(huán)鏈表，應執(zhí)行的操作為()過程中棧中元素個數(shù)最多時為()AB.3個CD.6個5.隊列的特點是()A任何位置進行插入和刪除B除如果每個字符占1個字節(jié)，指針占2個字節(jié)，該鏈串的存儲密度為()AB.1/27.廣義表A=(a,B,(a,B,(a,B,……)))的長度為()A.1B.2CD.無限值址為420，則A[5][5]的存儲地址為()9.在一棵二叉樹中，度為2的結點數(shù)為15，度為1的結點數(shù)為3，則葉子結點數(shù)為()10.在帶權圖的最短路徑問題中，路徑長度是指()A.路徑上的頂點數(shù)B.路徑上的邊數(shù)C.路徑上的頂點數(shù)與邊數(shù)之和D.路徑上各邊的權值之和AeB.2eCneD.n2-112.要以O(nlogn)時間復雜度進行穩(wěn)定的排序，可用的排序方法是()AB.快速排序)A.堆排序B.快速排序14.對有序表進行二分查找成功時，元素比較的次數(shù)()A.僅與表中元素的值有關B.僅與表的長度和被查元素的位置有關C.僅與被查元素的值有關D.僅與表中元素按升序或降序排列有關15.散列文件是一種()A.順序存取的文件B.隨機存取的文件---」| (1)畫出三元組表； (1)畫出該森林； (1)畫出該散列表； (2)求等概率情況下查找成功的平均查找長度ASL; (3)寫出刪除值為70的關鍵字時所需進行的關鍵字比較次數(shù)。 (2)簡述f30的功能。{∥L為非空的有序表 {iLdataki+;}} (2)簡述函數(shù)f31的功能。} (1)若向量BT為：AABCDEFG1234567畫出執(zhí)行函數(shù)f32(BT,7,1)的返回結果;{if(i＞n)returnNULL;}：intadjvex;∥圖的最大頂點數(shù)∥鄰接點域intn,e;}ALGraph;intn,e;∥鏈指針域∥邊表結點結構∥頂點域∥邊表頭指針∥頂點表結點結構∥鄰接表∥圖中當前頂點數(shù)和邊數(shù)∥鄰接表描述的圖∥頂點表∥鄰接矩陣∥圖中當前頂點數(shù)和邊數(shù)∥鄰接矩陣描述的圖{inti,j;G2－＞e=(1);for(i=0;i＜G1.n;i++){G2－＞vertex[i]=(2);for(j=0;j＜G1.n;j++)G2－＞adjmatrix[i][j]=0;while(p) (3);}}}34.設順序表L是一個遞增有序表。編寫算法，要求利用二分查找法確定插入位置，將元素x插入到L中，使L保持有序。1.每個結點有且僅有一個直接前趨和多個(或無)直接后繼(第一個結點除外)的數(shù)據(jù)結構稱為(A)CD.層次結構存儲結構是(D)A.單鏈表B.雙鏈表C.僅有頭指針的單循環(huán)鏈表D.僅有尾指針的單循環(huán)鏈表 (C)A.iB.n-iCC.n-i+lD.不確定4.下面關于串的敘述中，正確的是(A)AB5.無向完全圖G有n個結點，則它的邊的總數(shù)為(C)AnBnn-1)7.如圖所示，在下面的4個序列中，不符合深度優(yōu)先遍歷的序列是(A8.無論待排序列是否有序，排序算法時間復雜度都是O(n2)的排序方法是(D)A.快速排序B.歸并排序9.已知二叉排序樹G，要輸出其結點的有序序列，則采用的遍歷方法是(C)A.按層遍歷B.前序遍歷10.用ISAM和VSAM組織的文件都屬于(B)A文件B.索引順序文件CD.多關鍵字文件15)，則采用的排序方法是(C)A.選擇B.快速12.當采用分塊查找時，數(shù)據(jù)的組織方式為(D)A若干塊，每塊內(nèi)數(shù)據(jù)有序C序，塊間是否有序均可13.下述編碼中不是前綴碼的是(B)14.若一個棧以向量V[1..n]存儲，初始棧頂指針top為n+l，則x進棧的正確操作是(A)指針在最head環(huán)鏈表中，指針p指向鏈尾結點的條件是(D)A[10][10]的每個元素占2個單元，現(xiàn)將其三條對角堆：：：{inti=0,j,k；.while(str[i]!='\0')i++；ifiki1；for(j=k;j<i;j++)ifstrjpops)}31.下列算法是利用二分查找方法在遞減有序表R中插入元素x，并保持表R的有序性。請在空缺處{mid=(low+high)/2；}for(i=*n；i>=low；i--)R[i+1]=R[i]； ++(*n)；}{if(p==NULL)printf("error\n")；{}}}{//n<MaxLen-1RkkeyRklkey{Rn1]=R[k]；R[i-1]=R[i];R[i-l]=R[n+1]；}}A判斷棧空B空aAB．26CD．34BAB下列操作后頭、尾指針的當前值。構造過程。 (2)該算法的功能是什么？intlength；{inti,j；i=0；{for(j=i+1;j<L->length;j++}}} 例如，一個有向圖的鄰接矩陣如下所示：A=Voidf31(MGraphG){Inti,j,k=0;for(i=0;i<G.n;i++)for(j=0;j<G.n;j++)if(G.edges[i][j]==1)k++;printf(“%dn”,k)for(j=0;j<G.n;j++){k=0;for(i=0;i<G.n;j++)if(G.edges[i][j]==1)k++;printf(“%dn”,k)}}{{r[0]=r[i]；j=i-l；while(r[0]<r[j]){r[j+l]=r[j]；}r[j+l]=r[0]；}}if(r[0]<r[1])for(i=2；i<n；i++)if(r[i]<a)a=r[i];elseif(r[i]>b)b=r[i]；}在每小題列出的四個備選項中只有一個是符合題目要求的，請將其選出并將“答題AB結構和鏈式結構CD構D．A．5B.6C7D.8A．ACDBAA．ACDBADAB1CD.4AeB.2eA.n-lB.nA．2B.3C．4從大到下自底向上排序D.5AB.分塊有序D。=66kList算法，并回答問題：voidf30(LinklListhead,DataTypex)}(2)若單鏈表的長度為n，算法的時間復雜度是多少該時間復雜度和鏈表的初始狀態(tài)有關嗎31．閱讀下列算法(假設棧的操作函數(shù)都已定義)，并回答問題：voidf31()y=′k′；}}{∥在中序線索樹中找結點*p的中序前趨，設p非空{(diào)}}一voidf33(inta[],intn)for(i=0；i<n；i++)∥語句1{j=i；if(a[k]<a[j])j=k；∥語句2t=a[i];a[i]=a[j];a[j]=t;}}五、算法設計題(本題10分)pedefstructnodestructnode*lchild,*rchild;在每小題列出的四個備選項中只有一個是符合題目要求的，請將其選出并將“答題紙”的相應代碼涂黑。錯涂、多涂或未征的是A法的可讀性B程度D．執(zhí)行算法所耗費的存儲空間22．對需要頻繁插入和刪除結點的線性表，適合的存儲方式是A．順序儲存B．鏈式存儲CD．散列存儲3．在頭指針為head的循環(huán)鏈表中，判斷指針變量P指向尾結點的條件是C．p->next->next==NULLD．p->next==NULL4．迪杰斯特拉(Dijkstra)算法的功能是A．求圖中某頂點到其他頂點的最短路徑B．求圖中所有頂點之間的最短路徑C．求圖的最小生成樹D．求圖的拓撲排序序列6．A是7×4的二維數(shù)組，按行優(yōu)先方式順序存儲，元素A[0][0]的存儲地址為1000，若每個元素占2個字節(jié)，則元素A[3][3]的存儲地址為7．深度為4的完全二叉樹的結點數(shù)至少為A．4B．88．若采用鄰接矩陣A存儲有向圖G，則結點k的入度等于A中A．結點k對應行元素之和B．結點k對應列元素之和C．結點k對應行和列元素之和D．非零元素之和A．對稱矩陣B．對角矩陣C．三角矩陣D．單位矩陣10．下列關于有向帶權圖G的敘述中，錯誤的是A．圖G的任何一棵生成樹都不含有回路B．圖G生成樹所含的邊數(shù)等于頂點數(shù)減1C．圖G含有回路時無法得到拓撲序列D．圖G的最小生成樹總是唯一的A．冒泡排序B．希爾排序C．直接插入排序D．直接選擇排序12．對下圖進行拓撲排序，可以得到的拓撲序列是13．下列線性表中，能使用二分查找的是A．順序查找B．分塊查找C．散列查找D．基于B樹的查找15．下列排序算法中，時間復雜度為O(nlogn)的算法是A序16．數(shù)據(jù)的同一種邏輯結構，可以對應多種不同的_____存儲結構(物理結構)_____。17．若在長度為n的順序表第i個元素之前插入一個元素，則需要向后移動的元素個數(shù)是_n-i+1_________。____操作。22．圖的遍歷方法有兩種，一種是深度優(yōu)先遍歷，另一種是____廣度優(yōu)先遍歷______。23．如果排序算法是穩(wěn)定的，則關鍵字相同的兩個記錄排序前后相對次序____不變______。查法處理沖突，則關鍵字為60的結點保存的地址是_____7____。26．設Q[M]是有M個元素存儲空間的循環(huán)隊列，若front指向隊首元素，rear指向隊尾分別用C語言描述下列操作：(1)將元素x入隊；(3)計算當前隊列中元素個數(shù)。(1)畫出對應的圖G(2)畫出圖G的最小生成樹下列函數(shù)并回答問題}LinkNode；TypedefLinkNode*Linklist；{while(q!=NULL)if(q->data==x){}}}(1)執(zhí)行該函數(shù)后，單鏈表head中data值為x的結點數(shù)是多少?(2)該函數(shù)的功能是什么?函數(shù)并回答問題}BinTNode；{if(bt!=NULL){Inorder(bt->lchild)；rchild}}(1)給出對如題31圖所示的二叉樹執(zhí)行函數(shù)Inorder后得到的輸出序列。(2)該函數(shù)的功能是什么?32．下列函數(shù)實現(xiàn)直接插入排序，請?zhí)顚戇m當內(nèi)容，使其功能完整。{{r[0]-r[i]；while((3)){r[j+1]_=r[j]；}r[j+l]=r[0]；}}(1)在空白處填寫適當內(nèi)容，使函數(shù)功能完整。(2)查找成功時函數(shù)的返回值是什么?(3)查找失敗時函數(shù)的返回值是什么?while(10w<=high){if(R[mid].key==k)if(R[mid].key>k)low=mid+l；}}}LinkNode；typedefLinkNode*LinkList；請編寫原型為intListisequal(LinkListA，LinkListB)的函數(shù)，指針A、B分別指向兩個帶頭結點的單鏈表。函數(shù)功能是：若單鏈表A、B中全部對應結點的data值相等，則返回1，否則返回0。，請將其選出并將“答題紙”的相應A.棧B.鏈表C.順序表D.二叉鏈表A.2B.3C.4D..6A列是一種先進先出的線性表B表C是否為空AB.節(jié)省存儲空間C便于輸入輸出D.降低時間復雜度A.14B.64AneB.eC2D.411.對序列(15,9,7,8,20,-1,4)進行排序,若一趟排序后的結果為(-1,15,9,7,8,20,4),則采用的排序方法是A