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