下載本文檔
版權(quán)說明:本文檔由用戶提供并上傳,收益歸屬內(nèi)容提供方,若內(nèi)容存在侵權(quán),請(qǐng)進(jìn)行舉報(bào)或認(rèn)領(lǐng)
文檔簡介
1、河 北 大 學(xué) 課 程 考 核 試 卷( 2005 2006 學(xué)年第 1 學(xué)期)考核科目 數(shù)據(jù)結(jié)構(gòu) 課程類別 選修 考核方式 閉卷 卷別_A_一二三四五六七八九十十一總分得分評(píng)卷人一、選擇題(每題2分,共20分)( )1、如果線性表中最常用的操作是存取第 i個(gè)元素及其前驅(qū)結(jié)點(diǎn)的值,則采用 存儲(chǔ)方式節(jié)省時(shí)間。A)單鏈表B)雙鏈表C)單循環(huán)鏈表D)順序表( )2、在一個(gè)鏈隊(duì)列中,若f,r分別為隊(duì)首、隊(duì)尾指針,則插入s所指結(jié)點(diǎn)的操作為 A)f->next=s;f=s; B) r->next=s;r=s; C)s->next=r;r=s; D) s->next=f;f=s;(
2、)3、一棵非空的二叉樹的先序遍歷序列與后序遍歷序列正好相反,則該二叉樹定滿足 A)所有的結(jié)點(diǎn)均無左孩子 B)所有的結(jié)點(diǎn)均無右孩子C)只有一個(gè)葉子結(jié)點(diǎn) D)是任意一棵二叉樹( )4、設(shè)F是一個(gè)森林,B是由F變換得到的二叉樹。若F中有n個(gè)非終端結(jié)點(diǎn),則B中右指針域?yàn)榭盏慕Y(jié)點(diǎn)有 個(gè)。A)n-1 B)n C)n1 D)n2( )5、有10個(gè)結(jié)點(diǎn)的無向圖至少有 條邊才能確保其是連通圖A)8 B)9 C)10 D)11A1( )6、二叉排序樹中,鍵值最小的結(jié)點(diǎn)一定 A)左指針為空 B)右指針為空 C)左右指針均為空 D)左右指針均非空( )7、在一個(gè)有向圖中,所有頂點(diǎn)的入度之和等于所有頂點(diǎn)的出度之和的 倍
3、。 A)1/2 B)1 C)2 D)4( )8、設(shè)高度為h的二叉樹上只有度為0和2的結(jié)點(diǎn),則此二叉樹中所包含的結(jié)點(diǎn)數(shù)至少為 A)2*h B)2*h-1 C)2*h+1 D)h+1 ( )9、一棵深度為k的平衡二叉樹,其每個(gè)非終端結(jié)點(diǎn)的平衡因子均為0,則該樹共有 個(gè)結(jié)點(diǎn)。A)2k-1-1B)2k-1+1C)2k-1D)2k+1( )10、一組記錄的排序碼為(46,79,56,38,40,84),則利用堆排序的方法建立的初始堆為 ) 79,46,56,38,40,80) 84,79,56,38,40,46) 84,79,56,46,40,38) 84,56,79,40,46,38得分評(píng)卷人二、判斷
4、題(每題1分,共10分)( )1、順序存儲(chǔ)方式只能用于線性結(jié)構(gòu),不能用于非線性結(jié)構(gòu)。( )2、若一個(gè)結(jié)點(diǎn)是某二叉樹子樹的中序遍歷序列中的第一個(gè)結(jié)點(diǎn),則它必是該子樹的后序遍歷序列中的第一個(gè)結(jié)點(diǎn)。( )3、求最小生成樹的Prim算法在邊較少、結(jié)點(diǎn)較多時(shí)效率較高。( )4、折半查找只能在有序的順序表上進(jìn)行而不能在有序鏈表上進(jìn)行。( )5、快速排序的速度在所有排序方法中為最快,而且所需附加空間也最少。( )6、在一個(gè)有向圖的鄰接表中,若某結(jié)點(diǎn)的鏈表為空,則該頂點(diǎn)的度一定為零。( )7、插入排序、選擇排序和冒泡排序不都是穩(wěn)定的排序算法。A2( )8、在二叉樹排序中刪除一個(gè)結(jié)點(diǎn),接著又將該結(jié)點(diǎn)插入到該二叉
5、排序樹中去,該二叉樹不會(huì)發(fā)生變化。( )9、在二叉排序樹上刪除一個(gè)結(jié)點(diǎn)時(shí),不必移動(dòng)其它結(jié)點(diǎn),只要將該結(jié)點(diǎn)相應(yīng)的指針域置空即可。( )10、由二叉樹的后序序列和中序序列可以唯一地確定一棵二叉樹。得分評(píng)卷人三、簡答題(每題6分,共36分)1、試描述頭指針、頭結(jié)點(diǎn)、第一個(gè)結(jié)點(diǎn)的區(qū)別,并說明頭指針和頭結(jié)點(diǎn)的作用。2、已知一棵二叉樹的前序序列和中序序列分別為ABDGHCEFI和GDHBAECIF,求其對(duì)應(yīng)的二叉樹。3、已知如下所示長度為12的查找表:Jan, Feb, Mar, Apr, May, June, July, Aug, Sep, Oct, Nov, Dec;試按表中元素的順序依次插入到一棵初
6、始為空的二叉排序樹。畫出插入完成后的二叉排序樹,并求其在等概率的情況下查找成功的平均查找長度。4、對(duì)下面連通圖,畫出其鄰接矩陣,并用Prim算法構(gòu)造其最小生成樹。14213abcdhgfe2221125、設(shè)AOE網(wǎng)如下圖所示,求:列出各個(gè)事件的最早、最遲發(fā)生時(shí)間;找出該AOE網(wǎng)中的關(guān)鍵路徑,并回答完成該工程需要的最短時(shí)間。V1V2V4V3V5V6V7V8V9V10a1=5a2=6a3=3a4=6a5=3a6=3a7=10a8=5a9=1a12=5a10=4a11=4a13=2a14=2A36、應(yīng)用直接插入排序算法,對(duì)關(guān)鍵值序列25,84,68,47,35,27, 21, 15,24從小到大排列。試寫出每趟排序的結(jié)果。得分評(píng)卷人四、算法設(shè)計(jì)題(共34分)【要求】定義主要數(shù)據(jù)的存儲(chǔ)類型;對(duì)算法中的主要操作步驟加以注釋。1、已知帶頭結(jié)點(diǎn)的單鏈表L中的結(jié)點(diǎn)是按整數(shù)值遞增排列的,試寫一算法,將值為x 的結(jié)點(diǎn)插入到表L中,使得L仍然有序。(10分)2、假設(shè)二叉排序樹T的各個(gè)元素的值均不相同,設(shè)計(jì)一個(gè)算法按值遞減的
溫馨提示
- 1. 本站所有資源如無特殊說明,都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請(qǐng)下載最新的WinRAR軟件解壓。
- 2. 本站的文檔不包含任何第三方提供的附件圖紙等,如果需要附件,請(qǐng)聯(lián)系上傳者。文件的所有權(quán)益歸上傳用戶所有。
- 3. 本站RAR壓縮包中若帶圖紙,網(wǎng)頁內(nèi)容里面會(huì)有圖紙預(yù)覽,若沒有圖紙預(yù)覽就沒有圖紙。
- 4. 未經(jīng)權(quán)益所有人同意不得將文件中的內(nèi)容挪作商業(yè)或盈利用途。
- 5. 人人文庫網(wǎng)僅提供信息存儲(chǔ)空間,僅對(duì)用戶上傳內(nèi)容的表現(xiàn)方式做保護(hù)處理,對(duì)用戶上傳分享的文檔內(nèi)容本身不做任何修改或編輯,并不能對(duì)任何下載內(nèi)容負(fù)責(zé)。
- 6. 下載文件中如有侵權(quán)或不適當(dāng)內(nèi)容,請(qǐng)與我們聯(lián)系,我們立即糾正。
- 7. 本站不保證下載資源的準(zhǔn)確性、安全性和完整性, 同時(shí)也不承擔(dān)用戶因使用這些下載資源對(duì)自己和他人造成任何形式的傷害或損失。
最新文檔
- 2023-2024學(xué)年安徽省九年級(jí)語文上學(xué)期期中質(zhì)量檢測(cè)試卷附答案解析
- 五年級(jí)中國民間故事題及答案
- 2024年冷軋薄板市場(chǎng)前景分析:冷軋薄板市場(chǎng)規(guī)模達(dá)到2742.49億元
- 60字左右的自我介紹
- 20歲生日宴會(huì)發(fā)言稿
- 2024年安全生產(chǎn)月安全標(biāo)語
- 2024-2025學(xué)年高中化學(xué)必修第二冊(cè)滬科版(2020)教學(xué)設(shè)計(jì)合集
- 今讀陰平、陽平聲的古入聲常用字表
- 產(chǎn)業(yè)園咨詢服務(wù)協(xié)議書范本
- 成都2024年四川天府新區(qū)人民醫(yī)院第五批招聘24人筆試歷年參考題庫解題思路附帶答案詳解
- 網(wǎng)站后臺(tái)萬能密碼
- 電鍍失效模式與效應(yīng)分析 8A0035SL Plating PFMEA2006templet
- 燃?xì)忮仩t出力不足的原因分析及解決措施
- 落地式卸料平臺(tái)安全專項(xiàng)施工方案
- 《兩票三制培訓(xùn)》
- 同振動(dòng)方向簡諧振動(dòng)的合成
- 機(jī)械畢業(yè)設(shè)計(jì)1523修井作業(yè)自動(dòng)卡瓦設(shè)計(jì)(60t)(共36頁)
- 常見焊條焊絲型號(hào)牌號(hào)對(duì)照一覽表重點(diǎn)講義
- 統(tǒng)編版五年級(jí)語文上冊(cè)全冊(cè)看拼音寫詞語及答案
- 小學(xué)數(shù)學(xué)四年級(jí)答題卡模板(共4頁)
- ALC板工程施工組織設(shè)計(jì)方案
評(píng)論
0/150
提交評(píng)論