2026年计算机专业试卷及解析

2026年计算机专业试卷及解析考试时间：______分钟总分：______分姓名：______一、单项选择题1.若一个栈的输入序列为1,2,3,4，则不可能得到的输出序列是A.1,2,3,4B.4,3,2,1C.1,3,4,2D.3,4,2,12.循环队列存储在数组A[0..m]中，则入队时的操作为A.rear=rear+1B.rear=(rear+1)%(m-1)C.rear=(rear+1)%mD.rear=(rear+1)%(m+1)3.在一个单链表中，已知q所指结点是p所指结点的直接前驱，若在p、q之间插入s结点，则执行操作A.s->next=p->next;p->next=s;B.q->next=s;s->next=p;C.p->next=s;s->next=q;D.p->next=s;s->next=q->next;4.一棵完全二叉树有1001个结点，则其叶子结点的个数为A.500B.501C.251D.2505.设森林F=(T1,T2,...,Tk)，与F对应的二叉树B的中序遍历序列为A.T1,T2,...,TkB.T2,T3,...,Tk,T1C.中序遍历序列与转换后的二叉树B的中序遍历序列相同D.中序遍历序列与转换后的二叉树B的前序遍历序列相同6.在一个无向图中，所有顶点的度数之和等于所有边数的A.1倍B.2倍C.3倍D.4倍7.设有向图G=(V,E)，顶点集V={1,2,3,4}，边集E={<1,2>,<1,3>,<2,4>,<3,4>}，则从顶点1出发的深度优先遍历序列不可能是A.1,2,4,3B.1,3,4,2C.1,2,3,4D.1,3,2,48.对一个具有n个顶点的图进行广度优先遍历，其算法的时间复杂度为A.O(n)B.O(n+e)C.O(n^2)D.O(e)9.对n个记录的文件进行快速排序，最坏情况下所需的辅助存储空间为A.O(1)B.O(log2n)C.O(n)D.O(n^2)10.下列排序算法中，排序不稳定的是A.直接插入排序B.冒泡排序C.归并排序D.基数排序11.下列序列中，是堆的是A.100,70,80,31,60,50,40B.100,70,80,31,60,50,10C.100,70,80,31,60,40,50D.100,70,80,31,50,40,6012.顺序查找法适合于存储结构为A.散列存储B.顺序存储或链接存储C.压缩存储D.索引存储13.顺序查找成功时的平均查找长度为A.NB.N/2C.(N+1)/2D.(N-1)/214.下列关于二叉排序树（BST）的说法中，正确的是A.二叉排序树的中序遍历序列一定是有序序列B.二叉排序树中不存在值相等的结点C.二叉排序树的插入操作总是发生在叶子结点D.二叉排序树的删除操作总是发生在叶子结点15.两个序列x和y，若x为y的子序列，则称它们之间存在A.拓扑序列B.最短路径C.最长公共子序列D.关键路径16.下列关于哈希查找的说法中，错误的是A.哈希函数的构造方法有多种，其中平方取中法是常用的方法之一B.冲突处理方法中，开放定址法要求哈希表的空间必须比记录集合的空间大C.链地址法适用于装填因子较大的哈希表D.哈希查找的平均查找长度与表长有关，而与记录个数无关17.下列算法中，属于分治法的是A.动态规划B.贪心算法C.归并排序D.回溯法18.下列关于稀疏矩阵压缩存储的说法中，正确的是A.三元组表可以用于存储任意稀疏矩阵B.十字链表适合存储非正方形稀疏矩阵C.稀疏矩阵的压缩存储会改变矩阵的逻辑结构D.只有当矩阵中零元素远多于非零元素时，才适合压缩存储19.设有一个100阶的对称矩阵A，采用压缩存储（以行序为主序存储下三角元素），a[1,1]为第一个元素，存储地址为1，则a[99,50]的地址为A.2475B.2476C.2477D.247820.下列关于广义表的说法中，正确的是A.广义表只能作为树的存储结构B.广义表不能为空表C.广义表的深度与所含原子元素的个数有关D.一个广义表可以是自身的一个子表21.下列关于图的存储结构说法中，正确的是A.用邻接矩阵存储图，便于统计顶点的度B.用邻接表存储图，便于统计顶点的度C.用邻接矩阵存储图，便于进行深度优先遍历D.用邻接表存储图，便于进行广度优先遍历22.在有向图中，一个顶点的入度为k1，出度为k2，则该顶点的度为A.k1B.k2C.k1+k2D.k1*k223.下列关于关键字比较次数的说法中，错误的是A.二分查找在查找成功时，关键字比较次数最多为log2n+1B.二分查找在查找成功时，关键字比较次数最少为1C.二分查找在查找失败时，关键字比较次数最多为log2n+1D.二分查找对有序顺序表进行查找，其平均查找长度为(n+1)/224.设哈希函数为H(key)=key%13，哈希表长度为14，关键字序列为{19,14,23,1,68,20,84,27,55,11}，采用线性探测法处理冲突，则23的存储位置是A.10B.11C.12D.1325.下列关于算法复杂度的说法中，正确的是A.时间复杂度与具体计算机硬件性能无关B.空间复杂度是指算法在运行过程中临时占用存储空间的大小C.最坏情况下的时间复杂度一定优于平均情况下的时间复杂度D.算法的时间复杂度是指算法执行过程中所执行的所有语句频度的总和二、多项选择题1.下列数据结构中，属于非线性结构的是A.树B.图C.栈D.队列2.下列关于栈的描述中，正确的是A.栈是一种先进后出的线性表B.栈可以在任意位置进行插入和删除操作C.栈没有专门的存储结构D.栈是受限的线性表3.下列关于链表的描述中，正确的是A.单链表中可以通过头指针访问任何一个结点B.双向链表中，每个结点都有两个指针域C.循环链表的最后一个结点的指针域指向头结点D.链表适用于频繁插入和删除的情况4.下列排序算法中，时间复杂度为O(n^2)的有A.冒泡排序B.选择排序C.快速排序D.插入排序5.下列关于二叉树遍历的说法中，正确的是A.前序遍历是先访问左子树，再访问右子树，最后访问根B.中序遍历是先访问左子树，再访问根，最后访问右子树C.后序遍历是先访问根，再访问左子树，最后访问右子树D.层次遍历是按层次从上到下，从左到右访问结点6.下列关于图的最短路径算法的说法中，正确的是A.Dijkstra算法适用于求带权有向图中单源点到其他顶点的最短路径B.Floyd-Warshall算法适用于求带权有向图中任意两点间的最短路径C.Dijkstra算法不能处理带负权边的图D.Floyd-Warshall算法的时间复杂度为O(n^3)7.下列关于哈希查找的说法中，正确的是A.哈希函数的构造应尽量使计算出的地址均匀分布B.冲突处理方法中，开放定址法要求哈希表空间大于记录空间C.链地址法不会增加哈希表的存储空间开销D.哈希查找的平均查找长度不直接依赖于表长8.下列关于B树的描述中，正确的是A.B树是一棵平衡的多路搜索树B.B树的每个结点至少有两棵子树C.B树的根结点至少有两个子树D.B树适合用于索引文件9.下列关于广义表的说法中，正确的是A.广义表是线性表的推广B.广义表的长度是指表中原子结点的个数C.广义表的深度是指表中原子结点的最大层次D.广义表可以被自身引用10.下列关于算法设计的说法中，正确的是A.算法必须有输出，也可以没有输入B.算法的可行性是指算法中的每一步操作都可以通过执行有限次实现C.算法的时间复杂度主要取决于问题的规模D.算法的空间复杂度是指算法在执行过程中所需要的辅助空间三、综合应用题1.设顺序栈S的栈顶指针top为10，栈的最大容量maxsize为20，现将元素x入栈。若入栈成功，栈顶指针top的值是多少？若栈已满，再进行入栈操作会发生什么？2.已知一棵二叉树的中序遍历序列为：D,B,E,A,F,C,G；后序遍历序列为：D,E,B,H,G,C,F,A。请画出这棵二叉树，并写出该二叉树的前序遍历序列。3.设有向图G=(V,E)，其中V={1,2,3,4,5}，E={<1,2>,<1,3>,<2,4>,<3,4>,<3,5>,<4,5>}。请画出该有向图的邻接表表示，并从顶点1出发进行深度优先遍历，写出所有可能的遍历序列。4.已知序列{49,38,65,97,76,13,27,50}，请使用快速排序算法对该序列进行排序。请写出第一趟排序的结果，并说明第一趟排序的基准元素选取的是什么。5.设有一个有序表R[0..9]，其关键字分别为{5,13,19,21,37,56,64,75,80,92}。现利用二分查找算法查找关键字21，请写出查找过程中比较的序列（用下标表示），并回答查找成功时需要进行多少次比较。6.已知一个稀疏矩阵A，其三元组表（row,col,value）存储如下，请画出该稀疏矩阵，并写出其转置矩阵的三元组表表示。(0,1,12),(0,3,9),(1,0,3),(2,2,5),(3,0,6)7.设哈希函数为H(key)=key%13，哈希表长度为14，关键字序列为{19,14,23,1,68,20,84,27,55,11}。请画出采用链地址法处理冲突的哈希表，并计算该哈希表的平均查找长度（ASL）。8.设有一个顺序存储的循环队列CQ，其数组容量为maxsize=10，队头指针front和队尾指针rear的初始值均为0。现进行如下操作：(1)元素A,B,C,D,E依次入队；(2)执行出队操作两次，取出元素；(3)元素F,G入队；(4)