2017年成都信息工程大学数据结构考研复试核心题库
● 摘要
一、应用题
1． 在多关键字排序时，LSD 和MSD 两种方法的特点是什么？
【答案】（1）最高位优先（MSD ）法 先对最高位关键字进行排序，将序列分成若干子序列，
每个子序列中的记录都具有相同的值，然后，分别就每个子序列对关键字
列。
（2）最低位优先
先对最低位关键字
位关键字
序列参加排序，
但对法 进行排序，然后对高一级关键字进行排序，依次重复，直至对最高进行排序，按值不同再分成若干更小的子序列，依次重复，直至最后对最低位关键字排序完成，将所有子序列依次连接在一起，成为一个有序子序排序后便成为一个有序序列。进行排序时，不必分成子序列，对每个关键字都是整个排序时，只能用稳定的排序方法。另一方面，按LSD 进行排序时，可以不通过关键字比较实现排序，而是通过若干次“分配”和“收集”来实现排序。
2． 为什么文件的倒排表比多重表组织方式节省空间？
【答案】倒排表有两项，一是次关键字值，二是具有相同次关键字值的物理记录号，这些记录号有序且顺序存储，不使用多重表中的指针链接，因而节省了空间。
3． 将关键字序列（7, 8, 30，11，18, 9，14）散列存储到散列表中，散列表的存储空间是一个下标从0开始的一维数组。散列函数是：
列法，要求装填（载）因子为0.7。
（1）请画出所构造的散列表。
（2）分别计算等概率情况下查找成功和查找不成功的平均查找长度。
【答案】（1）要求装填因子为0.7, 数组的长度应该为7/0.7=10, 数组下标为0〜9。各关键字的散列函数值如下表：
采用线性探测法再散列法处理冲突，所构造的散列表为：
（2）查找成功时，在等概率情况下，查找表中每个元素的概率是相等的，因此是根据表中元素个数来计算平均查找长度，各关键字的比较次数如下表所示： 处理冲突采用线性探测再散
故查找成功的平均查找长度为（1+1+1+1+3+3+2）/7=12/7。
在不成功的情况下，由于任意关键字key , H （key ）的值只能是0〜6之间，H （key ）为0需要比较3次，H （key ）为1需要比较2次，H （key ）为2需要比较1次，H （key ）为3需要比较2次，H （key ）为4需要比较1次，H （key ）为5需要比较5次，H （key ）为6需要比较4次，共7种情况，如下表所示：
所以，在等概率下，查找失败的平均查找长度为：（3+2+1+2+1+5+4）/7=18/7。
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． 设G=（V , E）以邻接表存储，如图所示，试画出图1的深度优先生成树和广度优先生成树。
图1
【答案】设从顶点1开始遍历，则深度优先生成树如图2所示，广度优先生成树如图3所示：
图2 图3
6． 某16位计算机主存按字节编码。存取单位为16位；采用16位定长指令格式；CPU 采用单总线结构，主要部分如下图所示。图中为通用寄存器；T 为暂存器；SR 为移位寄存器，可实现直送（mov ）、左移一位（left ）、右移一位（right ） 3种操作，控制信号为Srop , SR的输
ALU 可实现直送A A 加 B （add ）A 减 B （sub ）A 与 B （and ）出信号Srout 控制；（mova ）、、、、
A 或 B （or ）、非 A （not ）、A 加 1 （inc ） 7 种操作，控制信号为
请回答下列问题。
（1）图中哪些寄存器是程序员可见的？为何要设置暂存器T?
（2）控制信号（4）端点和的位数至少各是多少？ （3）控制信号Srout 所控制部件的名称或作用是什么？ 中，哪些端点须连接到控制部件的输出端？
中相应的端点之间添加必要的连线。写出连（5）为完善单总线数据通路，需要在端点
线的起点和终点，以正确表示数据的流动方向。
（6）为什么二路选择器MUX 的一个输入端是2?
【答案】（1）图中程序员可见的寄存器有通用寄存器和程序计数器PC ; 当执行算术或逻辑操作时，由于ALU 本身是没有内部存储功能的组合电路，因此如要执行加法运算，被相加的两个数必须在ALU 的两个输入端同时有效，因此设置暂存器T 用于暂存数据总线发送的数据。
（2）ALUop 和SRop 的位数分别为3，2。
（3）Srout 所控制的部件是状态字寄存器，用来存放ALU 及CPU 的指令状态。
（4）须连接到控制部件的输出端端点有
（5）
（6）数据宽度是16位，以字节编址，输入端是2是为了增加地址获取ALU 的第二个操作数。
【解析】（1）程序员可见的寄存器包括：程序计数器、通用寄存器和状态寄存器。其他的IR 、
相关内容
相关标签