商丘学院软件工程专业大二2017年数据结构与算法模拟试题1VIP

1、商丘学院软件工程专业大二2017年数据结构与算法模拟试题1您的姓名： 填空题 *_1.对于线性结构的复习中循环队列是常用的线性结构，循环队列队头是front，队尾是rear，队的最大空间是MAX，则队长如何计算（）。 单选题 *A、(rear-front+MAX)%MAX(正确答案)B、(rear-front)%MAXC、(rear+1)%MAX=frontD、rear%MAX=front2.链表的指针域可以有（）。 单选题 *A、只能有一个B、可以有多个(正确答案)C、不可以有两个D、可以没有指针域3.栈有后进先出的特性，那么入栈顺序是x,y,z的三个元素，出栈不可能的顺序是（）。 单选题

2、*A、x,y,zB、z,y,xC、y,z,xD、z,x,y(正确答案)4.队列具有先进先出的特性，那么入队的O，P，Q顺序的三个元素，出队顺序是（）。 单选题 *A、O，P，Q(正确答案)B、O，Q，PC、Q，P，OD、O，Q，P5.顺序表可以存储大量密集数据，不需要额外的空间存储线性表元素之间的逻辑关系，顺序表的存储密度是（）。 单选题 *A、1(正确答案)B、0.9C、0.75D、0.256.在树中，堂兄弟是指（）。 单选题 *A、双亲在同一层，又不是同一个结点(正确答案)B、在树的不同的层C、和兄弟的概念一样D、以上都不对7.在树的概念中，下列选项中关于树的深度描述正确的是（）。 单选题

3、 *A、树的深度指各结点层次的最大值(根结点算第一层)(正确答案)B、树的深度指树的结点数C、树的深度指第一层结点数目D、无正确答案8.关于二叉树描述正确的是（）。 单选题 *A、可以是空二叉树(正确答案)B、不能为空C、每个结点的度都必须是2D、二叉树的度可以大于29.二叉树的先序序列是：ABCDEF；中序序列是：BDCFEA；则其后序序列是（）。 单选题 *A、EFDCBAB、DFECBA(正确答案)C、FEDCBAD、EDFCBA10.对于二叉树的遍历算法可以用选项中的哪种算法来实现，因为其定义是递归定义的（） 。 单选题 *A、递归(正确答案)B、逆推C、回溯D、穷举11.关于二叉树树

4、，某完全二叉树按层次编号后，某结点是i，若有左孩子，则左孩子的编号是（）。 单选题 *A、2i(正确答案)B、2i+1C、2i-1D、i/212.一颗二叉树高度为h，所有结点的度或为0，或为2，则这颗二叉树最少有（）个结点。单选题 单选题 *F占位符号不用管A、2hB、2h-1(正确答案)C、2h+1D、h+113.二叉树的先序遍历和中序遍历如下：先序遍历:EFHIGJK；中序遍历：HFIEJKG。该二叉树根的右子树的根是:（）。单选题 单选题 *A、EB、FC、G(正确答案)D、H14.改进的顺序查找方法比原来的顺序查找法优势在于（）。 单选题 *A、查找次数减少B、比较次数大量减少(正确答

5、案)C、时间复杂度降低D、都不对15.删除p指针指向结点的后继结点并回收空间，指针域为next，语句序列是：（）。 单选题 *A、p->next=p->next->next;B、p->next=p->next->next;free(p);C、q=p->next;p->next=p->next->next;free(q);(正确答案)D、q=p->next->next;p->next->next=p->next->next;free(q);16.给定一组数据6，2，7，10，3，12以它构造一棵赫夫曼

6、树，则树高为()，带权路径长度WPL的值为（）。 单选题 *A、696B、596(正确答案)C、493D、49817.在下列结论中，正确的是（）。单选题1）只有一个结点的二叉树的度为02）二叉树的度为23）二叉树的左右子树可任意交换4）深度为K的完全二叉树的结点个数小于或等于深度相同的满二叉树 单选题 *A、123B、24C、14(正确答案)D、418.用二分(折半)查找表的元素的速度比用顺序查找法（）。 单选题 *A、必然快B、必然慢C、相等D、不能确定(正确答案)19.关于是否能查找到特定元素，下列选项中说法正确的是（）。 单选题 *A、若查找表中存在特定元素称为查找失败B、若查找表中存在

7、特定元素称为查找成功(正确答案)C、若查找表中存在特定元素称为查找中D、若查找表中存在特定元素称为未找到20.下列选项中是顺序查找的时间复杂度的是（）。 单选题 *A、O(1)B、O(n)(正确答案)C、 O(n2)D、O(log2n)22.设树T的度为4，其中度为1，2，3和4的结点个数分别为4，2，2，1则T中的叶子数不可能是（）。 *A、5(正确答案)B、6(正确答案)C、10D、8(正确答案)23.在下列结论中，正确的是（）。 *A、只有一个结点的二叉树的度为0(正确答案)B、二叉树的度小于等于2(正确答案)C、二叉树的左右子树不可任意交换(正确答案)D、深度为K的完全二叉树的结点个数

8、小于或等于深度相同的满二叉树(正确答案)24.深度为7的二叉树，不可能有的结点个数是（）。 *A、127B、255(正确答案)C、256(正确答案)D、257(正确答案)25.二叉树的先序序列是：ABCDEF；中序序列是：BDCFEA；则其后序序列顺序不正确的是（）。 *A、EFDCBA(正确答案)B、DFECBAC、FEDCBA(正确答案)D、EDFCBA(正确答案)27.下列选项中符合折半查找的前提的是（）。 *A、顺序存储(正确答案)B、记录有序(正确答案)C、记录无序D、链式存储28.关于查找表的分类，下列选项中说法正确的是（）。 *A、查找表有静态查找表法(正确答案)B、查找表有动态

9、查找表法(正确答案)C、查找表分为混合查找表D、查找表分为物理查找表29.O(n)是以下哪种算法的复杂度（）。 *A、顺序查找(正确答案)B、顺序表删除元素(正确答案)C、顺序表插入元素(正确答案)D、单链表查找第i个元素(正确答案)30.单链表，在s指针指向的结点后插入p指针指向的结点，指针域为next，语句序列不正确的是：（）。 *A、p->next=s->next; s->next=p;B、s->next=p->next; p->next=s;(正确答案)C、s->next=s->next->next; free(p);(正确答案)D

10、、s->next=p; p->next=s->next;(正确答案)31.数据结构与算法内，折半查找中，low指向低端的记录，high指向高端的记录，每次计算中间位置mid的公式是（）。 单选题 *A: (low&high)/2B: (low+high)/2(正确答案)C: (low-high)/2D: low/2+high/232.数据结构与算法内，从时间复杂度的角度来看，快速排序的时间复杂度是（）。 单选题 *A: O(n*n)B: O(nlog2n)(正确答案)C: O(1)D: 都不对33.青蛙过河案例中，如果河中没有石柱，有3片荷叶的话，那么从左岸到右岸可以

11、过去（）只青蛙。 单选题 *A: 3只B: 4只(正确答案)C: 2只D: 1只34.数据结构与算法内，设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)35.数据结构与算法内，改进的冒泡排序的任一趟排序过程中，如果没有发生（），则说明已经有序；排序完毕。 单选题 *A: 数据交换(正确答案)B: 数据删除C: 数据增加D: 都不对36.就性能而言，希尔排序的时间

12、复杂度是（）。 单选题 *A: O(n*n)B: O(nlog2n)C: O(n)D: O(n3/2)(正确答案)37.数据结构与算法内，哈希表的装填因子（）。 单选题 *A: 越大，发生冲突的可能越小B: 越小，发生冲突的可能越大C: 与是否发生冲突无关D: 越大，发生冲突的可能性越大(正确答案)38.数据结构与算法内，二叉排序树的第5层多有多少个结点（）。 单选题 *A: 4B: 16(正确答案)C: 32D: 839.数据结构与算法内，折半查找的时间复杂度是（）。 单选题 *A: O(1)B: O(log2n)(正确答案)C: O(n*n)D: O(n)40素数是只能被1和它本身整除的是

13、，以下是素数的是（）。 单选题 *A: 12B: 7(正确答案)C: 27D: 9941. 求两个数的最大公约数，依照方式不同其时间复杂度可能是（）。 *A: O(n)(正确答案)B: O(log2n)(正确答案)C: O(n*n)D: O(1)42.有关函数，下面描述正确的是（）。 *A: 定义函数时如果在函数名前加void,表示该函数没有返回值(正确答案)B: 函数的值只能通过return语句返回主调函数(正确答案)C: 定义函数时函数名可以定义fun。(正确答案)D: 从参数角度看函数可分为库函数和用户定义函数43.下面关于函数调用格式正确的是（）。 *A: 函数语句：如fun(n1,n

14、2);(正确答案)B: 函数表达式：如 fun(n)+3;(正确答案)C: 函数参数：如 printf(“%d”,fun(n);(正确答案)D: 函数定义后是无法调用的44.回文字符串是正反都一样的英文字符串，那么下面不是回文字符串的应为（）。 *A: XYZZ(正确答案)B: XYZXYZ(正确答案)C: XXMXXD: MMNMMN(正确答案)45. 现实生活中，荷兰国旗的三种颜色是（）。 *A: 红色(正确答案)B: 白色(正确答案)C: 蓝色(正确答案)D: 绿色46.树的深度和树的高度是一个概念。 判断题 *对(正确答案)错47.树可以为空，而且不空时，定义具有递归性。 判断题 *对

15、(正确答案)错48.兄弟与堂兄弟的共同之处就是一定在树的同一层上。 判断题 *对(正确答案)错49.二叉树不是树的特例。 判断题 *对(正确答案)错50.二叉树和树都是线形结构。 判断题 *对错(正确答案)51.满二叉树一定是一棵完全二叉树，完全二叉树也一定是满二叉树。 判断题 *对错(正确答案)52.折半查找的时间复杂度是O(log2n) 。 判断题 *对(正确答案)错53.次关键字能标识若干条记录。 判断题 *对(正确答案)错54.折半查找需要记录是顺序存储并且有序。 判断题 *对(正确答案)错55.顺序查找即用逐一比较的办法顺序查找关键字。 判断题 *对(正确答案)错56. 定义二维数组int arr24如果全部元素输出，共需要输出6个元素。 判断题 *对错(正确答案)57.二维数组定义的形式是：类型说明符 数组名常量表达式 1,常量表达式 2。 判断题 *对错(正确答案)58可以使用两个下标定义的数组,称为二维数组。 判断题 *对(正确答案)错59.荷兰国旗的时间复杂度与顺序表插入算法的时