商丘学院软件工程专业大二2017年数据结构与算法周考二测试

1、商丘学院软件工程专业大二 2017 年数据结构与算法周考二测试您的姓名： 填空题 *1、队列具有先进先出的特性，那么入队的 O，P，Q 顺序的三个元素，出队顺序是（）。 单选题 *A:OA:O，P，Q(正确答案B:O，Q，P C:Q，P，OD:O，Q，P2、循环队列最大容量是 MAX，队头是 front，队尾是 rear，采用人为浪费一个单元的形式，则队的长度是（）。 单选题 *A:(rearfront)%MAXA:(rearfront)%MAXB: (rearfront+MAX)%MAX(正确答案) C: rearfront+MAXD:都不对3、单链表中删除 p 指针指向结点的后继(假设存在

2、)的语句序列正确的是（）。 单选题 *A:p-next=p-next;A:p-next=p-next;B:p-next=p-next-next;(正确答案C:p-next=p;D:p=p-next;4、串的 KMP 算法是由三个科学家同时发现的，对原有的算法改进点在于（）。单选题 *A:A:指向主串的指针不需要回溯，只模式串滑动尽可能远的距离后继续进行模式匹配(正确答案)B:主串的指针要回溯到之前的某个位置，同时模式串滑动尽可能远的距离后继续进行模式匹配C:某个字符匹配失败时，主串与模式都不需要回溯指针D:时间复杂度可提高到 O(n*m),n 和 m 表示主串和模式串的长度。5、在树的概念中，

3、树的某结点的直接后继称为该结点的（）。 单选题 *A:A:孩子(正确答案) B:双亲C: 子孙D:祖先6、度为 0 的结点又称为（）。 单选题 *A:A:叶子(正确答案) B:根结点C:分支结点内部结点7、结点的度是指（）。 单选题 *A:A:结点挂接的子树的数目(正确答案) B:零C:叶子的个数无正确答案8、树是一种常用的数据结构，树的逻辑结构是（）。 单选题 *A:A:一对多(正确答案B:一对一C:二对一多对多9、二叉树如果有根结点，只能有（）个。 单选题 *A: A: 一(正确答案) B: 两C:D:10、满二叉树的叶子结点都在（）。 单选题 *A:A:最后一层(正确答案) B:可以在不

4、同的的层C:没有叶子结点D:都不对11、一颗二叉树度为 2 的结点的个数是 6，则问度为 0 的结点的个数是（）。 单选题 *A:6A:6B:7(正确答案C:8D:512、当二叉树的结点个数 n 是 0 的时候表示，它是（）。 单选题 *A: A: 满二叉树B:空二叉树(正确答案)C:C:完全二叉树D:哈夫曼树13、左子树、右子树、根结点的遍历顺序称为（）单选题 *A:A:中序遍历B:先序遍历C:后序遍历(正确答案)D:都不对14、左子树、根结点、右子树的遍历顺序称为（）单选题 *A:A:中序遍历(正确答案B:先序遍历C:后序遍历D:都不对15、根结点、左子树、右子树的遍历顺序称为（）单选题

5、*中序遍历B:先序遍历(正确答案C:后序遍历D:都不对16、对于二叉树，每个结点都访问，且只访问一次是（）的概念。 单选题 *A:A:遍历(正确答案B:访问C:探测回溯A: E F D C B AB:D F E C B 正确答案C:F E D C BAD:E D F C BA17A: E F D C B AB:D F E C B 正确答案C:F E D C BAD:E D F C BA18、给定一组数据6，8，7，10，3，12以它构造一棵赫夫曼树，则树深度为()， 带权路径长度 WPL 的值是（）。 单选题 *A:5 96A:5 96B:6 96C:4116(正确答案D:4 9819、加设树

6、 T 的度为 4，其度为 1，2，3 和 4 的结点个数分别是 4，2，2，1 则 T中的叶子数有（）个。 单选题 *A: 5A: 5B: 6C:10(正确答案D: 820、有 n 个终端结点的哈夫曼树的结点总数为（）。 单选题 *A:2nA:2nB:不确定C:2n+1D:2n-1(正确答案)哈希表采用“再哈希法”处理冲突，则（）单选题 *A: A: 不容易产生“聚集”(正确答案) B: 任然容易产生“聚集”C: 必然产生“聚集”D: 以上说法都不对哈希表的查找是依靠（）单选题*A:A:哈希函数(正确答案B:逐一比对C: 折半比较D: 集合14H(key)=key%11,15，38，61，84

7、 共四个，现要将关键字为 49 的结点加到表中，用二次探测再散列法解决冲突，则放入的位置是（）。 单选题 *A: 8A: 8B:9(正确答案C: 5D: 3二叉排序树的（）单选题 *A: A: 左子树(正确答案) B: 右子树C: 左子树和右子树D: 都不对关于查找的效率问题，下面说法中正确的是（）单选题 *A: A: 顺序查找一定没有折半查找快B: B: 顺序查找比折半查找快C: 折半查找不一定比顺序查找快(正确答案) D: 就平均效率而言，顺序查找的效率更高二叉排序树是一颗特殊的二叉树，其中序序列是一个（） *A:A:倒序序列B:升序序列(正确答案C: 乱序序列D: 都不对折半查找要求是顺

8、序存储且（） *A: A: 记录有序(正确答案) B: 记录无序C: 记录随机排放D: 都不对14H(key)=key%11,15，38，61，84 共四个，现要将关键字为 49 的结点加到表中，用二次探测再散列法解决冲突，则放入的位置是（）。 单选题 *A: 8A: 8B:9(正确答案C: 5D: 3ABCDEFG，它的中序遍历序列可能是（）选题 *A: CABDEFGA: CABDEFGB: ABCDEFGB: ABCDEFG(正确答案) C: DACEFBGD: ADCFEG数据结构与算法内，折半查找的时间复杂度是（）单选题 *A: O(1)A: O(1)B: O(log2n)(正确答案

9、) C: O(n*n)D: O(n)以下属于哈希函数的构造方法的是（）单选题 *A: A: 直接定址法(正确答案) B: 哈希再散列法C: 线性探测再散列法D:二次探测再散列法kk中，至少要进行多少次探测？（）单选题*A: k-1 A: k-1 次B: k 次C: k+1 次D: k(k+1)/2 次(正确答案)33、某二叉树的所有结点的度不是 0 就是 2，则（）。 *A:A:该二叉树是满二叉树B:该二叉树不一定是满二叉树(正确答案)C:该二叉树的度为 0 的结点一定是叶子(正确答案)D: D: 该二叉树若有 n 层，则最少的结点数是 2*n-1(正确答案)34、在下列结论中，正确的是（）。

10、 *A:A:只有一个结点的二叉树的度为 0(正确答案) B:二叉树的度小于等于 2(正确答案)C:二叉树的左右子树不可任意交换(正确答案)D:深度为 K 的完全二叉树的结点个数小于或等于深度相同的满二叉树(正确答案)35、已知某二叉树的中序序列是形： A+B*C-D/E，后序序列是为 ABC*+DE/-，则其先序序列不可能是（）。 *A:-A+B*C/DEA:-A+B*C/DE(正确答案) B:-A+B*CD/E(正确答案) C:-+*ABC/DE(正确答案) D: -+A*BC/DE36、二叉树的中序遍历序列是 E、B、A、C、F、D，若 A 是根结点，则 E 结点不可能在（）。 *A:A:

11、左子树B: 右子树(正确答案)C:右子树的第二层(正确答案) D:右子树的根节点(正确答案)37、在树中，度不为 0 的结点(根除外)可以称为（）。 *A:A:叶子B:终端结点分支结点(正确答案)内部结点(正确答案)38、下列选项中关于二叉树的遍历和恢复说法正确的是（）。 *A:A:先序序列和中序序列已知，可以恢复二叉树(正确答案) B:中序序列和后序序列已知，可以恢复二叉树(正确答案) C:先序序列和后序序列已知，可以恢复二叉树D:无正确答案装填因子的计算方法是（）*A: 1-(A: 1-(表中未填入记录的数目/哈希表的总长度)(正确答案) B: 表中未填入记录的数目/哈希表的总长度C: (

12、表中未填入的记录数-1)/哈希表的总长度D: 表中填入的记录数/哈希表的总长(正确答案)下面属于构造散列函数的方法是（）*A:A:直接定址法(正确答案B:数字分析法(正确答案) C:除留余数法(正确答案)D:平方取中法(正确答案)静态查找表中，对顺序表的查找方式有（）*A:A:顺序查找(正确答案B:折半查找(正确答案) C: 分块查找D:随机查找42、以下是 C 语言中的字符串处理函数的，且带有两个参数的是（）。 *A:strcatA:strcat(正确答案)B:strcpy(正确答案)C:strlenC:strlenD:strcmp(正确答案)43. 关于二叉排序树描述有误的是（）。 *A:

13、 A: 二叉排序的右子树上结点的关键字小于左子树上的结点的关键字(正确答案) B: 二叉排序的左子树上结点的关键字小于右子树上的结点的关键字C: 二叉排序的根节点的关键大于右子树上结点的关键字(正确答案)D: 二叉排序的根节点的关键大于左子树上结点的关键字44、由于队列是先进先出的特性，入队的顺序是 A、B、C 则出队的顺序不可能是（）。 *A:AA:A、C、B(正确答案) B:A、B、CC:C、A、正确答案)、A(正确答案)45、各结点层次的最大值(根结点算第一层)，这个概念不是说（）的。 *A:A:树的深度B:树的高度C:树的度(正确答案)D:结点的度(正确答案)46、度为 0 的结点可以

14、称为（）。 *A:A:叶子(正确答案)B:终端结点(正确答案) C:分支结点D:根结点47、满二叉树的叶子一定只能出现在最后一层。 判断题 *对对(正确答案)错48、非空左斜树的先序遍历序列和后序遍历序列正好相反。 判断题 *对对(正确答案)错49、若二叉树不空，二叉树的先序序列中第一个结点一定是根结点。 判断题 *对对(正确答案)错50、某完全二叉树有 13 个度为 2 的结点，1 个度为 1 的结点，则可以推算出该完全二叉树总共有 28 个结点。 判断题 *对对(正确答案)错51、若输入序列为 1,2,3,4,5,6,则通过一个栈可以输出序列 4,2,5,6,3,1。 判断题 *对对错(正确答案)52 静态查找与动态查找并没有什么区别。 判断题 *对对错(正确答案)判断题*对对(正确答案)错判断题 *对对错(正确答案)strcpychar*判断题 *对对(正确答案)错56、字符串的处理函数 strlen 是系统