数据结构与算法分析c版答案

A. 数据结构与算法题需要回答

《数据结构与算法》模拟题
一、填空题：（共15分）（每空一分）
按照排序时，存放数据的设备，排序可分为<1> 排序和<2> 排序。内部排序和外部排序
图的常用的两种存储结构是<3> 和<4> 。邻接矩阵和邻接表
数据结构中的三种基本的结构形式是<5> 线性结构 和<6> 树型结构 、图型结构<7> 。
一个高度为6的二元树，最多有<8> 63 个结点。
线性查找的时间复杂度为：<9> O(n^2) ，折半查找的时间复杂度为：<10> O(nlogn) 、堆分类的时间复杂度为：<11> O(nlogn) 。
在采用散列法进行查找时，为了减少冲突的机会，散列函数必须具有较好的随机性，在我们介绍的几种散列函数构造法中，随机性最好的是<12> 随机数 法、最简单的构造方法是除留余数法<13> 。
线性表的三种存储结构是：数组、<14> 链表 、<15> 静态链表 。
二、回答下列问题：（共30分）
现有如右图的树，回答如下问题：看不见图
根结点有：
叶结点有：
具有最大度的结点：
结点的祖先是：
结点的后代是：
栈存放在数组A[m]中，栈底位置是m-1。试问：
栈空的条件是什么？top=m-1
栈满的条件是什么？top=-1
数据结构和抽象数据型的区别与联系：
数据结构（data structure)—是相互之间存在一种或多种特定关系的数据元素的集合。数据元素相互之间的关系称为结构。
抽象数据类型（ADT）：是指一个数学模型（数据结构）以及定义在该模型（数据结构）上的一组操作。

B. 数据结构（c语言版）题目求答案

3.28
void InitCiQueue(CiQueue&Q)//初始化循环链表表示的队列Q
{
Q=(CiLNode*)malloc(sizeof(CiLNode));
Q->next=Q;
}//InitCiQueue
voidEnCiQueue(CiQueue&Q,int x)//把元素x插入循环列表表示的队列Q,Q指向队尾元素，Q->next指向头结点，Q->next->next指向队尾元素
{
p=(CiLNode*)malloc(sizeof(CiLNode));
p->data=x;
p->next=Q->next;//直接把p加在Q的后面
Q->next=p;
Q=p;//修改尾指针
}
Status DeCiQueue(CiQueue&Q,int x)//从循环链表表示的队列Q头部删除元素x
{
if(Q==Q->next)return INFEASIBLE;//队列已空
p=Q->next->next;
x=p->data;
Q->next->next=p->next;
free(p);
rturn OK;
}//DeCiqueue

3.31

int Palindrome_Test()
{
InitStack(S);InitQueue(Q);
while((c=getchar())!='@')
{
Push(S,c);EnQueue(Q,c);
}
while(!StackEmpty(S))
{
pop(S,a);DeQueue(Q,b);
if(a!=b)return ERROR;
}
return OK;
}

C. 数据结构与算法分析 C++

你说的是中序线索二叉树的插入和删除

#include<stdio.h>
#include"malloc.h"
#include"windows.h"
#definemaxsize20//规定树中结点的最大数目
typedefstructnode{//定义数据结构
intltag,rtag;//表示child域指示该结点是否孩子
chardata;//记录结点的数据
structnode*lchild,*rchild;//记录左右孩子的指针
}Bithptr;

Bithptr*Q[maxsize];//建队，保存已输入的结点的地址
Bithptr*CreatTree(){//建树函数，返回根指针
charch;
intfront,rear;
Bithptr*T,*s;
T=NULL;
front=1;rear=0;//置空二叉树
printf("建立一棵二叉树，请输入结点信息：
");
printf("请输入新的结点信息，@为空结点，#为结束标志：");
ch=getchar()();//输入第一个字符
while(ch!='#')//判断是否为结束字符
{
s=NULL;
if(ch!='@')//判断是否为虚结点
{
s=(Bithptr*)malloc(sizeof(Bithptr));
s->data=ch;
s->lchild=NULL;
s->rchild=NULL;
s->rtag=0;
s->ltag=0;
}
rear++;
Q[rear]=s;//将结点地址加入队列中
if(rear==1)T=s;//输入为第一个结点为根结点
else
{
if(s!=NULL&&Q[front]!=NULL)//孩子和双亲结点均不是虚结点
if(rear%2==0)
Q[front]->lchild=s;
elseQ[front]->rchild=s;
if(rear%2==1)front++;
}getchar()();
printf("请输入新的结点信息，@为空结点，#为结束标志：");
ch=getchar()();
}
returnT;
}
voidInorder(Bithptr*T)//中序遍历
{
if(T)
{
if(T->ltag!=1)Inorder(T->lchild);
printf("→%c",T->data);
if(T->rtag!=1)Inorder(T->rchild);
}
}

Bithptr*pre=NULL;
voidPreThread(Bithptr*root)//中序线索化算法，函数实现
{
Bithptr*p;
p=root;
if(p){
PreThread(p->lchild);//线索化左子树
if(pre&&pre->rtag==1)pre->rchild=p;//前驱结点后继线索化
if(p->lchild==NULL)
{
p->ltag=1;
p->lchild=pre;
}
if(p->rchild==NULL)//后继结点前驱线索化
p->rtag=1;
pre=p;
PreThread(p->rchild);
}
}
voidPrintIndex(Bithptr*t)//输出线索
{
Bithptr*f;
f=t;
if(f)
{
if(f->ltag==1&&f->lchild==NULL&&f->rtag==1)printf("【%c】",f->data);//如果是第一个结点
if(f->ltag==1&&f->lchild!=NULL)printf("%c→【%c】",f->lchild->data,f->data);//如果此结点有前驱就输出前驱和此结点
if(f->ltag==1&&f->rtag==1&&f->rchild!=NULL)printf("→%c",f->rchild->data);//如果此结点有前驱也有后继，就输出后继
elseif(f->rtag==1&&f->rchild!=NULL)printf("【%c】→%c",f->data,f->rchild->data);//如果没有前驱，就输出此结点和后继
printf("
");
if(f->ltag!=1)PrintIndex(f->lchild);
if(f->rtag!=1)PrintIndex(f->rchild);
}
}
Bithptr*SearchChild(Bithptr*point,charfindnode)//查找孩子结点函数
{
Bithptr*point1,*point2;
if(point!=NULL)
{
if(point->data==findnode)returnpoint;
else
if(point->ltag!=1){point1=SearchChild(point->lchild,findnode);if(point1!=NULL)returnpoint1;}
if(point->rtag!=1){point2=SearchChild(point->rchild,findnode);if(point2!=NULL)returnpoint2;}
returnNULL;
}
else
returnNULL;
}
Bithptr*SearchPre(Bithptr*point,Bithptr*child)//查找父亲结点函数
{
Bithptr*point1,*point2;
if(point!=NULL)
{
if((point->ltag!=1&&point->lchild==child)||(point->rtag!=1&&point->rchild==child))returnpoint;//找到则返回
else
if(point->ltag!=1)
{
point1=SearchPre(point->lchild,child);
if(point1!=NULL)
returnpoint1;
}
if(point->rtag!=1)
{
point2=SearchPre(point->rchild,child);
if(point2!=NULL)
returnpoint2;
}
returnNULL;
}
else
returnNULL;
}
voidInsert(Bithptr*root)
{
charch;
charc;
Bithptr*p1,*child,*p2;
printf("请输入要插入的结点的信息:");
scanf("%c",&c);
scanf("%c",&c);
p1=(Bithptr*)malloc(sizeof(Bithptr));//插入的结点信息
p1->data=c;
p1->lchild=NULL;
p1->rchild=NULL;
p1->rtag=0;
p1->ltag=0;
printf("输入查找的结点信息:");
scanf("%c",&ch);
scanf("%c",&ch);
child=SearchChild(root,ch);//查孩子结点的地址
if(child==NULL){
printf("没有找到结点
");
system("pause");
return;
}
elseprintf("发现结点%c
",child->data);
if(child->ltag==0)//当孩子结点有左孩子的时候
{
p2=child;
child=child->lchild;
while(child->rchild&&child->rtag==0)//找到左子树下，最右结点
child=child->rchild;
printf("发现结点%c
",child->data);
p1->rchild=child->rchild;//后继化
p1->rtag=1;
child->rtag=0;
child->rchild=p1;//连接
p1->lchild=child;//前驱化
p1->ltag=1;
}
else//当孩子结点没有左孩子的时候
{
p1->lchild=child->lchild;//前驱化
child->ltag=0;
p1->ltag=1;
child->lchild=p1;
p1->rchild=child;
p1->rtag=1;
}
printf("	插入结点操作已经完成，并同时完成了线索化的恢复
");
}