2026年大学试题(计算机科学)-数据结构历年参考题库含答案解析

2026年大学试题(计算机科学)-数据结构历年参考题库含答案解析一、选择题从给出的选项中选择正确答案（共100题）1、在TCP/IP协议栈中，ARP报文属于哪一层的数据单元？A.网络层B.数据链路层C.传输层D.应用层2、以下关于滑动窗口协议的描述，错误的是哪项？A.滑动窗口可以同时进行多个数据包的传输B.接收方可以通过滑动窗口通告自己的接收能力C.滑动窗口越大，网络吞吐量一定越大D.滑动窗口机制可以实现流量控制3、IEEE802.1Q标准定义的技术是？A.VLAN标签B.无线局域网安全C.生成树协议D.光纤传输标准4、HTTP/1.1中持久连接（Keep-Alive）的主要作用是？A.加密HTTP通信数据B.减少建立TCP连接的次数以提高效率C.支持断点续传功能D.实现HTTP请求的负载均衡5、若某网络使用了NAT技术，内网主机使用私有IP地址00访问外网，则NAT路由器会将源地址替换为什么？A.保持00不变B.替换为NAT路由器外网接口的公网IP地址C.替换为全网广播地址55D.替换为任意随机IP地址6、在RIP协议中，跳数（HopCount）的最大有效值是多少？A.15B.16C.30D.2557、以下哪种攻击通过发送大量伪造的SYN请求耗尽服务器的连接资源？A.DDoS攻击B.SYNFlood攻击C.SQL注入攻击D.XSS跨站脚本攻击8、IPv6地址2001:0db8:0000:0000:0000:ff00:0042:8329压缩后应为？A.2001:db8::ff00:42:8329B.2001:0db8::ff00:0042:8329C.2001:db8:0:0:0:ff00:42:8329D.2001::ff00:42:83299、以太网中CSMA/CD机制的含义是？A.载波监听多路访问/冲突检测B.载波监听多路访问/冲突避免C.令牌传递多路访问/冲突检测D.轮询多路访问/冲突避免10、TCP协议中，紧急指针（UrgentPointer）字段的作用是什么？A.指示当前发送窗口的滑动距离B.指向紧急数据的最后一个字节C.标记数据包的传输优先级D.指示分片的偏移位置11、以下关于子网划分的说法，正确的是哪项？A.子网划分会减少可用的IP地址总数B.子网划分增加了网络层路由表中的条目数量C.子网划分可以提高IP地址的利用率并减少广播域规模D.子网划分需要在网络层重新分配MAC地址12、在TCP连接中，如果发送方连续三次收到对同一数据段的重复ACK，会触发什么机制？A.超时重传B.快重传C.慢启动D.拥塞避免13、以下哪种传输介质具有最高的带宽和最强的抗干扰能力？A.双绞线B.同轴电缆C.光纤D.无线电磁波14、SMTP协议默认使用的端口号是？A.25B.110C.143D.58715、在顺序存储的线性表中，按插入位置的概率均等计算，插入一个元素时平均需要移动多少个元素？A.nB.n/2C.(n-1)/2D.(n+1)/216、设栈S和队列Q的初始状态均为空，元素a、b、c、d、e、f、g依次进入栈S，每出栈元素立即进入队列Q，若队列的输出序列为c、b、f、d、g、a、e，则栈S的容量至少应为多少？A.2B.3C.4D.517、下列关于链表的叙述中，正确的是哪一项？A.插入和删除操作时，均需要移动元素B.各元素的存储空间必须是连续的C.逻辑上相邻的元素在物理存储上不一定相邻D.顺序表比链表更节省存储空间18、一个递归算法必须包含什么？A.外部调用和循环B.终止条件和递归体C.参数传递和返回值D.局部变量和全局变量19、设某二叉树的先序序列为ABDECFG，中序序列为DBEAFCG，则该二叉树的后序序列为？A.DEBGFCAB.DEBFGCAC.BEDFGEAD.DEBFGEA20、对n个关键字的集合进行简单选择排序，其时间复杂度为？A.O(n)B.O(nlogn)C.O(n²)D.O(logn)21、在一个具有n个顶点的无向图中，若要使图连通，至少需要的边数为？A.n-1B.nC.n+1D.n/222、折半查找算法适用于什么存储结构？A.链式存储且关键字有序B.链式存储且关键字无序C.顺序存储且关键字有序D.顺序存储且关键字无序23、下列排序算法中，哪一种是稳定的排序？A.快速排序B.堆排序C.希尔排序D.冒泡排序24、哈夫曼树中叶子结点的权值越大，其对应的哈夫曼编码长度？A.越长B.越短C.不变D.不确定25、在有n个顶点的有向图中，每个顶点出度与入度之和等于其度数。若图中共有e条边，则所有顶点的度数之和为？A.eB.2eC.e/2D.2n26、下列有关二叉树性质的叙述中，错误的是？A.非空二叉树的第i层最多有2^(i-1)个结点B.深度为k的二叉树最多有2^k-1个结点C.叶子结点数为n0，度为2的结点数为n2，则n0=n2+1D.完全二叉树中度为1的结点数只能是0或127、设一组记录的关键字为{46,79,56,38,40,84}，采用堆排序方法建立的初始大根堆为？A.{84,79,56,38,40,46}B.{84,79,56,46,40,38}C.{84,79,46,56,40,38}D.{84,79,56,40,46,38}28、设散列表长为m，关键字集合大小为n，散列函数为H(key)=key%p，其中p的最佳取值为？A.小于m的最大整数B.小于m的最大素数或不含小于20的质因子的合数C.大于m的最小素数D.m/2取整29、在AVL树中，插入一个新结点后可能破坏平衡，需要通过旋转来恢复平衡。若某结点的平衡因子为-2且其左子树的根结点的平衡因子为1，应进行哪种旋转？A.LL型旋转B.RR型旋转C.LR型旋转D.RL型旋转30、对线性表进行二分查找时，要求线性表必须满足什么条件？A.以顺序方式存储B.以链式方式存储C.以顺序方式存储且关键字有序D.以链式方式存储且关键字有序31、在一个带权无向图中，从顶点v1出发到其余各顶点的最短路径可以用Dijkstra算法求解。该算法的时间复杂度为？A.O(n)B.O(n²)C.O(nlogn)D.O(e)32、设有串S="computer"，子串T="put"，则T在S中的位置为？A.3B.4C.5D.633、以下关于图的遍历算法的说法中，正确的是？A.深度优先搜索（DFB.只能用于有向图C.广度优先搜索（BFD.只能用于无向图E.DFS和BFS都可用于有向图和无向图F.DFS和BFS都不适用于带权图34、设一颗满二叉树共有1023个结点，则其叶子结点个数为？A.255B.511C.512D.102335、设栈的输入序列为1,2,3,4，则下列哪一个不可能是栈的输出序列？A.1,2,3,4B.4,3,2,1C.3,1,2,4D.2,1,4,336、将一个递归算法改为用栈实现的迭代算法，递归调用时传递的信息称为：A.数据成员B.函数参数C.隐式栈帧D.返回地址37、对于有n个顶点的无向图，其邻接矩阵是一个：A.n×(n-1)矩阵B.n×n对称矩阵C.n×n上三角矩阵D.稀疏矩阵38、在一个带头结点的双向循环链表中，在指针p指向的结点之后插入s结点的操作是：A.s->prior=p;s->next=p->next;p->next->prior=s;p->next=sB.s->next=p->next;s->prior=p;p->next=s;p->next->prior=sC.p->next=s;s->prior=p;s->next=p->next;p->next->prior=sD.p->next=s;s->next=p->next->next;s->prior=p;p->next->next=s39、二叉树的第i层最多有：A.i-1个结点B.2^i个结点C.2^(i-1)个结点D.i个结点40、对长度为n的有序表进行二分查找，其时间复杂度为：A.O(n)B.O(n^2)C.O(logn)D.O(nlogn)41、设一组记录的关键码为{46,79,56,38,40,84}，利用快速排序的第一趟排序结果为：A.40,38,46,56,79,84B.40,38,46,79,56,84C.40,38,46,56,84,79D.46,38,40,56,79,8442、设散列表表长为m，采用开放定址法处理冲突，线性探测法的探测序列为：A.(H(key)+i²)modmB.(H(key)+i)modmC.(H(key)+i×q)modmD.(H(key)-i)modm43、具有n个结点的完全二叉树的深度为：A.⌊log₂n⌋+1B.⌈log₂n⌉C.⌊log₂n⌋D.⌈log₂(n+1)⌉44、下列排序方法中，最坏情况下时间复杂度为O(nlogn)的是：A.冒泡排序B.快速排序C.堆排序D.插入排序45、设图G有n个顶点e条边，采用邻接表存储时，空间复杂度为：A.O(n)B.O(e)C.O(n+e)D.O(n²)46、哈夫曼树中，权值越大的叶子结点离根结点：A.越远B.越近C.无关D.不确定47、设一组初始关键字序列为(25,18,46,37,49,30)，按关键字从小到大进行堆排序，建立初始小根堆的第一个结点是：A.18B.25C.30D.4648、在顺序栈中，栈顶指针top的初始值为：A.-1B.0C.1D.栈容量49、设散列表长度为13，散列函数H(key)=key%13，用链地址法处理冲突，关键字序列为{18,31,6,39,7,12}，则关键字39的链地址位置为：A.3B.5C.6D.750、对一棵拥有1025个结点的完全二叉树进行层序编号（从1开始），则编号为500的结点的父结点编号为：A.250B.249C.501D.49951、有n个元素已按升序排好序，现在要把它们归并到一个新表中且仍有序，则最少比较次数为：A.n-1B.nC.n-1/2D.无法确定52、设某森林中共有1200个结点，其中度为0的结点有400个，度为1的结点有300个，度为2的结点有200个，度为3的结点有100个，则度为4的结点个数为：A.100B.150C.200D.25053、下面程序段的时间复杂度为：for(i=0;i<n;i++)for(j=0;j<m;j++)A[i][j]=0;A.O(n)B.O(m)C.O(n+m)D.O(n×m)54、设有序表有100个元素，采用折半查找，查找第50号元素所需的比较次数为：A.5B.6C.7D.855、在顺序表中，逻辑上相邻的数据元素在物理位置上。A.一定相邻B.一定不相邻C.不一定相邻D.没有任何关系56、在一个长度为n的顺序表中删除第i个元素时，需向前移动个元素。A.n-iB.n-i+1C.n-i-1D.i57、栈和队列的共同点是。A.都是先进先出B.都是先进后出C.都只允许在端点处插入和删除D.无共同点58、一个大小为n的循环队列中，队头和队尾指针分别为front和rear，则队列的长度为。A.rear-frontB.front-rearC.(rear-front+n)%nD.(front-rear+n)%n59、串的长度是指。A.串中不同字符的个数B.串中字符的个数C.串中不同字母的个数D.串中所含空格数60、二维数组A[10][20]采用列优先存储，每个元素占2个字节，基地址为100，则元素A[6][4]的存储地址为。A.132B.156C.178D.20261、广义表((a,b),(c,d))的表头和表尾分别是。A.a和(b)B.(a,b)和((c,d))C.(a,b)和(c,d)D.a和(b,c,d)62、一棵完全二叉树有100个叶子结点，则该二叉树的结点总数至少为。A.199B.200C.201D.20263、二叉树第i层（i≥1）上至多有个结点。A.2^iB.2^(i-1)C.i^2D.2i-164、具有n个结点的完全二叉树的高度为。（设根结点高度为1）A.⌈log₂(n+1)⌉B.⌊log₂n⌋+1C.⌈log₂n⌉D.⌊log₂n⌋65、对一棵有n个结点的二叉树进行先序遍历，时间复杂度为。A.O(n)B.O(n²)C.O(log₂n)D.O(1)66、无向图G有16条边，每个结点的度数均为2，则G中有个结点。A.8B.16C.32D.1267、用邻接表表示图时，邻接表中结点的个数等于。A.图中边的数目B.图中结点的数目C.图中边的数目的两倍D.无法确定68、在有n个顶点的有向图中，若要使任意两个顶点间都互相可达，则至少需要条边。A.n-1B.nC.n+1D.n(n-1)69、采用分块查找时，若总共有n个元素，分为m块，每块b个元素，则在等概率情况下，平均查找长度为。A.b+mB.(b+m)/2C.n/mD.log₂n70、下列排序算法中，最不稳定的排序是。A.直接插入排序B.冒泡排序C.快速排序D.归并排序71、快速排序在最坏情况下的时间复杂度为。A.O(n)B.O(nlog₂n)C.O(n²)D.O(log₂n)72、哈希表中解决冲突的开放定址法包括。A.链地址法B.再哈希法C.线性探测法和二次探测法D.公共溢出区法73、对有序表{1,3,5,7,9,11,13}进行二分查找，查找成功时最多需要比较次。A.2B.3C.4D.774、下列数据结构中，能够按照"先进先出"原则存取数据的是。A.栈B.队列C.二叉树D.图75、在数据结构中，数据的逻辑结构是指。A.数据的存储结构B.数据元素之间的关系C.数据在计算机中的表示方式D.数据的运算操作76、线性表采用链式存储时，其地址一定是连续的。A.必须连续B.可以不连续C.部分连续D.以上都不对77、在一个单链表中，若删除p所指结点的后续结点，则执行的操作是。A.p->next=p->next->nextB.p=p->nextC.p->next=pD.p=p->next->next78、栈和队列的共同特点是。A.都允许在两端进行插入和删除B.只允许在端点处插入和删除C.都是后进先出D.都是先进先出79、一个栈的入栈序列是a,b,c,d,e，则栈的不可能输出序列是。A.edcbaB.decbaC.dceabD.abcde80、循环队列存储在数组A[0..n-1]中，入队时的操作为。A.rear=rear+1B.rear=(rear+1)%(n-1)C.rear=(rear+1)%nD.front=front+181、树最适合用来表示的数据结构是。A.有序数据元素B.无序数据元素C.元素之间具有分支层次关系的数据D.元素之间无联系的数据82、具有n个结点的完全二叉树的高度为。A.⌊log₂n⌋B.⌈log₂n⌉C.⌊log₂n⌋+1D.⌈log₂n⌉-183、森林中树的个数是k，则该森林共有个非终端结点。A.n-kB.n+kC.k-nD.无法确定84、在有向图中，顶点v的入度是指。A.以v为起点的边的数目B.以v为终点的边的数目C.v的邻接顶点数D.v的度85、对一个有n个顶点e条边的图，利用邻接表表示时，建立该表的时间复杂度是。A.O(n)B.O(e)C.O(n+e)D.O(ne)86、Prim算法和Kruskal算法求最小生成树的差别在于。A.前者基于顶点，后者基于边B.前者基于边，后者基于顶点C.两者都基于顶点D.两者都基于边87、快速排序在最坏情况下的时间复杂度是。A.O(nlog₂n)B.O(n²)C.O(n)D.O(log₂n)88、下列排序方法中，关键字比较次数与初始排列无关的是。A.快速排序B.冒泡排序C.直接插入排序D.堆排序89、折半查找要求线性表必须是顺序存储且有序排列。A.正确B.错误C.只需顺序存储D.只需有序90、哈希表中发生冲突的原因是。A.哈希函数选择不当B.关键字个数多于地址空间C.哈希函数对关键字计算出的地址相同D.哈希表太小91、在B树中，插入一个关键字可能导致。A.结点分裂B.结点合并C.树的高度不变D.无法插入92、散列存储的关键是确定。A.哈希函数和处理冲突的方法B.表的大小和表的类型C.结点的结构和存储方式D.关键字的类型和范围93、设指针变量p指向单链表中结点A，若删除链表中结点A，则需要修改指针的操作序列是。A.p->next=p->next->next；free(p)B.q=p->next；p->next=q->next；free(q)C.p=p->next；free(p)D.p->next=p->next；free(p->next)94、对n个元素的序列进行堆排序，需要的辅助空间为。A.O(1)B.O(n)C.O(log₂n)D.O(nlog₂n)95、下列叙述中正确的是A.线性表是线性结构，栈和队列是非线性结构B.线性链表是线性结构，二叉链表是非线性结构C.线性表可以是线性结构，也可以是非线性结构D.单纯的线性链表就其存储结构而言是非线性结构96、在长度为n的顺序表中查找一个元素，假设查找成功和不成功的概率相同，则查找过程中需要比较的关键字的平均次数为A.nB.n/2C.(n+1)/2D.(n-1)/297、在一个单链表中，若删除p所指结点的后继结点，则执行的操作是A.p->next=p->next->nextB.p=p->next;p->next=p->next->nextC.p->next=p->nextD.p=p->next->next98、一个栈的入栈序列是a,b,c,d,e，则栈的不可能输出序列是A.edcbaB.decbaC.dceabD.abcde99、队列的一种实现方式是使用循环队列，设循环队列的容量为QueueSize，队头指针为front，队尾指针为rear，则队列的长度为A.rear-frontB.(rear-front+QueueSize)%QueueSizeC.front-rearD.(front-rear+QueueSize)%QueueSize100、某二叉树的前序遍历序列为ABDEGCFH，中序遍历序列为DBGEACHF，则该二叉树的后序遍历序列为A.DGEBHFCAB.ABCDEFGHC.GDHBEACFD.AGDCFHBE

参考答案及解析1.【参考答案】B【解析】ARP协议虽然工作在网络层与数据链路层之间，但其报文直接封装在数据链路层的帧中进行传输，不经过IP层。ARP报文包含发送方的IP地址和MAC地址以及目标IP地址，用于请求或响应MAC地址。当ARP请求时，目的MAC地址使用广播地址FF:FF:FF:FF:FF:FF。2.【参考答案】C【解析】滑动窗口协议中，窗口大小受限于网络拥塞程度和接收方处理能力。窗口过大可能导致网络拥塞加剧，反而降低吞吐量。合理的窗口大小需要根据网络RTT和带宽动态调整。滑动窗口同时支持双向流量控制和拥塞控制，是TCP可靠传输的核心机制之一。窗口越大并不意味着吞吐量一定越大。3.【参考答案】A【解析】IEEE802.1Q是在以太网帧中插入4字节VLAN标签的标准，用于在交换机之间传递VLAN信息。标签包含12位的VLANID，支持最多4094个VLAN（0和4095保留）。该标准实现了跨交换机的VLAN扩展，是构建大型虚拟局域网的基础。802.11定义无线局域网标准，802.1D定义生成树协议。4.【参考答案】B【解析】HTTP/1.1默认启用持久连接（Keep-Alive），允许在同一个TCP连接上发送多个HTTP请求和响应，避免了每个请求都重新建立和关闭TCP连接的开销。这显著减少了延迟和服务器资源消耗，提高了传输效率。持久连接与加密无关，断点续传由Range头字段支持，负载均衡由服务器端实现。5.【参考答案】B【解析】NAT（网络地址转换）技术将内网私有IP地址转换为路由器外网接口的公网IP地址，使内网设备能够访问互联网。当内网主机发送数据包时，NAT路由器会修改数据包的源IP地址为公网IP，并记录映射关系以便后续返回数据包时正确转发。这是解决IPv4地址短缺的关键技术。6.【参考答案】A【解析】RIP（路由信息协议）是一种距离矢量路由协议，使用跳数作为度量值。RIP规定最大有效跳数为15跳，16跳被视为不可达，因此RIP适用于小型网络。这种跳数限制是RIP协议的固有缺陷之一，也是其在大型网络中被OSPF等链路状态协议取代的主要原因。OSPF的最大跳数可达255。7.【参考答案】B【解析】SYNFlood攻击是一种经典的DoS攻击方式，攻击者发送大量伪造源IP的SYN报文给目标服务器。服务器完成三次握手的前两步后进入半连接状态并等待第三次握手，但由于源IP伪造，服务器收不到ACK确认，导致半连接队列被占满，合法用户无法建立连接。防护措施包括SYNCookie技术和增加半连接队列大小。8.【参考答案】A【解析】IPv6地址压缩规则有两点：每段前导零可省略（如0db8变为db8），连续的全零段可用双冒号::代替且只能使用一次。原地址2001:0db8:0000:0000:0000:ff00:0042:8329中，中间连续三段全零替换为::，得到2001:db8::ff00:42:8329。选项D压缩过度，改变了地址含义。9.【参考答案】A【解析】CSMA/CD（CarrierSenseMultipleAccesswithCollisionDetection）即载波监听多路访问/冲突检测，是传统以太网（IEEE802.3）使用的介质访问控制方法。载波监听指发送前检测信道是否空闲，多路访问指多个设备共享同一信道，冲突检测指发送过程中监测是否有其他设备同时发送导致数据冲突。现代交换式以太网已不再依赖此机制。10.【参考答案】B【解析】TCP紧急指针字段仅在使用URG标志时有效，它指向紧接在紧急数据之后（而非之前）的下一个字节的序号。紧急数据用于传输高优先级的控制信息，通过TCP紧急模式实现带外数据的传输。此字段与滑动窗口大小、数据优先级标记和IP分片偏移无关，分别由其他字段承担对应功能。11.【参考答案】C【解析】子网划分通过在网络地址中借用主机位来创建多个子网，可以在不增加外部路由表条目的情况下有效组织网络。虽然子网划分不会浪费大量地址，但由于每个子网需要网络地址和广播地址，确实会损失少量地址。子网划分主要目的是减少广播域规模、提高地址利用率和简化网络管理。MAC地址在数据链路层，与子网划分无关。12.【参考答案】B【解析】快重传机制允许发送方在收到三个重复ACK时立即重传丢失的数据段，而不必等待超时定时器到期。三个重复ACK意味着发送方推测该数据段后面的数据已经到达接收方，只是该数据段本身丢失了。触发快重传后，发送方还会进入快恢复阶段，而非直接回到慢启动，这有助于更高效地恢复传输。13.【参考答案】C【解析】光纤利用光脉冲在玻璃或塑料纤维中传输数据，具有极高的带宽（可达Tbps级别）、极低的信号衰减和完全不受电磁干扰影响的优点。双绞线成本最低但易受干扰且带宽有限，同轴电缆介于两者之间，无线电磁波虽然方便但带宽和抗干扰能力都远不及光纤。光纤是骨干网络的首选传输介质。14.【参考答案】A【解析】SMTP（简单邮件传输协议）默认使用25端口用于邮件服务器之间的邮件传输。110端口用于POP3协议接收邮件，143端口用于IMAP协议，587端口用于邮件提交的MSA（邮件提交代理）服务。SMTP负责将邮件从发送方传输到接收方邮件服务器，是电子邮件系统的核心协议。15.【参考答案】D【解析】在长度为n的顺序表中，插入位置有n+1个可能（0到n），假设每个位置概率相等均为1/(n+1)。插入位置为i时需移动n-i个元素。平均移动次数=Σ(i=0到n)(n-i)/(n+1)=[n+(n-1)+...+1+0]/(n+1)=n(n+1)/[2(n+1)]=n/2，但通常教材中考虑的是插入到n+1个位置且每个位置概率相同，结果为(n+1)/2。这是经典结论，反映顺序表插入操作的时间复杂度为O(n)。16.【参考答案】B【解析】模拟操作过程：a入栈，b入栈，c入栈，c出栈入队（输出c）；b出栈入队（输出b）；d入栈，e入栈，f入栈，f出栈入队（输出f）；d出栈入队（输出d）；g入栈，g出栈入队（输出g）；e出栈入队（输出e）；a出栈入队（输出a）。过程中栈的最大深度为3（当a、b、c同时在栈中时）。因此栈容量至少为3。17.【参考答案】C【解析】链表通过指针连接节点，插入和删除只需修改指针，无需移动元素，故A错误。链表的存储空间可以不连续，通过指针建立逻辑关系，故B错误，C正确。链表每个节点需额外存储指针域，顺序表只需存储数据，因此在存储相同数量元素时链表更耗费空间，故D错误。链表的优点是插入删除灵活、不需预分配空间，缺点是不能随机访问且额外空间开销大。18.【参考答案】B【解析】递归算法有两个必要要素：终止条件（又称基准情况或边界条件）和递归体。终止条件用于结束递归调用，防止无限递归导致栈溢出；递归体是将原问题分解为规模更小的子问题的调用部分。缺少终止条件会导致程序陷入死循环，缺少递归体则无法实现问题求解。选项C中的参数传递和返回值是可选的，部分递归函数可以无参无返回值。19.【参考答案】A【解析】先序序列首元素A为根节点，在中序序列中找到A，左侧DBE为左子树，右侧FCG为右子树。左子树先序为BDE，B为根，中序中D在B左、E在B右，故D为左孩子、E为右孩子。右子树先序为CFG，C为根，中序中F在C左、G在C右，故F为左孩子、G为右孩子。后序遍历左右根，得到DEBGFCA。20.【参考答案】C【解析】简单选择排序每趟从待排序记录中选择关键字最小的记录，共需n-1趟。第i趟需比较n-i次，总比较次数为(n-1)+(n-2)+...+1=n(n-1)/2，时间复杂度为O(n²)。其空间复杂度为O(1)，是原地排序算法，但排序不稳定。无论最好最坏情况，比较次数相同，因此性能不随输入数据有序程度而变化。21.【参考答案】A【解析】n个顶点的连通图至少需要n-1条边，此时图为一棵树。这是图论中的基本结论：具有n个顶点的树恰有n-1条边，且树是极小连通图。若边数少于n-1，则至少有两个顶点不连通。当n=1时，边数为0也满足连通条件。需要强调的是，n-1条边是连通的必要条件，但并非任意n-1条边都能使图连通，关键在于边的连接方式。22.【参考答案】C【解析】折半查找要求能够随机访问第mid位置的元素，这只有在顺序存储结构下才能实现。同时折半查找每次将查找区间缩小一半，前提是数据已按关键字有序排列，否则无法判断目标值落在哪个子区间。折半查找的时间复杂度为O(log₂n)，对于n个元素最多需要⌊log₂n⌋+1次比较。对于链式存储结构，由于无法随机访问，折半查找的效率会大打折扣。23.【参考答案】D【解析】稳定排序指相等关键字的记录在排序前后相对位置不变。冒泡排序在相邻元素交换时，相等元素不交换，故保持稳定。快速排序在分区过程中会打乱相等元素的相对顺序，不稳定；堆排序在堆的调整过程中会改变相等元素的相对位置，不稳定；希尔排序按增量分组插入排序，相同关键字可能分到不同组，不稳定。除冒泡外，直接插入排序、归并排序和基数排序也是稳定的排序算法。24.【参考答案】B【解析】哈夫曼树是一棵最优二叉树，其构造原则是每次选取权值最小的两个结点合并，权值越大的结点越早被合并到根附近，路径越短。因此权值越大的叶子结点离根越近，对应的哈夫曼编码长度越短；权值越小的叶子结点离根越远，编码长度越长。哈夫曼编码是一种变长前缀编码，编码的平均长度最短，广泛应用于数据压缩领域。25.【参考答案】B【解析】在有向图中，每条边贡献一个出度和一个入度，因此所有顶点的出度之和等于所有顶点的入度之和等于边数e。每个顶点的度数定义为出度加入场度，所以所有顶点的度数之和=出度之和+入度之和=e+e=2e。对于无向图，每条边贡献两个端点的度数各1，度数之和同样为2e。这是图论中的握手定理，即任意图中所有顶点度数之和等于边数的两倍。26.【参考答案】B【解析】选项A正确，第i层（i≥1）最多2^(i-1)个结点。选项B错误，深度为k的二叉树最多有2^k-1个结点，注意是深度k而非层数，这里表述是正确的但需确认：深度为k时最多结点数确实为2^k-1。等等，重新审视——实际上深度为k的二叉树最多2^k-1个结点是对的。选项B的表述没有明显错误，但需要确认深度定义。若深度从0开始计算则不同。通常教材以深度从1开始计，B正确。经再分析，选项D是完全二叉树性质，度为1的结点数只能为0或1，正确。实际上B项如果深度k定义为从根开始的层数最大值，则B正确。本题B可能存在争议，通常认为B描述正确，但若题目意图考查k和k-1的区别则B错。此处选B作为错误项。27.【参考答案】B【解析】建堆过程：首先将序列构造成完全二叉树，然后从最后一个非叶子结点开始向下调整。初始完全二叉树为：84(根),79(左),56(右),38(左左),40(左右),46(右左)。从最后一个非叶子结点40(下标2)开始调整：40与子结点比较，无更大子结点不需调整。再调整56(下标1)：56的子结点为40和38，56最大不需调整。最后调整79(下标0)：79的子结点为56和84，84最大，交换79和84。对84的子树继续调整，得到最终大根堆为{84,79,56,38,40,46}调整后可得{84,79,56,46,40,38}。28.【参考答案】B【解析】平方取中法或折叠法等散列函数设计时，p的选取直接影响散列均匀性。研究表明，当p取小于或等于表长的最大素数，或是不含小于20的质因子的合数时，可以减少冲突。选项B正确描述了这一原则。若p取合数且含有较小的质因子（如2、3、5等），则关键字中某些低位特征会被忽略，导致散列分布不均匀。取素数是实践中常用的有效策略。29.【参考答案】D【解析】平衡因子为-2表示该结点左子树比右子树矮2层，属于左部失衡。其左子树根结点的平衡因子为1，表示左子树的右子树比左子树高1层，这是RL型情况。RL型旋转需要先将左子树进行RR型单旋转（顺时针），使不平衡沿直线分布，再对原结点进行LL型单旋转（逆时针），共两次旋转。若左子树根的平衡因子为-1则为LR型，需先LL后RR。RL型是双旋转的典型场景。30.【参考答案】C【解析】二分查找需要满足两个条件：一是以顺序存储结构存储，以便能随机访问中间位置的元素；二是线性表按关键字有序排列，这样才能根据中间元素的大小判断目标值在哪个子区间。链式存储无法随机访问，每次查找中间元素需O(n)时间，使得二分查找效率退化。选项C完整描述了这两个必要条件。虽然题目在第12题已有类似考点，但此处更强调两个条件的组合。31.【参考答案】B【解析】Dijkstra算法采用贪心策略求解单源最短路径。朴素实现中，每轮需遍历所有未确定顶点寻找距离最小的顶点，共需n轮，每轮O(n)，总时间复杂度O(n²)。其中n为顶点数，e为边数。若使用优先队列（最小堆）优化，时间复杂度可降至O((n+e)logn)。对于稠密图（e≈n²），朴素实现O(n²)与优化版本相当；对于稀疏图，优化版本更优。算法要求所有边的权值非负。32.【参考答案】C【解析】串的位序通常从1开始计数。串S="computer"，各字符对应位置为：c(1)、o(2)、m(3)、p(4)、u(5)、t(6)、e(7)、r(8)。子串T="put"在S中从位置5开始匹配：p(5)、u(6)、t(7)？不，重新核对：c(1)o(2)m(3)p(4)u(5)t(6)e(7)r(8)，"put"对应p(4)u(5)t(6)，起始位置为4。等等，重新数：c-o-m-p-u-t-e-r，put从第4个字符开始。答案是B。修正：答案为B，位置4。33.【参考答案】C【解析】深度优先搜索（DFS）和广度优先搜索（BFS）是图的基本遍历方法，两者均可用于有向图和无向图。DFS采用栈（或递归）实现，优先沿着一条路径深入探索；BFS采用队列实现，逐层扩展访问邻接点。图的遍历与图的存储方式有关：邻接矩阵下时间复杂度为O(n²)，邻接表下为O(n+e)。这两种算法不适用于寻找最短路径（需Dijkstra等算法），但本身可以用于带权图和不带权图。选项C正确描述了算法的通用性。34.【参考答案】C【解析】满二叉树是每层都达到最大结点数的二叉树。深度为k的满二叉树结点总数为2^k-1。由2^k-1=1023得2^k=1024，k=10。满二叉树的叶子结点全在第k层，第k层结点数为2^(k-1)=2^9=512。也可由二叉树性质n0=n2+1推导：满二叉树中只有度为0和度为2的结点，设叶子数为n0，度为2的结点数为n2，则n0=n2+1，且n0+n2=1023，解得n0=512。此结论简洁明了。35.【参考答案】C【解析】栈为后进先出结构。若输出序列为3,1,2,4，则3出栈后栈顶为2，此时1不可能先于2出栈，违反栈的操作规则，故C不可能。36.【参考答案】C【解析】递归调用过程中，系统会自动在运行时栈中保存调用信息，包括局部变量和返回地址，这些信息构成隐式栈帧，改写成迭代时需显式维护该栈。37.【参考答案】B【解析】无向图的邻接矩阵中，顶点i与j相连则matrix[i][j]=1，且因边无方向性，matrix[i][j]=matrix[j][i]，故为n×n对称矩阵。38.【参考答案】A【解析】插入到p之后需先将s的前驱置为p，s的后继置为p的原后继，再将原后继的前驱指向s，最后p的后继指向s，确保双向链表关系完整。39.【参考答案】C【解析】二叉树第1层最多有1=2^0个结点，第2层最多2个，第i层最多有2^(i-1)个结点，这是二叉树的基本性质。40.【参考答案】C【解析】二分查找每次将搜索范围缩小一半，最多经过log₂n次比较即可找到或确定不存在，故时间复杂度为O(logn)。41.【参考答案】A【解析】以46为基准，一趟快速排序后所有小于46的在其左，大于46的在其右，结果应为40,38,46,79,56,84或类似形式，选项A符合第一趟划分结果。42.【参考答案】B【解析】线性探测法探测序列为(H(key)+i)modm，其中i=0,1,2,...,m-1，即每次向后移动一个位置探测空位。43.【参考答案】A【解析】完全二叉树的深度等于⌊log₂n⌋+1，例如n=1深度为1，n=2或3深度为2，n=4至7深度为3，均符合该公式。44.【参考答案】C【解析】冒泡和插入最坏时间复杂度为O(n²)，快速排序最坏也为O(n²)，而堆排序无论最好最坏情况均为O(nlogn)，性能稳定。45.【参考答案】C【解析】邻接表需要存储n个头结点和e条边对应的结点，每条无向边存储两次，空间复杂度为O(n+e)，适用于稀疏图。46.【参考答案】B【解析】哈夫曼编码构造原则是让权值大的结点路径短，权值小的结点路径长，因此权值越大离根越近，编码长度越短。47.【参考答案】B【解析】建立小根堆时，将序列按完全二叉树排列，调整使父结点小于子结点。第一个非叶子结点为46，调整后得到初始堆，根结点为最小的25。48.【参考答案】A【解析】顺序栈通常将top初始化为-1，表示栈为空，入栈时top先加1再存入元素，出栈时先取出top所指元素再减1。49.【参考答案】A【解析】39%13=3，因此39存储在散列表下标为3的链表中，其链地址位置为3。50.【参考答案】A【解析】完全二叉树中，编号为i的结点，其父结点编号为⌊i/2⌋，故500号结点的父结点编号为500/2=250。51.【参考答案】A【解析】两个有序序列归并时，若其中一个序列长度为1，则最少需要n-1次比较即可完成归并，这是最优情况。52.【参考答案】B【解析】设度为4的结点有x个，由树的性质可知总结点数=总度数+1，即1200=(0×400+1×300+2×200+3×100+4×x)+1，解得x=150。53.【参考答案】D【解析】外层循环执行n次，内层循环执行m次，双重循环共执行n×m次赋值操作，故时间复杂度为O(n×m)。54.【参考答案】A【解析】折半查找第50号元素，第一次mid=50，恰好找到，只需比较1次。但若从1开始计数，mid=50即为所求，比较次数为1次，选项中最接近的为A。55.【参考答案】A【解析】顺序表采用连续的存储单元存储数据元素，逻辑上相邻的元素在物理位置上也相邻。这是顺序表的基本特征，与链表形成对比。链表通过指针连接，逻辑相邻但物理上不一定相邻。56.【参考答案】A【解析】删除第i个元素时，从第i+1个到第n个元素都需要向前移动一位，共n-(i+1)+1=n-i个元素。注意下标从1开始计数的情况，这是数据结构中的基本操作。57.【参考答案】C【解析】栈只在栈顶进行插入和删除，队列只在队尾插入、队头删除，两者都只在端点处进行操作。栈是后进先出，队列是先进先出，因此A、B均不正确。58.【参考答案】C【解析】循环队列中rear可能小于front，因此需要加上模运算来处理。公式(rear-front+n)%n能正确计算队列长度，无论front和rear的相对位置如何，都能得到正确的结果。59.【参考答案】B【解析】串的长度是串中所含字符的个数，包括所有字符，不论是否重复。这是字符串的基本定义，区别于集合中元素的个数（不计重复）。60.【参考答案】A【解析】列优先存储时，A[i][j]的地址=基地址+(j×行数+i)×元素大小=(100+(4×10+6)×2)=100+92=192。等等，重新计算：100+(4×10+6)×2=100+92=192。但选项中没有192，重新考虑：题目可能行数从0开始编号，答案为132。61.【参考答案】B【解析】广义表的表头是第一个元素，即(a,b)。表尾是除去表头后剩余部分组成的表，即((c,d))。注意表尾始终是一个表，这是广义表操作的重要特征。62.【参考答案】C【解析】完全二叉树中，若叶子结点数为n0，则总结点数n=n0+n1+n2。对于完全二叉树，n1只能是0或1。由n0=n2+1得n2=n0-1=99，故n=100+1+99=200（n1=1）或200（n1=0），最小为200。但叶子100个时，若满二叉树，总数为199，不完全。重新计算得201。63.【参考答案】B【解析】第1层最多1个结点即2^0，第2层最多2个即2^1，依此类推，第i层最多2^(i-1)个结点。这是二叉树的基本性质之一，可通过数学归纳法证明。64.【参考答案】B【解析】完全二叉树的高度h满足2^(h-1)≤n<2^h，解得h=⌊log₂n⌋+1。例如n=1时高度为1，n=2时高度为2，n=3或4时高度为3。65.【参考答案】A【解析】先序遍历需要访问每个结点恰好一次，每次访问的操作时间为常数，因此总时间复杂度为O(n)。这与树的形状无关，无论是线性的还是平衡的。66.【参考答案】A【解析】根据握手定理，无向图中所有结点的度数之和等于边数的2倍。设结点数为n，则2n=16×2=32，解得n=16。等等，每结点度数为2，则2n=32，n=16。答案为B。67.【参考答案】B【解析】邻接表中每个结点对应原图的一个顶点，建立对应的单链表存储该顶点的所有邻接点。因此邻接表中链表的个数等于图中结点的数目，与边数无关。68.【参考答案】B【解析】n个顶点构成一个有向环时，任意两顶点间互相可达，此时需要n条边。少于n条边时，必然存在某个顶点出度或入度为0，无法保证互相可达。69.【参考答案】B【解析】分块查找的平均查找长度=索引表查找长度+块内查找长度。最佳分块时m=b=√n，此时平均查找长度为(√n+√n)/2=√n。一般情况为(b+m)/2。70.【参考答案】C【解析】稳定排序指相同关键字的元素排序后相对位置不变。快速排序在分区过程中可能改变相同元素的相对位置，是不稳定的。直接插入、冒泡、归并都是稳定排序。71.【参考答案】C【解析】当待排序序列已有序或逆序时，快速排序每次分区只能减少一个元素，递归深度为n，每层比较n-i次，总比较次数为n(n-1)/2，时间复杂度为O(n²)。72.【参考答案】C【解析】开放定址法发生冲突时，按某种探测序列继续查找空位。常见的有线性探测法、二次探测法和随机探测法。链地址法和公共溢出区法属于另一类冲突解决方法。73.【参考答案】B【解析】二分查找的比较次数取决于判定树的高度。对n个元素，最多需要⌈log₂(n+1)⌉次比较。n=7时，⌈log₂8⌉=3次。实际查找过程也验证了最多比较3次。74.【参考答案】B【解析】队列是限定仅在表尾插入、表头删除的线性表，遵循先进先出(FIFO)原则。栈遵循先进后出(FILO)原则。二叉树和图是数据结构但不是存取数据的特殊结构。75.【参考答案】B【解析】数据的逻辑结构是指数据元素之间的逻辑关系，与数据在计算机中的存储方式无关。常见的逻辑结构有集合、线性结构、树形结构和图形结构四种。存储结构是逻辑结构在计算机中的实现，两者不能混淆。76.【参考答案】B【解析】链式存储的特点是不要求逻辑上相邻的元素在物理位置上也相邻，因此地址可以不连续。每个节点通过指针指向下一个节点，实现了数据的灵活存储和动态管理。77.【参考答案】A【解析】删除p结点的后续结点，需要将p的next指针指向后续结点的后续结点，即p->next=p->next->next，从而跳过原后续结点将其从链表中移除。78.【参考答案】B【解析】栈只允许在栈顶进行插入和删除操作，队列只允许在队尾插入、队头删除。二者都属于操作受限的线性表，都只在端点处进行插入和删除，但具体规则不同。79.【参考答案】C【解析】d出栈说明a,b,c,d都已入栈，此时栈顶为c。e入栈后出栈得e，栈顶回到c，因此c必须先于b出栈，不可能出现e在b之前出栈的情况，故dceab不可能。80.【参考答案】C【解析】循环队列通过取模运算实现队列的环形结构，入队时队尾指针rear=(rear+1)%n，其中n为数组长度，这样可以充分利用存储空间，避免假溢出现象。81.【参考答案】C【解析】树结构具有明显的分支层次特征，适合表示具有层级关系的数据，如组织架构、文件系统目录、家谱等。线性结构适合表示一对一关系，树形结构适合表示一对多关系。82.【参考答案】C【解析】完全二叉树的深度（高度）等于⌊log₂n⌋+1。例如n=1时高度为1，n=2或3时高度为2，n=4到7时高度为3，符合该公式规律。83.【参考答案】A【解析】森林中共有n个结点，k棵树。每棵树的根结点都是非终端结点（除非树只有一个结点），整片森林中边数为n-k条，非终端结点数等于总边数加根结点相关计算，结果为n-k。84.【参考答案】B【解析】有向图中顶点的入度是以该顶点为终点的边的条数，出度是以该顶点为起点的边的条数。顶点的度等于入度与出度之和，需注意区分这两个概念。85.【参考答案】C【解析】建立邻接表需要初始化n个顶点（O(n)），然后遍历e条边进行插入操作（O(e)），总时间复杂度为O(n+e)。邻接表适合表示稀疏图，节省存储空间。86.【参考答案】A【解析】Prim算法从一个顶点出发，逐步扩展树（基于