数据结构试卷

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

2、Uàfront= =mo B. QUàrear-QUàfront-1= =mo C. QUàfront= =QUàrear D. QUàfront= =QUàrear+16.在循环双链表的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

3、 à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=S7.在一个单链表中，已知q所指结点是P所指结点的前驱结点，若在q和P之间插入S结点，则执行。 A.S ànext=P ànext;P ànext=S; B.P

4、 à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

5、.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. 非

6、空的循环单链表head的尾结点（由p所指向），满足条件 。9. 在栈顶指针为HS的链表中，计算该链栈中结点个数的函数是 。10. 已知一个图的邻接矩阵表示，计算第三个结点的入度的方法是 。得分评分人三、简答题(35分)1试比较链式存储结构和顺序存储结构的优缺点：2设如图所示的逻辑结构图示，给出它的逻辑结构： 3对于一个栈，给出输入项A,B,C，如果输入项序列由A,B,C所组成，试写出全部可能的输出序列。4.由如图所示的二叉树,回答以下问题: (1) 其中序遍历序列 （2）其前序遍历序列 （3）其后序遍历序列 （4）该二叉树的中序线索二叉树 （5）该二叉树的后序线索二叉树 （6）该二叉树对应的森林 5.一棵二叉树的结点数据采用顺序存储结构,存储于数组t中,如图所示,则该二叉树的链接表示形式Eafdgcjihb1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 图得分评分人五、程序设计(20分)1.已知一个顺序表L，其中的元素按值非递减有序排