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

目錄

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

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

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

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

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

第 1 頁，共 68 頁

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

編（一）

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

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

一、選擇題

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

A.1條，1條

B.1條，多條

C. 多條，1條

D. 多條，多條

【答案】A

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

2． 串的長度是指（ ）。

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

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

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

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

【答案】B

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

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

【答案】C

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

4． 對矩陣壓縮存儲是為了（ ）。

A. 方便運算

B. 方便存儲

C. 提高運算速度

第 2 頁，共 68 頁

D. 減少存儲空間

【答案】D

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

5． 棧和隊的共同點是（ ）。

A. 都是先進后出

B. 都是后進先出

C. 只允許在端點處插入和刪除元素

D. 沒有共同點

【答案】C

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

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

A. 最大概率

B. 最小概率

C. 平均概率

D. 同等概率

【答案】D

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

A.0、1

B.1、0

C.1、2

D.2、0

【答案】B

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

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

A. 樹

B. 字符串

C. 隊

D. 棧

【答案】A

第 3 頁，共 68 頁

【解析】非線性結(jié)構(gòu)是指存在一對多或者多對一的關(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é)點的左、右子結(jié)點中保存的關(guān)鍵字分別是（ ）。

A.13、48

B.24、48

C.24、53

D.24、90

【答案】C

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

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

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

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

第 4 頁，共 68 頁