数据结构与算法模拟测试题附答案

数据结构与算法模拟测试卷附答案1.散列表的地址区间为0-17,散列函数为H(K)=Kmod17。采用线性探测法处理冲突，并将关键字序列26，25，72，38，8，18，59依次存储到散列表中。则元素59存放在散列表中的地址是()。A:9B:11(正确答案)C:10D:82.二叉排序树的叶子结点个数为5个，则度为2的结点的数目是()。A:6B:5C:4(正确答案)D:33.N个记录采用直接插入排序的最好的情况是记录完全有序，只要比较()次，不需要插入就可以排序完成。A:NB:N-1(正确答案)C:N-2D:N(N-1)/24.就性能而言，希尔排序的时间复杂度是()。A:O(nn)B:O(nlog2n)C:O(n)D:O(n3/2)(正确答案)5.改进的冒泡排序的任一趟排序过程中，如果没有发生()，则说明已经有序；排序完毕。A:数据交换(正确答案)B:数据删除C:数据增加D:数据修改6.从算法的时间复杂度来看，O(nlog2n)是哪种排序的时间复杂度()。A:快速排序(正确答案)B:直接插入排序C:简单选择排序D:冒泡排序7.N个记录，采用简单选择排序，每趟最多进行()次交换。A:1(正确答案)B:2C:N-2D:N-18.希尔排序是根据增量，将所有记录分为若干个组，每组采用()排序进行排序。A:直接插入排序(正确答案)B:冒泡排序C:快速排序D:简单选择排序9.程序调用自身的编程技巧，称为()。A:数组B:函数C:递归(正确答案)D:排序10.青蛙过河案例中，如果河中没有石柱，有y片荷叶的话，那么从左岸到右岸可以过去()只青蛙。A:y+1只(正确答案)B:y+2只C:y+3只D:y+4只11.关于素数描述正确的是()。A:素数就是合数B:素数不能被本身整除C:素数又称为质数只能被1和它本省整除(正确答案)D:素数不仅能被1和它本身整除，还能被其它数整除12.下列关于break语句描述错误的是()。A:当break用于单层循环中时，可以终止循环.B:break用于switch语句中与case搭档，跳出switch语句C:if(i%2==0)break;执行语句后如果i的值是6则结果条件判断.(正确答案)D:for(i=1;i<=10;i++)if(i%2==0)break;如果i的值是2则退出循环13.已知do…while结构的基本语法如下

do

{

语句

}while(表达式);

下面对于do…while的叙述正确的是()。A:{}里面的语句只能放一条语句。B:while后面小括号里的表达式只能放关系表达式。C:while小括号后面的分号可以省略D:while小括号后面的分号不可以省略(正确答案)14.鸡兔同笼是一个历史悠久的问题，早在中国的数学典籍()中就有记载：“今有雉(鸡)兔同笼，上有三十五头，下有九十四足。问雉兔各几何。A:孙子算经(正确答案)B:孙子兵法C:九章算术D:九章算经15.一个大人一餐吃2个面包，两个小孩一餐吃1个面包，现在有大人和小孩共99人，一餐刚好吃了99个面包，大人、小孩各有多少人()。A:大人33人，小孩66人(正确答案)B:大人66人，小孩33人C:大人22人，小孩77人D:大人44人，小孩55人16.一根绳子有320米长，每天截取12米，问多少天后绳子长度不足40米？其代码编写如下：voidmain()

{

intcount=0,len=320;

while(len>=40)

{

（填空）;

printf("%d\t",len);

count++;

}

printf("\n总计需要%d天后绳子的长度不足40米\n",count);

}则填空处应该填写的语句序列是()。A:len=len-12;(正确答案)B:len=len+12;C:len=12;D:len-1217.以下是汉诺塔问题算法：#include"stdio.h"

intstep=1;

voidmove(intm,charp,charq,charr)

{

if(m==1)//如果m为1，则为直接可解结点

{

printf("第%d步move1#from%cto%c\n",step,p,r);

step++;

}

else

{

move(m-1,p,r,q);

printf("第%d步move%d#from%cto%c\n",step,m,p,r);

step++;

(填空);

}

}则填空处应填写的语句是()。A:move(m-1,q,p,r)(正确答案)B:move(m-1,p,r,q)C:move(m,p,r,q)D:move(m,q,p,r)18.关于回文字符串，描述正确的是()。A:回文字符串的长度一定是奇数B:回文字符串的长度一定是偶数C:回文字符串的长度可以是奇数也可以是偶数(正确答案)D:回文字符串只要求首尾字母是一样的。19.荷兰国旗算法的时间复杂度是()。A:O(1)B:O(n)(正确答案)C:O(nlog2n)D:O(nn)20.小明的烦恼算法的时间复杂度是()。A:O(1)B:O(n)C:O(nlog2n)D:O(nn)(正确答案)21.已知一棵树是二叉排序树，则该树具有()的特点。A:若左子树不为空，则左子树上的所有结点的值(关键字)都小于根节点的值；(正确答案)B:若右子树不为空，则右子树上的所有结点的值(关键字)都大于根节点的值；(正确答案)C:左、右子树都分别为二叉排序树。(正确答案)D:其中序序列是一个非递减有序序列。(正确答案)22.O(n)是以下哪种算法的复杂度()。A:顺序查找(正确答案)B:顺序表删除元素(正确答案)C:顺序表插入元素(正确答案)D:单链表查找第i个元素(正确答案)23.装填因子的计算方法是()。A:1-(表中未填入记录的数目/哈希表的总长度)(正确答案)B:表中未填入记录的数目/哈希表的总长度C:(表中未填入的记录数-1)/哈希表的总长度D:表中填入的记录数/哈希表的总长(正确答案)24.哈希表的平均查找长度与哪些()因素有关。A:处理冲突的方法(正确答案)B:哈希函数(正确答案)C:装填因子(正确答案)D:待存记录的大小25.按照待排记录是否全部在内存中，排序可分为()。A:外部排序(正确答案)B:内部排序(正确答案)C:归并排序D:基数排序26.关于希尔排序描述正确的是()。A:希尔排序是不稳定排序(正确答案)B:希尔排序是属于插入排序(正确答案)C:希尔排序的时间复杂度是O(n3/2)(正确答案)D:希尔排序又称为缩小增量排序(正确答案)27.从排序大类上看，属于选择排序的是()。A:简单选择排序(正确答案)B:堆排序(正确答案)C:快速排序D:冒泡排序28.下列排序中属于不稳定排序的有()。A:快速排序(正确答案)B:直接插入排序C:简单选择排序(正确答案)D:希尔排序(正确答案)29.快速排序的特性描述正确的是()。A:快速排序是稳定排序B:快速排序不稳定排序(正确答案)C:快速排序的时间复杂度是O(nlog2n)(正确答案)D:快速排序的时间复杂度是O(nn)30.以下不是汉诺塔问题的时间复杂度的是()。A:O(1)(正确答案)B:O(n)(正确答案)C:O(nn)(正确答案)D:O(2的n次幂)31.若哈希表的装填因子α<1，则可避免冲突的产生。对错(正确答案)32.二叉排序树的充要条件：二叉排序树的任意结点的关键字都大于其左孩子的关键字，且小于其右孩子的关键字。对错(正确答案)33.直接插入排序必须需要使用return语句才能实现。对错(正确答案)34.希尔排序是不稳定排序是因为存在不相邻的元素之间的交换。对(正确答案)错35.冒泡排序需要比较不相邻元素之间的大小，以便交换。对错(正确答案)36.快速排序在