目录

2017年中山大学S3405005数学综合考试之数据结构复试实战预测五套卷（一） ................. 2 2017年中山大学S3405005数学综合考试之数据结构复试实战预测五套卷（二） ................. 9 2017年中山大学S3405005数学综合考试之数据结构复试实战预测五套卷（三） ............... 14 2017年中山大学S3405005数学综合考试之数据结构复试实战预测五套卷（四） ............... 20 2017年中山大学S3405005数学综合考试之数据结构复试实战预测五套卷（五） ............... 26

第 1 页，共 32 页

2017年中山大学S3405005数学综合考试之数据结构复试实战预测五套卷（一）

说明：本资料为2017复试学员内部使用，终极模拟预测押题，实战检测复试复习效果。 ————————————————————————————————————————

一、应用题

1． 假定有下列，

矩阵（n为奇数）

如果用一维数组B按行主次序存储A的非零元素，问： （1）A中非零元素的行下标与列下标的关系； （2）给出A中非零元素的下标位在B中的位置公式。

【答案】（1）主对角线上元素的坐标是i=j，副对角线上元素的坐标i和j有所以A中非零元素的行下标和列下标的关系是

或

的关系，

与B中的下标R的关系；

给出利用的下标

定

（3）假定矩阵中每个元素占一个存储单元且B的起始地址为

（2）非零元素分布在两条主、副对角线上，除对角线相交处一个元素（下称“中心元素”）外，其余每行都有两个元素。主对角线上的元素，在向量B中存储的下标是

副对角线上的元素，在中心元素前，在向量B中存储的下标是

在中心元素后，其下标如下：

（3）在B中的位置如下：

第 2 页，共 32 页

2． 已知世界六大城市为：北京（Pe）、纽约（N）、巴黎（Pa）、伦敦（L）、东京（T）、墨西哥，下表给定了这六 大城市之间的交通里程： （M）

（1）画出这六大城市的交通网络图； （2）画出该图的邻接表表示法；

（3）画出该图按权值递增的顺序来构造的最小（代价）生成树。 【答案】（1）这六大城市的交通网络图如图1所示：

图1

（2）该图的邻接表表示法如图2所示：

图2

（3）最小生成树有6个顶点与条边：V（G）={Pe，N，Pa，L, T，M}

E（G）=（ {（L, Pa, 3）, （Pe, T, 21）, （M, N, 32）, （L, N, 55）, （L, Pe, 81）}

3． 对给定文件（28，07，39，10，65，14，61，17，50，21）选择第一个元素28进行划分，写出其快速排序第一遍的排序过程。

【答案】快速排序的思想如下：首先将待排序记录序列中的所有记录作为当前待排序区域，，凡其关键字不大干枢轴的记录均移动至该记录之前，以第一个记录的关键字作为枢轴（或支点）

凡关键字不小于枢轴的记录均移动至该记录之后。致使一趟排序之后，记录的无序序

第 3 页，共 32 页

将分

割成两部分：

和

和且然后再递归地将

进行快速排序。快速排序在记录有序时蜕变为起泡排序，可用“三者取中”法

改善其性能，避免最坏情况的出现。本题解答如下：

初始序列：[28]，07，39，10，65，14，61，17，50，21 21移动：21，07，39，10，65，14，61，17，50，[] 39移动：21，07，[]，10，65，14，61，17，50，39 17移动：21，07，17，10，65，14，61，[]，50，39 65移动：21，07，17，10，[]，14，61，65，50，39 14移动：21，07，17，10，14，[28]，61，65，50，39

4． 请写出应填入下列叙述中（ ）内的正确答案。

某一工程作业的网络图如图1所示，其中箭头表示作业，箭头边的数字表示完成作业所需的天 数。箭头前后的圆圈表示事件，圆圈中的数字表示事件的编号。用事件编号的序列（例如0-2-7-9-11）表示进行作业的路径。

完成此工程的关键路径是（A）完成此工程所需的最少天数为（B）天，此工程中具有最大充，充裕天数是（D）裕天数的事件是（C）。关键路径上的事件的充裕天数是（E）。

图1

【答案】A. 0-2-6-9-11; B. 20; C.事件顶点1、5和7各充裕两天；D. 4天；E. 0

5． 为什么文件的倒排表比多重表组织方式节省空间？

…… 此处隐藏0字 ……

【答案】倒排表有两项，一是次关键字值，二是具有相同次关键字值的物理记录号，这些记录号有序且顺序存储，不使用多重表中的指针链接，因而节省了空间。

6． 给出模式串在KMP算法中的next和nextval数组。

【答案】模式串的next函数定义如下：

根据此定义，可求解模式串

的next和nextval值如下：

第 4 页，共 32 页