《数据结构》实验要求2014-10

班级： 学号： 姓名：

1 第4章 树

一、单项选择题： 1. 如下图4-1所示的4棵二叉树中， 不是完全二叉树。

A. B. C. D.

图4-1 4棵二叉树

2. 二叉树按某种顺序线索化后，任一结点均有指向其前驱和后续的线索，这种说法 。

A.正确 B.错误

3. 二叉树的先序遍历序列中，任意一个结点均处在其孩子结点的前面，这种说法 。

A.正确 B.错误

4. 由于二叉树中每个结点的度最大为2，所以二叉树是一种特殊的树，这种说法 。

A.正确 B.错误

5. 设高度为h的二叉树上只有度为0和度为2的结点，则此类二叉树中所包含的结点数至少为 。

A.2h B.2h-1 C.2h+1 D.h+1

6. 如果T2是由有序树T1转换而来的二叉树，那么T1中结点的先根遍历就是T2中结点的 遍历。

A.先序 B.中序 C.后序 D.层次序

7. 某二叉树的先序遍历序列和后序遍历序列正好相反，则该二叉树一定是 。

A.空或只有一个结点 B.完全二叉树 C.二叉排序树 D.高度等于其结点数 班级： 学号： 姓名：

2 8. 如下图4-2所示的T2是由森林T1转化而来的二叉树，那么森林T1有 个叶子结点。

A.4 B.5 C.6 D.7

图4-2 一棵二叉树

9. 按照二叉树的定义，具有3个结点的二叉树有 种。 A.3 B.4 C.5 D.6

10. 在一非空二叉树的中序遍历序列中，根结点的右边 。

A. 只有右子树上的所有结点 B.只有右子树上的部分结点

C. 只有左子树上的部分结点 D.只有左子树上的所有结点

11. 任何一棵二叉树的叶子结点在先序、中序和后序遍历序列中的相对次序 。

A.不发生改变 B.发生改变 C.不能确定 D.以上都不对

12. 设n，m为一棵二叉树上的两个结点，在中序遍历时，n在m前的条件是 。

A.n在m右方 B.n是m祖先 C.n在m左方 D.n是m子孙

13. 线索二叉树是一种 结构。

.专业.专注.

. word可编辑 . 《数据结构》课程设计大纲

课程设计名称：数据结构

实验室名称：计算机与信息技术实验室

适用专业：计算机科学与技术、信息管理与信息系统

实验对象：本科生

实验要求：必修

一、课程设计的目的

课程设计是《数据结构》课程教学必不可缺的一个重要环节，它可加深学生对该课程所学内容的进一步的理解与巩固，是将计算机课程与实际问题相联接的关键步骤。通过课程设计，能够提高学生分析问题、解决问题，从而运用所学知识解决实际问题的能力，因而必须给予足够的重视。

二、课程设计的要求

1．明确课程任务，复习与查阅有关资料。

2．按要求完成课程设计内容，课程设计报告要求文字和图工整、思路清楚、正确。

3．一至四名同学分为一组，完成一个应用问题的程序的编写工作。

4．应用程序应具有一定的可用性：

（1）等候用户输入时，给出足够的提示信息，如“Please Select（1—3）：”提示用户选择。

（2）格式明显易懂，配上适当的颜色、声音等辅助效果，能方便地改正输入时的错误，.专业.专注.

. word可编辑 . 使用户感到方便、好用。

（3）有联机求助功能。用户能直接从系统得到必要的提示，不查手册也能解决一些疑难。

5．程序具有一定的健壮性，不会因为用户的输入错误引起程序运行错误而中断执行：

（1）对输入值的类型、大小范围、字符串的长度等，进行正确性检查，对不合法的输入值给出出错信息，指出错误类型，等待重新输入。

（2）当可能的回答有多种时，应允许输入任何一种回答。

（3）对删除数据应给出警告。

三、课程设计的内容

课程设计的题目可由教师指定，如可在下列选题中选择，或由教师另外选择，也可由学生自行选择。但选题内容、难度要适当，要有一定的实际意义，并能达到进一步巩固和强化本课程所学知识的效果。

选题1．一元稀疏多项式简单计算器

问题描述：

设计一个一元多项式简单的计算器。

《数据结构与算法》

综合实验报告

系 别：

专 业：

学生姓名：

指导教师：

2011年 11月 25日

实验目的

掌握线性表的建立、插入、删除算法；

掌握查找算法；

掌握排序算法；

实验要求

使用C语言（环境任意）开发程序，能够对用户输入的任意一组数据，建立一个线性表，可以输出此线性表。并且能够对此线性表进行插入、删除、查找、排序等操作。

程序流程

建表如下：

定义一个整型的数据类型data和next指针：

定义头指针和当前结点指针，申请连续空间将单个字节大小复制给头指针，把头指针赋值给当前节点指针：

若输入的数是0，则

若输入不为0，把输入的数赋值给已申请的新结点，把新结点赋给当前节点的next域，再把新结点赋值给当前结点，以此方法重复执行得到如下链表：

输出函数：

把头指针赋值给当前结点指针，当当前节点的next域不为空时输出当前节点所指向的数据，把当前结点的next域赋值给当前节点，否则输出链表为空

对此线性表进行插入、删除、查询、排序操作

把已申请的结点数据域指向所输入的数

再把插入w结点赋值头结点，是插入的位置，如果w=0则插入结点的next域赋值给头结点

否则如果w>表长，则输出超出范围

代码及运行结果（主要语句要求有注释）

#include"stdafx.h" #include #include #define NULL 0 typedef struct linknode { int data; struct linknode *next; }node; node *head; node *creat() { node *currnode,*newnode; int x; head=(node*)malloc(sizeof(node)); currnode=head; do{ scanf("%d",&x); newnode=(node*)malloc(sizeof(node)); newnode->data=x; currnode->next=newnode; currnode=newnode;

国家开放大学《数据结构》课程实验报告

（实验3 栈、队列、递归设计）

学生姓名 学 号

班 级 指导老师

实验名称 实验成绩

实验报告

实

验

概

述 实验目的：

编写一个算法，输出指定栈中的栈底元素，并使得原栈中的元素倒置。

实验要求：

（1）正确理解栈的先进后出的操作特点，建立初始栈，通过相关操作显示栈底元素。

（2）程序中要体现出建栈过程和取出栈底元素后恢复栈的入栈过程，按堆栈的操作规则打印结果栈中的元素。

实验基本原理：

（1）采用顺序栈，即用数组存储栈元素。

（2）设定一个临时队列，用来存放从初始栈中出栈的元素。

（3）取出栈底元素后，将队列中的元素逐一出队并压入初始栈中。

实

验

内

容 程序代码：

/*实验2.1 栈和队列的基本操作*/

#include

#include

#define MaxSize 100

typedef int ElemType;

typedef struct

{

ElemType data[MaxSize];

int top; /*栈顶指针*/

} SeqStack; /*定义顺序栈*/

typedef struct

{

ElemType data[MaxSize];

int front,rear; /*队头和队尾指针*/

} SeqQueue; /*定义顺序队列*/

void InitStack(SeqStack *s); /*初始化栈*/

int StackEmpty(SeqStack *s); /*判栈空*/

int StackFull(SeqStack *s); /*判栈满*/

void Push(SeqStack *s,ElemType x); /*进栈*/

ElemType Pop(SeqStack *s); /*出栈*/