目錄2017年青海民族大學(xué)計(jì)算機(jī)學(xué)院827計(jì)算機(jī)綜合之?dāng)?shù)據(jù)結(jié)構(gòu)考研導(dǎo)師圈點(diǎn)必考題匯編（一） 2 2017年青海民族大學(xué)計(jì)算機(jī)學(xué)院827計(jì)算機(jī)綜合之?dāng)?shù)據(jù)結(jié)構(gòu)考研導(dǎo)師圈點(diǎn)必考題匯編（二）.........

目錄

2017年青海民族大學(xué)計(jì)算機(jī)學(xué)院827計(jì)算機(jī)綜合之?dāng)?shù)據(jù)結(jié)構(gòu)考研導(dǎo)師圈點(diǎn)必考題匯編（一） 2 2017年青海民族大學(xué)計(jì)算機(jī)學(xué)院827計(jì)算機(jī)綜合之?dāng)?shù)據(jù)結(jié)構(gòu)考研導(dǎo)師圈點(diǎn)必考題匯編（二）

........................................................................................................................................ 15 2017年青海民族大學(xué)計(jì)算機(jī)學(xué)院827計(jì)算機(jī)綜合之?dāng)?shù)據(jù)結(jié)構(gòu)考研導(dǎo)師圈點(diǎn)必考題匯編（三）

........................................................................................................................................ 29 2017年青海民族大學(xué)計(jì)算機(jī)學(xué)院827計(jì)算機(jī)綜合之?dāng)?shù)據(jù)結(jié)構(gòu)考研導(dǎo)師圈點(diǎn)必考題匯編（四）

........................................................................................................................................ 41 2017年青海民族大學(xué)計(jì)算機(jī)學(xué)院827計(jì)算機(jī)綜合之?dāng)?shù)據(jù)結(jié)構(gòu)考研導(dǎo)師圈點(diǎn)必考題匯編（五）

........................................................................................................................................ 54

第 1 頁，共 68 頁

2017年青海民族大學(xué)計(jì)算機(jī)學(xué)院827計(jì)算機(jī)綜合之?dāng)?shù)據(jù)結(jié)構(gòu)考研導(dǎo)師圈點(diǎn)必考題匯

編（一）

說明：①本資料為VIP 學(xué)員內(nèi)部使用，整理匯編了歷屆導(dǎo)師圈點(diǎn)的重點(diǎn)試題及?？荚囶}。

——————————————————————————————————————————

一、選擇題

1． 如果本地域名服務(wù)無緩存，當(dāng)采用遞歸方法解析另一網(wǎng)絡(luò)某主機(jī)域名時(shí)，用戶主機(jī)、本地域名服務(wù)器發(fā)送的域名請求消息數(shù)分別為（ ）。

A.1條，1條

B.1條，多條

C. 多條，1條

D. 多條，多條

【答案】A

【解析】所謂遞歸查詢方式就是：如果主機(jī)所詢問的本地域名服務(wù)器不知道被查詢域名的IP 地址，那么本地域名服務(wù)器就以DNS 客戶的身份向其他服務(wù)器繼續(xù)發(fā)出查詢請求報(bào)文，而不是讓該主機(jī)自行下一步的查詢。所以主機(jī)只需向本地域名服務(wù)器發(fā)送一條域名請求，采用遞歸查詢方法，本地域名服務(wù)器也只需向上一級(jí)的根域名服務(wù)器發(fā)送一條域名請求，然后依次遞歸。正確選項(xiàng)為A 。

2． 串的長度是指（ ）。

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

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

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

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

【答案】B

【解析】串中字符的數(shù)目n 稱為字符的長度，不必考慮其中單個(gè)字符是否相等。

3． 下列序列中，（ ）是執(zhí)行第一趟快速排序后所得的序列。

【答案】C

【解析】快速排序?qū)?shù)據(jù)劃分成兩部分，其中一部分關(guān)鍵字比另一部分關(guān)鍵字小。

4． 對(duì)矩陣壓縮存儲(chǔ)是為了（ ）。

A. 方便運(yùn)算

B. 方便存儲(chǔ)

C. 提高運(yùn)算速度

第 2 頁，共 68 頁

D. 減少存儲(chǔ)空間

【答案】D

【解析】壓縮存儲(chǔ)也就是對(duì)那些沒用的元素不進(jìn)行存儲(chǔ)或者對(duì)那些具有一定規(guī)律的相同元素放在一個(gè)存儲(chǔ)空間，目的就是為了節(jié)省空間。

5． 棧和隊(duì)的共同點(diǎn)是（ ）。

A. 都是先進(jìn)后出

B. 都是后進(jìn)先出

C. 只允許在端點(diǎn)處插入和刪除元素

D. 沒有共同點(diǎn)

【答案】C

【解析】棧和隊(duì)列的區(qū)別是棧是先進(jìn)后出的數(shù)據(jù)結(jié)構(gòu)，隊(duì)列是先進(jìn)先出的數(shù)據(jù)結(jié)構(gòu)，棧和隊(duì)列的共同點(diǎn)是都只能在端點(diǎn)處插入和刪除元素。

6． 哈希函數(shù)有一個(gè)共同的性質(zhì)，即函數(shù)值應(yīng)當(dāng)以（ ）取其值域中的每個(gè)值。

A. 最大概率

B. 最小概率

C. 平均概率

D. 同等概率

【答案】D

7． 設(shè)與某資源相關(guān)聯(lián)的信號(hào)量初值為3, 當(dāng)前為1，若M 表示該資源的可用個(gè)數(shù)，N 表示等待該資源的進(jìn)程數(shù)，則M ，N 分別是（ ）。

A.0、1

B.1、0

C.1、2

D.2、0

【答案】B

【解析】信號(hào)量初值是3表示資源數(shù)有3個(gè)，當(dāng)前為1表示已經(jīng)用掉2個(gè)，剩余可用的資源數(shù)就只有1個(gè)了，由于資源有剩余，可見沒有其他進(jìn)程等待使用該資源，故進(jìn)程數(shù)為0。

8． 以下數(shù)據(jù)結(jié)構(gòu)中，（ ）是非線性數(shù)據(jù)結(jié)構(gòu)。

A. 樹

B. 字符串

C. 隊(duì)

D. 棧

【答案】A

第 3 頁，共 68 頁

【解析】非線性結(jié)構(gòu)是指存在一對(duì)多或者多對(duì)一的關(guān)系。常見的非線性結(jié)構(gòu)有樹結(jié)構(gòu)和圖結(jié)構(gòu)。

9． 下列排序算法中，占用輔助空間最多的是（ ）。

A. 歸并排序

B. 快速排序

C. 希爾排序

D. 堆排序

【答案】A

【解析】

歸并排序的輔助空間為

快速排序所占用的輔助空間為堆排序所占 用的輔助空間為

10．在下圖所示的平衡二叉樹中，插入關(guān)鍵字48后得到一棵新平衡二叉樹。在新平衡二叉樹中，關(guān)鍵字37 所在結(jié)點(diǎn)的左、右子結(jié)點(diǎn)中保存的關(guān)鍵字分別是（ ）。

A.13、48

B.24、48

C.24、53

D.24、90

【答案】C

【解析】題目中，插入48以后，樹根結(jié)點(diǎn)的平衡因子由-1變?yōu)?2, 失去平衡。這屬于RL （先右后左）型平衡旋轉(zhuǎn)，需做兩次（先右旋后左旋轉(zhuǎn)）旋轉(zhuǎn)操作。過程如下圖所示：

顯然，在調(diào)整后的新平衡二叉樹中，關(guān)鍵字37所在結(jié)點(diǎn)的左、右子結(jié)點(diǎn)中保存的關(guān)鍵字分別是24, 53。

11．下列有關(guān)總線定時(shí)的敘述中，錯(cuò)誤的是（ ）。

A. 異步通信方式中，全互鎖協(xié)議最慢

第 4 頁，共 68 頁