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页
答案请答在答题纸上，答在本试题上的答案一律无效。
[注] 编写程序可选用C语言；
 算法描述采用类语言，应加上必要的注释；
 所有答案均要求写在答题纸上。
一、简答问题 （每小题6分，共30分）
1、四类数据结构名称及其关系图示。
2、为什么说数组和广义表是线性表的推广？
3、算法的定义与特性。
4、数据类型与抽象数据类型。
5、图遍历算法中设置访问标志数组的作用。
二、方法选择 （每小题10分，共20分）
1、快速排序方法的最坏最好情况是什么，简要分析说明理由。
2、二叉排序树中结点各不相同，欲得到一个由大到小的结点值递减序列，你认为应当采用什么方法，便可得到要求结果，简述原因。
三、构造结果 （每小题8分，共40分）
1、给定叶结点权值：（2，3，5，6，9，11），构造哈夫曼树，并计算其带权路径长度。
2、已知一二叉树中序序列BDCAEF，前序序列ABCDEF，给出其对应的二叉树。
3、已知二维数组A[M][N]采用行序为主方式存储，每个元素占K个存储单元，已知A[1][1]（设起始下标为1）的存储地址是100，给出A[i][j]的存储地址算式。
4、在地址空间0—12的散列区中，对以下关键字序列：
（Jan，Feb，Apr，May，Jun，Jul，Aug，Sep，Oct）建哈希表，设哈希函数为H(X)=i/2，其中i为关键字中的第一个字母在字母表中的序号，处理冲突可选用线性探测法或链地址法之一，要求构造哈希表，并求出在等概率的情况下查找成功与不成功的平均查找长度。


5、给出求N阶hanoi塔的函数定义如下：
hanoi(int n，char x，char y，char z)
{
if(n==1)  move(x，1，z)
else
{
hanoi(n-1，x，z，y)；
move(x，n，z)；
hanoi(n-1，y，x，z)；
}
}
请写出执行hanoi(3，a，b，c)时递归函数的实在参量变化及move的搬动过程。
四、编写算法 （每小题15分，共30分）
1、编写建立二叉树算法，要求二叉树按照二叉链表方式存储。 [15分]
2、已知二叉树采用二叉链表存储，要求编写算法，完成计算出二叉树中度为0、度为1的结点数目。 [15分]
五、编写程序 （15分）
要求实现如下功能：
1、键盘输入N个有序整数，建立数组存储；
2、输入关键字key，完成折半查找的功能。
六、编写算法 （15分）
已知二叉树采用二叉链表存储，编写算法实现按层次遍历二叉树。













西北大学2010年招收攻读硕士学位研究生试题
科目名称：数据结构                                   科目代码：848
适用专业：计算机技术、软件工程                     共2页
答案请答在答题纸上，答在本试题上的答案一律无效。
[注] 编写程序可选用C语言，
 算法描述采用类语言，算法应加上必要的注释；
 所有答案均要求写在答题纸上。
一、简答问题 [共30分，每小题6分]
1、简述字符串、栈属于线性表原因。
2、线性结构与非线性结构的差别。
3、算法定义与算法特性。
4、数据类型与抽象数据类型。
5、图遍历中设置访问标志数组的作用。
二、方法选择 [共20分，每小题10分]
1、说明稳定排序含义，并给出一种不稳定排序方法的名称与证明。
2、在一个连通无向图上，欲求从一点 到另一点 （ ）所经结点数目短路径，在深度优先搜索、广度优先搜索、从一点到其余各顶点的最短路径算法中，你认为最好选择哪种方法为基础，简述原因。
三、构造结果 [共40分，每小题8分]
1、构造10个结点的折半判定树，并计算查找成功的平均查找长度。
2、已知一二叉树中序序列为BDAEC，后序序列为DBECA，给出其对应的二叉树。
3、已知n阶下三角矩阵A（即当i<j时，有 ），按照压缩存储的思想，可以主对角线以下所有元素（包括主对角线上的元素）依次存放于一维数组B中。请从第一列开始，采用行序为主序，给出在B中确定元素 存放位置的公式。
4、二叉排序树采用二叉链表方式存放，树中结点值各不相同，欲得到一个由小到大的结点值递增序列，简述处理方法思路。


5、给出求N阶hanoi塔的函数定义如下：
hanoi(int n，char x，char y，char z)
{
if(n==1)  move(x，1，z)
else
{
hanoi(n-1，x，z，y)；
move(x，n，z)；
hanoi(n-1，y，x，z)；
}
}
请写出执行hanoi(3，a，b，c)时递归函数的实在参量变化及move的搬动过程。
四、编写程序 [共15分]
要求实现如下功能：
将数组C[1:n]中所有奇数移到偶数之前，要求时间复杂度为O(n)。
五、编写算法 [共30分，每小题15分]
（1）写一个建立二叉树的算法，要求二叉树按二叉链表存储。
（2）已知二叉树用二叉链表存储，要求写出算法，实现该二叉树左右子树交换。
fch    data    nsib
六、编写算法 [15分]
树采用孩子—兄弟存放，结点结构为
其中fch表示指向第一个孩子，nsib表示指向下一个兄弟。
编写算法，要求由根开始逐层输出树中的各条边，边输出格式为（ ）。
例：







输出为：AB，AC，AD，BE，BF，CG。



西北大学2014年招收攻读硕士学位研究生试题
科目名称：软件工程学科专业基础综合                     科目代码：844
适用专业：计算机系统结构  计算机应用技术           共2页
          信息安全        软件工程
答案请答在答题纸上，答在本试题上的答案一律无效。
[注] 编写程序可选用C语言，
 算法描述采用类语言，算法应加上必要的注释。
数据结构试题（75分）
一、简答问题 （共15分，每小题5分）
1、简述队列、广义表属于线性表原因。
2、排序稳定性的定义及证明不稳定排序的方法举例。
3、简述图的两类存储名称及结构示意。
二、写出要求结果 （共20分，每小题5分）
1、设哈希表长度为11，哈希函数H(K)=(K的第一字母在字母表中的序号)MOD 11，若输入顺序为（D，BA，TN，M，CI，I，K，X，TA），处理冲突方法为线性探测再散列或链地址法，要求构造哈希表，并求出等概率情况下查找成功与不成功的平均查找长度。
2、设有5000个无序元素，仅要求找出前10个最小元素，在下列排序方法（归并排序、冒泡排序、快速排序、堆排序、插入排序）中哪些方法快，为什么？
3、已知一棵二叉树，其中序序列DBCAFGE，前序序列ABDCEFG，构造该二叉树。
4、用于通信的电文由8个字母a，b，c，d，e，f，g，h组成，各字母在电文中出现的频率分别为5，25，3，6，10，11，36，4。试为这8个字母设计哈夫曼编码，并计算给出该电文编码的总长度（WPL带权路径长度）。
三、编写算法 （共10分）
已知二叉树采用二叉链表结构存放，要求统计二叉树中度为1结点个数和度为2的结点个数。


四、编写算法 （共15分）
1、键盘输入一组非零的整数序列，最后输入零为结束标志，要求根据输入建立一棵二叉排序树算法，采用二叉链表方式存放。 （10分）
2、给出按由大到小顺序输出此二叉排序树中结点值的算法。 （5分）
五、编写算法 （共15分）
已有无向图采用邻接表结构存储，要求按广度优先搜索策略编写求出所有连通子图的生成树（生成树中的边用（ ）格式输出）。


























西北大学2013年招收攻读硕士学位研究生试题
科目名称：软件工程学科专业基础综合                     科目代码：844
适用专业：计算机系统结构  计算机应用技术           共2页
          信息安全        软件工程
答案请答在答题纸上，答在本试题上的答案一律无效。
[注] 编写程序可选用C语言，
 算法描述采用类语言，算法应加上必要的注释。
数据结构试题（75分）
一、简答问题 （共15分，每小题5分）
1、简述数据类型和抽象数据类型的含义与关系。
2、简述数组、广义表属于线性表原因。
3、说明在图的遍历中，设置访问标志数组的作用。
二、写出要求结果 （共20分，每小题5分）
1、已知一棵二叉树，其中序序列DBCAFGE，后序序列DCBGFEA，构造该二叉树。
2、快速排序方法的最坏最好情况是什么，简要分析说明理由。
3、已知关键字序列为：（75，33，52，41，12，88，66，27）哈希表长为10，哈希函数为：H(K)=K MOD 7，解决冲突用线性探测再散列法，要求构造哈希表，并求出等概率下查找成功与不成功的平均查找长度。
4、给定叶结点权值：（3，4，5，6，7，8，9），构造哈夫曼树，并计算其带权路径长度。
三、编写程序 （共10分）
键盘输入n个有序值建立线性表（ ），按折半查找策略实现查找给定值为key的元素。
四、编写算法 （共15分）
已知有N个结点的无向图，采用邻接表结构存储，要求由根开始逐层输出连通子图中所有生成树中的各条边，边输出格式为（ ）。