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

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

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

2

0

9

0

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

TypedefStruct intdata;structnode}BiTNode,*voidCountLeaf(BiTree