數(shù)據(jù)結(jié)構(gòu)模擬試題一及答案

千里之行，始于足下讓知識(shí)帶有溫度。第第2頁/共2頁精品文檔推薦數(shù)據(jù)結(jié)構(gòu)模擬試題一及答案數(shù)據(jù)結(jié)構(gòu)模擬試題一

一、推斷題（每小題1分，共15分）

1.計(jì)算機(jī)程序處理的對(duì)象可分為數(shù)據(jù)和非數(shù)據(jù)兩大類。

2.全體自然數(shù)按大小關(guān)系排成的序列是一個(gè)線性表。

3.在描述單向鏈表的結(jié)點(diǎn)類型時(shí)，必需首先描述數(shù)值字段，然后再描述指針字段。

4.挨次棧是一種規(guī)定了存儲(chǔ)辦法的棧。

5.樹形結(jié)構(gòu)中的每個(gè)結(jié)點(diǎn)都有一個(gè)前驅(qū)。

6.在任何一棵徹低二叉樹中，最多惟獨(dú)一個(gè)度為1的分支結(jié)點(diǎn)。

7.若某頂點(diǎn)是有向圖的根，則該頂點(diǎn)的入度一定是零。

8.假如某圖的鄰接矩陣有全零的行，沒有全零的列，則該圖一定是有向圖。

9.用一維數(shù)組表示矩陣可以節(jié)約存儲(chǔ)空間。

10.廣義表的長度與廣義表中含有多少個(gè)原子元素有關(guān)。

11.分塊查找的效率與線性表被分成多少塊有關(guān)。

12.散列表的負(fù)載因子等于存入散列表中的結(jié)點(diǎn)個(gè)數(shù)。

13.在起泡排序過程中，某些元素可能會(huì)向相反的方向移動(dòng)。

14.按某種規(guī)律關(guān)系組織起來的記錄的集合稱為規(guī)律記錄。

15.索引非挨次文件的特點(diǎn)是索引表中的索引項(xiàng)不一定按關(guān)鍵字大小有序羅列。

二、填空題（每空1分，共15分）

1.挨次表是一種_____________線性表。

2.若用Q[1]~Q[m]作為非循環(huán)挨次隊(duì)列的存儲(chǔ)空間，則對(duì)該隊(duì)列最多只能執(zhí)行___次插入

操作。

3.棧和隊(duì)列的區(qū)分在于________的不同。

4.在高度為h(h≥0)的二叉樹中至少有___個(gè)結(jié)點(diǎn)，至多有___個(gè)結(jié)點(diǎn)。

5.若用二叉鏈表來存儲(chǔ)具有m個(gè)葉子，n個(gè)分支結(jié)點(diǎn)的樹，則二叉鏈表中有___個(gè)左指針

域?yàn)榭盏慕Y(jié)點(diǎn)，有___個(gè)右指針域?yàn)榭盏慕Y(jié)點(diǎn)。

6.n個(gè)頂點(diǎn)的有根有向圖中至少有___條邊，至多有___條邊。

7.10行20列矩陣若用行優(yōu)先挨次表來表示，則矩陣中第8行第7列元素是挨次表中第___

個(gè)元素。

8.在各元素查找概率相等的狀況下，用挨次查找辦法從含有12個(gè)元素的有序表中查找一

個(gè)元素，元素間的平均比較次數(shù)是_____。

9.在歸并兩個(gè)長度為m的有序表時(shí)，排序碼的比較次數(shù)至少是___次，至多是___次。

10.在高度為3的6階B-樹中，至少有___個(gè)關(guān)鍵字，至多有___個(gè)關(guān)鍵字。

三、挑選題（每題2分，共30分）

1.計(jì)算機(jī)所處理的數(shù)據(jù)普通具有某種內(nèi)在聯(lián)系性，這是指________。

A．元素和元素之間存在某種關(guān)系B．?dāng)?shù)據(jù)和數(shù)據(jù)之間存在某種關(guān)系

C．元素內(nèi)部具有某種結(jié)構(gòu)D．?dāng)?shù)據(jù)項(xiàng)和數(shù)據(jù)項(xiàng)之間存在某種關(guān)系

2.假設(shè)挨次表目前有4個(gè)元素，第i個(gè)元素放在R[i]中，1≤i≤4。若把新插入元素存入R[6]，則________。

A．會(huì)產(chǎn)生運(yùn)行錯(cuò)誤B．R[1]~R[6]不構(gòu)成一個(gè)挨次表

C．挨次表的長度大于挨次表元素個(gè)數(shù)，會(huì)降低存儲(chǔ)空間利用率

D．挨次表元素序號(hào)和數(shù)組元素下標(biāo)不全都，會(huì)給使用帶來棘手

3.設(shè)H是不帶表頭結(jié)點(diǎn)循環(huán)單向鏈表的表頭指針，P是和H同類型的變量。當(dāng)P指向鏈表最后一個(gè)結(jié)點(diǎn)時(shí)，_________。

A．P所指結(jié)點(diǎn)指針字段的值為空B．P的值與H的值相等

C．P所指結(jié)點(diǎn)的地址與H的值相等D．P所指結(jié)點(diǎn)指針字段的值與H的值相等

4.棧的定義不涉及數(shù)據(jù)的__________。

A．規(guī)律結(jié)構(gòu)B．存儲(chǔ)結(jié)構(gòu)C．運(yùn)算D．規(guī)律結(jié)構(gòu)和存儲(chǔ)結(jié)構(gòu)

5.設(shè)5個(gè)元素進(jìn)棧的挨次是1,2,3,4,5，則出棧的挨次有可能是___________。

A．2,4,1,3,5B．3,4,1,5,2C．3,2,4,1,5D．4,1,3,2,5

6.若某棵二叉樹結(jié)點(diǎn)的前序序列和中序序列相同，則該二叉樹_________。

A．惟獨(dú)一個(gè)結(jié)點(diǎn)B．每個(gè)結(jié)點(diǎn)都沒有左孩子C．每個(gè)結(jié)點(diǎn)都沒有右孩子D．不存在7.對(duì)于一棵具有n個(gè)結(jié)點(diǎn)，度為3的樹來說，____________。

A．樹的高度至多是n-3B．樹的高度至多是n-2C．樹的最低高度是┏log3(n+1)┓D．至少在某一層上正巧有3個(gè)結(jié)點(diǎn)

8．n個(gè)頂點(diǎn)的有向圖假如可以舉行拓?fù)渑判颍瑒t可以斷定該有向圖

A．含n個(gè)強(qiáng)連通重量B．有唯一的入度為0的頂點(diǎn)C

D．是一個(gè)有根有向圖

9.特別矩陣用行優(yōu)先挨次表表示，_____________

A．簡化了矩陣元素之間的規(guī)律關(guān)系B．便于按行處理矩陣元素

C．無法按照行列號(hào)計(jì)算矩陣元素的存儲(chǔ)地址D．可以節(jié)約存儲(chǔ)空間

10.對(duì)一個(gè)非空的廣義表來說，______________。

A．可能不含任何原子元素B．至少含一個(gè)原子元素

C．其長度不小于其中任何一個(gè)子表的長度D．至少含一個(gè)非空的子表元素

11.在有序表（2,4,6,8,10,12,14,16,18,20）上用折半查找辦法查找13，依次被比較的是___________。

A．10,16,12,14B．10,16,12C．12,16,14D．10,16,12,13

12.含14個(gè)結(jié)點(diǎn)的平衡二叉排序樹，其最大深度是____。

A．4B．5C．6D．7

13．假如元素R1和R2有相同的排序碼，并且舉行歸并排序前，R1在R2的前面，則當(dāng)排序結(jié)束后，___________。

A．R1有可能在R2的后面B．R1一定在R2的后面

C．R1一定在R2的前面D．挑選R1或R2中的一個(gè)留在線性表中

14.下面4個(gè)序列中，惟獨(dú)___滿足堆的定義。

A．13,27,49,76,76,38,85,97B．76,38,27,49,76,85,13,97

C．13,76,49,76,27,38,85,97D．13,27,38,76,49,85,76,97

15．下面4種排序辦法中，屬于不穩(wěn)定的排序辦法是_________排序和_________排序。A．迅速B．歸并C．容易挑選D．折半插入

四、圖表題

1.已知樹結(jié)點(diǎn)的前序序列是abcdefgh，后序序列是cdebfhga，請(qǐng)畫出這棵樹的規(guī)律結(jié)構(gòu)圖。

2.采納基數(shù)排序法，對(duì)排序碼序列572,586,413,15,724,529,525,608,37,119按從小到大的次

序排序，請(qǐng)寫出每趟收集后的線性表。

五、算法填空題

假設(shè)G是n個(gè)頂點(diǎn)的連通無向圖的鄰接矩陣。下面的算法可用于對(duì)無向圖舉行深度遍歷。請(qǐng)?jiān)诳諆?nèi)填入適當(dāng)內(nèi)容，將算法補(bǔ)充完整。

Constn=10;

IntG[n][n];