河北大學(xué)數(shù)據(jù)結(jié)構(gòu)期末考試真題A

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è)算法按值遞減的