福建师范大学2021年8月课程考试《数据结构概论》作业考核试题【带参考答案部分】

二、填空题（每小题2分，共30分）

1. 下面程序段的时间复杂度为_O(n)_______。

       sum=1; for(i=0;sum<n;i++) sum+=1;

2. 设数组a[M](M为最大空间个数)作为循环队列Q的存储空间，front为队头指针(指向第一个存放数据的位置)，rear为队尾指针(指向最后一个存放数据位置的下一个)，则判定Q队列的队满条件是____front == (rear + 1) % M_________。

3. 若已知一棵二叉树的前序序列是BEFCGDH，中序序列是FEBGCHD，则它的后序序列必是___FEGHDCB_____。

4. 散列法存储的基本思想是由_____关键码的值__________决定数据的存储地址。

5.  在一棵度为3的树中，度为2的结点个数是1，度为0的结点个数是6，则度为3的结点个数是__2______。

6. 设一棵完全二叉树有700个结点，则共有_______350_____个叶子结点 。

7. n个顶点e条边的图采用邻接矩阵存储，深度优先遍历算法的时间复杂度为__O（n*n）_____________；若采用邻接表存储时，该算法的时间复杂度为____O(n+e)__________ 。

8. 在堆排序和快速排序中，若初始记录接近正序或反序，则选用____堆排序__________；若初始记录基本无序，则最好选用_______快速排序________。

9. 若要求一个稀疏图G的最小生成树，最好用____克鲁斯卡尔___________ 算法来求解。

10. 一棵深度为6的满二叉树有 ________31________ 个分支结点和___32_________个叶子。

11.用5个权值{3, 2, 4, 5, 1}构造的哈夫曼（Huffman）树的带权路径长度是______33____。

12. 有向图G用邻接矩阵存储，其第i行的所有元素之和等于顶点i的_ 出度__________。

三、解答题(每小题9分，共27分)

1. 已知以下的有向图，用Dijkstra算法求出从顶点1出发到各顶点的最短路径（按步给分）。

1 到各结点的长度

       2   3   4    5   

 第一轮    10  ∞  ∞  ∞      添加路径 1->2

 第二轮    10  ∞  ∞  13      添加路径 1->2->5

 第三轮    10  ∞  15  13      添加路径 1->2->4

第四轮   10 17   15  13      添加路径 1->2->4->3

2.待排序的序列为：25,47,36,21,90,84,62,78,15,32。写出用（大根）堆排序的每一趟的结果。

答：

构建最大堆

25 47 36 21 90 84 62 78 15 32

25 47 36 78 90 84 62 21 15 32

25 47 84 78 90 36 62 21 15 32

25 90 84 78 47 36 62 21 15 32

90 78 84 25 47 36 62 21 15 32

排序调整

84 78 62 25 47 36 32 21 15 90

78 47 62 25 15 36 32 21 84 90

62 47 36 25 15 21 32 78 84 90

47 32 36 25 15 21 62 78 84 90

36 32 21 25 15 47 62 78 84 90

32 25 21 15 36 47 62 78 84 90

25 15 21 32 36 47 62 78 84 90

21 15 25 32 36 47 62 78 84 90

15 21 25 32 36 47 62 78 84 90

3.一棵度为2的有序树与一棵二叉树有何区别？

答：度为2的树要求每个节点最多只能有两棵子树，并且至少有一个节点有两棵子树。二叉树的要求是度不超过2，节点最多有两个叉，可以是1或者0。在任意一棵二叉树中，度为0的结点（即叶子结点）总是比度为2的结点多一个。

  度为2的树有两个分支，但分支没有左右之分；一棵二叉树也有两个分支，但有左右之分，左右子树的次序不能随意颠倒。

   度为2的树从形式上看与二叉树很相似，但它的子树是无序的，而二叉树是有序的。即，在一般树中若某结点只有一个孩子，就无需区分其左右次序，而在二叉树中即使是一个孩子也有左右之分。

四、程序设计题（共13分）

 1、已知r[]为一维数组，其中r[0]到r[n-1]为待排序的n个元素，排序好的元素仍放在r[0]到r[n-1]中，请写出对该数组进行非递归的直接插入排序算法，取名为insertsort(elemtype r[],int n)。

elemtype[] insertsort(elemtype r[], int n) {

        for (int i = 1; i < n; i++) {

            elemtype val = r[i];

            int j;

            for (j = i - 1; j >= 0; j--) {

                if (val >= r[j]) {

                    break;

                }else {

                    r[j+1] = r[j];

                }

            }

            r[j+1] = val;

        }

        return r;

    }