1、專業(yè)班級(jí)： 姓名： 學(xué)號(hào)： 密封線河南理工大學(xué)萬方學(xué)院 2006-2007學(xué)年第 2 學(xué)期專業(yè)班級(jí)： 姓名： 學(xué)號(hào)： 密封線數(shù)據(jù)結(jié)構(gòu)試卷（A卷）考試方式： 閉卷 本試卷考試分?jǐn)?shù)占學(xué)生總評(píng)成績的 80 %總 分題號(hào)一二三四核分人得分 復(fù)查總分 總復(fù)查人 得分評(píng)卷人 毋小省一、單選題（本題的每一備選答案中，只有一個(gè)是正確的，請(qǐng)把你認(rèn)為正確的答案的題號(hào)填入題干的括號(hào)內(nèi)，每小題2分，共30分）1. 若長度為n的線性表采用順序存儲(chǔ)結(jié)構(gòu)，在其第i個(gè)位置插入一個(gè)新元素的算法的時(shí)間復(fù)雜度為( )。(1in+1) (1) O(0) (2) O(1) (3) O(n) (4) O(n2)2.在單鏈表中p所指結(jié)點(diǎn)后

2、插入s所指結(jié)點(diǎn),則下列語句正確的是( ) (1) pnext=s; snext=p; (2) snext=pnext; pnext=s; (3) snext=p; pnext=s; (4) pnext=snext; snext=p;3. 設(shè)一個(gè)棧的輸入序列為A，B，C，D，則借助一個(gè)棧所得到的輸出序列不可能是( )（1）A，B，C，D （2）D，C，B，A （3）A，C，D，B （4）D，A，B，C4.若由樹林轉(zhuǎn)化得到的二叉樹是非空的二叉樹，則二叉樹形狀是（ ）（1） 根結(jié)點(diǎn)無右子樹的二叉樹 （2） 根結(jié)點(diǎn)無左子樹的二叉樹（3） 根結(jié)點(diǎn)可能有左二叉樹和右二叉樹 （4） 根結(jié)點(diǎn)只有一個(gè)孩子結(jié)點(diǎn)的

3、二叉樹5設(shè)二叉樹的根為第一層，則深度為i的二叉樹結(jié)點(diǎn)數(shù)最多為（ ）（1）i （2） i +1 （3）i - （4）i -1 6. 首先訪問結(jié)點(diǎn)的左子樹，然后訪問該結(jié)點(diǎn)，最后訪問結(jié)點(diǎn)的右子樹，這種遍歷稱為()（1）前序遍歷 （2）后序遍歷 （3）中序遍歷 （4）層次遍歷7給定下列有向圖，從頂點(diǎn)1出發(fā)，其廣度優(yōu)先搜索序列為（ ）（1）12534 （2）12435 （3） 14325 （4）123458散列表中的沖突是指（ ）（1）兩個(gè)元素具有相同的序號(hào) （2） 兩個(gè)元素的關(guān)鍵字相同，而其他屬性相同（3） 不同的關(guān)鍵字對(duì)應(yīng)相同的存儲(chǔ)地址 （4） 數(shù)據(jù)元素的地址相同9. 線性表若采用鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)時(shí)，要

4、求內(nèi)存中可用存儲(chǔ)單元的地址:（ ）（1）必須是連續(xù)的 （2）部分地址必須是連續(xù)的（3）一定是不連續(xù)的 （4）連續(xù)或不連續(xù)都可以10下面程序段的時(shí)間復(fù)雜度為（ ） for (int i=1;im;i+) for (int j=1;j1）個(gè)頂點(diǎn)的無向連通圖最少由n-1條邊。（ ）7.有向圖的鄰接表表示中邊表中結(jié)點(diǎn)的總數(shù)與有向圖中有向邊的條數(shù)相等。（ ）8.一個(gè)無向圖的鄰接矩陣中各元素之和與圖中邊的條數(shù)相等。（ ）9.歸并排序要求待排序文件已部分排序。（ ）10.順序檢索時(shí)數(shù)據(jù)的存儲(chǔ)方式可以是順序的，也可以是鏈接的。得分評(píng)卷人 毋小省四、綜合題（共40分）1已知某系統(tǒng)在通信聯(lián)絡(luò)中只可能出現(xiàn)8種字符，

5、其概率分別為0.05，0.29，0.07，0.08，0.14，0.23，0.03，0.11，試設(shè)計(jì)哈夫曼編碼。(7分) 2設(shè)待排序的記錄的關(guān)鍵字序列為12，2，16，30，10，20，18，寫出使用鏈?zhǔn)交鶖?shù)排序每趟的結(jié)果。(6分)3、拓?fù)渑判虻慕Y(jié)果不是唯一的，對(duì)于下圖的結(jié)點(diǎn)進(jìn)行拓?fù)渑判颍噷懗銎渲械娜我?個(gè)。(5分)V1V3V4V6V5V7V8V9V2A4分別按前序、后序、對(duì)稱序列寫出下圖二叉樹的結(jié)點(diǎn)，并轉(zhuǎn)化為樹林，分別按先根次序、后根次序列出其結(jié)點(diǎn)。(6分)IFDEABCGH5.已知一組關(guān)鍵字為（19，14，23，01，68，20，84，27，55，11，10，79），則按哈希函數(shù)H(key)=key MOD 13,表長為13，分別用線性探查法和鏈地址法處理沖突構(gòu)造哈希表，并計(jì)算各平均查找長度。(10分)6.程序填空(6分)對(duì)有序表R0至Rn-1進(jìn)行二分查找，成功時(shí)返回記錄在表中的位置，失敗時(shí)返回0.Struct sqlist keytype key; int binsrch(sqlist R ,keytype k) /在表R中查找關(guān)鍵字k int low ,high,mid; low=0; high=n-1; while