2025年西北大学计算机专硕研究生入学考试历年真题 .pdf

不飞则已，一飞冲天；不鸣则已，一鸣惊人。——《韩非子》

科目名称：数据结构科目代码：851

适用专业：计算机技术、软件工程共2页

答案请答在答题纸上，答在本试题上的答案一律无效。

一、简答［每小题6分，共30分］

1、简述四类基本的数据逻辑关系，并用图表示。

2、简述数组、广义表属于线性表原因。

3、算法的定义及特性。

4、什么是平衡二叉排序树？平衡因子的取值范围是什么？

5、简述稳定排序含义，给出两种稳定排序方法以及两种不稳定排序方法名称并证

明。

二、分析与方法选择［每小题10分，共30分］

1、折半查找法对待查找的列表哪两个要求？

答：必须采用顺序存储结构；必须按关键字大小有序排列。

2、分析快速排序的性能（最好情况、最坏情况）。

3、关于二叉树结点度数的计算。（牢记二叉树的5条性质，会计算二叉树及K叉树

相关的计算。）

三、构造结果［每小题8分，共40分］

1、已知一棵二叉树的前序序列及后序序列，给出其对应的二叉树。

备注：西大历年试卷都是给出前序序列、中序序列或者中序序列、后序序列，写

出对应的二叉树，这种题型很好做，且结果给出的二叉树唯一。但是2015年

试题给出的是已知前序序列、后序序列，求对应的二叉树，这题我们平时几乎都没做

过，但是其实也不难，往往给出前序序列、后序序列，构造的二叉树不是唯一的，但

是这次考题设置的巧妙，最后给出的结果二叉树应该是唯一的。这道题具体我也不

记得了，反正有点难，我也花了很长时间最后才做出来的。

2、图的两种存储结构及表示、深度优先搜索遍历、广度优先搜索遍历、最小生成树

的生成。

3、依次输入（26,30，15,10,28，19,18，22），构造二叉排序树，并计算等概

率情况下的查找成功的平均查找长度。

4、画出10个元素的折半判定树，并计算等概率情况下查找成功的平均查找长度。

百学须先立志。——朱熹

5、最小生成树生成的两种算法：普里姆算法、克鲁斯卡尔算法四、编写算法[每小

题10分，共20分]

1、以单链表作存储结构实现线性表的就地逆置算法，即在原表的存储空间将线性表

(a,a,,a)逆置为(a,a,,a)。(记得不太清楚了，反正就是耿国华《数据

12nnn11

结构》第2章习题中的一道程序题。)

2、在中序线索树中找结点前驱(或在中序线索树中找结点后继)。(课本上的源程

序。)

五、编写算法[共15分]这道题忘记了。反正我这道题不太会做，但是也程序写的

满满的。记住即使不会做，也得写，写的满满的较好。只要你写老师都给分，估计给

个10来分吧。

如果你不答，空着的话，就只能得0分了。

六、编写算法[共15分]

编写算法，实现哈希链表的存储，哈希函数是H(k)=k%p,哈希表长为mP

为小于等于m的最大素数。处理冲突的方法采用线性探测再散列。