数据结构单元测试1

单元练习7

一．判断题（下列各题，正确的请在前面的括号内打√；错误的打╳ ） （√）（1）树结构中每个结点最多只有一个直接前驱。 （ㄨ）（2）完全二叉树一定是满二查树。 （ㄨ）（3）在中序线索二叉树中，右线索若不为空，则一定指向其双亲。 （√）（4）一棵二叉树中序遍历序列的最后一个结点，必定是该二叉树前序遍历的最后一个结点。 （√）（5）二叉树的前序遍历中，任意一个结点均处于其子女结点的前面。 （√）（6）由二叉树的前序遍历序列和中序遍历序列，可以推导出后序遍历的序列。 （√）（7）在完全二叉树中，若一个结点没有左孩子，则它必然是叶子结点。 （ㄨ）（8）在哈夫曼编码中，当两个字符出现的频率相同，其编码也相同，对于这种情况应该做特殊处理。 （ㄨ）（9）含多于两棵树的森林转换的二叉树，其根结点一定无右孩子。 （√）（10）具有n个叶子结点的哈夫曼树共有2n-1个结点。

二．填空题 （1） 在树中，一个结点所拥有的子树数称为该结点的 度 。 （2） 度为零的结点称为 叶（或叶子，或终端） 结点。 （3） 树中结点的最大层次称为树的 深度（或高度） 。 （4） 对于二叉树来说，第i层上至多有 2i-1 个结

单元练习7

一．判断题（下列各题，正确的请在前面的括号内打√；错误的打╳ ） （√）（1）树结构中每个结点最多只有一个直接前驱。 （ㄨ）（2）完全二叉树一定是满二查树。 （ㄨ）（3）在中序线索二叉树中，右线索若不为空，则一定指向其双亲。 （√）（4）一棵二叉树中序遍历序列的最后一个结点，必定是该二叉树前序遍历的最后一个结点。 （√）（5）二叉树的前序遍历中，任意一个结点均处于其子女结点的前面。 （√）（6）由二叉树的前序遍历序列和中序遍历序列，可以推导出后序遍历的序列。 （√）（7）在完全二叉树中，若一个结点没有左孩子，则它必然是叶子结点。 （ㄨ）（8）在哈夫曼编码中，当两个字符出现的频率相同，其编码也相同，对于这种情况应该做特殊处理。 （ㄨ）（9）含多于两棵树的森林转换的二叉树，其根结点一定无右孩子。 （√）（10）具有n个叶子结点的哈夫曼树共有2n-1个结点。

二．填空题 （1） 在树中，一个结点所拥有的子树数称为该结点的 度 。 （2） 度为零的结点称为 叶（或叶子，或终端） 结点。 （3） 树中结点的最大层次称为树的 深度（或高度） 。 （4） 对于二叉树来说，第i层上至多有 2i-1 个结

第一章 线性表 一 单选题

1 线性表是具有n个____的有限序列。 A) 表元素 B) 字符 C) 数据元素 D) 数据项 E)信息项

**2 线性表的静态链表存储结构与顺序存储结构相比优点是_____。 A) 所有的操作算法实现简单 B) 便于随机存储 C) 便于插入和删除 D) 便于利用零散的存储器空间 3 若长度为n的线性表采用顺序存储结构，在其第i个位置插入一个新元素算法的时间复杂度为____。

2

A) O(n ) B ) O(l) C) O(n) D) O(n)

**4 (1) 静态链表既有顺序存储的优点，又有动态链表的优点。所以，它存取表中第i个元素的时间与i无关; (2) 静态链表中能容纳元素个数的最大数在定义是就确定了,以后不能增加; (3) 静态链表与动态链表在元素的插入,删除上类似,不需做元素的移动. 以上错误的是_____. A) (1),(2) B) (1) C) (1),(2),(3) D) (2) P 5 将图1.10所示的s所指结点加到p所指结点之后,其语句应为____.

A) s?next=p+1; p?next=s; B) (*p).

第一章 线性表 一 单选题

1 线性表是具有n个____的有限序列。 A) 表元素 B) 字符 C) 数据元素 D) 数据项 E)信息项

**2 线性表的静态链表存储结构与顺序存储结构相比优点是_____。 A) 所有的操作算法实现简单 B) 便于随机存储 C) 便于插入和删除 D) 便于利用零散的存储器空间 3 若长度为n的线性表采用顺序存储结构，在其第i个位置插入一个新元素算法的时间复杂度为____。

2

A) O(n ) B ) O(l) C) O(n) D) O(n)

**4 (1) 静态链表既有顺序存储的优点，又有动态链表的优点。所以，它存取表中第i个元素的时间与i无关; (2) 静态链表中能容纳元素个数的最大数在定义是就确定了,以后不能增加; (3) 静态链表与动态链表在元素的插入,删除上类似,不需做元素的移动. 以上错误的是_____. A) (1),(2) B) (1) C) (1),(2),(3) D) (2) P 5 将图1.10所示的s所指结点加到p所指结点之后,其语句应为____.

A) s?next=p+1; p?next=s; B) (*p).

单元练习2

一．判断题（下列各题，正确的请在前面的括号内打√；错误的打╳ ）

（×）（1）线性表的链式存储结构优于顺序存储。 （×）（2）链表的每个结点都恰好包含一个指针域。

（√）（3）在线性表的链式存储结构中，逻辑上相邻的两个元素在物理位置上并不一定紧邻。 （×）（4）顺序存储方式的优点是存储密度大，插入、删除效率高。

（×）（5）线性链表的删除算法简单，因为当删除链中某个结点后，计算机会自动地将后续的各个单元向前移动。

（×）（6）顺序表的每个结点只能是一个简单类型，而链表的每个结点可以是一个复杂类型。 （√）（7）线性表链式存储的特点是可以用一组任意的存储单元存储表中的数据元素。 （√）（8）线性表采用顺序存储，必须占用一片连续的存储单元。

（×）（9）顺序表结构适宜于进行顺序存取，而链表适宜于进行随机存取。

（ㄨ）（10）插入和删除操作是数据结构中最基本的两种操作，所以这两种操作在数组中也经常使用。

二．填空题

（1） 顺序表中逻辑上相邻的元素在物理位置上 必须 相连。 （2） 线性表中结点的集合是有限的，结点间的关系是 一对一 关系。 （3） 顺序表相对于链表的优点是： 节省存储 和随机存取。 （4）

第1章 绪论 一、选择题

1. 算法的计算量的大小称为计算的（ ）。【北京邮电大学2000 二、3 （20/8分）】 A．效率 B. 复杂性 C. 现实性 D. 难度 2. 算法的时间复杂度取决于（ ）【中科院计算所 1998 二、1 （2分）】 A．问题的规模 B. 待处理数据的初态 C. A和B 3.计算机算法指的是（1），它必须具备（2） 这三个特性。

(1) A．计算方法 B. 排序方法 C. 解决问题的步骤序列 D. 调度方法 (2) A．可执行性、可移植性、可扩充性 B. 可执行性、确定性、有穷性

C. 确定性、有穷性、稳定性 D. 易读性、稳定性、安全性 【南京理工大学 1999 一、1（2分） 【武汉交通科技大学 1996 一、1（ 4分）】 4．一个算法应该是（ ）。【中山大学 1998 二、1（2分）】

A．程序 B．问题求解步骤的描述 C．要满足五个

1

一、单项选择题(每小题2分。共30分) 1．链表所具备的特点是( c )。 A．可以随机访问任一结点 B．占用连续的存储空间

C．插入删除元素的操作不需要移动元素结点 D．可以通过下标对链表进行直接访问

2．线性结构中数据元素的位置之间存在( a )的关系。 A．一对一 B．一对多 C．多对多

D。每一个元素都有一个直接前驱和一个直接后继 3．算法的时间复杂度与( c )有关。 A．所使用的计算机 B．与计算机的操作系统 C．与算法本身 D．与数据结构

4．在一个单链表中，p、q分别指向表中两个相邻的结点，且q所指结点是P所指结点的直接后继，现要删除q所指结点，可用的语句是( c )。 A．p=q->next B．p->next=q C．p->next=q->next D．q->next=NULL

5．在一个链队中，假设f和r分别为队头和队尾指针，则删除一个结点的运算为( c )。 A．r=f->next： B．r=r->next： C．f=f一>next；

C 线性表

1. 初始化线性表L InitList(L) 2. 销毁线性表L DestoryList(L) 3. 清空线性表L ClearList(L) 4. 求线性表L的长度 ListLength(L) 5. 判断线性表L是否为空 IsEmpty(L)

6. 获取线性表L中的某个数据元素内容 GetElem(L,i,e) 7. 检索值为e的数据元素 LocateELem(L,e)

8. 在线性表L中插入一个数据元素 ListInsert(L,i,e) 9. 删除线性表L中第i个数据元素 ListDelete(L,i,e)

1. 初始化线性表L InitList(L)

Status InitList_Sq(SqList *L) //构造一个空的顺序表L {

L-> elem=new ElemType[MAXSIZE]; //为顺序表分配空间 if(! L-> elem) exit(OVERFLOW); //存储分配失败 L-> length=0; //空表长度为0

实验1: 顺序表的操作实验

一、实验名称和性质

所属课程 实验名称 实验学时 实验性质 必做/选做 数据结构 顺序表的操作 2 √验证□综合√设计 √必做□选做 二、实验目的

1．掌握线性表的顺序存储结构的表示和实现方法。 2．掌握顺序表基本操作的算法实现。 3．了解顺序表的应用。 三、实验内容 1．建立顺序表。

2．在顺序表上实现插入、删除和查找操作（验证性内容）。 3．删除有序顺序表中的重复元素（设计性内容）。

4．完成一个简单学生成绩管理系统的设计（应用性设计内容）。 四、实验的软硬件环境要求

硬件环境要求：

PC机（单机）

Windows环境下的VC++6.0 使用的软件名称、版本号以及模块： 五、知识准备

前期要求熟练掌握了C语言的编程规则、方法和顺序表的基本操作算法。 六、验证性实验 1．实验要求

编程实现如下功能：

（1）根据输入顺序表的长度n和各个数据元素值建立一个顺序表，并输出顺序表中各元素值，观察输入的内容与输出的内容是否一致。

（2）在顺序表的第i个元素之前插入一个值为x的元素，并输出插入后的顺序表中各元素值。

（3）删除顺序表中第i个元素，并输出删除后的顺序表中各元素值。

（4）在顺序表中查找值为e的数据元素，如

范文 范例 指导 学习

实验1: 顺序表的操作实验

一、实验名称和性质

所属课程 实验名称 实验学时 实验性质 必做/选做 数据结构 顺序表的操作 2 √验证 □综合 √设计 √必做 □选做 二、实验目的

1．掌握线性表的顺序存储结构的表示和实现方法。 2．掌握顺序表基本操作的算法实现。 3．了解顺序表的应用。 三、实验内容 1．建立顺序表。

2．在顺序表上实现插入、删除和查找操作（验证性内容）。 3．删除有序顺序表中的重复元素（设计性内容）。

4．完成一个简单学生成绩管理系统的设计（应用性设计内容）。 四、实验的软硬件环境要求

硬件环境要求：

PC机（单机）

Windows环境下的VC++6.0 使用的软件名称、版本号以及模块： 五、知识准备

前期要求熟练掌握了C语言的编程规则、方法和顺序表的基本操作算法。 六、验证性实验 1．实验要求

编程实现如下功能：

（1）根据输入顺序表的长度n和各个数据元素值建立一个顺序表，并输出顺序表中各元素值，观察输入的内容与输出的内容是否一致。

（2）在顺序表的第i个元素之前插入一个值为x的元素，并输出插入后的顺序表中各元素值。

（3）删除顺序表中第i个元素，并输出删除