武昌工学院软件工程专业大二2019年数据结构与算法周测

1、武昌工学院软件工程专业大二2019年数据结构与算法周测您的姓名： 填空题 *_1.二叉树是非线性数据结构，所以（）。 单选题 *A: 它不能用顺序存储结构存储B: 它不能用链式存储结构存储C: 顺序存储结构和链式存储结构都能存储(正确答案)D: 顺序存储结构和链式存储结构都不能使用2.有n个终端结点的哈夫曼树的结点总数为（）。 单选题 *A: 2nB: 不确定C: 2n+1D: 2n-1(正确答案)3.一棵树的结点有4层，则树的度是（）。 单选题 *A: 4B: 3C: 5D: 不确定(正确答案)4.C结点有3个堂兄弟(不算自己)，B是C的双亲，则B的度是（）。 单选题 *A: 0B: 4C:

2、 3D: 不确定，至少大于等于1(正确答案)5.在C语言描述的数据结构算法中，函数malloc的作用是（）。 单选题 *A: 为指针变量分配空间(正确答案)B: 回收指针变量的空间C: 为普通变量分配空间D: 释放普通变量的空间6.二叉树的先序序列是：A B C D E F；中序序列是：B D C F E A；则其后序序列是()。 单选题 *A: E F D C B AB: D F E C B A(正确答案)C: F E D C B AD: E D F C B A7.假设一棵二叉树的前序遍历结果为ABCDEF,中序遍历结果为CBAEDF,则后序遍历的结果为（）。 单选题 *A: CBEFDA(

3、正确答案)B: FEDCBAC: CBEDFAD: 不确定8.非线性结构的二叉树中，其先序序列是：A B C D E F；中序序列是：B D C F E A；则其后序序列是()。 单选题 *A: E F D C B AB: D F E C B A(正确答案)C: F E D C B AD: E D F C B A9.一棵具有1025个结点的二叉树的深度为h，则h的最大值是（）。 单选题 *A: 11B: 10C: 11至1025之间D: 1025(正确答案)10.一颗二叉树高度为h，所有结点的度或为0，或为2，则这颗二叉树最少有（）个结点。 单选题 *A: 2hB: 2h-1(正确答案)C:

4、2h+1D: h+111.已知某完全二叉树上有结点1001个，其中度为0的结点的个数是（）。 单选题 *A: 250B: 都不对(正确答案)C: 500D: 50512.用二分(折半)查找表的元素的速度比用顺序查找法（）。 单选题 *A、必然快B、必然慢C、相等D、不能确定(正确答案)13.关于是否能查找到特定元素，下列选项中说法正确的是（）。 单选题 *A、若查找表中存在特定元素称为查找失败B、若查找表中存在特定元素称为查找成功(正确答案)C、若查找表中存在特定元素称为查找中D、若查找表中存在特定元素称为未找到14.下列选项中是顺序查找的时间复杂度的是（）。 单选题 *A、O(1)B、O(n

5、)(正确答案)C、O(n2)D、O(log2n)15.改进的顺序查找方法比原来的顺序查找法优势在于（）。 单选题 *A、查找次数减少B、比较次数大量减少(正确答案)C、时间复杂度降低D、都不对16.顺序表可以存储大量密集数据，不需要额外的空间存储线性表元素之间的逻辑关系，顺序表的存储密度是（）。 单选题 *A、1(正确答案)B、0.9C、0.75D、0.2517.数据结构与算法里，哈希表的装填因子（）。 单选题 *A.越大，发生冲突的可能越小B.越小，发生冲突的可能越大C.与是否发生冲突无关D.越大，发生冲突的可能性越大(正确答案)18.已知某完全二叉树上有结点1001个，其中度为0的结点的个

6、数是（）。 单选题 *A.250B.都不对(正确答案)C.500D.50519.数据结构与算法里，二叉排序树的第5层多有多少个结点（）。 单选题 *A.4B.16(正确答案)C.8D.3220.n个记录的某顺序表，查找某关键字，采用顺序查找，最坏的情况是比较多少次（）。 单选题 *A: n(正确答案)B: 1C: n-1D: n+121.线性结构之队列的应用包括哪些（）。 *A: 消息的缓存(正确答案)B: 操作系统的作业调度(正确答案)C: 离散事件的模拟(正确答案)D: 进制转换22.已知某完全二叉树上有结点1001个，其中度为0的结点的个数是（  ）。单选题 *A: 250B:

7、 都不对(正确答案)C: 500D: 50523.已知某完全二叉树上有结点1002个，其中度为0的结点的个数是（）。 *A: 250B: 都不对C: 501(正确答案)D: 50524.一个具有1025个结点的二叉树的高h的值可能是（）。 *A: 11(正确答案)B: 10C: 500(正确答案)D: 1025(正确答案)25.完全二叉树中，结点个数为n，则编号最大的分支结点的编号不可能为（）。 *A: n/2向下取整B: n/2向下取整+1(正确答案)C: n/2向下取整+2(正确答案)D: n/2向下取整-1(正确答案)26.已知某二叉树的中序序列是形： A+B*C-D/E，后序序列是为A

8、BC*+DE/-，则其先序序列不可能是（）。 *A: -A+B*C/DE(正确答案)B: -A+B*CD/E(正确答案)C: -+*ABC/DE(正确答案)D: -+A*BC/DE27.深度是5的二叉树，可以有多少个结点（）。 *A: 5(正确答案)B: 7(正确答案)C: 31(正确答案)D: 3228.二叉树的遍历分为（）。 *A: 先序遍历(正确答案)B: 中序遍历(正确答案)C: 后序遍历(正确答案)D: 按层次遍历(正确答案)29.关于二叉树的遍历和恢复说法正确的是（）。 *A: 先序序列和中序序列已知，可以恢复二叉树(正确答案)B: 中序序列和后序序列已知，可以恢复二叉树(正确答案

9、)C: 先序序列和后序序列已知，可以恢复二叉树D: 已知先序序列和按层次遍历序列可以恢复二叉树30.给定一组数据6，2，7，10，3，12以它构造一棵赫夫曼树，则树高为()，带权路径长度WPL的值不可能为（）。 *A: 5 96B: 6 96(正确答案)C: 4 93(正确答案)D: 4 98(正确答案)31.关于树的深度说法不正确的是（）。 *A: 树的深度：所有结点层次的最大值，根结点算第一层B: 树的深度：所有结点度中的最大值(正确答案)C: 树的深度：和树的高度是一个概念D: 树的深度：是分支结点中度的最小值(正确答案)32.数据结构与算法里，关于二叉排序树相关描述正确的是（）。 *A

10、.二叉排序树是应用于动态查找的结构(正确答案)B.二叉排序树的中序列是升序序列(正确答案)C.二叉排序树的左子树也是二叉排序树(正确答案)D.二叉排序树的定义具有递归性(正确答案)33.线性结构之队列的应用包括哪些（）。 *A: 消息的缓存(正确答案)B: 操作系统的作业调度(正确答案)C: 离散事件的模拟(正确答案)D: 进制转换34.树的术语中描述不正确有哪些项（）。 *A: 祖先：即从根到该结点所经分支的所有结点B: 子孙：即该结点下层子树中的任一结点C: 树的度：指所有结点中最大的层数(正确答案)D: 树的高度(深度)：所有结点度中的最大值(正确答案)35.一个具有1025个结点的二叉

11、树的高h的值可能是（）。 *A: 11(正确答案)B: 10C: 500(正确答案)D: 1025(正确答案)36.O(n)是以下哪种算法的复杂度（）。 *A、顺序查找(正确答案)B、顺序表删除元素(正确答案)C、顺序表插入元素(正确答案)D、单链表查找第i个元素(正确答案)37.单链表，在s指针指向的结点后插入p指针指向的结点，指针域为next，语句序列不正确的是：（）。 *A、p->next=s->next; s->next=p;B、s->next=p->next; p->next=s;(正确答案)C、s->next=s->next->

12、next; free(p);(正确答案)D、s->next=p; p->next=s->next;(正确答案)38. 哈希表的平均查找长度与哪些（）因素有关。 *A、处理冲突的方法(正确答案)B、哈希函数(正确答案)C、装填因子(正确答案)D、待存记录的大小39. 深度为7的二叉树，不可能有的结点个数是（）。 *A: 127B: 255(正确答案)C: 256(正确答案)D: 257(正确答案)40.一棵具有128个结点的二叉树，其深度可能是（）。 *A: 8(正确答案)B: 7C: 100(正确答案)D: 128(正确答案)41. 关于装填因子，以下说法正确的是（）。 *A

13、: 哈希表的平均查找长度与处理冲突的方法无关。B: 若散列表的负载因子(装填因子)<1，则可避免冲突的产生。C: 散列法的平均检索长度不随表中结点数目的增加而增加，而是随负载因子的增大而增大。(正确答案)D: 负载因子 (装填因子)是散列表的一个重要参数，它反映散列表的装满程度。(正确答案)42.二叉树不是树的特例。 判断题 *对(正确答案)错43.链表的删除算法很简单，因为当删除链中某个结点后，计算机会自动将后续各个单元向前移动，所以时间复杂度是O(1)。 判断题 *对错(正确答案)44.顺序存储结构的主要缺点是密度为1，不用特意花空间存储元素之间的关系。 判断题 *对错(正确答案)4

14、5. 二叉排序树的充要条件：二叉排序树的任意结点的关键字都大于其左孩子的关键字，且小于其右孩子的关键字。 判断题 *对错(正确答案)46. 若哈希表的装填因子<1，则可避免冲突的产生。 判断题 *对错(正确答案)47.动态查找表属于树形结构，因为这里涉及二叉排序树。 判断题 *对错(正确答案)48. 栈和队列的特性是相同的，都是先进先出。 判断题 *对错(正确答案)49.树的深度和树的高度是一个概念。 判断题 *对(正确答案)错50.树可以为空，而且不空时，定义具有递归性。 判断题 *对(正确答案)错51.兄弟与堂兄弟的共同之处就是一定在树的同一层上。 判断题 *对(正确答案)错52.在树形结构中，树和二叉树是两种不同的数据结构，二叉树不是树的特例。 判断题 *对(正确答案)错53. 哈夫曼树(赫夫曼树)有这样的特点：只有度为0和度为2的结点，没有度为1的结点。 判断题 *对(正确答案)错54. 在使用除留余数法时，对p的选择很重要。若p选的不好，容易产生同义词。 判断题 *对(正确答案)错55.直接定址法就是取关键字或关键字的某个线性函数值为哈希地址。 判断题 *对(正确答案)错56.若对于关键字集合中的任何一个关键字，经哈希函数映像到地址集合中任何一个地址的概率是相等的。则称此类哈希函数为均匀的(Uniform)哈希函数。 判断题 *对(