數(shù)據(jù)結(jié)構(gòu)講義本科課件試題2009final

1、西 安 電 子 科 技 大 學(xué)時(shí)間分鐘試題1.形式：閉卷；2。日期：20 年 月日 3.本試卷共 四 大題，滿分 100 分。班級學(xué)號 任課教師 一. 選擇題（15 小題，共 30 分）1. 邏輯上通常可以將數(shù)據(jù)結(jié)構(gòu)分為（A.動態(tài)結(jié)構(gòu)和靜態(tài)結(jié)C.線性結(jié)構(gòu)和非線性結(jié)構(gòu)）.順序結(jié)構(gòu)和鏈?zhǔn)浇Y(jié)構(gòu)D.初等結(jié)構(gòu)和組合結(jié)構(gòu)2. 在下列對順序表進(jìn)行的操作中，算法時(shí)間復(fù)雜度為 O(1)的是（A.第 i 個元素的前驅(qū)（1< i £ n ）后一個新元素(1£ i £ n )B.在第 i 個元C.刪除第 i 個元素(1£ i £ n ) D.對順序表中元素進(jìn)行排

2、序3. 一個棧的輸入序列為 123n，若輸出序列的第一個元素是 n，輸出第 i（1<=i<=n）個元素是（A. 不確定4. 如果將矩陣）。B. n-i+1C.iD. n-iAn× n的每一列看成一個子表，整個矩陣看成是一個廣義表 L，即L=(a11,a21,an1),( a12,a22,an2),，（a1n,a2n,ann）),并且可以通過求表頭 head 和求表尾 tail 的運(yùn)算求取矩陣中的每一個元素，則求得 a21 的運(yùn)算是（）A. head (tail (head (L)C. tail (head (tail (L)B. head (head(head(L)D.

3、head (head (tail (L)第1頁 共 頁題號一二三四五六七十總分分?jǐn)?shù)第2頁 共 頁5. 設(shè)森林 F 中有三棵樹，第一、第二、第三棵樹的結(jié)點(diǎn)個數(shù)分別為 M1，M2 和 M3，則與森林 F 對應(yīng)的二叉樹根結(jié)點(diǎn)的右子樹上的結(jié)點(diǎn)個數(shù)是（）。AM1BM1+M2CM3DM2+M36. 對下列關(guān)鍵字序列進(jìn)行快速排序時(shí)，所需進(jìn)行比較次數(shù)最少的是（）A.（1，2，3，4，5，6，7，8） C.（4，3，8，6，1，7，5，2）7. 以下程序的時(shí)間復(fù)雜度為（for（i=0；i<m；i+） for（j=0；j<t；j+）cij=0； for（i=0；i<m；i+）for（j=0；j&

4、lt;t；j+）for（k=0；k<n；k+）B.（8，7，6，5，4，3，2，1）D.（2，1，5，4，3，6，7，8）cij=cij+aik*bkj；A.O（m+n×t）C.O（m×n×t）B.O（m+n+t）D.O（m×t+n）8.對一棵有 100 個結(jié)點(diǎn)的完全二叉樹按層序編號，則編號為 49 的結(jié)點(diǎn)，它的左孩子的編號為（A.99 C.97）B.98D.509.A. 3C. 5的有向無環(huán)圖可以得到的拓?fù)湫蛄械膫€數(shù)是（B. 4D. 6）10.已知含6個頂點(diǎn)(v0，v1，v2，v3，v4，v5)的無向圖的鄰接矩陣，則從頂點(diǎn)v0 出發(fā)進(jìn)行深度優(yōu)先遍

5、歷可能得到的頂點(diǎn)A.(v0，v1，v2，v5，v4，v3) B.(v0，v1，v2，v3，v4，v5) C.(v0，v1，v5，v2，v3，v4)D.(v0，v1，v4，v5，v2，v3)序列為()11.已知用某種排序方法對關(guān)鍵字序列（51，35，93，24，13，68，56，42，77）進(jìn)行排序時(shí)，前兩趟排序的結(jié)果為（35，51，24，13，68，56，42，77，93）（35，24，13，51，56，42，68，77，93）所采用的排序方法是（）A.排序B. 冒泡排序D. 歸并排序C. 快速排序12.已知棧的最大容量為 4。若進(jìn)棧序列為 1，2，3，4，5，6，且進(jìn)棧和出?？梢源┎暹M(jìn)行,則

6、可能出現(xiàn)的出棧序列為（A.5，4，3，6，1，2 C.3，2，5，4，1，6）B.2，3，5，6，1，4 D.1，4，6，5，2，313.在長度為32 的有序表中進(jìn)行二分查找時(shí)，所需進(jìn)行的關(guān)鍵字比較次數(shù)最多為()A. 4C. 6B.5D.714.定義二維數(shù)組 A18，010，起始地址為 LOC，每個元素占 2L 個單元，在以行序?yàn)橹餍虻姆绞较?，某?shù)據(jù)元素的地址為 LOC+50L，則在以列序?yàn)橹餍虻姆绞较?，該元素的A. LOC+28LC. LOC+50L地址為（）B. LOC+36LD. LOC+52L15已知串 s=aabacbabcaccab，串 t1=abc,串 t2=cba,函數(shù) ind

7、ex(s,t)的返回值為串 t 在串 s 中首次出現(xiàn)的位置，則能求得串a(chǎn)bcacba的操作序列為（ 注：所有與位置相關(guān)的值都從 0 開始計(jì)數(shù)A. substr (s1,s,6,index(s,t1); substr (s2,s,index(s,t1),1);strcat(s1,s2);B. substr (s1,s,7,index(s,t1); substr (s2,s,index(s,t1),1);strcat(s2,s1);C. substr(s1,s,6,index(s,t2); substr(s2,s,index(s,t2),3);strcat(s1,s2);D. substr(s1,

8、s,6,index(s,t2); substr(s2,s,index(s,t2),3);strcat(s2,s1);）第3頁 共 頁第4頁 共 頁二. 填空題（10 小題，共 20 分）1. 已知串 S=aaaaba,則 KMP 算法的 Next 數(shù)組值為。2. 設(shè)某算法的計(jì)算時(shí)間可用遞推關(guān)系式 T(n) = 2T(n/2) + n 表示，則該算法的時(shí)間復(fù)雜度為。3.已知指針p 和 q 分別指向某單鏈表中第一個結(jié)點(diǎn)和最后一個結(jié)點(diǎn)。假設(shè)指針 s 指向另一個單鏈表中某個結(jié)點(diǎn)，則在 s 所指結(jié)點(diǎn)之后為。上述鏈表應(yīng)執(zhí)行的語句4.冒泡排序最好的時(shí)間復(fù)雜度為，平均時(shí)間復(fù)雜度為，是一種穩(wěn)定的排序算法。5.已

9、知循環(huán)隊(duì)列的空間大小為 m，隊(duì)頭指針 front 指向隊(duì)頭元素，隊(duì)尾指針 rear 指向隊(duì)尾元素的下一個位置，則在隊(duì)列不滿的情況下，隊(duì)列的長度是。6. n 個頂點(diǎn)且含有環(huán)路的無向連通圖中，至少含有條邊。7. 從空樹起，依次關(guān)鍵字 1l，27，35，48，52，66 和 73 構(gòu)造所得的二叉排序樹，在等概率查找的假設(shè)下，查找時(shí)的平均查找長度為。 8用希爾排序方法對關(guān)鍵字序列（20，25，12，47，15，83，30，76）進(jìn)行排序時(shí)， 增量為 3 的一趟排序的結(jié)果為。9.已知一組關(guān)鍵字為15，36，28，97，24，78，47，52，13，86，其中每相鄰兩個關(guān)鍵字 個有序子序列。 對這些子序列

10、進(jìn)行一趟兩兩歸并的結(jié)果是 。10.假設(shè)一棵完全二叉樹含 1000 個結(jié)點(diǎn),則其中度為 2 的結(jié)點(diǎn)數(shù)為。三. 簡答題（4 小題，共 30 分）1.(6 分)由森林轉(zhuǎn)換得到的對應(yīng)二叉樹序序列。，寫出原森林中第三棵樹的前序序列和后ABELCFGKDHIJ2.(9 分)假定一個待散列的線性表為（32，75，63，48，94，25，36，18，70），散列地址空間為0.10，若散列函數(shù)為 H(key)=key%11，并采用拉鏈法處理，試給出它們對應(yīng)的散列表。并計(jì)算等概率查找情況下查找度。和查找失敗的平均查找長3.(6 分)設(shè)有向圖鄰接表定義如下；typedef structVertexNode adjl

11、istMax VertexNum;int n,e;ALGraph;/圖的當(dāng)前頂點(diǎn)數(shù)和弧數(shù)/鄰接表類型其中頂點(diǎn)表結(jié)點(diǎn) VertexNode 結(jié)構(gòu)為：邊表結(jié)點(diǎn) EdegNode 結(jié)構(gòu)為：閱讀下列算法 f，并回答問題： (1)已知有向圖 G 的鄰接表(2)簡述算法 f 的功能。void dfs (ALGraph *G,int v) EdgeNode * p; visitedv=TRUE;,寫出算法 f 的輸出結(jié)果;printf(%c,G>adjlistv·vertex);for(p =G>adjlistv)·firstedge; p; p=p>next) if(

12、! visitedp>adjvex) dfs (G, p>adjvex);void f (ALGraph *G)第5頁 共 頁adjvexnextvertexfirstedge第6頁 共 頁int v,w;for(v=0; v <G>n; v +) for(w=0;w<G>n; w+)visitedw=FALSE; printf(%d: ,v);dfs(G,v);printf(n);4(9 分)已知序列（21,41, 7, 43, 58, 63, 29, 8）(1) 寫出增量為 3 的第一趟希爾排序結(jié)果；(2) 寫出以第一元素為樞軸的快速排序第一趟結(jié)果；(3

13、)該序列是否為堆。若不是，將其調(diào)整為小頂堆，畫出調(diào)整完的小頂堆。四算法設(shè)計(jì)題（2 小題，共 20 分）1.(10 分)假設(shè)以單鏈表表示線性表,單鏈表的類型定義如下: typedef struct node DataType data; struct node *next; LinkNode, *LinkList;編寫算法,將一個頭指針為 head 且不結(jié)點(diǎn)的單鏈表改造為一個含頭結(jié)點(diǎn)且頭指針仍為 head 的單向循環(huán)鏈表，并分析算法的時(shí)間復(fù)雜度。2. (10 分)假設(shè)二叉排序樹以中序后繼線索鏈表作為結(jié)構(gòu)，編寫按非遞減順序輸出該二叉排序樹中所有大于 a 且小于b 的關(guān)鍵字的算法，并分析算法的時(shí)間復(fù)雜度。相關(guān)數(shù)據(jù)結(jié)構(gòu)定義如下/元素類型typedef structint key;/關(guān)鍵字InfoTyp