您的位置:考研教育网> >历年试题>考研专业课> 正文

浙江理工大学2008年考研数据结构试题

考研教育网   2008-11-11 15:41 【 】【我要纠错

  一、选择填空题(每空格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 的双亲是 :%c\n,x1->data);

  else printf( 结点 x 是树根 \n);

  if(x2!=NULL) printf( 结点 x 的左孩子是 :%c\n,x2->data);

  else printf( 结点 x 无左孩子 \n);

  if(x3!=NULL) printf( 结点 x 的右孩子是 %c\n,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)

  请点击查看更多浙江理工大学考研相关信息>>>

  相关链接:浙江理工大学考研专业课试题汇总

◇ 编辑推荐
·2015年考研复习:政治 英语 数学  专业课 · 2014年考研真题及答案汇总   历年考研真题
· 考研网上辅导热招!  ·2015年考研报考指南   ·历年考研国家分数线汇总   复试信息
考研网上辅导课程 特色班 精品班 实验班
学费 购买 学费 购买 学费 购买
公共课 政 治 800元 购买 1500元 购买 3500元 购买
英 语 800元 购买 1500元 购买 3500元 购买
数 学 800元 购买 1500元 购买 3500元 购买

专业课

视频

《管理类联考综合》、《会计学》、《中医综合》、《西医综合》、《法硕联考综合(法学)》、
《法硕联考综合(法学)》、《法硕联考专业基础(法学)》、《法硕联考专业基础(非法学)》

专业课

资料

952所考研院校、57300个招生专业、245000份考研辅导课件、核心纲要、考研笔记、内部题库现正热卖!

说明 专业课请到考研开放平台上注册及缴费----帮助