《数据结构概论》1、非空循环链表head的尾结点p满足下列()...

奥鹏网院作业

福建师范大学17年2月《数据结构概论》作业考核试题答案

作业答案及论文写作，请联系QQ515224986
福建师范大学网络与继续教育学院
《数据结构概论》期末考试A卷（闭卷）
姓名：
专业：
学号：
学习中心：

一、选择：(答案写在相应框格内，每题2分，共30分)

1、非空循环链表head的尾结点p满足下列()条件。
A.head&gtnext==pB.head==p
C.p&gtnext==headD.p&gtnext==nil
2、设栈s的类型为sqstack，判定栈空的条件是()。
A.s==nilB.s&gttop==0
C.s.top==0D.s.top==nil
3、具有4个顶点的无向完全图有()边。
A.20B.12C.6D.8
4、一个向量的第一个元素的地址是100，每个元素的长度是2，则第五个元素的地址是()。
A.102B.110C.108D.120
5、一个栈的输入序列是a,b,c,d,e，则不可能输出是()。
A.ecdabB.cdeba
C.decbaD.abcde
奥鹏易百网
6、已知二叉树的前、中根序列分别是abdefcg和defbagc，则该二叉树的后根遍历序列是()。
A.defbgcaB.fedbgca
C.abcdefgD.gfedcba
7、深度为4的二叉树至多有个()结点。
A.12B.13C.14D.15
8、具有6个顶点的无向图至少要有()条边才能确保是一个连通图。
A.4B.5C.6D.7
9、已知一个顺序存储的线性表,设每个结点需占m个存储单元,若第一个结点的地址为da1,则第i个结点的地址为()
A.da1+(i1)*mB.da1+i*m
C.da1i*mD.da1+(i+1)*m
10、在n个结点的顺序表中,算法的时间复杂度是O(1)的操作是
A.访问第i个结点(1&lt=i&lt=n)和求第i个结点的直接前趋(2&lt=i&lt=n)
B.在第i个结点后插入一个新的结点(1&lt=i&lt=n)
C.删除第i个结点(1&lt=i&lt=n)D.将n个结点从小到大排序.
11、用邻接表表示图进行深度优先遍历时,通常采用()来实现算法.
A.栈B.队列C.树D.图
12、非线性结构中,每个结点()
A.无直接前趋.B.只有一个直接前驱和后继
C.只有一个直接前驱和个数不受限制的直接后继
D.有个数不受限制的直接前驱和后继.
13、在最好和最坏情况下的时间复杂度均为O(n*logn)且稳定的排序方法是：
A.快速排序B.堆排序C.归并排序D.基数排序
14、设高度为h的二叉树中只有度为0，2的结点，则该二叉树至少有()个结点。
A.2hB.2h1C.2h+1D.h+1
15、若进栈序列为a,b,c，则通过入出栈操作可能得到的a,b,c的不同排列个数为：()
A.4B.5C.6D.7
二、（）：(每空2分，共20分)
1、在n个结点的顺序表中,删除一个结点需平均移动_______个结点,具体的移动次数取决于____________.
2、在循环链表中,可根据在一结点的地址遍历整个链表,而单链表中需要知道_________才能遍历整个链表。
3、在栈中存取数据的原则是：____________.
4、在栈结构中，允许插入，删除的一端称为______，另一端称为_________。
5、顺序表相对于链表的优点有_______和_________.
6、某二叉树的前序和后序正好相反，则该二叉树一定是__________二叉树。
7、将一棵有100个结点的完全二叉树从上到下，从左到右依次对结点进行编号，根结点的编号为1，则编号为49的结点的孩子编号为：_________
三、解答题：(每题6分，共30分)
1、设长度为n的链队列用单循环链表表示，若只设头指针，则入队，出队操作的时间是什么？如果只设尾指针呢？






2、若一组记录的关键码为(46,79,56,38,40,84),则利用快速排序的方法,分别写出以第一个记录为基准得到的前三次划分结果。





3、在具有n个结点的K（k&gt=2)叉树的K叉链表表示中，有多少个空指针。



4、已知一棵二叉树的前序序列和中序序列分别为abdghcefi和gdhbaecif,请画出该二叉树。



5、无向图G有6个结点和9条边,并依次输入这9条边为(0,1),(0,2),(0,4),(0,5),(1,2),(2,3),(2,4),(3,4),(4,5),试从顶点0出发,分别写出按深度优先搜索法和广度优先搜索法进行遍历的结点序列。





四、算法题：(每题10分，共20分)
1、下述两个算法的功能是什么?
ListNode*Demo1(LinkListL,ListNode*p)
{//L是有头结点的单链表
ListNode*q=L&gtnext
while(q&amp&ampq&gtnext!=p)
q=q&gtnext
if(q)returnq
elseError(&quot*pisnotinL&quot)
}






voidDemo2(ListNode*p,ListNode*q)
{//*p,*q是某个链表中的两个结点
DataTypetemp
temp=p&gtdata
p&gtdata=q&gtdata
q&gtdata=temp
}













福建师范大学网络与继续教育学院
《数据结构概论》期末考试A卷（闭卷）
&#615051
姓名：
专业：
学号：
学习中心：
2、设栈S=(1,2,3,4,5,6,7)，其中7为栈顶元素。
(1)简述函数f31中第一个循环语句的功能；
(2)写出调用f31(&amps)后的s。
Voidf31(stack*s)
{queueqstacktinti=0
Initqueue(&ampq)initstack(&amps)
while(!stackempty(s))
if((i=!i)!=0)push(&ampT,pop(S))
elseenqueue(&ampq,pop(s))
while(!stackempty(t))push(s,pop(T))
while(!queueempty(&ampq))push(s,dequeue(&ampq))
}







































更多学习资料请进www.openhelp100.com