2017年西北师范大学955数据结构考研复试核心题库
● 摘要
一、应用题
1． 下图是5阶B 树，画出删去P 后的B 树，再画出删去D 后的B 树。
【答案】删除P 后
删除D 后
2． 写出下面算法中带标号语句的频度。
设k 的初值等于1。
【答案】（1）这是一个递归调用，因k 初值为1，由语句（6）知，每次调用k 增1，故第（1）语句执行n 次，所以频度是n 。
（2）这是FOR 循环语句，在满足（1）的条件下执行，该语句进入循环体（3）n 次，加上最后一次判断出界，故执彳丁了n ＋1次，所以频度是n ＋1。
（3）这是循环体语句，共执行了n 次，所以频度是n 。
，k=2时判断n 次，最后（4）这是循环语句，当k=l时判断n ＋1次（进入循环体（5）n 次）
一次k=n－l 时判断3次，故执行次数是（n ＋1）＋n ＋... ＋3=（n ＋4）（n －1）/2次，所以频度是（n ＋4）（n －1）/2。
（5）语句（5）是（4）的循环体，每次比（4）少一次判断，故执行次数是n ＋（n －1）＋... ＋2=（n ＋2）（n －1）/2次，所以频度是（n ＋2）（n －1）/2。
（6）这是循环体语句，共执行了n －1次，所以频度是n －1。
3． 某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 、MAR 和MDR 等 是CPU 的内部工作寄存器，对程序员不可见。
（2）ALU 中共有7种命令，用三位即可区别表示，SR 共有三种命令二位二进制即可表示。 （4）操作符命令，传输等都需要控制信号进行控制。
4． 一个长度为的升序序列S , 处在第「L/2」个位置的数为S 的中位数。例如，若序列Sl= （11，13, 15, 17，19），则S1的中位数是15。两个序列的中位数是含它们所有元素的升序序列的中位数。例如，若S2= （2, 4, 6, 8, 20）, 则S1和S2的中位数是11。现有两个等长升序序列A 和B ，试设计一个时间和空间两方面都尽可能高效的算法，找出两个序列A 和B 的中位数。要求：
（1）给出算法的基本设计思想。
（2）根据设计思想，采用C 或C++或JA V A 语言描述算法，关键之处给出注释。 （3）说明你所设计算法的时间复杂度和空间复杂度。
【答案】（1）算法的基本设计思想：分别求两个升序序列A 和B 的中位数，设为a 和b 。 ① 若a=b，则a 或b 即为所求的中位数。
② 否则，若a 所在序列B 的较大一半。若a>b，中位数只能出现（b ，a ）范围内，舍弃b 所在序列B 的较小一半，同时舍弃a 所在序列A 的较大一半。 ③在保留的两个升序序列中求出新的中位数a 和b ，重复上述过程，直到两个序列中只含一个元素时为止，则较小者即为所求的中位数。 （2）用C 语言算法描述如下：