考研数据结构A在线题库每日一练（五十九）

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

1、链表不具有的特点是（ ）。

A、可随机访问任一元素

B、插入、删除不需要移动元素

C、不必事先估计存储空间

D、所需空间与线性表长度成正比

2、有n个球队参加的某联赛按单循环方式进行比赛，那么共需要进行（ ）场比赛。

A、n(n-1)/2

B、n

C、n(n-1)

D、n+1

3、假设一个有n个顶点和e条弧的有向图用邻接表表示，则删除与某个顶点vi相关的所有弧的时间复杂度是（ ）。

A、O(n)

B、O(e)

C、O(n+e)

D、O(n*e)

4、含有10个结点的树有（ ）条分支。

A、0

B、10

C、9

D、不确定

5、对n个记录的集合进行冒泡排序使之形成非递减有序序列，在从小到大排列好的情况下比较的次数最少，其比较次数为（ ）。

A、n+1

B、n

C、n-1

D、n(n-1)/2

1、试题答案：A

试题解析：

对于A，链表不是随机访问的结构，顺序表才是；对于B，链表的插入和删除不需要移动元素，仅需要改变指针；对于C，链表是动态存储，每插入一个结点就开辟一个新的存储空间，不必预先估计空间，而顺序表需要预先估计存储空间；对于D，线性表的长度与结点个数成正比，而存储空间也和结点个数成正比，因此链表所需空间与线性表长度成正比。故本题选A。

2、试题答案：A

试题解析：

n个球队需要和除自身以外的其余队比赛，因此n*(n-1)，而A同B比赛与B同A比赛是一样的，将重复计算的部分去掉n*(n-1)/2。这种计算思路与求有n个顶点的完全无向图的边数的思路是一样的。故本题选A。

3、试题答案：C

试题解析：

本题要求删除与某个顶点相关的所有弧，即删除当前结点的出度边和入度边，需要遍历所有顶点和所有边一次，将与Vi相关的所有结点删除，故本题选C。

4、试题答案：C

试题解析：

含有10个结点的树有9条分支。这是由于树中每个结点（除了根结点）都有一条从其父结点引出的分支，因此10个结点的树共有9条分支。故本题选C。

5、试题答案：C

试题解析：

冒泡排序中，最好情况下记录已经按非递减有序排列，只需要进行一趟比较即可完成排序，此时比较次数为n-1。故本题选C。