數(shù)據(jù)結(jié)構(gòu)自測(cè)題

1數(shù)據(jù)結(jié)構(gòu)網(wǎng)上自測(cè)習(xí)題

1.1（一）章

數(shù)據(jù)結(jié)構(gòu)中，與所使用的計(jì)算機(jī)無(wú)關(guān)的是數(shù)據(jù)的解析：邏輯結(jié)構(gòu)指數(shù)據(jù)元素之間的關(guān)系，與計(jì)算機(jī)無(wú)關(guān)。

存儲(chǔ)結(jié)構(gòu)

物理結(jié)構(gòu)

邏輯結(jié)構(gòu)

物理和存儲(chǔ)結(jié)構(gòu)

我的答案：

下列說(shuō)法不正確的是：

數(shù)據(jù)元素是數(shù)據(jù)的基本單位

數(shù)據(jù)項(xiàng)是數(shù)據(jù)中不可分割的最小標(biāo)識(shí)單位

數(shù)據(jù)可由若干個(gè)數(shù)據(jù)元素構(gòu)成

數(shù)據(jù)項(xiàng)可由若干個(gè)數(shù)據(jù)元素構(gòu)成

我的答案：

答案解析：數(shù)據(jù)元素可由若干個(gè)數(shù)據(jù)項(xiàng)構(gòu)成。

判斷題（共題，每題分）

數(shù)據(jù)結(jié)構(gòu)按邏輯結(jié)構(gòu)可分為兩大類(lèi)，它們分別是：順序結(jié)構(gòu)和鏈?zhǔn)浇Y(jié)構(gòu)。

對(duì)錯(cuò)

我的答案：

算法的便于閱讀和理解的特性稱(chēng)為

茁壯性高效率

易讀性正確性

1

我的答案：

2算法的計(jì)算量大小稱(chēng)為計(jì)算的

現(xiàn)實(shí)性難度

復(fù)雜性效率

我的答案：

1.2(二)章

1已知線性表1,經(jīng)運(yùn)算2之后，等于

121,2

21

2線性表1,a2下列i說(shuō)法正確的是n

每一個(gè)元素都有一個(gè)直接前驅(qū)和直接后繼

線性表中至少要有一個(gè)元素

表中各元素的羅列順序必須由小到大或者由大到小

除第一個(gè)元素和最后一個(gè)元素外，其余元素都有且僅有一個(gè)直接前驅(qū)和直接后繼

在n個(gè)結(jié)點(diǎn)的順序表中，算法的時(shí)間復(fù)雜度是(1)的操作是

訪問(wèn)第i個(gè)結(jié)點(diǎn)(1WiWn)和求第i個(gè)結(jié)點(diǎn)的直接前驅(qū)(2WiWn)

在第i個(gè)結(jié)點(diǎn)后插入一個(gè)新結(jié)點(diǎn)(1WiWn)

刪除第i個(gè)結(jié)點(diǎn)(1Wi近n)

將n個(gè)結(jié)點(diǎn)從小到大排序

對(duì)于順序表的優(yōu)缺點(diǎn)，以下說(shuō)法錯(cuò)誤的是

無(wú)需為表示結(jié)點(diǎn)間的邏輯關(guān)系而增加額外的存儲(chǔ)空間

2

B.可以方便地隨機(jī)存取表中的任一結(jié)點(diǎn)

插?入和刪除運(yùn)算較方便.

D.由于順序表要求占用連續(xù)的空間，存儲(chǔ)分配只能預(yù)先進(jìn)行靜態(tài)分配

指.針P和分別指向單鏈表的兩個(gè)元素，P所指元素是所指元素的前驅(qū)的判斷條件是:

.pnext==

B.next==p

.P二二

D.pnext==next

.線性表采用鏈?zhǔn)酱鎯?chǔ)時(shí)，其地址：D

必.須是連續(xù)的

B.部份地址必須是連續(xù)的

一?定是不連續(xù)的

D.連續(xù)與否均可以

在.單向循環(huán)鏈表中，若頭指針為head,那末p所指結(jié)點(diǎn)為尾結(jié)點(diǎn)的條件是：D

.p==NULL

B.p->next二二NULL

.p二二head

D.pTnext二二head

設(shè).指針P指向雙鏈表的某一結(jié)點(diǎn)，則雙鏈表結(jié)構(gòu)的對(duì)稱(chēng)性可表示為

?PPnext-pnextnext

B.pPnext=pnextnext

?PPnext==pnextP

D.pnextnext==ppP

3

1.3（三）章

棧操作數(shù)據(jù)的原則是：

先進(jìn)先出后進(jìn)先出

后進(jìn)后出不分順序

設(shè)數(shù)組元素...............挨次通過(guò)棧結(jié)構(gòu)，則不可能排成的序列為：

若用鏈接方式實(shí)現(xiàn)棧，則出棧時(shí)：

必須判別棧是否滿(mǎn)必須判別棧是否空必須判別棧是否空對(duì)棧不作任何判別

設(shè)計(jì)一個(gè)判別表達(dá)式中左、右括號(hào)是否正確配對(duì)浮現(xiàn)的算法，采用哪種數(shù)據(jù)結(jié)構(gòu)最佳？

線性表?xiàng)ｊ?duì)列二叉樹(shù)

任何遞歸算法都能通過(guò)使用那種數(shù)據(jù)結(jié)構(gòu)轉(zhuǎn)化為非遞歸算法？

線性表?xiàng)ｊ?duì)列二叉樹(shù)

若一個(gè)初始為空的隊(duì)列的進(jìn)隊(duì)序列是，，，，則出隊(duì)序列是（）：

循環(huán)隊(duì)列存儲(chǔ)在數(shù)組中，則入隊(duì)時(shí)隊(duì)尾指示變量的變化方法為（）：

1.4（四）章

4

下述陳述錯(cuò)誤的是。（）

空白串是任意串的子串空白串是任意串的子串

串常量不同于串變量串常量不同于串變量

串的長(zhǎng)度是指。（）

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

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

判斷題（共題，每題分）

兩個(gè)長(zhǎng)度不相同的串有可能相等。（）

對(duì)錯(cuò)

兩個(gè)長(zhǎng)度不相同的串有可能相等。（）

有效位移是惟獨(dú)是有效位移

惟獨(dú)，是有效位移惟獨(dú)，，是有效位移

下面關(guān)于串的敘述中，哪一個(gè)是不正確的。（）

串是字符的有限序列空串是由空格構(gòu)成的串

模式匹配是串的一種重要運(yùn)算串既可以采用順序存儲(chǔ)，也可以采用鏈?zhǔn)酱鎯?chǔ)

1.5（五）章

有一個(gè)行列的二維數(shù)組，用順序查找法在該數(shù)組中查找值為的元素的時(shí)間復(fù)雜度是（）

1.6（六）章

5

一棵個(gè)葉子結(jié)點(diǎn)的徹底二叉樹(shù)最多有個(gè)結(jié)點(diǎn)。（）

下述陳述正確的是。（）

下述陳述正確的是。（）徹底二叉樹(shù)一定是滿(mǎn)二叉樹(shù)嚴(yán)格的二叉樹(shù)一定是徹底二叉樹(shù)

多選題（共題，每題分）

具有個(gè)結(jié)點(diǎn)的樹(shù)共有（）種不同的形態(tài)，具有個(gè)結(jié)點(diǎn)的二叉樹(shù)共有（）種不同的形態(tài)

設(shè)根的層數(shù)為，若深度為的徹底二叉樹(shù)具有至少的結(jié)點(diǎn)，則編號(hào)最小和編號(hào)最大的葉子結(jié)點(diǎn)編號(hào)分別是

。個(gè)結(jié)點(diǎn)的徹底二叉樹(shù)高度為取下整。

對(duì)錯(cuò)

我的答案：

已知某二叉樹(shù)的前序序列為，中序序列為，則其后序序列為（）

個(gè)結(jié)點(diǎn)的線索二叉樹(shù)中線索數(shù)目為（）

一棵左子樹(shù)為空的二叉樹(shù)在前序線索化后，其中空的鏈域個(gè)數(shù)為（）

不確定

在以下四種樹(shù)的存儲(chǔ)結(jié)構(gòu)中，容易實(shí)現(xiàn)查找指定結(jié)點(diǎn)的祖先和后代的是（）

雙親鏈表表示法孩子鏈表表示法

雙親孩子鏈表表示法雙親孩子鏈表表示法

6

下述編碼中哪一個(gè)不是前綴碼。（）

1.7（七）章

在下面有關(guān)有向圖的頂點(diǎn)的度的敘述中，正確的是（）

個(gè)頂點(diǎn)的強(qiáng)連通圖中所有頂點(diǎn)的度之和的最小值為

頂點(diǎn)的出度等于其它頂點(diǎn)指向該頂點(diǎn)的有向邊的數(shù)目

頂點(diǎn)的出度等于其它頂點(diǎn)指向該頂點(diǎn)的有向邊的數(shù)目

每一個(gè)頂點(diǎn)的入度等于出度

有個(gè)頂點(diǎn)的圖，若用鄰接矩陣表示，則該矩陣中元素的個(gè)數(shù)為（）

圖的深度優(yōu)先搜索是樹(shù)的（）遍歷的推廣

先序中序后序?qū)有?/p>

我的答案：

用鄰接表表示圖進(jìn)行廣度優(yōu)先搜索時(shí)，通常采用（）來(lái)實(shí)現(xiàn)算法

線性表?xiàng)ｊ?duì)列樹(shù)

我的答案：

有個(gè)頂點(diǎn)的連通圖的生成樹(shù)有（）條無(wú)向邊

我的答案：

有向無(wú)環(huán)圖簡(jiǎn)稱(chēng)（）

7

我的答案:

求一個(gè)頂點(diǎn)到其他各頂點(diǎn)的最短路徑可以使用（）算法

弗洛伊德克魯斯卡爾迪杰斯特拉普里姆

我的答案：

弗洛伊德算法的時(shí)間復(fù)雜度是（）

我的答案：

1.8（八）章

折半插入排序的時(shí)間復(fù)雜度為（）

我的答案：

在對(duì)一組記錄｛.............................,｝進(jìn)行直接插入排序時(shí)，當(dāng)把第個(gè)記錄插入到

有序表時(shí)，為尋覓插入位置需比較（）次。

我的答案：

當(dāng)初始序列有序時(shí)，冒泡排序的時(shí)間復(fù)雜度為（）。

我的答案：

每次把待排序的元素劃分為左、右兩個(gè)子區(qū)間，其中左區(qū)間中元素的關(guān)鍵字均小于等于基準(zhǔn)元素的關(guān)鍵字，

右區(qū)間中元素的關(guān)鍵字均大于基準(zhǔn)元素的關(guān)鍵字，則此排序方法叫做（）。

直接插入排序希爾排序

8

冒泡排序快速排序

我的答案：

快速排序在（）情況下最不利于發(fā)揮其長(zhǎng)處。

被排序的數(shù)據(jù)量很大

被排序的數(shù)據(jù)已基本有序

被排序的數(shù)據(jù)徹底無(wú)序

被排序的數(shù)據(jù)中最大值與最小值相差不大

我的答案：

在堆排序過(guò)程中，由個(gè)待排序的記錄建成初始堆需要（）次篩選。

我的答案：

一組記錄的關(guān)鍵字為（，，，，，，，，，），其中含有個(gè)長(zhǎng)度為的有序表，用

歸并排序方法對(duì)該序列進(jìn)行一趟歸并后的結(jié)果為（）。

我的答案：

在歸并排序中，若待排序記錄的個(gè)數(shù)為，則共需要進(jìn)行（）趟歸并。

我的答案：

在所有的內(nèi)部排序方法中，關(guān)鍵字的比較次數(shù)與記錄的初始羅列無(wú)關(guān)的是（）

希爾排序希爾排序

直接插入排序簡(jiǎn)單選擇排序

我的答案：

9

在內(nèi)部排序中，要求附加的內(nèi)存容量最大的是（）

快速排序選擇排序

歸并排序