郑州大学现代远程教育
《数据结构》课程（本科）
学习指导书
郭纯一一 编
课程内容与基本要求
“数据结构”在计算机科学中是一门综合性的专业基础课。 本课程将主要介 绍数据结构
的基本概念和术语、 非数值计算中常用的数据结构（线性表、栈和队 列、串、树和图）和基本技术（查找和排序方法）三大部分。
本课程要求学生在掌握线性表、栈和队列、串、树和二叉树、图等基本数据
类型的基础上，会分析各种数据结构的特性，会根据应用需求为所涉及的数据合 理选择适当的逻辑结构和存储结构， 并能据此设计实现问题的算法；还应初步掌 握算法的时间和空间效率的分析方法。
课程学习进度与指导 早节 第一早 课程内容 学时分配 学习指导 （均以课件学习为主） 氏U 绪论 4学时 重点掌握基本概念和时间复杂度的计算 方法 重点掌握顺序结构和链式结构表示线性 表的方法和操作的实现；结合具体例子理 解编程实现一个问题的2种方法 重点掌握栈和队列的特点以及它们各自 的存储表第二章* 线性表 10学时 第三章 栈和队列 8学时 2学时 示，尤其是顺序栈和循环队列的 实现；结合具体例子理解栈和队列的应用 重点掌握串的术语、串操作结果和不同存 储结构的特点 重点掌握二叉树的定义、存储、性质、遍 历算法（递归）及应用、线索化；掌握树 和森林与二叉树的转换以及Huffman树和 第四章 串 第七章* 树和二叉树 10学时 Huffman编码的构造方法 重点掌握图的术语、存储、遍历算法及应 用；掌第八章 图 8学时 握最小生成树的2种构造方法及特 点、会求拓扑排序序列和单源取短路径 重点掌握各种动态查找表的构造过程、性 能分第九章* 查找 8学时 析、插入/删除方法；掌握静态查找 表的顺序、折半和分块查找及ASL求法 掌握关于排序的术语及分类方法；重点掌 握插入第十章* 排序 8学时 排序、交换排序、选择排序等内排 序方法及其性能分析方法 第一章
一、 章节学习目标与要求
绪论
欢迎下载 2
1、 理解数据抽象和信息隐蔽原则
2、 掌握所有的基本概念和术语、掌握时间复杂度的计算方法、会用
抽象数据类型和算法；能够熟练使用 C语言编写程序
二、 本章重点、难点
C语言描述
重点：基本概念和术语，C语言描述算法的方式，简单程序的时间复杂度的求法。 难点：时间复杂度的计算方法和原则。
三章节练习
、(
一
-)选择题： 1. 具有线性结构的数据结构是
。
A.图 B. 树 C. 集合 D.
栈
2.
计算机算法疋扌曰
。
A.计算方法和运算结果
B.
调度方法
C.解决某一问题的有限运算系列 D.
排序方法 3. 线性结构中，最后一个结点有
个后继结点。
A. 0 B. 1 C. 任意多
4. 算法分析的目的是
。
A.找出数据结构的合理性
B.
研究算法中输入和输出的关系
C.分析算法的效率以求改进 D. 分析算法的可读性和可行性
5. 具有非线性结构的数据结构是
。
A.图 B.
线性表 C. 串
D. 栈
6. 算法具有5个特性：
、
、
、输入和输出
A.稳定性、确定性、可行性
B, 有穷性、确定性、可行性
.
C.有穷性、安全性、可行性
D .
有穷性、确定性、可移植性
7?设n为正整数。则下面程序段的时间复杂度为 _________________ _
i=1; k=0;
while(i<=n-1){
@ k+=10*i;
i++；
}
欢迎下载 3
A.0(1) B. 0(n) C. 0( nlogn) D. O(n
2
)
8?设n为正整数。则下面程序段的时间复杂度为 _________________ 。
k=0;
for(i=1;i<=n ;i++){ for(j=i;j<=n ;j++) @ k++; }
A.0(1) B. 0(n) C. 0( nlogn) D. 0(n
(二) 判断题：
2
)
1 ?在数据结构中，从逻辑上可以把数据结构分为动态结构和静态结构两大类。 2.
结构， 存储结构。
()
()
任何一个算法的设计取决于数据的逻辑而算法的实现则依赖于所采用的
3. 数据元素是数据的不可分割的最小单位。
4. 算法分析的两个主要方面是时间复杂度和空间复杂度。
第二章
一、 章节学习目标与要求
线性表
() ()
1、 理解线性表的逻辑结构特性、顺序表和链表表示线性表的优缺点、循环链表 和双向链表的
特点。
2、 掌握线性表的两种存储方式及其实现：熟练掌握顺序表和链表的创建、插入 元素、删除元
素以及定位等常用操作的实现算法并会求相应算法的时间复杂度。 二、 本章重点、难点
重点：线性表的特点、两种表示方式及它们的运算实现，会求算法的时间复杂度。 难点：单链表结构、特点及其实现 三、 章节练习 (一) 选择题：
1. ___________________ 顺序表是一种 ______________________ 的存储结构，单链表是
___________________________ 的存储结构。
A.顺序存取 B. 随机存取 C.
索引存取
欢迎下载 4
2?顺序表中第一个元素的起始存储地址为 100，每个元素的长度为4,则第五个
元素的起始地址是 ___________ 。
A. 105 B. 110 C. 116 D. 120
3 .非空循环单链表（head为头指针）的尾结点（由指针p所指示）应满足 ____________ 。
A. p->n ext==NULL; B. p==NULL; C. p->n ext==head; D. p==head; 4.
表的任何位置上插入元素的概率是相等的，那么在长度为
表中插入一个元素时需平均移动 _______________ 元素。
若在线性
n的顺序
A. n B. （n-1）/2 C. n/2 D. （n+1）/2
5. _______________________________________________ 在带头结点的非空单链
表中，头结点的位置由 ________________________________________ 旨示，首元结点的存 储位置由 __________ 指示，除首元结点外，其它任一元素结点的存储位置由 _________旨示。
A.头指针 B.
头结点的指针域的指针
C.前驱结点的指针域的指针
6. 单链表的头指针为p，若有头结点，则表空的判断条件是 __________________________ ;
若不带头结点，则表空的判断条件是 ______________________ 。
A. p==NULL B. p->n ext==NULL C. p-> next-> next==NULL
（二） 判断题：
1.
单链表中插入或删除元素时是以结点的指针变化来反映逻辑关系的变化， 此不需要移动元素。
（）
在因
2. 顺序表能够以元素在计算机内的物理位置的相邻性来表示线性表中元素之间
的逻辑关系。
（）
3. 在不带头结点的非空单链表中，首元结点的存储位置由头指针指示，除首元结
点外，其它任一元素结点的存储位置由前驱结点的指针域的指针指示。 （三） 问答题：
（）
欢迎下载 5
郑州大学远程教育学院数据结构试题及答案
