2022年沈阳建筑大学数据结构(同等学力加试)考研复试核心题库

考研专业课资料、辅导、答疑一站式服务平台

第 1 页，共 37 页

目录

2018年沈阳建筑大学数据结构(同等学力加试)考研复试核心题库（一） (2)

2018年沈阳建筑大学数据结构(同等学力加试)考研复试核心题库（二） (9)

2018年沈阳建筑大学数据结构(同等学力加试)考研复试核心题库（三） (14)

2018年沈阳建筑大学数据结构(同等学力加试)考研复试核心题库（四） (20)

2018年沈阳建筑大学数据结构(同等学力加试)考研复试核心题库（五） (30)

考研专业课资料、辅导、答疑一站式服务平台

第 2 页，共 37 页 2018年沈阳建筑大学数据结构(同等学力加试)考研复试核心题库（一）

特别说明：

1-本资料为学员内部使用，整理汇编了2018考研复试重点题及历年复试常考题型。

2-资料仅供复试复习参考，与目标学校及研究生院官方无关，如有侵权、请联系我们立即处理。 ————————————————————————————————————————

一、应用题

1． 证明:在二叉树的三种遍历序列中，所有叶结点间的先后关系都是相同的。要求每步论断都指出根据。

【答案】前序遍历是“根左右”，中序遍历是“左根右”，后序遍历是“左右根”。若将“根”去掉，三种遍历就剩“左右”。三种遍历中的差别就是访问根结点的时机不同。二叉树是递归定义的，对左右子树均是按左右顺序来遍历的，因此所有叶结点间的先后关系都是相同的。

2． 假定采用带头结点的单链表保存单词,当两个单词有相同的后缀时,则可共享相同的后缀存储空间。例如,“loading ”和“being ”的存储映像如下图所示。

图 存储映像本意图

设str1和str2分别指向两个单词所在单链表的头结点,链表结点结构为

,请设计一个时间上尽可能高效的算法,找出由str1和str2所指的两个链表共同后缀的起始位置(如图中字符i 所在结点的位置p)。要求:

(1)给出算法的基本设计思想。

(2)根据设计思想,采用C 或或JA V A 语言描述算法,关键之处给出注释。

(3)说明你所设计算法的时间复杂度。

【答案】(1)算法的基本设计思想:

①分别求出str1和str2所指的两个链表的长度m 和n ;

②将两个链表以表尾对齐:令指针p 、q 分别指向str1和str2的头结点,若m>n ,则使p 指向链表中的第n+1个结点;若m

③反复将指针p 和q 同步向后移动,并判断它们是否指向同一结点。若p 和q 指向同一结点,则该点即为所求的共同后缀的起始位置。

(2)用C 语言算法描述如下:

考研专业课资料、辅导、答疑一站式服务平台

第 3 页，共 37 页

(3)参考答案的时间复杂度为:

或。其中m 、n 分别为两个链表的长度。 3． 假设以S 和X 分别表示入栈和出栈操作，则对初态和终态均为空的栈操作可由S 和X 生成的

序列表示(如SXSX)。 (1)试指出判别给定序列是否合法的一般规则；

(2)两个不同合法序列(对同一输入序列)能否得到相同的输出元素序列?如能得到，请举列说明。

【答案】(1)通常有两条规则。第一是给定序列中S 的个数和X 的个数相等；第二是从给定序列的开始，到给定序列中的任一位置，S 的个数要大于或等于X 的个数。

(2)可以得到相同的输出元素序列。例如，输入元素为A ，B ，C ，则两个输入的合法序列ABC 和BAC 均可得到输出元素序列ABC 。对于合法序列ABC ，使用SXSXSX 操作序列；对于合法序列BAC ，使用SSXXSX 操作序列。

4． 设目标为

，模式为 (1)计算模式p 的nextval 函数值；

(2)不写出算法，只画出利用KMP 算法进行模式匹配时每一趟的匹配过程。

【答案】(1)P 的nextval 函数值为0110132(P 的next 函数值为0111232)。

(2)利用KMP(改进的nextval)算法，每趟匹配过程如下:

第一趟匹配:abcaabbabcabaacbacba

abcab(i ＝5，j ＝5)

第二趟匹配:abcaabbabcabaacbacba

abc(i ＝7jj ＝3)

第三趟匹配:abcaabbabcabaacbacba

a(i ＝7，j ＝l)

第四趟匹配:abcaabbabcabaacbacba

(成功)abcabaa(i ＝15，j ＝8)

5． 索引顺序存取方法(ISAM)中，主文件已按关键字排序，为何还需要主关键字索引？

【答案】ISAM 是专为磁盘存取设计的文件组织方式。即使主文件关键字有序，但因磁盘是以盘组、柱面和磁道(盘面)三级地址存取的设备，因此通常对磁盘上的数据文件建立盘组、柱面和磁道(盘面)三级索引。在ISAM 文件上检索记录时，先从主索引(柱面索引的索引)找到相应柱面索引。再从柱面索引找到记录所在柱面的磁道索引，最后从磁道索引找到记录所在磁道的第一个记录的位置，由此出发在该磁道上进行顺序查找直到查到为止；反之，若找遍该磁道而未找到所

考研专业课资料、辅导、答疑一站式服务平台

第 4 页，共 37 页 查记录，则文件中无此记录。

6． 我们知道，对于n 个元素组成的线性表进行快速排序时，所需进行的比较次数与这n 个元素的初始排序有关。问:

当n=7时，在最好情况下需进行多少次比较?请说明理由。

当n=7时，给出一个最好情况的初始排序的实例。

当n=7时，在最坏情况下需进行多少次比较?请说明理由。

当n=7时，给出一个最坏情况的初始排序的实例。

【答案】(1)在最好情况下，每次划分能得到两个长度相等的子文件。假设文件的长度

，那么第一趟划分得到两个长度均为

的子文件，第二趟划分得到4个长度均为的子文件，以此类推，总共进行

(n+1)趟划分，各子文件的长度均为1，排序完毕。当n=7时，k=3，在最好情况下，第一需比较6次，第二趟分别对两个子文件(长度均为3，k=2)进行排序，各需2次，

共10次即可。

(2)在最好情况下快速排序的原始序列实例:4，1，3，2，6，5，7。

(3)在最坏情况下，若每次用来划分的记录的关键字具有最大(或最小)值，那么只能得到左(或右)子文件，其长度比原长度少1。因此，若原文件中的记录按关键字递减次序排列，而要求排序后按递增次序排列时，快速排序的效率与起泡排序相同，其时间复杂度为

。所以当n=7时，最坏情况下的比较次数为21次。

(4)在最坏情况下快速排序的初始序列实例:7，6，5，4，3，2，1，要求按递增排序。

7． 二叉树的带权路径长度(WPL)是二叉树中所有叶结点的带权路径长度之和,给定一棵二叉树T ,采用二叉链表存储,节点结构为:

其中叶节点的weight 域保存该结点的非负权值。设root 为指向T 的根节点的指针,设计求T 的WPL 的算法。要求:

(1)给出算法的基本设计思想;

(2)使用C 或语言,给出二叉树结点的数据类型定义;

(3)根据设计思想,采用C 或语言描述算法,关键之处给出注释。 【答案】(1)算法的基本思路是利用利用递归的思想来求解二叉树的带权路径长度,如果当前节点不是叶子节点,那么当前节点为根的树的带权路径长度便等于它的子树的带权路径长度之和,对于此函数要传入一个当前节点的树高的形参,那么递归调用孩子节点时只需要将这个形参加一即可。

(2)typedef struct BiNode

(3)具体算法实现如下:

考研专业课资料、辅导、答疑一站式服务平台

第 5 页，共 37 页

如果当前节点为空节点

如果当前节点的左右孩子节点都为空,即当前节点为叶子节点,直接返回当前节点的

WPL

如果当前节点不是叶子节点,则对当前节点的左右子树进行递归,返回左右子树WPL 之

和

8． 某计算机字长16位，采用16位定长指令字结构，部分数据通路结构如下图所示，图中所有控制信号为1时表示有效，为0时表示无效，例如控制信号MDRinE 为1表示允许数据从DB 打入MDR ，MDRin 为1表示允许数据从内总线打入MDR 。假设MAR 的输出一直处于使能状态。加法指令“ADD(Rl)，R0”的功能为(R0) ＋((R1))—(R1)，即将R0中的数据与R1的内容所指主存单元的数据相加，并将结果送入R1的内容所指主存单元中保存。

下表给出了上述指令取指和译码阶段每个节拍(时钟周期)的功能和有效控制信号，请按表中描述方式用表格列出指令执行阶段每个节拍的功能和有效控制信号。

本文来源：https://www.bwwdw.com/article/hspl.html