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

1、考生注意：1、學(xué)號(hào)、姓名、 年級(jí)、專業(yè)等應(yīng)填 寫準(zhǔn)確“2、考試作弊 者，責(zé)令?？迹?績(jī)作廢。廣西民族大學(xué)成人高等教育考試復(fù)習(xí)題教學(xué)點(diǎn)課程名稱：數(shù)據(jù)結(jié)構(gòu)考試日期：20 年 月 考核時(shí)長(zhǎng)：120分鐘 考核方式：開(kāi)卷試卷類別：b卷得分評(píng)卷人答案20級(jí)層次形式高起專命題教師張桂芬教研室主任一、單項(xiàng)選擇題。（每題2分，共20分）1.以下程序段中帶&語(yǔ)句的執(zhí)行頻度和算法的時(shí)間夏雜度分別是（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)過(guò)棧的作用后可以得到（a.3c. 5d. 6）種不同的輸出序列。4.數(shù)組a|7 6的每個(gè)元素占5個(gè)字節(jié)，將其以行為主序存儲(chǔ)在起始地址為100（）的內(nèi)存單元 中.則元素a 5 4的地址是（ca.1165b.ii80c. 1170d.12i05.對(duì)于順序存儲(chǔ)的線性表，訪問(wèn)元素和插入元素的時(shí)間夏雜度分別為：（a. o(n) , o<n) b. o(n) 0(1)c. 0(1) . 0(1)6.在單鏈表指針為p的結(jié)點(diǎn)之后插入指針為s的結(jié)點(diǎn)，正確的操作是（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個(gè)頂點(diǎn)的有向圖中，含有向邊的數(shù)目最多為（dd. 0(1) , o(n)9. 若一棵二叉樹(shù)具有10個(gè)度為2的結(jié)點(diǎn)，5個(gè)度為1的結(jié)點(diǎn)，則葉子結(jié)點(diǎn)數(shù)為（ba. 9 b. 11c. 15 d.不確定10. 適用于折半查找的表的存儲(chǔ)方式及元素排列要求為（）。a順序方式存儲(chǔ)，元素有序 b.順序方式存儲(chǔ)，元素?zé)o序c.鏈接方式存儲(chǔ).元素有序 d,鏈接方式存儲(chǔ).元素?zé)o厚二、填空題。（每空1分，共8分）1. 度量算法效率可通過(guò)時(shí)

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

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

6、已知圖g如卜，請(qǐng)同答以卜問(wèn)題：（1）從頂點(diǎn)1出發(fā)，用普里姆算法構(gòu)造最小生成樹(shù)，請(qǐng)寫出構(gòu)樹(shù)的邏輯步驟,（2）計(jì)算出帶權(quán)路徑長(zhǎng)度wpl。解：哈夫曼樹(shù)為:（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個(gè)帶lu）州出以它們?yōu)槿~子結(jié)點(diǎn)的哈夫地椅（樹(shù)中左孩子結(jié)點(diǎn)的權(quán)值不大于右孩子結(jié)點(diǎn)的權(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.己知棵樹(shù)的雙親表示法如下,回答以下問(wèn)題:<1）畫出該樹(shù)及其對(duì)應(yīng)的二叉樹(shù)。 解：樹(shù)hd二叉樹(shù)(4分)對(duì)應(yīng)的二叉村（4分）五、算法閱讀題。（共14分）1.假設(shè)以帶頭堵點(diǎn)的單鏈表表示線性表,閱讀下列算法fi.井回

8、答問(wèn)題: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 為：而 請(qǐng)儷出執(zhí)行fl (l)；后的單鏈表l：|4 a21 h 4

9、1+1 a6 |人|(6 分)2.算法f?功能：在有序表*中折半查找關(guān)鍵字等于key的數(shù)據(jù)元素.請(qǐng)回答下列何題：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) 請(qǐng)完成算法填空.(2) sl=( 5. 13, 19, 21, 37, 56. 64 , 75 , 80, 96)：求 f2(st, 21)=:sl=(5. 13, 19, 21, 37, 56,