问题【30分，每小题6分】1、简述数组、广义表属于线性表原因。2、算法特性与算法时间复杂度。3、线性结构与非线性结构的差别。4、图遍历中设置访问标志数组的作用。5、数据类型的含义与作用。
二、方法选择【20分，每小题10分】1、只想得到N个元素序列中第K个最大元素之前的部分递减有序序列（KN），列出2种速度快的方法名称与原因。2、在数轴上有
个彼此不交的相邻区间，每个区间下、上界都是整数，按区间位置从左到右依次编号为1N。试问：要查找某个给定值x所在区间，你认为应选择什么方法查找最快，简述原因。
三、写出要求结果【共40分，每小题8分】1、已知计算阿克曼递归函数定义如下：
Akmi
tm，i
t
ifm0retur
1；elseif
0retur
akmm1，1
felseretur
akmm1，akmm，
1；
请给出执行Akm2，1时，递归调用顺序及执行结果。2、已知关键字序列为：（75，33，52，41，12，88，66，27）哈希表长为10，哈希函数为：HKKMOD7，解决冲突用线性探测再散列法，要求构造哈希表，并求出等概率下查找成功与不成功的平均查找长度。3、给定权值8，12，4，5，26，16，9，构造一棵哈夫曼树，并计算其带权路径长度。4、在中序线索树中，要找出X结点的前驱结点，请写出相关函数定义。
LtagLcDataRtagRc
5、已知一棵二叉树，其中序序列BDAEC，后序序列DBECA，构造该二叉树。
四、编写算法【15分】要求实现在链式存储方式下的模式匹配。已知主串s和子串t分别以单链表存储，t和s中每个字符均用一结点表示（如图）
即求：子串t在主
data
Next
串s中第一次出现的位置指针。
五、编写算法【共30分，每小题15分】（1）要求二叉树按二叉链表存储，写建立一棵二叉树的算法。15分（2）编写输出二叉树中的非叶子结点的算法。15分
六、编写算法【15分】
已知有N个结点的无向图，采用邻接表结构存储，要求编写算法实现广度优先搜索策略遍历图中所有顶点。
西北大学2013年招收攻读硕士学位研究生试题
科目名称：数据结构
适用专业：计算机技术、软件工程
答案请答在答题纸上，答在本试题上的答案一律无效。注算法描述采用类语言，算法应加上必要的注释
科目代码：852共2页
一、简答问题（共30分，每小题5分）1、线性结构与非线性结构的差别。2、说明在图的遍历中，设置访问标志数组的作用。3、简述数组和字符串属于线性表的原因。4、算法特性与算法时间复杂度。
f5、数据类型与抽象数据类型。6、简述稳定排序含义，给出一种不稳定排序方法名称并证明r