2017年北京工业大学北京未来网络科技创新中心数据结构复试实战预测五套卷
● 摘要
一、应用题
1． 对于具有n 个叶结点且所有非叶结点都有左、右孩子的二叉树。
（1）试问这种二叉树的结点总数是多少？
（2）试证明 。其中：表示第i 个叶结点所在的层号（设根结点所在层号为1）。
【答案】（1）根据二叉树中度为2的结点个数等于叶结点个数减1的性质，故具有n 个叶结点且非叶子结点均有左子树的二叉树的结点数是2n-l 。
（2）证明：当i=l时，
成立。
设某叶结点的层号为t ，当将该结点变为内部结点，从而再增加两个叶结点时，这两个叶结点的层号都是t+1, 对于公式的变化，是减少了一个原来的叶结点，増加了两个新叶结点，反映到公
，所以结果不变，这就证明当i=n时公式仍成立。证毕。 式中. 因为
2． 已知图的邻接矩阵为：
, 公式成立。设当i=n-1时公式成立，证明当i=n时公式仍
当用邻接表作为图的存储结构，且邻接点都按序号从大到小排列时，试写出：
（1）以顶点V1为出发点的唯一的深度优先遍历序列；
（2）以顶点V1为出发点的唯一的广度优先遍历序列；
（3）该图唯一的拓扑有序序列。
1）V1，V4，V9, V10，V7, V6, V8，V3，V2, V5 【答案】（
（2） V1, V4, V3, V2, V9, V7, V6, Y5, V10, V8
（3） V1, V2, V5, V3, V4, V6, V8, V7, V9, VIO
3． 在模试匹配KMP 算法中所用失败函数的定义中，为何要求
真子串？且为最大真子串？
【答案】失败函数（即next ）的值只取决于模式串自身，若第j 个字符与主串第i 个字符失配
两头匹配的
时，假定主串不回溯，模式串用第k （即next[j]个字符与第i 个相比，有为了不因模式串右移与主串第i 个字符比较而丢失可能的匹配，对于上式中可能存在的多个k 值，应取其中最大的一个。这样，因j-k 最小，即模式串向右滑动的位数最小，避免因右移造成可能匹配的丢失。
4． 假定某计算机的CPU 主频为80MHz , CPI为4, 并且平均每条指令访存1.5次，主存与Cache 之间交换的块大小为168, Cache的命中率为存储器总线宽度为32位。请回答下列问题。
（1）该计算机的MIPS 数是多少? 平均每秒Cache 缺失的次数是多少? 在不考虑DMA 传送的情况下，主存带宽至少达到多少才能满足CPU 的访存要求？
（2）假定在Cache 缺失的情况下访问主存时，存在
期挪用方式，磁盘接口的数据缓冲寄存器为32位，则磁盘的缺页率，则CPU 平均每秒产接口平均每秒发出的DMA 生多少次缺页异常? 若页面大小为4KB ，每次缺页都需要访问磁盘，访问磁盘时DMA 传送采用周请求次数至少是多少？
（3）CPU 和DMA 控制器同时要求使用存储器总线时，哪个优先级更高? 为什么？
（4）为了提高性能，主存采用4体交叉存储模式，工作时每
每个体的存储周期为50ns ，则该主存能提供的最大带宽是多少？
【答案】
（1）平均每秒CPU 执行的指令数为：
平均每秒Cache 缺失的次数为：
为
：
足CPU 的访存要求。
（2）平均每秒钟“缺页”异常次数为：
故平均每秒磁盘DMA 请求的次数至少为：
请求得不到及时响应，
传输数据可能会丢失。 因为存储器总线宽度为32位，所以，每传送32位数据，磁盘控制器发出一次DMA 请求，CPU 和DMA 控制器同时要求使用存储器总线时，DMA 请求优先级更高；因为若DMA （3）（4）4体交叉存储模式能提供的最大带宽为：故MIPS 数为20; =300000; 才能满个存储周期启动一个体。若当Cache 缺失时，CPU 访问主存，主存与Cache 之间以块为单位传送数据，此时，主存带宽在不考虑DMA 传输的情况下，主存带宽至少达到
5． 假设Internet 的两个自治系统构成网络如题图所示，自治系统ASI 由路由器R1连接两个子网构成；自治系统AS2由路由器R2、R3互联并连接3个子网构成。各子网地址、R2的接口名、R1与R3的部分接口 IP 地址如题图所示。请回答下列问题。
题图网络拓扑结构
（1）假设路由表结构如下所示。请利用路由聚合技术，给出R2的路由表，要求包括到达题图中所有子网的路由，且路由表中的路由项尽可能少。
（2）若R2收到一个目的IP 地址为194.17.20.200的IP 分组，R2会通过哪个接口转发该IP 分组？
R1与R2之间利用哪个路由协议交换信息？该路由协议的报文被封装到哪个议的分组中（3）
进行传输？
【答案】
（1）在AS1中，子网中，子
网和子网单独连接到的接口可以聚合为子网但缺少子网
于是可以得到R2的路由表如下：
（2）该IP 分组的目的IP 地址194.17.20.200与路由表中194.17.20.0/23和194.17.20.128/25两个路由表项均匹配，根据最长匹配原则，R2将通过E0接口转发该1P 分组。
（3）R1与R2之间利用BGP4 （或BGP ）交换路由信息；BGP4的报文被封装到TCP 协议段中进行传输。2012年全国硕士研究生入学统一考试计算机科学与技术学科联考计算机学科专此基础综合真题及详解
6． 设G=（V , E）以邻接表存储，如图所示，试画出图1的深度优先生成树和广度优先生成树。 和子网可以聚合为子网在AS2