福建师范大学网络与继续教育学院 《数据结构概论》期末考试A卷（闭卷）

李老师

福建师范大学网络与继续教育学院
《数据结构概论》期末考试A卷（闭卷）

@
姓名：        
专业：
学号：         
学习中心：


一、        选择：(答案写在相应框格内，每题2分，共30分)
题目        1        2        3        4        5        6        7        8        9        10        11        12        13        14        15
答案                                                                                                                       
1、非空循环链表head 的尾结点 p 满足下列(       )条件。
A. head->next==p                  B. head==p                 
C. p->next==head                  D. p->next==nil
2、设栈s的类型为sqstack ，判定栈空的条件是(      )。
A. s = =nil       B. s->top= =0   
C. s.top = =0     D. s.top = = nil
3、具有4个顶点的无向完全图有(      )边。
A. 20         B. 12            C.6           D.8
4、一个向量的第一个元素的地址是100，每个元素的长度是2 ，则第五个元素的地址是(     )。
A. 102                   B. 110                   C. 108                           D. 120
5、一个栈的输入序列是a,b,c,d,e ，则不可能输出是(     )。
A. ecdab                   B. cdeba                  
C. decba                         D. abcde
6、已知二叉树的前、中根序列分别是abdefcg 和 defbagc，则该二叉树的后根遍历序列是(   )。
A. defbgca                                   B. fedbgca                  
C. abcdefg                            D. gfedcba
7、深度为4 的二叉树至多有个(    )结点。
A.12            B.13            C.14               D.15
8、具有6个顶点的无向图至少要有(    )条边才能确保是一个连通图。
A.4     B.5      C.6      D.7
9、已知一个顺序存储的线性表,设每个结点需占m个存储单元,若第一个结点的地址为da1,则第i个结点的地址为()
A.da1+(i-1)*m     B.da1+i*m      
C.da1-i*m         D.da1+(i+1)*m
10、在n个结点的顺序表中,算法的时间复杂度是O(1)的操作是:
A.访问第i个结点(1<=i<=n)和求第i个结点的直接前趋(2<=i<=n)
B.在第i个结点后插入一个新的结点(1<=i<=n)
C.删除第i个结点(1<=i<=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.2h                            B.2h-1                     C.2h+1                            D.h+1
15、若进栈序列为a,b,c，则通过入出栈操作可能得到的a,b,c的不同排列个数为：(  )
A.4          B.5            C.6             D.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>=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(LinkList L,ListNode *p)
{//L是有头结点的单链表
ListNode *q=L->next;
while(q&&q->next!=p)
   q=q->next;
if(q) return q;
else Error("*p is not in L");
}












void Demo2(ListNode *p,ListNode *q)
{//*p,*q是某个链表中的两个结点
DataType temp;
temp=p->data;
p->data=q->data;
q->data=temp;
}



























2、        设栈S=(1,2,3,4,5,6,7) ，其中7为栈顶元素。
(1)        简述函数f31中第一个循环语句的功能；
(2)        写出调用f31(&s)后的s。

Void f31(stack *s)
{ queue q;  stack t;   int i=0;
Initqueue(&q);    initstack(&s);
while(!stackempty(s))
    if((i=!i)!=0) push(&T,pop(S));
    else enqueue(&q,pop(s));
while (!stackempty(t))  push(s,pop(T));
while(!queueempty(&q))  push(s,dequeue(&q));
}