數(shù)據(jù)結構與算法復習題

1、考生注意：1、學號、姓名、 年級、專業(yè)等應填 寫準確“2、考試作弊 者，員令?？?，成 績作廢。廣西民族大學成人高等教育考試復習題課程名稱：數(shù)據(jù)結構與算法考試fi期：20年 月考核時長:120分伸得分評卷人答案教學點考核方式：開卷試卷類別：b卷年級20級層次形式高起專命題教師張桂芬教研室主任一、單項選擇題。(每題2分，共20分)1. 以下程序段中帶硝句的執(zhí)行頻度和算法的時間復雜度分別是().for (i=l; i<= n ; +i )for (j=i+l; j<=n; +j) 0 mi;a. n(n-l)/2： n2 b. n2； n2c. n(n-l)/2： n d. n； n2.

2、 下列排序方法中是秘定排序的是(b >.a.希爾排序b.歸并排序c.快速排序d.堆排序3. 設輸入序列為字符a、b、c,則經(jīng)過棧的作用后可以得到(c )種不同的輸出序列。a.3b. 1c. 5d. 64. 數(shù)組a|7 |6的每個元素占5個字節(jié).將其以行為主序存依在起始地址為100()的內(nèi)存單元 中.則元素a 5 4的地址是< c )。a.1165b.1180c. 1170d.12105. 對于順序存儲的線性表，訪問元素和插入元素的時間復雜度分別為：()。a. o(n) , o(n) b. o(n) . 0(1) c. 0(1) . 0(1) d. 0(1) . o(n)6. 在單鏈

3、表指針為p的結點之后插入指針為，的結點，正確的操作是( b 九a. p->next=s： s->next=p->ncxtb. s->nexl=p->next： p->next=sc. p->ncx(=s： p->ncxt=s->ncxtd. p->ncxt=s->ncxt： p->ncxt=s7. n個頂點的有向圖中，含有向邊的數(shù)目最多為()。a n-1b. nc. n(n-l)/2d. n(n-l)8. 對下面有向圖給出了四種可能的拓撲序列，其中錯誤的是(c ).a. l 5. 2, 6, 3, 4b,5, 6, 2.

4、3, 4c. 5, 1， 6， 3, 4, 2d. 5, l 2, 6, 4, 39. 若一棵二叉樹具有10個度為2的結點，5個度為1的結點，則葉子結點數(shù)為(ba. 9 b. 11c. 15 d.不確定10. 適用于折半查找的表的存儲方式及元素排列要求為()<>a順序方式存飭，元素有序 b.順序方式存儲，元素無序c.鏈接方式存儲.元素有序d.鏈接方式存儲.元素無序二、填空題。(每空1分，共8分)1. 度量算法效率可通過時間復雜度和兩方面進行。2. 迷宮問題是一個回溯控制的問我，最好使用_結構來記錄路徑數(shù)據(jù)。3. 設字符sl= abcde s2= aaa 則執(zhí)行運j? strinse

5、rt(s 1. strlength(s2). s2)；sl=_'abaaacdc、:若串 s2 采用 sstring 存儲結構，則 s20=4. 進行哈希查找的基木思想是由關蝕字決定記錄的存儲地址。5. 設某棵二叉樹中有2000個結點，則該二叉樹的最小深度為6. 采用順序查找方法查找長度為n的表時，等概率情況卜的平均查找長度為：(nq 27. 在隊列中存取數(shù)據(jù)的原則是。三、簡答題。(每題6分，共12分)1 .試分別畫出具有3個結點的樹和3個結點的二叉樹的所有不同形態(tài)。答：具有3個結點的樹有2種形態(tài)：具有3個結點的二叉樹有5種形態(tài)：2. 一個“好”的算法應考慮達到哪些目標？答：算法是對特

6、定問題求解步驟的種描述它是指令的有限序列。（2分 它的五個重要特性是:<1）有窮性：（2）確定性：（3）可行性：（4）零個或多個輸入：四、應用題。（每題12分，共36分）1.已知圖g如請回答以下問題:（d從頂點1出發(fā),用普里姆算法構造最小生成樹，請寫出構樹的邏輯步驟.wpl= (10+14) *2+ (6+7+8) *3+ (2+3) *4 =24*2+21*3+5*4=48+63+20=131(4 分)3.己知棵樹的雙親表示法如下，回答以下問題:u= ,v.u=(23,45 tf>4>(1)u=1,2 ,v.u=3,4§ ,te=(1,2)(2)（每步2分，共8分

7、）u=1,2,4,5j ,v-u= <bte=(1,2),(1,4),(2,5),(5)u=*，、-u=3,5te=(1,2),(1,4)（2）寫出圖g的鄰接矩陣。u=1,2,4,5 ,v.u=3te=(1,2),(1,4),(2,5)2.有7個帶權站點.其權值分別為3. 7,8,2,6,10, 14：（i）畫出以它們?yōu)槿~子結點的哈夫曼樹（樹中左孩子結點的權值不大丁右孩子結點的權值）： 計算出帶權路徑長度wpl。解：哈夫曼樹為:（8分）<2）寫出該樹的前序和后序遍歷序列。 解：該樹的前序遍歷序列：abefcgdh （2分）五、算法閱讀題。（共14分）1 .假設以帶頭結點的單鏈表表示

8、線性表.閱讀卜列算法fl,并回答問題:void fklinklist l） （p=l;while （p && p->next）q = p->next;2129p->next =q->next; p =q->next; fnre(|);設單鏈表 l 為：e4|h al a2 a3 « a4 a5 一 a6 “卜7 囚 清畫出執(zhí)行fl(l)；后的單鏈表l：e*1riirn*i 孩41 bn亦|(6 分)2.算法f2功能：在有序表st中折半查找關鍵字等于key的數(shù)據(jù)元素，請叵i答卜列問題：int f2(<istab!c st, keytype key) low=l; high=st.length;while (low<=high) (mid= (l»w+hmh) /2:if ( key=st.elem|mid|.key)return mid;else if (key< slelemmid.key) high=mid-l;else low=mid+l;return 0;)(i)請完成算法填空。(每空2分，共8分)六、算法設計題。(共10分)1.以順序存儲結構表示線性表，編寫算法，求出線性表中元素的址大值。函數(shù)原型為：status s(