考
生
信
息
栏
精品文档
系学号
订
专业
级班线级
厦门理工学院试卷
2012－2013学年第一学期
课程名称
数据结构与算法
专业2011级班级
试卷A■卷别B□□
考试闭卷■方式开卷□
本试卷共四大题4页，满分100分，考试时间120分钟。请在答题纸上作答，在试卷上作答无效。
装姓名
精品文档
f精品文档
一、选择题：（本题共20小题，每题2分，共40分）
1、链式存储的存储结构所占存储空间（）。
A．分两部分，一部分存放结点的值，另一部分存放表示结点间关系的指针
B．只有一部分，存放结点的值
C．只有一部分，存储表示结点间关系的指针
D．分两部分，一部分存放结点的值，另一部分存放结点所占单元素
2、已知一个顺序存储的线性表，设每个结点占m个存储单元，若第一个结点的地址为B，则第i个结点的地址为（）。
A．Bi1m
B．Bim
C．BimD．Bi1m
3、两个指针P和Q，分别指向单链表的两个元素，P所指元素是Q所指元素前驱的条件是（）。
A．P
extQ
extB．P
extQC．Q
extP
D．PQ
4、下面关于线性表的叙述中，错误的是（）关系。
A．顺序表必须占一片地址连续的存储单元
B．顺序表可以随机存取任一元素
C．链表不必占用一片地址连续的存储单元
D．链表可以随机存取任一元素
5、等概率情况下，在有
个结点的顺序表上做插入结点运算，需平均移动结点的数目为（）。
A．

B．
12
C．
2
D．
12
6、设数组datam作为循环队列SQ的存储空间，fro
t为队头指针，rear为队尾指针，则执行出队操作后其头指针fro
t值为（）。
A．fro
tfro
t1
B．fro
tfro
t1m1
C．fro
tfro
t1m
D．fro
tfro
t1m
精品文档
f精品文档
7、下列算法的时间复杂度是（）。
fori0i
i
forj0j
j
cijij
AO（1）
BO（
）CO（log2
）DO（
2）
8、从一个栈顶指针为top的链栈中删除一个结点时，用x保存被删除的结点的值，应执行下列命令。
A．xtoptoptop
ext
B．toptop
extxtopdata
C．xtopdata
D．xtopdatatoptop
ext
9、经过下列栈的运算后，x的值是（
）。
I
itStacks（初始化栈）
Pushsa
Pushsb
ReadTops
Popsx
A．a
B．b
C．1
D．0
10、一个栈的入栈次序ABCDE，则栈的不可能的输出序列是。
A．EDCBA
B．DECBA
C．DCEAB
D．ABCDE
11、设某棵二叉树中有2000个站点，则该二叉树的最小高度为（）。
A、9
B、10C、11
D、12
12、若用一个大小为6的数组来实现循环队列，且当前fro
t和rear的值分别为3和0，当从队列中删除一个元素，再加入r