《数据结构概论》期末试卷 一、单项选择题 (请将答案填写在本大题后面的表格中，每小题2分，共30分) 1.查找n个元素的有序表时，最有效的查找方法是( ) A.顺序查找 B.分块查找 C.折半查找 D.二叉
![福建师范大学2021年8月课程考试《数据结构概论》作业考核试题[答案]](/uploads/allimg/240109/4682e5ce9899d2fce86deaddcac55c54.jpg)
福建师范大学2021年8月课程考试《数据结构概论》作业考核试题[答案]满分答案
《数据结构概论》期末试卷
一、单项选择题 (请将答案填写在本大题后面的表格中，每小题2分，共30分)
1.查找n个元素的有序表时，最有效的查找方法是( )
A.顺序查找 B.分块查找
C.折半查找 D.二叉排序树查找
2.具有12个关键字的有序表，查找成功时折半查找的平均查找长度是( )
A.3.1 B.4 C.2.5 D.5
3.在具有n个结点的有序单链表中插入一个新结点并使链表仍然有序的时间复杂度是( )
A.O(1) B.O(n)
C.O(nlogn) D.O(n2)
4.对平均性能而言，以下最好的内排序方法是( )。
A.冒泡排序 B.希尔排序
C.交换排序 D.快速排序
5.链栈与顺序栈相比，比较明显的优点是( )
A.插入操作更加方便 B.删除操作更加方便
C.不会出现下溢的情况 D.不会出现上溢的情况
6.二叉树中第5层上的结点个数最多为( )
A.8 B.15
C.16 D.32
7.以下数据结构中，( )是非线性数据结构。
A.树 B.字符串
C.队 D.栈
8.一个向量的第一个元素的地址是100，每个元素的长度是2 ，则第五个元素的地址是( )。
A.102 B.110
C.108 D.120
9.已知图的邻接表如下所示，根据算法，则从顶点0出发按广度优先遍历的结点序列是( )
A. 0 3 2 1 B. 0 1 2 3
C. 0 1 3 2 D.0 3 1 2
（第9题配图：数组的下标为0,1,2,3）
10.对于哈希函数H(key)=key%13,被称为同义词的关键字是( )
A.35和41 B.23和39
C.15和44 D.25和51
11.有一个有序表为{ 1，3，9，12，32，41，45，62，77，88，92，100}，用折半查找法，若要找63，要经过( )次与63比较。
A.12 B.6
C.4 D.5
12.下述几种排序方法中，稳定的排序算法是( )
A.直接插入排序 B.快速排序
C.堆排序 D.希尔排序
13.具有n个顶点的无向图至少要有( )条边才能确保是一个连通图。
A.n(n+1) B.n-1
C.n+1 D.n(n-1)
14.二叉树是非线性数据结构，所以 ( )
A.它不能用顺序存储结构存储 B.它不能用链式存储结构存储
C.顺序存储结构和链式存储结构都能存储 D.顺序存储结构和链式存储结构都不能使用
15.有8个结点的无向图最多有( )条边。
A.14 B.28
C.56 D.112
单项选择题答题表格（请将答案填写在下表中）
1 2 3 4 5 6 7 8 9 10
11 12 13 14 15
二、填空题（每小题2分，共30分）
1. 下面程序段的时间复杂度为________。
sum=1; for(i=0;sum<n;i++) sum+=1;
2. 设数组a[M](M为最大空间个数)作为循环队列Q的存储空间，front为队头指针(指向第一个存放数据的位置)，rear为队尾指针(指向最后一个存放数据位置的下一个)，则判定Q队列的队满条件是_____________。
3. 若已知一棵二叉树的前序序列是BEFCGDH，中序序列是FEBGCHD，则它的后序序列必是________。
4. 散列法存储的基本思想是由_______________决定数据的存储地址。
5. 在一棵度为3的树中，度为2的结点个数是1，度为0的结点个数是6，则度为3的结点个数是________。
6. 设一棵完全二叉树有700个结点，则共有____________个叶子结点 。
7. n个顶点e条边的图采用邻接矩阵存储，深度优先遍历算法的时间复杂度为_______________；若采用邻接表存储时，该算法的时间复杂度为______________ 。
8. 在堆排序和快速排序中，若初始记录接近正序或反序，则选用______________；若初始记录基本无序，则最好选用_______________。
9. 若要求一个稀疏图G的最小生成树，最好用_______________ 算法来求解。
10. 一棵深度为6的满二叉树有 ________________ 个分支结点和____________个叶子。
11.用5个权值{3, 2, 4, 5, 1}构造的哈夫曼（Huffman）树的带权路径长度是__________。
12. 有向图G用邻接矩阵存储，其第i行的所有元素之和等于顶点i的____________。
三、解答题(每小题9分，共27分)
1. 已知以下的有向图，用Dijkstra算法求出从顶点1出发到各顶点的最短路径（按步给分）。
2.待排序的序列为：25,47,36,21,90,84,62,78,15,32。写出用（大根）堆排序的每一趟的结果。
3.一棵度为2的有序树与一棵二叉树有何区别？
四、程序设计题（共13分）
1、已知r[]为一维数组，其中r[0]到r[n-1]为待排序的n个元素，排序好的元素仍放在r[0]到r[n-1]中，请写出对该数组进行非递归的直接插入排序算法，取名为insertsort(elemtype r[],int n)。
福建师范大学2021年8月课程考试《数据结构概论》作业考核试题[答案]历年参考题目如下：
《数据结构概论》期末考试
一、 选择：(答案写在相应框格内，每题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个结点后插入一个ABC结点(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));
}
