數(shù)據(jù)結(jié)構(gòu)(c語(yǔ)言版)期末考試復(fù)習(xí)試題

語(yǔ)言版）期末考復(fù)習(xí)題一、選擇題。．在數(shù)據(jù)結(jié)構(gòu)中，從邏輯上可以把數(shù)據(jù)結(jié)構(gòu)分為 。A．動(dòng)態(tài)結(jié)構(gòu)和靜態(tài)結(jié)構(gòu) B．緊湊結(jié)構(gòu)和非緊湊結(jié)構(gòu)．線性結(jié)構(gòu)和非線性結(jié)構(gòu) ．內(nèi)部結(jié)構(gòu)和外部結(jié)構(gòu)．?dāng)?shù)據(jù)結(jié)構(gòu)在計(jì)算機(jī)內(nèi)存中的表示是指 A 。A．?dāng)?shù)據(jù)的存儲(chǔ)結(jié)構(gòu) B．?dāng)?shù)據(jù)結(jié)構(gòu) ．?dāng)?shù)據(jù)的邏輯結(jié)構(gòu) ．?dāng)?shù)據(jù)元素之間的關(guān)系．在數(shù)據(jù)結(jié)構(gòu)中，與所使用的計(jì)算機(jī)無(wú)關(guān)的是數(shù)據(jù)的 A 結(jié)構(gòu)。A．邏輯 B．存儲(chǔ) ．邏輯和存儲(chǔ) ．物理．在存儲(chǔ)數(shù)據(jù)時(shí)，通常不僅要存儲(chǔ)各數(shù)據(jù)元素的值，而且還要存儲(chǔ) 。A．?dāng)?shù)據(jù)的處理方法 B．?dāng)?shù)據(jù)元素的類型．?dāng)?shù)據(jù)元素之間的關(guān)系 ．?dāng)?shù)據(jù)的存儲(chǔ)方法．在決定選取何種存儲(chǔ)結(jié)構(gòu)時(shí)，一般不考慮 A 。A．各結(jié)點(diǎn)的值如何 B．結(jié)點(diǎn)個(gè)數(shù)的多少．對(duì)數(shù)據(jù)有哪些運(yùn)算 ．所用的編程語(yǔ)言實(shí)現(xiàn)這種結(jié)構(gòu)是否方便。．以下說(shuō)法正確的是 。A．?dāng)?shù)據(jù)項(xiàng)是數(shù)據(jù)的基本單位B．?dāng)?shù)據(jù)元素是數(shù)據(jù)的最小單位．?dāng)?shù)據(jù)結(jié)構(gòu)是帶結(jié)構(gòu)的數(shù)據(jù)項(xiàng)的集合．一些表面上很不相同的數(shù)據(jù)可以有相同的邏輯結(jié)構(gòu)．算法分析的目的是 ，算法分析的兩個(gè)主要方面是 A 。（）A．找出數(shù)據(jù)結(jié)構(gòu)的合理性 B．研究算法中的輸入和輸出的關(guān)系．分析算法的效率以求改進(jìn) ．分析算法的易讀性和文檔性（）A．空間復(fù)雜度和時(shí)間復(fù)雜度 B．正確性和簡(jiǎn)明性．可讀性和文檔性 ．?dāng)?shù)據(jù)復(fù)雜性和程序復(fù)雜性．下面程序段的時(shí)間復(fù)雜度是 。

I

=

;．下面程序段的時(shí)間復(fù)雜度是 。

i

A[i][j]

＝

．下面程序段的時(shí)間復(fù)雜度是 。i

＝

；（）i

=

i

*

；．在以下的敘述中，正確的是 B 。A．線性表的順序存儲(chǔ)結(jié)構(gòu)優(yōu)于鏈表存儲(chǔ)結(jié)構(gòu)B．二維數(shù)組是其數(shù)據(jù)元素為線性表的線性表．棧的操作方式是先進(jìn)先出．隊(duì)列的操作方式是先進(jìn)后出

B

。A．?dāng)?shù)據(jù)元素具有同一特點(diǎn)B致．每個(gè)數(shù)據(jù)元素都一樣．?dāng)?shù)據(jù)元素所包含的數(shù)據(jù)項(xiàng)的個(gè)數(shù)要相等．鏈表不具備的特點(diǎn)是 A 。A．可隨機(jī)訪問(wèn)任一結(jié)點(diǎn) B．插入刪除不需要移動(dòng)元素．不必事先估計(jì)存儲(chǔ)空間 ．所需空間與其長(zhǎng)度成正比．不帶頭結(jié)點(diǎn)的單鏈表head

為空的判定條件是 A 。A．head

==

NULL B

．

==head

．帶頭結(jié)點(diǎn)的單鏈表head

為空的判定條件是 B 。A．head

==

NULL B

．

==head

．若某表最常用的操作是在最后一個(gè)結(jié)點(diǎn)之后插入一個(gè)結(jié)點(diǎn)或刪除最后一個(gè)結(jié)點(diǎn)，則采用 存儲(chǔ)方式最節(jié)省運(yùn)算時(shí)間。A．單鏈表 B．給出表頭指針的單循環(huán)鏈表 ．雙鏈表 ．帶頭結(jié)點(diǎn)的雙循環(huán)鏈表．需要分配較大空間，插入和刪除不需要移動(dòng)元素的線性表，其存儲(chǔ)結(jié)構(gòu)是B 。A．單鏈表 B．靜態(tài)鏈表 ．線性鏈表 ．順序存儲(chǔ)結(jié)構(gòu)．非空的循環(huán)單鏈表head

的尾結(jié)點(diǎn)（由

p

所指向）滿足 。A．

==

NULL B．p

==

NULL．

==head ．p

==

head．在循環(huán)雙鏈表的p

所指的結(jié)點(diǎn)之前插入

所指結(jié)點(diǎn)的操作是 。A．

=

；

=

p；

=

；

=

B．

=

；

=

；

=

p；

=

．

=

p；

=

；

=

；

=

．

=

p；

=

；

=

；

=

．如果最常用的操作是取第i

個(gè)結(jié)點(diǎn)及其前驅(qū)，則采用 存儲(chǔ)方式最節(jié)省時(shí)間。A．單鏈表 B．雙鏈表 ．單循環(huán)鏈表 ．

順序表．在一個(gè)具有

個(gè)結(jié)點(diǎn)的有序單鏈表中插入一個(gè)新結(jié)點(diǎn)并仍然保持有序的時(shí)間復(fù)雜度是 B

。A．（） B．（） ．（） ．（）．在一個(gè)長(zhǎng)度為（n>1）的單鏈表上，設(shè)有頭和尾兩個(gè)指針，執(zhí)行 B 操作與鏈表的長(zhǎng)度有關(guān)。A．刪除單鏈表中的第一個(gè)元素B．刪除單鏈表中的最后一個(gè)元素．在單鏈表第一個(gè)元素前插入一個(gè)新元素．在單鏈表最后一個(gè)元素后插入一個(gè)新元素．與單鏈表相比，雙鏈表的優(yōu)點(diǎn)之一是 。A．插入、刪除操作更簡(jiǎn)單B．可以進(jìn)行隨機(jī)訪問(wèn)．可以省略表頭指針或表尾指針．順序訪問(wèn)相鄰結(jié)點(diǎn)更靈活．如果對(duì)線性表的操作只有兩種，即刪除第一個(gè)元素，在最后一個(gè)元素的后面插入新元素，則最好使用 B 。A．只有表頭指針沒(méi)有表尾指針的循環(huán)單鏈表B．只有表尾指針沒(méi)有表頭指針的循環(huán)單鏈表．非循環(huán)雙鏈表．循環(huán)雙鏈表．在長(zhǎng)度為

的順序表的第

i

個(gè)位置上插入一個(gè)元素（1≤

≤n+1動(dòng)次數(shù)為： A 。A．

–

i

+

B．

–

i ．i ．i

–

．對(duì)于只在表的首、尾兩端進(jìn)行插入操作的線性表，宜采用的存儲(chǔ)結(jié)構(gòu)為 。A．順序表 B．

用頭指針表示的循環(huán)單鏈表．用尾指針表示的循環(huán)單鏈表 ．單鏈表．下述哪一條是順序存儲(chǔ)結(jié)構(gòu)的優(yōu)點(diǎn)？ 。A

插入運(yùn)算方便 B

可方便地用于各種邏輯結(jié)構(gòu)的存儲(chǔ)表示

存儲(chǔ)密度大

刪除運(yùn)算方便．下面關(guān)于線性表的敘述中，錯(cuò)誤的是哪一個(gè)？ B 。A

線性表采用順序存儲(chǔ)，必須占用一片連續(xù)的存儲(chǔ)單元B

線性表采用順序存儲(chǔ)，便于進(jìn)行插入和刪除操作。

線性表采用鏈?zhǔn)酱鎯?chǔ)，不必占用一片連續(xù)的存儲(chǔ)單元

線性表采用鏈?zhǔn)酱鎯?chǔ)，便于進(jìn)行插入和刪除操作。．線性表是具有

個(gè) B 的有限序列。A．字符 B．?dāng)?shù)據(jù)元素 ．?dāng)?shù)據(jù)項(xiàng) ．表元素．在

個(gè)結(jié)點(diǎn)的線性表的數(shù)組實(shí)現(xiàn)中，算法的時(shí)間復(fù)雜度是（）的操作是A 。A．訪問(wèn)第

i（1<=i<=n）個(gè)結(jié)點(diǎn)和求第i

個(gè)結(jié)點(diǎn)的直接前驅(qū)（1<i<=n）B．在第

i（1<=i<=n）個(gè)結(jié)點(diǎn)后插入一個(gè)新結(jié)點(diǎn)．刪除第

i（1<=i<=n）個(gè)結(jié)點(diǎn)．以上都不對(duì)

i

個(gè)位置插入一個(gè)新元素的算法的時(shí)間復(fù)雜度為 。A． B． ． ．

．對(duì)于順序存儲(chǔ)的線性表，訪問(wèn)結(jié)點(diǎn)和增加、刪除結(jié)點(diǎn)的時(shí)間復(fù)雜度為 。A．

B．

．

．

．線性表（ …

）以鏈?zhǔn)椒绞酱鎯?chǔ)，訪問(wèn)第i

位置元素的時(shí)間復(fù)雜度為 。A． B． ． ．．單鏈表中，增加一個(gè)頭結(jié)點(diǎn)的目的是為了 。A．使單鏈表至少有一個(gè)結(jié)點(diǎn) B．標(biāo)識(shí)表結(jié)點(diǎn)中首結(jié)點(diǎn)的位置．方面運(yùn)算的實(shí)現(xiàn) ．說(shuō)明單鏈表是線性表的鏈?zhǔn)酱鎯?chǔ)p

的結(jié)點(diǎn)之后插入指針為

B 。A．； B．

；．； ．；．線性表的順序存儲(chǔ)結(jié)構(gòu)是一種 A 。A．隨機(jī)存取的存儲(chǔ)結(jié)構(gòu) B．順序存取的存儲(chǔ)結(jié)構(gòu)．索引存取的存儲(chǔ)結(jié)構(gòu) ．

存取的存儲(chǔ)結(jié)構(gòu)．棧的特點(diǎn)是 B ，隊(duì)列的特點(diǎn)是 A 。A．先進(jìn)先出 B．先進(jìn)后出．棧和隊(duì)列的共同點(diǎn)是 。A．都是先進(jìn)后出 B．都是先進(jìn)先出．只允許在端點(diǎn)處插入和刪除元素 ．沒(méi)有共同點(diǎn)．一個(gè)棧的進(jìn)棧序列是，b，，d，e，則棧的不可能的輸出序列是 。A． B． ． ．．設(shè)有一個(gè)棧，元素依次進(jìn)棧的順序?yàn)?/p>

A、B、、、E。下列 是不可能的出棧序列。A．A,B,C,D,E B．B,C,D,E,A ．E,A,B,C,D ．E,D,C,B,A．以下 B 不是隊(duì)列的基本運(yùn)算？A．從隊(duì)尾插入一個(gè)新元素 B．從隊(duì)列中刪除第

i

個(gè)元素．判斷一個(gè)隊(duì)列是否為空 ．讀取隊(duì)頭元素的值．若已知一個(gè)棧的進(jìn)棧序列是，，，，，其輸出序列為，，，…，pn，若

＝，則

為 。A．i B．－i ．－i＋ ．不確定．判定一個(gè)順序棧（最多元素為

）為空的條件是 B 。A．

B．

==

．

．

== ．判定一個(gè)順序棧（最多元素為

）為滿的條件是 。A．

B．

==

．

．

== ．一個(gè)隊(duì)列的入隊(duì)序列是，，，，則隊(duì)列的輸出序列是 B 。A．，，， B．，，，．，，， ．，，，．判定一個(gè)循環(huán)隊(duì)列qu（最多元素為

）為空的條件是 。A．

–

B．

–

．

．

．在循環(huán)隊(duì)列中，若

與

分別表示對(duì)頭元素和隊(duì)尾元素的位置，則判斷循環(huán)隊(duì)列空的條件是 。A． B． ． ．

的帶頭結(jié)點(diǎn)的鏈棧中插入指針

操作。A．

; B．

;．

=s

; ．

;．輸入序列為

ABC，可以變?yōu)?/p>

CBA

時(shí)，經(jīng)過(guò)的棧操作為 B 。A．，pop，，pop，，pop B．，，，pop，

pop，pop．，，pop，

pop，，pop ．，pop，，，pop，pop．若棧采用順序存儲(chǔ)方式存儲(chǔ)，現(xiàn)兩棧共享空間 ，、分別代表第

和第

個(gè)棧的棧頂，棧

的底在

，棧

的底在

，則棧滿的條件是 B 。A． B

．

．．．設(shè)計(jì)一個(gè)判別表達(dá)式中左、右括號(hào)是否配對(duì)出現(xiàn)的算法，采用 數(shù)據(jù)結(jié)構(gòu)最佳。A．線性表的順序存儲(chǔ)結(jié)構(gòu) B

．隊(duì)列

．線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)．棧．允許對(duì)隊(duì)列進(jìn)行的操作有 。A．對(duì)隊(duì)列中的元素排序 B．取出最近進(jìn)隊(duì)的元素．在隊(duì)頭元素之前插入元素 ．刪除隊(duì)頭元素．對(duì)于循環(huán)隊(duì)列 。A．無(wú)法判斷隊(duì)列是否為空 B．無(wú)法判斷隊(duì)列是否為滿．隊(duì)列不可能滿 ．以上說(shuō)法都不對(duì)．若用一個(gè)大小為

的數(shù)值來(lái)實(shí)現(xiàn)循環(huán)隊(duì)列，且當(dāng)前

和

的值分別為

和

，當(dāng)從隊(duì)列中刪除一個(gè)元素，再加入兩個(gè)元素后，

和

的值分別為B 。A．

和

B．

和

．

和

．

和

．隊(duì)列的“先進(jìn)先出”特性是指 。A．最早插入隊(duì)列中的元素總是最后被刪除B．當(dāng)同時(shí)進(jìn)行插入、刪除操作時(shí)，總是插入操作優(yōu)先．每當(dāng)有刪除操作時(shí)，總是要先做一次插入操作．每次從隊(duì)列中刪除的總是最早插入的元素．和順序棧相比，鏈棧有一個(gè)比較明顯的優(yōu)勢(shì)是 A 。A．通常不會(huì)出現(xiàn)棧滿的情況 B．

通常不會(huì)出現(xiàn)?？盏那闆r．插入操作更容易實(shí)現(xiàn) ．刪除操作更容易實(shí)現(xiàn)．用不帶頭結(jié)點(diǎn)的單鏈表存儲(chǔ)隊(duì)列，其頭指針指向隊(duì)頭結(jié)點(diǎn)，尾指針指向隊(duì)尾結(jié)點(diǎn)，則在進(jìn)行出隊(duì)操作時(shí) 。A．僅修改隊(duì)頭指針 B．僅修改隊(duì)尾指針．隊(duì)頭、隊(duì)尾指針都可能要修改 ．隊(duì)頭、隊(duì)尾指針都要修改．若串

‘ B 。A． B． ． ．．串的長(zhǎng)度是指 B 。A．串中所含不同字母的個(gè)數(shù) B．串中所含字符的個(gè)數(shù)．串中所含不同字符的個(gè)數(shù) ．串中所含非空格字符的個(gè)數(shù)．串是一種特殊的線性表，其特殊性體現(xiàn)在 B 。A．可以順序存儲(chǔ) B．?dāng)?shù)據(jù)元素是一個(gè)字符．可以鏈?zhǔn)酱鎯?chǔ) ．?dāng)?shù)據(jù)元素可以是多個(gè)字符．設(shè)有兩個(gè)串

p

和

q，求

q

在

p

中首次出現(xiàn)的位置的運(yùn)算稱為 B 。A．連接 B．

模式匹配 ．求子串 ．求串長(zhǎng)．?dāng)?shù)組

A

中，每個(gè)元素的長(zhǎng)度為

個(gè)字節(jié)，行下標(biāo)

i

從

到

，列下標(biāo)

j

從

到

，從首地址

SA

開始連續(xù)存放的存儲(chǔ)器內(nèi)，該數(shù)組按行存放，元素的起始地址為 。A．SA＋ B．

SA＋ ．SA＋ ．SA＋．?dāng)?shù)組

A

中，每個(gè)元素的長(zhǎng)度為

個(gè)字節(jié)，行下標(biāo)

i

從

到

，列下標(biāo)

j

從

到

，從首地址

SA

開始連續(xù)存放的存儲(chǔ)器內(nèi)，該數(shù)組按行存放，元素的起始地址為 。A．SA＋ B．

SA＋ ．SA＋ ．SA＋．若聲明一個(gè)浮點(diǎn)數(shù)數(shù)組如下：

假設(shè)該數(shù)組的內(nèi)存起始位置為，

的內(nèi)存地址是 。A． B． ． ．．設(shè)二維數(shù)組

…

…

按行存儲(chǔ)在數(shù)組

B

中，則二維數(shù)組元素

A[i,j]在一維數(shù)組

B

中的下標(biāo)為 A 。A． B．

． ．．有一個(gè)

×

的稀疏矩陣，非

元素有

，設(shè)每個(gè)整型數(shù)占

個(gè)字節(jié)，則用三元組表示該矩陣時(shí)，所需的字節(jié)數(shù)是 B 。A． B．

．

．．?dāng)?shù)組

…

，

…

， …中含有的元素個(gè)數(shù)是 A 。A． B．

． ．．對(duì)矩陣進(jìn)行壓縮存儲(chǔ)是為了 。A．方便運(yùn)算 B．

方便存儲(chǔ) ．提高運(yùn)算速度 ．減少存儲(chǔ)空間．設(shè)有一個(gè)

階的對(duì)稱矩陣

A，采用壓縮存儲(chǔ)方式，以行序?yàn)橹鞔鎯?chǔ)，為第一個(gè)元素，其存儲(chǔ)地址為

，每個(gè)元素占

個(gè)地址空間，則

B 。A． B．

． ．

的地址為．稀疏矩陣一般的壓縮存儲(chǔ)方式有兩種，即 。A．二維數(shù)組和三維數(shù)組 B． 三元組和散列．三元組和十字鏈表 ． 散列和十字鏈表．樹最適合用來(lái)表示 。A．有序數(shù)據(jù)元素 B．無(wú)序數(shù)據(jù)元素．元素之間具有分支層次關(guān)系的數(shù)據(jù) ．元素之間無(wú)聯(lián)系的數(shù)據(jù)．深度為

的二叉樹至多有 個(gè)結(jié)點(diǎn)。A． B．

． ． ．對(duì)一個(gè)滿二叉樹，m

個(gè)葉子，

個(gè)結(jié)點(diǎn)，深度為

，則 。A．

=

h+m B

h+m

=

m

=

=

．任何一棵二叉樹的葉子結(jié)點(diǎn)在前序、中序和后序遍歷序列中的相對(duì)次序A 。A．不發(fā)生改變 B．發(fā)生改變 ．不能確定 ．以上都不對(duì)．在線索化樹中，每個(gè)結(jié)點(diǎn)必須設(shè)置一個(gè)標(biāo)志來(lái)說(shuō)明它的左、右鏈指向的是樹結(jié)構(gòu)信息，還是線索化信息，若

標(biāo)識(shí)樹結(jié)構(gòu)信息，

標(biāo)識(shí)線索，對(duì)應(yīng)葉結(jié)點(diǎn)的左右鏈域，應(yīng)標(biāo)識(shí)為__

__。A． B． ． ．．在下述論述中，正確的是 。①只有一個(gè)結(jié)點(diǎn)的二叉樹的度為；②二叉樹的度為；③二叉樹的左右子樹可任意交換；④深度為

K

的順序二叉樹的結(jié)點(diǎn)個(gè)數(shù)小于或等于深度相同的滿二叉樹。A．①②③ B．②③④ ．②④ ．①④．設(shè)森林F

對(duì)應(yīng)的二叉樹為

B，它有m

個(gè)結(jié)點(diǎn)，B

的根為

p，p

的右子樹的結(jié)點(diǎn)個(gè)數(shù)為

，森林

F

中第一棵樹的結(jié)點(diǎn)的個(gè)數(shù)是 A 。A．m-n B． ．n+1 ．不能確定．若一棵二叉樹具有

個(gè)度為

的結(jié)點(diǎn)，

個(gè)度為

的結(jié)點(diǎn)，則度為

的結(jié)點(diǎn)的個(gè)數(shù)是 B

。A． B． ． ．不能確定．具有

個(gè)葉子結(jié)點(diǎn)的二叉樹中有 B 個(gè)度為

的結(jié)點(diǎn)。A． B． ． ．．在一個(gè)無(wú)向圖中，所有頂點(diǎn)的度數(shù)之和等于所有邊數(shù)的 倍。A． B

B 倍。A． B

（左中右）

ABCDEFG

BDCAFGE樹中結(jié)點(diǎn)數(shù)目為： A． B． ． ．83．已知一算術(shù)表達(dá)式的中綴形式為

A＋B

*C–D/E，后綴形式為

ABC

*+DE/–，其前綴形式為 D 。

A ． – B ． – – ．–

出發(fā)

a

按深度搜索法進(jìn)行遍歷，則可能得到的一種頂點(diǎn)序列

b

e

c

為____D___；按廣度搜索法進(jìn)行遍歷，則可能

d

f

得到的一種頂點(diǎn)序列為___A___；①A．，b，e，，d， B．，，，e，b，d．，e，b，，，d， ．，e，d，，，b②A．，b，，e，d， B．，b，，e，，d．，e，b，，，d， ．，，，d，e，b．采用鄰接表存儲(chǔ)的圖的深度優(yōu)先遍歷算法類似于二叉樹的___A____。A．先序遍歷 B．中序遍歷 ．后序遍歷 ．按層遍歷．采用鄰接表存儲(chǔ)的圖的廣度優(yōu)先遍歷算法類似于二叉樹的___D____。A．先序遍歷 B．中序遍歷 ．后序遍歷 ．按層遍歷．具有

個(gè)結(jié)點(diǎn)的連通圖至少有 A 條邊。A． B．

．

．

），）的表頭是

，表尾是 。A． B （）

（）

（（））

，表尾是 B 。A． B （）

（）

（（））．順序查找法適合于存儲(chǔ)結(jié)構(gòu)為 B 的線性表。A 散列存儲(chǔ) B 順序存儲(chǔ)或鏈?zhǔn)酱鎯?chǔ) 壓縮存儲(chǔ) 索引存儲(chǔ)．對(duì)線性表進(jìn)行折半查找時(shí)，要求線性表必須 B 。A 以順序方式存儲(chǔ) B 列 以鏈?zhǔn)椒绞酱鎯?chǔ) 列．采用折半查找法查找長(zhǎng)度為

的線性表時(shí)，每個(gè)元素的平均查找長(zhǎng)度為 。A B ．有一個(gè)有序表為｛，，，，，，，，，，，，｝，當(dāng)折半查找值為

的結(jié)點(diǎn)時(shí)， 次比較后查找成功。A． B ．二叉樹為二叉排序樹的充分必要條件是其任一結(jié)點(diǎn)的值均大于其左孩子的值、小于其右孩子的值。這種說(shuō)法 B 。A 正確 B 錯(cuò)誤．下面關(guān)于

B

樹和

樹的敘述中，不正確的結(jié)論是 A 。A B樹和樹都能有效的支持順序查找 B B樹和樹都能有效的支持隨機(jī)查找 B樹和樹都是平衡的多叉樹 B樹和樹都可用于文件索引結(jié)構(gòu)．以下說(shuō)法錯(cuò)誤的是 B 。A．散列法存儲(chǔ)的思想是由關(guān)鍵字值決定數(shù)據(jù)的存儲(chǔ)地址B．散列表的結(jié)點(diǎn)中只包含數(shù)據(jù)元素自身的信息，不包含指針。．負(fù)載因子是散列表的一個(gè)重要參數(shù)，它反映了散列表的飽滿程度。法。．查找效率最高的二叉排序樹是 。A．所有結(jié)點(diǎn)的左子樹都為空的二叉排序樹。B．所有結(jié)點(diǎn)的右子樹都為空的二叉排序樹。．平衡二叉樹。．沒(méi)有左子樹的二叉排序樹。．排序方法中，從未排序序列中依次取出元素與已排序序列中的元素進(jìn)行比較，將其放入已排序序列的正確位置上的方法，稱為 。A．希爾排序 B。冒泡排序

插入排序 。選擇排序．在所有的排序方法中，關(guān)鍵字比較的次數(shù)與記錄的初始排列次序無(wú)關(guān)的是 。A．希爾排序 B．冒泡排序 ．直接插入排序 ．直接選擇排序？．堆是一種有用的數(shù)據(jù)結(jié)構(gòu)。下列關(guān)鍵碼序列 是一個(gè)堆。A． B．

,,, ,

,,, ,． ．．堆排序是一種 B 排序。A．插入 B．選擇 ．交換 ．歸并． 在鏈表中進(jìn)行操作比在順序表中進(jìn)行操作效率高。A．順序查找 B．折半查找 ．分塊查找 ．插入．直接選擇排序的時(shí)間復(fù)雜度為 。（

為元素個(gè)數(shù)）A．（ B． ． ．

二、填空題。．?dāng)?shù)據(jù)邏輯結(jié)構(gòu)包括 線性結(jié)構(gòu) 、 樹形結(jié)構(gòu) 和 圖狀結(jié)構(gòu) 三種類型，樹形結(jié)構(gòu)和圖狀結(jié)構(gòu)合稱

非線性結(jié)構(gòu) 。．?dāng)?shù)據(jù)的邏輯結(jié)構(gòu)分為 集合 、線性結(jié)構(gòu) 、 樹形結(jié)構(gòu) 和 圖狀結(jié)構(gòu)

種。．在線性結(jié)構(gòu)中，第一個(gè)結(jié)點(diǎn)

沒(méi)有

前驅(qū)結(jié)點(diǎn)，其余每個(gè)結(jié)點(diǎn)有且只有

個(gè)前驅(qū)結(jié)點(diǎn)；最后一個(gè)結(jié)點(diǎn)

沒(méi)有 后續(xù)結(jié)點(diǎn)，其余每個(gè)結(jié)點(diǎn)有且只有 個(gè)后續(xù)結(jié)點(diǎn)。．線性結(jié)構(gòu)中元素之間存在

一對(duì)一

關(guān)系，樹形結(jié)構(gòu)中元素之間存在

一對(duì)多關(guān)系，圖形結(jié)構(gòu)中元素之間存在 多對(duì)多 關(guān)系。．在樹形結(jié)構(gòu)中，樹根結(jié)點(diǎn)沒(méi)有

前驅(qū)

結(jié)點(diǎn)，其余每個(gè)結(jié)點(diǎn)有且只有

個(gè)前驅(qū)結(jié)點(diǎn)；葉子結(jié)點(diǎn)沒(méi)有 后續(xù) 結(jié)點(diǎn)，其余每個(gè)結(jié)點(diǎn)的后續(xù)結(jié)點(diǎn)可以 任意多個(gè) 。．?dāng)?shù)據(jù)結(jié)構(gòu)的基本存儲(chǔ)方法是

順序 、 鏈?zhǔn)?、 索引 和 散列 存儲(chǔ)

。

時(shí)間復(fù)雜度與

空間復(fù)雜度

。．評(píng)估一個(gè)算法的優(yōu)劣，通常從 時(shí)間復(fù)雜度 和 空間復(fù)雜度 兩個(gè)方面考察。

個(gè)重要特性是 有窮性 、

確定性

、

可行性

的順序表中刪除第

i

個(gè)元素。．在單鏈表中，要?jiǎng)h除某一指定的結(jié)點(diǎn)，必須找到該結(jié)點(diǎn)的 前驅(qū) 結(jié)點(diǎn)。．在雙鏈表中，每個(gè)結(jié)點(diǎn)有兩個(gè)指針域，一個(gè)指向

前驅(qū)

結(jié)點(diǎn)，另一個(gè)指向后繼結(jié)點(diǎn)

。．在順序表中插入或刪除一個(gè)數(shù)據(jù)元素，需要平均移動(dòng)

個(gè)數(shù)據(jù)元素，移動(dòng)數(shù)據(jù)元素的個(gè)數(shù)與

位置

有關(guān)。．當(dāng)線性表的元素總數(shù)基本穩(wěn)定，且很少進(jìn)行插入和刪除操作，但要求以最快的速度存取線性表的元素是，應(yīng)采用 順序 存儲(chǔ)結(jié)構(gòu)。．根據(jù)線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)中每一個(gè)結(jié)點(diǎn)包含的指針個(gè)數(shù)，將線性鏈表分成 單鏈表 和

雙鏈表

。．順序存儲(chǔ)結(jié)構(gòu)是通過(guò)

下標(biāo) 表示元素之間的關(guān)系的；鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)是通過(guò) 指針

表示元素之間的關(guān)系的。L中只有一個(gè)元素結(jié)點(diǎn)的條件是 。18． 棧 是限定僅在表尾進(jìn)行插入或刪除操作的線性表，其運(yùn)算遵循 后進(jìn)先出 的原則。．空串是

零個(gè)字符的串 ，其長(zhǎng)度等于

零?？瞻状怯梢粋€(gè)或多個(gè)空格字符組成的串，其長(zhǎng)度等于其包含的空格個(gè)數(shù)。．組成串的數(shù)據(jù)元素只能是

單個(gè)字符 。．一個(gè)字符串中

任意個(gè)連續(xù)字符構(gòu)成的部分

稱為該串的子串。．子串

””

在主串

””

中的位置是 。

的每個(gè)元素是

i

的范圍從

到

下標(biāo)

j

的范圍從

到

，則存放

至少需要

個(gè)字節(jié)；

的第

列和第

行共占

個(gè)字節(jié)。24．稀疏矩陣一般的壓縮存儲(chǔ)方法有兩種，即

三元組表 和 十字鏈表

。），（（b），），（（（d））））的長(zhǎng)度是 ，深度是 。．在一棵二叉樹中，度為零的結(jié)點(diǎn)的個(gè)數(shù)為，度為

的結(jié)點(diǎn)的個(gè)數(shù)為

，則有

＝ 。．在有

個(gè)結(jié)點(diǎn)的二叉鏈表中，空鏈域的個(gè)數(shù)為。．一棵有

個(gè)葉子結(jié)點(diǎn)的哈夫曼樹共有個(gè)結(jié)點(diǎn)。．深度為

的二叉樹至多有 個(gè)結(jié)點(diǎn)。．若某二叉樹有

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

個(gè)結(jié)點(diǎn)僅有一個(gè)孩子，則該二叉樹的總結(jié)點(diǎn)個(gè)數(shù)為 。

。．線索二叉樹的左線索指向其

遍歷序列中的前驅(qū) ，右線索指向其遍歷序列中的后繼 。．在各種查找方法中，平均查找長(zhǎng)度與結(jié)點(diǎn)個(gè)數(shù)

無(wú)關(guān)的查找方法是 散列查找法 。．在分塊索引查找方法中，首先查找 索引表 ，然后查找相應(yīng)的 塊表 。．一個(gè)無(wú)序序列可以通過(guò)構(gòu)造一棵

二叉排序

樹而變成一個(gè)有序序列，構(gòu)造樹的過(guò)程即為對(duì)無(wú)序序列進(jìn)行排序的過(guò)程。．具有

個(gè)頂點(diǎn)的無(wú)向圖，邊的總數(shù)最多為__45__。．已知圖

的鄰接表如圖所示，其從頂點(diǎn)

出發(fā)的深度優(yōu)先搜索序列為，其從頂點(diǎn)

出發(fā)的廣度優(yōu)先搜索序列為。

．索引是為了加快檢索速度而引進(jìn)的一種數(shù)據(jù)結(jié)構(gòu)。一個(gè)索引隸屬于某個(gè)數(shù)據(jù)記錄集，它由若干索引項(xiàng)組成，索引項(xiàng)的結(jié)構(gòu)為 關(guān)鍵字

和

關(guān)鍵字對(duì)應(yīng)記錄的地址

。．

算法生成一個(gè)最小生成樹每一步選擇都要滿足

邊