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

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

1、一个栈的输入序列为a，b，c，d，下面哪一个序列不可能是这个栈的输出序列？（ ）

A、b，c，d，a

B、d，c，a，b

C、a，c，b，d

D、c，d，b，a

2、下面程序段的时间复杂度是（ ）。m=10;n=10;s=0;for(i=0;i<m;i++) for(j=0;j<n;j++) s+=i*j;

A、O(m)

B、O(n)

C、O(m*n)

D、O(1)

3、若线性表的操作主要是查找，很少涉及到插入、删除操作时，宜采用以下哪种存储结构较为合适（ ）。

A、双链表

B、单链表

C、顺序表

D、循环链表

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

A、1/2

B、1

C、2

D、4

5、判定一个循环队列Q（最多元素为m个）为满队列的条件是（ ）。

A、Q.front==Q.rear

B、Q.front!=Q.rear

C、Q.front==(Q.rear+1)%m

D、Q.front!=(Q.rear+1)%m

1、试题答案：B

试题解析：

对于A，可以经过这样的操作得到该输出序列：push(a)、push(b)、pop(b)、push(c)、pop(c)、push(d)、pop(d)、pop(a)；对于C，可以经过这样的操作得到该输出序列：push(a)、pop(a)、push(b)、push(c)、pop(c)、pop(b)、push(d)、pop(d)；对于D，可以经过这样的操作得到该输出序列：push(a)、push(b)、push(c)、pop(c)、push(d)、pop(d)、push(b)、push(a)。而对于B，若首先出栈的元素是d，则证明在d之前其余元素已入栈，且入栈的顺序为a，b，c，d，则出栈的顺序应为d，c，b，a，故本题选B。

2、试题答案：D

试题解析：

时间复杂度反映的是算法的执行时间随数据规模增长的变化趋势，题干所示的代码执行了100次，是一个常量的执行时间，与输入的规模无关，因此其时间复杂度为O(1)，故本题选D。

3、试题答案：C

试题解析：

链式存储结构是非随机存储结构，因此在双链表、单链表、循环链表中查找元素均需要从头开始遍历查找，时间复杂度均为O(n)。在链表中进行插入和删除操作时无需移动元素仅需要改变指针的指向，因此链式结构中插入和删除的时间复杂度为O(1)。而顺序存储结构是随机存储机构，在顺序表中查找元素的时间复杂度为O(1)，插入和删除元素操作需要移动元素，其时间复杂度为O(n)，故本题选C。

4、试题答案：C

试题解析：

对于无向图而言，顶点v的度是和v相关联的边的数目。对于有向图而言，顶点v的度是顶点v的入度+出度，以顶点v为头的弧的数目称为v的入度，以顶点v为尾的弧的数目称为v的出度。无论是有向图还是无向图，所有顶点的度数之和等于边数的2倍。故本题选C。

5、试题答案：C

试题解析：

将顺序队列首尾相接成环状空间即为循环队列。在循环队列中，队头指针指向头元素，队尾指针指向尾元素的下一个位置。若循环队列中存放n个元素，则rear==front，此时无法判断是队空的条件还是队满的条件。为了区分这两者，规定循环队列中当元素个数为n-1个时，判定队列已满。队列已满的条件为队头指针front在队尾指针rear的下一个位置上，因此最大容量为s的循环队列，队满条件为（rear+1）%s==front；队空条件为rear==front。故本题选C。