考研数据结构及程序设计在线题库每日一练（一十八）

本文提供考研数据结构及程序设计在线题库每日一练，以下为具体内容

1、下面关于线性表的叙述中，错误的是哪一个（ ）。

A、线性表采用顺序存储，必须占用一片连续的存储单元

B、线性表采用顺序存储，便于进行插入和删除操作

C、线性表采用链式存储，不必占用一片连续的存储单元

D、线性表采用链式存储，便于插入和删除操作

2、图G是n个顶点的无向完全图，则下列说法错误的有（ ）。

A、G的邻接多重表需要n(n-1)个边节点和n个顶点节点

B、G的连通分量个数最少

C、G为连通图

D、G所用顶点的度的总和为n(n-1)

3、下列叙述中正确的是（ ）。

A、程序执行的效率与数据的存储结构密切相关

B、程序执行的效率只取决于程序的控制结构

C、程序执行的效率只取决于所处理的数据量

D、以上三种说法都不对

4、设A是n×n的对称矩阵，将A的对角线及对角线上方的元素以列为主的次序存放在一维数组B[1…n(n+1)/2]中，对上述任一元素aij（1≤i，j≤n，且i≤j）在B中的位置为（ ）。

A、i(i-1)/2+j

B、j(j-1)/2+i

C、j(j-1)/2+i-1

D、i(i-1)/2+j-1

5、已知有向图G=(V，E)，其中V={V1，V2，V3，V4，V5，V6，V7}，E={<V1，V2>，<V1，V3>，<V1，V4>，<V2，V5>，<V3，V5>，<V3，V6>，<V4，V6>，<V5，V7>，<V6，V7>}，G的拓扑序列是（ ）。

A、V1，V3，V4，V6，V2，V5，V7

B、V1，V3，V2，V6，V4，V5，V7

C、V1，V3，V4，V5，V2，V6，V7

D、V1，V2，V5，V3，V4，V6，V7

1、试题答案：B

试题解析：

【考点】本题考查顺序表和链表的特点。
【解析】线性表采用顺序存储，即顺序表，系统必须为其分配一片连续的空间，可以随机查找，但是不便于进行插入和删除操作。因为，在顺序表中进行插入和删除操作时，可能需要移动大量元素。线性表采用链式存储，即链表，其中各个结点通过指针两两连接，不需要占用一片连续的存储单元。在链表中进行插入和删除操作时，只需要修改指针指向即可，非常方便。故本题选B。

2、试题答案：A

试题解析：

【考点】本题考查无向完全图的特点。
【解析】本题涉及的概念如下：
（1）完全图：假设一个图有n个顶点，那么如果任意两个顶点之间都有边的话，该图就称为完全图。
（2）连通图：从顶点v到w有路径，就称顶点v和w连通。如果图中任意两个顶点都连通，则该图为连通图。
（3）连通分量：无向图中的极大连通子图称为连通分量 。
A：n个顶点的无向完全图，其有n(n-1)/2条边，所以G的邻接多重表需要n(n-1) /2个边节点。因此，选项A说法错误。
B：G是完全图则其一定是连通图，所以它的连通图只有其本身。
C：G 是完全图，则其一定是连通图。
D n个顶点的无向完全图，其有n(n-1)/2条边。而一条边对应一个出度和一个入度，所以G所用顶点的度的总和为n(n-1)。
综上所述，本题选A。

3、试题答案：A

试题解析：

【考点】本题考查影响程序执行效率的因素。
【解析】影响程序执行的效率有很多，比如数据的存储结构、程序的控制结构、程序所处理的数据量等。故本题选A。

4、试题答案：B

试题解析：

【考点】本题考查对称矩阵的压缩存储。
【解析】因为i从1开始，所以非零元素aij是第i行第j个元素。下三角矩阵A（n×n）按列优先顺序压缩时，aij是第（1+2+…+j-1）+i=j（j-1）/2+i个元素。又因为数组B的下标是从1开始的，所以aij存储在对应的数组下标为j(j-1)/2+i的位置。故本题选B。

5、试题答案：A

试题解析：

【考点】本题考查拓扑排序。
【解析】生成拓扑序列的过程如下所示，由此可知本题选A。