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

数据结构与算法模拟试题及答案1 .对于线性结构的复习中循环队列是常用的线性结构，循环队列队头是 front,队尾是rear,队的最大空间是MAX,那么队长如何计算()。A、(rear-front+MAX)%MAX(正确答案)(rear-front)%MAXC (rear+1)%MAXfrontD> rear%MAX=front2 .链表的指针域可以有()oA、只能有一个B、可以有多个(正确答案)C、不可以有两个D、可以没有指针域3 .栈有后进先出的特性，那么入栈顺序是x, y, z的三个元素，出栈不可能的顺 序是()0A、x, y, zB、z, y, xC、y, z, xD、z,x,y (正确答案)4 .队列具有先进先出的特性，那么入队的0, P, Q顺序的三个元素，出队顺序 是()。A、0, P, Q(正确答案)B、 0, Q, PC、 Q, P, 0D、 0, Q, P5.顺序表可以存储大量密集数据，不需要额外的空间存储线性表元素之间的逻 辑关系，顺序表的存储密度是()o对（正确答案）错49 .二叉树不是树的特例。对（正确答案）错50 .二叉树和树都是线形结构。对错（正确答案）51 .满二叉树一定是一棵完全二叉树，完全二叉树也一定是满二叉树。对错（正确答案）52 .折半查找的时间复杂度是0Qog2n）。对（正确答案）错53 .次关键字能标识假设干条记录。对（正确答案）错54 .折半查找需要记录是顺序存储并且有序。对（正确答案）错55 .顺序查找即用逐一比拟的方法顺序查找关键字。对（正确答案）错56,定义二维数组int arr 2 4如果全部元素输出，共需要输出6个元素。对错（正确答案）57.二维数组定义的形式是：类型说明符数组名常量表达式1,常量表达式2。对错（正确答案）58可以使用两个下标定义的数组,称为二维数组。对（正确答案）借59 .荷兰国旗的时间复杂度与顺序表插入算法的时间复杂度是一样的。对（正确答案）错60 . strcpy和strcat的返回值类型不一样。对错（正确答案）A、1（正确答案）B、0.9C、0. 75D、0. 256 .在树中，堂兄弟是指（）oA、双亲在同一层，又不是同一个结点（正确答案）B、在树的不同的层C、和兄弟的概念一样D、以上都不对7 .在树的概念中，以下选项中关于树的深度描述正确的选项是（）oA、树的深度指各结点层次的最大值（根结点算第一层）（正确答案）B、树的深度指树的结点数C、树的深度指第一层结点数目D、无正确答案8 .关于二叉树描述正确的选项是（）oA、可以是空二叉树（正确答案）B、不能为空C、每个结点的度都必须是2D、二叉树的度可以大于29 .二叉树的先序序列是：ABCDEF；中序序列是：BDCFEA；那么其后序序列是 （）OA、 EFDCBAB、DFECBA （正确答案）C、 FEDCBAD、 EDFCBA10 .对于二叉树的遍历算法可以用选项中的哪种算法来实现，因为其定义是递 归定义的O oA、递归（正确答案）B、逆推C、回溯D、穷举11 .关于二叉树树，某完全二叉树按层次编号后，某结点是i,假设有左孩子， 那么左孩子的编号是（）oA、2i （正确答案）B、 2i+lC、 2i-lD、i/212.一颗二叉树高度为h,所有结点的度或为0,或为2,那么这颗二叉树最少有 （）个结点。单项选择题F占位符号不用管A、2hB、2h-l （正确答案）C、 2h+lD、h+113 .二叉树的先序遍历和中序遍历如下：先序遍历:EFHIGJK；中序遍历： HFIEJKGo该二叉树根的右子树的根是：（）。单项选择题A、EB、FC、G （正确答案）D、H14 .改进的顺序查找方法比原来的顺序查找法优势在于（）oA、查找次数减少B、比拟次数大量减少（正确答案）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以它构造一棵赫夫曼树，那么树高为 0,带权路径长度WPL的值为（）oA、696B、596（正确答案）C、493D、49817 .在以下结论中，正确的选项是（）o 单项选择题1）只有一个结点的二叉树的度为02）二叉树的度为23）二叉树的左右子树可任意交换4）深度为K的完全二叉树的结点个数小于或等于深度相同的满二叉树A、123B、24C、14（正确答案）D、418 .用二分（折半）查找表的元素的速度比用顺序查找法（）oA、必然快B、必然慢C、相等I）、不能确定（正确答案）19 .关于是否能查找到特定元素，以下选项中说法正确的选项是（）oA、假设查找表中存在特定元素称为查找失败B、假设查找表中存在特定元素称为查找成功（正确答案）C、假设查找表中存在特定元素称为查找中D、假设查找表中存在特定元素称为未找到20 .以下选项中是顺序查找的时间复杂度的是（）oA、0（1）B、0（n）（正确答案）C、0（n2）D、0 （log2n）22 .设树T的度为4,其中度为1, 2, 3和4的结点个数分别为4, 2, 2, 1那么 T中的叶子数不可能是（）oA、5（正确答案）B、6（正确答案）C、10D、8（正确答案）23 .在以下结论中，正确的选项是（）。A、只有一个结点的二叉树的度为0（正确答案）B、二叉树的度小于等于2（正确答案）C、二叉树的左右子树不可任意交换（正确答案）D、深度为K的完全二叉树的结点个数小于或等于深度相同的满二叉树（正确 答案）24 .深度为7的二叉树，不可能有的结点个数是（）oA、127B、255（正确答案）C、256（正确答案）D、257（正确答案）25 .二叉树的先序序列是：ABCDEF；中序序列是：BDCFEA；那么其后序序列顺序 不正确的选项是（）oA、EFDCBA （正确答案）B、 DFECBAC、FEDCBA （正确答案）D、EDFCBA （正确答案）27 .以下选项中符合折半查找的前提的是（）oA、顺序存储（正确答案）B、记录有序（正确答案）C、记录无序D、链式存储28 .关于查找表的分类，以下选项中说法正确的选项是（）oA、查找表有静态查找表法（正确答案）B、查找表有动态查找表法（正确答案）C、查找表分为混合查找表D、查找表分为物理查找表29 . 0（n）是以下哪种算法的复杂度（）oA、顺序查找（正确答案）B、顺序表删除元素（正确答案）C、顺序表插入元素（正确答案）D、单链表查找第i个元素（正确答案）30 .单链表，在s指针指向的结点后插入p指针指向的结点，指针域为next, 语句序列不正确的选项是：（）oA、 p->next=s->next; s->next=p;B、s->next=p->next; p->next=s;（正确答案）C、s->next=s->next->next; free （p）;（正确答案）D、 s->next=p; p->next=s->next; （正确答案）31 .数据结构与算法内，折半查找中，low指向低端的记录，high指向高端的 记录，每次计算中间位置mid的公式是（）oA: （low&high）/2B: （low+high）/2（正确答案）C: (low-high)/2D: low/2+high/232 .数据结构与算法内，从时间复杂度的角度来看，快速排序的时间复杂度是 ()OA: 0(nn)B: 0(nlog2n)(正确答案)C: 0(1)D:都不对33 .青蛙过河案例中，如果河中没有石柱，有3片荷叶的话，那么从左岸到右 岸可以过去()只青蛙。A: 3只B: 4只(正确答案)C: 2只D: 1只34 .数据结构与算法内，设fun(n)表示斐波那契数列的第n项的值，fun是函 数名，n是整型参数，那么根据递归思想它应等于()oA: fun(n)+fun(n-l)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 .就性能而言，希尔排序的时间复杂度是()oA: 0(nn)B: 0(nlog2n)C: 0(n)D: 0(n3/2)(正确答案)37 .数据结构与算法内，哈希表的装填因子()oA:越大，发生冲突的可能越小B:越小，发生冲突的可能越大C:与是否发生冲突无关D:越大，发生冲突的可能性越大(正确答案)38 .数据结构与算法内，二叉排序树的第5层多有多少个结点()oA: 4B: 16(正确答案)C: 32D: 839.数据结构与算法内，折半查找的时间复杂度是()-A: 0(1)B: 0Qog2n)(正确答案)C: 0(nn)D: 0(n)40素数是只能被1和它本身整除的是，以下是素数的是()oA: 12B: 7(正确答案)C: 27D: 9941 .求两个数的最大公约数，依照方式不同其时间复杂度可能是()oA: 0(n)(正确答案)B: 0(log2n)(正确答案)C: 0(nn)D: 0(1)42 .有关函数，下面描述正确的选项是（）oA:定义函数时如果在函数名前加void,表示该函数没有返回值（正确答案）B:函数的值只能通过return语句返回主调函数（正确答案）C:定义函数时函数名可以定义fun。（正确答案）D:从参数角度看函数可分为库函数和用户定义函数43 .下面关于函数调用格式正确的选项是（）oA:函数语句：如fun（nl, n2）;（正确答案）B:函数表达式：如fun（n）+3;（正确答案）C:函数参数:如printf （ "d” , fun（n）;（正确答案）D:函数定义后是无法调用的44 .回文字符串是正反都一样的英文字符串，那么下面不是回文字符串的应为OA: XYZZ（正确答案）B: XYZXYZ（正确答案）C: XXMXXD: MMNMMN（正确答案）45 .现实生活中，荷兰国旗的三种颜色是（）oA:红色（正确答案）B:白色（正确答案）C:蓝色（正确答案）D:绿色46 .树的深度和树的高度是一个概念。对（正确答案）错47 .树可以为空，而且不空时，定义具有递归性。对（正确答案）错48 .兄弟与堂兄弟的共同之处就是一定在树的同一层上。