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

《数据结构试题大题编程及参考答案.pdf》由会员分享，可在线阅读，更多相关《数据结构试题大题编程及参考答案.pdf（6页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、数据结构考试题参考答案数据结构考试题参考答案1、设顺序表 L 中的数据元素递增有序;试写一算法,将数据元素 x 插入到顺序表 L 的适当位置,以保持该表的有序性;解：存储结构为：typedefstructSeqList DataTypedata;int MaxLen;intlen;SeqList;算法如下：void insertLxSeqList&L,DataType x if=return;int i=;whilei=0&xnext&p-next-data=xp=p-next;/找 x 的前驱结点 p;ifp-next return;/若不存在结点 x,则返回；q=new Lnode;q-d

2、ata=y;q-next=p-next;p-next=q;3、试写一个算法,统计带头指针的单链表L 的元素个数;解：存储结构如下：typedefstructLnodeElemType data;struct Lnode next;Lnode,LinkList;算法如下：int lengthLinkList L int len=0;Lnode p=L;whilep len+;p=p-next;returnlen;注：如果单链表是带头结点的,则算法如下：int lengthLinkList L int len=0;Lnode p=L-next;whilep len+;p=p-next;return

3、len;4、试写一个算法,在带头结点的单链表 L 的第 k 个结点后插入一个结点x;解：存储结构如下：typedefstructLnodeElemType data;struct Lnode next;Lnode,LinkList;算法如下：voidinsert_after_k LinkList L,intk,ElemTypex ifk0 return;Lnode q,p=L;int i=0;whilep&inext;/找到第 k 个结点 p;ifp return;/若不存在第 k 个结点,则返回；q=new Lnode;q-data=x;q-next=p-next;p-next=q;注：如果

4、是在 L 的第 k 个结点前插入一个结点,则找第 k-1 个结点 p,然后插入;、试写一个算法,在带头结点的单链表中删除所有的数据元素为x 的结点;解：存储结构如下：typedefstructLnodeElemType data;struct Lnode next;Lnode,LinkList;算法如下：voidDelete_all_xLinkList L,Elemtype x Lnode p,q;p=L;whilep ifp-next&p-next-data=xq=p-next;p-next=q-next;delete q;elsep=p-next;注意：要删除所有的值为x 的结点;、假设一

5、个单循环链表的数据域为整型,设计一个算法,求该表中所有结点的数据之和;解：存储结构如下：typedefstructLnodeElemType data;struct Lnode next;Lnode,LinkList;假设带头结点,且指向头结点,则算法如下：int sum_Of_DataLinkListL int s=0;Lnode p=L-next;whilep=L s+=p-data;p=p-next;return s;假设不带头结点,且指向循环链表中任何一个结点,则算法如下：int sum_of_dataLinkListL int s=0;Lnode p=L;ifL s+=p-data;

6、p=p-next;whilep=L s+=p-data;p=p-next;return s;注：以上两种情形,只要给出其中一种情形的解即可;、假设二叉树用二叉链表存储,设计一个算法,求二叉树的结点个数;解：存储结构如下：typedef struct bitnodeElemTypedata;struct bitnode lchild,rchild;bitnode,bitree;算法如下：int nodesbitree T ifT return 0;elsereturn 1+nodesT-lchild+nodesT-rchild;、写一个算法,建立二叉树的二叉链表;解：存储结构如下：typedef

7、 charElemType;typedef struct bitnodeElemTypedata;struct bitnode lchild,rchild;bitnode,bitree;算法如下：void creat_bitreebitree&T/按扩展的先序序列输入结点,输入表示空;ElemType ch;cinch;ifch=T=0;else T=new bitnode;T-data=ch;creat_bitreeT-lchuild;creat_bitreeT-rchild;或者写成以下算法：bitreecreat_bitreevoid/按扩展的先序序列输入结点,输入表示空;bitreeT

8、;ElemType ch;cinch;ifch=T=0;else T=new bitnode;T-data=ch;creat_bitreeT-lchuild;creat_bitreeT-rchild;returnT;9、假设一棵二叉树的先序序列为 EBADCFHGIKJ,中序序列为 ABCDEFGHIJK,请画出该二叉树,并写出后序序列;解：该二叉树如下：后序序列为：ACDBGJKIHFE;10、假设一棵二叉树的层次序列为 ABCDEFGHIJ,中序序列为 DBGEHJACIF,请画出该二叉树,并写出其先序序列和后序序列;解：该二叉树如下：先序序列为：ABDEGHJCFI；后序序列为：DGJH

9、EBIFCA;11、编写一个递归算法,将用二叉链表表示的二叉树的所有结点的左、右子树交换;解：存储结构如下：typedef charElemType;typedef struct bitnodeElemTypedata;struct bitnode lchild,rchild;bitnode,bitree;算法如下：void exchangebitree&TifT return;bitree temp;temp=T-lchild;T-lchild=T-rchild;T-rchild=temp;exchangeT-lchild;exchangeT-rchild;12、试写出二叉链表表示的二叉树的

10、先序遍历的非递归算法;解：存储结构如下：typedef charElemType;typedef struct bitnodeElemTypedata;struct bitnode lchild,rchild;bitnode,bitree;算法如下：void preorderbitree T/先序遍历,当前结点入栈;defineMaxNum 20bitree stackMaxNum;int top=0;/指向栈顶的下一位置;bitnodep;p=T;whilep|top0whilepcoutdata;stacktop+=p;p=p-lchild;iftop0 p=stack-top;p=p-rchild;coutendl;注：这里假设访问结点即为输出结点;若访问结点是其它操作,则换成相应的函数便可;