2017青島大學(xué)考研真題921數(shù)據(jù)結(jié)構(gòu)與算法基礎(chǔ)

1、1青島大學(xué)青島大學(xué)2017年碩士研究生入學(xué)考試試題年碩士研究生入學(xué)考試試題科目代碼：921科目名稱：數(shù)據(jù)結(jié)構(gòu)與算法基礎(chǔ)（共5頁）請考生寫明題號，將答案全部答在答題紙上，答在試卷上無效一、單項選擇題（共一、單項選擇題（共15小題，每小題小題，每小題2分，共分，共30分）分）1.以下時間復(fù)雜度T(n)最高的是：A.T(n)=666n999B.T(n)=100n2C.T(n)=2nD.T(n)=22223nlog2n2.二叉樹T中度為2的結(jié)點

2、有2016個，則T中葉子結(jié)點有：A.2015個B.2016個C.2017個D.以上都不對3.逆波蘭式(后綴式)10255283的值是：A.2B.0C.1D.64.元素ABCDE依次入棧，則以下()是不可能的出棧次序。A.ABCDEB.EDCBAC.ACBDED.DABCE5.對于有N個結(jié)點的二叉搜索樹(BinarySearchTree)，以下說法正確的是：A.在此樹中查找值為x的結(jié)點的時間復(fù)雜度是O(logN)。B.將此樹的每個結(jié)點的左

3、右兒子結(jié)點互換，產(chǎn)生的新樹依然是一棵二叉搜索樹。C.此樹中值最大的結(jié)點一定在右子樹。D.此樹中值最小的結(jié)點一定不在右子樹。6.一個具有N個頂點的無向連通圖G，其生成樹為T，以下說法正確的是：A.該生成樹一定是唯一的。B.該生成樹可能不唯一，但不同生成樹各邊的權(quán)值之和是相等的。C.生成樹T一定具有N1條邊。D.生成樹T是圖G的極大連通子圖。7.二叉樹的第k(k=1)層的結(jié)點數(shù)最多為：A2k1B.2k1C.2k1D.2k18.下列排序算法中

4、，其中（）是穩(wěn)定的3A.目前最快的排序算法的平均時間復(fù)雜度是O(NlogN)。B.歸并排序的最好、平均和最壞情況下的時間復(fù)雜度都是O(NlogN)。C.快速排序的最壞情況下的時間復(fù)雜度是O(NlogN)。D.冒泡排序的最好情況下的時間復(fù)雜度是O(N2)。二、判斷題（共二、判斷題（共5小題，每小題小題，每小題2分，共分，共10分）分）1.稀疏圖較適合采用鄰接矩陣的存儲方式。2.采用哈希（散列）進行查找的時間復(fù)雜度是O(N)。3.任何一棵二

5、叉樹的葉結(jié)點在前、中、后序三種遍歷中的相對次序不變。4.對二叉搜索樹（BST）進行中序遍歷，可得到一個遞增序列。5.對圖進行非遞歸的深度優(yōu)先搜索，一般均使用隊列（Queue）實現(xiàn)。三、填空題（共三、填空題（共5空，每空空，每空2分，共分，共10分）分）1.設(shè)一棵完全二叉樹有65個結(jié)點，則該樹有(1)層結(jié)點，葉子結(jié)點的數(shù)量是(2)。2.若一個無向完全圖有20個頂點，則該圖所有頂點的度之和為(3)。3.循環(huán)隊列的數(shù)組大小為MaxSize，元

6、素入隊時，對于隊尾位置rear的操作是(4)。4.假設(shè)一個文本使用的字符集是abcdef，字符的哈夫曼編碼依次為1100110111101001111，則編碼串11110010110111001110對應(yīng)的文字是(5)。四、應(yīng)用題（共四、應(yīng)用題（共4小題，每題小題，每題15分，共分，共60分）分）1.根據(jù)右圖所示二叉樹，回答以下問題：(1)寫出該樹的前序、中序、后序遍歷序列。(2)該樹是一棵二叉搜索樹，請簡述二叉搜索樹刪除結(jié)點的算法，并