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

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

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

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

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

5、都访问，且只访问一次是（）的概念。 单选题 *A: 遍历(正确答案)B:访问C:探测D:回溯17、非线性结构的二叉树中，其先序序列是：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 A18、给定一组数据6，8，7，10，3，12以它构造一棵赫夫曼树，则树深度为()，带权路径长度WPL的值是（）。 单选题 *A:5 96B:6 96C:4 116(正确答案)D:4 9819、加设树T的度为4，其度为1，2，3和4的结点个数分别是4，2，2

6、，1 则T中的叶子数有（）个。 单选题 *A: 5B: 6C: 10(正确答案)D: 820、有n个终端结点的哈夫曼树的结点总数为（）。 单选题 *A:2nB:不确定C:2n+1D:2n-1(正确答案)21.哈希表采用“再哈希法”处理冲突，则（）。 单选题 *A: 不容易产生“聚集”(正确答案)B: 任然容易产生“聚集”C: 必然产生“聚集”D: 以上说法都不对22.哈希表的查找是依靠（）来计算出元素的存储地址的。 单选题 *A: 哈希函数(正确答案)B: 逐一比对C: 折半比较D: 集合23.设哈希表长为14，哈希函数是H(key)=key%11,表中已有数据的关键字为15，38，61，84

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

8、序列D: 都不对27.折半查找要求是顺序存储且（）。 单选题 *A: 记录有序(正确答案)B: 记录无序C: 记录随机排放D: 都不对28.设哈希表长为14，哈希函数是H(key)=key%11,表中已有数据的关键字为15，38，61，84共四个，现要将关键字为49的结点加到表中，用二次探测再散列法解决冲突，则放入的位置是（）。 单选题 *A: 8B: 9(正确答案)C: 5D: 329.一棵二叉树的前序遍历序列为ABCDEFG，它的中序遍历序列可能是（）。 单选题 *A: CABDEFGB: ABCDEFG(正确答案)C: DACEFBGD: ADCFEG30.数据结构与算法内，折半查找的时

9、间复杂度是（）。 单选题 *A: O(1)B: O(log2n)(正确答案)C: O(n*n)D: O(n)31.以下属于哈希函数的构造方法的是（）。 单选题 *A: 直接定址法(正确答案)B: 哈希再散列法C: 线性探测再散列法D: 二次探测再散列法32.假定有k个关键字互为同义词，若用线性探测法把这k个关键字存入散列表中，至少要进行多少次探测？（）。 单选题 *A: k-1次B: k次C: k+1次D: k(k+1)/2次(正确答案)33、某二叉树的所有结点的度不是0就是2，则（）。 *A:该二叉树是满二叉树B:该二叉树不一定是满二叉树(正确答案)C:该二叉树的度为0的结点一定是叶子(正确

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

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

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

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

14、的结点可以称为（）。 *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静态查找与动态查找并没有什么区别。 判断题 *对错(正确答案)53. 二叉排序树的右子树也应该是棵二叉排序树。 判断题 *对(正确答案)错54.满二叉树一定是一棵完全二叉树，完全二叉树也一定是满二叉树。 判断题 *对错(正确答案)55.字符串的处理函数strcpy是系统定义的，作用是进行字符串拷贝，两个参数，返回值为char*。 判断题 *对(正确答案)错56、字符串的处理函数strl