ACM初赛综合试题及解析答案

ACM初赛综合试题及解析答案考试时间：______分钟总分：______分姓名：______一、单项选择题1.在C++语言中，若定义inta=10,b=20;charc='A';，则表达式a+b*c的值及其类型是A.170,intB.170,charC.250,intD.250,char2.下列关于栈的说法中，正确的是A.栈是一种先进先出的线性表B.栈只能在栈顶进行插入和删除操作C.栈的插入操作称为出栈D.栈的存储结构只能是顺序存储3.以下哪个排序算法在最坏情况下的时间复杂度为O(n²)？A.快速排序B.归并排序C.冒泡排序D.堆排序4.若一个二叉树的前序遍历序列为ABC，中序遍历序列为BAC，则其后序遍历序列为A.ACBB.BCAC.BACD.CBA5.给定序列[3,5,2,4,1]，使用堆排序进行建堆（大顶堆）的过程，第一次调整后的数组状态最接近于A.[5,3,2,4,1]B.[5,4,2,3,1]C.[5,3,4,2,1]D.[5,1,2,4,3]6.在图论中，一个有向图的邻接矩阵是一个n阶方阵，若第i行第j列的元素为1，则表示A.顶点i与顶点j之间有边，且i是j的邻接点B.顶点i与顶点j之间有边，且i是j的前驱C.顶点i与顶点j之间有边，且i是j的后继D.顶点i与顶点j之间无边7.以下算法的时间复杂度分析正确的是（n表示问题规模）A.冒泡排序的时间复杂度是O(n)B.二分查找的时间复杂度是O(logn)C.矩阵乘法的时间复杂度是O(n²)D.求解斐波那契数列递归算法的时间复杂度是O(n)8.若要实现“后进先出”的数据结构，最合适的数据结构是A.队列B.串C.栈D.树9.给定一个包含n个元素的数组，使用快速排序进行分区操作，基准值pivot选为数组中间位置的元素，则该操作的时间复杂度最接近于A.O(1)B.O(logn)C.O(n)D.O(n²)10.一个连通图的生成树包含原图的A.所有顶点B.所有边C.所有顶点和所有边D.所有顶点和至少一条边11.在解决“迷宫问题”时，通常使用的搜索算法是A.深度优先搜索（DFS）B.广度优先搜索（BFS）C.归并排序D.快速排序12.下列关于哈希表的说法，错误的是A.哈希冲突是指不同的关键字映射到同一个哈希地址B.处理哈希冲突的方法主要有开放定址法和链地址法C.哈希表的查找效率主要取决于哈希函数的构造D.哈希表的平均查找长度与表中记录的数量n无关13.若用邻接表表示图，则邻接表中每个结点包含两个域：邻接点域和链域，分别指向该结点的A.邻接点和下一个结点B.下一个结点和邻接点C.邻接点和前驱结点D.前驱结点和下一个结点14.以下哪组数据属于堆？A.[1,3,5,7,9]B.[9,7,5,3,1]C.[3,5,7,1,9]D.[9,1,7,3,5]15.设递归函数f(n)的定义如下：f(1)=1;f(n)=f(n-1)+2(n-1)。则f(5)的值为A.10B.11C.16D.1716.在计算机中，数据的最小存储单位是A.字节B.位C.字D.字长17.下列关于递归函数的描述，正确的是A.递归函数必须有一个明确的终止条件B.递归函数中不能包含循环语句C.递归函数的效率通常高于非递归函数D.递归函数调用结束后，返回值会自动消失18.一个无向图有n个顶点和e条边，所有顶点的度数之和等于A.nB.2eC.eD.2n19.若要求数据既能快速查找，又要求动态插入、删除，则应使用的数据结构是A.有序顺序表B.二叉排序树C.栈D.队列20.以下关于循环队列的说法，正确的是A.循环队列的入队操作和出队操作的时间复杂度都是O(1)B.循环队列的长度可以通过队头指针减去队尾指针得到C.循环队列可以解决假溢出问题D.循环队列中，队头指针总是小于队尾指针二、多项选择题21.下列排序算法中，属于稳定排序的有A.直接插入排序B.冒泡排序C.快速排序D.归并排序E.堆排序22.关于二叉树的性质，下列说法正确的有A.在任意一棵二叉树中，度为0的结点数等于度为2的结点数加1B.二叉树中不存在度大于2的结点C.完全二叉树中，编号为i的结点的左孩子编号为2iD.满二叉树一定是完全二叉树E.二叉树的前序遍历序列中，第一个结点一定是根结点23.以下关于栈的应用，描述正确的有A.函数调用时使用栈来保存返回地址B.表达式求值（如算符优先法）使用栈C.递归过程实现依赖于栈D.括号匹配检查使用栈E.线性表的链式存储结构需要使用栈来管理内存24.在数据结构中，以下哪些是线性结构？A.线性表B.栈C.队列D.树E.图25.下列关于图的遍历，说法正确的有A.深度优先遍历类似于树的先根遍历B.广度优先遍历类似于树的层序遍历C.连通图的深度优先遍历可以访问到所有顶点D.无向图的邻接矩阵是对称矩阵E.图的遍历过程中，每个顶点最多被访问两次26.下列哪些操作可以改变线性表的数据内容？A.插入B.删除C.查找D.更新E.排序27.以下哪些是动态规划算法的基本特征？A.最优子结构性质B.重叠子问题性质C.贪心选择性质D.无后效性E.递推关系28.在哈希表中，处理哈希冲突的方法有A.开放定址法B.链地址法C.再哈希法D.建立公共溢出区E.随机法29.下列关于链表的说法，正确的有A.链表中的每个结点至少包含两个域：数据域和指针域B.单链表只能从头结点开始遍历C.循环链表的最后一个结点的指针域指向头结点D.双向链表中的结点包含两个指针域E.链表在插入和删除操作时，不需要移动元素，只需修改指针30.关于时间复杂度，以下说法正确的有A.O(n)表示算法的执行时间与n成正比B.O(logn)表示算法的执行时间与n的对数成正比C.算法的平均时间复杂度一定优于最坏时间复杂度D.两个算法的时间复杂度都是O(n²)，则它们的效率相同E.算法的时间复杂度与硬件环境无关三、填空题31.在一个长度为n的顺序表中删除第i个元素（1≤i≤n），需要移动表中个元素。32.二分查找算法要求待查找的顺序表必须存储在内存中，且表中元素必须有序。33.已知一棵二叉树的前序遍历序列为ABDECFG，中序遍历序列为DBEAFCG，则其后序遍历序列为。34.对于一个具有n个顶点的无向图，若采用邻接矩阵表示，则矩阵中非零元素的个数为。35.栈的基本操作包括入栈和出栈，栈是限定在表尾进行插入和删除操作的线性表。36.快速排序算法在最好情况下的时间复杂度为，最坏情况下的时间复杂度为。37.在递归函数调用过程中，系统利用来保存函数调用的现场信息，