计算机专业(基础综合)模拟试卷106(题后含答案及解析)VIP免费

计算机专业（基础综合）模拟试卷106(题后含答案及解析)题型有：1.单项选择题2.综合应用题单项选择题1-40小题，每小题2分，共80分。下列每题给出的四个选项中，只有一个选项是最符合题目要求的。1．输入受限的双端队列是指元素只能从队列的一端输入，但可以从队列的两端输出，如图3-1所示。若有8、1、4、2依次进入输入受限的双端队列，则得不到输出序列()。A．2、8、1、4B．1、4、8、2C．4、2、1、8D．2、1、4、8正确答案：D解析：A选项：首先，8、1、4、2都从左端入队，然后2从左端出队，8从右端出队，1从右端出队，4从左端出队，得到A的序列。B选项：首先，8和1分别从左端输入，然后1从左端出队，4再从左端入队，4再从左端出队，2从左端入对，8从右端出队，2从左端出队，得到B的序列。C选项：首先，8、1、4都从左端入队，4从左端出队，2再从左端入队，2从左端出队，1从左端出队，8从左端或者右端出队，得到C的序列。D选项：首先，8、1、4、2都从左端入队，然后2从左端出队，队列的序列变成如图3-7所示，接着如果要让1出队列，必须4或8先出队列，所以D的序列不可能实现。2．若要在O(1)的时间复杂度上实现两个循环链表头尾相接，则对应两个循环链表各设置一个指针，分别指向()。A．各自的头结点B．各自的尾结点C．各自的第一个元素结点D．一个表的头结点，另一个表的尾结点正确答案：B解析：两个循环链表头尾相接，需要改变头结点和尾结点之间的指针，而这个指针是从尾结点指向头结点的，所以只有将两个指针分别指向自己循环链表的尾结点才能完成操作。实现的代码如下：voidconnect(LNode*A，LNode*＆B)／／假设A、B为非空带头结点的循环链表的尾指针{LNode*p=A-＞next；／／保存A表的头结点A-＞neXt=B-＞next-＞next；／／B的开始结点链接到A表尾free(B-＞next)；／／释放B表的头结点B-＞next=p；／／将B表的尾结点链接到A表的头结点}3．下列说法正确的是()。Ⅰ．用链式方式存储的队列，在进行出队操作时，队头、队尾指针都必须修改Ⅱ．将递归算法转换成等价的非递归算法应使用栈Ⅲ．图的广度优先搜索使用了栈来实现A．ⅠB．Ⅰ、ⅡC．ⅡD．Ⅱ、Ⅲ正确答案：C解析：Ⅰ：队列以链表方式存储时，如果队列中只有一个元素，则出队操作需要修改队头、队尾指针；反之，只需要修改队头指针，所以Ⅰ错误。Ⅱ：考查栈的基本应用，在二叉树遍历的非递归算法中可以得到认证，所以Ⅱ正确。Ⅲ：队列具有先进先出的特性，在广度优先搜索算法中，访问完每一个结点，可将其子结点全部加入队列中，这样可实现结点的按层次优先的访问，故广度优先搜索使用了队列来实现，所以Ⅲ错误。4．下列关于二叉排序树的说法正确的是()。Ⅰ．向二叉排序树中插入一个结点，所需要比较的次数可能大于此二叉排序树的高度Ⅱ．二叉排序树一定是平衡二叉树Ⅲ．删除二叉排序树中的一个结点，再重新插入，一定能得到原来的二叉排序树Ⅳ．平衡二叉树是指左、右子树的高度差的绝对值不大于1的二叉树A．Ⅰ、Ⅱ、ⅣB．Ⅱ、Ⅲ、ⅣC．Ⅰ、ⅣD．全错正确答案：D解析：Ⅰ：根据二叉排序树插入操作的步骤可知，比较次数最坏情况下等于树的高度，所以Ⅰ错误。Ⅱ：二叉排序树不一定是平衡二叉树。例如，降序的一个序列组建二叉排序树时，会出现没有右子树的二叉树，此时明显不是平衡二叉树，所以Ⅱ错误Ⅲ：不一定可以得到以前的排序二叉树。例如，给出一个二叉排序树，如图3-8所示。此时删除结点3，二叉排序树变为图3-8b，再插入结点3，变为图3-8c。显然图3-8a和图3-8c不是同一个二叉排序树，所以Ⅲ错误。Ⅳ：根据平衡二叉树的概念可知，该说法是错误的，应该改为：平衡二叉树是指左、右子树的高度差的绝对值不大于1的二叉排序树(出此选项的目的是让大家深刻记住平衡二叉树默认是二叉排序树)，所以Ⅳ错误。5．对于顺序查找，假定查找成功与不成功的概率相同，对每个记录的查找概率也相同，此时顺序查找的平均查找长度为()。A．0．5(n+1)B．0．25(n+1)C．0．5(n-1)D．0．75n+0．25正确答案：D解析：在查找成功的情况下，平均查找长度为(1+n)／2；在查找不成功时，每次都需要查找n次，即平均查找长度为n，而题目告诉我们查找成功与查找不...