數(shù)據(jù)結(jié)構(gòu)學(xué)習(xí)通章節(jié)答案期末考試題庫(kù)2023年

數(shù)據(jù)結(jié)構(gòu)學(xué)習(xí)通超星課后章節(jié)答案期末考試題庫(kù)2023年⑵使用三元組表存儲(chǔ)稀疏矩陣的元素，有時(shí)并不能節(jié)省存儲(chǔ)空間。

答案:

對(duì)

⑴數(shù)組是一種復(fù)雜的數(shù)據(jù)結(jié)構(gòu)，數(shù)組元素之間的關(guān)系既不是線性的，也不是樹(shù)形的。

答案:

錯(cuò)

⑷稀疏矩陣一般壓縮存儲(chǔ)方法有兩種，分別是（）和（）。

答案:

三元組順序表###十字鏈表

⑶設(shè)有一個(gè)10階的對(duì)稱矩陣A采用壓縮存儲(chǔ)，A[0][0]為第一個(gè)元素，其存儲(chǔ)地址為d，每個(gè)元素占1個(gè)存儲(chǔ)單元，則元素A[8][5]的存儲(chǔ)地址為（）。

答案:

d+41

⑵二維數(shù)組A中行下標(biāo)從10到20，列下標(biāo)從5到10，按行優(yōu)先存儲(chǔ)，每個(gè)元素占4個(gè)存儲(chǔ)單元，A[10][5]的存儲(chǔ)地址是1000，則元素A[15][10]的存儲(chǔ)地址是（）。

答案:

1140

⑴數(shù)組通常只有兩種運(yùn)算：（存取）和（修改），這決定了數(shù)組通常采用（）結(jié)構(gòu)來(lái)實(shí)現(xiàn)存儲(chǔ)。

答案:

順序存儲(chǔ)

兩個(gè)串相等的充分必要條件是長(zhǎng)度相同且（）的字符相等。

答案:

對(duì)應(yīng)位置

⑼串是一種特殊的線性表，其特殊性體現(xiàn)在數(shù)據(jù)元素的類型是一個(gè)（）。

答案:

字符

⑻下面的說(shuō)法中，不正確的是（

）

答案:

稀疏矩陣中大量值為零的元素分布有規(guī)律，因此可以采用三元組表方法存儲(chǔ)

⑸下面（

）不屬于特殊矩陣。

答案:

稀疏矩陣

⑷對(duì)特殊矩陣采用壓縮存儲(chǔ)的目的主要是為了（

）

答案:

減少不必要的存儲(chǔ)空間

⑶下面的說(shuō)法中，不正確的是（

）

答案:

除了插入與刪除操作外，數(shù)組的基本操作還有存取、修改、檢索和排序等

⑵將數(shù)組稱為隨機(jī)存取結(jié)構(gòu)是因?yàn)椋?/p>

）

答案:

對(duì)數(shù)組任一元素的存取時(shí)間是相等的

⑸用一維數(shù)組存儲(chǔ)二叉樹(shù)時(shí)，總是以前序遍歷存儲(chǔ)結(jié)點(diǎn)。

答案:

錯(cuò)

⑷由樹(shù)轉(zhuǎn)換成二叉樹(shù)，其根結(jié)點(diǎn)的右子樹(shù)總是空的。

答案:

對(duì)

⑶二叉樹(shù)是度為2的樹(shù)。

答案:

錯(cuò)

⑵在二叉樹(shù)的前序遍歷序列中，任意一個(gè)結(jié)點(diǎn)均處在其子女的前面。

答案:

對(duì)

⑴在線索二叉樹(shù)中，任一結(jié)點(diǎn)均有指向其前趨和后繼的線索。

答案:

錯(cuò)

（10）在有n個(gè)葉子的哈夫曼樹(shù)中，葉子結(jié)點(diǎn)總數(shù)為（），分支結(jié)點(diǎn)總數(shù)為（）。

答案:

n###n-1

⑼在具有n個(gè)結(jié)點(diǎn)的二叉鏈表中，共有（）個(gè)指針域，其中（）個(gè)指針域用于指向其左右孩子，剩下的（）個(gè)指針域則是空的。

答案:

2n###n-1###n+1

⑻某二叉樹(shù)的前序遍歷序列是ABCDEFG，中序遍歷序列是CBDAFGE，則其后序遍歷序列是（）。

答案:

CDBGFEA

⑺已知一棵度為3的樹(shù)有2個(gè)度為1的結(jié)點(diǎn)，3個(gè)度為2的結(jié)點(diǎn)，4個(gè)度為3的結(jié)點(diǎn)。則該樹(shù)中有（）個(gè)葉子結(jié)點(diǎn)。

答案:

12

⑹具有100個(gè)結(jié)點(diǎn)的完全二叉樹(shù)的葉子結(jié)點(diǎn)數(shù)為（）。

答案:

50

⑶一棵二叉樹(shù)的第i（i≥1）層最多有（）個(gè)結(jié)點(diǎn)；一棵有n（n>0）個(gè)結(jié)點(diǎn)的滿二叉樹(shù)共有（）個(gè)葉子結(jié)點(diǎn)和（）個(gè)非終端結(jié)點(diǎn)。

答案:

(n+1)/2###(n-1)/2

⑵樹(shù)中某結(jié)點(diǎn)的子樹(shù)的個(gè)數(shù)稱為該結(jié)點(diǎn)的（），子樹(shù)的根結(jié)點(diǎn)稱為該結(jié)點(diǎn)的（），該結(jié)點(diǎn)稱為其子樹(shù)根結(jié)點(diǎn)的（）。

答案:

度###孩子###雙親

⑴樹(shù)是n（n≥0）結(jié)點(diǎn)的有限集合，在一棵非空樹(shù)中，有（有且僅有一個(gè)）個(gè)根結(jié)點(diǎn)，其余的結(jié)點(diǎn)分成m（m＞0）個(gè)（）的集合，每個(gè)集合都是根結(jié)點(diǎn)的子樹(shù)。

答案:

互不相交

（10）討論樹(shù)、森林和二叉樹(shù)的關(guān)系，目的是為了（）。

答案:

B

將樹(shù)、森林按二叉樹(shù)的存儲(chǔ)方式進(jìn)行存儲(chǔ)并利用二叉樹(shù)的算法解決樹(shù)的有關(guān)問(wèn)題

⑺任何一棵二叉樹(shù)的葉子結(jié)點(diǎn)在前序、中序、后序遍歷序列中的相對(duì)次序（）。

答案:

A

肯定不發(fā)生改變

⑹一個(gè)高度為h的滿二叉樹(shù)共有n個(gè)結(jié)點(diǎn)，其中有m個(gè)葉子結(jié)點(diǎn)，則有（

）成立。

答案:

D

n=2m-1

⑷線索二叉樹(shù)中某結(jié)點(diǎn)R沒(méi)有左孩子的充要條件是（

）。

答案:

C

R.ltag=1

⑷邏輯結(jié)構(gòu)與數(shù)據(jù)元素本身的內(nèi)容和形式無(wú)關(guān)。

答案:

對(duì)

⑶二叉樹(shù)的前序序列和后序序列正好相反，則該二叉樹(shù)一定是（）的二叉樹(shù)。

答案:

B

高度等于其結(jié)點(diǎn)數(shù)

⑴如果結(jié)點(diǎn)A有3個(gè)兄弟，B是A的雙親，則結(jié)點(diǎn)B的度是（

）。

答案:

4

要求：提交運(yùn)行截圖和實(shí)驗(yàn)報(bào)告。

答案:

見(jiàn)教材

⑻

在

AOE

網(wǎng)中一定只有一條關(guān)鍵路徑.

答案:

錯(cuò)

⑺

若一個(gè)有向圖的鄰接矩陣中對(duì)角線以下元素均為零，則該圖的拓?fù)湫蛄斜囟ù嬖凇?/p>

答案:

對(duì)

⑹

在一個(gè)有向圖的拓?fù)湫蛄兄?，若頂點(diǎn)

a

在頂點(diǎn)

b

之前，則圖中必有一條弧。

答案:

錯(cuò)

⑸

對(duì)任意一個(gè)圖，從某頂點(diǎn)出發(fā)進(jìn)行一次深度優(yōu)先或廣度優(yōu)先遍歷，可訪問(wèn)圖的所有頂點(diǎn)。

答案:

錯(cuò)

⑷

無(wú)向圖的鄰接矩陣一定是對(duì)稱的，有向圖的鄰接矩陣一定是不對(duì)稱的

答案:

錯(cuò)

⑶

圖

G

的生成樹(shù)是該圖的一個(gè)極小連通子圖

答案:

錯(cuò)

⑵

用鄰接矩陣存儲(chǔ)圖，所占用的存儲(chǔ)空間大小只與圖中頂點(diǎn)個(gè)數(shù)有關(guān)，而與圖的邊數(shù)無(wú)關(guān)。

答案:

對(duì)

⑴

一個(gè)有向圖的鄰接表和逆鄰接表中的結(jié)點(diǎn)個(gè)數(shù)一定相等。

答案:

對(duì)

⑼

如果一個(gè)有向圖不存在（

），則該圖的全部頂點(diǎn)可以排列成一個(gè)拓?fù)湫蛄小?/p>

答案:

回路

⑺

圖的深度優(yōu)先遍歷類似于樹(shù)的（

）遍歷，它所用到的數(shù)據(jù)結(jié)構(gòu)是（

）；圖的廣度優(yōu)先遍歷類似于樹(shù)的（

）遍歷，它所用到的數(shù)據(jù)結(jié)構(gòu)是（

）。

答案:

前序###棧###層序###隊(duì)列

⑸基于某種邏輯結(jié)構(gòu)之上的基本操作，其實(shí)現(xiàn)是唯一的。

答案:

錯(cuò)

⑹

有向圖

G

用鄰接矩陣

A[n][n]存儲(chǔ)，其第

i

行的所有元素之和等于頂點(diǎn)

i

的（

）。

答案:

出度

⑸

已知一個(gè)有向圖的鄰接矩陣表示，計(jì)算第

j

個(gè)頂點(diǎn)的入度的方法是（

）。

答案:

求第j列的所有元素之和

⑷

已知無(wú)向圖

G

的頂點(diǎn)數(shù)為

n，邊數(shù)為

e，其鄰接表表示的空間復(fù)雜度為（

）。

答案:

O(n+e)

⑶

圖的存儲(chǔ)結(jié)構(gòu)主要有兩種，分別是（

）和（

）。

答案:

鄰接矩陣###鄰接表

⑵

任何連通圖的連通分量只有一個(gè)，即是（

）。

答案:

其自身

⑴

設(shè)無(wú)向圖

G

中頂點(diǎn)數(shù)為

n，則圖

G

至少有（

）條邊，至多有

n(n-1)/2

條邊；若

G

為有向圖，則至少有（

）

條邊，至多有

n(n-1)

條邊。

答案:

0###0

⑽

下面關(guān)于工程計(jì)劃的

AOE

網(wǎng)的敘述中，不正確的是（

）

答案:

B

任何一個(gè)關(guān)鍵活動(dòng)提前完成，那么整個(gè)工程將會(huì)提前完成

⑼

判定一個(gè)有向圖是否存在回路除了可以利用拓?fù)渑判蚍椒ㄍ猓€可以用（

）。

答案:

D

深度優(yōu)先遍歷算法

⑻

最小生成樹(shù)指的是（

）

。

答案:

C

連通網(wǎng)中所有生成樹(shù)中權(quán)值之和為最小的生成樹(shù)

⑺

G

是一個(gè)非連通無(wú)向圖，共有

28

條邊，則該圖至少有（

）個(gè)頂點(diǎn)。

答案:

9

⑹

設(shè)無(wú)向圖

G=(V,

E)和

G'

=(V',

E'

)，如果

G'

是

G

的生成樹(shù)，則下面的說(shuō)法中錯(cuò)誤的是（

）。

答案:

B

G'

為

G

的連通分量

⑸

圖的生成樹(shù)（唯一性不能確定），n

個(gè)頂點(diǎn)的生成樹(shù)有（

）條邊。

答案:

n-1

⑶

含

n

個(gè)頂點(diǎn)的連通圖中的任意一條簡(jiǎn)單路徑，其長(zhǎng)度不可能超過(guò)（

）。

答案:

n-1

⑴

在一個(gè)無(wú)向圖中，所有頂點(diǎn)的度數(shù)之和等于所有邊數(shù)的（

）倍。

答案:

2

要求：輸出順時(shí)針數(shù)字旋轉(zhuǎn)方針，N=9

答案:

見(jiàn)教材

英文字母的概率從網(wǎng)上查找

答案:

如題

4.實(shí)現(xiàn)查找功能

答案:

見(jiàn)教材

當(dāng)裝填因子小于1時(shí)，向散列表中存儲(chǔ)元素時(shí)不會(huì)引起沖突。

答案:

錯(cuò)

散列技術(shù)的查找效率主要取決于散列函數(shù)和處理沖突的方法。

答案:

錯(cuò)

若二叉排序樹(shù)中關(guān)鍵碼互不相同，則其中最小元素和最大元素一定是葉子結(jié)點(diǎn)。

答案:

錯(cuò)

二叉排序樹(shù)的查找和折半查找的時(shí)間性能相同。

答案:

錯(cuò)

二叉排序樹(shù)的充要條件是任一結(jié)點(diǎn)的值均大于其左孩子的值，小于其右孩子的值。

答案:

錯(cuò)

與其他方法相比，散列查找法的特點(diǎn)是通過(guò)（）計(jì)算記錄的存儲(chǔ)地址，并進(jìn)行一定的比較。

答案:

關(guān)鍵碼

在各種查找方法中，平均查找長(zhǎng)度與結(jié)點(diǎn)個(gè)數(shù)無(wú)關(guān)的查找方法是（）。

答案:

散列查找

在散列技術(shù)中，處理沖突的兩種主要方法是（

）和（

）。

答案:

開(kāi)放定址法###拉鏈法

假定一個(gè)數(shù)列{25，43，62，31，48，56}，采用的散列函數(shù)為H(k)=kmod7，則元素48的同義詞是（）。

答案:

62

長(zhǎng)度為20的有序表采用折半查找，共有（）個(gè)元素的查找長(zhǎng)度為3。

答案:

4

對(duì)于數(shù)列{25，30，8，5，1，27，24，10，20，21，9，28，7，13，15}，假定每個(gè)結(jié)點(diǎn)的查找概率相同，若用順序存儲(chǔ)結(jié)構(gòu)組織該數(shù)列，則查找一個(gè)數(shù)的平均比較次數(shù)為（）。若按二叉排序樹(shù)組織該數(shù)列，則查找一個(gè)數(shù)的平均比較次數(shù)為（）。

答案:

8###59/15

設(shè)有一個(gè)已按各元素值排好序的線性表，長(zhǎng)度為125，用折半查找與給定值相等的元素，若查找成功，則至少需要比較（）次，至多需比較（）次。

答案:

1###7

順序查找技術(shù)適合于存儲(chǔ)結(jié)構(gòu)為（順序存儲(chǔ)和鏈接存儲(chǔ)）的線性表，而折半查找技術(shù)適用于存儲(chǔ)結(jié)構(gòu)為（

）存儲(chǔ)的線性表，并

且表中的元素必須是按（

）有序。

答案:

順序###關(guān)鍵碼

在采用線性探測(cè)法處理沖突所構(gòu)成的閉散列表上進(jìn)行查找，可能要探測(cè)多個(gè)位置，在查找成功的情況下，所探測(cè)的這些位置的鍵值（）。

答案:

C

不一定都是同義詞

散列技術(shù)中的沖突指的是（）。

答案:

D

不同鍵值的元素對(duì)應(yīng)于相同的存儲(chǔ)地址

二叉排序樹(shù)中，最小值結(jié)點(diǎn)的（）。

答案:

A

左指針一定為空

長(zhǎng)度為12的有序表采用順序存儲(chǔ)結(jié)構(gòu)，采用折半查找技術(shù)，在等概率情況下，查找成功時(shí)的平均查找長(zhǎng)度是（37/12），查找失敗時(shí)的平均查找長(zhǎng)度是（）。

答案:

62/13

有一個(gè)按元素值排好序的順序表（長(zhǎng)度大于2），分別用順序查找和折半查找與給定值相等的元素，比較次數(shù)分別是s和b，在查找成功的情況下，s和b的關(guān)系是（）。

答案:

不一定

靜態(tài)查找與動(dòng)態(tài)查找的根本區(qū)別在于（）。

答案:

B

施加在其上的操作不同

設(shè)有鍵值序列（k1,k2,…,kn），當(dāng)i>n/2時(shí)，任何一個(gè)子序列（ki,ki+1,…,kn）一定是堆。

答案:

對(duì)

堆排序所需的時(shí)間與待排序的記錄個(gè)數(shù)無(wú)關(guān)。

答案:

錯(cuò)

對(duì)n個(gè)記錄的集合進(jìn)行快速排序，所需要的附加空間是Ο(n)。

答案:

錯(cuò)

當(dāng)待排序的元素很大時(shí)，為了交換元素的位置，移動(dòng)元素要占用較多的時(shí)間，這是影響時(shí)間復(fù)雜性的主要因素。

答案:

對(duì)

如果某種排序算法是不穩(wěn)定的，則該排序方法沒(méi)有實(shí)際應(yīng)用價(jià)值。

答案:

錯(cuò)

對(duì)于鍵值序列（12，13，11，18，60，15，7，18，25，100），用篩選法建堆，必須從鍵值為（）的結(jié)點(diǎn)開(kāi)始。

答案:

60

如果要將序列（50，16，23，68，94，70，73）建成堆，只需把16與（）交換。

答案:

50

利用簡(jiǎn)單選擇排序?qū)個(gè)記錄進(jìn)行排序，最壞情況下，記錄交換的次數(shù)為（）。

答案:

n-1

對(duì)一組記錄（54,38,96,23,15,72,60,45,83）進(jìn)行快速排序，在遞歸調(diào)用中使用的棧所能達(dá)到的最大深度為（）。

答案:

3

對(duì)一組記錄（54,38,96,23,15,72,60,45,83）進(jìn)行直接插入排序，當(dāng)把第7個(gè)記錄60插入到有序表時(shí)，為尋找插入位置需比較（）次。

答案:

3

對(duì)n個(gè)元素進(jìn)行起泡排序，在（正序）情況下比較的次數(shù)最少，其比較次數(shù)為（）。在（反序）情況下比較次數(shù)最多，其比較次數(shù)為（）。

答案:

n-1###n(n-1)/2;(n-1)n/2;n*(n-1)/2;(n-1)*n/2

排序的主要目的是為了以后對(duì)已排序的數(shù)據(jù)元素進(jìn)行（）。

答案:

查找

（）方法是從未排序序列中挑選元素，并將其放入已排序序列的一端。

答案:

D

選擇排序

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

答案:

C

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

設(shè)有5000個(gè)元素，希望用最快的速度挑選出前10個(gè)最大的，采用（）方法最好。

答案:

B

堆排序

當(dāng)待排序序列基本有序或個(gè)數(shù)較小的情況下，最佳的內(nèi)部排序方法是（直接插入排序），就平均時(shí)間而言，（）最佳。

答案:

D

快速排序

堆的形狀是一棵（）。

答案:

C

完全二叉樹(shù)

對(duì)初始狀態(tài)為遞增有序的序列進(jìn)行排序，最省時(shí)間的是（插入排序），最費(fèi)時(shí)間的是（快速排序）。已知待排序序列中每個(gè)元素距其最終位置不遠(yuǎn)，則采用（）方法最節(jié)省時(shí)間。

答案:

B

插入排序

下列序列中，（）是執(zhí)行第一趟快速排序的結(jié)果。

答案:

A[da，ax，eb，de，bb]ff[ha，gc]

下述排序方法中，比較次數(shù)與待排序記錄的初始狀態(tài)無(wú)關(guān)的是（）。

答案:

C

選擇排序和歸并排序

m階B—樹(shù)中任何一個(gè)結(jié)點(diǎn)的左右子樹(shù)的高度都相等。

答案:

對(duì)

m階B—樹(shù)中每個(gè)結(jié)點(diǎn)的子樹(shù)個(gè)數(shù)都大于或等于

m/2。

答案:

錯(cuò)

在索引順序表的查找中，對(duì)索引表既可以采取順序查找，也可以采用折半查找。

答案:

對(duì)

對(duì)于B—樹(shù)中任何一個(gè)非葉結(jié)點(diǎn)中的某個(gè)關(guān)鍵碼k來(lái)說(shuō)，比k大的最小關(guān)鍵碼和比k小的最大關(guān)鍵碼一定都在葉結(jié)點(diǎn)中。

答案:

對(duì)

B—樹(shù)是一種動(dòng)態(tài)索引結(jié)構(gòu)，它既適用于隨機(jī)查找，也適用于順序查找。

答案:

錯(cuò)

在索引順序表上采用分塊查找，在等概率情況下，其平均查找長(zhǎng)度不僅與子表個(gè)數(shù)有關(guān)，而且與每一個(gè)子表中的對(duì)象個(gè)數(shù)有關(guān)。

答案:

對(duì)

在一棵高度為h的B—樹(shù)中，葉子結(jié)點(diǎn)處于第（）層，當(dāng)向該B—樹(shù)中插入一個(gè)新關(guān)鍵碼時(shí)，為查找插入位置需讀?。ǎ﹤€(gè)結(jié)點(diǎn)。

答案:

h+1###h

在一棵B—樹(shù)中刪除關(guān)鍵碼，若最終引起樹(shù)根結(jié)點(diǎn)的合并，則新樹(shù)比原樹(shù)的高度（）。

答案:

減少

1

層

一棵5階B—樹(shù)中，除根結(jié)點(diǎn)外，每個(gè)結(jié)點(diǎn)的子樹(shù)樹(shù)目最少為（），最多為（）。

答案:

3###5

在10階B—樹(shù)中根結(jié)點(diǎn)所包含的關(guān)鍵碼個(gè)數(shù)最多為（），最少為（）。

答案:

9###1

分塊有序是指將文件劃分為若干塊，（）無(wú)序，（）有序。

答案:

塊內(nèi)###塊間

在索引表中，每個(gè)索引項(xiàng)至少包含（）和關(guān)鍵碼對(duì)應(yīng)的記錄在存儲(chǔ)器中的（）等信息

答案:

關(guān)鍵碼###位置

用快速排序法，希爾排序法，直接插入排序法，堆排序法對(duì)10000個(gè)整數(shù)進(jìn)行排序。要求：提交四個(gè)排序時(shí)間截圖。排列好的數(shù)據(jù)不需要截圖，代碼也不需要截圖

答案:

見(jiàn)書本

設(shè)散列表表長(zhǎng)m=14，散列函數(shù)H(k)=kmod11。表中已有15、38、61、84四個(gè)元素，如果用線性探側(cè)法處理沖突，則元素49的存儲(chǔ)地址是（）。

答案:

8

④假定每個(gè)關(guān)鍵字的查找概率相等，求查找成功時(shí)的平均查找長(zhǎng)度。

答案:

①畫表如下：012345678910111213141516173217634924401030314647②查找63,首先要與H(63)=63%16=15號(hào)單元內(nèi)容比較，即63vs31,no;然后順移，與46,47,32,17,63相比，一共比較了6次?、鄄檎?0,首先要與H(60)=60%16=12號(hào)單元內(nèi)容比較，但因?yàn)?2號(hào)單元為空（應(yīng)當(dāng)有空標(biāo)記），所以應(yīng)當(dāng)只比較這一次即可。④對(duì)于黑色數(shù)據(jù)元素，各比較1次；共6次；對(duì)紅色元素則各不相同，要統(tǒng)計(jì)移位的位數(shù)?！?3”需要6次，“49”需要3次，“40”需要2次，“46”需要3次，“47”需要3次，所以ASL=1/11（6＋2＋3×3+6）＝23/11

由3個(gè)結(jié)點(diǎn)可以構(gòu)造出多少種不同的二叉樹(shù)？（

）

答案:

5

對(duì)二叉樹(shù)的結(jié)點(diǎn)從1開(kāi)始進(jìn)行連續(xù)編號(hào)，要求每個(gè)結(jié)點(diǎn)的編號(hào)大于其左、右孩子的編號(hào)，同一結(jié)點(diǎn)的左右孩子中，其左孩子的編號(hào)小于其右孩子的編號(hào)，可采用（

）遍歷實(shí)現(xiàn)編號(hào)。

答案:

后序

利用二叉鏈表存儲(chǔ)樹(shù)，則根結(jié)點(diǎn)的右指針是（

）。

答案:

空

一棵非空的二叉樹(shù)的先序遍歷序列與后序遍歷序列正好相反，則該二叉樹(shù)一定滿足（

）。

答案:

只有一個(gè)葉子結(jié)點(diǎn)

一棵完全二叉樹(shù)上有1001個(gè)結(jié)點(diǎn)，其中葉子結(jié)點(diǎn)的個(gè)數(shù)是（

）。

答案:

501

引入二叉線索樹(shù)的目的是（

）。

答案:

加快查找結(jié)點(diǎn)的前驅(qū)或后繼的速度

把一棵樹(shù)轉(zhuǎn)換為二叉樹(shù)后，這棵二叉樹(shù)的形態(tài)是（

）。

答案:

唯一的

若X是二叉中序線索樹(shù)中一個(gè)有左孩子的結(jié)點(diǎn)，且X不為根，則X的前驅(qū)為（

）。

答案:

?X的左子樹(shù)中最右結(jié)點(diǎn)

若一棵二叉樹(shù)的先序遍歷序列為：a,e,b,d,c,后序遍歷序列為：b,c,d,e,a,則根結(jié)點(diǎn)的孩子結(jié)點(diǎn)（）

答案:

只有e

串是一種特殊的線性表，其特殊性體現(xiàn)在（

）。

答案:

數(shù)據(jù)元素是一個(gè)字符

串下面關(guān)于串的的敘述中，（

）是不正確的？

答案:

空串是由空格構(gòu)成的串

串“ababaaababaa”的next數(shù)組為（

）

答案:

011234223456

串“abcdefghi”的next為（

）。

答案:

011111111

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

）。

答案:

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

已知模式串t=‘a(chǎn)bcaabbabcab’寫出用KMP法求得的每個(gè)字符對(duì)應(yīng)的next函數(shù)值。

答案:

模式串t的next和nextval值如下：j1

2

3

4

5

6

7

8

9

101112t串a(chǎn)

b

c

a

a

b

b

a

b

c

a

bnext[j]0

1

1

1

2

2

3

1

2

3

4

5nextval[j]0

1

1

0

2

1

3

0

1

1

0

5

設(shè)目標(biāo)為t=“abcaabbabcabaacbacba”,模式為p=“abcabaa”①計(jì)算模式p的naxt函數(shù)值；②不寫出算法,只畫出利用KMP算法進(jìn)行模式匹配時(shí)每一趟的匹配過(guò)程。

答案:

①p的nextval函數(shù)值為0110132。（p的next函數(shù)值為0111232）。②利用KMP(改進(jìn)的nextval)算法，每趟匹配過(guò)程如下：

第一趟匹配：abcaabbabcabaacbacba

abcab(i=5,j=5)

第二趟匹配：abcaabbabcabaacbacba

abc(i=7,j=3)

第三趟匹配：abcaabbabcabaacbacba

a(i=7,j=1)

第四趟匹配：abcaabbabcabaacbacba

(成功)

abcabaa(i=15,j=8)

若讓元素1，2，3，4，5依次進(jìn)棧，則出棧次序不可能出現(xiàn)在（

）種情況。

答案:

4，3，1，2，5

若已知一個(gè)棧的入棧序列是1，2，3，…，n，其輸出序列為p1，p2，p3，…，pn，若p1=n，則pi為（

）。

答案:

n-i+1

則計(jì)算fact(n)需要調(diào)用該函數(shù)的次數(shù)為（

）。

答案:

n+1

設(shè)棧S和隊(duì)列Q的初始狀態(tài)為空，元素e1、e2、e3、e4、e5和e6依次進(jìn)入棧S，一個(gè)元素出棧后即進(jìn)入Q，若6個(gè)元素出隊(duì)的序列是e2、e4、e3、e6、e5和e1，則棧S的容量至少應(yīng)該是（）。

答案:

3

在一個(gè)具有n個(gè)單元的順序棧中，假設(shè)以地址高端作為棧底，以top作為棧頂指針，則當(dāng)作進(jìn)棧處理時(shí)，top的變化為（）。

答案:

top--

最大容量為n的循環(huán)隊(duì)列，隊(duì)尾指針是rear，隊(duì)頭是front，則隊(duì)空的條件是（）。

答案:

rear==front

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

答案:

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

一個(gè)遞歸算法必須包括（）。

答案:

終止條件和遞歸部分

在數(shù)據(jù)結(jié)構(gòu)中，從邏輯上可以把數(shù)據(jù)結(jié)構(gòu)分成（

）。

答案:

線性結(jié)構(gòu)和非線性結(jié)構(gòu)

與數(shù)據(jù)元素本身的形式、內(nèi)容、相對(duì)位置、個(gè)數(shù)無(wú)關(guān)的是數(shù)據(jù)的（

）。

答案:

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

?通常要求同一邏輯結(jié)構(gòu)中的所有數(shù)據(jù)元素具有相同的特性，這意味著（

）。

答案:

不僅數(shù)據(jù)元素所包含的數(shù)據(jù)項(xiàng)的個(gè)數(shù)要相同，而且對(duì)應(yīng)數(shù)據(jù)項(xiàng)的類型要一致

以下說(shuō)法正確的是（

）。

答案:

一些表面上很不相同的數(shù)據(jù)可以有相同的邏輯結(jié)構(gòu)

a[i][j]=0;

答案:

O（m*n）

i=i*3;

答案:

O（log3n）

s+=++i;

答案:

o()

x++;

答案:

因?yàn)閤++共執(zhí)行了n-1+n-2+……＋1=n(n-1)/2，所以執(zhí)行時(shí)間為O（n2）

⑹算法的描述方法通常有（）、（）、（）和（偽代碼）四種，其中，（偽代碼）被稱為算法語(yǔ)言。

答案:

自然語(yǔ)言###程序設(shè)計(jì)語(yǔ)言###流程圖

⑸算法具有五個(gè)特性，分別是（有零個(gè)或多個(gè)輸入）、（有一個(gè)或多個(gè)輸出）、（）、（）、（）。

答案:

有窮性###確定性###可行性

⑷數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)主要有（順序存儲(chǔ)結(jié)構(gòu)）和（鏈接存儲(chǔ)結(jié)構(gòu)）兩種基本方法，不論哪種存儲(chǔ)結(jié)構(gòu)，都要存儲(chǔ)兩方面的內(nèi)容：（）和（）。

答案:

數(shù)據(jù)元素###數(shù)據(jù)元素之間的關(guān)系

⑶從邏輯關(guān)系上講，數(shù)據(jù)結(jié)構(gòu)主要分為集合、（）、（）和（）。

答案:

線性結(jié)構(gòu)###樹(shù)結(jié)構(gòu)###圖結(jié)構(gòu)

⑺在一般情況下，一個(gè)算法的時(shí)間復(fù)雜度是（）的函數(shù)。

答案:

問(wèn)題規(guī)模

⑻

設(shè)待處理問(wèn)題的規(guī)模為n，若一個(gè)算法的時(shí)間復(fù)雜度為一個(gè)常數(shù)，則表示成數(shù)量級(jí)的形式為（

），若

為2n*log5n+8n，則表示成數(shù)量級(jí)的形式為（

）。

答案:

Ο(1);Ο（1）;Ο(1)###Ο(n*logn);Ο(nlogn)

⑴算法的時(shí)間復(fù)雜度都要通過(guò)算法中的基本語(yǔ)句的執(zhí)行次數(shù)來(lái)確定。

答案:

錯(cuò)

⑵每種數(shù)據(jù)結(jié)構(gòu)都具備三個(gè)基本操作：插入、刪除和查找。

答案:

錯(cuò)

⑶所謂數(shù)據(jù)的邏輯結(jié)構(gòu)指的是數(shù)據(jù)之間的邏輯關(guān)系。

答案:

錯(cuò)

⑵（

）是數(shù)據(jù)的最小單位，（

）是討論數(shù)據(jù)結(jié)構(gòu)時(shí)涉及的最小數(shù)據(jù)單位。

答案:

數(shù)據(jù)項(xiàng)###數(shù)據(jù)元素

⑴（）是數(shù)據(jù)的基本單位，在計(jì)算機(jī)程序中通常作為一個(gè)整體進(jìn)行考慮和處理

答案:

數(shù)據(jù)元素

⑸算法分析的目的是（），算法分析的兩個(gè)主要方面是（）。

答案:

分析算法的效率以求改進(jìn)###空間性能和時(shí)間性能

⑴

順序存儲(chǔ)結(jié)構(gòu)中數(shù)據(jù)元素之間的邏輯關(guān)系是由（）表示的，鏈接存儲(chǔ)結(jié)構(gòu)中的數(shù)據(jù)元素之間的邏輯關(guān)系是由（

）表示的。

答案:

存儲(chǔ)位置###指針

⑷下面（）不是算法所必須具備的特性。

答案:

高效性

⑶算法指的是（）。

答案:

對(duì)特定問(wèn)題求解步驟的一種描述，是指令的有限序列。

⑵

假設(shè)有如下遺產(chǎn)繼承規(guī)則：丈夫和妻子可以相互繼承遺產(chǎn)；子女可以繼承父親或母親的遺產(chǎn)；子女間不

能相互繼承。則表示該遺產(chǎn)繼承關(guān)系的最合適的數(shù)據(jù)結(jié)構(gòu)應(yīng)該是（

）。

答案:

圖

⑸

在單鏈表中，要取得某個(gè)元素，只要知道該元素所在結(jié)點(diǎn)的地址即可，因此單鏈表是隨機(jī)存取結(jié)構(gòu)。

答案:

錯(cuò)

⑷

線性結(jié)構(gòu)的基本特征是：每個(gè)元素有且僅有一個(gè)直接前驅(qū)和一個(gè)直接后繼。

答案:

錯(cuò)

⑶設(shè)p，q是指針，若p=q，則*p=*q。

答案:

錯(cuò)

⑵

線性表的順序存儲(chǔ)結(jié)構(gòu)優(yōu)于鏈接存儲(chǔ)結(jié)構(gòu)。

答案:

錯(cuò)

⑴

線性表的邏輯順序和存儲(chǔ)順序總是一致的。

答案:

錯(cuò)

⑻

可由一個(gè)尾指針唯一確定的鏈表有（

）、（

）、（

）。

答案:

循環(huán)鏈表;循環(huán)單鏈表###循環(huán)雙鏈表###雙鏈表

⑺

一個(gè)具有

n

個(gè)結(jié)點(diǎn)的單鏈表，在指針

p

所指結(jié)點(diǎn)后插入一個(gè)新結(jié)點(diǎn)的時(shí)間復(fù)雜度為（

）；在給定值為x

的結(jié)點(diǎn)后插入一個(gè)新結(jié)點(diǎn)的時(shí)間復(fù)雜度為（

）。

答案:

Ο(1);O（1）;o(1);o（1）###Ο(n);O（n）;o(n);o（n）

⑹

在由尾指針

rear

指示的單循環(huán)鏈表中，在表尾插入一個(gè)結(jié)點(diǎn)

s

的操作序列是（

）；刪除開(kāi)始結(jié)點(diǎn)的操作序列為（

）。

答案:

s->next

=rear->next;

rear->next

=s;

rear

=s;###q=rear->next->next;

rear->next->next=q->next;

delete

q;

⑸

非空的單循環(huán)鏈表由頭指針

head

指示，則其尾結(jié)點(diǎn)（由指針

p

所指）滿足（

）。

答案:

p->next=head

⑷

單鏈表中設(shè)置頭結(jié)點(diǎn)的作用是（

）。

答案:

為了運(yùn)算方便

⑶設(shè)單鏈表中指針p指向結(jié)點(diǎn)A，若要?jiǎng)h除A的后繼結(jié)點(diǎn)（假設(shè)A存在后繼結(jié)點(diǎn)），則需修改指針的操作為（）。

答案:

p->next=(p->next)->next

⑵順序表中第一個(gè)元素的存儲(chǔ)地址是100，每個(gè)元素的長(zhǎng)度為2，則第5個(gè)元素的存儲(chǔ)地址是（）。

答案:

108

⑴在順序表中，等概率情況下，插入和刪除一個(gè)元素平均需移動(dòng)（表長(zhǎng)的一半）個(gè)元素，具體移動(dòng)元素的個(gè)數(shù)與（）和（該元素在表中的位置）有關(guān)。

答案:

表長(zhǎng)

⑴線性表的順序存儲(chǔ)結(jié)構(gòu)是一種（）的存儲(chǔ)結(jié)構(gòu)，線性表的鏈接存儲(chǔ)結(jié)構(gòu)是一種（）的存儲(chǔ)結(jié)構(gòu)。

答案:

A

隨機(jī)存取###B

順序存取

在循環(huán)雙鏈表的p所指結(jié)點(diǎn)后插入s所指結(jié)點(diǎn)的操作是（）。

答案:

s->prior=p;

s->next=p->next;

p->next->prior=s;

p->next=s;

(9)在一個(gè)單鏈表中，已知q所指結(jié)點(diǎn)是p所指結(jié)點(diǎn)的直接前驅(qū)，若在q和p之間插入s所指結(jié)點(diǎn)，則執(zhí)行（）操作。

答案:

q->next=s;

s->next=p;

(8)

使用雙鏈表存儲(chǔ)線性表，其優(yōu)點(diǎn)是可以（

）。

答案:

更方便數(shù)據(jù)的插入和刪除

⑺

若鏈表中最常用的操作是在最后一個(gè)結(jié)點(diǎn)之后插入一個(gè)結(jié)點(diǎn)和刪除最后一個(gè)結(jié)點(diǎn)，則采用（

）存儲(chǔ)方法最節(jié)省運(yùn)算時(shí)間。

答案:

循環(huán)雙鏈表

⑹

若鏈表中最常用的操作是在最后一個(gè)結(jié)點(diǎn)之后插入一個(gè)結(jié)點(diǎn)和刪除第一個(gè)結(jié)點(diǎn)，則采用（

）存儲(chǔ)方法最節(jié)省時(shí)間。

答案:

帶尾指針的單循環(huán)鏈表

⑸若某線性表中最常用的操作是取第i個(gè)元素和找第i個(gè)元素的前驅(qū)，則采用（）存儲(chǔ)方法最節(jié)省時(shí)間。

答案:

順序表

⑷

鏈表不具有的特點(diǎn)是（

）。

答案:

可隨機(jī)訪問(wèn)任一元素

⑶

單循環(huán)鏈表的主要優(yōu)點(diǎn)是（

）。

答案:

從表中任一結(jié)點(diǎn)出發(fā)都能掃描到整個(gè)鏈表

⑵

線性表采用鏈接存儲(chǔ)時(shí)，其地址（

）。

答案:

連續(xù)與否均可以

⑸空串與空格串是相同的。

答案:

錯(cuò)

⑷在循環(huán)隊(duì)列中，front指向隊(duì)頭元素的前一個(gè)位置，rear指向隊(duì)尾元素的位置，則隊(duì)滿的條件是front=rear。

答案:

錯(cuò)

⑶在棧滿的情況下不能做進(jìn)棧操作，否則將產(chǎn)生“上溢”。

答案:

對(duì)

⑵棧可以作為實(shí)現(xiàn)過(guò)程調(diào)用的一種數(shù)據(jù)結(jié)構(gòu)。

答案:

對(duì)

⑴有n個(gè)元素依次進(jìn)棧，則出棧序列有(n-1)/2種。

答案:

錯(cuò)

⑹循環(huán)隊(duì)列的引入是為了克服（）。

答案:

假溢出

⑸棧和隊(duì)列是兩種特殊的線性表，棧的操作特性是（），隊(duì)列的操作特性是（），棧和隊(duì)列的主要區(qū)別在于（對(duì)插入和刪除操作限定的位置不同）。

答案:

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

⑷表達(dá)式a*(b+c)-d的后綴表達(dá)式是（）。

答案:

abc+*d-

⑶（）可作為實(shí)現(xiàn)遞歸函數(shù)調(diào)用的一種數(shù)據(jù)結(jié)構(gòu)。

答案:

棧

(2)用循環(huán)鏈表表示的隊(duì)列長(zhǎng)度為n，若只設(shè)頭指針，則出隊(duì)和入隊(duì)的時(shí)間復(fù)雜度分別是（）和（）。

答案:

O(1)###O(n)

⑴設(shè)有一個(gè)空棧，棧頂指針為1000H，現(xiàn)有輸入序列為1、2、3、4、5，經(jīng)過(guò)push，push，pop，push，pop，push，push后，輸出序列是（），棧頂指針為（）。

答案:

23###1003H

⑼設(shè)有兩個(gè)串p和q，求q在p中首次出現(xiàn)的位置的運(yùn)算稱作（）。

答案:

模式