数据结构与算法模拟题及答案.docxVIP

数据结构与算法模拟题及答案 .关于素数描述正确的选项是（）O A:素数就是合数 B:素数不能被本身整除 C:素数又称为质数只能被1和它本省整除（正确答案） D:素数不仅能被1和它本身整除，还能被其它数整除 . for循环的（表达式1;表达式2;表达式3）中表达式3的作用是（）。 A:循环的增量表达式（正确答案） B:循环的条件 C:循环的初值 D:循环体 .哪一种排序，可能存在这种情况：“最后一趟开始之前，所有记录均不在其 最终位置上” （）o A:快速排序 B:冒泡排序 C:直接插入排序（正确答案） D:简单项选择择排序 4简单项选择择排序，按照从小到大排序，原始序列是：19 11 17 18 16 15,那么经过一趟排序后的结果是（）o A:ll19 17 18 16 15（正确答案）B:ll15 16 17 18 19C:ll17 18 16 15 19D:19 A:ll 19 17 18 16 15（正确答案） B:ll 15 16 17 18 19 C:ll 17 18 16 15 19 D:19 11 17 18 16 15 5、关于查找的效率问题，下面说法中正确的选项是（）o A :顺序查找一定没有折半查找快 B:顺序查找比折半查找快 D: for语句是c语言所提供的功能更强，使用更广泛的一种循环语句。（正确 答案） 44、以下可用递归实现的是（）o A:求1-n的和（正确答案） B:求n的阶乘（正确答案） C:斐波那契数列（正确答案） 口：11%。表示幕）（正确答案） 45.静态查找表中，对顺序表的查找方式有（）o A:顺序查找（正确答案） B:折半查找（正确答案） C:分块查找 D:随机查找 46、从排序大类上看，属于选择排序的是（）。 A:简单项选择择排序（正确答案） B:堆排序（正确答案） C:快速排序 D:冒泡排序 47、在简单项选择择排序中，每一趟排序过程中最多进行1次记录交换。 对（正确答案） 错 . for循环的思想是，先分析清楚循环的初始值，循环的控制条件，循环变 量的步长变化，然后直接把语句再写到for的循环体里即可，这样可以让问题想的 很清楚，流程也很清楚。 对（正确答案） 错 .二叉排序树的充要条件是树中任何一个结点的左孩子的关键字要小于根结 点的关键字，右孩子的关键字要大于根节点的关键字。 对 错（正确答案） .快速排序的时间复杂度低于冒泡排序的时间复杂度。 对（正确答案） 错 .装填因子越大，发生冲突的可能性就越大；当装填因子减小到一定程度， 那么冲突是可以防止的。 对 错（正确答案） .青蛙过河问题是一种用递归算法可以解决的问题，这种算法的特点是自身 调用自身。 对（正确答案） 错 排序算法中，第一趟排序后，任一元素都不能确定其最终位置的算法是插 入排序。 对（正确答案） 错 54青蛙过河案例中，如果河中有2根石柱，有3片荷叶，那么可以过24只青 蛙。 对 错（正确答案） .稳定排序是指排序前后相同关键字的记录相对位置不变。 对（正确答案） 错 .希尔排序是一种选择排序，也不稳定排序，时间复杂度是0（n3/2）。 对 错（正确答案） .冒泡排序和快速排序都是基于交换两个逆序元素的排序方法，冒泡排序算法 的最坏时间复杂性是O（nn）,而快速排序算法的最坏时间复杂性是0（nlog2n）,所以 快速排序比冒泡排序算法效率更高。 对 错（正确答案） .把规模大的问题转换为规模小的相似问题，这是递归的思想。 对（正确答案） 借 .简单项选择择排序每趟排序可能出现屡次记录交换。 对 错（正确答案） c:折半查找不一定比顺序查找快（正确答案） D:就平均效率而言，顺序查找的效率更高 .青蛙过河案例中，如果河中没有石柱，有y片荷叶的话，那么从左岸到右岸 可以过去（）只青蛙。 y+1只（正确答案） y+2 只 y+3 只 y+4 只 .青蛙过河案例中，如果河中有1根石柱，问最少有几片荷叶就能过4只青蛙 （）0 1片（正确答案） 3片 0片 2片 .某些排序存在不相邻记录之间的交换，因此是不稳定排序，以下是不稳定的 排序是（）o A:快速排序（正确答案） B:冒泡排序 C:直接插入排序 D:都不对 .从算法的时间复杂度来看，0（nlog2n）是哪种排序的时间复杂度（）。 A:快速排序（正确答案） B:直接插入排序 C:简单项选择择排序 D：冒泡排序 .简单项选择择排序中，每一趟选择最小的记录的过程，那么每一趟排序的时间复 杂度是O o 0（n）（正确答案） O（nn） 0（1） 0（nlog2n） . 10个记录进行简单项选择择排序，需要（）趟排序。 9（正确答案） 8 10 D:都不对 .采用简单项选择择排序，共有N个记录，每趟最多进行（）次交换。 1（正确答案） 2 N-2 N-1 .快速排序在