。
二、方法选择（共10分，每小题5分）1、设有10000个无序元素，要求找出前30个最大元素，在下列排序方法（归并排序、基数排序、快速排序、堆排序、插入排序）中哪些方法最好，为什么？2、在一个待排序的序列中，只有很少量元素不在自己最终的正确位置上，但离他们的正确位置都不远，简述应使用哪种排序方法最好。
三、构造结果：（共40分，每小题8分）1、给定叶结点权值：（3，4，5，6，7，8，9），构造哈夫曼树，并计算其带权路径长度。2、已知一二叉树中序序列为BDCAEF，前序序列为ABCDEF，给出其对应的二叉树。3、已知二维数组A100200采用行序为主方式存储，每个元素占K个存储单元，已知A00的存储地址是1500，给出A6080的存储地址。4、给出12个结点的折半判定树，并计算其在等概率情况下的平均查找长度。5、在地址空间012的散列区中，对以下关键字序列：（Ja
，Feb，Apr，May，Ju
，Jul，Aug，Sep，Oct）建哈希表，设哈希函数为HXi2，其中i为关键字中的第一个字母在字母表中的序号，处理冲突可选用线性探测法或链地址法之一，要求构造哈希表，并求出在等概率的情况下查找成功与不成功的平均查找长度。
四、编写算法（20分）设主串s和子串t分别以单链表存储，t和s中的每个字符均用一结点表示（如图）。
实现在链式存储方现的位置指针。
data
Next
式下的模式匹配，即求子串t在主串s中第一次出
五、编写算法（20分）
已知二叉排序树按二叉链表形式存储，树中结点各不相同，欲得到一个由小到大的结点值递增序列，编写算法达到要求结果。
六、编写算法（20分）无向图采用邻接表方式存储，编写出广度优先遍历访问的算法。
七、编写语句（10分）在前序线索树中要找出X结点的后继结点。LtagLcDataRtagRc
西北大学2014年招收攻读硕士学位研究生试题
f科目名称：数据结构适用专业：计算机技术、软件工程答案请答在答题纸上，答在本试题上的答案一律无效。
科目代码：852共2页
一、简答每小题6分，共30分1、简述四类基本的数据逻辑关系，并用图表示。2、特殊矩阵的压缩原则有哪些？3、什么是平衡二叉排序树？平衡因子的取值范围是什么？4、具有
个结点的k叉树，若采用k叉树链表存储，则空链域有多少个？（写出求解步骤）。5、递归进层时需要做哪些事？
二、分析与方法选择每小题10分，共30分1、在10000个元素中，欲找出10个最大的元素，采用哪些排序方法较好。简述原因。
2、在一个连通无向图上，欲求顶点vi到顶点vj（vivjr