数据结构考试题参考答案
1、设顺序表L中的数据元素递增有序。试写一算法,将数据元素x插入到顺序表L的适当位置,以保持该表的有序性。
解:存储结构为:
typedef  struct  SeqList
{ DataType  *data;
  int MaxLen;
  int  len;
}SeqList;
算法如下:
void insertLx(SeqList &L, DataType x)
{ if(L.len==L.maxlen) return;
int i=L.len-1;
while(i>=0 && x<L.data[i])
{ L.data[i+1]=L.data[i]; i=i-1;}
L.data[i+1]=x; L.len++;
}
2、试写一个算法,在带头结点的单链表L的元素x前插入一个结点y。
解:存储结构如下:
typedef  struct  Lnode
{ElemType data;
struct Lnode *next;
二叉树中序遍历非递归算法
}Lnode,  *LinkList;
算法如下:
void  insert_y_before_x(LinkList  L, ElemType  x, ElemType y)
{ Lnode  *q,  *p=L;
  while(p->next && p->next->data!=x)  p=p->next;  //x的前驱结点p;
if(!p->next) return;  // 若不存在结点x,则返回;
q=new Lnode;
q->data=y; q->next=p->next;  p->next=q;
}
3、试写一个算法,统计带头指针的单链表L的元素个数。
解:存储结构如下:
typedef  struct  Lnode
{ElemType data;
struct Lnode *next;
}Lnode,  *LinkList;
算法如下:
int length(LinkList L)
{ int len=0;
Lnode *p=L;
while(p) { len++;  p=p->next; }
return  len;
}
注:如果单链表是带头结点的,则算法如下:
int length(LinkList L)
{ int len=0;
Lnode *p=L->next;;
while(p) { len++;  p=p->next; }
return  len;
}
4、试写一个算法,在带头结点的单链表L的第k个结点后插入一个结点x。
解:
存储结构如下:
typedef  struct  Lnode
{ElemType data;
struct Lnode *next;
}Lnode,  *LinkList;
算法如下:
void  insert_after_k( LinkList L,  int  k,  ElemType  x)
{ if(k<0) return;
Lnode *q, *p=L;
int i=0;
while(p && i<k) {i++;  p=p->next; }  //到第k个结点p;
if(!p) return;  //若不存在第k个结点,则返回;
q=new Lnode;  q->data=x;  q->next=p->next;  p->next=q;
}
注:如果是在L的第k个结点前插入一个结点,则第k-1个结点p,然后插入。
5、试写一个算法,在带头结点的单链表L中删除所有的数据元素为x的结点。
解:
存储结构如下:
typedef  struct  Lnode
{ElemType data;
struct Lnode *next;
}Lnode,  *LinkList;
算法如下:
void  Delete_all_x(LinkList L, Elemtype x)
{ Lnode *p, *q;  p=L;
while(p)
{ if(p->next && p->next->data==x)
{q=p->next;  p->next=q->next;  delete q; }
else  p=p->next;
}
}
注意:要删除所有的值为x的结点。
6、假设一个单循环链表L的数据域为整型,设计一个算法,求该表中所有结点的数据之和。
解:
存储结构如下:
typedef  struct  Lnode
{ElemType data;
struct Lnode *next;
}Lnode,  *LinkList;
假设L带头结点,且L指向头结点,则算法如下:
int sum_Of_Data(LinkList  L)
{ int s=0;  Lnode *p=L->next;
while(p!=L) {s+=p->data;  p=p->next; }
return s; }
假设L不带头结点,且L指向循环链表中任何一个结点,则算法如下:
int sum_of_data(LinkList  L)
{ int s=0;  Lnode *p=L;
if(L)
{ s+=p->data;  p=p->next;
while(p!=L) { s+=p->data; p=p->next; }
}
return s;
}
注:以上两种情形,只要给出其中一种情形的解即可。
7、假设二叉树用二叉链表存储,设计一个算法,求二叉树的结点个数。
解:存储结构如下:
 typedef struct bitnode
{ElemType  data;
struct bitnode *lchild,  *rchild;
}bitnode, *bitree;
算法如下:
int nodes(bitree T)
{ if(!T) return 0;
else  return (1+nodes(T->lchild)+nodes(T->rchild));
}
8、写一个算法,建立二叉树的二叉链表。
解:存储结构如下:
typedef char  ElemType;
 typedef struct bitnode
{ElemType  data;
struct bitnode *lchild,  *rchild;
}bitnode, *bitree;
算法如下:
void creat_bitree(bitree &T)
{ //按扩展的先序序列输入结点,输入‘#’表示空。
ElemType ch;  cin>>ch;
if(ch==’#’) T=0;
else
{ T=new bitnode;  T->data=ch;
creat_bitree(T->lchuild);
creat_bitree(T->rchild);
}
}
或者写成以下算法:
bitree  creat_bitree(void)
{ //按扩展的先序序列输入结点,输入‘#’表示空。
bitree  T;
ElemType ch;  cin>>ch;
if(ch==’#’) T=0;
else
{ T=new bitnode;  T->data=ch;
creat_bitree(T->lchuild);
creat_bitree(T->rchild);
}
return  T;
}
9、假设一棵二叉树的先序序列为EBADCFHGIKJ,中序序列为ABCDEFGHIJK,请画出该二叉树,并写出后序序列。
解:该二叉树如下:
后序序列为:ACDBGJKIHFE。
10、假设一棵二叉树的层次序列为ABCDEFGHIJ,中序序列为DBGEHJACIF,请画出该二叉树,并写出其先序序列和后序序列。
解:该二叉树如下:
先序序列为:ABDEGHJCFI;
后序序列为:DGJHEBIFCA。
11、编写一个递归算法,将用二叉链表表示的二叉树的所有结点的左、右子树交换。
解:存储结构如下:
typedef char  ElemType;
 typedef struct bitnode
{ElemType  data;
struct bitnode *lchild,  *rchild;
}bitnode, *bitree;

版权声明:本站内容均来自互联网,仅供演示用,请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198,我们将在24小时内删除。