2017年重庆工商大学数据结构(C语言)考研复试核心题库
● 摘要
一、应用题
1． 快速排序的最大递归深度是多少? 最小递归深度是多少？
【答案】设待排序记录的个数为n ，则快速排序的最小递归深度为
最大递归深度n 。
2． 证明：在二叉树的三种遍历序列中，所有叶结点间的先后关系都是相同的。要求毎步论断都指出根据。
【答案】前序遍历是“根左右”. 中序遍历是“左根右”. 后序遍历是“左右根”。若将“根”去掉，三祌遍历就剩“左右”。三种遍历中的差别耽足访问根结点的时机不同。二叉树是递归定义的，对左右子树均是按左右顺序来遍历的，因此所有叶结点间的先后关系都是相同的。
3． 设将n （n ＞l ）个整数存放到一维数组R 中。试设计一个在时间和空间两方面都尽可能高效的算法，将R 中存有的序列循环左移P （0＜P ＜n ）个位置，即将R 中的数据由
变换为
（1）给出算法的基本设计思想。 （2）根据设计思想，采用C 或
或JA V A 语言描述算法，关键之处给出注释。
原地逆置，
得到
（3）说明你所设计算法的时间复杂度和空间复杂度。 【答案】（1）算法的基本设计思想：先将n
个数据由然后再将数组R 中的前
，
（2）用C 语言算法描述如下：
（3）说明算法的复杂性：上述算法中3个Reverse 函数的的时间复杂度分别为
第 2 页，共 32 页
要求：
个数和后P 个数分别原地逆置，
最终得到结果
为O 故算法的时间复杂度为，算法的空间复杂度为0（1）。
4． 某计算机字长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 的存储单元的内容会改变，改变后的内容分别为
：
5． 请阅读下列算法，回答问题。
第 3 页，共 32 页
（逗号前为源操作数，逗号后为目的操作数）
对应的机器码是什么（十六进制表示）？该指令执行后，哪些寄存器和存储单元的内容会改变?
条不同的指令；指令操作上占6
个通用寄存器；主存容
个存储单元，故MDR 和MAR 至少各
位，寻址方式占3位，于是寄存器编号占3位，该计算机最多可以有
+对应的机器码为该指令执行后，
问题一：这是什么类型的排序算法，该排序算法稳定吗？ 问题二：设置
|的作用是什么? 若将WHILE--DO 语句中判断条件改为
该
算法将会有什么变化，是否还能正确工作？
【答案】问题一：此为直接插入排序算法，该算法稳定。 问题二：采用
的作用是监视哨，免去每次检测文件是否到尾，提高了排序效率。
描述算法后，算法变为不稳定排序，但能正常工作。
6． 设内存中可利用空间已连成一个单链表，对用户的存储空间需求，一般有哪三种分配策略？
【答案】（1）首次适配法
从链表头指针开始查找，找到第一个大于等于所需空间的结点即分配。首次适配法适合事先不知道请求分配和释放信息的情况，分配时需查询，释放时插在表头。
（2）最佳适配法
链表结点大小增序排列，找到第一个大于等于所需空间的结点即分配。最佳适配法适用于请求分配内存大小范围较宽的系统，释放时容易产生存储量很小难以利用的内存碎片，同时保留那些很大的内存块以备将来可能发生的大内存量的需求，分配与回收均需查询。
（3）最差适配法
链表结点大小逆序排列，总从第一个结点开始分配，将分配后结点所剩空间插入到链表适当位置。最差适配法适合请求分配内存大小范围较窄的系统，分配时不查询，回收时查询，以便插入适当位置。
7． 将下列出三棵树组成的森林转换为二叉树（只要求给出转换结果）。
图1
【答案】森林转换为二叉树分以下三步：
（1）连线（将兄弟结点相连，各树的根看作兄弟）。
（2）切线（保留最左边子女为独生子女，将其他子女分支切掉）。
第 4 页，共 32 页
相关内容
相关标签