考研计算机专业综合在线题库每日一练（一十六）

本文提供考研计算机专业综合在线题库每日一练，以下为具体内容

1、某线性表中最常用的操作是在最后一个元素之后插入一个元素和删除第一个元素，则最节省运算时间的存储方式是（ ）。

A、 单链表

B、 仅有头指针的单循环链袭

C、 双链表

D、 仅有尾指针的单循环链表

2、对一颗有100个结点的完全二叉树按层编号，则编号为49的结点，它的父结点的编号为（ ）。

A、 24

B、 25

C、 98

D、 99

3、若采用邻接矩阵存储一个n个顶点的无向图，则该邻接矩阵是一个（ ）。

A、 上三角矩阵

B、 稀疏矩阵

C、 对角矩阵

D、 对称矩阵

4、在一个图中，所有顶点的度数之和等于所有边数的（ ）倍。

A、 1/2

B、 1

C、 2

D、 4

5、设无向图的邻接链表如下图所示，则该图的边的数目是（ ）。

A、 4

B、 5

C、 10

D、 20

1、试题答案：D

试题解析：

【考点】本题考查线性表的插入和删除操作。
【解析】链表有尾指针可以直接找到最后一个元素，在其后面插入一个元素的时间复杂度为O(1)。单循环链表中尾结点所指结点的next指针域指向第一个元素，删除第一个元素的时间复杂度为O(1)。故本题选D。

2、试题答案：A

试题解析：

【考点】本题考查完全二叉树性质。
【解析】对于一颗完全二叉树而言，若某一结点编号为i，则其父结点、左孩子和右孩子结点编号如下所示：

本题中i=49，则其父结点编号为⌊i/2⌋=49/2=24。故本题选A。

3、试题答案：D

试题解析：

【考点】本题考查邻接矩阵的性质。
【解析】用邻接矩阵来表示的图中，若从一个顶点到另一个顶点有边相连，则相应位置上为1，否则为0。对于无向图而言，若顶点a到顶点b有边相连，则顶点b到顶点a必定有边相连，因此用邻接矩阵表示的无向图必定是对称矩阵。故本题选D。

4、试题答案：C

试题解析：

【考点】本题考查图的性质。
【解析】一条边对应一个源结点和一个终结点，边对于它的源结点是一个出度，对于它的终结点是一个入度。综上，任意一条边都对应2个度，所以度数之总和是边数总和的两倍。故本题选C。

5、试题答案：B

试题解析：

【考点】本题考查邻接链表表示的图
【解析】由邻接链表得出的无向图如下所示，易知该图共5条边。故本题选B。