算法與數(shù)據(jù)結(jié)構(gòu)-B卷

第3頁共3頁石家莊鐵道大學(xué)2013-2014學(xué)年第1學(xué)期2012級(jí)本科期末考試試卷（B）課程名稱：算法與數(shù)據(jù)結(jié)構(gòu)任課教師：考試時(shí)間：分鐘學(xué)號(hào)：姓名：班級(jí)：考試性質(zhì)（學(xué)生填寫）：題號(hào)一二三四五六七總分滿分206020100得分閱卷人答案一律寫在答題紙上，寫在試卷上無效。一、單項(xiàng)選擇題（每小題2分，共20分）1、若某線性表最常用的操作是取第i個(gè)元素和找第i個(gè)元素的前驅(qū)元素，則采?。ǎ┐鎯?chǔ)方式最節(jié)省時(shí)間。A．單鏈表B．雙鏈表C．單向循環(huán)鏈表D．順序表2、在單鏈表中增加一個(gè)頭結(jié)點(diǎn)的目的是（）。A．使單鏈表至少有一個(gè)結(jié)點(diǎn)B．標(biāo)示表結(jié)點(diǎn)中首結(jié)點(diǎn)的位置C．方便運(yùn)算的實(shí)現(xiàn)D．說明單鏈表是線性表的鏈?zhǔn)酱鎯?chǔ)3、一個(gè)棧的輸入序列為12345，則下列序列中（）不可能是棧的輸出隊(duì)列。A．23415B．54132C．23145D．154324、一個(gè)子串在包含它的主串中的位置是指（）。A．子串的最后一個(gè)字符在主串中的位置B．子串的最后一個(gè)字符在主串中首次出現(xiàn)的位置C．子串的第一個(gè)字符在主串中的位置D．子串的第一個(gè)字符在主串中首次出現(xiàn)的位置5、已知廣義表LS=((a,b,c),(d,e,f))，運(yùn)用head和tail函數(shù)取出LS中原子e的運(yùn)算是（）。A．head(tail(LS))B．tail(head(LS))C．head(tail(head(tail(LS))))D．head(tail(tail(head(LS))))6、若X是中序線索二叉樹中一個(gè)有左孩子的結(jié)點(diǎn)，且X不為根，則X的前驅(qū)為（）。A．X的雙親B．X的左子樹中最右結(jié)點(diǎn)C．X的右子樹中最左結(jié)點(diǎn)D．X的左子樹中最左結(jié)點(diǎn)7、（）的鄰接矩陣是對(duì)稱矩陣。A．有向圖B．無向圖C．AOV網(wǎng)D．AOE網(wǎng)8、如果從無向圖的任一頂點(diǎn)出發(fā)進(jìn)行一次深度優(yōu)先搜索即可訪問所有頂點(diǎn)，則該圖一定是（）。A．完全圖B．連通圖C．有回路D．一棵樹9、散列文件使用散列函數(shù)將記錄的關(guān)鍵字值計(jì)算轉(zhuǎn)化為記錄的存放地址，因?yàn)樯⒘泻瘮?shù)是一對(duì)一的關(guān)系，則選擇好的（）是散列文件的關(guān)鍵。A．散列函數(shù)B．除余法中的質(zhì)數(shù)C．沖突處理方法D.散列函數(shù)和沖突處理方法10、堆排序中，堆的形狀是一棵（）。A．二叉排序樹B．滿二叉樹C．完全二叉樹D．平衡二叉樹二、簡(jiǎn)答題（共60分）1、（13分）在某報(bào)文系統(tǒng)中只出現(xiàn)以下字符，字符的權(quán)值分別為：A B C D E F G 7 21 20 23 3 2 24為這7個(gè)字母設(shè)計(jì)Huffman編碼。（1）畫出Huffman樹。（7分）（2）Huffman樹HT存儲(chǔ)結(jié)構(gòu)的終態(tài)如下表所示，請(qǐng)?zhí)顚懲暾?。?分）結(jié)點(diǎn)iweightparentlchildrchild1700221003200042300530062007240089101112132.（12分）圖的鄰接矩陣如下：（1）根據(jù)鄰接矩陣畫出這個(gè)圖。（4分）（2）畫出該圖的廣度優(yōu)先生成樹（從頂點(diǎn)1出發(fā)）。（4分）（3）畫出該圖的深度優(yōu)先生成樹（從頂點(diǎn)3出發(fā)）。（4分）3.（11分）散列表的地址范圍為0—15，散列函數(shù)H(key)=key%13，關(guān)鍵字序列為（26，51，3，23，11，33，38，42，69，13，9），用鏈地址法處理沖突。（1）對(duì)該關(guān)鍵字序列構(gòu)造散列表。（8分）（2）求等概率下查找成功時(shí)的平均查找長(zhǎng)度ASLsucc。（3分）4.（12分）待排序的關(guān)鍵字序列為{39，1，28，12，6，24，51，70，19，45}，從小到大排序。（1）寫出采用冒泡快速排序算法每趟排序結(jié)束后關(guān)鍵字序列的狀態(tài)。（6分）（2）寫出采用希爾排序算法每趟排序結(jié)束后關(guān)鍵字序列的狀態(tài)。（6分）5.（12分）已知二叉樹的層次訪問序列為ABCDEFGHIJ；二叉樹的中序訪問次序?yàn)镈BGEHJACIF。（1）畫出和上述已知序列對(duì)應(yīng)的樹T。（5分）（2）寫出樹T的前序遍歷序列。（3分）（3）將二叉樹T轉(zhuǎn)換成相應(yīng)的森林。（4分）三、算法設(shè)計(jì)題（每小題10分，共20分）用類C語言編寫算法。1、有一個(gè)帶頭結(jié)點(diǎn)的單鏈表，其結(jié)點(diǎn)的元素以非遞減有序排列，請(qǐng)(