广东工业大学数据结构二叉树课程设计
数据结构实验报告题目：二叉树抽象数据类型
学院计算机学院
专业计算机科学与技术
年级班别
学号
学生姓名
指导教师
成绩____________________
2013年6月
一．实验概要
实验项目名称: 二叉树抽象数据类型的实现
实验项目性质: 设计性实验
所属课程名称: 数据结构
实验计划学时: 6
二.实验目的
1.了解二叉树的定义以及各项基本操作。
2.实现二叉树存储、遍历及其他基本功能
三. 实验仪器设备和材料
硬件：PC机
软件：Visual C++ 6.0
四．实验的内容
1.二叉树类型定义以及各基本操作的简要描述；
ADT BinaryTree {
数据对象D:D是具有相同特性的数据元素的集合.
数据关系R:
若D=?，则R=,称BinaryTree为空二叉树；
若D≠，则R={H}，H是如下二元关系：
(1)在D中存在惟一的称为根的数据元素root，它在关系H下无前
驱；
(2)若D-{root}≠?，则存在D-{root}={D1,Dr}，且D1∩Dr=?；
(3)若D1≠?，则D1中存在惟一的元素x1，
在Dr上的关系Hr∈H；H={
(4)（D1，{H1}）是一棵符合本定义的二叉树，称为根的左子树，
是一棵符合本定义的二叉树，称为根的右子树。
基本操作P:
InitBiTree(&T);
操作结果：构造空二叉树T。
DestroyBiTree(&T);
初始条件：二叉树T存在。
操作结果：销毁二叉树T。
CreateBiTree(&T,definition);
初始条件：definition给出二叉树T的定义。
操作结果：按definition构造二叉树T。
ClearBiTree(&T);
初始条件：二叉树T存在。
操作结果：将二叉树T清为空树。
BiTreeEmpty(T);
初始条件：二叉树T存在。
操作结果：若T为空二叉树，则返回TURE,否则FALSE。BiTreeDepth(T);
初始条件：二叉树T存在。
操作结果：返回T的深度。
Root(T);
初始条件：二叉树T存在。
操作结果：返回T的根。
Value(T,e);
初始条件：二叉树T存在，e是T中的某个结点。
操作结果：返回e的值。
Assign(T,&e,value);
初始条件：二叉树T存在，e是T中的某个结点。
操作结果：结点e赋值为value。
Parent(T,e);
初始条件：二叉树T存在，e是T中的某个结点。
操作结果：若e是T的非跟结点，则返回它的双亲，否则返回“空”。
LeftChild(T,e);
初始条件：二叉树T存在，e是T中的某个结点。
操作结果：返回e的左孩子。若e无左孩子，则返回“空”。
RightChild(T,e);
初始条件：二叉树T存在，e是T中的某个结点。
操作结果：返回e的右孩子。若e无右孩子，则返回“空”。
LeftSibling(T,e);
初始条件：二叉树T存在，e是T中的某个结点。
操作结果：返回e的左兄弟。若e无左孩子或无左兄弟，则返回“空”。
RightSibling(T,e);
初始条件：二叉树T存在，e是T中的某个结点。
操作结果：返回e的右兄弟。若e无右孩子或无右兄弟，则返回“空”。}ADT BinaryTree
2.存储结构：采用无头结点的链式存储结构实现
3.源代码：
头文件及存储结构:
#include
#include
#define TURE 1
#define FALSE 0
#define OK 1
#define ERROR 0
#define OVERFLOW 0
#define MAXQSIZE 100 //最大队列长度
typedef char TElemType;
typedef struct BiTNode //二叉树结构体
{
TElemType data;
struct BiTNode *lchild,*rchild;
}BiTNode,*BiTree;
typedef BiTree QElemType;
typedef struct QNode
{
QElemType data;
struct QNode *next;
}QNode, *QueuePtr; //结点结构体
typedef struct
{
QueuePtr front;
QueuePtr rear;
}LinkQueue; //链队列结构体
算法设计：
int InitQueue(LinkQueue &Q) //构造空队列
{
Q.front = Q.rear = (QueuePtr)malloc(sizeof(QNode));
if(!Q.front) //存储分配失败
exit(OVERFLOW);
Q.front->next = NULL;
return OK;
}
int EnQueue(LinkQueue &Q, QElemType e) //新元素入队尾
{
QueuePtr p;
p = (QueuePtr)malloc(sizeof(QNode));
if(!p) //存储分配失败
exit (OVERFLOW);
p->data = e;
p->next = NULL;
Q.rear->next = p;
Q.rear = p;
return OK;
}
int DeQueue(LinkQueue &Q, QElemType &e) //删除队头元素
{
QueuePtr p;
if(Q.front == Q.rear) //队列为空队
return ERROR;
p = Q.front->next;
e = p->data;
Q.front->next = p->next;
if(Q.rear == p) //判断删除队头元素后，队列是否为空队Q.rear = Q.front;
free(p);
return OK;
}
int QueueEmpty(LinkQueue Q) //判断队列是否为空队
{
if (Q.front == Q.rear)
return TURE;
else
return FALSE;
}
int InitBiTree(BiTree &T) // 构造空二叉树
{
T = NULL;
return OK;
}
int DestroyTree(BiTree &T) //销毁二叉树
{
if(!T)
return ERROR;
else
DestroyTree(T->lchild);
DestroyTree(T->rchild);
free(T);
T=NULL;
return OK;
}
void CreateBiTree(BiTree &T) //用先序遍历的方式构建二叉树,以…@?表示空结点。
{
TElemType ch;
scanf("%c",&ch);
if(ch=='@')
T=NULL;
else
{
if(!(T=(BiTree)malloc(sizeof(BiTNode))))
exit(OVERFLOW); //分配存储空间失败
T->data=ch;
CreateBiTree(T->lchild); //构造左子树
CreateBiTree(T->rchild); //构造右子树
}
}
int ClearBiTree(BiTree &T) //清空二叉树函数
{
if(!T)
return ERROR;
else
{
ClearBiTree(T->lchild);
ClearBiTree(T->rchild);
free(T);
T=NULL;
return OK;
}
}
int BiTreeEmpty(BiTree T) //判断二叉树是否为空
{
if(!T)
return TURE;
else
return FALSE;
}
int BiTreeDepth(BiTree T) //计算二叉树深度
{
int lcd,rcd;
if(!T)
return 0;
lcd=BiTreeDepth(T->lchild);
rcd=BiTreeDepth(T->rchild);
return ((lcd>rcd?lcd:rcd)+1);
}
TElemType Root(BiTree T) //判断二叉树是否空，若非空返回其根
{
if(BiTreeEmpty(T))
return NULL;
else
return (T->data);
}
TElemType Value(BiTree T,BiTree e) //返回e结点的值
{
return e->data;
}
int Assign(BiTree T,BiTree &e,TElemType value) // 将value 的值给结点e
{
e->data=value;
return OK;
}
TElemType Parent(BiTree T,TElemType e)
{//返回双亲
LinkQueue q;
QElemType a;
if(T)
{
InitQueue(q);
EnQueue(q,T);//树根入队列
while(!QueueEmpty(q))//队不空
{
DeQueue (q, a);//出队，队列元素赋给a
if(a->lchild&&a->lchild->data==e||a->rchild&&a->rchild ->data==e) //找到e
return a->data; //返回双亲的值
else
{
if(a->lchild)
EnQueue(q,a->lchild);//入队列左孩子
if(a->rchild)
EnQueue(q,a->rchild);//入队列右孩子
}
}
}
return NULL;
}
BiTree Point(BiTree T,TElemType s)//返回二叉树T中指向元素值为S的结点指针
{
LinkQueue q;
QElemType a;
if(T)
{
InitQueue(q);
EnQueue(q,T);
while(!QueueEmpty(q))
{
DeQueue(q,a);
if(a->data==s)
{
return a;
}
if(a->lchild)
{
EnQueue(q,a->lchild);
}
if(a->rchild)
{
EnQueue(q,a->rchild);
}
}
}
return NULL;
}
TElemType LeftChild(BiTree T,TElemType e)
{//返回e的左孩子
BiTree a;
if(T)
{
a=Point(T,e);//a是指向结点e的指针
if(a&&a->lchild)
return a->lchild->data;
}
return NULL;
}
TElemType RightChild(BiTree T,TElemType e) //返回e的右孩子
{
BiTree a;
if(T)
{
if((a=Point(T,e))&&a->rchild)
return a->rchild->data;
}
return NULL;
}
TElemType LeftSibling(BiTree T,TElemType e)
{ //返回左兄弟
TElemType a;
BiTree p;
if(T)
{
a=Parent(T,e);//a为e的双亲
if(a!=NULL)
{
p=Point(T,a);//p指向结点a的指针
if(p->lchild&&p->rchild&&p->rchild->data==e)//p存在左右孩子而且右孩子是e
return p->lchild->data;
}
}
return NULL;
}
TElemType RightSibling(BiTree T,TElemType e)
{ //返回右兄弟
TElemType a;
BiTree p;
if(T)
{
a=Parent(T,e);//a为e的双亲
if(a!=NULL)
{
p=Point(T,a);//p指向结点a的指针
if(p->lchild&&p->rchild&&p->lchild->data==e)//p存在左右孩子而且左孩子是e
return p->rchild->data;
}
}
return NULL;
}
int InsertChild(BiTree T,BiTree p,int LR,BiTree c) //根据LR为0或者1，插入C为T中P所指结点的左或者右子树，
//P所指的结点原有左或右子树则成为C的右子树
{
if(p)
{
if(LR==0) //把二叉树C插入p所指结点的左子树
{
c->rchild=p->lchild;
p->lchild=c;
}
else
{
c->rchild=p->rchild;
p->rchild=c;
}
return OK;
}
return ERROR;
}
int DeleteChild(BiTree T,BiTree p,int LR)
{
if(p)
{
if(LR==0)
{
ClearBiTree(p->lchild);
}
else
{
ClearBiTree(p->rchild);
}
return OK;
}
return ERROR;
}
void visit(TElemType e) //二叉树结点访问函数
{
printf("%c",e);
}
int PreOrderTraverse(BiTree T,void(*visit)(TElemType)) //先序遍历二叉树
{
if(T)
{
visit(T->data);
PreOrderTraverse(T->lchild,visit);
PreOrderTraverse(T->rchild,visit);
return OK;
}
return ERROR;
}
int InOrderTraverse(BiTree T,void(*visit)(TElemType))
{ //中序遍历二叉树
if(T)
{
InOrderTraverse(T->lchild,visit);
visit(T->data);
InOrderTraverse(T->rchild,visit);
return OK;
}
return ERROR;
}
int PostOrderTraverse(BiTree T,void(*visit)(TElemType)) { //后序遍历二叉树
if(T)
{
PostOrderTraverse(T->lchild,visit);
PostOrderTraverse(T->rchild,visit);
visit(T->data);
return OK;
}
return ERROR;
}
int LevelOrderTraverse(BiTree T,void(*visit)(TElemType)) {//层序遍历二叉树
LinkQueue q;
QElemType a;
if(T)
{
InitQueue(q);//初始化队列
EnQueue(q,T);//根指针入队
while(!QueueEmpty(q))
{
DeQueue(q,a);//出队元素，赋给a
visit(a->data);//访问a所指结点
if(a->lchild!=NULL)
EnQueue(q,a->lchild);
if(a->rchild!=NULL)
EnQueue(q,a->rchild);
}
return OK;
}
return ERROR;
}
主函数：
int main()
{
int i,j,LR;
TElemType value,a,temp;
BiTree p,C;
printf("欢迎使用本二叉树程序，请按回车键继续...\n");
getchar();
printf("正在构造空二叉树，请稍候...");
printf("\n");
BiTree T;
InitBiTree(T);
if(BiTreeEmpty(T))
printf("构造空二叉树成功！\n");
else
printf("构造空二叉树失败！\n");
printf("请按先序遍历顺序输入二叉树各结点的值！空结点用@表示！
\n");
CreateBiTree(T);
printf("\n");
getchar();
printf("请选择接下来的操作:输入“1”为查看二叉树深度，输入“2”为查看二叉树根节点...\n");
scanf("%d",&i);
if(i==1)
printf("此二叉树的深度为：%d\n\n",BiTreeDepth(T));
if(i==2)
printf("此二叉树的根节点为：%c\n\n",Root(T));
printf("请选择遍历该二叉树的顺序：输入“1”为先序遍历，输入“2”为中序遍历，输入“3”为后序遍历，输入“4”为层序遍历...\n");
scanf("%d",&i);
getchar();
printf("\n");
if(i==1)
{
j=PreOrderTraverse(T,visit);
printf("\n");
if(j==0)
printf("该二叉树为空树，请重新运行程序！\n");
}
if(i==2)
{
j=InOrderTraverse(T,visit);
printf("\n");
if(j==0)
printf("该二叉树为空树，请重新运行程序！\n");
}
if(i==3)
{
j=PostOrderTraverse(T,visit);
printf("\n");
if(j==0)
printf("该二叉树为空树，请重新运行程序！\n");
}
if(i==4)
{
j=LevelOrderTraverse(T,visit);
printf("\n");
if(j==0)
printf("该二叉树为空树，请重新运行程序！\n"); }
printf("\n请输入需要替换的结点：\n");
scanf("%c",&a);
getchar();
p=Point(T,a);
printf("请输入需要代入的结点值：\n");
scanf("%c",&value);
getchar();
Assign(T,p,value);
printf("赋值之后该结点的值为：%c\n\n",p->data);
printf("请输入“1”求该结点的双亲结点，输入“2”求该结点的左孩子，输入“3”求该结点的右孩子，输入“4”求该结点的左兄弟，输入“5”求该结点的右兄弟..\n\n");
scanf("%d",&i);
getchar();
switch(i)
{
case 1:
{
if(Parent(T,value)==NULL)
printf("该结点没有双亲结点。\n");
else
printf("该结点的双亲结点为：%c\n\n",Parent(T,value));break;
}
case 2:
{
if(LeftChild(T,value)==NULL)
printf("该结点没有左孩子结点。\n");
else
printf("该结点的左孩子结点为：%c\n\n",LeftChild(T,value));break;
}
case 3:
{
if(RightChild(T,value)==NULL)
printf("该结点没有右孩子结点。\n");
else
printf("该结点的右孩子结点
为：%c\n\n",RightChild(T,value));break;
}
case 4:
{
if(LeftSibling(T,value)==NULL)
printf("该结点没有左兄弟。\n");
else
printf("该结点的左兄弟为：%c\n\n",LeftSibling(T,value));
break;
}
case 5:
{
if(RightSibling(T,value)==NULL)
printf("该结点没有右兄弟。\n");
else
printf("该结点的右兄弟为：%c\n\n",RightSibling(T,value));
break;
}
}
printf("\n现在进行结点插入子树，请按照先序遍历的顺序输入二叉树C，注意该二叉树没有右子树！\n");
InitBiTree(C);
CreateBiTree(C);
getchar();
printf("\n请输入您需要插入子树的结点：\n");
scanf("%c",&a);
getchar();
p=Point(T,a);
printf("\n输入0示插入C为%c结点的左子树而该结点原来的左子树变为c的右子树...",a);
printf("\n输入1示插入C为%c结点的右子树而该结点原来的左子树变为c的右子树,请选择...\n",a);
scanf("%d", &LR);
getchar();
j= InsertChild(T, p, LR, C);
if(j==0)
{
printf("插入失败！\n");
}
else
{
printf("插入成功！该新二叉树的先序遍历为：");
PreOrderTraverse(T, visit);
}
printf("\n\n进行删除操作，请输入需要删除左子树或者右子树的结点：
");
scanf("%c",&a);
getchar();
p=Point(T,a);
printf("\n输入 0 表示删除%c结点的左子树， 1 表示删除%c结点的右子树，请选择...\n",a);
scanf("%d", &LR);
getchar();
j = DeleteChild(T, p, LR);
if(j==0)
{
printf("删除失败！\n");
}
else
{
printf("删除成功！该新二叉树的先序遍历为：");
PreOrderTraverse(T, visit);
}
DestroyTree(T);
if (!T)
printf("\n树已被成功销毁！程序执行完毕，请按回车键\n");
else
printf("\n树销毁不成功！程序执行完毕，请按回车键\n");
getchar();
for(i=1;i<=4;++i)
printf("\n");
printf("
*********************************************************
******************\n");
printf("
*********************************************************
******************\n");
printf("
*********************************************************
******************\n");
printf("
*********************************************************
******************\n");
printf("
*********************************************************
******************\n");
printf("
*********************************************************
******************\n");
printf("
*********************************************************
******************\n");
printf("
*********************************************************
******************\n");
printf(" ****************************** 感谢使用
*****************************\n");
printf(" ****************************** * *
*****************************\n");
printf(" ****************************** 计科四班
*****************************\n");
printf(" ****************************** *****************************\n");
printf(" ******************************制作人：罗志权
数据结构课程设计参考题目
数据结构课程设计题目 数据结构课程设计题目(大题目).doc 一、公司销售管理系统 项目开发基本要求 1．客户信息管理：对客户的基本信息进行添加、修改和删除。 2．产品信息管理：对产品的基本信息进行添加、修改和删除。 3．供应商信息管理：对供应商的基本信息进行添加、修改和删除。 4．订单信息管理：对订单的基本信息进行添加、修改和删除。 二、高校科研管理系统 系统主要用于帮助高校或科研单位管理和维护各项科研相关资料 项目开发基本要求 1．系统用户管理模块：为系统新用户设置用户名及口令；操作员更改自己的系统口令。2．数据字典管理模块：管理项目性质包括：分为国家自然科学基金、863、部省科委及企业集团四种情况；范围包括：分为全国、国际、地方三种情况；检索源包括：分为EI、SCI、核心和一般四种情况。 3．项目参加人员管理模块包括：显示添加修改删除查询。 4．项目基本情况模块包括：显示添加修改删除查询。 5．项目获奖情况模块包括：显示添加修改删除查询。 6．期刊论文管理模块包括：显示添加修改删除查询。 7．著作管理模块包括：显示添加修改删除查询。 8．科研工作量统计模块：按照学校科研工作量计算办法，为每位科研人员进行科研工作量的计算和统计。 9．科研积分统计模块：按照学校科研积分计算办法，为每位科研人员进行科研计分的计算和统计。 三、网络五子棋对战 四、不同排序算法模拟 五、科学计算器 数据结构课程设计题目 1.运动会分数统计 任务：参加运动会有n个学校，学校编号为1……n。比赛分成m个男子项目，和w个女子项目。项目编号为男子1……m，女子m+1……m+w。不同的项目取前五名或前三名积分；取前五名的积分分别为：7、5、3、2、1，前三名的积分分别为：5、3、2；哪些取前五名或前三名由学生自己设定。（m<=20,n< =20） 功能要求： 1)可以输入各个项目的前三名或前五名的成绩； 2)能统计各学校总分，
数据结构二叉树习题含答案
2.1 创建一颗二叉树 创建一颗二叉树，可以创建先序二叉树，中序二叉树，后序二叉树。我们在创建的时候为了方便，不妨用‘#’表示空节点，这时如果先序序列是：6 4 2 3 # # # # 5 1 # # 7 # #，那么创建的二叉树如下： 下面是创建二叉树的完整代码：穿件一颗二叉树，返回二叉树的根 2.2 二叉树的遍历 二叉树的遍历分为：先序遍历，中序遍历和后序遍历，这三种遍历的写法是很相似的，利用递归程序完成也是灰常简单的： 2.3 层次遍历 层次遍历也是二叉树遍历的一种方式，二叉树的层次遍历更像是一种广度优先搜索（BFS）。因此二叉树的层次遍历利用队列来完成是最好不过啦，当然不是说利用别的数据结构不能完成。 2.4 求二叉树中叶子节点的个数 树中的叶子节点的个数= 左子树中叶子节点的个数+ 右子树中叶子节点的 个数。利用递归代码也是相当的简单， 2.5 求二叉树的高度 求二叉树的高度也是非常简单，不用多说：树的高度= max(左子树的高度，右子树的高度) + 1 2.6 交换二叉树的左右儿子 交换二叉树的左右儿子，可以先交换根节点的左右儿子节点，然后递归以左右儿子节点为根节点继续进行交换。树中的操作有先天的递归性。。 2.7 判断一个节点是否在一颗子树中 可以和当前根节点相等，也可以在左子树或者右子树中。 2.8 求两个节点的最近公共祖先 求两个节点的公共祖先可以用到上面的：判断一个节点是否在一颗子树中。（1）如果两个节点同时在根节点的右子树中，则最近公共祖先一定在根节点的右子树中。（2）如果两个节点同时在根节点的左子树中，则最近公共祖先一定在根节点的左子树中。（3）如果两个节点一个在根节点的右子树中，一个在根节点的
数据结构树和二叉树实验报告
《数据结构》课程实验报告 实验名称树和二叉树实验序号 5 实验日期 姓名院系班级学号 专业指导教师成绩 教师评语 一、实验目的和要求 (1)掌握树的相关概念，包括树、结点的度、树的度、分支结点、叶子结点、儿子结点、双亲结点、树 的深度、森林等定义。 (2)掌握树的表示，包括树形表示法、文氏图表示法、凹入表示法和括号表示法等。 (3)掌握二叉树的概念，包括二叉树、满二叉树和完全二叉树的定义。 (4)掌握二叉树的性质。 (5)重点掌握二叉树的存储结构，包括二叉树顺序存储结构和链式存储结构。 (6)重点掌握二叉树的基本运算和各种遍历算法的实现。 (7)掌握线索二叉树的概念和相关算法的实现。 (8)掌握哈夫曼树的定义、哈夫曼树的构造过程和哈夫曼编码产生方法。 (9)掌握并查集的相关概念和算法。 (10)灵活掌握运用二叉树这种数据结构解决一些综合应用问题。 二、实验项目摘要 1．编写一程序，实现二叉树的各种基本运算，并在此基础上设计一个主程序完成如下功能： （1）输出二叉树b; （2）输出H结点的左、右孩子结点值； （3）输出二叉树b的深度； （4）输出二叉树b的宽度； （5）输出二叉树b的结点个数； （6）输出二叉树b的叶子结点个数。 2．编写一程序，实现二叉树的先序遍历、中序遍历和后序遍历的各种递归和非递归算法，以及层次遍历的算法。 三、实验预习内容 二叉树存储结构，二叉树基本运算（创建二叉树、寻找结点、找孩子结点、求高度、输出二叉树）
三、实验结果与分析 7-1 #include
KTV点歌系统广工数据库课程设计
课程设计 课程名称数据库系统 题目名称___ 卡拉OK点歌系统___ 学生学院计算机学院 专业班级 2010级计算机科学与技术四班学号 3110006015 学生姓名张法光 指导教师路璐 2013年1 月12 日成绩
评价标准分数比例 （%） 成绩 论文论文结构包含： 1、相关技术介绍、需求分析、 2、概念结构设计（涉及的实体至少三个以上）、 3、逻辑结构设计（有完整性约束说明）、 4、数据库物理设计、 5、数据库完整性设计（违反实体、参照完整性时的解决办法，比 如触发器、存储过程等） 5、数据库安全性设计、 6、数据库实施、系统测试方案和测试报告、 7、系统的主要功能和使用说明、系统安装说明。 要求论文完整、内容详细，格式规范。 40 程序1、系统运行正确； 2、功能完善：有增、删、改、查功能，输入、输出功能； 3、有基本的统计、报表功能 4、有多表连接查询、自身连接查询、字符串匹配查询、模糊查询、 分组查询等。 5、工作量饱满； 6、系统实现技术的难度。 30 数据库设计E-R图设计正确，至少3个实体； 数据库逻辑结构设计规范化； 数据库物理设计合理。 30 总评成绩优良中及格不及格总分
目录 1 引言 (7) 1.1课题来源 (7) 1.2课题研究主要内容 (7) 1.3主要工作 (8) 2 需求分析 (8) 2.1信息要求分析 (8) 2.2处理要求分析 (8) 2.3数据字典及安全性、完整性要求分析 (9) 3 概念结构设计 (10) 3.1数据实体描述及分ER图 (10) 3.2整体ER图 (13) 4 系统概要设计 (14) 4.1数据库逻辑结构设计 (14) 4.2数据库物理设计 (16) 4.3系统总体框架 (17) 5 系统详细设计 (17) 5.1数据库实施 (17) 5.2数据库的数据完整性设计 (29) 5.3数据的安全设计 (31) 5.4系统功能模块的设计与实现 (31) 5.5系统功能测试 (32) 5.6数据库性能检测与备份设计 (49) 5.7系统安装使用说明 (49) 6 回顾与展望 (50) 7 参考文献 (50)
数据结构树练习题
数据结构－树练习题 一、选择题 1、二叉树的深度为k，则二叉树最多有（ C ）个结点。 A. 2k B. 2k-1 C. 2k-1 D. 2k-1 2、用顺序存储的方法，将完全二叉树中所有结点按层逐个从左到右的顺序存放在一维数组R[1..N]中，若结点R[i]有右孩子，则其右孩子是（ B ）。 A. R[2i-1] B. R[2i+1] C. R[2i] D. R[2/i] 3、设a,b为一棵二叉树上的两个结点，在中序遍历时，a在b前面的条件是（ B ）。 A. a在b的右方 B. a在b的左方 C. a是b的祖先 D. a是b的子孙 4、设一棵二叉树的中序遍历序列：badce，后序遍历序列：bdeca，则二叉树先序遍历序列为（）。 A. adbce B. decab C. debac D. abcde 5、在一棵具有5层的满二叉树中结点总数为（ A ）。 A. 31 B. 32 C. 33 D. 16 6、由二叉树的前序和后序遍历序列（ B ）惟一确定这棵二叉树。 A. 能 B. 不能 7、某二叉树的中序序列为ABCDEFG，后序序列为BDCAFGE，则其左子树中结点数目为（ C ）。 A. 3 B. 2 C. 4 D. 5 8、若以{4,5,6,7,8}作为权值构造哈夫曼树，则该树的带权路径长度为（ C ）。 A. 67 B. 68 C. 69 D. 70 9、将一棵有100个结点的完全二叉树从根这一层开始，每一层上从左到右依次对结点进行编号，根结点的编号为1，则编号为49的结点的左孩子编号为（A ）。 A. 98 B. 99 C. 50 D. 48 10、表达式a*(b+c)-d的后缀表达式是（ B ）。 A. abcd+- B. abc+*d- C. abc*+d- D. -+*abcd 11、对某二叉树进行先序遍历的结果为ABDEFC，中序遍历的结果为DBFEAC，则后序遍历的结果是（ B ）。 A. DBFEAC B. DFEBCA C. BDFECA D. BDEFAC 12、树最适合用来表示（ C ）。 A. 有序数据元素 B. 无序数据元素 C. 元素之间具有分支层次关系的数据 D. 元素之间无联系的数据 13、表达式A*(B+C)/(D-E+F)的后缀表达式是（ C ） A. A*B+C/D-E+F B. AB*C+D/E-F+ C. ABC+*DE-F+/ D. ABCDED*+/-+ 14、任何一棵二叉树的叶结点在先序、中序和后序遍历序列中的相对次序（）。 A. 不发生改变 B. 发生改变 C. 不能确定 D. 以上都不对 15、假定在一棵二叉树中，度为2的结点数为15，度为1的结点数为30，则叶子结点数为（）个。 A. 15 B. 16 C. 17 D. 47 16、由权值为3，6，7，2，5的叶子结点生成一棵哈夫曼树，它的带权路径长度为（）。 A. 51 B. 23 C. 53 D. 74
第六章树和二叉树习题数据结构
习题六树和二叉树 一、单项选择题 1．以下说法错误的是 ( ) A．树形结构的特点是一个结点可以有多个直接前趋 B．线性结构中的一个结点至多只有一个直接后继 C．树形结构可以表达(组织)更复杂的数据 D．树(及一切树形结构)是一种"分支层次"结构 E．任何只含一个结点的集合是一棵树 2．下列说法中正确的是 ( ) A．任何一棵二叉树中至少有一个结点的度为2 B．任何一棵二叉树中每个结点的度都为2 C．任何一棵二叉树中的度肯定等于2 D．任何一棵二叉树中的度可以小于2 3．讨论树、森林和二叉树的关系，目的是为了（） A．借助二叉树上的运算方法去实现对树的一些运算 B．将树、森林按二叉树的存储方式进行存储 C．将树、森林转换成二叉树 D．体现一种技巧，没有什么实际意义 4．树最适合用来表示 ( ) A．有序数据元素 B．无序数据元素 C．元素之间具有分支层次关系的数据 D．元素之间无联系的数据 5．若一棵二叉树具有10个度为2的结点，5个度为1的结点，则度为0的结点个数是（）A．9 B．11 C．15 D．不确定 6．设森林F中有三棵树，第一，第二，第三棵树的结点个数分别为M1，M2和M3。与森林F对应的二叉树根结点的右子树上的结点个数是（）。 A．M1 B．M1+M2 C．M3 D．M2+M3 7．一棵完全二叉树上有1001个结点，其中叶子结点的个数是（） A． 250 B． 500 C．254 D．505 E．以上答案都不对 8. 设给定权值总数有n 个，其哈夫曼树的结点总数为( ) A．不确定 B．2n C．2n+1 D．2n-1 9．二叉树的第I层上最多含有结点数为（） A．2I B． 2I-1-1 C． 2I-1 D．2I -1 10．一棵二叉树高度为h,所有结点的度或为0，或为2，则这棵二叉树最少有( )结点A．2h B．2h-1 C．2h+1 D．h+1 11. 利用二叉链表存储树，则根结点的右指针是（）。 A．指向最左孩子 B．指向最右孩子 C．空 D．非空 14．在二叉树结点的先序序列，中序序列和后序序列中，所有叶子结点的先后顺序（）A．都不相同 B．完全相同 C．先序和中序相同，而与后序不同 D．中序和后序相同，而与先序不同 15．在完全二叉树中，若一个结点是叶结点，则它没（）。 A．左子结点 B．右子结点 C．左子结点和右子结点 D．左子结点，右子结点和兄弟结点 16．在下列情况中，可称为二叉树的是（）
数据结构课程设计独立题目
题目2：运动会分数统计 1.问题描述 参加运动会有n个学校，学校编号为1……n。比赛分成m个男子项目，和w个女子项目。项目编号为男子1……m，女子m+1……m+w。不同的项目取前五名或前三名积分；取前五名的积分分别为：7、5、3、2、1，前三名的积分分别为：5、3、2；哪些取前五名或前三名由学生自己设定。（m<=20,n<=20） 2.功能要求 1)可以输入各个项目的前三名或前五名的成绩； 2)能统计各学校总分； 3)可以按学校编号、学校总分、男女团体总分排序输出； 4)可以按学校编号查询学校某个项目的情况；可以按项目编号查询取得前三或前五名的学校。 存储结构：学生自己根据系统功能要求自己设计，但是要求运动会的相关数据要存储在数据文件中。 。 题目6：哈夫曼编/译码器 1.问题描述 利用哈夫曼编码进行信息通信可以大大提高信道利用率，缩短信息传输时间，降低传输成本。但是，这要求在发送端通过一个编码系统对待传数据预先编码，在接收端将传来的数据进行译码（复原）。对于双工信道（即可以双向传输信息的信道），每端都需要一个完整的编/译码系统。试为这样的信息收发站写一个哈夫曼编/译码系统。 2.功能要求 I：初始化（Initialization）。从终端读入字符集大小n，以及n个字符和n个权值，建立哈夫曼树，并将它存于文件hfmTree中。 E：编码（Encoding）。利用已建好的哈夫曼树（如不在内存，则从文件htmTree 中读入），对文件ToBeTran中的正文进行编码，然后将结果存入文件CodeFile 中。 D：译码（Decoding）。利用已建好的哈夫曼树将文件CodeFile中的代码进行译码，结果存入文件TextFile中。 P：印代码文件（Print）。将文件CodeFile以紧凑格式显示在终端上，每行50个代码。同时将此字符形式的编码写入文件CodePrint中。 T：印哈夫曼树（Tree Printing）。将已在内存中的哈夫曼树以直观的方式（树或凹入表形式）显示在终端上，同时将此字符形式的哈夫曼树写入文件TreePrint 中。 题目9：构造可以使n个城市连接的最小生成树 1.问题描述 给定一个地区的n个城市间的距离网，用Prim算法或Kruskal算法建立最小生成树，并计算得到的最小生成树的代价。 2.功能要求 城市间的距离网采用邻接矩阵表示，邻接矩阵的存储结构定义采用课本中给出的定义，若两个城市之间不存在道路，则将相应边的权值设为自己定义的无穷大值。要求在屏幕上显示得到的最小生成树中包括了哪些城市间的道路，并显示得到的最小生成树的代价。
数据结构 二叉树练习题答案
数据结构第6章树和二叉树 一、下面是有关二叉树的叙述，请判断正误 （√）1.若二叉树用二叉链表作存贮结构，则在n个结点的二叉树链表中只有n-1个非空指针域。 n个结点的二叉树有n-1条分支 （×）2.二叉树中每个结点的两棵子树的高度差等于1。 （√）3.二叉树中每个结点的两棵子树是有序的。 （×）4.二叉树中每个结点有两棵非空子树或有两棵空子树。 （×）5.二叉树中每个结点的关键字值大于其左非空子树（若存在的话）所有结点的关键字值，且小于其右非空子树 （若存在的话）所有结点的关键字值。 （应当是二叉排序树的特点） （×）6.二叉树中所有结点个数是2k-1-1，其中k是树的深度。（应2k-1） （×）7.二叉树中所有结点，如果不存在非空左子树，则不存在非空右子树。 （×）8.对于一棵非空二叉树，它的根结点作为第一层，则它的第i层上最多能有2i -1个结点。
（应2i-1） （√）9.用二叉链表法（link-rlink）存储包含n个结点的二叉树，结点的2n个指针区域中有n+1个为空指针。（用二叉链表存储包含n个结点的二叉树，结点共有2n个链域。由于二叉树中，除根结点外，每一个结点有且仅有一个双亲，所以只有n-1个结点的链域存放指向非空子女结点的指针，即有后继链接的指针仅n-1个，还有n+1个空指针。）采用二叉链表存储有2n个链域，空链域为：2n-（n-1）=n+1 （√）10.具有12个结点的完全二叉树有5个度为2的结点。 最快方法：用叶子数＝[ n/2] ＝6，再求n2=n0-1=5 [n/2] 除的结果四舍五入 二、填空 1．由３个结点所构成的二叉树有5种形态。 2. 一棵深度为6的满二叉树有n1+n2=0+ n2= n0-1=31 个分支结点和26-1 =32个叶子。 注：满二叉树没有度为1的结点，所以分支结点数就是二度结点数。 (或：总结点数为n=2k-1=26-1=63，叶子数为n0= [ n/2] =32，满二叉数没有度为1的结点，由n0=n2+1得n2=n0-1=32-1=31)
目前最完整的数据结构1800题包括完整答案树和二叉树答案
第6章树和二叉树 部分答案解释如下。 12. 由二叉树结点的公式：n=n0+n1+n2=n0+n1+(n0-1)=2n0+n1-1，因为n=1001,所以1002=2n0+n1,在完全二叉树树中，n1只能取0或1,在本题中只能取0，故n=501，因此选E。 42.前序序列是“根左右”，后序序列是“左右根”，若要这两个序列相反，只有单支树，所以本题的A和B均对，单支树的特点是只有一个叶子结点，故C是最合适的，选C。A或B 都不全。由本题可解答44题。 47. 左子树为空的二叉树的根结点的左线索为空（无前驱），先序序列的最后结点的右线索为空（无后继），共2个空链域。 52．线索二叉树是利用二叉树的空链域加上线索，n个结点的二叉树有n+1个空链域。 部分答案解释如下。 6．只有在确定何序（前序、中序、后序或层次）遍历后，遍历结果才唯一。 19．任何结点至多只有左子树的二叉树的遍历就不需要栈。 24. 只对完全二叉树适用，编号为i的结点的左儿子的编号为2i(2i<=n)，右儿子是2i+1（2i+1<=n） 37. 其中序前驱是其左子树上按中序遍历的最右边的结点（叶子或无右子女），该结点无右孩子。 38 . 新插入的结点都是叶子结点。 42. 在二叉树上，对有左右子女的结点，其中序前驱是其左子树上按中序遍历的最右边的结点（该结点的后继指针指向祖先），中序后继是其右子树上按中序遍历的最左边的结点（该结点的前驱指针指向祖先）。 44．非空二叉树中序遍历第一个结点无前驱，最后一个结点无后继，这两个结点的前驱线索和后继线索为空指针。 三.填空题
1.(1)根结点(2)左子树(3)右子树 2.(1)双亲链表表示法(2)孩子链表表示法(3)孩 子兄弟表示法 3．p->lchild==null && p->rchlid==null 4.(1) ++a*b3*4-cd (2)18 5.平衡 因子 6. 9 7. 12 8.(1)2k-1 (2)2k-1 9.(1)2H-1 (2)2H-1 (3)H=?log2N?+1 10. 用顺序存储二叉树时，要按完全二叉树的形式存储，非完全二叉树存储时，要加“虚结 点”。设编号为i和j的结点在顺序存储中的下标为s 和t ,则结点i和j在同一层上的条 件是?log2s?=?log2t?。 11. ?log2i?=?log2j?12.(1)0 (2)(n-1)/2 (3)(n+1)/2 (4) ?log2n?+1 13.n 14. N2+1 15.(1) 2K+1-1 (2) k+1 16. ?N/2? 17. 2k-2 18. 64 19. 99 20. 11 21.(1) n1-1 (2)n2+n3 22.(1)2k-2+1（第k层1个结点，总结点个数是2H-1，其双亲是2H-1/2=2k-2）(2) ?log2i?+1 23.69 24. 4 25.3h-1 26. ?n/2? 27. ?log2k?+1 28.(1)完全二叉树 (2)单枝树，树中任一结点（除最后一个结点是叶子外）,只有左子女或 只有右子女。 29.N+1 30.(1) 128(第七层满，加第八层１个) (2) 7 31. 0至多个。任意二叉树，度为１的结点个数没限制。只有完全二叉树，度为１的结点个 数才至多为1。 32．21 33.(1)2 (2) n-1 (3) 1 (4) n (5) 1 (6) n-1 34.(1) FEGHDCB (2)BEF（该二叉树转换成森林，含三棵树，其第一棵树的先根次序是 BEF） 35.(1)先序（2）中序 36. (1)EACBDGF （2）2 37.任何结点至多只有右子女 的二叉树。 38.(1)a (2) dbe (3) hfcg 39.(1) . (2) ...GD.B...HE..FCA 40.DGEBFCA 41．(1)5 （2）略 42.二叉排序树 43.二叉树 44. 前序 45.(1)先根次序（2）中根次序46.双亲的右子树中最左下的叶子结点47.2 48.(n+1)/2 49.31（x的后继是经x的双亲y的右子树中最左下的叶结点） 50.(1)前驱 (2)后 继 51.(1)1 (2)y^.lchild (3)0 (4)x (5)1 (6) y (7)x(编者注：本题按 中序线索化) 52.带权路径长度最小的二叉树，又称最优二叉树 53.69 54.(1)6 (2)261 55.(1)80 (2)001（不唯一）56.2n0-1 57.本题①是表达式求值，②是在二叉排序树中删除值为x的结点。首先查找x，若没有x， 则结束。否则分成四种情况讨论：x结点有左右子树；只有左子树；只有右子树和本身是叶 子。 (1)Postoder_eval(t^.Lchild) (2) Postorder_eval(t^.Rchild) (3)ERROR(无此运 算符)(4)A (5)tempA^.Lchild (6)tempA=NULL(7)q^.Rchild (8)q (9)tempA^.Rchild (10)tempA^.Item 《数据结构》课程设计题目 1. 排序算法的性能分析 问题描述 设计一个测试程序，比较几种内部排序算法的关键字比较次数和移动次数以取得直观感受。 基本要求 （1）对冒泡排序、直接排序、选择排序、箱子排序、堆排序、快速排序及归并排序算法进行比较。 （2）待排序表的表长不小于100，表中数据随机产生，至少用5组不同数据作比较，比较指标：关键字参加比较次数和关键字的移动次数（关键字交换记为3次移动）。 （3）输出比较结果。 选做内容 （1）对不同表长进行比较。 （2）验证各算法的稳定性。 （3）输出界面的优化。 2. 排序算法思想的可视化演示—1 基本要求 排序数据随机产生，针对随机案例，对冒泡排序、箱子排序、堆排序、归并算法，提供排序执行过程的动态图形演示。 3. 排序算法思想的可视化演示—2 基本要求 排序数据随机产生，针对随机案例，，对插入排序、选择排序、基数排序、快速排序算法，提供排序执行过程的动态图形演示。 4. 线性表的实现与分析 基本要求 ①设计并实现线性表。 ②线性表分别采取数组（公式化描述）、单链表、双向链表、间接寻址存储方 式 ③针对随机产生的线性表实例，实现线性表的插入、删除、搜索操作动态演示(图 形演示)。 5. 等价类实现及其应用 问题描述：某工厂有一台机器能够执行n个任务，任务i的释放时间为r i（是一个整数），最后期限为d i（也是整数）。在该机上完成每个任务都需要一个单元的时间。一种可行的调 度方案是为每个任务分配相应的时间段，使得任务i的时间段正好位于释放时间和最后期限之间。一个时间段不允许分配给多个任务。 基本要求： 使用等价类实现以上机器调度问题。 等价类分别采取两种数据结构实现。 6. 一元稀疏多项式计算器 问题描述 设计一个一元稀疏多项式简单计算器。 基本要求 一元稀疏多项式简单计算器的基本功能是： （1）输入并建立多项式； （2）输出多项式，输出形式为整数序列：n，c1，e1，c2，e2，…,c n，e n，其中n是多项式的项数，c i，e i，分别是第i项的系数和指数，序列按指数降序排序； （3）多项式a和b相加，建立多项式a+b； （4）多项式a和b相减，建立多项式a-b； （5）计算多项式在x处的值； （6）计算器的仿真界面（选做） 7. 长整数的代数计算 问题描述 应用线性数据结构解决长整数的计算问题。设计数据结构完成长整数的表示和存储，并编写算法来实现两长整数的加、减、乘、除等基本代数运算。 基本要求 ①长整数长度在一百位以上。 ②实现两长整数在取余操作下的加、减、乘、除操作，即实现算法来求解a+b mod n, a-b mod n, a?b mod n, a÷b mod n。 ③输入输出均在文件中。 ④分析算法的时空复杂性。 8. 敢死队问题。 有M个敢死队员要炸掉敌人的一碉堡，谁都不想去，排长决定用轮回数数的办法来决定哪个战士去执行任务。如果前一个战士没完成任务，则要再派一个战士上去。现给每个战士编一个号，大家围坐成一圈，随便从某一个战士开始计数，当数到5时，对应的战士就去执行任务，且此战士不再参加下一轮计数。如果此战士没完成任务，再从下一个战士开始数数，被数到第5时，此战士接着去执行任务。以此类推，直到任务完成为止。排长是不愿意去的，假设排长为1号，请你设计一程序，求出从第几号战士开始计数才能让排长最后一个留下来而不去执行任务。 要求：至少采用两种不同的数据结构的方法实现。 9. 简单计算器 树和二叉树习题数据结 构 标准化管理处编码[BBX968T-XBB8968-NNJ668-MM9N] 习题六树和二叉树一、单项选择题 1．以下说法错误的是 ( ) A．树形结构的特点是一个结点可以有多个直接前趋B．线性结构中的一个结点至多只有一个直接后继 C．树形结构可以表达(组织)更复杂的数据 D．树(及一切树形结构)是一种"分支层次"结构 E．任何只含一个结点的集合是一棵树 2．下列说法中正确的是 ( ) A．任何一棵二叉树中至少有一个结点的度为2 B．任何一棵二叉树中每个结点的度都为2 C．任何一棵二叉树中的度肯定等于2 D．任何一棵二叉树中的度可以小于2 3．讨论树、森林和二叉树的关系，目的是为了（）A．借助二叉树上的运算方法去实现对树的一些运算B．将树、森林按二叉树的存储方式进行存储 C．将树、森林转换成二叉树 D．体现一种技巧，没有什么实际意义 4．树最适合用来表示 ( ) A．有序数据元素 B．无序数据元素 C．元素之间具有分支层次关系的数据 D．元素之间无联系的数据5．若一棵二叉树具有10个度为2的结点，5个度为1的结点，则度为0的结点个数是（） A．9 B．11 C．15 D．不确定 6．设森林F中有三棵树，第一，第二，第三棵树的结点个数分别为M1，M2和M3。与森林F对应的二叉树根结点的右子树上的结点个数是（）。 A．M1 B．M1+M2 C．M3 D．M2+M3 7．一棵完全二叉树上有1001个结点，其中叶子结点的个数是（）A． 250 B． 500 C．254 D．505 E．以上答案都不对 8. 设给定权值总数有n 个，其哈夫曼树的结点总数为( ) A．不确定 B．2n C．2n+1 D．2n-1 9．二叉树的第I层上最多含有结点数为（） A．2I B． 2I-1-1 C． 2I-1 D．2I -1 10．一棵二叉树高度为h,所有结点的度或为0，或为2，则这棵二叉树最少有( )结点 树与二叉树 一.选择题 1.假定在一棵二叉树中，双分支结点数为15，单分支结点数为30个，则叶子结 点数为（）个。 A．15B．16C．17D．47 2.按照二叉树的定义，具有3个结点的不同形状的二叉树有（）种。 A. 3 B. 4 C. 5 D. 6 3.按照二叉树的定义，具有3个不同数据结点的不同的二叉树有（）种。 A. 5 B. 6 C. 30 D. 32 4.深度为5的二叉树至多有（）个结点。1 A. 16 B. 32 C. 31 D. 10 5.设高度为h的二叉树上只有度为0和度为2的结点，则此类二叉树中所包含的 结点数至少为（）。 A. 2h B. 2h-1 C. 2h+1 D. h+1 6.对一个满二叉树2，m个树叶，n个结点，深度为h，则（）。 A. n=h+m3 B. h+m=2n C. m=h-1 D. n=2 h-1 1深度为n的二叉树结点至多有2n-1 2满二叉树是除最后一层无任何子节点外，每一层上的所有结点都有两个子结点的二叉树7.任何一棵二叉树的叶结点在先序.中序和后序遍历序列中的相对次序（）。 A.不发生改变 B.发生改变 C.不能确定 D.以上都不对 8.如果某二叉树的前根次序遍历结果为stuwv，中序遍历为uwtvs，那么该二叉 树的后序为（）。 A. uwvts B. vwuts C. wuvts D. wutsv 9.某二叉树的前序遍历结点访问顺序是abdgcefh，中序遍历的结点访问顺序是 dgbaechf，则其后序遍历的结点访问顺序是（）。 A. bdgcefha B. gdbecfha C. bdgaechf D. gdbehfca 10.在一非空二叉树的中序遍历序列中，根结点的右边（）。 A. 只有右子树上的所有结点 B. 只有右子树上的部分结点 C. 只有左子树上的部分结点 D. 只有左子树上的所有结点 11.树的基本遍历策略可分为先根遍历和后根遍历；二叉树的基本遍历策略可分为 先序遍历.中序遍历和后序遍历。这里，我们把由树转化得到的二叉树4叫做这棵数对应的二叉树。结论（）是正确的。 A.树的先根遍历序列与其对应的二叉树的先序遍历序列相同 B.树的后根遍历序列与其对应的二叉树的后序遍历序列相同 3对于深度为h的满二叉树，n=20+21+…+2h-1=2h-1，m=2h-1。故而n=h+m。 4树转化为二叉树的基本方法是把所有兄弟结点都用线连起来，然后去掉双亲到子女的连线，只留下双亲到第一个子女的连线。因此原来的兄弟关系就变为双亲与右孩子的关系。 1/ 9 课程名称数据库系统 题目名称小型超市管理系统学生学院计算机学院 专业班级 学号 学生姓名 指导教师 2013 年 1 月 目录 1 引言 (1) 1.1课题来源 (1) 1.2课题研究主要内容 (1) 1.3主要工作 (1) 2 开发工具和平台 (1) 3 命名约定 (1) 4 需求分析 (2) 4.1信息要求分析 (2) 4.2处理要求分析 (2) 5 概念结构设计 (3) 5.1数据实体描述及分ER图 (3) 5.2整体ER图 (3) 6 系统概要设计 (4) 6.1数据库逻辑结构设计 (4) 6.2数据库物理设计 (6) 6.3系统总体框架 (7) 7 系统详细设计 (7) 7.1数据库实施 (7) 7.2数据库的数据完整性设计 (9) 7.3数据的安全设计 (10) 7.4系统功能模块的设计与实现 (11) 7.5系统安装使用说明 (21) 8 回顾与展望 (21) 参考文献 (22) 1 引言 1.1课题来源 到超市购物是一种较为频繁的生活事件。由于人们的超市购物行为越来越频繁，超市规模越来越大，商品种类数目与之俱增，超市商品的管理变得更加困难。显然手工的管理方式是不合适的。因此利用数据库相关技术开发一个规模适当、操作方便、功能完备的超市管理系统显得很有必要。 1.2课题研究主要内容 使用数据库管理系统和应用程序实现小型超市管理系统的商品销售结算，销售情况管理，商品信息管理，库存管理，权限管理等功能。 1.3主要工作 先对小型超市管理系统的设计进行需求分析，建立数据流图和数据字典。进行概念结构设计，作出E-R图并进行优化。进行逻辑结构设计，建立数据关系模型。进行物理结构设计，选择适当的存取方法。利用数据库管理系统按前面的分析设计作出若于基本表，根据应用程序和用户的需要建立视图。最后进行应用程序的设计、调试、运行。 2 开发工具和平台 数据库管理系统：Microsoft SQL Server 2008 程序设计语言：Java 1.6 应用程序开发工具：eclipse 测试平台 Windows 7 64bit 3 命名约定 表名和属性名的首字母大写（虽然SQL语言不分大小写，但设计过程仍遵守这一约定）， 1 《数据结构》课程设计课题表 课题1：设计出链表结构的相关函数库，以便在程序设计中调用。要求： （1）包括线性表的各种基本函数以及常用函数（自己确定函数、函数形式及理由）。 （2）最好能借助语言环境实现图形显示功能，以便能将抽象的数据结构以图形方式显示出来，将复杂的运行过程以动态方式显示出来。 （3）给出若干例程，演示通过调用自己的库函数来实现相关问题的求解。 课题2：设计出顺序表结构的相关函数库，以便在程序设计中调用。要求： （1）包括线性表的各种基本函数以及常用函数（自己确定函数、函数形式及理由）。 （2）最好能借助语言环境实现图形显示功能，以便能将抽象的数据结构以图形方式显示出来，将复杂的运行过程以动态方式显示出来。 （3）给出若干例程，演示通过调用自己的库函数来实现相关问题的求解。 课题3：设计程序以实现任意两个高次多项式的加法和乘法运算。 要求： （1）所设计的数据结构应尽可能节省存储空间。 （2）程序的运行时间应尽可能少。 课题4：设计一个模拟计算器的程序，要求能对包含加、减、乘、除、括号运算符及SQR和ABS函数的任意整型表达式进行求解。 要求：要检查有关运算的条件，并对错误的条件产生报警。 课题5：设计出二叉链表结构的相关函数库，以便在程序设计中调用。要求： （1）包括二叉树的各种基本函数以及常用函数（自己确定函数、函数形式及理由）。 （2）最好能借助语言环境实现图形显示功能，以便能将抽象的数据结构以图形方式显示出来，将复杂的运行过程以动态方式显示出来。 （3）给出若干例程，演示通过调用自己的库函数来实现相关问题的求解。 课题6：设计出树结构的相关函数库，以便在程序设计中调用。要求： （1）包括树结构的存储结构及各种基本函数以及常用函数（自己确定函数、函数形式及理由）。 （2）最好能借助语言环境实现图形显示功能，以便能将抽象的数据结构以图形方式显示出来，将复杂的运行过程以动态方式显示出来。 （3）给出若干例程，演示通过调用自己的库函数来实现相关问题的求解。 课题7：选择合适的存储结构表示广义表，并能实现下列运算要求： （1）用大写字母表示广义表，用小写字母表示原子，并提供设置广义表的值的功能。 （2）取广义表L的表头和表尾的函数head(L)和tail(L)。 第六章 树和二叉树 一、选择题 1．已知一算术表达式的中缀形式为 A+B*C-D/E ，后缀形式为ABC*+DE/-，其前缀形式为 ( ) A ．-A+B*C/DE B. -A+B*CD/E C ．-+*ABC/DE D. -+A*BC/DE 【北京航空航天大学 1999 一、3 （2分)】 2．算术表达式a+b*（c+d/e ）转为后缀表达式后为（ ）【中山大学 1999 一、5】 A ．ab+cde/* B ．abcde/+*+ C ．abcde/*++ D ．3. 设有一表示算术表达式的二叉树（见下图）， 它所表示的算术表达式是（ ） 【南京理工大学1999 一、20（2分）】 A. A*B+C/(D*E)+(F-G) B. (A*B+C)/(D*E)+(F-G) C. (A*B+C)/(D*E+（F-G ）) D. A*B+C/D*E+F-G 4. 设树T 的度为4，其中度为1，2，3和4的结点个数分别为4，2，1 ，1 则T 中的叶子数为（ ） A ．5 B ．6 C ．7 D ．8 【南京理工大学 2000 一、8 （1.5分）】 5. 在下述结论中，正确的是（ ）【南京理工大学 1999 一、4 （1分）】 ①只有一个结点的二叉树的度为0; ②二叉树的度为2； ③二叉树的左右子树可任意 交换; ④深度为K 的完全二叉树的结点个数小于或等于深度相同的满二叉树。 A ．①②③ B ．②③④ C ．②④ D ．①④ 6. 设森林F 对应的二叉树为B ，它有m 个结点，B 的根为p,p 的右子树结点个数为n,森林F 中第一棵树的结点个数是（ ） A ．m-n B ．m-n-1 C ．n+1 D ．条件不足，无法确定 【南京理工大学2000 一、 17（1.5分）】 7. 树是结点的有限集合，它（ (1）)根结点，记为T 。其余结点分成为m （m>0）个(（2）) 的集合T1，T2， …，Ｔm ，每个集合又都是树，此时结点T 称为Ti 的父结点，Ti 称为T 的子结点（1≤i ≤m ）。一个结点的子结点个数称为该结点的( （3） )。二叉树与树是两个 不同的概念，二叉树也是结点的有限集合，它(（4）)根结点。可以把树的根结点的层数定 义为1，其他结点的层数等于其父结点所在层数加上1。令T 是一棵二叉树，Ki 和Kj 是T 中子结点数小于2的结点中的任意两个，它们所在的层数分别为λKi 和λKj ，当关系式│ λKi-λKj │≤1一定成立时，则称T 为一棵（(5)）。供选择的答案： （1）(4) A. 有0个或1个 B. 有0个或多个 C. 有且只有一个 D. 有1个或1 个以上 （2） A. 互不相交 B.允许相交 C.允许叶结点相交 D.允许树枝结点相交 （3） A. 权 B.维数 C.次数 D.序 （5） A. 丰满树 B.查找树 C.平衡树 D.完全树 【上海海运学院1999二、 2(5分）】 8．若一棵二叉树具有10个度为2的结点，5个度为1的结点，则度为0的结点个数是（ ） A ．9 B ．11 C ．15 D ．不确定 【北京工商大学2001一.7(3 分)】 9．在一棵三元树中度为3的结点数为2个，度为2的结点数为1个，度为1的结点数为2 计算机与通信工程学院 数据库课程设计(酒店 管理系统) 数据库系统课程设计报告题目: 酒店管理系统 课程代号:0680036 课程名称：数据库系统课程设计 学号： 姓名： 班级： 指导教师 完成日期：2011年4月 目录 第一章引言 第二章系统分析与设计 2.1需求分析 2.2结构设计 2.3数据库设计 第三章系统开发及实现 3.1创建主窗体 3.2创建子窗体 3.3建立公共模块 第四章总结 参考文献 附录（附部分源代码） 第一章引言 酒店管理系统是现代服务行业不可缺少的一个组成环节。 酒店管理信息系统是一个由人、计算机和数据库组成的进行酒店经营管理的系统，通过对信息的收集、传递、整理、加工、维护和使用，提高管理水平和效率，从而实现酒店管理的自动化、规范化和人性化。 本文简要介绍了基于Microsoft和VB程序语言开发实现的酒店管理系统，着重阐述了该系统开发实现过程，从系统的需求分析、方案论证、模块设计、数据设计、详细设计到系统测试等各个环节都进行了较为详尽的分析和描述。 关键词：酒店管理系统、Access、数据库、VB 第二章系统分析与设计 2.1需求分析 在进行一个项目的设计之前，首先要进行必要的需求分析。酒店需要管理各种人员和入住信息，希望实现酒店的信息化管理，通过建立一个酒店管理系统来管理酒店的日常业务。其完成功能如下： 1、能够实现对客人的登记信息查询，包括逐个浏览，以及对客人资料的增加、删除和编辑操作。 2、能够的酒店人员值班情况进行管理。 3、管理人员也可以直接增加和删除用户信息。 系统功能模块图如图1所示。 图1系统的功能模块图 根据功能模块图设计划出的实体有散客入住实体、团队入住实体、投诉管理实体、值班管理实体。 散客入住实体E-R如图2所示。 团队入住实体E-R如图3所示 投诉管理实体E-R图如图4所示 值班管理实体E-R图如图5所示 2.2 统Access即可。他们之间的关系如图6所示。 数据结构课程设计 一、考核方法和容 根据课程设计过程中学生的学生态度、题目完成情况、课程设计报告书的质量和回答问题的情况等按照10%、40%、30%、20%加权综合打分。成绩评定实行优秀、良好、中等、及格和不及格五个等级。 评分标准： 优秀：答辩所有问题都能答出+报告良好 或报告良好+实现“提高部分”的功能； 良好：答辩所有问题都能答出+报告一般； 或报告一般+实现“提高部分”的功能； 中等：答辩大部分问题能答出+报告良好； 及格：答辩大部分问题能答出+报告一般； 以下四种，都不及格： 1)答辩几乎答不出问题； 2)报告几乎都是代码； 3)雷同部分达到60%； 4)课设报告与数据结构和c/c++关联不大。 课设报告的装订顺序如下： 任务书（签名，把题目要求贴在相应位置，注意下划线）-----目录（注意目录的格式，页码）-----1、设计任务（题目要求）-----2、需求分析（准备选用什么数据逻辑结构？数据元素包含哪些属性？需要哪些函数？为什么要这样设计？最后列出抽象数据类型定义）-----3、系统设计（设计实现抽象数据类型，包含选择什么物理存储方式？数据元素的结构体或类定义，以及各函数的设计思路，算法，程序流程图等）----4、编码实现（重要函数的实现代码）-----5、调试分析（选择多组测试数据、运行截图、结果分析）-----6、课设总结（心得体会）-----7、谢辞-----8、参考文献； 课设报告打印要求： B5纸打印，报告总页数控制在10—15页，报告中不能全是代码，报告中代码总量控制在3页。版式：无页眉，有页码，页码居中 字号：小四，单倍行距 字体：宋体+Times new Romar 截图：截图要配图的编号和图的题目，如：“图1 Insert函数流程图” 二、课程设计的题目 1.长整数的加法运算 2.通讯录管理系统的设计与实现——顺序表 3.广义表的应用 4.学生成绩管理系统的设计与实现 5.家谱管理系统的设计与实现数据结构课程设计题目
树和二叉树习题数据结构
数据结构树和二叉树习题
数据库课程设计超市管理系统(广工)
数据结构课程设计题目表
数据结构 习题 第六章 树和二叉树
[精编]数据库课程设计(酒店管理系统)
数据结构课程设计题目
- 数据库课程设计(完整版) (2)
- 学生信息管理系统数据库课程设计报告
- 广东工业大学数据库原理与应用课程设计
- 大型数据库课程设计完整版
- 广工数据库实验报告
- 广工数据库课程设计
- 数据库课程设计学生选修课系统.docx
- 学生信息管理系统数据库课程设计
- 人员信息管理系统数据库课程设计
- 数据库课程设计学生选课管理系统
- 教学管理系统数据库课程设计报告(广东工业大学)
- 广工数据库实验报告
- 广工数据库课程设计报告
- 数据库课程设计-学生宿舍管理系统
- 仓库管理系统数据库课程设计
- 广东工业大学数据库原理与设计试卷部分答案
- [精编]数据库课程设计(酒店管理系统)
- 数据库课程设计-学生信息管理系统教程文件
- 广东工业大学数据库课程设计机房管理系统设计
- 数据库系统实验报告广东工业大学