3、线性表若是采用链式存储结构时，要求内存中可用存储单元的地址（A、必须是连续的C、一定是不连续的B、部分地址必须是连续的D、连续或不连续都可以）
4、在以下的叙述中，正确的是（
A、线性表的线性存储结构优于链表存储结构
学号线
B、栈的操作方式是先进先出C、二维数组是其数据元素为线性表的线性表
栏
D、队列的操作方式是先进后出
姓名
5、一个栈的入队序列是12345，则栈的不可能的输出序列是（A、54321B、43512C、45321D、12345
）；
息
6、链表不具有的特点是（）。
信订
A、可随机访问任一元素C、不必事先估计存储空间
B、插入删除不需要移动元素D、所需空间与线性表长度成正比
级班级
生
7、深度为6的二叉树至多有（）个结点。A、32B、31C、63D、64）；
考
8、带头结点的单链表head为空的判定条件是（
专业
A、headNULL
装
B、head
extNULLD、headNULL）。C、只允许在端点处插入和删除元素
C、head
exthead9、栈和队列的共同点是（A、都是先进后出D、没有共同点
B、都是先进先出
10、某算法的时间复杂度为O（
2），表明该算法的（）。
系
A、问题规模是
2
B、执行时间等于
2D、问题规模与
2成正比
C、执行时间与
2成正比
第3页共6页
f11、若线性表最常用的运算是存取第i个元素及其前驱的值，则采用（）存储方式节省时间。A、单链表B、双链表C、单循环链表D、顺序表。
12、在一个单链表中，删除p结点之后的一个结点的操作是（）。A、p
extpC、p
ext
extpB、p
ext
extp
extD、p
extp
ext
ext
13、循环队列用数组A0，m1存放其元素值，已知其头尾指针分别是fro
t和rear，则当前队列中的元素个数是（1）A、（rearfro
tm）mB、rearfro
t1C、rearfro
t1D、rearfro
t
14、在一非空二叉树的中序遍历序列中，根结点的左边（）。A、只有右子树上的所有结点C、只有左子树上的部分结点B、只有右子树上的部分结点D、只有左子树上的所有结点
15、对一个满二叉树，m个树叶，
个结点，深度为h，则（）。A、
hmB、hm2
C、
2h1D、m2h1
16、表达式abcd的后缀表达式是（）A、abcdB、abcdC、abcdD、abcd
17、在一个有向图中，所有顶点的入度之和等于所有顶点的出度之和的（）倍。A、12B、1C、2D、4
18、对线性表进行二分查找时，要求线性表必须（）。A、以顺序方式存储B、以链接方式存储C、以顺序方式存储，且结点按关键字有序排序D、以链接方式存储，且结点按关键字有序排序
四、程序填空题：（本题共2小题，每题6分，共12分）
1、下面程序的功能r