数据结构试卷.doc

数据结构期末试卷
（适用计算机应用专业)
一
二
三
总分

得分
评分人

一。选择题（30分）
1.计算机算法指的是＿＿＿
A.计算方法 B。排序方法
C。解决问题的有限运算序列 D。调度方法
2线性表若采用链式存储结构时,要求内存中可用存储单元的地址＿＿＿。
A.必须是连续的 B。部分地址必须是连续的
C。一定是不连续的 D。连续不连续都可以
3.一个栈的入栈序列是a、b、c、d、e，则栈的不可能的输出序列是＿＿＿。
A.edcba B.decba C。dceab D.abcde
4.栈的特点是＿＿，队列的特点是＿＿。
A.先进先出 B.先进后出
5.判定一个队列QU（最多元素为mo)为空的条件是＿＿＿。
A.QUàrear-QUàfront= =mo B。 QUàrear-QUàfront—1= =mo
C. QUàfront= =QUàrear D. QUàfront= =QUàrear+1
6。在循环双链表的P所指结点之后插入S所指结点的操作是＿＿＿。
A。Pàright=S；Sàleft=P;Pàrightàleft=S；S àright=Pàright
B.Pàright=S;Pàrightà left=S；Sàleft=P；Sàright=Pàright
C。Sàleft=P；Sàright=Pàright；Pàright=S;Pàrightà left=S
D。Sàleft=P;Sàright=Pàright；Pàrightà left=S；Pàright=S
7.在一个单链表中，已知q所指结点是P所指结点的前驱结点，若在q和P之间插入S结点，则执行＿＿＿。
A。Sànext=Pànext；Pànext=S； B.Pànext=Sànext；Sànext=P；
C.qànext=S;Sànext=P; D.Pànext=S;Sànext=P；
8。在线索化二叉树中,t所指结点没有左子树的充要条件是＿＿＿。
A。tàleft==NULLB。tàltag==1C.tàltag==1且tàleft==NULLD.以上都不对
9.如果T2是由有序树T转换而来的二叉树，那么T中结点的前序就是T2中结点的＿＿＿。
A。前序 B.中序 C。后序 D.层次序
10.深度为5的二叉树至多有＿＿＿个结点。
A。16 B。32 C。31 D。10
得分
评分人

二.填空题：（20分）
1。 在一个长度为n的向量中的第i个元素（1<=i<=n)之前插入一个元素时，需向后移动个元素.
2. 在一个长度为n的向量中删除第i个元素(1<=i〈=n）时，需向前动
个元素。
3。 向栈中压入元素的操作是。
4。 一个栈的输入序列是1 2 3 4 5，则栈的输出序列4 3 5 1 2是。
5。 在双链表中,每个结点有两个指针域，一个指向,另一个指向.
6。 带有一个头结点的单链表head为空的条件是。
7。 在一个单链表中p所指结点之后插入一个s所指结点时，应执行s->next=和p—>next=的操作.
8。 非空的循环单链表head的尾结点(由p所指向），满足条件.
9. 在栈顶指针为HS的链表中,计算该链栈中结点个数的函数是。
10。已知一个图的邻接矩阵表示，计算第三个结点的入度的方法是。
得分
评分人

三、简答题（35分）
1．试比较链式存储结构和顺序存储结构的优缺点：
2．设如图所示的逻辑结构图示,给出它的逻辑结构：

3．对于一个栈,给出输入项A，B，C,如果输入项序列由A，B,C所组成，试写出全部可能的输出序列。
4.由如图所示的二叉树，回答以下问题:
(1） 其中序遍历序列
（2）其前序遍历序列
（3）其后序遍历序列
(4）该二叉树的中序线索二叉树
（5）该二叉树的后序线索二叉树
（6）该二叉树对应的森林

5。一棵二叉树的结点数据采用顺序存储结构，存储于数组t中,如图所示，则该二叉树的链接表示形式
E
a
f

d

g

c
j

i
h

b
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21
图
4

得分
评分人

五、程序设计（20分）
1。已知一个顺序表L，其中的元素按值非递减有序排列，设计一个算法插入一个元素x后保持该顺序表仍然按递减有序排列.
2。设计一个算法从顺序表L中删除所有值为x的元素
3.取栈顶元素gettop(st,x）
将栈st的栈顶元素赋给x,栈指针不变.（写出算法)