郑州大学现代远程教育
《数据结构》课程(本科)
学习指导书
郭纯一编
⏹课程内容与基本要求
“数据结构”在计算机科学中就是一门综合性的专业基础课。本课程将主要介绍数据结构的基本概念与术语、非数值计算中常用的数据结构(线性表、栈与队列、串、树与图)与基本技术(查找与排序方法)三大部分。
本课程要求学生在掌握线性表、栈与队列、串、树与二叉树、图等基本数据类型的基础上,会分析各种数据结构的特性,会根据应用需求为所涉及的数据合理选择适当的逻辑结构与存储结构,并能据此设计实现问题的算法;还应初步掌握算法的时间与空间效率的分析方法。
⏹课程学习进度与指导
第一章绪论
一、章节学习目标与要求
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++;
}
A、O(1)
B、 O(n)
C、 O(nlogn)
D、 O(n2)
8.设n为正整数。则下面程序段的时间复杂度为________。
k=0;
for(i=1;i<=n;i++){
for(j=i;j<=n;j++) @ k++;
}
A、O(1)
B、 O(n)
C、 O(nlogn)
D、 O(n2)
(二)判断题:
1.在数据结构中,从逻辑上可以把数据结构分为动态结构与静态结构两大类。( )
2.任何一个算法的设计取决于数据的逻辑结构,而算法的实现则依赖于所采用的存储结构。 ( )
3、数据元素就是数据的不可分割的最小单位。 ( )
4、算法分析的两个主要方面就是时间复杂度与空间复杂度。 ( )
第二章线性表
一、章节学习目标与要求
1、理解线性表的逻辑结构特性、顺序表与链表表示线性表的优缺点、循环链表与双向链表的特点。
2、掌握线性表的两种存储方式及其实现:熟练掌握顺序表与链表的创建、插入元素、删除元素以及定位等常用操作的实现算法并会求相应算法的时间复杂度。
二、本章重点、难点
重点:线性表的特点、两种表示方式及它们的运算实现,会求算法的时间复杂度。难点:单链表结构、特点及其实现
三、章节练习
(一)选择题:
1.顺序表就是一种________的存储结构,单链表就是________的存储结构。
A、顺序存取
B、随机存取
C、索引存取
2.顺序表中第一个元素的起始存储地址为100,每个元素的长度为4,则第五个元
素的起始地址就是_______。
A、 105
B、 110
C、 116
D、 120
3.非空循环单链表(head为头指针)的尾结点(由指针p所指示)应满足________。
A、 p->next==NULL;
B、 p==NULL;
C、 p->next==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->next==NULL
C、 p->next->next==NULL
(二)判断题:
1.在单链表中插入或删除元素时就是以结点的指针变化来反映逻辑关系的变化,因此不需要移动元素。 ( )
2. 顺序表能够以元素在计算机内的物理位置的相邻性来表示线性表中元素之间的逻辑关系。 ( )
3、在不带头结点的非空单链表中,首元结点的存储位置由头指针指示,除首元结点外,其它任一元素结点的存储位置由前驱结点的指针域的指针指示。 ( )
(三)问答题:
1.若线性表要求以最快的速度存取而表中元素变动不大,则应采取什么存储结构(顺序或链式结构)？为什么？
2.若线性表经常做插入/删除操作,则应采取什么存储结构？为什么？
3、在单链表中设置头结点有什么作用？
(四)算法题:
1、设带头结点的单链表(L为头指针)中的数据元素递增有序。设计算法,将x插
