2021年安徽师范大学计算机理论基础考研真题

2021 年安徽师范大学计算机理论基础考研真题第一部分 数据结构（80 分）一、简答题（每小题 5 分，共 20 分）1.简述线性结构中数据元素间关系的特点，并列举常用的线性结构（3 种以上）。2.简述头结点和头指针的概念，并说明链表中加入头结点的作用。3.对于一个栈，如果输入序列为 A、B、C，给出全部可能的输出序列。4.简述稀疏矩阵压缩存储的方法。二、应用题（每小题 8 分，共 40 分）1.一棵二叉树的后序遍历序列为 CEFDBKJIHGA，中序遍历序列为 CBEDFAHJKIG，给出相应的二 叉树以及先序遍历序列。2.已知图 G 的邻接矩阵如下图所示，顶点集 V={ V0，V1，V2，V3，V4，V5}。（1）画出图 G;（2）基于上述邻接矩阵，给出从顶点 V。出发的深度优先遍历序列。3.已知权值集合为{16，5，9，3，30...