数据结构试题大题编程及参考答案(6页).doc
-数据结构试题大题编程及参考答案-第 6 页数据结构考试题参考答案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.datai) L.datai+1=L.datai; i=i-1;L.datai+1=x; L.len+;2、试写一个算法，在带头结点的单链表L的元素x前插入一个结点y。解：存储结构如下：typedef struct LnodeElemType 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 LnodeElemType 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 LnodeElemType 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，然后插入。、试写一个算法，在带头结点的单链表中删除所有的数据元素为x的结点。解：存储结构如下：typedef struct LnodeElemType 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的结点。、假设一个单循环链表的数据域为整型，设计一个算法，求该表中所有结点的数据之和。解：存储结构如下：typedef struct LnodeElemType data; struct Lnode *next;Lnode, *LinkList;假设带头结点，且指向头结点，则算法如下：int sum_Of_Data(LinkList L) int s=0; Lnode *p=L->next;while(p!=L) s+=p->data; p=p->next; return s; 假设不带头结点，且指向循环链表中任何一个结点，则算法如下：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;注：以上两种情形，只要给出其中一种情形的解即可。、假设二叉树用二叉链表存储，设计一个算法，求二叉树的结点个数。解：存储结构如下：typedef struct bitnodeElemType data; struct bitnode *lchild, *rchild;bitnode, *bitree;算法如下：int nodes(bitree T) if(!T) return 0; else return (1+nodes(T->lchild)+nodes(T->rchild);、写一个算法，建立二叉树的二叉链表。解：存储结构如下：typedef char ElemType;typedef struct bitnodeElemType 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 bitnodeElemType data; struct bitnode *lchild, *rchild;bitnode, *bitree;算法如下：void exchange(bitree &T)if(!T) return; bitree temp;temp=T->lchild;T->lchild=T->rchild;T->rchild=temp;exchange(T->lchild);exchange(T->rchild);12、试写出二叉链表表示的二叉树的先序遍历的非递归算法。解：存储结构如下：typedef char ElemType;typedef struct bitnodeElemType data; struct bitnode *lchild, *rchild;bitnode, *bitree;算法如下：void preorder(bitree T) /先序遍历，当前结点入栈。#define MaxNum 20bitree stackMaxNum;int top=0; /指向栈顶的下一位置。bitnode *p;p=T;while(p | top>0)while(p) cout<<p->data; stacktop+=p; p=p->lchild; if(top>0) p=stack-top; p=p->rchild; cout<<endl;注：这里假设访问结点即为输出结点。若访问结点是其它操作，则换成相应的函数便可。
