專升本數(shù)據(jù)結(jié)構(gòu).doc

專升本數(shù)據(jù)結(jié)構(gòu)試卷一、填空題：（每小題2分，共10分）1. 設(shè)有數(shù)據(jù)結(jié)構(gòu)（D，R），其中 D 是數(shù)據(jù)元素的有限集，R 是 的有限集。2. 深度為 k 的二叉樹其結(jié)點數(shù)至多有 個。3. 棧是一種特殊的線性表，它允許在表的一端進行 操作。4. 通常象交通、道路問題的數(shù)學(xué)模型是一種稱為 的數(shù)據(jù)結(jié)構(gòu)。5. 哈希表是一種查找表，可以根據(jù)哈希函數(shù)直接獲得 。二、單項選擇題：（每小題2分，共10分）對于下列各題，在備選答案中選出一個正確的，并將其編號填在“ ”位置上。1. 若線性表最常用的操作是存取第 i 個元素及其前驅(qū)元素的值，則采用 存儲方式最節(jié)省運算時間。A. 單鏈表 B. 雙鏈表 C. 單循環(huán)鏈表 D. 順序表2. 下列排序算法中， 算法在進行一趟相應(yīng)的排序處理結(jié)束后不一定能選出一個元素放到其最終位置上。A. 直選擇排序 B. 冒泡排序 C. 歸并排序 D. 堆排序3. 隊列的操作原則是 。A. 先進后出 B. 先進先出 C. 只能進行插入 D. 只能進行刪除4. 在具有 n 個結(jié)點的二叉鏈表中，非空的鏈域個數(shù)為 。A. n-1 B. n C. n+1 D. 不確定5. 對具有 n 個元素的有序查找表采用折半查找算法查找一個鍵值，其最壞比較次數(shù)的數(shù)量級為 。A. O(log2n) B. O(n) C. O(nlog2n) D. O(n2)三、判斷題：（每小題2分，共10分）判斷下列各題是否正確，若正確，在題后的括號內(nèi)填“T”，否則填“F”。1. 在棧為空的情況下不能作出棧處理，否則，將產(chǎn)生下溢出。（ ）2. 如果有向圖 G=(V, E) 的拓?fù)湫蛄形ㄒ?，則圖中必定僅有一個頂點的入度為0、一個頂點的出度為0。（ ）3. 在大根堆中，必定滿足每個結(jié)點的鍵值大于其左右子樹中所有結(jié)點的鍵值。（ ）4. 在采用線性探測法處理沖突的散列表中所有同義詞在表中相鄰。（ ）5. 在索引順序表中，對索引表既可采用順序查找，也可采用二分查找。（ ）四、解答下列各題：（每題10分，共40分）1. 已知線性表 L 采用帶頭結(jié)點的的單向循環(huán)鏈表表示，試給出它的存儲結(jié)構(gòu)類型描述及相應(yīng)的示意圖。2. 已知一棵二叉樹的先序、中序和后序序列如下所示，請?zhí)顚懜餍蛄兄锌崭裉幍慕Y(jié)點，并畫出該二叉樹的二叉鏈表存儲結(jié)構(gòu)示意圖。先序序列是：_ B _ F _ I C E H _ G； 中序序列是：D _ K F I A _ E J C _ ；后序序列是：_ K _ F B H J _ G _ A3. 已知數(shù)據(jù)表為（48，70，33，65，24，56，12，92，86，22），a) 寫出采用快速排序算法進行排序時第一趟快速劃分的詳細過程及結(jié)果；b) 寫出按基數(shù)排序思想對最低位進行一次分配和收集的結(jié)果。4. 對圖1所示的帶權(quán)無向圖，寫出它的鄰接矩陣和深度優(yōu)先搜索序列，并按克魯斯卡算法求其最小生成樹（寫出求解的詳細過程示意圖）。圖1 帶權(quán)無向圖五、算法設(shè)計題：（前兩題必做，每題15分，共30分；第三題為附加題，選做，10分）1. 已知隊列 Q 以循環(huán)隊列存儲。寫出 Q 的存儲結(jié)構(gòu)類型描述，并試編寫算法實現(xiàn)將元素 x 插入隊列 Q 的入隊操作 EnQueue(Q,x)和從隊列 Q 中獲取隊首元素的函數(shù) GetTop(Q)。2. 假設(shè)線性表 L=(a1,a2,an) 用帶頭結(jié)點的單鏈表存儲表示，試編寫算法對其實現(xiàn)就地逆置，即利用原鏈表中每一個結(jié)點存儲空間，使得元素的邏輯次序改變?yōu)?an, a2,a1)。3. 設(shè)非空二叉樹 T 采用中序線索二叉鏈表表示，寫出 T 的存儲結(jié)構(gòu)類型描述。試編寫算法 InOrderTraverse(T) 實現(xiàn)對二叉樹 T 的中序遍歷。山東：07年專升本考試數(shù)據(jù)結(jié)構(gòu)模擬試題2來源：考試吧（E）整理點擊： 122更新：2006-12-27 0:36:04 一、單項選擇題：（每小題2分，共10分）對于下列各題，在備選答案中選出一個正確的，并將其編號填在“ ”位置上。1. 折半查找法要求查找表中各元素的鍵值必須是 。A. 遞增或遞減 B. 遞增 C. 遞減 D. 無序2. 若對某線性表最常進行的操作是在最后一個元素之后插入和刪除第一個元素，則采用 存儲方式最節(jié)省運算時間。A. 單鏈表 B. 雙鏈表C. 僅有頭指針的單循環(huán)鏈表 D. 僅有尾指針的單循環(huán)鏈表3. 有64個結(jié)點的完全二叉樹的深度為 （假設(shè)根結(jié)點的層次為1）。A. 8 B. 7 C. 6 D. 54. 對于鍵值序列（2，33，21，18，65，38，7，49，24，86），用篩選法建堆，必須從鍵值為 的結(jié)點開始。A. 86 B. 2 C. 65 D. 385. 設(shè)圖 G 用鄰接表存儲，則求每個頂點入度的算法時間復(fù)雜度為 。A. O(n) B. O(n+e) C. O(n*n) D. O(n*e)二、判斷題：（每小題2分，共10分）判斷下列各題是否正確，若正確，在題后的括號內(nèi)填“T”，否則填“F”。1. 在隊滿情況下不能作入隊處理，否則，將產(chǎn)生“上溢”。（ ）2. 基于插入思想的排序算法都是穩(wěn)定的。（ ）3. 一個有向圖的鄰接表和逆鄰接表中的結(jié)點個數(shù)不一定相等。（ ）4. 若一棵二叉樹的任一非葉子結(jié)點度為2，則該二叉樹為滿二叉樹。（ ）5. 廣義表是線性表的推廣，因此也可以采用順序方式進行存儲。（ ）三、填空題：（每小題2分，共10分）1. 在單鏈表中，刪除指針 P 所指結(jié)點的后繼結(jié)點的語句是： 。2. 有向圖 G 用鄰接矩陣 A1.n，1.n 存儲表示，其第 i 行的所有元素之和等于頂點 i 的 。3. 基數(shù)排序算法的時間復(fù)雜度為 。4. 平衡二叉樹中每個結(jié)點的平衡因子定義為 。5. 利用直接插入排序算法對有 n 個元素的數(shù)據(jù)表進行排序，在最壞情況下，元素的移動次為。四、解答下列各題：（每小題10分，共40分）1. 寫出采用順序方式存儲的棧的類型描述及相應(yīng)的入棧、出棧操作的示意圖。2. 已知數(shù)據(jù)表為（60，20，31，5，44，55，61，30，80，150，4，29），寫出采用希爾排序算法進行排序的詳細過程和結(jié)果（假設(shè)增量序列 dlta =6,3,1）。3. 已知圖 G 的鄰接表存儲結(jié)構(gòu)示意圖如下所示，畫出它的邏輯關(guān)系示意圖，以及按深度優(yōu)先搜索和廣度優(yōu)先搜索進行遍歷所得到的頂點序列。4. 設(shè)散列函數(shù)為 H(K) = K mod 5，散列表的地址空間為 0.6，初始時散列表為空，用線性探測法解決沖突，請寫出依次插入23，14，9，6，30，12，18時散列地址的計算過程及結(jié)果，以及最后得到的散列表。五、算法設(shè)計題：（前兩題必做，每題15分，共30分；第三題為附加題，選做，10分）1. 設(shè)計算法將一個帶頭結(jié)點的單循環(huán)鏈表 A 分解為兩個具有相同結(jié)構(gòu)的鏈表 B、C，其中：B 表中的結(jié)點為 A 表中元素的順序號為奇數(shù)的結(jié)點，而 C 表中的結(jié)點為 A 表中元素的順序號為偶數(shù)的結(jié)點。（要求利用原表結(jié)點。）2. 已知