数据结构复习提纲

发布 2021-05-29 19:07:28 阅读 1647

第一部分试题说明。

1、试卷考试时间为90分钟。

2、试题类型:选择题(20个,每题2分,共40分)、简答题(6个,每题5分,共30分)和算法设计题(2个,每题15分,共30分)。

第二部分各章知识点。

第1章绪论。

1、 数据结构的概念。

2、 数据结构的形式化表示方法:ds=(d,r),要求给定一个形式化表示,能够画出该数据结构的拓扑图。

3、 数据的逻辑结构和存储结构(物理结构)的定义。

4、 抽象数据类型的概念。

5、 算法的概念及其5个特点。

6、 语句频度的计算。

第2章线性表。

1、 线性表的概念和特点。

2、 顺序表的存储特点和基本操作。

3、 链表的存储特点和基本操作。

4、 几个典型算法:1)有序表的合并。2)顺序表的就地逆置。3)链表的就地逆置。

5、 习题集讲过的“基础知识题”

第3章栈和队列。

1、栈的概念和特点。

2、顺序栈的定义和表示。

3、队列的基本概念和特点。

4、循环队列(顺序队列)的几个特殊状态的判断条件:队列满、队列空、如何求得队列中元素的个数。

5、几个典型算法:1)进制转换。2)括号匹配的判定。3)回文的判定。

6、 习题集讲过的“基础知识题”

第4章串。1、串的各种基本概念。如串、字串、串的长度、字串在主串中的位置等。

2、串的基本操作。

3、几个典型算法:1)串的模式匹配算法。2)串在堆分配存储表示下的串比较和串连接操作。

4、习题集讲过的“基础知识题”

第6章树。1、树的各种基本概念。

2、二叉树的概念和5条基本性质。

3、二叉树的顺序和二叉链表存储结构的定义。

4、二叉树的遍历算法。

5、树和森林的表示,以及它们和二叉树的转换方法(6.4节)。

6、哈夫曼树的定义和构造方法。要求对给定的一个权值集合w,能够构造出相应的哈夫曼树。

7、几个典型算法:1)二叉树的三种(先序、中序和后序)遍历算法。2)二叉树的层次遍历算法(课堂上没讲,自己查阅资料并编写)。

3)用递归方法求二叉树中的叶子结点的个数(课堂上没讲,自己查阅资料并编写)。

8、习题集讲过的“基础知识题”。

数据结构复习提纲

软件学院数据结构与算法复习提纲。data structures and algorithms 概念 type,类型 一组值的集合。type,简单类型例如整数,因为它的值不含有子结构。aggregate type,复杂类型,一个记录含有多项信息。银行账户含有多项信息如姓名 地址 composite t...

数据结构复习提纲

第一章概论 1 数据结构的基本概念和术语。数据 数据元素 数据项 数据对象 数据结构等基本概念。数据结构的逻辑结构,存储结构及数据运算的含义及其相互关系。数据结构的四种逻辑结构及四种常用的存储表示方法。第二章算法分析技术。1 算法的描述和分析。无穷大阶的几种描述方法的区别。算法 算法的时间复杂度和空...

数据结构复习提纲

概述。1 数据结构定义 本质。2 数据结构三要素。3 顺序存储方式和链式存储方式优缺点。4 数据结构按关系分类 线性结构 非线性结构 集合结构。5 时间复杂度估计 讲过的例题 线性表。1 顺序栈 特点lifo 存储定义 基本操作 入栈 出栈 入栈时需判栈是否为满 出栈时需判栈是否为空 入栈出栈时to...