2019年北京建筑大學專升本數據結構考試真題

一、單項選擇題，請選擇最佳答案(每題2分，共40分)。

1、【 】是數據的最小單位。

A. 數據項 B.數據元素 C.結構 D.算法

2、數據結構是指數據以及它們之間的【 】。

A. 運算 B.關系 C.計算方法 D.存儲

3、數據結構在計算機中的表示可以分為【 】。

A.動態結構和靜態結構 B.順序結構和鏈式結構

C.緊湊結構和非緊湊結構 D.內部結構和外部結構

4、算法分析的目的【 】。

A.找出數據結構的合理性 B.研究算法的輸入輸出關系

C.分析算法的效率以求改進 D.算法是否具有較好的可讀性

5、線性表是具有n個【 】的有限序列

A.數據元素 B.字符 C.邏輯關系 D.數據項

6、在具有n個元素的順序表中查找一個元素的時間復雜度是【 】。

A. O(1) B. O(n) C. O(n2) D. O(nlog2n)

7、帶頭結點的單鏈表L為空的判定條件是【 】。

A.L= =NULL B.L->next= =NULL

C.L->next=L D.L!=NULL

8、如果最常用的操作是取線性表中第i個元素及其前驅，則采用【 】存儲方式最節省時間。

A.單鏈表 B.雙向鏈表 C.循環鏈表 D.順序表

9、遞歸程序執行時，要用到的數據結構是【 】。

A. 棧 B. 隊列 C. 線性表 D. 數組

10、一個棧的入棧序列是1,2,3，下列不可能的出棧序列是【 】。

A.123 B.132 C.312 D.213

11、串的長度是指【 】。

A.串中所含非空格字符的個數 B.串中所含字符的個數

C.串中所含不同字符的個數 D. 串中所含不同字母的個數

12、稀疏矩陣用三元組表示的目的是【 】。

A. 便于進行矩陣運算 B. 便于輸入和輸出

C. 節省存儲空間 D.降低運算的時間復雜度

13、圖最合適用來表示【 】。

A.元素之間具有線性關系的數據 B.元素之間具有分支層次關系的數據

C.元素之間具有網狀關系的數據 D.元素之間無聯系的數據

14、二叉樹第4層上至多有【 】結點。

A. 4 B.8 C.16 D.7

15、若有向圖中的頂點能排成拓撲序列,則該有向圖【 】。

A.是有向無環圖 B.不存在回路

C.含有多個入度為0的頂點 D.是強連通圖

16、如果從無向圖中任一頂點出發進行一次深度優先搜索即可訪問圖中所有頂點,則該圖一定是【 】。

A.完全圖 B.連通圖 C.有回路 D.一棵樹

17、具有20個葉結點的二叉樹中有【 】個度為2的結點，

A. 8 B. 19 C. 20 D. 2l

18、在一個無向圖中，所有頂點的度數之和等于所有邊數【 】倍。

A.1/2 B.2 C.1 D.4

19、具有6個頂點的無向圖至少應有幾條邊才能確保是一個連通圖【 】。

A.5 B.6 C.7 D.8

20、從有序表(14，20，34，58，69，72，87，96)中用二分查找法查找34時，其查找長度為【 】。

A. 2 B. 1 C. 3 D. 4

二、簡答與運算題(44分)

1、設有下列用二元組表示的數據結構，畫出它們的邏輯圖形表示，并指出它屬于哪種結構。(5分)

DS= (D，S)，其中：

D = { a,b,c,d,e,f,g}

S = { , ,,,,,}

2、學生成績表中有100個學生信息，每個學生信息有學號、姓名、成績，現在需要對學生成績進行管理，分析這個問題中的數據、數據元素、數據項、數據結構及可能涉及的基本操作(答出三個即可)。(8分)

3、在下列單鏈表中，寫出刪除元素b的語句系列，設結點類型為Node，它含兩個域：數據域data和指針域next。(5 分)

4、對下列二叉樹，回答問題。(5分)

(1)該二叉樹的深度為 ;

(2)該二叉樹的度為 ;

(3)該二叉樹的葉子節點個數為 ;

(4)該二叉樹的中序遍歷序列為 。

5、請根據給出的無向圖，回答下列問題：(9分)

(1)該圖的鄰接矩陣表示：

(2)該圖從節點1 出發的深度優先搜索序列;

(3)該圖從節點1出發的廣度優先搜索序列。

6、設有關鍵字{ 8, 15, 19, 10，27, 16, 11, 23 }，采用哈希法將它們填入到表長p=13的表中。要求：使用哈希函數H(key)=key % p ，解決沖突的方法采用線性探測再散列。(8分)

7、輸入數據(28,15, 39, 10，27, 16, 11, 43, 12)，寫出每一趟快速排序后的結果。(4分)

三、算法設計(16分)

假設用順序表存儲線性表中元素，順序表定義如下：

typedef int ElemType;

typedef struct{

ElemType *elem; //數組指針表示存儲空間基址

int length; //當前長度

int listsize; //當前分配的存儲容量

}Sqlist;

在以上存儲結構上設計算法：

(1)編寫求順序表L中最大值元素所在位置并用e返回其值的算法。

(2)假設順序表L有序，編寫算法，實現用折半查找法查找一個給定的元素key，找到則返回其在表中的下標，沒有則返回-1。