1、精選優質文檔-傾情為你奉上數據結構考試試卷（A卷）班級： 姓名： 學號： 分數： 題號一二三四五六七八九十總分得分評卷人一. 單項選擇題(每題2分，共30分)(1) 一個棧的入棧序列為1 2 3 4，以下出棧序列不可能得到的是( )A. 1 3 2 4 B. 2 3 4 1C. 4 3 1 2 D. 3 4 2 1(2) 若一個二叉樹具有10個度為2的結點，則度為0的結點的個數為( )A. 9 B. 10 C. 11 D. 不確定(3) 鏈式結構線性表的特點是：( )A. 便于隨機存取B. 花費的存儲空間比順序結構少C. 便于插入和刪除D. 元素的物理順序與邏輯順序一致(4) 一個二叉樹的前序

2、遍歷序為ABCDEFG，則中序遍歷序可能是：( )A. CABDEFG B. ABCDEFG C. DACEFBG D. EABCDFG（5）樹最適合用來表示( )。 A.有序數據元素 B.無序數據元素 C.元素之間具有分支層次關系的數據 D.元素之間無聯系的數據(6) 下列有關圖遍歷的說法中不正確的是：( )A連通圖的深度優先搜索是一個遞歸過程。B圖的廣度優先搜索中鄰接點的尋找具有“先進先出”的特征。C非連通圖不能用深度優先搜索法。D圖的遍歷要求每一頂點僅被訪問一次。(7) 若已知待排序序列基本有序，則效率最高的排序方法是：( ) A. 直接插入排序 B. 直接選擇排序C. 快速排序D. 歸

3、并排序(8) 對一棵完全二叉樹按層次遍歷序進行遞增編號，根結點編號為1，那么編號為49的結點的左子的編號是：( )A. 98B. 99C. 50D. 48(9) 下列序列中不符合堆的定義的是：( )A. a c d g h m p q r xB. a c m d h p x g o rC. a d p r c q x m h gD. a d c m p g h x r q(10) 下列排序方法中，相同關鍵字元素的順序不會被改變的排序方法是：( )A. 希爾排序法B. 堆排序法 C. 快速排序D. 歸并排序法(11) 在有n個葉結點的哈夫曼樹上，結點總數為：( )A. 2n B. 2n+1 C.

4、 2n-1 D. 不確定(12) 對于關鍵字值序列(12、13、11、18、60、15、7、18、25、100)建堆，調整的起點是：( )A. 100B. 12C. 60D. 15(13) 下列關鍵字序列中，是執行完一趟快速排序后得到的序列的是：( )A. da,ax,eb,de,bbffha,gc B. cd,eb,ax,daffha,gc,bbC. gc,ax,eb,cd,bbffda,ha D. ax,bb,cd,daffeb,gc,ha(14) 若從二叉樹的任一結點出發到根的路徑上所經過的結點序列按其關鍵字有序，則該二叉樹是：( ) A. 二叉排序樹 B. 平衡二叉樹 C. 堆 D.

5、哈夫曼樹(15) 在平衡二叉樹中插入一個結點后造成了不平衡，設最低的不平衡結點為A，并已知A的左孩子的平衡因子為0右孩子的平衡因子為1，則應采取的調整型是：( )A. LL B. LR C. RL D. RR二. 填空題(每題2分，共20分)（1）通常從四個方面評價算法的質量：_ 、_ 、_和_。（2） 若用鏈表存儲一棵二叉樹時，每個結點除數據域外，還有指向左孩子和右孩子的兩個指針。在這種存儲結構中，n個結點的二叉樹共有_個指針域，其中有_個指針域是存放了地址，有_個指針是空指針。（3）AOV網是一種_的圖。（4） 在一個具有n個頂點的無向完全圖中，包含有_條邊，在一個具有n個頂點的有向完全圖

6、中，包含有_條邊。三. 判斷題 (每題2分，共30分)(1) 由二叉樹的前序和后序遍歷序可以推導出其中序遍歷序。( )(2) 線性表的邏輯順序和物理順序總是一致的。( )(3) 有向圖的鄰接表結構比鄰接矩陣結構要節省空間。( )(4) 棧和隊列都是限制了讀寫操作的線性表，只是所施加的限制不同。( )(5) 大頂堆（降序堆）是根結點大于其他所有結點的完全二叉樹。( )(6) 連通圖從任意頂點出發進行一趟深度優先遍歷，可以訪問到圖中的所有頂點。( )(7) 用二叉鏈結構存儲的一棵n個結點的二叉樹上，有n+1個空鏈。( )(8) 二路歸并排序的核心操作是將兩個有序序列歸并為一個有序序列。( )(9)

7、 設只有根結點的二叉樹高度為1，則高度為h的二叉樹，至多有2h-1個結點。( )(10) 遞歸形式的代碼一定可以用非遞歸的形式來實現。( )(11) 穩定排序法可以保證排序的效率，不穩定排序法不能保證排序的效率。( )(12) 鄰接矩陣所需存儲空間大小只與結點數有關，與弧的個數無關。( )(13) 二叉樹中，具有兩個子結點的中序后繼結點最多只可能有一個子結點。( )(14) 若一棵二叉樹的左右子樹都是平衡二叉樹，則該二叉樹亦為平衡二叉樹。( )(15) 折半查找法只適用于順序結構的線性表。( )四 (共10分)請畫出下圖的鄰接矩陣( 5分 )和鄰接表 ( 5分)。五. 已知某工程包括多個子項目，某些子項目可能存在前期子項目，也就是說，只有當前期子項目都完成后，該子項目才能開始。下面給出各子項目的工期，以及各子項目的前期