郑州大学现代远程教育《数据结构》课程(本科)学习指导书郭纯一编⏹课程内容与基本要求“数据结构”在计算机科学中就是一门综合性的专业基础课。
本课程将主要介绍数据结构的基本概念与术语、非数值计算中常用的数据结构(线性表、栈与队列、串、树与图)与基本技术(查找与排序方法)三大部分。
本课程要求学生在掌握线性表、栈与队列、串、树与二叉树、图等基本数据类型的基础上,会分析各种数据结构的特性,会根据应用需求为所涉及的数据合理选择适当的逻辑结构与存储结构,并能据此设计实现问题的算法;还应初步掌握算法的时间与空间效率的分析方法。
⏹课程学习进度与指导第一章绪论一、章节学习目标与要求1、理解数据抽象与信息隐蔽原则2、掌握所有的基本概念与术语、掌握时间复杂度的计算方法、会用C语言描述抽象数据类型与算法;能够熟练使用C语言编写程序二、本章重点、难点重点:基本概念与术语,C语言描述算法的方式,简单程序的时间复杂度的求法。
难点:时间复杂度的计算方法与原则。
三、章节练习(一)选择题:1．具有线性结构的数据结构就是__________。
A、图B、树C、集合D、栈2. 计算机算法就是指________。
A、计算方法与运算结果B、调度方法C、解决某一问题的有限运算系列D、排序方法3．线性结构中,最后一个结点有________个后继结点。
A、 0B、 1C、任意多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、 105B、 110C、 116D、 1203.非空循环单链表(head为头指针)的尾结点(由指针p所指示)应满足________。
A、 p->next==NULL;B、 p==NULL;C、 p->next==head;D、 p==head;4.若在线性表的任何位置上插入元素的概率就是相等的,那么在长度为n的顺序表中插入一个元素时需平均移动________个元素。
A、 nB、 (n-1)/2C、n/2D、 (n+1)/25.在带头结点的非空单链表中,头结点的位置由________指示,首元结点的存储位置由________指示,除首元结点外,其它任一元素结点的存储位置由________指示。
A、头指针B、头结点的指针域的指针C、前驱结点的指针域的指针6、单链表的头指针为p,若有头结点,则表空的判断条件就是______________;若不带头结点,则表空的判断条件就是______________。
A、 p==NULLB、 p->next==NULLC、 p->next->next==NULL(二)判断题:1.在单链表中插入或删除元素时就是以结点的指针变化来反映逻辑关系的变化,因此不需要移动元素。
( )2. 顺序表能够以元素在计算机内的物理位置的相邻性来表示线性表中元素之间的逻辑关系。
( )3、在不带头结点的非空单链表中,首元结点的存储位置由头指针指示,除首元结点外,其它任一元素结点的存储位置由前驱结点的指针域的指针指示。
( )(三)问答题:1.若线性表要求以最快的速度存取而表中元素变动不大,则应采取什么存储结构(顺序或链式结构)？为什么？2.若线性表经常做插入/删除操作,则应采取什么存储结构？为什么？3、在单链表中设置头结点有什么作用？(四)算法题:1、设带头结点的单链表(L为头指针)中的数据元素递增有序。
设计算法,将x插入到链表的适当位置上,并仍保持该表的有序性。
2、设顺序表va中的数据元素递增有序。
设计算法,将x插入到顺序表的适当位置上,并仍保持该表的有序性。
3、设计算法,实现单链表的就地逆置,即利用原表的存储空间将线性表(a1,a2,…,an)逆置为(an,an-1,…,a1)。
第三章栈与队列一、章节学习目标与要求1、理解用栈与队列解决实际问题的方法。
2、掌握栈与队列的定义以及特性、它们的2种不同的存储表示方法(特别就是顺序栈与循环队列)以及各种常见操作(如入、出操作)在不同表示方式上的实现。
二、本章重点、难点重点:栈与队列的定义、各种表示与实现方法,加深对线性结构的理解难点:循环队列的表示及为解决循环队列队空、队满判断条件相同而使用的不同实现方式;能在具体问题中灵活运用栈与队列结构。
三、章节练习(一)选择题:1.一个栈的入栈序列就是a,b,c,d,e,则栈的不可能的输出序列就是________。
A、 edcbaB、decbaC、dceabD、abcde2.栈与队列的共同点就是_______。
A、都就是后进先出B、都就是先进先出C、都就是只允许在端点处插入与删除元素D、无共同点3.一个队列的入队序列就是{1,2,3,4},则队列的输出序列就是______。
A、 {4321}B、 {1234}C、 {1432}D、 {3241}4.栈的入栈序列就是1,2,…,n,输出序列为p1,p2,…pn,若p1=n, 则pi为_____。
A、 iB、 n-iC、 n-i+1D、不确定5.队列就是限定在________进行插入,在________进行删除的线性表。
A、队头B、队尾C、任意位置6.循环队列中,设队列元素依次存放在Q[0、、m]中,f、r分别指示队头元素位置与队尾元素的下一个位置,约定存储m个元素时为队满。
则队列空的判定方法就是_______,队列满的判定方法就是_______。
A、f==rB、 (f+1)%(m+1)==rC、 (r+1)%(m+1)==fD、 (r+1)% m==f(二)判断题:1.若用户无法估计所用队列的最大长度,则最好采用链队列。
( )2.在链队列上删除队头元素时,只需修改头结点中的指针,不必修改尾指针。
( )3、栈就是限定仅在栈顶进行插入或删除操作的线性表。
( )4、队列就是限定在队尾插入元素,在队头删除元素的线性表。
( )(三)问答与算法题:1.对于一个栈,若输入序列依次为{A,B,C}, 试给出所有可能的输出序列。
2.假设将循环队列定义为:以整型域变量front与length分别指示循环队列中队头元素位置与队列中元素个数,指针elem指示存放队列元素的连续空间的首地址,写出相应的入队列与出队列的算法。
第四章串一、章节学习目标与要求1、理解串的抽象数据类型的定义以及相关术语、理解串在文本编辑中的作用。
2、掌握字符串的定义及各种基本操作的运算结果以及串的各种存储表示的特点。
二、本章重点、难点重点:串的基本运算、串的各种存储表示与特点。
继续加深对线性结构的理解难点:串的不同存储结构,区分它们与高级语言中串的存储方式的不同。
三、章节练习(一)选择题:1.设串s="I AM A STUDENT", 则其串长就是______。
A、 13B、 14C、 15D、 162、设s ="HE IS A WORKER",t="WORKER"。
则StrIndex(s,t,5)的返回值就是_____。
A、 4B、 5C、 6D、 9E、 103、串就是一种特殊的线性表,其特殊性体现在_____。
A、可以顺序存储B、数据元素就是一个字符C、可以链接存储D、数据元素可以就是多个字符4、已知串s="ABCDEFGH’,则s的所有不同子串的个数为________。
A、 8B、 9C、 36D、 375、设串s="I am a teacher、’,则s的第8个字符起、长度为7的子串为_______。
A、 "teacher、 "B、 "teacher"C、 "a teacher"D、 " teacher"6、设串s="student、",t=“good ",则执行StrInsert(s,1,t)后,s为____。
A、 "good student、"B、 "good student"C、 "goodstudent"D、 " good teacher"(二)判断题:1.空串与空格串就是相同的。
( )2、如果两个串含有相同的字符,则它们就是相同的。
( )3、串的基本操作与线性表的一样,都就是以“单个元素”作为操作对象的。
( )4、在串的链式存储结构中,结点大小与存储密度之间没有关系。
( )第七章树与二叉树一、章节学习目标与要求1、理解树、二叉树与森林的概念,理解线索化二叉树的特性、创建方法及在线索二叉树上寻找某结点的前驱与后继的方法;理解树与森林的存储方法。