数据结构试卷.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.abcde4.栈的特点是，队列的特点是。A.先进先出 B.先进后出5.判定一个队列QU（最多元素为mo)为空的条件是。 A.QUrear-QUfront= =mo B。 QUrear-QUfront1= =mo C. QUfront= =QUrear D. QUfront= =QUrear+16。在循环双链表的P所指结点之后插入S所指结点的操作是。 A。Pright=S；Sleft=P;Prightleft=S；S right=Pright B.Pright=S;Pright left=S；Sleft=P；Sright=Pright C。Sleft=P；Sright=Pright；Pright=S;Pright left=S D。Sleft=P;Sright=Pright；Pright left=S；Pright=S7.在一个单链表中，已知q所指结点是P所指结点的前驱结点，若在q和P之间插入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。后序 D.层次序10.深度为5的二叉树至多有个结点。 A。16 B。32 C。31 D。10 得分评分人二.填空题：（20分）1。 在一个长度为n的向量中的第i个元素（1=i=n)之前插入一个元素时，需向后移动个元素.2. 在一个长度为n的向量中删除第i个元素(1next=和pnext=的操作.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中,如图所示，则该二叉树的链接表示形式Eafdgcjihb1 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,栈指针不变.（写出算法)