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

1、数据结构与算法模拟题及答案.关于素数描述正确的选项是（）OA:素数就是合数B:素数不能被本身整除C:素数又称为质数只能被1和它本省整除（正确答案）D:素数不仅能被1和它本身整除，还能被其它数整除. for循环的（表达式1;表达式2;表达式3）中表达式3的作用是（）。A:循环的增量表达式（正确答案）B:循环的条件C:循环的初值D:循环体.哪一种排序，可能存在这种情况：“最后一趟开始之前，所有记录均不在其 最终位置上” （）oA:快速排序B:冒泡排序C:直接插入排序（正确答案）D:简单项选择择排序4简单项选择择排序，按照从小到大排序，原始序列是：19 11 17 18 16 15,那么经过一趟排序

2、后的结果是（）oA:ll19 17 18 16 15（正确答案）B:ll15 16 17 18 19C:ll17 18 16 15 19D:19 11 1718 16 155、关于查找的效率问题，下面说法中正确的选项是（）oA :顺序查找一定没有折半查找快B:顺序查找比折半查找快D: for语句是c语言所提供的功能更强，使用更广泛的一种循环语句。（正确 答案）44、以下可用递归实现的是（）oA:求1-n的和（正确答案）B:求n的阶乘（正确答案）C:斐波那契数列（正确答案）口：11%。表示幕）（正确答案）45.静态查找表中，对顺序表的查找方式有（）oA:顺序查找（正确答案）B:折半查找（正确答案

3、）C:分块查找D:随机查找46、从排序大类上看，属于选择排序的是（）。A:简单项选择择排序（正确答案）B:堆排序（正确答案）C:快速排序D:冒泡排序47、在简单项选择择排序中，每一趟排序过程中最多进行1次记录交换。对（正确答案）错. for循环的思想是，先分析清楚循环的初始值，循环的控制条件，循环变 量的步长变化，然后直接把语句再写到for的循环体里即可，这样可以让问题想的 很清楚，流程也很清楚。对（正确答案）错.二叉排序树的充要条件是树中任何一个结点的左孩子的关键字要小于根结 点的关键字，右孩子的关键字要大于根节点的关键字。对错（正确答案）.快速排序的时间复杂度低于冒泡排序的时间复杂度。对（

4、正确答案）错.装填因子越大，发生冲突的可能性就越大；当装填因子减小到一定程度， 那么冲突是可以防止的。对错（正确答案）.青蛙过河问题是一种用递归算法可以解决的问题，这种算法的特点是自身 调用自身。对（正确答案）错排序算法中，第一趟排序后，任一元素都不能确定其最终位置的算法是插 入排序。对（正确答案）错54青蛙过河案例中，如果河中有2根石柱，有3片荷叶，那么可以过24只青 蛙。对错（正确答案）.稳定排序是指排序前后相同关键字的记录相对位置不变。对（正确答案）错.希尔排序是一种选择排序，也不稳定排序，时间复杂度是0（n3/2）。对错（正确答案）.冒泡排序和快速排序都是基于交换两个逆序元素的排序方法

5、，冒泡排序算法 的最坏时间复杂性是O（nn）,而快速排序算法的最坏时间复杂性是0（nlog2n）,所以 快速排序比冒泡排序算法效率更高。对错（正确答案）.把规模大的问题转换为规模小的相似问题，这是递归的思想。对（正确答案）借.简单项选择择排序每趟排序可能出现屡次记录交换。对错（正确答案）c:折半查找不一定比顺序查找快（正确答案）D:就平均效率而言，顺序查找的效率更高.青蛙过河案例中，如果河中没有石柱，有y片荷叶的话，那么从左岸到右岸 可以过去（）只青蛙。y+1只（正确答案）y+2 只y+3 只y+4 只.青蛙过河案例中，如果河中有1根石柱，问最少有几片荷叶就能过4只青蛙 （）01片（正确答案）

6、3片0片2片.某些排序存在不相邻记录之间的交换，因此是不稳定排序，以下是不稳定的 排序是（）oA:快速排序（正确答案）B:冒泡排序C:直接插入排序D:都不对.从算法的时间复杂度来看，0（nlog2n）是哪种排序的时间复杂度（）。A:快速排序（正确答案）B:直接插入排序C:简单项选择择排序D：冒泡排序.简单项选择择排序中，每一趟选择最小的记录的过程，那么每一趟排序的时间复 杂度是O o0（n）（正确答案）O（nn）0（1）0（nlog2n）. 10个记录进行简单项选择择排序，需要（）趟排序。9（正确答案）810D:都不对.采用简单项选择择排序，共有N个记录，每趟最多进行（）次交换。1（正确答案）

7、2N-2N-1.快速排序在（）情况下不利于发挥其长处或优势。A:记录有相同的关键字时B:记录完全乱序时C:记录已经基本有序时（正确答案）D:记录的关键字较大时.改进的顺序查找方法比原来的顺序查找法优势在于（）oA:查找次数减少B:比拟次数大量减少（正确答案）C:时间复杂度降低D:都不对.快速排序按照选择第一个记录当中轴，从小到大排序，原始序列是：25 17 39 42 22 19 30,那么经过一趟快速排序后的结果是（）。19 17 22 25 42 39 30（正确答案）17 19 22 25 30 39 42C: 17 19 22 25 42 39 30D: 19 17 22 25 30

8、39 42直接插入排序，按照从小到大排序，原始序列是：18 19 20 16 14 13,那么 经过一趟排序后的结果是O 0n个记录，使用改进的冒泡排序，即按照一趟排序之内假设不存在记录交 换，那么停止排序的方法，按从小到大排序，最坏情况比拟次数为O on（n-1）/2（正确答案）n-1nnn（n-1）n个记录，使用改进的冒泡排序，即按照一趟排序之内假设不存在记录交 换，那么停止排序的方法，按从小到大排序，最好情况比拟次数为O on（n-l）/2nT （正确答案）nnn（n-1）.快速排序与冒泡排序是（）排序。A:同一类（正确答案）B:不同类C:不确定D:都不对.改进的冒泡排序的任一趟排序过程

9、中，如果没有发生（），那么说明已经有 序；排序完毕。A:数据交换（正确答案）B:数据删除C:数据增加D:数据修改N个记录进行冒泡排序最多需要()趟排序，可以完成排序。NT (正确答案)NN-2(N+D/222.ttinclude stdio.h;int fun(int i)if (i=l)return 1;elsereturn ifun(i-1);void main ()(int n;n=fun(3);printf (%d, n);子程序的递归边界是i是几的时候()。单项选择题A:是0B:是1(正确答案)C:是2D:是323青蛙过河案例中，如果河中有1根石柱，问最少有几片荷叶就能过4只青 蛙(

10、)。A: 1片(正确答案)B:3片C:0片D:2片24程序调用自身的编程技巧，称为（）。A:数组B:函数C:递归（正确答案）D:排序25某些排序存在不相邻记录之间的交换，因此是不稳定排序，以下是不稳定 的排序是（）oA:快速排序（正确答案）B:冒泡排序C:直接插入排序D:都不对.一趟快速排序是选择一个中轴，将小于中轴位置记录的调到它的左边，大 于的调到它的O oA:右边（正确答案）B:左边C:两边D:都不对. 10个记录进行简单项选择择排序，需要（）趟排序。A: 9（正确答案）B:8C:10D:都不对28.采用简单项选择择排序，共有N个记录，每趟最多进行（）次交换。1（正确答案）B:2C:N-

11、2D:N-129.快速排序按照选择第一个记录当中轴，从小到大排序，原始序列是：25 1739 42 2239 42 221930,那么经过一趟快速排序后的结果是（）oA:19172225423930（正确答案）B:17192225303942C:17192225423930D:1917222530394230.直接插入排序,30.直接插入排序,按照从小到大排序,原始序列是：18 19 20 16 14 13,那么经过一趟排序后的结果是（）oA:13A:131416181920B:181920161413（正确答案）C:181920141613D:13181920141631 .快速排序在情况下

12、不利于发挥其长处或优势。A:记录有相同的关键字时B:记录完全乱序时C:记录已经基本有序时（正确答案）D:记录的关键字较大时32冒泡排序最坏的情况是，记录完全逆序，20个记录待排序需要比拟（）次 才能完成排序。A: 2019C: 18D: 190（正确答案）33、简单项选择择排序中，每一趟选择最小的记录的过程，那么每一趟排序的时间复 杂度是O oA:0（n）（正确答案）B:O（nn）C:O（1）D:0（nlog2n）.二叉排序是应用于动态查找的，其特点正确的选项是（）0A:左子树上的关键字小于根结点的关键字（正确答案）B:右子树上的关键字大于根结点的关键字（正确答案）C:右子树上的关键字大于左子

13、树上的关键字（正确答案）D:左右子树都是二叉排序树（正确答案）.从排序的大的分类上讲，属于交换排序的是（）oA:简单项选择择排序B:堆排序C:快速排序（正确答案）D:冒泡排序（正确答案）.从待排记录是否都在内存中的角度看，属于内排序的是（）。A:简单项选择择排序（正确答案）B:堆排序（正确答案）C:快速排序（正确答案）D:冒泡排序（正确答案）. 30个记录的序列进行冒泡排序，那么有可能（）oA: 29次比拟就完成排序（正确答案）B:进行29趟排序才结束排序（正确答案）C:不能完成排序D:可能10趟就结束了排序。（正确答案）38.冒泡排序的改进之处说法不对的是（）oA:增加了比拟的次数（正确答案）B:增加了比拟的趟数（正确答案）C:尽可能的减少比拟次数和趟数D: 一定会减少比拟的次数和趟数（正确答案）.青蛙过河问题要刚好过4只青蛙，那么情况可以是（）oA:没有石柱，荷叶有3片的情况（正确答案）B:石柱有1个，荷叶有1片的情况（正确答案）C:石柱有1个荷叶有2片的情况D:石柱有2个，荷叶有1片的情况.关于快速排序描述不正确的选项是（）。A:快速排序是稳定排序（正确答案）B:快速排序的时间复杂度是。（nlog2n）C:快速排序不存在不相邻的记录之间的交换（正确答案）D:快速排序的时间复杂度是O（nn）（正确答案）.青蛙跳河游戏中，假设有2个荷叶，2