第一部分试题说明。
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...