2020年清华大学912计算机专业基础综合考研复试核心题库之数据结构应用题精编

特别说明

本书根据最新复试要求并结合历年复试经验对该题型进行了整理编写，涵盖了这一复试科目该题型常考及重点复试试题并给出了参考答案，针对性强，由于复试复习时间短，时间紧张建议直接背诵记忆，考研复试首选资料。

版权声明

青岛掌心博阅电子书依法对本书享有专有著作权，同时我们尊重知识产权，对本电子书部分内容参考和引用的市面上已出版或发行图书及来自互联网等资料的文字、图片、表格数据等资料，均要求注明作者和来源。但由于各种原因，如资料引用时未能联系上作者或者无法确认内容来源等，因而有部分未注明作者或来源，在此对原作者或权利人表示感谢。若使用过程中对本书有任何异议请直接联系我们，我们会在第一时间与您沟通处理。

因编撰此电子书属于首次，加之作者水平和时间所限，书中错漏之处在所难免，恳切希望广大考生读者批评指正。

重要提示

本书由本机构编写组多位高分在读研究生按照考试大纲、真题、指定参考书等公开信息潜心整理编写，仅供考研复试复习参考，与目标学校及研究生院官方无关，如有侵权请联系我们立即处理。

一、2020年清华大学912计算机专业基础综合考研复试核心题库之数据结构应用题精编

1．画出下列广义表的存储结构图，并利用取表头和取表尾的操作分离出原子e。

【答案】

2．己知广义表，运用求表头和表尾运算head和tail提取出GL中原子f的运算是什么？

【答案】取出GL中原子f的运算是。计算过程如下:

3．判定序列是否是堆，如果不是，则把它调整为堆。试给出堆排序方法的平均时间性能、在最坏情况下的时间性能和辅助存储量，并与快速排序方法在以上三方面进行比较。

【答案】它不是堆。调整过程如下图1、2、3所示。堆排序与快速排序的性能比较如下：

图1

图2

图3

4．如果给出了一个二叉树结点的前序序列和对称序序列，能否构造出此二叉树?若能，请证明之。若不能，请给出反例。如果给出了一个二叉树结点的前序序列和后序序列，能否构造出此二叉树?若能，请证明之。若不能，请给出反例。

【答案】给定二叉树结点的前序序列和对称序(中序)序列，可以唯一确定该二叉树。因为前序序列的第一个元素是根结点，该元素将二叉树中序序列分成两部分，左边(设个元素)表示左子树，若左边无元素，则说明左子树为空；右边(设r个元素)是右子树，若为空，则右子树为空。根据前序遍历中“根-左子树-右子树”的顺序，则由从第二元素开始的个结点序列和中序序列根左边的个结点序列构造左子树，由前序序列最后r个元素序列与中序序列根右边的r个元素序列构造右子树。

由二叉树的前序序列和后序序列不能唯一确定一棵二叉树，因无法确定左、右子树两部分。例如，任何结点只有左子树的一棵二叉树和任何结点只有右子树的一棵二叉树，其两棵树的前序序列相同，后序序列相同，但却是两棵不同的二叉树。

5．设有13个初始归并段，其长度分别为28、16、37、42、5、9、13、14、20、17、30、12和18。试画出4路归并时的最佳归并树，并计算它带权路径长度WPL。

【答案】最佳归并树如下图所示：

图

WPL=(5+9+12+13+14+16+17+18+20+28+23+37)x2+42=480

6．假定有下列n×n矩阵(n为奇数)

如果用一维数组B按行主次序存储A的非零元素，问：

(1)A中非零元素的行下标与列下标的关系；

(2)给出A中非零元素的下标与B中的下标R的关系；

(3)假定矩阵中的每个元素占一个存储单元且B的起始地址为，给出利用的下标定位在B 中的位置公式。

【答案】(1)非零元素满足i=j或i+j=n+l。

(2)当时，

当时，k=n;

当时，

(3)位置公式为，将(2)中k代入即得。

7．假设某循环单链表非空，且无表头结点也无表头指针，指针p指向该链表中的某结点。请设计一个算法，将p所指结点的后继结点变为p所指结点的前驱结点。

【答案】首先找到P的前驱结点，然后将前驱结点和后继结点交换。算法描述如下：