下载文档原格式
数据结构-c语言描述高等教育出版社耿国华第1章绪论习题一、问答题1. 什么是数据结构？2. 四类基本数据结构的名称与含义。
3. 算法的定义与特性。
4. 算法的时间复杂度。
5. 数据类型的概念。
6. 线性结构与非线性结构的差别。
7. 面向对象程序设计语言的特点。
8. 在面向对象程序设计中，类的作用是什么？9. 参数传递的主要方式及特点。
10. 抽象数据类型的概念。
二、判断题1. 线性结构只能用顺序结构来存放，非线性结构只能用非顺序结构来存放。
2. 算法就是程序。
3. 在高级语言（如C、或PASCAL）中，指针类型是原子类型。
三、计算下列程序段中X=X+1的语句频度for(i=1;i<=n;i++)for(j=1;j<=i;j++)for(k=1;k<=j;k++)x=x+1;[提示]：i=1时：1 = (1+1)×1/2 = (1+12)/2i=2时：1+2 = (1+2)×2/2 = (2+22)/2i=3时：1+2+3 = (1+3)×3/2 = (3+32)/2…i=n时：1+2+3+……+n = (1+n)×n/2 = (n+n2)/2f(n) = [ (1+2+3+……+n) + (12 + 22 + 32 + …… + n2 ) ] / 2 =[ (1+n)n/2 + n(n+1)(2n+1)/6 ] / 2=n(n+1)(n+2)/6=n3/6+n2/2+n/3区分语句频度和算法复杂度：O(f(n)) = O(n3)四、试编写算法求一元多项式Pn(x)=a0+a1x+a2x2+a3x3+…a n x n的值P n(x0)，并确定算法中的每一语句的执行次数和整个算法的时间复杂度，要求时间复杂度尽可能的小，规定算法中不能使用求幂函数。
注意：本题中的输入a i(i=0,1,…,n), x和n，输出为P n(x0).通常算法的输入和输出可采用下列两种方式之一：（1）通过参数表中的参数显式传递；（2）通过全局变量隐式传递。
第一章三、计算下列程序段中X=X+1 的语句频度for(i=1;i<=n;i++)for(j=1;j<=i;j++)for(k=1;k<=j;k++)x=x+1;[提示]：i=1 时： 1 = (1+1)×1/2 = (1+1 )/2i=2 时：1+2 = (1+2)×2/2 = (2+22)/2i=3 时：1+2+3 = (1+3)×3/2 = (3+32)/2…i=n时：1+2+3+……+n = (1+n)×n/2 = (n+n )/2f(n) = [ (1+2+3+……+n) + (1 + 2 + 3 + …… + n ) ] / 2=[ (1+n)×n/2 + n(n+1)(2n+1)/6 ] / 2=n(n+1)(n+2)/6=n /6+n /2+n/3区分语句频度和算法复杂度：O(f(n)) = O(n )四、试编写算法求一元多项式Pn(x)=a +a x+a x +a x +…a x 的值P (x )，并确定算法中的每一语句的执行次数和整个算法的时间复杂度，要求时间复杂度尽可能的小，规定算法中不能使用求幂函数。
注意：本题中的输入a (i=0,1,…,n), x和n，输出为P (x ).通常算法的输入和输出可采用下列两种方式之一：（1）通过参数表中的参数显式传递；（2 ）通过全局变量隐式传递。
试讨论这两种方法的优缺点，并在本题算法中以你认为较好的一种方式实现输入和输出。
[提示]：float PolyValue(float a[ ], float x, int n) {……}核心语句：p=1; (x 的零次幂)s=0;i 从0 到n 循环s=s+a[i]*p;p=p*x;或：p=x; (x 的一次幂)s=a[0];i 从1 到n 循环s=s+a[i]*p;p=p*x;第二章2.1 描述以下三个概念的区别：头指针，头结点，首元素结点。
第一章习题答案2、××√3、（1）包含改变量定义的最小范围（2）数据抽象、信息隐蔽（3）数据对象、对象间的关系、一组处理数据的操作（4）指针类型（5）集合结构、线性结构、树形结构、图状结构（6）顺序存储、非顺序存储（7）一对一、一对多、多对多（8）一系列的操作（9）有限性、输入、可行性4、（1）A（2）C（3）C5、语句频度为1+（1+2）+（1+2+3）+…+（1+2+3+…+n）第二章习题答案1、（1）一半，插入、删除的位置（2）顺序和链式，显示，隐式（3）一定，不一定（4）头指针，头结点的指针域，其前驱的指针域2、（1）A（2）A：E、AB：H、L、I、E、AC：F、MD：L、J、A、G或J、A、G（3）D（4）D（5）C（6）A、C3、头指针：指向整个链表首地址的指针，标示着整个单链表的开始。
头结点：为了操作方便，可以在单链表的第一个结点之前附设一个结点，该结点的数据域可以存储一些关于线性表长度的附加信息，也可以什么都不存。
首元素结点：线性表中的第一个结点成为首元素结点。
4、算法如下：int Linser(SeqList *L,int X){ int i=0,k;if(L->last>=MAXSIZE-1){ printf(“表已满无法插入”)；return(0);}while(i<=L->last&&L->elem[i]<X)i++;for(k=L->last;k>=I;k--)L->elem[k+1]=L->elem[k];L->elem[i]=X;L->last++;return(1);}5、算法如下：#define OK 1#define ERROR 0Int LDel(Seqlist *L,int i,int k){ int j;if(i<1||(i+k)>(L->last+2)){ printf(“输入的i，k值不合法”);return ERROR;}if((i+k)==(L->last+2)){ L->last=i-2;ruturn OK;}else{for(j=i+k-1;j<=L->last;j++)elem[j-k]=elem[j];L->last=L->last-k;return OK;}}6、算法如下：#define OK 1#define ERROR 0Int Delet(LInkList L,int mink,int maxk){ Node *p,*q;p=L;while(p->next!=NULL)p=p->next;if(mink<maxk||(L->next->data>=mink)||(p->data<=maxk)){ printf(“参数不合法”);return ERROR;}else{ p=L;while(p->next-data<=mink)p=p->next;while(q->data<maxk){ p->next=q->next;free(q);q=p->next;}return OK;}}9、算法如下：int Dele(Node *S){ Node *p;P=s->next;If(p= =s){printf(“只有一个结点，不删除”)；return 0;}else{if((p->next= =s){s->next=s;free(p);return 1;}Else{ while(p->next->next!=s)P=p->next;P->next=s;Free(p); return 1;}}}第三章习题答案2、（1）3、栈有顺序栈和链栈两种存储结构。
西安文理学院精品课《数据结构》教案计算机科学系韩利凯《数据结构》第一章绪论[教学目标]掌握数据结构的定义、内容、方法、描述、评价。
[重点、难点]数据结构的研究范围，研究采用的方法，算法规则描述的工具，对算法作性能评价。
[教学方法]用多媒体课件（ ppt ）以及与生活实例相结合等方法讲授，这样便于描述相关概念及学生记笔记，加深他们的印象，使基础知识掌握地比较牢固。
[学习要点]1. 熟悉各名词、术语的含义，掌握基本概念，特别是数据的逻辑结构和存储结构之间的关系。
分清哪些是逻辑结构的性质，哪些是存储结构的性质。
2. 了解抽象数据类型的定义、表示和实现方法。
3．理解算法五个要素的确切含义：①动态有穷性（能执行结束）；②确定性（对于相同的输入执行相同的路径）；③有输入；④有输出；⑤可行性（用以描述算法的操作都是足够基本的）。
4．掌握计算语句频度和估算算法时间复杂度的方法。
1.1 什么是数据结构（定义）首先介绍数据结构的相关名词。
1.数据（Data）数据是描述客观事物的数值、字符以及能输入机器且能被处理的各种符号集合。
2.数据元素（Data Element）数据元素是组成数据的基本单位 ,是数据集合的个体，在计算机中通常作为一个整体进行考虑和处理。
例如：学生登记表是数据，每一个学生的记录就是一个数据元素。
3.数据对象（Data Object）数据对象是性质相同的数据元素的集合，是数据的一个子集。
4.数据结构（DA TA Structure）数据结构是指相互之间存在一种或多种特定关系的数据元素集合，是带有结构的数据元素的集合，它指的是数据元素之间的相互关系，即数据的组织形式。
5.数据类型(Data Type)数据类型是一组性质相同的值集合以及定义在这个值集合上的一组操作的总称。
6.数据抽象与抽象数据类型１）数据的抽象高级语言中提供整型、实型、字符、记录、文件、指针等多种数据类型，可以利用这些类型构造出象栈、队列、树、图等复杂的抽象数据类型。
２）抽象数据类型(Abstract Data Type)抽象数据类型（简称ADT）是指基于一类逻辑关系的数据类型以及定义在这个类型之上的一组操作。
抽象数据类型是近年来计算机科学中提出的最重要的概念之一，它集中体现了程序设计中一些最基本的原则：分解、抽象和信息隐藏。
一个抽象数据类型确定了一个模型，但将模型的实现细节隐藏起来；它定义了一组运算，但将运算的实现过程隐藏起来。
用抽象数据类型的概念来指导问题求解的过程，可以用图1.4来表示：数据结构是基础，抽象数据类型是中枢。
1.2 数据结构的内容数据结构的内容可归纳为三个部分。
逻辑结构、存储结构、运算集合。
数据结构是一门主要研究怎样合理地组织数据、建立合适的数据结构、提高计算机执行程序所用的时空效率的学科。
1.3 算法1．算法（Algorithm）定义算法是规则的有限集合，是为解决特定问题而规定的一系列操作。
2．算法的特性⑴有限性有限步骤之内正常结束，不能形成无穷循环。
⑵确定性算法中的每一个步骤必须有确定含义，无二义性得以实现。
⑶输入有多个或0个输入⑷输出至少有一个或多个输出。
⑸可行性原则上能精确进行，操作可通过已实现基本运算执行有限次而完成。
在算法的五大特性中，最基本的是有限性、确定性、可行性。
3．算法设计的要求一般应该具有以下几个基本特征：１）算法的正确性2)可读性3）健壮性4）高效率和低存储量1.4 算法描述的工具1．算法、语言、程序的关系先分析数据结构中算法、语言、程序的关系：⑴算法：描述了数据对象的元素之间的关系（包括数据逻辑关系、存贮关系描述）。
⑵描述算法的工具：（自然语言、框图或高级程序设计语言）⑶程序是算法在计算机中的实现（与所用计算机及所用语言有关）2．设计实现算法过程步骤：●找出与求解有关的数据元素之间的关系（建立结构关系）●确定在某一数据对象上所施加运算●考虑数据元素的存储表示●选择描述算法的语言●设计实现求解的算法，并用程序语言加以描述。
3．类描述算法的语言选择采用了标准C语言作为算法描述的工具。
1.5 对算法作性能评价1．性能评价对问题规模与该算法在运行时所占的空间S与所耗费的时间T给出一个数量关系的评价。
2．有关数量关系计算数量关系评价体现在时间——算法编程后在机器中所耗费时间。
数量关系评价体现在空间——算法编程后在机器中所占存储量。
1）关于算法执行时间一个算法的执行时间大致上等于其所有语句执行时间的总和，对于语句的执行时间是指该条语句的执行次数和执行一次所需时间的乘积。
2）语句频度语句频度是指该语句在一个算法中重复执行的次数。
3）算法的时间复杂度:所谓算法的时间复杂度，即是算法的时间量度记做：T(n)=O(f(n))它表示随问题规模n的增大算法的执行时间的增长率和f(n)的增长率相同，称作算法的渐进时间复杂度，简称时间复杂度。
4）数据结构中常用的时间复杂度频率计数数据结构中常用的时间复杂度频率计数有7个：O(1) 常数型 O(n)线性型 O(n2)平方型 O(n3)立方型O(2n)指数型 O(log2n)对数型 O(nlog2n)二维型5）最坏时间复杂度算法中基本操作重复执行的次数还随问题的输入数据集的不同而不同。
6）算法的空间复杂度关于算法的存储空间需求，类似于算法的时间复杂度，我们采用空间复杂度作为算法所需存储空间的量度，记做：S(n)=O(f (n))1.6 关于学习数据结构1．数据结构课程地位数据结构发展趋势包括两个方面：一是面向专门领域中特殊问题的数据结构的研究和发展，如图形数据结构、知识数据结构、空间数据结构，另一方面，从抽象数据类型的角度，用面向对象观点来讨论数据结构，已成为新的发展趋势。
2．数据结构课程学习特点《数据结构》课程教学目标要求学生学会分析数据对象特征，掌握数据组织方法和计算机的表示方法，以便为应用所涉及数据选择适当的逻辑结构、存储结构及相应算法，初步掌握算法时间空间分析的技巧，培养良好的程序设计技能。
第2章线性表[教学目标]线性结构是一种最基本的数据结构,熟练掌握其逻辑结构、存储结构各种运算。
[重点、难点]链表结构，重点掌握单链表、循环链表、双向链表，初步掌握静态链表。
[教学方法]首先给出线性表的抽象数据类型定义，然后分别用顺序结构和链表结构实现线性表，最后给出一个应用实例。
[学习要点]1. 了解线性表的逻辑结构特性是数据元素之间存在着线性关系，在计算机中表示这种关系的两类不同的存储结构是顺序存储结构和链式存储结构。
用前者表示的线性表简称为顺序表，用后者表示的线性表简称为链表。
2. 熟练掌握这两类存储结构的描述方法，如一维数组中一个区域[i..j]的上、下界和长度之间的变换公式(L=j-i+1, i=j-L+1, j=i+L-1)，链表中指针p和结点*p的对应关系(结点*(p->next)是结点*p的后继等)，链表中的头结点、头指针和首元结点的区别及循环链表、双向链表的特点等。
链表是本章的重点和难点。
扎实的指针操作和内存动态分配的编程技术是学好本章的基本要求。
3. 熟练掌握线性表在顺序存储结构上实现基本操作：查找、插入和删除的算法。
4. 熟练掌握在各种链表结构中实现线性表操作的基本方法，能在实际应用中选用适当的链表结构。
5. 能够从时间和空间复杂度的角度综合比较线性表两种存储结构的不同特点及其适用场合。
2.1 线性表的概念及运算2.1.1 线性表的逻辑结构线性表是n个类型相同的数据元素的有限序列，数据元素之间是一对一的关系，即每个数据元素最多有一个直接前驱和一个直接后继。
2.1.2 线性表的抽象数据类型定义一个抽象数据类型定义了一个模型，但不涉及模型的具体实现问题。
2.2 线性表的顺序存储2.2.1 线性表的顺序存储结构线性表的顺序存储是指用一组地址连续的存储单元依次存储线性表中的各个元素，使得线性表中在逻辑结构上相邻的数据元素存储在相邻的物理存储单元中。
采用顺序存储结构的线性表通常称为顺序表。
2.2.2 线性表顺序存储结构上的基本运算1. 查找操作线性表有两种基本的查找运算。
按序号查找GetData(L,i): 要求查找线性表L中第i个数据元素，其结果是L.elem[i-1]或L->elem[i-1]。
按内容查找Locate（L,e）:要求查找线性表L中与给定值e相等的数据元素，其结果是：若在表L中找到与e相等的元素，则返回该元素在表中的序号；若找不到，则返回一个“空序号”，如-1。
2.插入操作线性表的插入运算是指在表的第i (1≤i≤n+1)个位置，插入一个新元素e，使长度为n 的线性表(e1，…，e i-1，e i，…，e n) 变成长度为n+1的线性表（e1，…,e i-1，e，e i，…，e n）。
3. 删除操作线性表的删除运算是指将表的第i(1≤i≤n)个元素删去，使长度为n的线性表(e1，…,e i-1，e i，e i+1，…，e n)，变成长度为n-1的线性表(e1，…,e i-1，e i+1，…，e n)。
2.3 线性表的链式存储采用链式存储结构的线性表称为链表。
2.3.1 单链表链表是用一组任意的存储单元来存放线性表的结点，在存储线性表的每个数据元素值的同时，存储指示其后继结点的地址（或位置）信息，这两部分信息组成的存储映象叫做结点（Node），如图2.5 所示。
图2.5 单链表的结点结构它包括两个域：数据域用来存储结点的值；指针域用来存储数据元素的直接后继的地址（或位置）。
由于链表的每个结点只有一个指针域，故将这种链表又称为单链表。
应设一个头指针H指向第一个结点，由于表中最后一个结点没有直接后继，则指定线性表中最后一个结点的指针域为“空”（NULL）。
例如：图2.6所示为线性表（A,B,C,D,E,F,G,H）的单链表存储结构，整个链表的存取需从头指针开始进行，依次顺着每个结点的指针域找到线性表的各个元素。
图2.6 单链表的示例图有时为了操作的方便，还可以在单链表的第一个结点之前附设一个头结点，头结点的数据域可以存储一些关于线性表的长度的附加信息，也可以什么都不存；而头结点的指针域存储指向第一个结点的指针。
此时带头结点单链表的头指针就不再指向表中第一个结点而是指向头结点。
如果线性表为空表，则头结点的指针域为“空”，如图 2.8所示。
(a)带头结点的空单链表(b)带头结点的单链表图2.8 带头结点单链表图示2.3.2 单链表上的基本运算1．建立单链表动态建立单链表的常用方法有如下两种：1）头插法建表算法描述：从一个空表开始，重复读入数据，生成新结点，将读入数据存放到新结点的数据域中，然后将新结点插入到当前链表的表头结点之后，直至读入结束标志为止。
2）尾插法建表该方法是将新结点插到当前链表的表尾上。
