2023年云南广播电视大学职业技术学院五高职教育第一学期数据结构期末复习指导

云南广播电视大学职业技术学院五年制高职教育

2023—2023学年度第一学期

计算机应用专业2023、2023级第七、五学期

《数据结构》期末复习指导

责任教师伍嘉

一、期末复习的基本规定：

本课程期末复习的总规定为：

理解：数据、数据元素、数据对象、数据结构算法的时间量度等基本概念；线性表、单向链表的基本概念

及其特点;单链表中插入或删除•个元素的基本操作;栈的概念；顺序栈的特点；队列的基本运算；链接方

式存储队列的删除运算;二叉树的概念及特点。

掌握:顺序存储结构和链式存储结构的优缺陷；单向链表中附加一个头结点的作用；线性表的链示存储结

构；栈和队列的区别等。

纯熟掌握:顺序表（有序）插入元素的算法；先序、中序、后序、遍历二叉树。

二、命题原则及题型：

1.命题原则：考试立足于主教材及学习指导手册，各章节教学规定中的纯熟掌握部分为重点考核内容，掌

握部分为重要考核内容，了解部分的内容占的比例较少或不作考试内容。

2.题型及题量：填空题（20空，20分）、单选题（10题，30分）、简答题（5题,30分）、算法题（2题，

20分）。

三、各章复习要点：

第一章绪论

理解:数据、数据元素、数据对象、数据结构算法的时间量度等基本概念。

第二章线性表

理解：线性表、单向链表的基本概念及其特点;单链表中插入或删除一个元素的基本操作。

掌握：顺序存储结构和链式存储结构的优缺陷；单向链表中附加一个头结点的作用；线性表的顺序存储结

构；线性表的链示存储结构等。

纯熟掌握：顺序表（有序）插入元素的算法。

第三章栈和队列

理解:栈和队列的概念;顺序栈的特点;队列的基本运算；链接方式存储队列的删除运算。

掌握:栈和队列的区别等。

第六章树

理解：二叉树的概念及特点。

纯熟掌握：先序、中序、后序、遍历二叉树。

第八章查找

理解：二分法查找。

纯熟掌握:顺序查找的函数算法;折半查找的函数算法。

第九章排序

纯熟掌握：直接插入排序、冒泡排序、快速排序的原理。

四、期末复习题

一、填空题

1、数据是描述客观事物的、以及所有能输入到计算机中并

被计算机解决的的总称。

2、是数据的基本单位,在计算机中通常作为一个整体进行考虑和解决。

3数据对象

是是数据的

一个子集。

4、线性表是指个具有相同类型数据元素（或称结点）的有限序列，可表达为（al,

a2,•ai,•,an）»其中，ai代表,（al称为表头

（或）,an称为表尾（或）,a（OWi〈n）称为ai+1

的,ai+1称为ai

的

称为线性表的长度,长度为的线性表称为空表,记为

5、算法的时间量度记作,表达随着的增大，算法执行时

间的增长率和的增长率相同，称做,简称时间复杂

度。

6、为表达相邻数据元素之间的逻辑关系，将每个存储结点分为两个域:用来存放•个数

据元素的自身信息:用来存放该数据元素直接后继的存储位置。这样，可以通

过中存放的信息（称为）将n个结点连接成一个链表,即成为线

性表的链式存储结构。由于这种存储结构中每个结点只有一个指针域，故又将其称

为或

7、若S为一栈，则为空栈,意为满

栈。为栈底元素,为栈顶元素。

二、单选题

1、以下数据结构中（）是一个线性结构。

A.有向图B.栈

C.线索二叉树D.B树

2、在一个单链表中，若要向表中第i个结点前(用p指向i的前一结点)插入一个由指针s指向的结点,

则执行()o

A.s—>next=p：p->next=s;

B.s->next=p->next；p->next=s；

C.p—>next=s;p=s->next;

D.p->next=s->next;s->next=p;

3、在一个单链表中，若要删除表中第i个数据结点（用p指向i的前一结点），则执行（）o

A.p->next=p;

B.p—>next=p—>next->next;

C.p->next=s；p=s->next；

D.p->next=s->next;s->next=p;

4、()是顺序存储方式的优点。

A.存储密度大B.插入运算方便

C.删除运算方便D.以上所有

5、()不是队列的基本运算。

A.从队尾插入一个新元素B.从队列中删除第i个元素

C.判断一个队列是否为空D.读取队头元素的值

三、简答题

1、试对栈和队列进行比较

2、单向链表中附加一个头结点的作用。

3、假定一棵二叉树如图所示，分别写出对它进行先序、中序、后序、遍历的结果。

4、