loading^`
四、编写算法 （20分）
设主串s和子串t分别以单链表存储，t和s中的每个字符均用一结点表示（如图）。
data Next
实现在链式存储方式下的模式匹配，即求子串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个最大元素之前的部分递减有序序列（K< 2、在数轴上有n个彼此不交的相邻区间，每个区间下、上界都是整数，按区间位置从左到右依次编号为1—N。试问：要查找某个给定值x所在区间，你认为应选择什么方法查找最快，简述原因。 三、写出要求结果 【共40分，每小题8分】 1、已知计算阿克曼递归函数定义如下： Akm(int m，int n) { if(m==0) return(n+1)； else if(n==0) return(akm(m-1，1)); else return(akm(m-1，akm(m，n-1)))； } 请给出执行Akm(2，1)时，递归调用顺序及执行结果。 2、已知关键字序列为：（75，33，52，41，12，88，66，27）哈希表长为10，哈希函数为：H(K)=K MOD 7，解决冲突用线性探测再散列法，要求构造哈希表，并求出等概率下查找成功与不成功的平均查找长度。 ^` 3、给定权值{8，12，4，5，26，16，9}，构造一棵哈夫曼树，并计算其带权路径长度。 4、在中序线索树中，要找出X结点的前驱结点，请写出相关函数定义。 Ltag Lc Data Rtag Rc 5、已知一棵二叉树，其中序序列BDAEC，后序序列DBECA，构造该二叉树。 四、编写算法 【15分】 要求实现在链式存储方式下的模式匹配。 已知主串s和子串t分别以单链表存储，t和s中每个字符均用一结点表示 （如图） data Next 即求：子串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分） 已知二叉树采用二叉链表存储，编写算法实现按层次遍历二叉树。