(九月度)数据结构与算法月考测试1附有答案

(九月度)数据结构与算法月考测试1[复制]您的姓名：[填空题]*_________________________________1.12个待排记录，使用直接插入排序需要（）趟能完成全部排序。[单选题]*A:11(正确答案)B:12C:10D:都不对2.折纸问题是一种（）问题。[单选题]*A:迭代问题(正确答案)B:递归问题C:分治问题D:穷举问题3.在各种查找方法中，平均查找长度ASL与结点个数n无关的查找方法是（）。[单选题]*A:顺序查找B:折半查找C:哈希查找(正确答案)D:分块查找4.数据结构与算法内，设fun(n)表示斐波那契数列的第n项的值，fun是函数名，n是整型参数，那么根据递归思想它应等于（）。[单选题]*A:fun(n)+fun(n-1)B:fun(n-1)+fun(n-2)(正确答案)C:fun(n-1)*fun(n-2)D:fun(n-2)+fun(n-3)5.汉诺塔问题是是一类（）问题。[单选题]*A:递归(正确答案)B:分治C:穷举D:迭代6.对于二叉树的遍历：先访问根结点，再访问左子树，最后访问右子树，则是（）。[单选题]*A:中序遍历B:先序遍历(正确答案)C:后序遍历D:按层次遍历7.青蛙过河案例中，如果河中有1根石柱，有1片荷叶的话，那么从左岸到右岸可以过去（）只青蛙。[单选题]*A:3只B:4只(正确答案)C:2只D:1只8.关于二叉树树，某完全二叉树按层次编号后，某结点是i，若有左孩子，则左孩子的编号是（）。[单选题]*A:2i(正确答案)B:2i+1C:2i-1D:i/29.荷兰国旗算法的时间复杂度是（）。[单选题]*A:O(1)B:O(n)(正确答案)C:O(nlog2n)D:O(n*n)10.下面程序执行后的结果是(

)。[单选题]

#include"stdio.h"

voidmain()

{

intarr[4][4]={{2,2,3,4},{5,6,7,8},{9,10,11,12},{13,14,15,15}},i,sum=0;

for(i=0;i<4;i++

{

sum=sum+arr[i][i];

}

printf("%d",sum);

}[单选题]*A28B34(正确答案)C40D1011.单链表中删除p指针指向结点的后继(假设存在)的语句序列正确的是（）。[单选题]*A:p->next=p->next;B:p->next=p->next->next;(正确答案)C:p->next=p;D:p=p->next;12.变量height要比原来少15，则应写成（）。[单选题]*A:height-15B:height=15C:height=-15D:height-=15(正确答案)13.下列选项中关于栈和队列理解正确的是（）。[单选题]*A:栈和队列是操作受限的线性结构(正确答案)B:栈和队列是先进先出的线性结构C:栈和队列是后进先出的线性结构D:栈和队列是先进后出的线性结构14.顺序表删除元素的时间复杂度是（）。[单选题]*A:O(1)B:O(n)(正确答案)C:O(n*n)D:都不对15.鸡兔同笼算法具有算法的每一步都是确定没有二义性，这是（）。[单选题]*A:有穷性B:确定性(正确答案)C:可行性D:正确性16.C结点有3个堂兄弟(不算自己)，B是C的双亲，则B的度是（）。[单选题]*A:0B:4C:3D:不确定，至少大于等于1(正确答案)17.在树的术语中，某结点挂接的子树的数目称为（）。[单选题]*A:结点的度(正确答案)B:树的度C:树的深度D:无正确答案18.装填因子又称为（）。[单选题]*A:负载因子(正确答案)B:平衡因子C:外力因子D:合力因子19.二叉树的遍历算法可以用（）算法来实现，因为其定义是递归定义的。[单选题]*A:递归(正确答案)B:逆推C:回溯D:分治20.直接插入排序的稳定性和希尔排序的稳定性是（）。[单选题]*A:一样的B:不一样(正确答案)C:可能一样也可能不一样D:不确定21.快速排序的特性描述正确的是（）。*A:快速排序是稳定排序B:快速排序不稳定排序(正确答案)C:快速排序的时间复杂度是O(nlog2n)(正确答案)D:快速排序的时间复杂度是O(n*n)22.二叉树转换为树需要哪些步骤（）。*A:去线(正确答案)B:加线(正确答案)C:调整角度(正确答案)D:遍历一遍23.数据结构与算法里，顺序表的查找有_和_（）。*A:顺序查找(正确答案)B:折半查找(正确答案)C:随机查找D:索引查找24.有以下程序main()

{

inta[2][4]={1,12,3,4,5,6,7,9};

printf("%d",a[1][3]);

}则程序的输出结果不可能是（）。[多选题]*A:6(正确答案)B:9C:7(正确答案)D:5(正确答案)25.while循环小括号的表达式类型可以是（）。*A:整型表达式(正确答案)B:关系表达式(正确答案)C:逻辑表达式(正确答案)D:算术表达式(正确答案)26.串是一种特殊的线性结构，串的操作可以有（）。*A:截取字串(正确答案)B:串判空(正确答案)C:连接字符串(正确答案)D:定位子串在主串中的位置(正确答案)27.下列选项中关于二叉树的遍历和恢复说法正确的是（）。*A:先序序列和中序序列已知，可以恢复二叉树(正确答案)B:中序序列和后序序列已知，可以恢复二叉树(正确答案)C:先序序列和后序序列已知，可以恢复二叉树D:无正确答案28.完全二叉树中，结点个数为n，则编号最大的分支结点的编号不可能为（）。*A:n/2向下取整B:n/2向下取整+1(正确答案)C:n/2向下取整+2(正确答案)D:n/2向下取整-1(正确答案)29.排序是稳定排序或不稳排序的插入排序是（）。*A:希尔排序(正确答案)B:直接插入排序(正确答案)C:堆排序D:快速排序30.按照排序中具有相同关键字的记录在排序前后的相对位置是否发生改变，排序分为（）。*A:稳定排序(正确答案)B:不稳定排序(正确答案)C:外部排序D:内部排序31.荷兰国旗算法的时间复杂度是O(n)。[判断题]*对(正确答案)错32.简单选择排序在一趟排序，找到最小值后最多进行一次交换。[判断题]*对(正确答案)错33.栈的使用很广泛，它的特性是先进先出。[判断题]*对错(正确答案)34.while语句是先计算表达式的值，再执行循环体，do…while是执行完一次循环体，再计算表达式的值。[判断题]*对(正确答案)错35.快速排序和希尔排序都是不稳定的排序，即排序前后关键字相同的记录的相对位置发生了改变。[判断题]*对(正确答案)错36.链表的每个结点由数据域和指针域，指针域只有一个的链表称为单链表。[判断题]*对(正确答案)错37.C语言中，do-while语句和while语句完全可以互相替换。[判断题]*对(正确答案)错38.对不同的关键字可能得到同一哈希地址