2017年西南大学数据结构(同等学力加试)考研复试核心题库
● 摘要
一、应用题
1． 三维数组
的存储首地址。
【答案】数组占的存储字节
数
的存储地
址的每个元素的长度为4个字节，试问该数组要占多少个字节的存储空间? 如果数组元素以行优先的顺序存储，设第一个元素的首地址是100，试求元素
2． 设有正文AADBAACACCDACACAAD ，字符集为A , B , C , D , 设计一套二进制编码，使得上述正文的编码最短。
A :1, B :000，C :01，D :001。 【答案】字符A , B , C , D 出现的次数为9, 1, 5, 3。其哈夫曼编码如下：
3． 请回答下列关于图（Graph ）的一些问题：
（1）有n 个顶点的有向强连通图最多有多少条边? 最少有多少条边？
（2）表示一个有1000个顶点、1000条边的有向图的邻接矩阵有多少个矩阵元素? 是否稀疏矩阵？
（3）对于一个有向图，不用拓扑排序，如何判断图中是否存在环？
【答案】⑴最多有n （n-l ）条边；最少有n 条边。
（2） 有有个矩阵元素；不一定是稀疏矩阵（稀疏矩阵的定义是非零元素个数远小于该矩阵元素个数，且分 布无规律）。
（3）使用深度优先遍历，按退出DFS 过程的先后顺序记录下的顶点是逆向拓扑有序序列。如果在执行DFS （V ） 未退出前，出现顶点u 到v 的回边，则说明存在包含顶点v 和顶点u 的环。
4． 请求分页管理系统中，假设某进程的页表内容如下表所示:
页面大小为4KB ，一次内存的访问时间是100ns ，一次快表（TLB ）的访问时间是10ns ，处
，进程的驻留集大小固定为2, 采理一次缺页的平均时间为108ns （已含更新TLB 和页表的时间）
用最近最少使用置换算法（LRU ）和局部淘汰策略。假设①TLB 初始为空；②地址转换时先访问TLB , 若TLB 未命中，再访问页表（忽略访问页表之后的TLB 更新时间）；③有效位为0表示页面不在内存，产生缺页中断，缺页中断处理后，返回到产生缺页中断的指令处重新执行。设有虚地址访问序列请问：
（1）依次访问上述三个虚地址，各需多少时间? 给出计算过程。
（2）基于上述访问序列，虚地址1565H 的物理地址是多少? 请说明理由。
【答案】⑴
页面大小为4KB ，因此，虚地址的低12位是页内偏移，其余高位是页号。
访问虚地址2362H , 虚页号为2，页内偏移362H 。查找TLB , TLB 初始为空，未命中，耗时10ns ; 访问页表，2号页面所在页框号为254H ，耗时100ns ; 计算得到的物理地址254362H ，访问内存，耗时100ns 。因此，总共用时
访问虚地址1565H ，虚页号为1, 页内偏移565H 。查找TLB ，未命中，耗时10ns ; 访问页表，有效位是0，未命中，耗时100m ; 产生缺页中断，进行缺页中断处理，耗时108m ; 采用LRU 置换算法，虚页1装入页帧号101H , 缺页中断处理完后，再次访问页表，命中，耗时100m ; 计算得到物理地址101565H ，再次访问内存，耗时100ns 。因此，总共用时
访问虚地址25A5H ，虚页号为2, 页内偏移5A5H 。查找TLB , 命中，耗时10ns ; 虚页2对应的页帧为254H ，因此计算得物理地址为2545A5H , 访问内存，耗时100ns 。因此，
总共用时
（2）当访问虚地址1565H 时，产生缺页中断，合法驻留集为2, 必须从页表中淘汰一个页面，根据题目的置换算法，应淘汰0号页面，因此1565H 的对应的页框号为101H ，故可知虚地址1565H 的物理地址为101565H 。
5． 设度为m 的树采用多重链表存储，毎个结点有m+1个域，其中有1个数据域，m 个指向孩子的指针。 则空指针的数目是多少？说明这种存储方式的利弊。
【答案】（1）空指针数目：n （n>0）个结点的m 度树共有nm 个链域，除根结点外，每个结点均有一个指针所指，故该树的空链域有nm-（n-1）=n（m-l ）+1个。
（2）利弊：这种存储结构统一，便于处理但空链域造成存储效率低。
6． 给出模式串在KMP 算法中的next 和nextval 数组。
【答案】模式串的next 函数定义如下：
根据此定义，
可求解模式串的next 和nextval 值如下：
7． 已知一个大小为512个字长的存储，假设先后有6个用户申请大小分别为23，45，52，100，11和19的存储空间，然后再顺序释放大小为45，52，11的占用块。假设以伙伴系统实现态存储管理。
（1）画出可利用空间表的初始状态。
（2）画出为6个用户分配所需要的存储空间后可利用空间表的状态以及每个用户所得到的存储块的起始地址。
（3）画出在回收3个占用块之后可利用空间表的状态。
【答案】（1）因为可利用空间表的初始状态图如图1所示：
图1 可利用空间表的初始状态
（2）当用户申请大小为23的内存块时，因但没有大小为的块，只有大小为的块，
故将
的块分裂成两个大小为的块，其中一块挂到可利用空间表上，另一块再分裂成两个
大小为
的块。又将其中大小为的一块挂到可利用空间表上，
另一块再分裂成两个大小为的
块。其中一块的块挂到可利用空间表上，
另一块分裂成两个大小为的块，其中一块挂到可利用空间表上，另一块分给用户（地址0〜31）。如此下去，最后每个用户得到的存储空间的起始地址如图2所示，为6个用户分配所需要的存储空间后可利用空间表的状态如图3所示。
图2 每个用户得到的存储空间的起始地址
相关内容
相关标签