数据结构试题大题编程及参考答案

1、精品文档 数据结构考试题参考答案 1、设顺序表 L 中的数据元素递增有序。试写一算法，将数据元素 x 插入到顺序表 L 的适当 位置，以保持该表的有序性。 解：存储结构为： typedef struct SeqList DataType *data; int MaxLen; int len; SeqList; 算法如下： void insertLx(SeqList int i=L.len-1; while(i=0 / 找 x 的前驱结点 p; if(!p- next) return; /若不存在结点x,则返回； q=new Lnode; q-data=y; q-next=p-next; p-n

2、ext=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-n

3、ext; 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(k0) return; Lnode *q, *p=L; int i=0; while(p / 找到第 k 个结点 p; if(!p) return; / 若不存在第 k 个结点，则返回； q=new

4、 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=q-ne

5、xt; 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不带

6、头结点，且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, *bitre

7、e; 算法如下： 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 cin ch; if(ch= #)T=0; else T=new

8、bit no de; 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 bit no de; T-data=ch; creat_bitree(T-lchuild); creat_bitree(T-rchild); return T; 9、假设一棵二叉树的先序序列为EBADCFHGIKJ中序序列为ABC

9、DEFGHIJK请画出该二叉树, 并写出后序序列。 解：该二叉树如下： ABCDEFGH，中序序列为DBGEHJAC，请画出该二叉树, 后序序列为：ACDBGJKIHFE 10、假设一棵二叉树的层次序列为 并写出其先序序列和后序序列。 解：该二叉树如下： 先序序列为：ABDEGHJCFI 后序序列为：DGJHEBIFCA 11、编写一个递归算法，将用二叉链表表示的二叉树的所有结点的左、右子树交换。 解：存储结构如下： typedef char ElemType; typedef struct bit node ElemType data; struct bit node *lchild, *r

10、child; bit no de, *bitree; 算法如下： void excha nge(bitree bitree temp; temp=T-lchild; T-lchild=T-rchild; T-rchild=temp; excha nge(T-lchild); excha nge(T-rchild); 12、试写出二叉链表表示的二叉树的先序遍历的非递归算法。 解：存储结构如下： typedef char ElemType; typedef struct bit node ElemType data; struct bit node *lchild, *rchild; bit no de, *bitree; 6欢迎下载 精品文档 算法如下： void preorder(bitree T) / 先序遍历，当前结点入栈。 #define MaxNum 20 bitree stackMaxNum; int top=0; / 指向栈顶的下一位置。 bitnode *p; p=T; while(p | top0) while(p) coutdata; stacktop+=p; p=