国家电网招聘考试计算机类专业知识数据结构与算法 (一)

国家电网招聘考试计算机类专业知识(数据结构与算法)模拟试卷2

(题后含答案及解析)

题型有：1.单项选择题

单项选择题

1.采用顺序查找法查找长度为n的顺序表时，查找成功的平均查找长度为

()。

A.(n-l)/2

B.(n+1)/2

C.n

D.n/2

正确答案：B

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

找的元素，最坏情况是查找的最后一个元素即想要查找的元素，所以查找成功的

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

2.在循环队列中用数组A[0..m-l]存放队列元素，其队头指针和队尾指

针分别为front和rear,则当前队列中的元素个数是()。

A.(front—rear+l)%m

B.(rear—front+1)%m

C.(front—rear+m)%m

D.(rear-front+m)%m

正确答案：D

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

A.找出数据结构的合理性

B.研究算法中输入和输出的关系

C.分析算法的效率，以求改进

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

正确答案：C

4.下列关于栈的叙述，正确的是()-

A.只要确定了入栈序列，就可以确定出栈序列

B.栈是一种操作受限的线性表，只允许在其两端进行操作

C.采用非递归方式重写递归程序时，必须使用栈

D.函数调用时，可以使用栈来保存必要的信息

正确答案：D

解析：确定了入栈序列无法确定出栈序列，因为各个元素出栈的时间是不确

定的；栈是一种操作受限的线性表，只允许在其一端进行操作；采用非递归方式

重写递归程序时，除了栈还可以使用循环结构算法。

5.若允许表达式中多种括号混合嵌套，则检查表达式中括号是否正确配对

的算法，通常选用的辅助结构是（）。

A.栈

B.线性表

C.队列

D.二叉排序树

正确答案：A

解析：由于栈具有先进后出的特点，因此选用辅助结构栈可以实现表达式中

多种括号混合嵌套的配对。例如，使用3个栈，就可以同时解决表达式中的“{”

与“}，，、“「，与，，］，，、，，（”与，，），，的配对问题。

6.设线性表的长度为15,采用冒泡排序，在最坏的情况下需要比较的次

数为（）o

A.66

B.78

C.105

D.112

正确答案：C

解析：冒泡排序在最坏的情况下需要比较n（n—1）/2次，本题中n=15,故

共需要比较105次。

7.在下列数据结构中，与所使用的计算机无关的是（）。

A.逻辑结构

B.存储结构

C.逻辑结构和存储结构

D.物理结构

正确答案：A

解析：存储结构和物理结构是同一概念的两个术语，都是数据结构在计算机

内存中的表示形式;逻辑结构是对数据元素间关系的描述，与所用的计算机无关。

8.对一个算法的评价，不包括（）方面的内容。

A.健壮性和可读性

B.并行性

C.正确性

D.时空复杂度

正确答案：B

解析：算法的评价标准：正确性、健壮性、可读性、高效性（时空复杂度）、

简单性。

9.算法指的是（）。

A.计算机程序

B.解决问题的计算方法

C.排序算法

D.解决问题的有限运算序列

正确答案：D

10.下列叙述正确的是（）。

A.串是一种特殊的线性表

B.串的长度必须大于零

C.串中元素只能是字母

D.空串就是空白串

正确答案：A

解析：串是由零个或多个字符的顺序排列所组成的线性表。串的长度可以等

于零，等于零时称为空串。空串和空白串是不同的，例如，Strings=""是空串；

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

11.在一棵度为3的树中，度为3的节点个数为2,度为2的节点个数为1,

度为1的节点个数为0,则度为0的节点个数为（）。

A.4

B.5

C.6

D.7

正确答案：C

解析：对于任一棵树，它的节点总数等于总度数加1。设度为0的节点个数

为n,则2+l+0+n=2X3+lX2+0Xl+nX0+l,解得n=6。因此，该树中度为0的

节点个数为6。

12.设链式栈中节点的结构为（data,link）,且top是指向栈顶的指针。若想

摘除链式栈的栈顶节点，并将被摘除节点的值保存到x中，则应执行（）操作。

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

解析：若想摘除链式栈的栈顶节点，并将被摘除节点的值保存到x中，则应

先将栈顶节点的值保存到x中，x=top—>data；,再摘除栈顶节点，即top=top

—>link；。

13.设广义表D（a,b,D）长度为3,则其深度为（）。

A.8

B.3

C.2

D.5

正确答案：A

解析：广义表D本身也是自己的子表，出现了递归，因此深度为8。

14.由权值分别为11、8、6、2、5的叶节点生成一棵哈夫曼树，它的带权

路径长度为（）o

A.53

B.71

C.48

D.24

正确答案：B

解析：根据题干描述，可画出哈夫曼树如下.则兵带杈路径长度=（6+8+11）

X2+（2+5）X3=71o

15.在一个顺序表的表尾插入一个元素的时间复杂度为（）。

oz\

(n

A.x7

oz2

(n

B.\

ozo

(

C.\

oz1

l

D.\

正确答案：D

解析：在一个顺序表的表尾插入一个元素的移动次数为0,时间复杂度为

O（l）o

16.判定一个栈ST（最多元素个数为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的单链表之后，这个过程的时间复

杂度为（）o

oz

(

A.\m)

ozm

(

B.CxD

o/

(

X

oz

(

D.\n)

正确答案：A

解析：将长度为n的单链表接在长度为m的单链表之后，需要先遍历长度

为m的单链表，找到最后一个节点，再进行链接操作。

18.设散列表中有m个存储单元，散列函数H（key）=key%p,则p最好选

择（）。

A.小于等于m的最大偶数

B.小于等于m的最大合数

C.小于等于m的最大奇数

D.小于等于m的最大素数

正确答案：D

19.采用开放定址法处理散列表的冲突时，其平均查找长度（）。

A.与链接法处理冲突相同

B.高于二分查找

C.低于链接法处理冲突

D.高于链接法处理冲突

正确答案：D

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

A.不存在度为1的节点

B.任意节点的左、右子树的节点数目相同

C.任意节点的左、右子树高度相同

D.任意节点的左、右子树高度之差的绝对值不大于1

正确答案：D

解析：平衡二叉树又称AVL树，它或者是一棵空树，或者是具有下列性质

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

差的绝对值不超过lo二叉树上节点的平衡因子定义为该节点的右子树的高度

减去它的左子树的高度。可见，平衡二叉树上所有节点的平衡因子只可能是一1、

0.lo只要二叉树上有一个节点的平衡因子的绝对值大于1,则该二叉树失去平

衡。

21.已知某二叉树的中序、层序遍历序列分别为DBAFCE、FDEBCA,则

该二叉树的后序遍历序列为（）。

A.DBACEF

B.DABECF

C.BCDEAF

D.ABDCEF

正确答案：D

解析：层序遍历是从根节点(第1层)出发，首先访问第1层的节点，其次从

左到右依次访问第2层上的节点，然后是第3层上的节点，依此类推，自上而下,

自左向右，逐层访问各层上的节点。层序遍历序列的第一个元素F为二叉树

的根节点；结合中序遍历序列可知，DBA为F的左子树，CE为F的右子树；层

序遍历序列的第二个元素D为F的左孩子节点，第三个元素E为F的右孩子节

点；根据子序列DBA可知，BA为D的右子树，层序遍历序列的第四个元素B

为D的右孩子节点；根据子序列CE可知，C为E的左孩子节点；根据子序列

BA可知，A为B的右孩子节点。综上所述，构造二叉树如下：因此，后序

遍历序列为ABDCEFo

22.快速排序在最坏情况下的时间复杂度为()。

A.0(n)

B.O(nlog2n)

C.O(log2n)

D.0(n2)

正确答案：D

解析：快速排序在最坏情况下，排序码共比较次数为n2/2,因此时间复杂

度为O(n2)。

23.树的度为3,共有29个节点，但没有度为1和2的节点，则该树中叶

节点个数为()。

A.0

B.9

C.18

D.不存在这样的树

正确答案：D

解析：若树的度为3,则说明树中只存在度为0、1、2、3的节点。假设叶

节点个数为n,由于没有度为1和2的节点，则说明度为3的节点个数为29-no

树中的节点总数=所有节点度之和+1,即29=3X(29—n)+l。解得n不是整数，

所以不存在这样的树。

24.A0V网络是一种()o

A.有向有环图

B.无向无环图

C.无向有环图

D.有向无环图

正确答案：D

解析：AOV网络是一种有向无环图，即没有回路。

25.下列关于算法的叙述，正确的是（）。

A.算法的时间复杂度就是算法执行的具体时间

B.算法的确定性是指算法可以在有限的时间内完成

C.通常使用算法的复杂度衡量其优劣

D.算法执行的基本运算次数与代码的长短有关

正确答案：C

解析：算法的时间复杂度是执行算法所需要的计算工作量。算法的确定性是

指算法必须步骤明确，不准模棱两可，不准有多义性。算法的复杂度是用来衡量

算法优劣的重要指标，包括空间复杂度和时间复杂度。算法执行的基本运算次数

与问题规模有关，并非取决于代码的长短。

26.设有一个二维数组A[m][n],假设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.元素之间无联系的数据

B.无序的数据元素

C.元素之间具有分支层次关系的数据

D.有序的数据元素

正确答案：c

解析：树是一种具有层次结构的非线性结构，所以树适合用来存储元素之间

具有分支层次关系的数据。

28.二叉树的第K层的节点数最多为（）个。

A.2k—1

B.2k+l

C.2k

D.2

正确答案：A

29.若含有18个元素的有序表存放在一维数组A[19]中，第一个元素放

A[l]中，现进行二分查找，则查找A[3]的比较序列的下标依次为（）。

A.9,5,3

B.