2017年兰州大学综合考试之数据结构复试实战预测五套卷
● 摘要
一、应用题
1． 某计算机字长16位，主存地址空间大小为128KB , 按字编址，采用单字长指令格式，指令各字段定义如下：
源操作数目的操作数
转移指令采用相对寻址方式，相对偏移量用补码表示，寻址方式定义如下：
注：（X ）表示存储器地址X 或寄存器X 的内容。请回答下列问题：
（1）该指令系统最多可有多少条指令? 该计算机最多有多少个通用寄存器? 存储器地址寄存器（MAR ）和存储器数据寄存器（MDR ）至少各需要多少位？
（2）转移指令的目标地址范围是多少？
（3）若操作码0010B 表示加法操作（助记符为add ）, 寄存器R4和R5的编号分别为100B 和101B ，R4的内容为1234H ，R5的内容为5678H , 地址1234H 的内容为5678H ，地址5678H 中的内容为1234H ，则汇编语句
改变后的内容是什么？
【答案】（1）指令操作码占4位，则指令系统最多可有
量为128KB ，计算机字长为16位，故主存有
需16位。
（2）由于寄存器字长为16位，所以转移指令的目标地址范围为0000H 〜FFFFH 。。
（3）汇编语句
寄存器
R5和地址为5678H 的存储单元的内容会改变，改变后的内容分别为
：
第 2 页，共 36 页 （逗号前为源操作数，逗号后为目的操作数）对应的机器码是什么（十六进制表示）？该指令执行后，哪些寄存器和存储单元的内容会改变? 条不同的指令；指令操作上占6个通用寄存器；主存容个存储单元，故MDR 和MAR 至少各位，寻址方式占3位，于是寄存器编号占3位，该计算机最多可以有+对应的机器码为该指令执行后，
2． 若森林共有n 个结点和b 条边（b 【答案】森林的n 个结点开始可看做是n 个连通分量，加入一条边将减少一个连通分量。因为树可以定义为无环的图，故加入b 条边将减少b 个连通分量，因而n 个结点b 条边的森林有n-b 棵树。 3． 文件F 由200条记录组成，记录从1开始编号，用户打开文件后，欲将内存中的一条记录插入文件F 中，作为其第30条记录，请回答下列问题，并说明理由。 （1）若文件系统为顺序分配方式，每个存储块存放一条记录，文件F 的存储区域前后均有足够空闲的存储空间，则要完成上述操作最少要访问多少存储块？ F 的文件控制区内容会有哪些改变？ （2）若文件系统为链接分配方式，每个存储块存放的一条记录和一个链接指针，则要完成上述操作最少要 访问多少存储块？若每个存储块大小为1KB ，其中4个字节存放指针，则该系统支撑文件的最大长度是多少？ 【答案】（1）因为要最少访问，所以选择将前29块前移一个存储块单元，然后将要写入的记录写入到当前的第30条的位置上。由于前移都要先访问原存储块将数据读出，再访问目标存储块将数据写入，所以最少需要访问 块存储块 F 的文件区的文件长度加1，起始块号减1 （2）采用链接方式则需要顺序访问前29块存储块，然后将新纪录的存储块插入链中即可，把新的块存入磁盘要1次访存，然后修改第29 块的链接地址存回磁盘又一次访存。一共就是 次。 4个字节的指针的地址范围为 所以此系统支撑文件的最大长度为 4． 一个ISAM 文件除了主索引外，还包括哪两级索引？ 【答案】ISAM 文件有三级索引：磁盘组、柱面和磁盘，柱面索引存放在某个柱面上，若柱面索引较大，占多个磁道时，可建立柱面索引的索引一主索引。故还包括的两级索引是盘组和磁道。 5． 试举一例，说明对相同的逻辑结构，同一种运算在不同的存储方式下实现，其运算效率不同。 【答案】线性表中的插入、删除操作，在顺序存储方式下平均移动近一半的元素，时间复杂度为O （n ）; 而在链式存储方式下，插入和删除时间复杂度都是0（1）。 6． 在某程序中，有两个栈共享一个一维数组空间 的栈底。 （1）对栈1、栈2, 试分别写出（元素x ）入栈的主要语句和出栈的主要语句。 （2）对栈1、栈2, 试分别写出栈满、栈空的条件。 【答案】（1）入栈主要语句 第 3 页，共 36 页 分别是两个栈 出栈主要语句 （2） 7． 已知图的邻接矩阵为： 当用邻接表作为图的存储结构，且邻接点都按序号从大到小排列时，试写出： （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 8． 试叙述动态存储分配伙伴系统的基本思想，它和边界标识法不同点是什么？ 【答案】（1）动态存储分配伙伴系统的基本思想 在伙伴系统中，无论占用块或空闲块，其大小均为（k 为大于等于0的正整数）。若内存容 量为 则空闲块大小只能是由同一大块分裂而得的两个小块互称“伙伴空 （若） ， 如内存大小为 间” 或的块分裂成两个大小为的块。只有两个“伙伴空间”才能合并成一个大（若 （2）和边界标识法的不同 边界标识法在每块的首尾均有“占用”/“空闲”标志，空闲块合并方便。伙伴系统算法简单、速度快，但只有互为伙伴的两个空闲块才可合并，因而易产生虽空闲但不能归并的碎片。 第 4 页，共 36 页 空间。起始地址为P ， 大小为的内存块，其伙伴的起始地址为：）。