08期中考试试卷
无烟日黑板报-四川音乐学院绵阳艺术学院
数据结构期中测试
一、选择题（共24分）
1. 数据结构中，与所使用的计算机无关的是数据的 结构。
[A] 存储 [B] 物理 [C] 逻辑 [D] 逻辑和存储
2. 二维数组A[0..9, 0..10]
采用行优先的存储方法，若每个元素各占3个存储单元且A[0,0]
的地
址为200，则A[6,9] 的地址为_________。
[A] 422
[B] 425 [C] 428 [D] 431
3.
在线性表的下列基本运算中，只有 不是加工型运算。
[A] 定位
[B] 排序 [C] 插入 [D] 删除
4.
若某线性表最常用的操作是取第i个元素和找第i个元素的直接前驱元素，则采用
存储
方式最节省运算时间。
[A] 顺序表 [B] 单链表
[C] 双链表 [D] 单循环链表
5.
已知单链表A长度为m，单链表B长度为n，若将B联接在A的末尾，其时间复杂度为 。
[A] O(1) [B] O(m) [C] O(n)
[D] O(m+n)
6. 利用双向链表作线性表的存储结构的优点是:
[A] 便于进行插入和删除的操作 [B] 提高按关系查找数据元素的速度
[C]
节省空间 [D] 便于销毁结构释放空间
7.
若编号为1,2,3,4,5,6的六节车厢依次通过一段栈形轨道，则在出口处不可能得到____的次序。
[A] 143562 [B] 456321 [C] 145326
[D] 426531
8. 设 n 是正整数, 则在下列程序段中, 语句 * 的执行次数是
[A] log
2
n [B]
log
2
n -1
[C] log
2
n + 1
[D] log
2
n
j:=1;
WHILE (j <= n)
* j:=j*2;
9.
在计算递归函数时，若不用递归则应借助数据结构
[A] 数组 [B]
队列 [C] 链表 [D] 栈
10. 若用数组A[0..m-1]
存放循环队列的元素值，头、尾指针分别为front和rear，则当前元素个
数为_______。
[A] rear-front+1 [B] (rear-
front+1) MOD m
[C] (rear-front+m) MOD m
[D] (rear-front) MOD m
11.
在任意一棵二叉树的前序序列和后序序列中，各叶子之间的相对次序关系 ( )
A．不一定相同 B．都相同 C．都不相同 D．互为逆序
12. 对广义表L＝（（a，b），c，（d，（e）））执行tail(tail(L))的结果是
（ ）
A．（d，（e））
B．（c，（d，（e）））
C．（（d，（e）））
D．（）
二、填空题（总共20分）
1. 构成抽象数据类型的三个要素为： 、 和
。
2．算法独立于具体的 ，与具体的程序设计语言 。
3. 称算法的时间复杂度为O(f(n))，它的含义是，算法执行时间的
和
相同。
4. 数据的存储结构是
的映象，其顺序映象的特点是借助 ；链
式映象的特点是借助
。
5.
假设带头结点的单循环链表中头指针L指向链表中最后一个结点，则在第一个结点之前插入指针
s
所指结点的语句组是 。
6.
n
阶对称矩阵A的下三角部分以列为主存储在一维数组A[n(n+1)2
]中，若n=5，则矩阵元素a
53
在S中的下标是 。
7.
若一个栈的输入序列是1,2,n，输出序列的第一个元素是n，则第i个输出元素是 。
8. 设字符串S='abbbabbc', T='bb',
R='b'，则置换操作REPLACE(S,T,R) 的执行结果是
S =
。
9. 已知单链表中指针p所指结点有后继结点，则判别该结点只有一个后继结点的条件
是
。
10. 已知字符串A='IBM computer'，B='com'，求长函数LENGTH
（A）的值为12，则定位函
数INDEX（A, B, 2）的值是 。
三、（10分）
已知一棵二叉树的前序遍历的结果是ABECDFGHIJ,
中序遍历的结果是
EBCDAFHIGJ,
试画出这棵二叉树，并给出这棵二叉树的后序遍历序列。
四、(10分)（用图形）阅读下列算法，举例说明该算法的功能。
void
ss( LinkList ha ) {
ha 为指向带头结点的单链表的头指针
LinkList p,q,s,min;
p = ha;
while (p->next) {
min = p; q =
p->next;
while ( q->next ) {
if (q->next->data < min->next->data) min = q;
q = q->next;
}while
if (min != p) {
s = min->next;
min->next = s->next; s->next = p->next;
p->next = s; p = p->next;
}if
}while
}ss
五.
（12分）已知二叉树的存储结构为二叉链表，类型定义如下：
typedef
struct node{
char data;
struct
node *lchild,*rchild;
}BinTNode,*BinTree;
阅读下列算法suanfa2，并回答问题：
void suanfa2(BinTree
T){
if (T){
A
suanfa2(T->lchild);
B
C
suanfa2(t->rchild);
D
If((!T->lchild) && T->rchild){
F
E
T->lchild=t->rchild;
T->rchild=NULL}
G
}
}
（1）
已知如图所示的二叉树以T为指向根结点的指针，画出执行suanfa2（T）的
二叉树；
（2） 简述算法suanfa2的功能；（10分）
六
、(12分)已知两个有序表 A 和 B ,都以带头结点的单链表作存储结构, ha 和 hb
分
别是它们的头指针, 编写算法判别表 A 中的元素是否都包含在表 B 中 。
例如, 若表 A = (2,3,9), 表 B =(1,2,3,4,5,7,9),
则返回'TRUE';
若表 A = (2,5,8), 表 B
=(1,2,3,4,5,7,9), 则返回'FALSE'。
链表的类型说明为
typedef struct LNode {
ElemType data;
Struct LNode *next;
}Lnode, *LinkList;
六、(12分) 假设以行逻辑链接
的顺序表表示稀疏矩阵，编写算法以行序为主序的次
序(每一行按列序有序)输入稀疏矩阵的非零元(行
下标、列下标、非零元的值)，建立该
稀疏矩阵的行逻辑链接的顺序表存储结构。