浙江理工大学938数据结构与数据库技术2010年考研真题考研试题

第 1 页 共 4 页
浙江理工大学
二 O 一 O 年硕士学位研究生招生入学考试试题
考试科目：数据结构与数据库技术 代码：938
（*请考生在答题纸上答题，在此试题纸上答题无效）
第一部分：数据结构（本部分共 90 分）
一、程序设计题
1. 假设以带头节点的循环链表表示队列，并且只设一个队尾指针 rear，不设
队首指针，试编写相应的入队列和出队列一个结点的算法。（20 分）
2．一颗树的根其层次定义为 0。任何其它结点的层次定义为比它的双亲的层
次大 1。树的深度是层次最大的结点的层次。一颗树的内部路径长度是该树中
边的总数。已知二叉树的根结点为 t，其二叉链表结构定义如下：
typedef struct node {
char data;
struct node *lch,*rch;
int level;
} tnode ;
这里，data 为结点的名称，lch 为其左孩子，rch 为其右孩子，level 为结点的
层次。试编写非递归程序算法，输出这颗树的深度和内部路径长度。（25 分）
3．已知哈希(Hash)函数 H(k)=k%p（k 为线性表的关键字），用开放地址法处理
冲突，其中：d1=H(k)，di=( di-1+m)%p (i=2,3,,…)；试编写程序算法，在 H[0~p-1]
的散列地址空间中，对关键字序列 a[0],a[1],…,a[p-1]构造哈希表（假设每个关
键字最终都能找到地址），并计算输出在等概率情况下查找成功的平均查找长
度。（20 分）
4．已知单链表结构如下所示。头指针为 head，关键字域为 key。试编写程序
构造一个单链表，将串 s 中的每个字符存放到单链表中去（每个结点存放一个
字符），同时在已有的单链表基础上，编写程序采用直接插入排序算法将单链
表中的各个结点按字符值大小进行升序排序。（25 分）
typedef struct node {
char key;
struct node *next;
} lnode;