发布时间 : 星期一 文章数据结构习题集1更新完毕开始阅读
{struct node *sublist; char data; }dd;
struct node *link; }NODE;
NODE *creat_GL(char **s) {
NODE *h; char ch; ch=*(*s); (*s)++; if(ch!='\\0') {
h=(NODE*)malloc(sizeof(NODE)); if(ch=='(') {
h->tag=1;
h->dd.sublist=creat_GL(s); } Else {
h->tag=0;
h->dd.data=ch; } } else
h=NULL; ch=*(*s); (*s)++; if(h!=NULL) if(ch==',')
h->link =creat_GL(s); else
h->link=NULL; return(h); }
void prn_GL(NODE *p) {
if(p!=NULL) {
if(p->tag==1) {
printf(\
if(p->dd.sublist ==NULL) printf(\
7
else
prn_GL(p->dd.sublist ); } else
printf(\ if(p->tag==1) printf(\if(p->link!=NULL) {
printf(\
prn_GL(p->link); } } }
NODE *copy_GL(NODE *p) {
NODE *q;
if(p==NULL) return(NULL);
q=(NODE *)malloc(sizeof(NODE)); q->tag=p->tag; if(p->tag)
q->dd.sublist =copy_GL(p->dd.sublist ); else
q->dd.data =p->dd.data; q->link=copy_GL(p->link); return(q); }
NODE *head(NODE *p) /*求表头函数 */ {
return(p->dd.sublist); }
NODE *tail(NODE *p) /*求表尾函数 */ {
return(p->link); }
int sum(NODE *p) /*求原子结点的数据域之和函数 */ { int m,n;
if(p==NULL) return(0); else
{ if(p->tag==0) n=p->dd.data; else
n=sum(p->dd.sublist); if(p->link!=NULL) m=sum(p->link); else m=0;
8
return(n+m); } }
int depth(NODE *p) /*求表的深度函数 */ {
int h,maxdh; NODE *q;
if(p->tag==0) return(0); else
if(p->tag==1&&p->dd.sublist==NULL) return 1; else {
maxdh=0;
while(p!=NULL) {
if(p->tag==0) h=0; else
{q=p->dd.sublist; h=depth(q); }
if(h>maxdh)maxdh=h; p=p->link; }
return(maxdh+1); } }
main() {
NODE *hd,*hc; char s[100],*p; p=gets(s);
hd=creat_GL(&p); prn_GL(head(hd)); prn_GL(tail(hd)); hc=copy_GL(hd); printf(\prn_GL(hc);
printf(\printf(\}
第六章 树
一、选择题
1.在线索化二叉树中,t所指结点没有左子树的充要条件是（ ）。 A．t-〉left==NULL B．t-〉ltag==1 C．t-〉ltag=1且t-〉left=NULL D．以上都不对
9
2.二叉树按某种顺序线索化后,任一结点均有指向其前趋和后继的线索,这种说法（ ）。 A．正确 B．错误 C．不同情况下答案不确定
3.二叉树的前序遍历序列中,任意一个结点均处在其子女结点的前面,这种说法（ ）。 A．正确 B．错误 C．不同情况下答案不确定
4.由于二叉树中每个结点的度最大为2,所以二叉树是一种特殊的树,这种说法（ ）。 A．正确 B．错误 C．不同情况下答案不确定
5.设高度为h的二叉树上只有度为0和度为2的结点,则此类二叉树中所包含的结点数至少为（ ）。
A．2h B．2h-1 C．2h+1 D．h+1
6.已知某二叉树的后序遍历序列是dabec。中序遍历序列是debac,它的前序遍历序列是（ ）。 A．acbed B．decab C．deabc D．cedba 7.如果T2是由有序树T转换而来的二叉树,那么T中结点的前序就是T2中结点的（ ） A．前序 B．中序 C．后序 D．层次序
8.某二叉树的前序遍历结点访问顺序是abdgcefh,中序遍历的结点访问顺序是dgbaechf,则其后序遍历的结点访问顺序是（ ）。
A．bdgcefha B．gdbecfha C．bdgaechf D．gdbehfca 9.二叉树为二叉排序树的充分必要条件是其任一结点的值均大于其左孩子的值、小于其右孩子的值。这种说法（ ）。
A．正确 B．错误 C．不同情况下答案不确定 10.按照二叉树的定义,具有3个结点的二叉树有（ ）种。 A．3 B．4 C．5 D．6 11.在一非空二叉树的中序遍历序列中,根结点的右边（ ）。 A．只有右子树上的所有结点 B．只有右子树上的部分结点 C．只有左子树上的部分结点 D．只有左子树上的所有结点 12.树最适合用来表示（ ）。 A．有序数据元素 B．无序数据元素 C．元素之间具有分支层次关系的数据 D．元素之间无联系的数据 13.任何一棵二叉树的叶结点在先序、中序和后序遍历序列中的相对次序（ ）。 A．不发生改变 B．发生改变 C．不能确定 D．以上都不对 14.实现任意二叉树的后序遍历的非递归算法而不使用栈结构,最佳方案是二叉树采用（ ）存储结构。
A．二叉链表 B．广义表存储结构 C．三叉链表 D．顺序存储结构 15.对一个满二叉树,m个树叶,n个结点,深度为h,则（ ）。 A．n=h+m B．h+m=2n C．m=h-1 D．n=2h-1 16.如果某二叉树的前序为stuwv,中序为uwtvs,那么该二叉树的后序为（ ）。 A．uwvts B．vwuts C．wuvts D．wutsv 17.具有五层结点的二叉平衡树至少有（ ）个结点。 A．10 B．12 C．15 D．17 二、判断题
1.二叉树中任何一个结点的度都是2。（ ）
2.由二叉树结点的先根序列和后根序列可以唯一地确定一棵二叉树。（ ） 3.一棵哈夫曼树中不存在度为1的结点。（ ）
4.平衡二叉排序树上任何一个结点的左、右子树的高度之差的绝对值不大于2（ ） 三、填空题
1.指出树和二叉树的三个主要差别________,________,________。
10