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

商丘学院软件工程专业大二2017年数据结构与算法周考二测试您的姓名：［填空题］*1、队列具有先进先出的特性，那么入队的O,P,Q顺序的三个元素，出队顺序是（）。［单选题］*A:O,P，Q（正确答案）B:O，Q，PC:Q，P，OD:O，Q，P2、循环队列最大容量是MAX，队头是front，队尾是rear，采用人为浪费一个单元的形式，则队的长度是（）。［单选题］*A:（rear—front）%MAXB:（rear—front+MAX）%MAX（正确答案）C:rear—front+MAXD:都不对3、 单链表中删除p指针指向结点的后继（假设存在）的语句序列正确的是（）。［单选题］*A:p->next=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、在树的概念中，树的某结点的直接后继称为该结点的（）。［单选题］*A:孩子（正确答案）8:双亲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的结点的个数是6,则问度为0的结点的个数是（）。［单选题］*A:6B:7（正确答案）C:8D:512、 当二叉树的结点个数n是0的时候表示，它是（）。［单选题］*A:满二叉树8:空二叉树（正确答案）C:完全二叉树D:哈夫曼树13、左子树、右子树、根结点的遍历顺序称为（）。［单选题］*A:中序遍历B:先序遍历C:后序遍历（正确答案）D:都不对14、左子树、根结点、右子树的遍历顺序称为（）。［单选题］*A:中序遍历（正确答案）B:先序遍历C:后序遍历D:都不对15、根结点、左子树、右子树的遍历顺序称为（）。［单选题］*A:中序遍历B:先序遍历（正确答案）C:后序遍历D:都不对16、 对于二叉树，每个结点都访问，且只访问一次是（）的概念。［单选题］*A:遍历（正确答案）B:访问C:探测D:回溯17、 非线性结构的二叉树中，其先序序列是：ABCDEF；中序序列是：BDCFEA；则其后序序列是（）。［单选题］*A:EFDCBAB:DFECBA（正确答案）C:FEDCBAD:EDFCBA18、 给定一组数据｛6,8,7,10，3,12｝以它构造一棵赫夫曼树，则树深度为（），带权路径长度WPL的值是（）。［单选题］*A:596B:696C:4116（正确答案）D:49819、 加设树T的度为4，其度为1，2，3和4的结点个数分别是4，2，2，1则T中的叶子数有（）个。［单选题］*A:5B:6C:10（正确答案）D:820、 有n个终端结点的哈夫曼树的结点总数为（）。［单选题］*A:2nB:不确定C:2n+1D:2n-1（正确答案）哈希表采用“再哈希法”处理冲突，则（）。［单选题］*A:不容易产生“聚集”（正确答案）B:任然容易产生“聚集”C:必然产生“聚集”D:以上说法都不对哈希表的查找是依靠（）来计算出元素的存储地址的。［单选题］*A:哈希函数（正确答案）B:逐一比对C:折半比较D:集合设哈希表长为14，哈希函数是H（key）=key%11,表中已有数据的关键字为15，38,61，84共四个，现要将关键字为49的结点加到表中，用二次探测再散列法解决冲突，则放入的位置是（）。［单选题］*A:8B:9（正确答案）C:5D:3二叉排序树的（）上结点的值都小于根结点的值。［单选题］*A:左子树（正确答案）B:右子树C:左子树和右子树D:都不对关于查找的效率问题，下面说法中正确的是（）。［单选题］*A:顺序查找一定没有折半查找快B:顺序查找比折半查找快C:折半查找不一定比顺序查找快（正确答案）D:就平均效率而言，顺序查找的效率更高二叉排序树是一颗特殊的二叉树，其中序序列是一个（）。［单选题］*A:倒序序列B:升序序列（正确答案）C:乱序序列D:都不对折半查找要求是顺序存储且（）。［单选题］*A:记录有序（正确答案）B:记录无序C:记录随机排放D:都不对设哈希表长为14，哈希函数是H（key）=key%11,表中已有数据的关键字为15，38,61，84共四个，现要将关键字为49的结点加到表中，用二次探测再散列法解决冲突，则放入的位置是（）。［单选题］*A:8B:9（正确答案）C:5D:3一棵二叉树的前序遍历序列为ABCDEFG，它的中序遍历序列可能是（）。［单选题］*A:CABDEFGB:ABCDEFG（正确答案）C:DACEFBGD:ADCFEG数据结构与算法内，折半查找的时间复杂度是（）。［单选题］*A:0（1）B:O（log2n）（正确答案）C:O（n*n）D:O（n）以下属于哈希函数的构造方法的是（）。［单选题］*A:直接定址法（正确答案）B:哈希再散列法C:线性探测再散列法D:二次探测再散列法假定有k个关键字互为同义词，若用线性探测法把这k个关键字存入散列表中，至少要进行多少次探测？（）。［单选题］*A:k-1次B:k次C:k+1次D:k（k+1）/2次（正确答案）某二叉树的所有结点的度不是0就是2,则（）。*人:该二叉树是满二叉树8:该二叉树不一定是满二叉树（正确答案）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，若A是根结点，则E结点不可能在（）。*A:左子树B:右子树（正确答案）C:右子树的第二层（正确答案）D:右子树的根节点（正确答案）37、 在树中，度不为0的结点（根除外）可以称为（）。*A:叶子B:终端结点C:分支结点（正确答案）38、下列选项中关于二叉树的遍历和恢复说法正确的是（）A:先序序列和中序序列已知，可以恢复二叉树（正确答案）B:中序序列和后序序列已知，可以恢复二叉树（正确答案）C:先序序列和后序序列已知，可以恢复二叉树D:无正确答案装填因子的计算方法是（）。*A:1-（表中未填入记录的数目/哈希表的总长度）（正确答案）B:表中未填入记录的数目/哈希表的总长度C:俵中未填入的记录数-1）/哈希表的总长度D:表中填入的记录数/哈希表的总长（正确答案）下面属于构造散列函数的方法是（）。*A:直接定址法（正确答案）B:数字分析法（正确答案）C:除留余数法（正确答案）D:平方取中法（正确答案）静态查找表中，对顺序表的查找方式有（）。*A:顺序查找（正确答案）B:折半查找（正确答案）C:分块查找D:随机查找以下是C语言中的字符串处理函数的，且带有两个参数的是（）。*A:strcat（正确答案）B:strcpy（正确答案）C:strlenD:strcmp（正确答案）43、 关于二叉排序树描述有误的是（）。*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的结点可以称为（）。*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静态查找与动态查找并没有什么区别。［判断题］*对错（正确答案）二叉排序树的右子树也应该是棵二叉排序树。［判断题］*对（正确答案）错54、 满二叉树一定是一棵完全二叉树，完全二叉树也一定是满二叉树。［判断题］*对错（正确答案）55、 字符串的处理函数strcpy是系统定义的，作用是进行字符串拷贝，两个参数，返回值为char*。［判断题］*对（正确答案）错56、 字符串的处理函数strlen是