数据结构考试题参考答案
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小时内删除。
发表评论