數(shù)據(jù)結(jié)構(gòu)復(fù)習(xí)-往年試卷參考答案

試卷編號 ）數(shù)據(jù)結(jié)構(gòu) 課 課程類別：題—二三四五六七八九十總題題—二三四五六七八九十總題得考生注意事項(xiàng)：1、本試卷共6頁，總分 分，考試時間 一、選擇題(2分，共30分計(jì)算機(jī)算法指的是（ 計(jì)算方 B.排序方C.解決問題的步驟序 D.調(diào)度方算法的計(jì)算量的大小稱為計(jì)算的（B效 B.復(fù)雜 C.現(xiàn)實(shí) D.難在下面的程序段中，對x（Cfor(i=1;i<=n;i++)for(j=1;j<=n;j++)2 D．O(log2線性表是具有n個（ （n>0表元 B．字 C．?dāng)?shù)據(jù)元 D．?dāng)?shù)據(jù)ps

B專業(yè)班級學(xué)學(xué)生簽專業(yè)班級學(xué)學(xué)生簽在循環(huán)隊(duì)列中用數(shù)組A[0..m-1]存放隊(duì)列元素其隊(duì)頭和隊(duì)尾指針分別為和rear，則當(dāng)前隊(duì)列中的元素個數(shù)是 D(front-rear+1)% B.(rear-front+1)%C．(front-rear+m)% D.(rear-front+m)%棧和隊(duì)都是（ 順序的線性結(jié) B.鏈?zhǔn)降姆蔷€性結(jié)C.限制存取點(diǎn)的線性結(jié) D.限制存取點(diǎn)的非線性結(jié)某堆棧的輸入序列為a,b，c，d,下面的四個序列中，不可能是它的輸出序列的是（DA. B.b, C.c,d，b, D.d,廣義表A=(a,b,(c,d),(e,(f,g))),則下面式子的值為 DA. B. C. D.在數(shù)組A中，每一個數(shù)組元素A[i][j]占用3個字，行下標(biāo)i從1到8，列下標(biāo)j從1到10。所有數(shù)組元素相繼存放于續(xù)的空間中，則存放該數(shù)組至少需要的字?jǐn)?shù)是（CA80B100C240D若一棵二叉樹具有10個度為2的結(jié)點(diǎn)，5個度為1的結(jié)點(diǎn)，則度為0的結(jié)點(diǎn)個數(shù)是（B） B．11C．15D．在有n個結(jié)點(diǎn)的二叉鏈表中，值為非空的鏈域的個數(shù)為(A) 由權(quán)值分別為11，8，6，2，5的葉子結(jié)點(diǎn)生成一棵樹，它的帶權(quán)路徑 A. C. D.下列哪一種圖的鄰接矩陣是對稱矩陣 有向圖B．無向圖C．AOVD．AOE采用順序查找方法查找長度為n B (n- 二、判斷題(1分，共10分?jǐn)?shù)據(jù)元素是數(shù)據(jù)的最小單位。( 線性表就是順序的表。( 為了很方便的插入和刪除數(shù)據(jù)，可以使向鏈表存放數(shù)據(jù)。 棧和隊(duì)列的方式，既可以是順序方式，又可以是鏈?zhǔn)椒绞剑?一個廣義表的表頭為空表，則此廣義表亦為空表。（ （×深度為K的二叉樹中結(jié)點(diǎn)總數(shù)≤2k-1 二叉樹的遍歷只是為了在應(yīng)用中找到一種線性次序（ 任何有向圖的結(jié)點(diǎn)都可以排成拓?fù)渑判?，而且拓?fù)湫蛄胁晃ㄒ唬?關(guān)鍵路徑是AOE網(wǎng)中從源點(diǎn)到終點(diǎn)的最長路徑（ 三、填空題(2分，共20分?jǐn)?shù)據(jù)結(jié)構(gòu)中評價(jià)算法的兩個重要指標(biāo)是算法的時間復(fù)雜度和空間復(fù)雜 n-i+1 的特點(diǎn)是利用指 來表示數(shù)據(jù)元間的邏輯關(guān)系INDEX‘DATASTRUCTURE‘STR）= 一棵具有257個結(jié)點(diǎn)的完全二叉樹，它的深度為 一棵完全二叉樹有900個結(jié)點(diǎn)，則共 個葉子結(jié)點(diǎn)由一棵二叉樹的前序序列和中序序列已知一無向圖G=（V，E），其中V={a,b,c,d,e}E={(a,b),(a,d),(a,c),(d,c),(b,e)}現(xiàn)用某一種圖遍歷方法從頂點(diǎn)a開始遍歷abecd，則采用的是深度優(yōu)先遍歷方法。對于一個具有nen-1四、應(yīng)用題（共３０分１.請讀下列程序，該程序是在單鏈表中刪除一個結(jié)點(diǎn)的算法，（6）voiddemo2(LinkListhead,ListNode{//head是結(jié)點(diǎn)的單鏈表，刪除P指向的結(jié)ListNodewhile(q&&q- q=q->next;（2if(!q) Error(“*pnotinhead”);q->next=p- （2 （2}已知一棵二叉樹的前序遍歷的結(jié)果是ABECDFGHIJ,中序遍歷的結(jié)果是EBCDAFHIGJ,試畫出與其對應(yīng)的二叉樹(4分)，并給出這棵二叉樹的后序遍歷序列(2分)。ABABFECGDHJI(4分這棵二叉樹的后序遍歷序列為： （2分GHIAJBEGHIAJBEKCFGDHIJKABABCDEF寫出它的鄰接矩陣（2分8152345 67用姆算法求出最小生成樹(要求從頂點(diǎn)8152345 67 ８５ 012

2

0

9

0

(2分（4分AOE（2分（2分參考答案：(1)此工程最早完成時間 ，關(guān)鍵路徑為(3)①②③④⑤⑥00五、算法設(shè)計(jì)題（共1０分1.編寫遞歸算法，計(jì)算二叉樹中葉子結(jié)點(diǎn)的數(shù)目。已知二叉樹

TypedefStruct intdata;structnode}BiTNode,*voidCountLeaf(BiTree