國家電網(wǎng)招聘考試計算機類專業(yè)知識數(shù)據(jù)結(jié)構(gòu)與算法 (一)

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

(題后含答案及解析)

題型有：1.單項選擇題

單項選擇題

1.采用順序查找法查找長度為n的順序表時，查找成功的平均查找長度為

()。

A.(n-l)/2

B.(n+1)/2

C.n

D.n/2

正確答案：B

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

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

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

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

針分別為front和rear,則當(dāng)前隊列中的元素個數(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.分析算法的效率，以求改進

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

正確答案：C

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

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

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

C.采用非遞歸方式重寫遞歸程序時，必須使用棧

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

正確答案：D

解析：確定了入棧序列無法確定出棧序列，因為各個元素出棧的時間是不確

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

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

5.若允許表達式中多種括號混合嵌套，則檢查表達式中括號是否正確配對

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

A.棧

B.線性表

C.隊列

D.二叉排序樹

正確答案：A

解析：由于棧具有先進后出的特點，因此選用輔助結(jié)構(gòu)?？梢詫崿F(xiàn)表達式中

多種括號混合嵌套的配對。例如，使用3個棧，就可以同時解決表達式中的“{”

與“}，，、“「，與，，］，，、，，（”與，，），，的配對問題。

6.設(shè)線性表的長度為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)中，與所使用的計算機無關(guān)的是（）。

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

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

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

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

正確答案：A

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

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

8.對一個算法的評價，不包括（）方面的內(nèi)容。

A.健壯性和可讀性

B.并行性

C.正確性

D.時空復(fù)雜度

正確答案：B

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

簡單性。

9.算法指的是（）。

A.計算機程序

B.解決問題的計算方法

C.排序算法

D.解決問題的有限運算序列

正確答案：D

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

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

B.串的長度必須大于零

C.串中元素只能是字母

D.空串就是空白串

正確答案：A

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

于零，等于零時稱為空串?？沾涂瞻状遣煌模?，Strings=""是空串；

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

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

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

A.4

B.5

C.6

D.7

正確答案：C

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

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

節(jié)點個數(shù)為6。

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

摘除鏈?zhǔn)綏５臈ｍ敼?jié)點，并將被摘除節(jié)點的值保存到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é)點，并將被摘除節(jié)點的值保存到x中，則應(yīng)

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

—>link；。

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

A.8

B.3

C.2

D.5

正確答案：A

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

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

路徑長度為（）o

A.53

B.71

C.48

D.24

正確答案：B

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

X2+（2+5）X3=71o

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

oz\

(n

A.x7

oz2

(n

B.\

ozo

(

C.\

oz1

l

D.\

正確答案：D

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

O（l）o

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

A.ST—>top==mO—1

B.ST->top==0

C.ST—>top!=mO

D.ST->top!=0

正確答案：A

解析：如果一個棧的棧頂指針ST—>top=mO-l,則該棧為滿。

17.將長度為n的單鏈表接在長度為m的單鏈表之后，這個過程的時間復(fù)

雜度為（）o

oz

(

A.\m)

ozm

(

B.CxD

o/

(

X

oz

(

D.\n)

正確答案：A

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

為m的單鏈表，找到最后一個節(jié)點，再進行鏈接操作。

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

擇（）。

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

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

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

D.小于等于m的最大素數(shù)

正確答案：D

19.采用開放定址法處理散列表的沖突時，其平均查找長度（）。

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

B.高于二分查找

C.低于鏈接法處理沖突

D.高于鏈接法處理沖突

正確答案：D

20.在平衡二叉樹中，（）。

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

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

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

D.任意節(jié)點的左、右子樹高度之差的絕對值不大于1

正確答案：D

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

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

差的絕對值不超過lo二叉樹上節(jié)點的平衡因子定義為該節(jié)點的右子樹的高度

減去它的左子樹的高度?？梢?，平衡二叉樹上所有節(jié)點的平衡因子只可能是一1、

0.lo只要二叉樹上有一個節(jié)點的平衡因子的絕對值大于1,則該二叉樹失去平

衡。

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

該二叉樹的后序遍歷序列為（）。

A.DBACEF

B.DABECF

C.BCDEAF

D.ABDCEF

正確答案：D

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

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

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

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

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

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

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

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

遍歷序列為ABDCEFo

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

A.0(n)

B.O(nlog2n)

C.O(log2n)

D.0(n2)

正確答案：D

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

度為O(n2)。

23.樹的度為3,共有29個節(jié)點，但沒有度為1和2的節(jié)點，則該樹中葉

節(jié)點個數(shù)為()。

A.0

B.9

C.18

D.不存在這樣的樹

正確答案：D

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

節(jié)點個數(shù)為n,由于沒有度為1和2的節(jié)點，則說明度為3的節(jié)點個數(shù)為29-no

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

所以不存在這樣的樹。

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

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

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

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

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

正確答案：D

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

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

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

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

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

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

正確答案：C

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

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

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

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

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

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

A.678

B.688

C.692

D.696

正確答案：C

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

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

27.樹最適合用來表示（）。

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

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

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

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

正確答案：c

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

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

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

A.2k—1

B.2k+l

C.2k

D.2

正確答案：A

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

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

A.9,5,3

B.