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

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

（题后含答案及解析）

题型有：1.单项选择题

单项选择题

1.设用邻接矩阵A表示有向图G的存储结构，则有向图G中顶点i的入

度为（）。

A.第i列0元素的个数

B.第i列非0元素的个数

C.第i行0元素的个数

D.第i行非0元素的个数

正确答案：B

解析：在有向图的邻接矩阵中，第i行非0元素的个数即为顶点i的出度，

第i列非0元素的个数即为顶点i的入度。

2.执行一趟排序结束后不一定能够选出一个元素放在其最终位置上的是

（）0

A.冒泡排序

B.堆排序

C.快速排序

D.希尔排序

正确答案：D

解析：冒泡排序每趟选出一个最值移至序列的一端；堆排序和快速排序的一

趟排序可以使选出的基准值移至最终位置。

3.一个栈的初始状态为空，现有一个入栈序列ABCDEF,则不可能的出

栈序列是（）。

A.ABCDEF

B.FEDCBA

C.ABCEDF

D.ABCFDE

正确答案：D

解析：栈的特点是元素后进先出。A、B、C三项的出栈序列均可能发生。D

项中的F出栈时，表明D和E已经入栈，而二者中后入栈的是E,因此不可能

出现D比E先出栈的情况。

4.顺序查找不论在顺序线性表中，还是在链式线性表中，时间复杂度都为

A.O(n-l)

B.O(n)

C.O(n+1)

D.O(log2n)

正确答案：B

解析：无论是顺序存储还是链式存储，使用顺序查找法的时间复杂度相同,

都为O(n)。

5.二路归并排序的时间复杂度为()0

A.O(n-l)

B.O(n)

C.O(nlog2n)

D.O(log2n)

正确答案：C

6.深度为k的完全二叉树中最少有()个节点。

A.2k-1-1

B.2k-l-l

C.2k-1

D.2k

正确答案：C

解析：当第k层只有最左边一个节点时，完全二叉树具有最少的节点，因此

最少的节点个数为2k—l—l+l=2k—l。

7.设指针变量front表示链式队列的队头指针，指针变量rear表示链式队

列的队尾指针，指针变量s指向将要入队的节点X,则入队的操作序列为()°

A.s->next=rear；rear=s；

B.front—>next=s；front=s；

C.real—>next=s；rear=s；

D.s->next=front；front=s；

正确答案：C

解析：向队列插入元素，即入队操作，应该在队尾进行，所以需要修改队尾

指针，实现新节点的入队操作。

8.下列关于数组的叙述，正确的是()。

A.数组大小是固定的,可以有不同类型的数组元素

B.数组大小是可变的,所有数组元素的类型必须相同

C.数组大小是固定的,所有数组元素的类型必须相同

D.数组大小是可变的,可以有不同类型的数组元素

正确答案：C

解析：数组的定义强调，在声明数组时需要确定数组大小，因此数组大小是

固定的，并且数组中的元素必须是相同的数据类型。

9.设某哈夫曼树中有199个节点，则该哈夫曼树中有（）个叶节点。

A.101

B.100

C.99

D.102

正确答案：B

解析：哈夫曼树中的节点只有两种，一种是度为0的节点，另一种是度为2

的节点。由于哈夫曼树是二叉树，因此可列方程组n2=n0—l,n0+n2=199,解得

n0=100o

10.下列程序段的时间复杂度为（）□for（i=0；i<m；i++）for（j=0；j<t；

j++）c[i][j]=0；for（i=0；i<m；i++）for（j=0；j<t；j++）for（k=0；k<n；

k++）c[i]U]=c[i]U]+a[i][k]*b[k][j];

A.O（mXnXt）

B.O（m+n+t）

C.O（mXt+n）

D.O（m+nxt）

正确答案：A

解析：在本题的程序段中，有两段循环程序，一段是一个双层嵌套循环，另

一段是一个三层嵌套循环，所以基本操作是c[i][j]=c[i]U]+a[i][k]*b[k]U],此基本

操作共执行mXtXn次。

11.设有序表中的元素为13,18,24,35,47,50,62,则在其中利用二

分查找法查找值为24的元素需要经过（）次比较。

A.4

B.2

C.3

D.1

正确答案：C

解析：二分查找法的每一次查找都要与中间值进行比较。24第1次与35进

行比较，24小于35,接下来在35的左半部分中进行查找，左半部分的中间值为

18；24第2次与18进行比较，24大于18,接下来在18的右半部分中进行查找;

24第3次与24进行比较，此时查找成功，共比较了3次。

12.设F是由Tl、T2和T3三棵树组成的森林，与F对应的二叉树为B,

Tl、T2和T3的节点数分别为Nl、N2和N3,则二叉树B的根节点的左子树的

节点个数为()o

A.N1-1

B.N2+N3

C.N2-1

D.N1+N3

正确答案：A

解析：由森林转换为二叉树，利用的是树转换为二叉树时，二叉树根节点的

右子树始终为空的特点。将森林转换为二叉树的过程：先将森林中的每一棵树转

换为二叉树，再将第一棵树的根节点作为转换后二叉树的根节点，第一棵树的左

子树作为转换后二叉树根节点的左子树，第二棵树作为转换后二叉树根节点的右

子树，第三棵树作为转换后二叉树根节点的右子树的右子树，以此类推，通过根

节点的兄弟链将各棵树转换成的二叉树链接起来，森林便可以转换为一棵二叉

树。因此，二叉树B的根节点的左子树的节点个数为N2—1。

13.利用直接插入排序法的思想建立一个有序线性表的时间复杂度为

()。

A.O(nlog2n)

B.O(n+1)

C.O(log2n)

D.0(n2)

正确答案：D

14.设指针变量p指向双向链表中节点A,指针变量s指向被插入的节点

X,则在节点A的后面插入节点X的操作序列为()o

A.p—>right=s；s->left=p；p—>right—>left=s；s—>right=p—>right；

B.p—>right=s；p—>right—>left=s；s—>left=p；s—>right=p->right；

C.s—>left=p；s—>right=p—>right；p—>right=s；p—>right—>left=s；

D.s—>left=p；s—>right=p—>right；p—>right—>left=s；p—>right=s；

正确答案：D

解析：为了防止插入节点时链表断裂，在修改指针时，需要先使S的后继指

针指向P原来的后继节点，然后修改P的后继指针。

15.将32个元素进行堆排序，则最坏的情况需要比较()次。

A.60

B.84

C.144

D.160

正确答案：D

解析：金排序的最坏情况需要比较nlog2n次，带人数值计算得，32个元素

进行堆排序，最坏的情况需要比较160次。

16.设顺序表的长度为n,则顺序查找的平均比较次数为()0

A.(n-l)/2

B.n/2

C.(n+l)/2

D.n

正确答案：C

解析：顺序查找是顺序遍历查找表，直至找到或查找失败，所以最好的情况

是第一个节点即想要查找的元素，最坏的情况是查找失败，所以平均比较次数为

(n+l)/2o

17.设顺序线性表的长度为30,分成5块，每块6个元素，如果采用分块

查找，则其平均查找长度为()。

A.5

B.11

C.7

D.6.5

正确答案：D

解析：分块查找是先在索引表中进行查找，找到该元素可能存在的块号，然

后在块中顺序查找，则本题的平均查找长度为(5+l)/2+(6+l)/2=6.5o

18.设有向无环图G中的有向边集合£={<1,2>,<2,3>,<3,4>,

<1，4>),则下列属于该有向图G的一种拓扑排序序列的是()。

A.1,2,3,4

B.2,3,4,1

C.1,2,4,3

D.1,4,2,3

正确答案：A

解析：根据题干描述，可画出有向图如下：对有向图进行拓扑排序，入

度为。的顶点成为可输出的候选顶点，每次选择入度为0的顶点输出，并删除该

顶点和其相关联的边，直到所有顶点都已输出，或者剩下的图中不存在入度为0

的顶点。因此，该有向图G的拓扑序列是1,2,3,4o

19.设有一组初始记录关键字序列为(34,76,45,18,26,54,92),则

由这组记录关键字生成的二叉排序树的深度为()。

A.4

B.6

C.5

D.7

正确答案：A

解析：根据题干描述，可画出二叉排序树如下：该二叉排序树的深度为

4o

20.设一组初始记录关键字序列为（Q,H,C,Y,P,A,M,S,R,D,

F,X）,则按字母升序的第一趟冒泡排序结束后的结果是（）。

A.A,D,C,R,F,Q,M,S,Y,P,H,X

B.P,A,C,S,q,D,F,X,R,H,M,Y

C.F,H,C,D,P,A,M,Q,R,S,Y,S

D.H,C,Q,P,A,M,S,R,D,F,X,Y

正确答案：D

解析：每一趟冒泡排序都是从第一个记录开始，将相邻的两个记录的关键字

进行比较，若是降序则进行交换，一趟排序完成后，关键字最大的记录被移至序

列的末尾。

21.由同一关键字集合构造的各棵二叉排序树，（）o

A.其形态不一定相同，但平均查找长度相同

B.其形态不一定相同，平均查找长度也不一定相同

C.其形态都相同，但平均查找长度不一定相同

D.其形态都相同，平均查找长度也相同

正确答案：B

解析：由同一关键字集合构造的各棵二叉排序树，由于关键字插入的顺序不

一定相同，所以其形态不一定相同，平均查找长度也不一定相同。

22.设指针q指向单链表中节点A,指针p指向单链表中节点A的后继节

点B,指针s指向被插入的节点X,则在节点A和节点B之间插入节点X的操

作序列为（）o

A.P->next=s；s—>next=q；

B.q—>next=s；s—>next=p；

C.p—>next=s—>next；s—>next=p；

D.s—>next=p->next；p—>next=s；

正确答案：B

解析：插入节点X,应使节点A的next域指向节点X,使节点X的next域

指向节点Bo

23.下列关于线性表的叙述，错误的是（）（>

A.线性表中的每个节点有且仅有一个后继节点

B.非空线性表只有一个根节点

C.线性表通常采用顺序存储和链式存储两种结构

D.线性表是有限序列

正确答案：A

解析：在线性表中，除了最后一个节点外，其他节点有且仅有一个后继节点；

除了第一个节点外，其他节点有且仅有一个前趋节点。

24.设有一个10阶的下三角矩阵A（包括对角线），按照从上到下、从左到

右的顺序存储到连续的55个存储单元中，每个数组元素占1个字节的存储空间，

则A[5][4]与A[0]⑼的地址之差为（）o

A.55

B.19

C.28

D.10

正确答案：B

解析：行优先压缩存储下三角矩阵，元素阴在数组中的存放位置为（i+1）

Xi/2+j,因此A⑶⑷的存放位置是19,A⑼⑼的存放位置是0,地址相差为

19o

25.设一组初始记录关键字的长度为8,则最多经过（）趟插入排序可以

得到有序序列。

A.8

B.7

C.9

D.6

正确答案：B

解析：插入排序的每一趟将待排序的记录按其关键字大小插入到前面已经排

好序的有序序列的适当位置，直到记录全部插入为止。所以共8个关键字的序列，

最多经过7趟插入排序就可以得到一个有序序列。

26.二叉排序树中左子树上所有节点的值均（）根节点的值。

A.小于

B.等于

C.大于

D.大于或等于

正确答案：A

解析：二叉排序树的左子树所有节点的值都小于根节点的值，并且根节点的

值都小于右子树所有节点的值。

27.设一组权值集合W={15,3,14,2,6,9,16,17},要求根据这一

权值集合构造一棵哈夫曼树，则这棵哈夫曼树的带权路径长度为（）o

A.219

B.129

C.189

D.229

正确答案：D

解析：根据题干描述，可画出哈夫曼树如下：则其带权路径长度=17X2+16

X2+15X3+14X3+9X3+6X4+3X5+2X5=229。

28.设有n个关键字具有相同的Hash函数值，则用线性探测法把这n个关

键字映射到Hash表中，需要做()次线性探测。

A.n(n+l)

B.n

C.n(n+l)/2

D.n(n—1]/2

正确答案：D

解析：线性探测法解决冲突的办法是一旦目标空间被占有，则探测相邻的下

一个空间，如果空闲则插入，否则继续向下一个探测，如果到了Hash表末尾则

返回Hash表开头进行探测，一旦全部空间都被占据，则无法插入。第一个关键

字映射到Hash表时插入成功，从第二个关键字开始出现冲突，第二个关键字映

射时做1次线性探测，第三个关键字映射时做2次线性探测，以此类推，第n

个关键字映射时做n—l次线性探测，因此共需