2017年湖南师范大学软件工程之数据结构(C语言版)考研复试核心题库
● 摘要
一、应用题
1． 下面程序段的时间复杂度是什么？
【答案】赋值语句一共被执行了m*n次，所以该程序段的时间复杂度是O （m*n）。
2． 二叉树的带权路径长度（WPL ）是二叉树中所有叶结点的带权路径长度之和，给定一棵二叉树T ，采用二叉链表存储，节点结构为：
其中叶节点的weight 域保存该结点的非负权值。设root 为指向T 的根节点的指针，设计求T 的WPL 的算法。要求：
（1）给出算法的基本设计思想；
（2）使用C 或C++语言，给出二叉树结点的数据类型定义；
（3）根据设计思想，采用C 或C++语言描述算法，关键之处给出注释。
【答案】（1）算法的基本思路是利用利用递归的思想来求解二叉树的带权路径长度，如果当前节点不是叶子节点，那么当前节点为根的树的带权路径长度便等于它的子树的带权路径长度之和，对于此函数要传入一个当前节点的树高的形参，那么递归调用孩子节点时只需要将这个形参加一即可。
（2）
typedef struct BiNode
（3）具体算法实现如下：
如果当前节点为空节点
//如果当前节点的左右孩子节点都为空，即当前节点为叶子节点，直接返回当前节点的
WPL
//如果当前节点不是叶子节点，则对当前节点的左右子树进行递归，返回左右子树WPL 之和
3． 已知有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 的路径的条数。
4． 设输入序列为2, 3, 4, 5, 6, 利用一个栈能得到序列2, 5, 3, 4, 6吗? 栈可以用单链表实现吗？
【答案】不能得到序列2, 5, 3, 4, 6。因为根据输入序列，2进栈之后，2出找，3, 4, 5依次进栈。5出栈，此时栈中剩下3, 4。因为4在栈顶，所以4应该比3先出栈，不能得到提供的序列。栈可以用单链表实现，这就是链栈。由于栈只在栈顶操作，所以链栈通常不设头结点。
5． 某计算机的主存地址空间大小为256MB ，按字节编址，指令Cache 和数据Cache 分离，均有8个Cache 行，每个Cache 行大小为64B , 数据Cache 采用直接映射方式。现有两个功能相同的程序A 和B , 其伪代码如下所本：程序A :程序B :
假定int 类型数据用32位补码表示，程序编译时i , j , sum 均分配在寄存器中，数组a 按行优先方式存放，首地址320（十进制数）。请回答下列问题，要求说明理由或给出计算过程。
（1）若不考虑用于Cache —致性维护和替换算法的控制位，则数据Cache 的总容量为多少？ （2）数组数据号从0开始）？
（3）程序A 和B 的数据访问命中率各是多少? 哪个程序的执行时间更短？
【答案】（1）每个Cache 行对应一个标记项，标记项包括有效位、脏位、替换控制位以及标记位。由主存空间大小为256M 可知地址总长度为28位，其中块内地址为log264=6位，Cache 块号为log28=3位，不考虑一致性维护和替换算法的控制位，则Tag 的位数为28-6-3=19位，还需一位有效位，数据Cache 共有8行，故Cache 的总容量为
（2）数组a 在主存的存放位置及其与Cache 之间的映射关系如下图所示：
和
各自所在的主存块对应的Cache 行号分别是多少（Cache 行
图
数组按行优先方式存放，首地址为320, 数组元素占4个字节。Cache 行号
为
所在的主存块对应的
所在的主存块对应的Cache 行号为