数据结构试卷

1、WORD格式数据构造期末试卷( 适用计算机应用专业 )一二三总分一. 选择题 (30 分)得分评分人1. 计算机算法指的是A. 计算方法B.排序方法C. 解决问题的有限运算序列D. 调度方法2 线性表假设采用链式存储构造时, 要求内存中可用存储单元的地址。A.必须是连续的B.局部地址必须是连续的C.一定是不连续的D.连续不连续都可以3. 一个栈的入栈序列是 a、b、c、d、e, 那么栈的不可能的输出序列是。A.edcbaB.decbaC.dceabD.abcde4. 栈的特点是 , 队列的特点是。 A. 先进先出 B. 先进后出5. 判定一个队列 QU(最多元素为 mo)为空的条件是。A.QU

2、rear-QUfront= =moB. QUrear-QUfront-1= =moC. QUfront= =QUrearD. QUfront= =QUrear+16. 在循环双链表的 P 所指结点之后插入 S 所指结点的操作是。A.Pright=S;Sleft=P;Prightleft=S;Sright=PrightB.Pright=S;Prightleft=S;Sleft =P;S right=PrightC.Sleft=P;Sright=Pright;Pright=S;Prightleft=SD.Sleft=P;Sright=Pright;Prightleft=S;Pright=S7. 在

3、一个单链表中，q 所指结点是 P 所指结点的前驱结点，假设在q 和 P专业资料整理WORD格式1专业资料整理WORD格式之间插入 S 结点，那么执行。A.Snext=Pnext;Pnext=S;B.Pnext=Snext;Snext=P;C.qnext=S;Snext=P;D.Pnext=S;Snext=P;8. 在线索化二叉树中 ,t 所指结点没有左子树的充要条件是。A.tleft=NULLB.tltag=1C.tltag=1 且 tleft=NULLD. 以上都不对9. 如果 T2 是由有序树 T 转换而来的二叉树 , 那么 T 中结点的前序就是 T2 中结点的。A. 前序B.中序C.后序

4、D.层次序10. 深度为 5 的二叉树至多有个结点。A.16B.32C.31D.10二. 填空题 :(20 分)得分评分人1. 在一个长度为 n 的向量中的第 i 个元素 1<=i<=n 之前插入一个元素时，需向后移动个元素。2. 在一个长度为 n 的向量中删除第 i 个元素 1<=i<=n时，需向前动个元素。3.向栈中压入元素的操作是。4.一个栈的输入序列是 1 2 3 4 5 ，那么栈的输出序列43512 是。5.在双链表中，每个结点有两个指针域， 一个指向，另一个指向。6.带有一个头结点的单链表head 为空的条件是。7. 在一个单链表中 p 所指结点之后插入一个

5、 s 所指结点时，应执行 s >next=和 p>next=的操作。8.非空的循环单链表 head 的尾结点由 p 所指向，满足条件。9.在栈顶指针为 HS的链表中，计算该链栈中结点个数的函数是。10.一个图的邻接矩阵表示，计算第三个结点的入度的方法是。专业资料整理WORD格式2得分评分人专业资料整理WORD格式三、简答题 (35 分)1试比较链式存储构造和顺序存储构造的优缺点：2设如下列图的逻辑构造图示，给出它的逻辑构造：A1A2A3A6A4A8A7A5A93对于一个栈，给出输入项A,B,C，如果输入项序列由A,B,C 所组成，试写出全部可能的输出序列。4. 由如下列图的二叉树 , 答复以下问题 :a(1) 其中序遍历序列2其前序遍历序列bc3其后序遍历序列4该二叉树的中序线索二叉树def5该二叉树的后序线索二叉树6该二叉树对应的森林ghi专业资料整理WORD格式3专业资料整理WORD格式5. 一棵二叉树的结点数据采用顺序存储构造 , 存储于数组 t 中, 如下列图 , 那么该二叉树的表示形式123456789101112 131415 16171819 2021Eafdgc jihb图五、程序设计 (20 分)1. 一个顺序表 L，其中的元素按值非递减有序排列，设计一个算法插入一个元素 x 后保持该顺序表仍然按递减有序排列。得分评分人2. 设计一