數(shù)據(jù)結(jié)構(gòu)試復(fù)習(xí)題

1、考生注意：1、學(xué)號、姓名、 年級、專業(yè)等應(yīng)填 寫準(zhǔn)確“2、考試作弊 者，責(zé)令停考，成 績作廢。廣西民族大學(xué)成人高等教育考試復(fù)習(xí)題教學(xué)點課程名稱：數(shù)據(jù)結(jié)構(gòu)考試日期：20 年 月 考核時長：120分鐘 考核方式：開卷試卷類別：b卷得分評卷人答案20級層次形式高起專命題教師張桂芬教研室主任一、單項選擇題。（每題2分，共20分）1.以下程序段中帶&語句的執(zhí)行頻度和算法的時間夏雜度分別是（for (i=l; i<= n ; +祈)lor (j=i+l; j<=n;a. n(n-l)z2； n2 b. n2； n22.下列排序方法中是槍定挎序的是（a.希爾排序b.歸并排序+j) 0 m

2、+；).c.快速排序d.堆排序3.改輸入序列為字符,4、b、c,則經(jīng)過棧的作用后可以得到（a.3c. 5d. 6）種不同的輸出序列。4.數(shù)組a|7 6的每個元素占5個字節(jié)，將其以行為主序存儲在起始地址為100（）的內(nèi)存單元 中.則元素a 5 4的地址是（ca.1165b.ii80c. 1170d.12i05.對于順序存儲的線性表，訪問元素和插入元素的時間夏雜度分別為：（a. o(n) , o<n) b. o(n) 0(1)c. 0(1) . 0(1)6.在單鏈表指針為p的結(jié)點之后插入指針為s的結(jié)點，正確的操作是（a. p->next=s： s->next=p->ncx(

3、 b. s->next=p->next：c- p->ncxt=s： p->ncx（=s->ncxt d. p->ncxt=s->ncxt：7. n個頂點的有向圖中，含有向邊的數(shù)目最多為（dd. 0(1) , o(n)9. 若一棵二叉樹具有10個度為2的結(jié)點，5個度為1的結(jié)點，則葉子結(jié)點數(shù)為（ba. 9 b. 11c. 15 d.不確定10. 適用于折半查找的表的存儲方式及元素排列要求為（）。a順序方式存儲，元素有序 b.順序方式存儲，元素?zé)o序c.鏈接方式存儲.元素有序 d,鏈接方式存儲.元素?zé)o厚二、填空題。（每空1分，共8分）1. 度量算法效率可通過時

4、間復(fù)雜度和兩方面進(jìn)行。2. 迷宮問題是一個回溯控制的何題，最好使用 _棧一結(jié)構(gòu)來記錄路徑數(shù)據(jù)。3. 設(shè)字符sl= abcde'. s2='aaa、，則執(zhí)行運(yùn)算 strlnseiksl. strlength（s2）. s2）；sl=_ abaaacdc、_:若串 s2 采用 sstring 存儲結(jié)構(gòu)，s2（0|=”1.進(jìn)行哈希杏找的灰木思擔(dān)是由關(guān)鍵字決定記錄的存儲地址。5. 設(shè)某棵二叉樹中有2000個結(jié)點，則該二叉樹的最小深度為o6. 采用順序查找方法查找k度為n的表時,等概率情況下的平均查找k度為：（nh）u27. 在從列中存取數(shù)據(jù)的原則是。三、簡答題。（每題6分，共12分）1

5、.試分別畫出具有3個結(jié)點的樹和3個結(jié)點的二叉樹的所有不同形態(tài)。答：具有3個結(jié)點的樹有2種形態(tài)：具有3個結(jié)點的二叉樹有5種形態(tài)：p->next=sp->ncxt=sd. n(n-l)8.對下面有向圖給出了四種可能的拓?fù)湫蛄?，其中錯誤的是（a. i.52,6.3.4b. 1,5,6.2.3,4c. 5,1,6.3,4,2d. 5,l2,6.4.32. 一個“好”的算法應(yīng)考慮達(dá)到哪些目標(biāo)？答：算法是對特定問距未解步驟的種描述它是指令的有限序列。（2分） 它的五個至要特性是:（1）有窮性:<2>確定性：（3）可行性：（4）零個或多個輸入：四、應(yīng)用題。（每題12分，共36分）1.

6、已知圖g如卜，請同答以卜問題：（1）從頂點1出發(fā)，用普里姆算法構(gòu)造最小生成樹，請寫出構(gòu)樹的邏輯步驟,（2）計算出帶權(quán)路徑長度wpl。解：哈夫曼樹為:（8分）u=1,2 ,vu=3,心u=1 ,v.u=23,45te=(l2)> 1e=4>>(1)(2)u=1,2,4,5 ,v.u=3te=(1,2),(1,4),(2,5)u=* w)te=(1,2),(1,4)(4)u=1,2,4,5j ,v-u= <bte=(1,2),(1,4),(2,5),(5)(5)（每步2分，共8分）<2）寫山圖g的鄰接矩陣。的:vl v2 v3 v4 v50 12 34v1v2v3v4

7、v501234oo3oo5oo3oo6oo5oo6oo725oo78oo（4分）2.有7個帶lu）州出以它們?yōu)槿~子結(jié)點的哈夫地椅（樹中左孩子結(jié)點的權(quán)值不大于右孩子結(jié)點的權(quán)值）：wpl= (10+14) *2+ (6+7+8) *3+ (2+3) *4=24*2+21*3+5*4=48+63+20=131(4 分)01234567dataabcdefghparent-100011233.己知棵樹的雙親表示法如下,回答以下問題:<1）畫出該樹及其對應(yīng)的二叉樹。 解：樹hd二叉樹(4分)對應(yīng)的二叉村（4分）五、算法閱讀題。（共14分）1.假設(shè)以帶頭堵點的單鏈表表示線性表,閱讀下列算法fi.井回

8、答問題:void rklinklist l） （p=l;status sqlistmax(sqlist l, elemtype &max)(if (l.length=o) return error; (1分)max= l.elem0; (2 分)while (p && p->next)(q = p->next;|>->next =q->next;p =q->next;for(i= 1 ;i<=l.length-1 ;i+) (3 分)free(q);設(shè)單鏈表 l 為：而 請儷出執(zhí)行fl (l)；后的單鏈表l：|4 a21 h 4

9、1+1 a6 |人|(6 分)2.算法f?功能：在有序表*中折半查找關(guān)鍵字等于key的數(shù)據(jù)元素.請回答下列何題：int f2(sstable st key type key) low=l; highest, length;while (lom<=high) mid=;if ( key=st.elem|mid.key)return mid;else if (kcy< $lelemmid.key) high=mid-l;else low=mid+l：return 0;)(1) 請完成算法填空.(2) sl=( 5. 13, 19, 21, 37, 56. 64 , 75 , 80, 96)：求 f2(st, 21)=:sl=(5. 13, 19, 21, 37, 56,