2017年中国海洋大学数据结构考研复试核心题库
● 摘要
一、应用题
1． 设有一棵算术表达式树，用什么方法可以对该树所表示的表达式求值？
【答案】有两种方法，具体如下：
（1）对该算术表达式（二叉树> 进行后序遍历. 得到表达式的后序遍历序列，再按后缀表达式求值。
（2）递归求出左子树表达式的值，再递归求出右子树表达式的值，最后按根结点运算符（+、一、*、/等） 进行求值。
2． 对于具有n 个叶结点且所有非叶结点都有左、右孩子的二叉树。
（1）试问这种二叉树的结点总数是多少？ （2）试证明
。其中：表示第i 个叶结点所在的层号（设根结点所在层号为1）。
【答案】（1）根据二叉树中度为2的结点个数等于叶结点个数减1的性质，故具有n 个叶结点且非叶子结点均有左子树的二叉树的结点数是2n-l 。
（2）证明：当i=l时，成立。
设某叶结点的层号为t ，当将该结点变为内部结点，从而再增加两个叶结点时，这两个叶结点的层号都是t+1, 对于公式的变化，是减少了一个原来的叶结点，増加了两个新叶结点，反映到公，所以结果不变，这就证明当i=n时公式仍成立。证毕。 式中. 因为
3． 某计算机的主存地址空间大小为256MB ，按字节编址，指令Cache 和数据Cache 分离，均有8个Cache 行，每个Cache 行大小为64B , 数据Cache 采用直接映射方式。现有两个功能相同的程序A 和B , 其伪代码如下所本：程序A :程序B :
假定int 类型数据用32位补码表示，程序编译时i , j , sum 均分配在寄存器中，数组a 按行优先方式存放，首地址320（十进制数）。请回答下列问题，要求说明理由或给出计算过程。
（1）若不考虑用于Cache —致性维护和替换算法的控制位，则数据Cache 的总容量为多少？
, 公式成立。设当i=n-1时公式成立，证明当i=n时公式仍
（2）数组数据号从0开始）？
和各自所在的主存块对应的Cache 行号分别是多少（Cache 行
（3）程序A 和B 的数据访问命中率各是多少? 哪个程序的执行时间更短？
【答案】（1）每个Cache 行对应一个标记项，标记项包括有效位、脏位、替换控制位以及标记位。由主存空间大小为256M 可知地址总长度为28位，其中块内地址为log264=6位，Cache 块号为log28=3位，不考虑一致性维护和替换算法的控制位，则Tag 的位数为28-6-3=19位，还需一位有效位，数据Cache 共有8行，故Cache 的总容量为
（2）数组a 在主存的存放位置及其与Cache 之间的映射关系如下图所示：
图
数组按行优先方式存放，首地址为320, 数组元素占4个字节。Cache 行号
为
（3）数组a 的大小为逐行访问数
组a ，共需访问的次数为A 的数据访问命中率为
次，每个字块的第一个数未面中，因此未面中次数为
Cache 总容量为
次，程序数组a —行的大
占用
个主存块，按行优先存放，程序A
所在的主存块对应的
所在的主存块对应的Cache 行号
为
小为1KB 正好是Cache 容量的2倍，可知不同行的同一列数组元素使用的是同一个Cache 单元，而程序B 逐列访问数组a 的数据时，都会将之前的字块置换出，也即每次访问都不会面中，故程序B 的数据访问命中率是0, 因此程序A 的执行过程更短。
4． 已知有5个顶点的图G 如下图所示
请回答下列问题
（1）写出图G 的邻接矩阵A （行、列下标从0开始）。 （2）求什么？
【答案】（1）邻接矩阵为
矩阵
中位于0行3列元素值的含义是什么？
非零元素的含义是
（3）若已知具有n （n>=2）个顶点的邻接矩阵为B ，则
（2）
为：
0行3列的元素的含义是顶点0到顶点3间是相通的，并且路径长度为2的路径有2条。 （3）
中非零元素的含义是：假设此顶点位于i 行j 列，表示从i 结点到j 结点路径长度为
m 的路径的条数。
5． 队列可以用循环单链表来实现，故可以只设置一个头指针或者只设置一个尾指针。请你分析对于循环单链表实现的队列，用哪种方案更合适。
【答案】循环单链表若只设头指针，则出队操作时间复杂度是是
若只设尾指针，则出队和入队操作时间复杂度都是
而如对操作时间复杂度
因此，用循环单链表来实现队
列，设置一个尾指针更合适。
6． （1）如果G1是一个具有n 个顶点的连通无向图，那么G1最多有多少条边?G1最少有多少条边？
（2）如果G2是一个具有n 个顶点的强连通有向图，那么G2最多有多少条边?G2最少有多少条