浙江理工大学2008年考研数据结构试题
一、选择填空题(每空格3分,本题共60分)
1.已知单链表结点的存储结构如下:
struct node {
int data;
struct node *next; };
这里,单链表的头指针为 head, 数据域为 data ,指针域为 next .试在下列 A~J 中选择一个正确答案,填入相应的空格处,分别实现下列四小题的算法功能,注意各个小题之间没有联系。
1)将单链表中值相同的多余结点删除。
void test1(struct node *head) {
struct node *p,*q,*r;
p=head;
while (p!=NULL) {
r=p;
(1)
while (q!=NULL) {
if (q->data==p->data) (2)
else r=q;
q=q->next;
}
(3)
}
}
2)将值为 y 的结点插入到值为 x 的结点之后,如果值为 x 的结点不存在,则将其插入到单链表的表尾。
void test2(struct node *head,int x,int y) {
struct node *p,*q,*r;
r=(struct node *)malloc(sizeof(struct node));
r->data=y;
int sgn=0;
p=head;
while (p!=NULL)&&(sgn==0) {
if (p->data==x) sgn=1;
(4)
p=p->next;
}
if (sgn==1) (5)
else (6)
q->next=r;
}
}
3)假设在上述单链表结点的存储结构中增加另一个指针域 prior ,将该单链表改造成双向循环链表 ( 假设该单链表中至少有一个结点 ) .
void test3(struct node *head) {
struct node *p,*q;
p=head;
while (p!=NULL) {
q=p->next;
if (q!=NULL) (7)
else {
(8)
head->prior=p;
break;
}
p=p->next;
}
}
4 )若采用单链表结构去存储一个堆栈,分别实现在堆栈中入栈和出栈一个元素的算法。
void test4(struct node *head,int x) {
struct node *p;
p=(struct node *)malloc(sizeof(struct node));
p->data=x;
p->next=head;
(9)
}
int test5(struct node *head) {
struct node *p;
if (head!=NULL) {
p=head;
(10)
x=p->data;
return(x); }
else exit(1);
}
本题选项:
(A)head=head->next; (B)head=p; (C)q=p; (D)q->prior=p;
(E)q=p->next; (F)p->next=head; (G)p=p->next; (H)r->next=p;
(I)r->next=q->next; (J)r->next=NULL;
2.已知二叉树结点的链表存储结构如下:
struct node {
char data;
struct node *lch,*rch; };
这里,树结点的数据域为 data ,左孩子指针域为 lch ,右孩子指针域为 rch ,根结点所在链结点的指针由 BT 给出。试在下列 A~J 中选择一个正确答案,填入相应的空格处,分别实现下列两个小题的算法功能,注意各个小题之间没有联系。
1)利用中序遍历算法,查找二叉树 BT 中值为 x 的这个结点的双亲、左孩子及右孩子。
void test6(struct node *BT,char x)
{
struct node *p,*q,*s[100];
struct node *x1,*x2,*x3;
int top=0;
x1=x2=x3=NULL;
p=BT;
while ((top!=0)||(p!=NULL)) {
if (p!=NULL) while(p!=NULL) {
top++;
s[top]=p;
p= (11)
}
else {
p=s[top];
(12)
if (p->data==x) {
(13) =p->lch;
(14) =p->rch;
}
q=p;
p=p->rch;
if (p!=NULL)&&(p->data==x) (15) =q;
}
}
if(x1!=NULL) printf( 结点 x 的双亲是 :%cn,x1->data);
else printf( 结点 x 是树根 n);
if(x2!=NULL) printf( 结点 x 的左孩子是 :%cn,x2->data);
else printf( 结点 x 无左孩子 n);
if(x3!=NULL) printf( 结点 x 的右孩子是 %cn,x3->data);
else printf( 结点 x 无右孩子 n);
}
2 )假设上述二叉树 BT 为一个二叉排序树,实现在该二叉排序树中插入一个结点 s 的算法。
void test7(struct node *BT,struct node *s)
{
struct node *p,*q;
if (BT==NULL) BT=s;
else {
(16)
while (p!=NULL) {
q=p;
if (s->data<p->data) (17)
else (18)
}
if(s->data<q->data) (19)
else (20)
}
}
本题选项:
(A)x1 (B)x2 (C)x3 (D)p=p->lch; (E)p=p->rch;
(F)p->lch; (G)p=BT; (H)q->lch=s; (I)q->rch=s; (J)top——;
二、算法程序设计题(每小题15分,本题共30分)
1.设哈希函数为HT,解决冲突的方法为外链地址法,哈希函数采用除留余数法(k%p,k为待删除的关键字,p为小于基本哈希表容量m的质数)。若哈希表中某个位置上的key域值为零,则表示该位置未被占用。试编写程序,实现从用哈希表中删除关键字k的算法(注意需要判断关键字是否存在)。
define m 100;
struct node
{ int key;
struct node *next;
}HT[m];
void test1(struct node HT[],int k,int p)
2.试 编写程序,实现用单链表表示的数据简单选择排序,并分析算法的时间复杂度。
这里结点的数据域为 data ,指针域为 next ,单链表的头结点为 head .
struct node
{ int data;
struct node *next; };
void test2(struct node *head)
相关链接:浙江理工大学考研专业课试题汇总
【浙江理工大学2008年考研数据结构试题】相关文章:
★ 第四军医大学1992年硕士研究生入学考试生物化学试题(2)
★ 中国人民大学2000年硕士研究生入学考试管理经济学与管理学试题
★ 武汉大学2002年硕士研究生考试新闻与传播学院新闻史论试题
- 2020-06-28【专业课试题】2021考研管综逻辑300道推理题及答案(21)
- 2020-05-27【专业课试题】2020考研管理类联考综合全国硕士研究生考试试题及答案(网友版)
- 2020-05-27【专业课试题】2020考研管综逻辑演绎推理类型试题及答案解析(查字典考研网版)
- 2020-05-27【专业课试题】2020考研管综逻辑分析推理类型试题及答案解析(查字典考研网版)
- 2020-05-27【专业课试题】2020考研管综初等数学算术部分试题解析及往年对比
- 2020-05-27【专业课试题】2020考研管综初数条件充分性判断部分试题答案及解析(查字典考研网版)
网友关注
- 【专业课试题】2018年四川大学055101英语笔译专业方向全日制考研复试分数线
- 【专业课试题】2018年四川大学100706药理学专业方向全日制考研复试分数线
- 【专业课试题】2018年四川大学071010生物化学与分子生物学专业方向全日制考研复试分数线
- 【专业课试题】2018年四川大学090302植物营养学专业方向全日制考研复试分数线
- 【专业课试题】2018年四川大学0302政治学专业方向全日制考研复试分数线
- 【专业课试题】2018年四川大学040303体育教育训练学专业方向全日制考研复试分数线
- 【专业课试题】2018年四川大学050201英语语言文学专业方向全日制考研复试分数线
- 【专业课试题】2018年四川大学071009细胞生物学专业方向全日制考研复试分数线
精品推荐
- 2021考研管综逻辑300道推理题及答案(21)
- 2020考研管理类联考综合全国硕士研究生考试试题及答案(网友版)
- 2020考研管综逻辑演绎推理类型试题及答案解析(查字典考研网版)
- 2020考研管综逻辑分析推理类型试题及答案解析(查字典考研网版)
- 2020考研管综初等数学算术部分试题解析及往年对比
- 2020考研管综初数条件充分性判断部分试题答案及解析(查字典考研网版)
- 2020考研管理类联考初数问题求解部分试题答案及解析(查字典考研网版)
- 2020考研管综初等数学数据分析部分试题解析及往年对比
- 2020考研管综初等数学平面图形部分试题解析及往年对比
- 2020考研管综初等数学空间几何体部分试题解析及往年对比