[奥鹏]福建师范大学2022年8月课程考试《数据结构概论》作业考核试题[正确答案]

福建师范大学2022年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)。
  

福建师范大学2022年8月课程考试《数据结构概论》作业考核试题[正确答案]奥鹏资讯分享：

[奥鹏]福建师范大学2022年8月课程考试《数据结构概论》作业考核试题[正确答案]相关练习题：
施工高度为角点设计地面标高与自然标高之差。（ ）

7．低压断路器成功率验证试验供抽样的产品数量可以小于试品数n的10倍。（   ）

单片机也称为( )。

内墙抹灰的厚度一般为（  ）

地下水是一种很活跃的地质营力。

最高限价也称限制价格,是政府所规定的某种商品的最高价格。限制价格低于均衡价格。()

下列关于我国社会主义法律的本质特征的表述错误的是（ ）。

下列各项不在资产负债表中反映的是（ ）

米德认为青春期的困难和危机乃是（ ）的产物。

根据计划内容的明确性标准，可以将计划分为（ ）。

劳动的主动性和有偿性，是劳动者所从事的劳动的两大主要特点。

（ ）是通过压缩计算工期，以达到要求工期目标或在约束条件下使工期最短的过程。

构造句型的语法树时，要从树的根结点出发，逐步向下构造，而不能从句型出发向上构造。

五言平起仄收式尾联出句的平仄应该是

18秋学期（1709、1803、1809）《细胞生物学》在线作业-0002

经济法的调整对象的范围包括（）

由于存储策略是使（）最小的经济原则来确定订货批量，故称该订货批量为经济订货批量

民主党派的民主监督在本质上是（ ）的一种具体体现方式。

下列软件中属于应用软件的是（）

关于常用制药用水的错误表述是