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

1、考生注意：1、學(xué)號(hào)、姓名、 年級(jí)、專業(yè)等應(yīng)填 寫準(zhǔn)確“2、考試作弊 者，員令?？?，成 績(jī)作廢。廣西民族大學(xué)成人高等教育考試復(fù)習(xí)題課程名稱：數(shù)據(jù)結(jié)構(gòu)與算法考試fi期：20年 月考核時(shí)長(zhǎng):120分伸得分評(píng)卷人答案教學(xué)點(diǎn)考核方式：開卷試卷類別：b卷年級(jí)20級(jí)層次形式高起專命題教師張桂芬教研室主任一、單項(xiàng)選擇題。(每題2分，共20分)1. 以下程序段中帶硝句的執(zhí)行頻度和算法的時(shí)間復(fù)雜度分別是().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. 設(shè)輸入序列為字符a、b、c,則經(jīng)過棧的作用后可以得到(c )種不同的輸出序列。a.3b. 1c. 5d. 64. 數(shù)組a|7 |6的每個(gè)元素占5個(gè)字節(jié).將其以行為主序存依在起始地址為100()的內(nèi)存單元 中.則元素a 5 4的地址是< c )。a.1165b.1180c. 1170d.12105. 對(duì)于順序存儲(chǔ)的線性表，訪問元素和插入元素的時(shí)間復(fù)雜度分別為：()。a. o(n) , o(n) b. o(n) . 0(1) c. 0(1) . 0(1) d. 0(1) . o(n)6. 在單鏈

3、表指針為p的結(jié)點(diǎn)之后插入指針為，的結(jié)點(diǎn)，正確的操作是( 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個(gè)頂點(diǎn)的有向圖中，含有向邊的數(shù)目最多為()。a n-1b. nc. n(n-l)/2d. n(n-l)8. 對(duì)下面有向圖給出了四種可能的拓?fù)湫蛄?，其中錯(cuò)誤的是(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個(gè)度為2的結(jié)點(diǎn)，5個(gè)度為1的結(jié)點(diǎn)，則葉子結(jié)點(diǎn)數(shù)為(ba. 9 b. 11c. 15 d.不確定10. 適用于折半查找的表的存儲(chǔ)方式及元素排列要求為()<>a順序方式存飭，元素有序 b.順序方式存儲(chǔ)，元素?zé)o序c.鏈接方式存儲(chǔ).元素有序d.鏈接方式存儲(chǔ).元素?zé)o序二、填空題。(每空1分，共8分)1. 度量算法效率可通過時(shí)間復(fù)雜度和兩方面進(jìn)行。2. 迷宮問題是一個(gè)回溯控制的問我，最好使用_結(jié)構(gòu)來記錄路徑數(shù)據(jù)。3. 設(shè)字符sl= abcde s2= aaa 則執(zhí)行運(yùn)j? strinse

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

6、定問題求解步驟的種描述它是指令的有限序列。（2分 它的五個(gè)重要特性是:<1）有窮性：（2）確定性：（3）可行性：（4）零個(gè)或多個(gè)輸入：四、應(yīng)用題。（每題12分，共36分）1.已知圖g如請(qǐng)回答以下問題:（d從頂點(diǎn)1出發(fā),用普里姆算法構(gòu)造最小生成樹，請(qǐng)寫出構(gòu)樹的邏輯步驟.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個(gè)帶權(quán)站點(diǎn).其權(quán)值分別為3. 7,8,2,6,10, 14：（i）畫出以它們?yōu)槿~子結(jié)點(diǎn)的哈夫曼樹（樹中左孩子結(jié)點(diǎn)的權(quán)值不大丁右孩子結(jié)點(diǎn)的權(quán)值）： 計(jì)算出帶權(quán)路徑長(zhǎng)度wpl。解：哈夫曼樹為:（8分）<2）寫出該樹的前序和后序遍歷序列。 解：該樹的前序遍歷序列：abefcgdh （2分）五、算法閱讀題。（共14分）1 .假設(shè)以帶頭結(jié)點(diǎn)的單鏈表表示

8、線性表.閱讀卜列算法fl,并回答問題:void fklinklist l） （p=l;while （p && p->next）q = p->next;2129p->next =q->next; p =q->next; fnre(|);設(shè)單鏈表 l 為：e4|h al a2 a3 « a4 a5 一 a6 “卜7 囚 清畫出執(zhí)行fl(l)；后的單鏈表l：e*1riirn*i 孩41 bn亦|(6 分)2.算法f2功能：在有序表st中折半查找關(guān)鍵字等于key的數(shù)據(jù)元素，請(qǐng)叵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)請(qǐng)完成算法填空。(每空2分，共8分)六、算法設(shè)計(jì)題。(共10分)1.以順序存儲(chǔ)結(jié)構(gòu)表示線性表，編寫算法，求出線性表中元素的址大值。函數(shù)原型為：status s(