数据结构
适用专业:计算机技术、软件工程
答案请答在答题纸上,答在本试题上的答案一律无效。注编写程序可选用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