一、简答 [每小题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、以单链表作存储结构实现线性表的就地逆置算法，即在原表的存储空间将线性表（）逆置为（）。（记得不太清楚了，反正就是耿国华数据结构第2章习题中的一道程序题。） 2、在中序线索树中找结点前驱（或在中序线索树中找结点后继）。（课本上的源程序。） 五、编写算法 [共15分] 这道题忘记了。反正我这道题不太会做，但是也程序写的满满的。记住即使不会做，也得写，写的满满的较好。只要你写老师都给分，估计给个10来分吧。如果你不答，空着的话，就只能得0分了。
6、 编写算法 [共15分] 编写算法，实现哈希链表的存储，哈希函数是Hkkp，哈希表长为m，p为小于等于m的最大素数。处理冲突的方法采用线性探测再散列。
备注我这道题也不太会做，但是也程序写的满满的。记住即使不会做，也得写，写的满满的较好。只要你写老师都给分，估计给个10来分吧。如果你不答，空着的话，就只能得0分了。
西北大学2014年招收攻读硕士学位研究生试题 科目名称数据结构 科目代码852 适用专业计算机技术、软件工程 共2页 答案请答在答题纸上，答在本试题上的答案一律无效。
一、简答 [每小题6分，共30分] 1、简述四类基本的数据逻辑关系，并用图表示。
2、特殊矩阵的压缩原则有哪些 3、什么是平衡二叉排序树平衡因子的取值范围是什么 4、具有n个结点的k叉树，若采用k叉树链表存储，则空链域有多少个（写出求解步骤）。
5、递归进层时需要做哪些事 二、分析与方法选择 [每小题10分，共30分] 1、在10000个元素中，欲找出10个最大的元素，采用哪些排序方法较好。简述原因。
2、在一个连通无向图上，欲求顶点vi到顶点vj（）的最短简单路径，应采用深度优先遍历还是广度优先遍历简述原因。
3、分析冒泡排序的性能（最好情况、最坏情况）。
三、构造结果 [每小题6分，共30分] 1、已知一棵二叉树的前序遍历的结果是ABDCEGF，中序遍历的结果是BDAEGCF，试画出这课二叉树，并将其转换为相应的森林。
2、假设T是一棵高度为5的二叉树，T中只有度为0和度为2的结点，给出 （1）T树可能的最大结点数，并画出这样的一棵二叉树。
（2）T树可能的最小结点数，并画出这样的一棵二叉树。
3、依次输入（26，30，15，10，28，19，18，22），构造二叉排序树，并计算等概率情况下的查找成功的平均查找长度。
4、画出10个元素的折半判定树，并计算等概率情况下查找成功的平均查找长度。
5、已知关键字集合{50，52，85，22，96，17，36，55}，以第一个关键字中轴元素，写出一趟快速排序的结果。
四、编写算法 [每小题10分，共30分] 1、编写算法void AdjustLinkList L，其功能是以第一个元素为基准，将小于该元素的结点全部放到前面，大于该元素的结点全部放到其后。
2、要求循环队列不损失一个空间全部都能得到利用，设置一个标志域tag，以tag为0或1来区分头尾指针相同时的列状态的空与满，请编写与此结构相应的出队算法。
3、二叉树采用二叉链表结构存储，编写算法实现统计二叉树中的结点个数。
五、编写算法 [共15分] 二叉树采用二叉链表结构存储，编写实现二叉树后序线索化的算法。
六、编写算法 [共15分] 编写算法，由依次输入的顶点数、弧数和各顶点信息、弧信息建立有向图的邻接表存储结构。
西北大学2013年招收攻读硕士学位研究生试题 科目名称数据结构 科目代码852 适用专业计算机技术、软件工程 共2页 答案请答在答题纸上，答在本试题上的答案一律无效。
[注] 算法描述采用类语言，算法应加上必要的注释 一、简答问题 （共30分，每小题5分） 1、线性结构与非线性结构的差别。
2、说明在图的遍历中，设置访问标志数组的作用。
3、简述数组和字符串属于线性表的原因。
4、算法特性与算法时间复杂度。
5、数据类型与抽象数据类型。
6、简述稳定排序含义，给出一种不稳定排序方法名称并证明。
二、方法选择 （共10分，每小题5分） 1、设有10000个无序元素，要求找出前30个最大元素，在下列排序方法（归并排序、基数排序、快速排序、堆排序、插入排序）中哪些方法最好，为什么 2、在一个待排序的序列中，只有很少量元素不在自己最终的正确位置上，但离他们的正确位置都不远，简述应使用哪种排序方法最好。
三、构造结果（共40分，每小题8分） 1、给定叶结点权值（3，4，5，6，7，8，9），构造哈夫曼树，并计算其带权路径长度。
2、已知一二叉树中序序列为BDCAEF，前序序列为ABCDEF，给出其对应的二叉树。
3、已知二维数组A[100][200]采用行序为主方式存储，每个元素占K个存储单元，已知A[0][0]的存储地址是1500，给出A[60][80]的存储地址。
4、给出12个结点的折半判定树，并计算其在等概率情况下的平均查找长度。
5、在地址空间012的散列区中，对以下关键字序列（Jan，Feb，Apr，May，Jun，Jul，Aug，Sep，Oct）建哈希表，设哈希函数为HXi/2，其中i为关键字中的第一个字母在字母表中的序号，处理冲突可选用线性探测法或链地址法之一，要求构造哈希表，并求出在等概率的情况下查找成功与不成功的平均查找长度。
四、编写算法 （20分） data Next 设主串s和子串t分别以单链表存储，t和s中的每个字符均用一结点表示（如图）。
实现在链式存储方式下的模式匹配，即求子串t在主串s中第一次出现的位置指针。
五、编写算法 （20分） 已知二叉排序树按二叉链表形式存储，树中结点各不相同，欲得到一个由小到大的结点值递增序列，编写算法达到要求结果。
六、编写算法 （20分） 无向图采用邻接表方式存储，编写出广度优先遍历访问的算法。
七、编写语句 （10分） 在前序线索树中要找出X结点的后继结点。
Ltag Lc Data Rtag Rc 西北大学2012年招收攻读硕士学位研究生试题 科目名称数据结构 科目代码852 适用专业计算机技术、软件工程 共2页 答案请答在答题纸上，答在本试题上的答案一律无效。
[注] 算法描述可选用类语言，并加上必要的注释 一、简答问题 【30分，每小题6分】 1、简述数组、广义表属于线性表原因。
2、算法特性与算法时间复杂度。
3、线性结构与非线性结构的差别。
4、图遍历中设置访问标志数组的作用。
5、数据类型的含义与作用。
二、方法选择 【20分，每小题10分】 1、只想得到N个元素序列中第K个最大元素之前的部分递减有序序列（KN），列出2种速度快的方法名称与原因。
2、在数轴上有n个彼此不交的相邻区间，每个区间下、上界都是整数，按区间位置从左到右依次编号为1N。试问要查找某个给定值x所在区间，你认为应选择什么方法查找最快，简述原因。
三、写出要求结果 【共40分，每小题8分】 1、已知计算阿克曼递归函数定义如下 Akmint m，int n { ifm0 returnn1；
else ifn0 returnakmm-1，1; else returnakmm-1，akmm，n-1；
} 请给出执行Akm2，1时，递归调用顺序及执行结果。
2、已知关键字序列为（75，33，52，41，12，88，66，27）哈希表长为10，哈希函数为HKK MOD 7，解决冲突用线性探测再散列法，要求构造哈希表，并求出等概率下查找成功与不成功的平均查找长度。
3、给定权值{8，12，4，5，26，16，9}，构造一棵哈夫曼树，并计算其带权路径长度。
4、在中序线索树中，要找出X结点的前驱结点，请写出相关函数定义。
Ltag Lc Data Rtag Rc 5、已知一棵二叉树，其中序序列BDAEC，后序序列DBECA，构造该二叉树。
四、编写算法 【15分】 要求实现在链式存储方式下的模式匹配。
data Next 已知主串s和子串t分别以单链表存储，t和s中每个字符均用一结点表示（如图） 即求子串t在主串s中第一次出现的位置指针。
五、编写算法 【共30分，每小题15分】 （1）要求二叉树按二叉链表存储，写建立一棵二叉树的算法。[15分] （2）编写输出二叉树中的非叶子结点的算法。[15分] 六、编写算法 【15分】 已知有N个结点的无向图，采用邻接表结构存储，要求编写算法实现广度优先搜索策略遍历图中所有顶点。
西北大学2011年招收攻读硕士学位研究生试题 科目名称数据结构 科目代码849 适用专业计算机技术、软件工程 共2页