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

第 1 页 ，共 4 页
浙 江 理 工 大 学
2011 年硕士学位研究生招生入学考试试题
考试科目： 数据结构与数据库技术 代码：938
（请考生在答题纸上答题，在此试题纸上答题无效）
第一部分：数据结构（本部分共 90 分）
一、程序设计题
1. 已知一个单链表 L（结构定义如下），其头结点指针为 head。试编写一个函数，将
单链表 L 分解为一个链栈（即使用链表存储的堆栈）S 和一个链队（即使用链表存储
的队列）Q。要求将 L 中的偶数元素存放到链栈 S 中，L 中的奇数元素存放到链队 Q
中。（本题 30 分）
typedef struct lnode {
int data;
struct lnode *next;
} node;
2．一颗树中根结点的层次定义为 0，任何其它结点的层次定义为比它的双亲的层次大
1。已知二叉树的根结点为 t，其二叉链表结构定义如下：
typedef struct node {
char data;
struct node *lch,*rch;
int level;
} tnode ;
这里，data 为结点的名称，lch 为其左孩子，rch 为其右孩子，level 为结点的层次。试
编写非递归程序算法，计算树中每个结点的层次 level 的值。（本题 25 分）
3．试编写一个函数，利用二分（折半）查找算法在一个有序线性表中插入一个元素 x，
并保持线性表的有序性。已知有序线性表结构如下：
int maxsize=100;
struct node {
int key;
char ch;
};
typedef struct sqlist[maxsize];
这里，key 为线性表的关键字，ch 为其它数据域。（本题 20 分）