3、假设以I和O分别表示入栈和出栈操作。栈的初态和终态均为空,入栈和出栈的操作序列可表示为仅由I和O组成的序列,称可以操作的序列为合法序列,否则称为非法序列。(15分)
(1)A和D是合法序列,B和C 是非法序列。
(2)设被判定的操作序列已存入一维数组A中。
int Judge(char A[])
//判断字符数组A中的输入输出序列是否是合法序列。如是,返回true,否则返
回false。
{i=0; //i为下标。
j=k=0; //j和k分别为I和字母O的的个数。
while(A[i]!=‘\0’) //当未到字符数组尾就作。
{switch(A[i])
{case‘I’: j++; break; //入栈次数增1。
case‘O’: k++; if(k>j){printf(“序列非法\n”);exit(0);} }
i++; //不论A[i]是‘I’或‘O’,指针i均后移。}
if(j!=k) {printf(“序列非法\n”);return(false);}
else {printf(“序列合法\n”);return(true);}
}//算法结束。
4、要求二叉树按二叉链表形式存储。15分
(1)写一个建立二叉树的算法。(2)写一个判别给定的二叉树是否是完全二叉树的算法。
BiTree Creat() //建立二叉树的二叉链表形式的存储结构
{ElemType x;BiTree bt;
scanf(“%d”,&x); //本题假定结点数据域为整型
if(x==0) bt=null;
else if(x>0)
{bt=(BiNode *)malloc(sizeof(BiNode));
bt->data=x; bt->lchild=creat(); bt->rchild=creat();
}
else error(“输入错误”);
return(bt);
}//结束 BiTree
int JudgeComplete(BiTree bt) //判断二叉树是否是完全二叉树,如是,返回1,否则,返回0
{int tag=0; BiTree p=bt, Q[]; // Q是队列,元素是二叉树结点指针,容量
足够大
if(p==null) return (1);
QueueInit(Q); QueueIn(Q,p); //初始化队列,根结点指针入队
while (!QueueEmpty(Q))
{p=QueueOut(Q); //出队
if (p->lchild && !tag) QueueIn(Q,p->lchild); //左子女入队
else {if (p->lchild) return 0; //前边已有结点为空,
本结点不空
数据结构复习题及答案(12级)_IT认证_资格考试/认证_教育专区。大学课程一、选择题。(每小题 2 分,共 40 分) (1) 计算机识别.存储和加工处理的对象被统称...
数据结构试题库及答案 第一章 概论一、选择题 1、研究数据结构就是研究( D )。 A. 数据的逻辑结构 B. 数据的存储结构 C. 数据的逻辑结构和存储结构 D. ...
数据结构试题及答案_理学_高等教育_教育专区。有用好风光好感动 1、线性表的逻辑顺序与物理顺序总是一致的。( ) ) 2、线性表的顺序存储表示优于链式存储表示。...
23490数据结构习题答案_计算机软件及应用_IT/计算机_专业资料。第2章 线性表 2.算法设计题 (1)将两个递增的有序链表合并为一个递增的有序链表。要求结果链表...
数据结构试题及答案_工学_高等教育_教育专区。《数据结构》试卷及答案 数据结构》 1.算法分析的目的是( C A.找出数据结构的合理性 C.分析算法的效率以求改进 ...
数据结构试题及答案_计算机硬件及网络_IT/计算机_专业资料。复习数据结构必备品。数据结构试卷(一)... 1 数据结构试卷(二)... 5 数据结构试卷(三)... 8 ...
习题1 判断题(下列各题,正确的请在前面的括号内打√;错误的打ㄨ)()(1)数据元素是数据的最小单位。 ()(2)程序和算法原则上没有区别,在讨论数据结构时可以...
数据结构复习题答案 2_理学_高等教育_教育专区。数据结构期末考试题一、填空。 1.顺序存储结构的特点是( 静态存储的物理次序和逻辑次序一致 ) ,链式存储结构的...
中南大学现代远程教育课程考试(专科) 中南大学现代远程教育课程考试(专科)复习题及参考答案数据结构一、判断题: 判断题: 1. 数组是一种复杂的数据结构,数组元素...
数据结构习题集答案(C语言版严蔚敏)_理学_高等教育_教育专区。数据结构习题集答案(C语言版严蔚敏)第1章 绪论 1.1 简述下列术语:数据,数据元素、数据对象、...
热门文档