?2019年北京建筑大學(xué)專升本數(shù)據(jù)結(jié)構(gòu)考試真題

2019年北京建筑大學(xué)專升本數(shù)據(jù)結(jié)構(gòu)考試真題

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

1、【 】是數(shù)據(jù)的最小單位。

A. 數(shù)據(jù)項(xiàng) B.數(shù)據(jù)元素 C.結(jié)構(gòu) D.算法

2、數(shù)據(jù)結(jié)構(gòu)是指數(shù)據(jù)以及它們之間的【 】。

A. 運(yùn)算 B.關(guān)系 C.計(jì)算方法 D.存儲(chǔ)

3、數(shù)據(jù)結(jié)構(gòu)在計(jì)算機(jī)中的表示可以分為【 】。

A.動(dòng)態(tài)結(jié)構(gòu)和靜態(tài)結(jié)構(gòu) B.順序結(jié)構(gòu)和鏈?zhǔn)浇Y(jié)構(gòu)

C.緊湊結(jié)構(gòu)和非緊湊結(jié)構(gòu) D.內(nèi)部結(jié)構(gòu)和外部結(jié)構(gòu)

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

A.找出數(shù)據(jù)結(jié)構(gòu)的合理性 B.研究算法的輸入輸出關(guān)系

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

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

A.數(shù)據(jù)元素 B.字符 C.邏輯關(guān)系 D.數(shù)據(jù)項(xiàng)

6、在具有n個(gè)元素的順序表中查找一個(gè)元素的時(shí)間復(fù)雜度是【 】。

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

7、帶頭結(jié)點(diǎn)的單鏈表L為空的判定條件是【 】。

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

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

8、如果最常用的操作是取線性表中第i個(gè)元素及其前驅(qū)，則采用【 】存儲(chǔ)方式最節(jié)省時(shí)間。

A.單鏈表 B.雙向鏈表 C.循環(huán)鏈表 D.順序表

9、遞歸程序執(zhí)行時(shí)，要用到的數(shù)據(jù)結(jié)構(gòu)是【 】。

A. 棧 B. 隊(duì)列 C. 線性表 D. 數(shù)組

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

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

11、串的長度是指【 】。

A.串中所含非空格字符的個(gè)數(shù) B.串中所含字符的個(gè)數(shù)

C.串中所含不同字符的個(gè)數(shù) D. 串中所含不同字母的個(gè)數(shù)

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

A. 便于進(jìn)行矩陣運(yùn)算 B. 便于輸入和輸出

C. 節(jié)省存儲(chǔ)空間 D.降低運(yùn)算的時(shí)間復(fù)雜度

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

A.元素之間具有線性關(guān)系的數(shù)據(jù) B.元素之間具有分支層次關(guān)系的數(shù)據(jù)

C.元素之間具有網(wǎng)狀關(guān)系的數(shù)據(jù) D.元素之間無聯(lián)系的數(shù)據(jù)

14、二叉樹第4層上至多有【 】結(jié)點(diǎn)。

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

15、若有向圖中的頂點(diǎn)能排成拓?fù)湫蛄?則該有向圖【 】。

A.是有向無環(huán)圖 B.不存在回路

C.含有多個(gè)入度為0的頂點(diǎn) D.是強(qiáng)連通圖

16、如果從無向圖中任一頂點(diǎn)出發(fā)進(jìn)行一次深度優(yōu)先搜索即可訪問圖中所有頂點(diǎn),則該圖一定是【 】。

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

17、具有20個(gè)葉結(jié)點(diǎn)的二叉樹中有【 】個(gè)度為2的結(jié)點(diǎn)，

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

18、在一個(gè)無向圖中，所有頂點(diǎn)的度數(shù)之和等于所有邊數(shù)【 】倍。

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

19、具有6個(gè)頂點(diǎn)的無向圖至少應(yīng)有幾條邊才能確保是一個(gè)連通圖【 】。

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

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

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

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

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

DS= (D，S)，其中：

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

S = { , ,,,,,}

2、學(xué)生成績表中有100個(gè)學(xué)生信息，每個(gè)學(xué)生信息有學(xué)號、姓名、成績，現(xiàn)在需要對學(xué)生成績進(jìn)行管理，分析這個(gè)問題中的數(shù)據(jù)、數(shù)據(jù)元素、數(shù)據(jù)項(xiàng)、數(shù)據(jù)結(jié)構(gòu)及可能涉及的基本操作(答出三個(gè)即可)。(8分)

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

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

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

(2)該二叉樹的度為 ;

(3)該二叉樹的葉子節(jié)點(diǎn)個(gè)數(shù)為 ;

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

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

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

(2)該圖從節(jié)點(diǎn)1 出發(fā)的深度優(yōu)先搜索序列;

(3)該圖從節(jié)點(diǎn)1出發(fā)的廣度優(yōu)先搜索序列。

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

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

三、算法設(shè)計(jì)(16分)

假設(shè)用順序表存儲(chǔ)線性表中元素，順序表定義如下：

typedef int ElemType;

typedef struct{

ElemType *elem; //數(shù)組指針表示存儲(chǔ)空間基址

int length; //當(dāng)前長度

int listsize; //當(dāng)前分配的存儲(chǔ)容量

}Sqlist;

在以上存儲(chǔ)結(jié)構(gòu)上設(shè)計(jì)算法：

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

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