【HBU】数据结构第一次月测题（线性结构）

数据结构第一次月测题

判断题：

1.在具有N个结点的单链表中，访问结点和增加结点的时间复杂度分别对应为O（1）和O（N）  F           访问节点的时间复杂度为O(N)

2.对于顺序存储长度为N的线性表，访问结点和增加结点的时间复杂度分别对应为O（1）和O（N） T

3.在用数组表示的循环队列中，front值一点小于等于rear值。 F

这是不对的。在用数组表示的循环队列中,front值不一定小于等于rear值。在一个循环队列中，如果已经有若干个元素出队了，而且入队元素的总个数超过了数组的大小个数，是会发生front大于raer这种现象的。

4.若某线性表最常用的操作是存取任一指定序号的元素和在最后进行插入和删除的运算，则利用顺序表存储最节省时间。 T

“存取任一指定序号”最好的方法是实现“随机存取”，则可采用顺序表。并且，因为插入和删除操作都是在最后进行的，所以无需大量移动数据元素，选项A是最合适的。

5.若用一个栈的输出序列为{1,2,3,4,5}，则不可能得到{3,4,1,2,5}   T

6.对于顺序存储的长度为N的线性表，删除第一个元素和插入最后一个元素的时间复杂度分别对应为O（1）和O（N）。 F  反了

7.若用链表来表示一个线性表，则表中元素的地址一定是连续的。 F

链表不一定是连续的

8.所谓“循坏队列”是指用单向循环链表或者循环数组表示的队列。 F

循环队列是顺序存储与循环数组存储结构一样，但循环链表是链式存储

9.若一个栈的输入序列为1,2,3，...，N，输出序列的第一个元素是i，则第j个输出元素是j-i-1。 F  解释：不一定为j-i-1

单选题：

1. 

    

解析：我们前面采用front与rear指针来实现循环队列其中队满的判断是front = （rear+ 1）% n来判断的，因此我们是实际容纳元素的个数就是m-1，但是这里我们用size代替了rear指针，也就是说我们队满可以用size与m的关系来判断。

因此这里的实际容纳元素的数目就是m。

2.

3.  

删除两个元素后，队首指针要加2，front=（front+2）%6，结果为2，每加入一个元素队尾指针加一，即real=（real+2）%6，加入两个元素后变为0，所以选B

4.

 M66位于第六行，则之上的元素数量为12+11+10+9+8=50，则M66在50+1=51个上，下标为50

5.

 

6.

 a[k]-->k=2i+j-2;   30*2+30-2 下标0开始所以-1最后为87

7.

 8.

 

9.

 10.

 11.

 

编程题：

1. 共享后缀的列表
2. 两个有序列表序列的交集
3. 最长连续递增子序列
4. 求链式线性表的倒数第K项
5. 链表逆置
6. 数组循环左移
7. 在一个数组中实现两个堆栈
8. 合并两个链表，区间删除
9. 链表拼接

注释：因为题目是随机出的，这是不同套题的总结 ，实际题目数量以实际为准。