2017年信阳师范学院计算机学科专业基础综合之数据结构复试实战预测五套卷
● 摘要
一、应用题
1. 试叙述动态存储分配伙伴系统的基本思想,它和边界标识法不同点是什么?
【答案】(1)动态存储分配伙伴系统的基本思想
在伙伴系统中,无论占用块或空闲块,其大小均为(k 为大于等于0的正整数)。若内存容
量为
则空闲块大小只能是由同一大块分裂而得的两个小块互称“伙伴空
(若)
,
如内存大小为
间”
或的块分裂成两个大小为的块。只有两个“伙伴空间”才能合并成一个大(若
(2)和边界标识法的不同
边界标识法在每块的首尾均有“占用”/“空闲”标志,空闲块合并方便。伙伴系统算法简单、速度快,但只有互为伙伴的两个空闲块才可合并,因而易产生虽空闲但不能归并的碎片。
2. 对于后序线索二叉树,怎样査找任意结点的直接后继? 对于中序线索二叉树,怎样査找任意结点的直接前驱?
【答案】(1)后序线索树中结点的后继的方法如下:根结点无后继:当结点的rtag=1时,其右线索指向后继;当结点的rtag=0且是其双亲的右孩子,或是双亲的左孩于且双亲无右孩时,其双亲是该结点的后继;当结点是其双亲的左孩子且双亲有右孩子时,其双亲结点右子树种最左下的叶结点是其后继。
(2)对中序线索二叉树的某结点,若其左标记等于1,则左孩子为线索,指向直接前驱;否则其前驱是其左子树上按中序遍历的最后一个结点。
3. 给出一组关键字:29,18,25,47,58,12,51,10,分别写出按下列各种排序方法进行排序时的变化过程:
(1)归并排序,每归并一次书写一个次序。
(2)快速排序,每划分一次书写一个次序。
(3)堆排序,先建成一个堆,然后每从堆顶取下一个元素后,将堆调整一次。
【答案】(1)2—路归并第一趟:18,29,25,47,12,58,10,51:
第二趟:18,25,29, 47,10,12,51,58;
第三趟:10,12,18,25,29,47,51,58
(2)快速排序第一趟:10,18,25,12,29,58,51,47;
第二趟:10,18,25,12,29,47,51,88;
第三趟:10,12,18,25,29,47,51,88
第 2 页,共 33 页 空间。起始地址为P ,
大小为的内存块,其伙伴的起始地址为:)。
(3)堆排序
建大堆:58,47,51,29,18,12,25,10;
①51,47,25,29,18,12,10,58;
②47,29,25,10,18,12,51,58;
③29,18,25,10,12,47,51,58;
④25,18,12,10,29,47,51,58;
⑤18,10,12,25,29, 47,51,58;
⑥12,10,18,25,29,47,51,58;
⑦10,12,18,25,29, 47,51,58
4. 设内存中可利用空间已连成一个单链表,对用户的存储空间需求,一般有哪三种分配策略?
【答案】(1)首次适配法
从链表头指针开始查找,找到第一个大于等于所需空间的结点即分配。首次适配法适合事先不知道请求分配和释放信息的情况,分配时需查询,释放时插在表头。
(2)最佳适配法
链表结点大小增序排列,找到第一个大于等于所需空间的结点即分配。最佳适配法适用于请求分配内存大小范围较宽的系统,释放时容易产生存储量很小难以利用的内存碎片,同时保留那些很大的内存块以备将来可能发生的大内存量的需求,分配与回收均需查询。
(3)最差适配法
链表结点大小逆序排列,总从第一个结点开始分配,将分配后结点所剩空间插入到链表适当位置。最差适配法适合请求分配内存大小范围较窄的系统,分配时不查询,回收时查询,以便插入适当位置。
5. 在改进了的(无回溯)字符串模式匹配中,要先求next 数组的值。下面是求nextval 值的算法。
{在模式P 中求nextval 数组的值
}
算法中第4行有第六行中也有两处比较语句相同。请分析说明此两处比较
第 3 页,共 33 页
语句的含义是什么? 分析此算法在最坏情况下的时间复杂度是多少?
【答案】第4行的语句是测试模式串的第J 个字符是否等于第K 个字符,如是,则
语句的意义是,当第J 个字符在模式匹配中失指针J 和K 均増加1,继续比较。第6行的
配时,若第K 个字符和第J 个字符不等,则下个与主串匹配的字符是第K 个字符;否则,若第K 个字符和第J 个字符相等,则下个与主串匹配的字符是第K
个字符失配时的下一个(即
)。该算法在最坏情况下的时间复杂度
6. 假定采用带头结点的单链表保存单词,当两个单词有相同的后缀时,则可共享相同的后缀存储空间。例如,“loading ”和“being ”的存储映像如图所示。
图 存储映像7K 意图
设str1和str2分别指向两个单词所在单链表的头结点,链表结点结构为
符i 所在结点的位置p )。要求:
(1)给出算法的基本设计思想。
(2)根据设计思想,采用C 或
【答案】
(1)算法的基本设计思想:
①分别求出strl 和str2所指的两个链表的长度m 和n ;
②将两个链表以表尾对齐:令指针p 、q 分别指向strl 和str2的头结点,若
表中的第个结点;若则使q 指向链表中的第
表尾的长度相等。
③反复将指针p 和q 同步向后移动,并判断它们是否指向同一结点。若p 和q 指向同一结点,则该点即为所 求的共同后缀的起始位置。
(2)用C 语言算法描述如下:
两个指针同步向后移动
第 4 页,共 33 页 请设计一个时间上尽可能高效的算法,找出由strl 和str2所指的两个链表共同后缀的起始位置(如图中字或JA V A 语言描述算法,关键之处给出注释。 (3)说明你所设计算法的时间复杂度。 则使p 指向链个结点,即使指针p 和q 所指的结点到
相关内容
相关标签