Question

1. 设有一个空栈，现在有输入序列1、2、3、4、5，经过push,push,pop,push,p

1. 设有一个空栈，现在有输入序列1、2、3、4、5，经过push,push,pop,push,pop,push,push，pop,pop,pop后，输出序列是_________.
(7.0 分)
a 1、2、3、4、5
b 2、3、5、4、1
c 5、4、3、2、1
d 1、3、4、2、5

2. 将长度为n的单链表链接在长度为m的单链表之后的算法的时间复杂度为（ ）
(7.0 分)
a O(1)
b O(n)
c O(m)
d O(m+n)

3. 若对有序表a、b、c、d、e、f、g、h进行折半查找，则在查找关键字a的过程中，先后进行比较的关键字依次为_______
(7.0 分)
a d、b、a
b d、c、a
c e、b、a
d e、c、a

4. 顺序查找不论在顺序线性表中还是在链式线性表中的时间复杂度为（ ）。
(7.0 分)
a O(n)
b O(n2)
c O(n1/2)
d O(1og2n)

5. 线性表若采用链式存储结构时，要求内存中的可用存储单元的地址?
(7.0 分)
a 必须连续
b 部分连续
c 一定不连续
d 可连续可不连续

6. 设有一个二维数组A[m][n]，假设A[0][0]存放位置在644(10)，A[2][2]存放位置在676(10)，每个元素占一个空间，问A[3][3](10)存放在什么位置？脚注(10)表示用10进制表示。
(7.0 分)
a 688
b 678
c 692
d 696

7. 设顺序循环队列Q[0：M-1]的头指针和尾指针分别为F和R，头指针F总是指向队头元素的前一位置，尾指针R总是指向队尾元素的当前位置，则该循环队列中的元素个数为（ ）。
(7.0 分)
a R-F
b F-R
c (R-F+M)％M
d (F-R+M)％M

8. 栈和队列的共同特点是( )。
(7.0 分)
a 只允许在端点处插入和删除元素
b 都是先进后出
c 都是先进先出
d 没有共同点

9. 在含n个顶点和e条边的无向图的邻接矩阵中,零元素的个数为( )
(7.0 分)
a e
b 2e
c n2－e
d n2－2e

10. 设一组初始记录关键字序列为(25，50，15，35，80，85，20，40，36，70)，其中含有5个长度为2的有序子表，则用归并排序的方法对该记录关键字序列进行一趟归并后的结果为（ ）。
(7.0 分)
a 15，25，35，50，20，40，80，85，36，70
b 15，25，35，50，80，20，85，40，70，36
c 15，25，35，50，80，85，20，36，40，70
d 15，25，35，50，80，20，36，40，70，85

二 判断题

1. 数据元素是数据的最小单位
(6.0 分)
a 错
b 对

2. 哈希表不需要进行比较便可以直接取得所查记录
(6.0 分)
a 错
b 对

3. 栈是限定在表尾进行插入或删除操作的线性表
(6.0 分)
a 错
b 对

4. 不论是入队列操作还是入栈操作，在顺序存储结构上都需要考虑“溢出”情况。（ ）
(6.0 分)
a 错
b 对

5. 设一棵树T可以转化成二叉树BT，则二叉树BT中一定没有右子树。（ ）
(6.0 分)
a 错
b 对

• 你的回答被采纳后将获得：
• 系统奖励15（财富值+成长值）+难题奖励30（财富值+成长值）

Answer 1

从蹩脚的题看到了蹩脚的老师；
蹩脚的老师带出学生怕要跑偏。。。

Answer 2

b a a...
这样也忒没有意思