2017年江西财经大学数据结构复试仿真模拟三套题
● 摘要
一、应用题
1． 分析ISAM 文件（IndeXed Sequential Access Methord）和VSAM 文件（Virtual storage Access Methord ）的应用场合、优缺点等。
【答案】ISAM 是一种专为磁盘存取设计的文件组织形式，采用静态索引结构，对磁盘上的数据文件建立盘组、柱面、磁道三级索引。ISAM 文件中记录按关键字顺序存放，插入记录时需移动记录并将同一磁道上最后的一个记录移至溢出区，同时修改磁道索引项，删除记录只需在存储位置作标记，不需移动记录和修改指针。经过多次插入和删除记录后，文件结构变得不合理，需周期整理ISAM 文件。
VSAM 文件采用
动态索引结构，文件只有控制区间和控制区域等逻辑存储单位，与外存储
树，作为文件的索引部分可实现顺链查找和从
器中柱面、磁道等具体存储单位没有必然联系。VSAM 文件结构包括索引集、顺序集和数据集三部分，记录存于数据集中，顺序集和索引集构成根结点开始的随机查找。
优缺点：与ISAM 文件相比，VSAM 文件有如下优点：动态分配和释放存储空间，不需对文件进行重组；能保持较高的查找效率，且查找先后插入记录所需时间相同。因此，基于
的VSAM
文件通常作为大型索引顺序文件的标准组织。
2． 设散列表为，现采用双散列法解决冲突。散列函数和再哈希函即表的大小为数分别为
：
注：％是求余数运算中，函数码序列为
（2）计算搜索成功的平均搜索长度
表示颠倒十进制数x 的各位，如
其
等。若插入的关键
（1）试画出插入这8个关键码后的哈希表；
【答案】（1）插入这8个关键码后的哈希表如表所示：
表 插入关键字后的哈希表
（2）
3． 证明任一结点个数为n 的二叉树的高度至少为0 （logn ）。
【答案】最低高度二叉树的特点是，除最下层结点个数不满外，其余各层的结点数都应达到各层的最大值。设n 个结点的二叉树的最低高度是h ，则n 应满足
第 2 页，共 23 页
。解此不等式，并考
虑h 是整数. 则有即任一结点个数为n 的二叉树的高度至少为
4． 试举一例，说明对相同的逻辑结构，同一种运算在不同的存储方式下实现，其运算效率不同。
【答案】线性表中的插入、删除操作，在顺序存储方式下平均移动近一半的元素，时间复杂度为O （n ）; 而在链式存储方式下，插入和删除时间复杂度都是0（1）。
5． 某计算机字长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 的存储单元的内容会改变，改变后的内容分别为
：
第 3 页，共 23 页
（逗号前为源操作数，逗号后为目的操作数）
对应的机器码是什么（十六进制表示）？该指令执行后，哪些寄存器和存储单元的内容会改变?
条不同的指令；指令操作上占6
个通用寄存器；主存容
个存储单元，故MDR 和MAR 至少各
位，寻址方式占3位，于是寄存器编号占3位，该计算机最多可以有
+对应的机器码为该指令执行后，
6． 三个进程P1、P2, P3互斥使用一个包含N P1每次用produce （N ＞0）个单元的缓冲区。（ ）生成一个正整数并用put （ ）送入缓冲区某一空单元中；P2每次用getodd （ ）从该缓冲区中取出一个奇数并用countodd （ ）统计奇数个数；P3每次用geteven （ ）从该缓冲区中取出一个偶数并用counteven （ ）统计偶数个数。请用信号量机制实现这三个进程的同步与互斥活动，并说明所定义信号量的含义。要求用伪代码描述。
【答案】定义信号量S1控制P1与P2之间的同步；S2控制P1与P3之间的同步；empty 控制生产者与消费者之间的同步；mutex 控制进程间互斥使用缓冲区，程序如下：
7． 将关键字序列（7, 8, 30，11，18, 9，14）散列存储到散列表中，散列表的存储空间是一个下标从0开始的一维数组。散列函数是：列法，要求装填（载）因子为0.7。
（1）请画出所构造的散列表。
第 4 页，共 23 页
处理冲突采用线性探测再散
相关内容
相关标签