数据结构
适用专业：计算机技术、软件工程
答案请答在答题纸上，答在本试题上的答案一律无效。注编写程序可选用C语言；
科目代码：849共2页
f算法描述采用类语言，应加上必要的注释；所有答案均要求写在答题纸上。
一、简答问题（每小题6分，共30分）1、四类数据结构名称及其关系图示。2、为什么说数组和广义表是线性表的推广？3、算法的定义与特性。4、数据类型与抽象数据类型。5、图遍历算法中设置访问标志数组的作用。
二、方法选择（每小题10分，共20分）1、快速排序方法的最坏最好情况是什么，简要分析说明理由。2、二叉排序树中结点各不相同，欲得到一个由大到小的结点值递减序列，你认为应当采用什么方法，便可得到要求结果，简述原因。
三、构造结果（每小题8分，共40分）1、给定叶结点权值：（2，3，5，6，9，11），构造哈夫曼树，并计算其带权路径长度。2、已知一二叉树中序序列BDCAEF，前序序列ABCDEF，给出其对应的二叉树。3、已知二维数组AMN采用行序为主方式存储，每个元素占K个存储单元，已知A11（设起始下标为1）的存储地址是100，给出Aij的存储地址算式。4、在地址空间012的散列区中，对以下关键字序列：（Ja
，Feb，Apr，May，Ju
，Jul，Aug，Sep，Oct）建哈希表，设哈希函数为HXi2，其中i为关键字中的第一个字母在字母表中的序号，处理冲突可选用线性探测法或链地址法之一，要求构造哈希表，并求出在等概率的情况下查找成功与不成功的平均查找长度。
5、给出求N阶ha
oi塔的函数定义如下：ha
oii
t
，charx，chary，charzif
1movex，1，zelseha
oi
1，x，z，y；movex，
，z；ha
oi
1，y，x，z；
请写出执行ha
oi3，a，b，c时递归函数的实在参量变化及move的搬动过程。
四、编写算法（每小题15分，共30分）
f1、编写建立二叉树算法，要求二叉树按照二叉链表方式存储。15分
2、已知二叉树采用二叉链表存储，要求编写算法，完成计算出二叉树中度为0、度为1的结点数目。15分
五、编写程序（15分）要求实现如下功能：1、键盘输入N个有序整数，建立数组存储；2、输入关键字key，完成折半查找的功能。
六、编写算法（15分）已知二叉树采用二叉链表存储，编写算法实现按层次遍历二叉树。
西北大学2012年招收攻读硕士学位研究生试题
科目名称：数据结构
适用专业：计算机技术、软件工程
答案请答在答题纸上，答在本试题上的答案一律无效。注算法描述可选用类语言，并加上必要的注释
科目代码：852共2页
一、简答r