5.分析下列各算法的时间

中南大学现代远程教育课程考试（考试）复习题及参考答案数据结构(使用教材：余腊生编著，人民邮电出版社出版，《数据结构—基于C++模板类的实现》一、判断题1．数组是一种复杂的数据结构，数组元素之间的关系既不是线性的也不是树形的。

[ ] 2．链式存储在插人和删除时需要保持物理存储空间的顺序分配，不需要保持数据元素之间的逻辑顺序。

[ ]3．在用循环单链表表示的链式队列中，可以不设队头指针，仅在链尾设置队尾指针。

[ ] 4．通常递归的算法简单、易懂、容易编写，而且执行的效率也高。

[ ] 5．一个广义表的表尾总是一个广义表。

[ ] 6．当从一个小根堆（最小堆）中删除一个元素时，需要把堆尾元素填补到堆顶位置，然后再按条件把它逐层向下调整，直到调整到合适位置为止。

[ ] 7．对于一棵具有n个结点，其高度为h的二叉树，进行任一种次序遍历的时间复杂度为O（h）。

[ ] 8．存储图的邻接矩阵中，邻接矩阵的大小不但与图的顶点个数有关，而且与图的边数也有关。

[ ] 9．直接选择排序是一种稳定的排序方法。

[ ] 10．30、闭散列法通常比开散列法时间效率更高。

[ ] 11．有n个结点的不同的二叉树有n!棵。

[ ] 12．直接选择排序是一种不稳定的排序方法。

[ ] 13．在2048个互不相同的关键码中选择最小的5个关键码，用堆排序比用锦标赛排序更快。

[ ] 14．当3阶B_树中有255个关键码时,其最大高度(包括失败结点层)不超过8。

[ ] 15．一棵3阶B_树是平衡的3路搜索树,反之,一棵平衡的3路搜索树是3阶非B_树。

[ ] 16．在用散列表存储关键码集合时，可以用双散列法寻找下一个空桶。

在设计再散列函数时，要求计算出的值与表的大小m互质。

[ ] 17．在只有度为0和度为k的结点的k叉树中，设度为0的结点有n0个，度为k的结点有nk个，则有n0=nk+1。

[ ] 18．折半搜索只适用于有序表，包括有序的顺序表和有序的链表。

（5）计算：最小公倍数=（m0*n0）/最大公约数；
（6）输出最大公约数和最小公倍数。
第一章概论自测题姓名班级
题号
一
二
三
四
五
六
总分
题分
33
15
9
8
20
15
100
得分
一、填空题（每空1分，共33分）
1.一个计算机系统包括和两大部分。
2.一台计算机中全部程序的集合，称为这台计算机的。
3.计算机软件可以分为软件和软件两大类。科学计算程序包属于，诊断程序属于。
解答：
（1）在程序段（1）中只有3条独立的语句，它们的执行频度都是1。这表明该程序段的执行时间是一个与问题的规模n无关的常数。所以其时间复杂度为常数阶T(n)=O(1)。
（2）程序段（2）是一个单循环，核心语句k=k+1要执行n-1次，其执行时间与问题的规模n成正比，故算法的时间复杂度为T(n)=O(n)。
C)可读性和文档性D)数据复杂性和程序复杂性
（）14.计算机算法指的是：
A)计算方法B)排序方法C)解决问题的有限运算序列D)调度方法
（）15.计算机算法必须具备输入、输出和等5个特性。
A)可行性、可移植性和可扩充性B)可行性、确定性和有穷性
C)确定性、有穷性和稳定性D)易读性、稳定性和安全性
三、简答题（每小题3分,共9分）
4.一种用助忆符号来表示机器指令的操作符和操作数的语言是。
5.数据结构是一门研究非数值计算的程序设计问题中计算机的以及它们之间的
和运算等的学科。
6.数据结构被形式地定义为（D, R），其中D是的有限集合，R是D上的有限集合。
7.数据结构包括数据的、数据的和数据的这三个方面的内容。

分治法1、二分搜索算法是利用（分治策略）实现的算法。

9. 实现循环赛日程表利用的算法是（分治策略）27、Strassen矩阵乘法是利用（分治策略）实现的算法。

34．实现合并排序利用的算法是（分治策略）。

实现大整数的乘法是利用的算法（分治策略）。

17．实现棋盘覆盖算法利用的算法是（分治法）。

29、使用分治法求解不需要满足的条件是（子问题必须是一样的）。

不可以使用分治法求解的是（0/1背包问题）。

动态规划下列不是动态规划算法基本步骤的是（构造最优解）下列是动态规划算法基本要素的是（子问题重叠性质）。

下列算法中通常以自底向上的方式求解最优解的是（动态规划法）备忘录方法是那种算法的变形。

（动态规划法）最长公共子序列算法利用的算法是（动态规划法）。

矩阵连乘问题的算法可由（动态规划算法B）设计实现。

实现最大子段和利用的算法是（动态规划法）。

贪心算法能解决的问题：单源最短路径问题，最小花费生成树问题，背包问题，活动安排问题，不能解决的问题：N皇后问题，0/1背包问题是贪心算法的基本要素的是（贪心选择性质和最优子结构性质）。

回溯法回溯法解旅行售货员问题时的解空间树是（排列树）。

剪枝函数是回溯法中为避免无效搜索采取的策略回溯法的效率不依赖于下列哪些因素（确定解空间的时间）分支限界法最大效益优先是（分支界限法）的一搜索方式。

分支限界法解最大团问题时，活结点表的组织形式是（最大堆）。

分支限界法解旅行售货员问题时，活结点表的组织形式是（最小堆）优先队列式分支限界法选取扩展结点的原则是（结点的优先级）在对问题的解空间树进行搜索的方法中,一个活结点最多有一次机会成为活结点的是( 分支限界法).从活结点表中选择下一个扩展结点的不同方式将导致不同的分支限界法,以下除( 栈式分支限界法)之外都是最常见的方式.（1）队列式(FIFO)分支限界法：按照队列先进先出（FIFO）原则选取下一个节点为扩展节点。

（2）优先队列式分支限界法：按照优先队列中规定的优先级选取优先级最高的节点成为当前扩展节点。

2022年忻州师范学院计算机科学与技术专业《数据结构与算法》科目期末试卷A（有答案）一、选择题1、n个结点的完全有向图含有边的数目（）。

A.n*nB.n(n+1)C.n/2D.n*(n-1)2、将两个各有N个元素的有序表归并成一个有序表，其最少的比较次数是（）。

A.NB.2N-1C.2ND.N-13、线性表的顺序存储结构是一种（）。

A.随机存取的存储结构B.顺序存取的存储结构C.索引存取的存储结构D.Hash存取的存储结构4、有六个元素6，5，4，3，2，1顺序入栈，下列不是合法的出栈序列的是（）。

A.543612B.453126C.346521D.2341565、在用邻接表表示图时，拓扑排序算法时间复杂度为（）。

A.O(n)B.O(n+e)C.O(n*n)D.O(n*n*n)6、已知关键字序列5，8，12，19，28，20，15，22是小根堆（最小堆），插入关键字3，调整后的小根堆是（）。

A．3，5，12，8，28，20，15，22，19B．3，5，12，19，20，15，22，8，28C．3，8，12，5，20，15，22，28，19D．3，12，5，8，28，20，15，22，197、下列关于无向连通图特性的叙述中，正确的是（）。

Ⅰ．所有的顶点的度之和为偶数Ⅱ．边数大于顶点个数减1 Ⅲ．至少有一个顶点的度为1A．只有Ⅰ B．只有Ⅱ C．Ⅰ和Ⅱ D．Ⅰ和Ⅲ8、一个具有1025个结点的二叉树的高h为（）。

A.11B.10C.11至1025之间D.10至1024之间9、一棵哈夫曼树共有215个结点，对其进行哈夫曼编码，共能得到（）个不同的码字。

A.107B.108C.214D.21510、数据序列（8，9，10，4，5，6，20，1，2）只能是下列排序算法中的（）的两趟排序后的结果。

A.选择排序B.起泡排序C.插入排序D.堆排序二、填空题11、在有n个顶点的有向图中，每个顶点的度最大可达______。