2025年考研计算机学科专业基础综合（408）历年真题精编与专项训练（2010-2024年）

考试时间：______分钟总分：______分姓名：______

一、数据结构

1.设有栈S，初始时为空。现输入元素a,b,c,d,e，依次进行出栈操作，则可能得到的出栈序列为______。请说明理由。

2.已知一棵二叉树的先根遍历序列为ABCD，后根遍历序列为BCDA，请画出该二叉树。

3.写出快速排序算法的递归实现过程，并简要说明其平均时间复杂度和空间复杂度。

4.设有稀疏矩阵A（3,4）和B（3,4），其三元组表分别为A.T=((1,1,5),(2,3