國(guó)家電網(wǎng)招聘考試計(jì)算機(jī)類(lèi)專(zhuān)業(yè)知識(shí)數(shù)據(jù)結(jié)構(gòu)與算法 (一)

國(guó)家電網(wǎng)招聘考試計(jì)算機(jī)類(lèi)專(zhuān)業(yè)知識(shí)(數(shù)據(jù)結(jié)構(gòu)與算法)模擬試卷2

(題后含答案及解析)

題型有：1.單項(xiàng)選擇題

單項(xiàng)選擇題

1.采用順序查找法查找長(zhǎng)度為n的順序表時(shí)，查找成功的平均查找長(zhǎng)度為

()。

A.(n-l)/2

B.(n+1)/2

C.n

D.n/2

正確答案：B

解析：在查找成功的前提下，查找的最好情況是查找的第一個(gè)元素即想要查

找的元素，最壞情況是查找的最后一個(gè)元素即想要查找的元素，所以查找成功的

平均查找長(zhǎng)度是(n+1)/2。

2.在循環(huán)隊(duì)列中用數(shù)組A[0..m-l]存放隊(duì)列元素，其隊(duì)頭指針和隊(duì)尾指

針?lè)謩e為front和rear,則當(dāng)前隊(duì)列中的元素個(gè)數(shù)是()。

A.(front—rear+l)%m

B.(rear—front+1)%m

C.(front—rear+m)%m

D.(rear-front+m)%m

正確答案：D

3.算法分析的目的是()。

A.找出數(shù)據(jù)結(jié)構(gòu)的合理性

B.研究算法中輸入和輸出的關(guān)系

C.分析算法的效率，以求改進(jìn)

D.分析算法的易懂性和文檔性

正確答案：C

4.下列關(guān)于棧的敘述，正確的是()-

A.只要確定了入棧序列，就可以確定出棧序列

B.棧是一種操作受限的線性表，只允許在其兩端進(jìn)行操作

C.采用非遞歸方式重寫(xiě)遞歸程序時(shí)，必須使用棧

D.函數(shù)調(diào)用時(shí)，可以使用棧來(lái)保存必要的信息

正確答案：D

解析：確定了入棧序列無(wú)法確定出棧序列，因?yàn)楦鱾€(gè)元素出棧的時(shí)間是不確

定的；棧是一種操作受限的線性表，只允許在其一端進(jìn)行操作；采用非遞歸方式

重寫(xiě)遞歸程序時(shí)，除了棧還可以使用循環(huán)結(jié)構(gòu)算法。

5.若允許表達(dá)式中多種括號(hào)混合嵌套，則檢查表達(dá)式中括號(hào)是否正確配對(duì)

的算法，通常選用的輔助結(jié)構(gòu)是（）。

A.棧

B.線性表

C.隊(duì)列

D.二叉排序樹(shù)

正確答案：A

解析：由于棧具有先進(jìn)后出的特點(diǎn)，因此選用輔助結(jié)構(gòu)?？梢詫?shí)現(xiàn)表達(dá)式中

多種括號(hào)混合嵌套的配對(duì)。例如，使用3個(gè)棧，就可以同時(shí)解決表達(dá)式中的“{”

與“}，，、“「，與，，］，，、，，（”與，，），，的配對(duì)問(wèn)題。

6.設(shè)線性表的長(zhǎng)度為15,采用冒泡排序，在最壞的情況下需要比較的次

數(shù)為（）o

A.66

B.78

C.105

D.112

正確答案：C

解析：冒泡排序在最壞的情況下需要比較n（n—1）/2次，本題中n=15,故

共需要比較105次。

7.在下列數(shù)據(jù)結(jié)構(gòu)中，與所使用的計(jì)算機(jī)無(wú)關(guān)的是（）。

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

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

C.邏輯結(jié)構(gòu)和存儲(chǔ)結(jié)構(gòu)

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

正確答案：A

解析：存儲(chǔ)結(jié)構(gòu)和物理結(jié)構(gòu)是同一概念的兩個(gè)術(shù)語(yǔ)，都是數(shù)據(jù)結(jié)構(gòu)在計(jì)算機(jī)

內(nèi)存中的表示形式;邏輯結(jié)構(gòu)是對(duì)數(shù)據(jù)元素間關(guān)系的描述，與所用的計(jì)算機(jī)無(wú)關(guān)。

8.對(duì)一個(gè)算法的評(píng)價(jià)，不包括（）方面的內(nèi)容。

A.健壯性和可讀性

B.并行性

C.正確性

D.時(shí)空復(fù)雜度

正確答案：B

解析：算法的評(píng)價(jià)標(biāo)準(zhǔn)：正確性、健壯性、可讀性、高效性（時(shí)空復(fù)雜度）、

簡(jiǎn)單性。

9.算法指的是（）。

A.計(jì)算機(jī)程序

B.解決問(wèn)題的計(jì)算方法

C.排序算法

D.解決問(wèn)題的有限運(yùn)算序列

正確答案：D

10.下列敘述正確的是（）。

A.串是一種特殊的線性表

B.串的長(zhǎng)度必須大于零

C.串中元素只能是字母

D.空串就是空白串

正確答案：A

解析：串是由零個(gè)或多個(gè)字符的順序排列所組成的線性表。串的長(zhǎng)度可以等

于零，等于零時(shí)稱(chēng)為空串?？沾涂瞻状遣煌?，例如，Strings=""是空串；

Strings=NULL,是空白串。串中的元素只能是字符，但并不只是字母。

11.在一棵度為3的樹(shù)中，度為3的節(jié)點(diǎn)個(gè)數(shù)為2,度為2的節(jié)點(diǎn)個(gè)數(shù)為1,

度為1的節(jié)點(diǎn)個(gè)數(shù)為0,則度為0的節(jié)點(diǎn)個(gè)數(shù)為（）。

A.4

B.5

C.6

D.7

正確答案：C

解析：對(duì)于任一棵樹(shù)，它的節(jié)點(diǎn)總數(shù)等于總度數(shù)加1。設(shè)度為0的節(jié)點(diǎn)個(gè)數(shù)

為n,則2+l+0+n=2X3+lX2+0Xl+nX0+l,解得n=6。因此，該樹(shù)中度為0的

節(jié)點(diǎn)個(gè)數(shù)為6。

12.設(shè)鏈?zhǔn)綏Ｖ泄?jié)點(diǎn)的結(jié)構(gòu)為（data,link）,且top是指向棧頂?shù)闹羔槨Ｈ粝?/p>

摘除鏈?zhǔn)綏５臈ｍ敼?jié)點(diǎn)，并將被摘除節(jié)點(diǎn)的值保存到x中，則應(yīng)執(zhí)行（）操作。

A.x=top->data；top=top->link；

B.top=top->link；x二top->data；

C.x=top；top=top->link；

D.x=top->data；

正確答案：A

解析：若想摘除鏈?zhǔn)綏５臈ｍ敼?jié)點(diǎn)，并將被摘除節(jié)點(diǎn)的值保存到x中，則應(yīng)

先將棧頂節(jié)點(diǎn)的值保存到x中，x=top—>data；,再摘除棧頂節(jié)點(diǎn)，即top=top

—>link；。

13.設(shè)廣義表D（a,b,D）長(zhǎng)度為3,則其深度為（）。

A.8

B.3

C.2

D.5

正確答案：A

解析：廣義表D本身也是自己的子表，出現(xiàn)了遞歸，因此深度為8。

14.由權(quán)值分別為11、8、6、2、5的葉節(jié)點(diǎn)生成一棵哈夫曼樹(shù)，它的帶權(quán)

路徑長(zhǎng)度為（）o

A.53

B.71

C.48

D.24

正確答案：B

解析：根據(jù)題干描述，可畫(huà)出哈夫曼樹(shù)如下.則兵帶杈路徑長(zhǎng)度=（6+8+11）

X2+（2+5）X3=71o

15.在一個(gè)順序表的表尾插入一個(gè)元素的時(shí)間復(fù)雜度為（）。

oz\

(n

A.x7

oz2

(n

B.\

ozo

(

C.\

oz1

l

D.\

正確答案：D

解析：在一個(gè)順序表的表尾插入一個(gè)元素的移動(dòng)次數(shù)為0,時(shí)間復(fù)雜度為

O（l）o

16.判定一個(gè)棧ST（最多元素個(gè)數(shù)為m0）為滿(mǎn)的條件是（）。

A.ST—>top==mO—1

B.ST->top==0

C.ST—>top!=mO

D.ST->top!=0

正確答案：A

解析：如果一個(gè)棧的棧頂指針ST—>top=mO-l,則該棧為滿(mǎn)。

17.將長(zhǎng)度為n的單鏈表接在長(zhǎng)度為m的單鏈表之后，這個(gè)過(guò)程的時(shí)間復(fù)

雜度為（）o

oz

(

A.\m)

ozm

(

B.CxD

o/

(

X

oz

(

D.\n)

正確答案：A

解析：將長(zhǎng)度為n的單鏈表接在長(zhǎng)度為m的單鏈表之后，需要先遍歷長(zhǎng)度

為m的單鏈表，找到最后一個(gè)節(jié)點(diǎn)，再進(jìn)行鏈接操作。

18.設(shè)散列表中有m個(gè)存儲(chǔ)單元，散列函數(shù)H（key）=key%p,則p最好選

擇（）。

A.小于等于m的最大偶數(shù)

B.小于等于m的最大合數(shù)

C.小于等于m的最大奇數(shù)

D.小于等于m的最大素?cái)?shù)

正確答案：D

19.采用開(kāi)放定址法處理散列表的沖突時(shí)，其平均查找長(zhǎng)度（）。

A.與鏈接法處理沖突相同

B.高于二分查找

C.低于鏈接法處理沖突

D.高于鏈接法處理沖突

正確答案：D

20.在平衡二叉樹(shù)中，（）。

A.不存在度為1的節(jié)點(diǎn)

B.任意節(jié)點(diǎn)的左、右子樹(shù)的節(jié)點(diǎn)數(shù)目相同

C.任意節(jié)點(diǎn)的左、右子樹(shù)高度相同

D.任意節(jié)點(diǎn)的左、右子樹(shù)高度之差的絕對(duì)值不大于1

正確答案：D

解析：平衡二叉樹(shù)又稱(chēng)AVL樹(shù)，它或者是一棵空樹(shù)，或者是具有下列性質(zhì)

的二叉樹(shù)：①左子樹(shù)和右子樹(shù)都是平衡二叉樹(shù)。②左子樹(shù)和右子樹(shù)的高度之

差的絕對(duì)值不超過(guò)lo二叉樹(shù)上節(jié)點(diǎn)的平衡因子定義為該節(jié)點(diǎn)的右子樹(shù)的高度

減去它的左子樹(shù)的高度。可見(jiàn)，平衡二叉樹(shù)上所有節(jié)點(diǎn)的平衡因子只可能是一1、

0.lo只要二叉樹(shù)上有一個(gè)節(jié)點(diǎn)的平衡因子的絕對(duì)值大于1,則該二叉樹(shù)失去平

衡。

21.已知某二叉樹(shù)的中序、層序遍歷序列分別為DBAFCE、FDEBCA,則

該二叉樹(shù)的后序遍歷序列為（）。

A.DBACEF

B.DABECF

C.BCDEAF

D.ABDCEF

正確答案：D

解析：層序遍歷是從根節(jié)點(diǎn)(第1層)出發(fā)，首先訪問(wèn)第1層的節(jié)點(diǎn)，其次從

左到右依次訪問(wèn)第2層上的節(jié)點(diǎn)，然后是第3層上的節(jié)點(diǎn)，依此類(lèi)推，自上而下,

自左向右，逐層訪問(wèn)各層上的節(jié)點(diǎn)。層序遍歷序列的第一個(gè)元素F為二叉樹(shù)

的根節(jié)點(diǎn)；結(jié)合中序遍歷序列可知，DBA為F的左子樹(shù)，CE為F的右子樹(shù)；層

序遍歷序列的第二個(gè)元素D為F的左孩子節(jié)點(diǎn)，第三個(gè)元素E為F的右孩子節(jié)

點(diǎn)；根據(jù)子序列DBA可知，BA為D的右子樹(shù)，層序遍歷序列的第四個(gè)元素B

為D的右孩子節(jié)點(diǎn)；根據(jù)子序列CE可知，C為E的左孩子節(jié)點(diǎn)；根據(jù)子序列

BA可知，A為B的右孩子節(jié)點(diǎn)。綜上所述，構(gòu)造二叉樹(shù)如下：因此，后序

遍歷序列為ABDCEFo

22.快速排序在最壞情況下的時(shí)間復(fù)雜度為()。

A.0(n)

B.O(nlog2n)

C.O(log2n)

D.0(n2)

正確答案：D

解析：快速排序在最壞情況下，排序碼共比較次數(shù)為n2/2,因此時(shí)間復(fù)雜

度為O(n2)。

23.樹(shù)的度為3,共有29個(gè)節(jié)點(diǎn)，但沒(méi)有度為1和2的節(jié)點(diǎn)，則該樹(shù)中葉

節(jié)點(diǎn)個(gè)數(shù)為()。

A.0

B.9

C.18

D.不存在這樣的樹(shù)

正確答案：D

解析：若樹(shù)的度為3,則說(shuō)明樹(shù)中只存在度為0、1、2、3的節(jié)點(diǎn)。假設(shè)葉

節(jié)點(diǎn)個(gè)數(shù)為n,由于沒(méi)有度為1和2的節(jié)點(diǎn)，則說(shuō)明度為3的節(jié)點(diǎn)個(gè)數(shù)為29-no

樹(shù)中的節(jié)點(diǎn)總數(shù)=所有節(jié)點(diǎn)度之和+1,即29=3X(29—n)+l。解得n不是整數(shù)，

所以不存在這樣的樹(shù)。

24.A0V網(wǎng)絡(luò)是一種()o

A.有向有環(huán)圖

B.無(wú)向無(wú)環(huán)圖

C.無(wú)向有環(huán)圖

D.有向無(wú)環(huán)圖

正確答案：D

解析：AOV網(wǎng)絡(luò)是一種有向無(wú)環(huán)圖，即沒(méi)有回路。

25.下列關(guān)于算法的敘述，正確的是（）。

A.算法的時(shí)間復(fù)雜度就是算法執(zhí)行的具體時(shí)間

B.算法的確定性是指算法可以在有限的時(shí)間內(nèi)完成

C.通常使用算法的復(fù)雜度衡量其優(yōu)劣

D.算法執(zhí)行的基本運(yùn)算次數(shù)與代碼的長(zhǎng)短有關(guān)

正確答案：C

解析：算法的時(shí)間復(fù)雜度是執(zhí)行算法所需要的計(jì)算工作量。算法的確定性是

指算法必須步驟明確，不準(zhǔn)模棱兩可，不準(zhǔn)有多義性。算法的復(fù)雜度是用來(lái)衡量

算法優(yōu)劣的重要指標(biāo)，包括空間復(fù)雜度和時(shí)間復(fù)雜度。算法執(zhí)行的基本運(yùn)算次數(shù)

與問(wèn)題規(guī)模有關(guān)，并非取決于代碼的長(zhǎng)短。

26.設(shè)有一個(gè)二維數(shù)組A[m][n],假設(shè)A⑼⑼存放位置在644,A[2][2]#

放位置在676,每個(gè)元素占一個(gè)空間，則A[3][3]存放（）位置。

A.678

B.688

C.692

D.696

正確答案：C

解析:A⑵⑵是A⑼[0]后面的第2n+2個(gè)元素，即2n+2=676—644,解得n=15。

A⑶⑶是A⑵⑵后面的第n+1個(gè)元素,676+n+l=692,則A⑶⑶存放位置是692。

27.樹(shù)最適合用來(lái)表示（）。

A.元素之間無(wú)聯(lián)系的數(shù)據(jù)

B.無(wú)序的數(shù)據(jù)元素

C.元素之間具有分支層次關(guān)系的數(shù)據(jù)

D.有序的數(shù)據(jù)元素

正確答案：c

解析：樹(shù)是一種具有層次結(jié)構(gòu)的非線性結(jié)構(gòu)，所以樹(shù)適合用來(lái)存儲(chǔ)元素之間

具有分支層次關(guān)系的數(shù)據(jù)。

28.二叉樹(shù)的第K層的節(jié)點(diǎn)數(shù)最多為（）個(gè)。

A.2k—1

B.2k+l

C.2k

D.2

正確答案：A

29.若含有18個(gè)元素的有序表存放在一維數(shù)組A[19]中，第一個(gè)元素放

A[l]中，現(xiàn)進(jìn)行二分查找，則查找A[3]的比較序列的下標(biāo)依次為（）。

A.9,5,3

B.