数据结构试卷

PAGEPAGE1数据结构期末试卷（适用计算机应用专业)一二三总分得分评分人一。选择题（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àrear-QUàfront==moB。QUàrear-QUàfront—1==moC.QUàfront==QUàrearD.QUàfront==QUàrear+16。在循环双链表的P所指结点之后插入S所指结点的操作是＿＿＿。A。Pàright=S；Sàleft=P;Pàrightàleft=S；Sàright=PàrightB.Pàright=S;Pàrightàleft=S；Sàleft=P；Sàright=PàrightC。Sàleft=P；Sàright=Pàright；Pàright=S;Pàrightàleft=SD。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à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。16B。32C。31D。10得分评分人二.填空题：（20分）1。在一个长度为n的向量中的第i个元素（1<=i<=n)之前插入一个元素时，需向后移动个元素.2.在一个长度为n的向量中删除第i个元素(1<=i〈=n）时，需向前动个元素。3。向栈中压入元素的操作是。4。一个栈的输入序列是12345，则栈的输出序列43512是。5。在双链表中,每个结点有两个指针域，一个指向,另一个指向.6。带有一个头结点的单链表head为空的条件是。7。在一个单链表中p所指结点之后插入一个s所指结点时，应执行s->next=和p—>next=的操作.8。非空的循环单链表head的尾结点(由p所指向），满足条件.9.在栈顶指针为HS的链表中,计算该链栈中结点个数的函数是。10。已知一个图的邻接矩阵表示，计算第三个结点的入度的方法是。得分评分人三、简答题（35分）1．试比较链式存储结构和顺序存储结构的优缺点：2．设如图所示的逻辑结构图示,给出它的逻辑结构：eq\o\ac（○,A1)eq\o\ac（○,A2）eq\o\ac(○，A3）eq\o\ac(○，A6）eq\o\ac（○,A4）eq\o\ac（○，A8)eq\o\ac(○，A7)eq\o\ac（○，A5）eq\o\ac（○,A9）3．对于一个栈,给出输入项A，B，C,如果输入项序列由A，B,C所组成，试写出全部可能的输出序列。4.由如图所示的二叉树，回答以下问题:eq\o\ac(○，a)(1）其中序遍历序列（2）其前序遍历序列eq\o\ac（○,b)eq\o\ac(○,c)（3）其后序遍历序列(4）该二叉树的中序线索二叉树eq\o\ac(○,d）eq\o\ac(○,e）eq\o\ac（○,f）（5）该二叉树的后序线索二叉树（6）该二叉树对应的森林eq\o\ac（○，g)eq\o\ac(○,h）eq\o\ac（○，i）5。一棵二叉树的结点数据采用顺序存储结构，存储于数组t中,如图所示，则该二叉树的链接表示形式Eafdgcjihb123456789101112131415161718192021图得分评分人五、程序设计（20分）1。已知一个顺序表L，其