当前位置：问答库＞考研试题

浙江理工大学

二O 一O 年硕士学位研究生招生入学考试试题

（*请考生在答题纸上答题，在此试题纸上答题无效）

第一部分：数据结构（本部分共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 为线性表的关键字），用开放地址法处理

d i =( di-1+m)%p (i=2,3,,…)；试编写程序算法，在H[0~p-1]冲突，其中：d 1=H(k)，

的散列地址空间中，对关键字序列a[0],a[1],…,a[p-1]构造哈希表（假设每个关键字最终都能找到地址），并计算输出在等概率情况下查找成功的平均查找长度。（20分）

4．已知单链表结构如下所示。头指针为head ，关键字域为key 。试编写程序构造一个单链表，将串s 中的每个字符存放到单链表中去（每个结点存放一个字符），同时在已有的单链表基础上，编写程序采用直接插入排序算法将单链表中的各个结点按字符值大小进行升序排序。（25分）

typedef struct node {

char key;

struct node *next;

} lnode;

第 1 页 共 4 页