數(shù)據(jù)結(jié)構(gòu)與算法設(shè)計考研復(fù)習(xí)模擬題及答案電子工業(yè)_第1頁
數(shù)據(jù)結(jié)構(gòu)與算法設(shè)計考研復(fù)習(xí)模擬題及答案電子工業(yè)_第2頁
數(shù)據(jù)結(jié)構(gòu)與算法設(shè)計考研復(fù)習(xí)模擬題及答案電子工業(yè)_第3頁
數(shù)據(jù)結(jié)構(gòu)與算法設(shè)計考研復(fù)習(xí)模擬題及答案電子工業(yè)_第4頁
數(shù)據(jù)結(jié)構(gòu)與算法設(shè)計考研復(fù)習(xí)模擬題及答案電子工業(yè)_第5頁
已閱讀5頁,還剩15頁未讀, 繼續(xù)免費閱讀

下載本文檔

版權(quán)說明:本文檔由用戶提供并上傳,收益歸屬內(nèi)容提供方,若內(nèi)容存在侵權(quán),請進行舉報或認領(lǐng)

文檔簡介

一、單項選擇一個算法應(yīng)該是 D.A和算法指的是 計算機程 B.解決問題的計算方C.排序算 D.解決問題的有限運算序列與數(shù)據(jù)元素本身的形式、內(nèi)容、相對位置、個數(shù)無關(guān)的是數(shù)據(jù)的 A.結(jié) B.邏輯結(jié) C.算 D.操 B.順序結(jié)構(gòu)、鏈?zhǔn)浇Y(jié)構(gòu) 線性表采用鏈?zhǔn)綍r,節(jié)點的的地址 B.連續(xù)與否均C.必須是連續(xù) D.和頭節(jié)點的地址相連在下面的程序段中,對x的賦值語句的頻度為 FORi:=1 FORj:=1TO nDO2 D.O(log2程序段FOR FORj:=1TOiDOIF A[j]與A[j+1]對換其中n為正整數(shù),則最后一行的語句頻度在情況下是 A. B. C. D.intfact(int if(n<=0) n*fact(n-1) } )A. B. C. D.n-用鏈表表示線性表的優(yōu)點是 便于隨機存 C.便于插入與刪 D.?dāng)?shù)據(jù)元素的物理順序與邏輯順序相鏈表不具有的特點是 ) A.n- B. C. D.n-n的順序表示,搜索成功的平均搜索長度為(A. B. C.(n- D.將長度為n的單鏈表在長度為m的單鏈表之后的算法的時間復(fù)雜度為(A. B. C. D. B.head-C. D.head- 鏈?zhǔn)綏Ec順序棧相比,一個比較明顯的優(yōu)點是 插入操作更加方 C.不會出現(xiàn)棧空的情 D.刪除操作更加方來看,通常遞歸過程比非遞歸過程()。A.較 B.較 C.相 D.不則pi為 )A B.n= C.n- D. )A. B. C. D.棧序列是()。A. B.C. D.對于棧操作數(shù)據(jù)的原則是 )A.先進先 B.后進先 C.后進后 D.不分順棧和隊列的共同點是 ) B.都是先進后C.只允許在端點處插入和刪除元 D.沒有共同 )A. B. D.則執(zhí)行出對操作后其頭指針front指為()。 引起循環(huán)隊列隊頭位置發(fā)生變化的操作是A.出 B.入 C.取隊頭元 D.取隊尾元 二維數(shù)組A[12][18]采用列優(yōu)先的方法若每個元素各占 地址為150,則元素A[9][7]的地址為()A. B. C. D.B[]中,A[0][0]存入B[0]中,則A[8][5]B[]中()位置。A. B. C. D.若對n 階對稱矩陣A 素)依次存放于一維數(shù)組[1..(n(n+1))/2中則在B中確定aji<j的位置k的關(guān)系為( A.i*(i- B.j*(j- C. D. 樹中所有結(jié)點的度之和等于所有結(jié)點數(shù)加()A. C. D.在一棵具有n個結(jié)點的二叉鏈表中,所有結(jié)點的空域個數(shù)等于 )A. B.n- C. D.某二叉樹的先序序列和后序序列正好相反,則該二叉樹一定是()空或只有一個結(jié) B.高度等于其節(jié)點C.任一結(jié)點無左孩 D.任一結(jié)點無右孩h02的結(jié)點,則此類二叉樹中所包含的結(jié)點數(shù)至少為()。A. B.2h- C. D.33221的節(jié)點個數(shù)為()A. B. C. D.n,森林F中第一棵的結(jié)點個數(shù)是 ) 號為1,則編號為49的節(jié)點的左孩子編號為()。A B. C. D.下列圖示的順序結(jié)構(gòu)表示的二叉樹是(A樹最適合用來表示 )有序數(shù)據(jù)元 B.無序數(shù)據(jù)元C.元間具有分支層次關(guān)系的數(shù) D.元間無聯(lián)系的數(shù)在一個非空二叉樹的中序遍歷序列中,根結(jié)點的右邊 )只有右上的所有結(jié) B.只有右上的部分結(jié)C.只有左的上的部分結(jié) D.只有左上的所有結(jié)任何一棵二叉樹的葉結(jié)點在先序、中序和后序遍歷序列中相對次序 )A.不發(fā)生改 B.發(fā)生改 C.不能確 D.以上都不在有n個葉子結(jié)點的樹中,其結(jié)點總數(shù)為 )A.不確 B. C. D.2n-權(quán)值為{1,2,6,8}的四個結(jié)點構(gòu)成的樹的帶權(quán)路徑長度是()A. B. C. D.對一個滿二叉樹,m個樹葉,k個分枝結(jié)點,n個結(jié)點,則()A. B. C.m=k- D.ne條邊的無向圖的鄰接矩陣中,零元素的個數(shù)為()A. B. C.n2- D.n2-若采用鄰接矩陣翻一個n個頂點的無向圖,則該鄰接矩陣是一個 )A.上三角矩 B.稀疏矩 C.對角矩 D.對稱矩在一個圖中,所有頂點的度數(shù)之和等于所有邊數(shù)的 A. B. C. D.在一個有向圖中,所有頂點的入度之和等于所有頂點的出度之和的 )倍A. B. C. D.n個頂點的連通圖至少中含有 A.n- B. C. D.n個頂點的完全有向圖中含有 n-1條有向 B.n條有向C.n(n-1)/2條有向 D.n(n-1)條有向所有弧的時間復(fù)雜度是()。A. B. C. 在無向圖中定義頂點Vi域Vj之間的路徑為從Vi到達Vj的一個 )A.頂點序 B.邊序 C.權(quán)值總 D.邊的條由同一組關(guān)鍵字集合構(gòu)造的各棵二叉排序樹 下面哪一方法可以判斷出一個有向圖是否有環(huán)(回路)A.求節(jié)點的 B.拓撲排 C.求最短路 D.求關(guān)鍵路圖的廣度優(yōu)先搜索類似于樹的 )次序遍歷A.先 B.中 C.后 D.層在圖采用鄰接表時,求最小生成樹的Prim算法的時間復(fù)雜度為 A. B. C. D.<V2,V5>,<V3,V5>,<V3,V6>,<V4,V6>,<V5,V7>,<V6,V7>},G( 關(guān)鍵路徑是結(jié)點網(wǎng)絡(luò)中 ) 對關(guān)鍵字序列(56,23,78,92,88,67,19,34)進行增量為3的一趟排序的結(jié)果 ) B.C. D.則采用的方法是 A.直接選擇排 B.排 C.歸并排 D.快速排基準(zhǔn)得到的第一次劃分結(jié)果為()。 B.C. D.下列排序算法中不穩(wěn)定的是 A.直接選擇排 B.二分插入排 C.冒泡排 D.快速排 A.直接選擇排 B.直接插入排 C.快速排 D.冒泡排iLi,那么查找失敗到達失敗點時所做的數(shù)據(jù)比較次數(shù)是() ()A. B. C. D.衡量查找算法效率的主要標(biāo)準(zhǔn)是()元素的個數(shù)B.所需的量C.平均查找長度D.算法難易程適合對動態(tài)查找表進行高效率查找的組織結(jié)構(gòu)是()A.有序表B.分塊有序表C.二叉排序樹D.快速排序n個元素,可以構(gòu)造出的邏輯結(jié)構(gòu)有集合,線性表,樹,圖順序映象的特點是借助元素在器中的相對位置來表示數(shù)據(jù)元間的邏輯關(guān)系非順序映象的特點是借助是指示元素地址的指針表示數(shù)據(jù)元素之間的邏輯關(guān)系。任何一個算法的設(shè)計取決于選定邏輯結(jié)構(gòu),而算法的實現(xiàn)依賴于采用的結(jié)構(gòu)。在帶有頭結(jié)點的單鏈表中L中,第一個元素結(jié)點的指針 head可用p表示為 設(shè)單鏈表的結(jié)點結(jié)構(gòu)為(data,next),nextpxdatax的結(jié)點,指針py指向datay的新結(jié)點,若將結(jié)點y插入結(jié)點x之后,則需要執(zhí)行以下語句:py->next=px->next;px->next=py。 棧下溢是指 棧 出棧順序,相應(yīng)的P和D的操作串 循環(huán)隊列的引入,目的是為了克 假溢出 二位數(shù)組Am×n按行優(yōu)先順序在內(nèi)存中元素a00地址為loc(a00),每個元素在內(nèi)存中占d個字節(jié)元素aij的地址計算為 表 樹內(nèi)個結(jié)點的 最大 稱為樹的度一個二叉樹第5層節(jié)點最多 個已知完全二叉樹T的第5層只有7個結(jié)點,則該樹共 在一棵二叉樹中度為零的結(jié)點的個數(shù)為N0,度為2的結(jié)點的個數(shù)為N2,則有N0= 在圖中任何兩個結(jié)點之間都可能存在關(guān)系因此圖的數(shù)據(jù)元間時一種 對多的關(guān)系。在有向圖中,以頂點v為終點的邊的數(shù)目稱為v 入 一個無向圖有n個頂點,e條邊,則所以頂點的度數(shù)之和 2eT(24341633829207 2產(chǎn)生現(xiàn)象的兩個關(guān)鍵字稱為該散列函數(shù) 同義 在散列函數(shù)H(key)=keyMODp中,p應(yīng) 素 設(shè)哈希表長m=14,哈希函數(shù)H(key)=keyMOD11.表中已有4個結(jié)點;addr(15)=4,addr(38)=5,addr(61)=6,addr(84)=7,其余地址為空。如用二次探測再散列處理,關(guān)鍵字為49的結(jié)點的地址是 排序是屬 插 三、程序填空voidreverse(pointer/*h{pointer {q=p;p=p->next;q->next=h->next;h- } ∥鏈表未到尾就一直 ∥將當(dāng)前結(jié)點作為頭結(jié)點后的第一元素 reverse(linklist{p=null;q=L;{ ; }L=L- ∥暫存后 ∥待逆置結(jié) ∥頭指針仍為四、解答寫出隊滿的條件表達式寫出隊空的條件表達式設(shè)m=40,rear=13,quelen=19,求隊頭元素的位置寫出一般情況下隊頭元素位置的表達quelen==quelen==(13-19+40)%40=(rear-quelen+m)%B / A ABCABCDEFGHA,B,D,G,J,E,H,C,F,I,K,L中序序列:D,J,G,B,E,H,A,C,K,I,L,F寫出該二叉樹的后序序列畫出該二叉該二叉樹的形式如圖所示 BCEDF IJ 該二叉樹高度為:5造一棵樹,并求其路徑長度WPL,字符c的編碼。WPL=80c:001(不唯一BFS0123456789111212111 (3)ASLsucc (4)ASLunsucc設(shè)有一組關(guān)鍵字{9,01,23,14,55,20,84,27},采用哈希函數(shù):H(key)=keymod7,012345678911123412以關(guān)鍵字27為例:H(27)=27%7=6()H1=(6+1)%10=7( H=(6+22)%10=0( H 所以比較了4次 快速排序:(21,13,17,)1330,60,58,28,30*,90堆排序:歸并排序按層遍歷 (1721 60 ( 58 四、算法設(shè)計題(10分voidtest(int{intx;if(x=0)sum=0else{test(sum);sum+=x;}} voidmain() (1分){intx,sum=0,top=0,s[]; whiles[++top]:=ascanf(“%d”,&x(3while(top)}structedgenode intadjvex; } voidmatritolist(intg[][],adjlistgl,intn edgenode*p,for(inti=0i<n;i++) for(inti=0;i<n;i++)for(intj=0;j<n; (g[i][j]!=0p=(edgenode*)malloc(sizeof(edgenode)); }} while((ch=getchar( }}xxet^tvoidadd_poly(Lnode*pa,Lnode{Lnode int while((p!=NULL)&&((q!=NULL)) (p->exp<q- pre=p;p=p->next; if(p->exp==q->exp){x=p->coef+q-if(x!=0){p->coef=x; {pre->next=p->next;(p);}

pre=q;q=u;}}if(q!=NULL) }typedefstructnode strunctnode voidfunction(linklist*head,elemtypex while(p!=NULL)&&(p->data!=x printf(“thereisnothisnode::\n”); q->next=p->next; (p); }void while(!Stackempty(s)) } if( }}voidFastTransposeSMatrix(MatrixM,Matrix&T) if(T.tu) for for(t=1;t<=M.tu;++t) forfor(p=1;p<=M.tu;++p) col=M.item[p].j;T.item[q].j=M.}}return}第四個for循環(huán),轉(zhuǎn)置過程;++cpot[col]:語句的功能是當(dāng)每一列進行一次轉(zhuǎn)置后,其位置向后 1typedefstruct char structBiTNode }voidCreateBiTree(BiTNode char if(ch==‘‘) T=(BiTNodeGwhile}}typedefstruct charstructBiTNode}voidinorder( }} voidfuncgraph(MGraph inti,j,k,w; charv1,v2;printf("Inputvexnum& printf("InputVertices:");forfor(i=0;i<G.vexnum;i++)for printf("InputArcs(v1,v2&}}第二個for循環(huán),初始化鄰接矩陣; );線性表的鏈?zhǔn)浇Y(jié)構(gòu)優(yōu)于順序結(jié)構(gòu)。棧和隊列也是線性表。如果需要,可對它們中的任一元素進行操作。字符串是數(shù)據(jù)對象特定的線性表。=P->next;一個無向圖的連通分量是其極大的連通子圖。鄰接表可以表示有向圖,也可以表示無向圖。遍歷。T 時間復(fù)雜度為0(n2);(d)方法所有情況下時間復(fù)雜度均為0(nlogn)。a.插入排 b.排 c.快速排 d.堆排不 下列二叉樹中,(a) )適用于查找有序單鏈表。a. 找d.哈希查找采用(a)方法。 a.log2m b.└log2m┘+1 c.m/2d.┌m/2┐-1 e.┌m/2┐ 56,34,58,26,79,52,64,37,28,84,57下列選擇中(c)(b) (d)(a)是初始堆(大堆頂)84,79,64,37,57,52,58,26,28,34,5628,34,57,26,56,52,58,37,79,84,6428,34,37,26,52,56,64,79,58,84,5752,34,64,84,56,26,37,57,58,28,7934,56,26,58,52,64,37,28,79,57,84三.填空題(每題2分共20分)2.已知某二叉樹的先序遍歷次序為afbcdeg,中序遍歷次序為cedbgfa。設(shè)有二維數(shù)組A5x7,每一元素用相鄰的4個字節(jié),器按字節(jié)編是(144);按列時,元素A14的第一個字節(jié)的地址是(184)。StatusPreordertraverse(BitreeT,Status(*Visit)(emtypeInitstack(S); Push(S,T);While(!stackempty(S)){While(gettop(S,p)&&p){visit(p->data);push(S,p->lchild;}Pop(S,p); }return四.簡答題(每 分 HashH(K)=Kmod130用二次探測再散列處理,給出關(guān)鍵字(23,34,56,24,75,12,49,5

溫馨提示

  • 1. 本站所有資源如無特殊說明,都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請下載最新的WinRAR軟件解壓。
  • 2. 本站的文檔不包含任何第三方提供的附件圖紙等,如果需要附件,請聯(lián)系上傳者。文件的所有權(quán)益歸上傳用戶所有。
  • 3. 本站RAR壓縮包中若帶圖紙,網(wǎng)頁內(nèi)容里面會有圖紙預(yù)覽,若沒有圖紙預(yù)覽就沒有圖紙。
  • 4. 未經(jīng)權(quán)益所有人同意不得將文件中的內(nèi)容挪作商業(yè)或盈利用途。
  • 5. 人人文庫網(wǎng)僅提供信息存儲空間,僅對用戶上傳內(nèi)容的表現(xiàn)方式做保護處理,對用戶上傳分享的文檔內(nèi)容本身不做任何修改或編輯,并不能對任何下載內(nèi)容負責(zé)。
  • 6. 下載文件中如有侵權(quán)或不適當(dāng)內(nèi)容,請與我們聯(lián)系,我們立即糾正。
  • 7. 本站不保證下載資源的準(zhǔn)確性、安全性和完整性, 同時也不承擔(dān)用戶因使用這些下載資源對自己和他人造成任何形式的傷害或損失。

評論

0/150

提交評論