天津科技大學2018年數(shù)據(jù)結(jié)構(gòu)考試卷

PAGEPAGE3天津科技大學2018年數(shù)據(jù)結(jié)構(gòu)考試卷一、填空題（每小題2分，共２０分）1.數(shù)據(jù)的邏輯結(jié)構(gòu)包括集合結(jié)構(gòu)、線性結(jié)構(gòu)、。2.對算法從時間和空間兩方面進行度量，分別稱為分析。3.不帶有頭結(jié)點的單鏈表head為空的條件是。4.對于棧只能在插入和刪除元素。5.深度為k的二叉樹最多有個結(jié)點。6.空格串是。7.Hash技術關鍵是兩個方面。8.快速排序的平均時間復雜度為。9.HEAD(TAIL(((a,(b,c))))=。10.已知一個圖的鄰接矩陣表示，計算第i個結(jié)點的入度的方法是。二、單項選擇題（每小題2分，共２０分）１．以下哪一個不是隊列的基本運算（）？（A）從隊尾插入一個新元素（B）從隊列中刪除第i個元素（C）判斷一個隊列是否為空（D）讀取隊頭元素的值2．若進棧序列為１,２,３,４,假定進棧和出棧可以穿插進行，則可能的出棧序列是（）。（A）２，４，１，３（B）３，１，４，２（C）３，４，１，２（D）１，２，３，４3．有64個結(jié)點的完全二叉樹的深度為（）（根的層次為1）。（A）8（B）7（C）6（D）54．串是一種特殊的線性表，其特殊性體現(xiàn)在（）。（A）可以順序存儲（B）數(shù)據(jù)元素是一個字符（C）可以鏈接存儲（D）數(shù)據(jù)元素可以是多個字符5．鏈表不具有的優(yōu)點是（）。（A）可隨機訪問任一元素（B）插入刪除不需要移動元素（C）不必事先估計存儲空間（D）所需空間與線性表長度成正比6．對有18個元素的有序表作二分查找，則查找A[3]的比較序列的下標依次為()。(A)1，2，3(B)9，5，2，3(C)9，5，3(D)9，4，2，37．對矩陣壓縮存儲是為了()。(A)方便運算(B)節(jié)省存儲空間(C)方便存儲(D)提高運算速度8．快速排序?qū)儆冢ǎ?A)插入排序(B)交換排序(C)歸并排序(D)選擇排序9．設矩陣A{1..n,1..n]是一個對稱矩陣，為了節(jié)省存儲，只將其下三角部分按行序存放在一維數(shù)組B[1..n(n-1)/2]中，對下三角部分中任一元素aij(i>=j),在一維數(shù)組B的下標位置k的值()。(A)i(i-1)/2+j-1(B)i(i-1)/2+j(C)i(i+1)/2+j-1(D)i(i+1)/2+j10．某二叉樹的先序序列和后序序列正好相反，則該二叉樹一定是（）二叉樹。(A)空或只有一個結(jié)點(B)高度等于其結(jié)點數(shù)(C)任一結(jié)點無左孩子(D)任一結(jié)點無右孩子三、簡答題（共40分）1.對下列數(shù)據(jù)表，寫出采用二路歸并算法排序的每一趟的結(jié)果。（7分）(50,12,20,31,44,66,61,80,30,75)2.已知某二叉樹按后序遍歷序列為CEDBHJIGFA，按中序遍歷序列為CBEDAHGIJF,試畫出該二叉樹形狀（要求寫出中間過程），并寫出它的先序遍歷序列。（9分）3．已知一組元素為(37,70,29,46,25,78,62,12)，畫出按元素排列輸入生成的一棵二叉排序樹，并求其在等概率情況下查找成功的平均查找長度（要求寫出每插入一個元素時二叉排序樹形狀）。（8分）4.設a,b,c,d,e,f六個字母出現(xiàn)的次數(shù)分別為7,19,2,6,32,3,試為這六個字母設計huffman編碼并畫出對應huffman樹。（8分）5．畫出下列無向圖的鄰接表存儲結(jié)構(gòu)，并由鄰接表寫出由E出發(fā)的廣度優(yōu)先搜索序列和深度優(yōu)先搜索序列。（8分）A|BCDE四、設