數(shù)據(jù)結(jié)構(gòu)與算法設(shè)計(jì)考研復(fù)習(xí)模擬題及答案電子工業(yè)

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