数据结构学习指导每章习题.docx
- 文档编号:12407903
- 上传时间:2023-06-05
- 格式:DOCX
- 页数:140
- 大小:186.15KB
数据结构学习指导每章习题.docx
《数据结构学习指导每章习题.docx》由会员分享,可在线阅读,更多相关《数据结构学习指导每章习题.docx(140页珍藏版)》请在冰点文库上搜索。
数据结构学习指导每章习题
数据结构学习指导
第1章概述
讲课提要
【主要内容】
1.数据结构的研究目的和研究内容
2.数据结构中的几个重要概念和术语
3.算法设计的基本要求以及算法复杂度的分析和计算方法
【教学目标】
1.了解数据结构的研究目的和研究内容
2.掌握数据结构中的重要概念和术语
3.掌握算法设计的基本要求以及算法复杂度的分析和计算方法
【所需课时】
2次课。
[第一次课]
1.数据结构的研究目的和研究内容
2.数据结构中的重要概念和术语
[第二次课]
3.算法设计的基本要求以及算法复杂度的分析和计算方法
学习指导
1.概念和术语
•数据:
是能输入到计算机中并能被计算机程序处理的符号的总称。
•数据元素:
是数据的基本单位,它在计算机处理和程序设计中通常作为一个整体进行考虑和处理。
一个数据元素可由若干数据项组成。
•数据对象:
是具有相同特征的数据元素的集合,是数据的一个子集。
•数据结构:
是数据元素的组织形式,或数据元素相互之间存在一种或多种特定关系的集合。
•数据的逻辑结构:
是指数据结构中数据元素之间的逻辑关系。
•数据的存储结构:
是数据的逻辑结构在计算机内存中的存储方式,又称物理结构。
•数据类型:
是一组具有相同性质的操作对象以及该组操作对象上的运算方法的集合。
•抽象数据类型:
是指一个数学模型以及在该模型上定义的一套运算规则的集合。
•算法:
建立在数据结构基础上的,为解决问题而采取的步骤和方法。
2.逻辑结构的四种基本形态
根据数据元素之间关系的不同特征,通常有下列四类基本结构:
(1)集合:
结构中的数据元素间除了“同属于一个集合”的关系外,别无其它关系。
(2)线性结构:
结构中的数据元素之间存在一个对一个的关系。
(3)树型结构:
结构中的数据元素之间存在一个对多个的关系。
(4)图型结构或网状结构:
结构中的数据元素之间存在多个对多个的关系。
3.数据存储结构的基本组织方式
数据存储结构有顺序和链式两种方式。
(1)顺序存储结构的特点:
要借助数据元素在存储器中的相应位置来体现数据元素相互间的逻辑关系,常用高级编程语言中的“一维数组”来描述或实现。
(2)链式存储结构的特点:
通过表示数据元素存储地址的指针来表示数据元素之间的逻辑关系,通常用链表来实现。
在顺序存储结构的基础上,又可延伸变化出另外两种存储结构,即索引存储和散列存储。
(1)索引存储就是在数据文件的基础上增加了一个索引表文件。
通过索引表建立索引,可以把一个顺序表分成几个顺序子表,其目的是在查询时提高查找效率,避免盲目查找。
(2)散列存储就是通过数据元素与存储地址之间建立起某种映射关系,使每个数据元素与每一个存储地址之间尽量达到一一对应的目的。
这样,查找时同样可大大提高效率。
4.数据结构的研究内容
数据结构的核心研究内容包括三个方面:
数据的逻辑结构、存储结构以及相应的基本操作运算的定义和实现。
5.算法的五个重要特征
(1)有穷性:
一个算法必须保证在执行有限步骤之后结束,而不是无限的。
(2)确定性:
算法中每一条指令必须有明确的含义,而不能是模棱两可的。
(3)可行性:
每一个操作步骤都必须在有限的时间内完成。
(4)输入:
一个算法可以有一个或多个输入,也可以没有输入。
(5)输出:
一个算法可以有一个或多个输出。
没有输出的算法是没有实际意义的。
6.算法的评价标准
(1)正确性。
(2)易读性。
(3)高效性。
(4)可维护性。
7.算法分析的目的
算法分析主要是指分析算法的效率。
算法效率的度量主要从两个方面:
算法的运行时间和算法所需的存储空间。
分析的目的是通过考察算法的时间和空间效率,以求改进算法或对不同的算法进行比较。
一般情况下,鉴于运算空间(内存)较为充足,所以把算法的时间复杂度分析作为重点。
8.算法的时间复杂度分析
(1)算法运算时间的度量的两种方法:
事后统计的方法和事前分析估算的方法。
(2)算法运行时间的分析规则
通常把一个程序的运行时间定义为一个T(n),其中n是该程序输入数据的规模,而不是某一个具体的输入。
T(n)的单位是不确定的,一般把它看成在一个特定计算机上执行的指令条数。
通常记作:
T(n)=O(f(n)),其中f(n)表示数据输入规模。
常见的算法时间复杂度的形式按性能降序的排列如下:
O
(1) ) ) ) ) ) 【例1-1】分析以下程序段的时间复杂度。 for(i=0;i for(j=0;j A[i][j]=0; 解: 该程序段的时间复杂度为O(m*n)。 【例1-2】分析以下程序段的时间复杂度。 i=s=0;① while(s {i++;② s+=i;③ } 解: 语句①为赋值语句,其执行次数为1次,所以其时间复杂度为O (1)。 语句②和语句③构成while循环语句的循环体,它们的执行次数由循环控制条件中s与n的值确定。 假定循环重复执行x次后结束,则语句②和语句③各重复执行了x次。 其时间复杂度按线性累加规则为O(x)。 此时s与n满足关系式: s≥n,而s=1+2+3+…+x。 所以有: 1+2+3+…+x≥n,可以推出: x= x与n之间满足x=f( ),所以循环体的时间复杂度为O( ),语句①与循环体由线性累加规则得到该程序段的时间复杂度为O( )。 【例1-3】分析以下程序段的时间复杂度。 i=1;① while(i<=n) i=2*i;② 解: 其中语句①的执行次数是1,设语句②的执行次数为f(n),则有: 。 得: T(n)=O( ) 【例1-4】有如下递归函数fact(n),分析其时间复杂度。 fact(intn) {if(n<=1) return (1); ① else return(n*fact(n-1)); ② } 解: 设fact(n)的运行时间函数是T(n)。 该函数中语句①的运行时间是O (1),语句②的运行时间是T(n-1)+O (1),其中O (1)为常量运行时间。 由此可得fact(n)的时间复杂度为O(n)。 9.算法空间复杂度的含义 空间复杂度是对一个算法在运行过程中临时占用存储空间大小的量度。 算法在计算机存储器内占用的存储空间主要分为三部分: 算法源代码本身占用的存储空间;算法输入输出数据所占用的存储空间;算法运行过程中临时占用的存储空间。 考虑一个算法的空间复杂度时,要综合分析这三个方面的因素。 通常记作: S(n)=O(f(n)),其中n为问题的规模(或大小)。 习题1 一、单项选择题 1.数据结构是指()。 A.数据元素的组织形式B.数据类型 C.数据存储结构D.数据定义 2.数据在计算机存储器内表示时,物理地址与逻辑地址不相同的,称之为()。 A.存储结构B.逻辑结构 C.链式存储结构D.顺序存储结构 3.树形结构是数据元素之间存在一种()。 A.一对一关系B.多对多关系 C.多对一关系D.一对多关系 4.设语句x++的时间是单位时间,则以下语句的时间复杂度为()。 for(i=1;i<=n;i++) for(j=i;j<=n;j++) x++; A.O (1)B.O( )C.O(n)D.O( ) 5.算法分析的目的是 (1),算法分析的两个主要方面是 (2)。 (1)A.找出数据结构的合理性B.研究算法中的输入和输出关系 C.分析算法的效率以求改进D.分析算法的易懂性和文档性 (2)A.空间复杂度和时间复杂度B.正确性和简明性 C.可读性和文档性D.数据复杂性和程序复杂性 6.计算机算法指的是 (1),它具备输入,输出和 (2)等五个特性。 (1)A.计算方法B.排序方法 C.解决问题的有限运算序列D.调度方法 (2)A.可行性,可移植性和可扩充性B.可行性,确定性和有穷性 C.确定性,有穷性和稳定性D.易读性,稳定性和安全性 7.数据在计算机内有链式和顺序两种存储方式,在存储空间使用的灵活性上,链式存储比顺序存储要()。 A.低B.高C.相同D.不好说 8.数据结构作为一门独立的课程出现是在()年。 A.1946B.1953C.1964D.1968 9.数据结构只是研究数据的逻辑结构和物理结构,这种观点()。 A.正确B.错误 C.前半句对,后半句错D.前半句错,后半句对 10.计算机内部数据处理的基本单位是()。 A.数据B.数据元素C.数据项D.数据库 二、填空题 1.数据结构按逻辑结构可分为两大类,分别是______________和_________________。 2.数据的逻辑结构有四种基本形态,分别是________________、__________________、__________________和__________________。 3.线性结构反映结点间的逻辑关系是__________________的,非线性结构反映结点间的逻辑关系是__________________的。 4.一个算法的效率可分为__________________效率和__________________效率。 5.在树型结构中,树根结点没有__________________结点,其余每个结点的有且只有__________________个前趋驱结点;叶子结点没有__________________结点;其余每个结点的后续结点可以__________________。 6.在图型结构中,每个结点的前趋结点数和后续结点数可以__________________。 7.线性结构中元素之间存在__________________关系;树型结构中元素之间存在__________________关系;图型结构中元素之间存在__________________关系。 8.下面程序段的时间复杂度是__________________。 for(i=0;i for(j=0;j A[i][j]=0; 9.下面程序段的时间复杂度是__________________。 i=s=0; while(s {i++; s+=i; } 10.下面程序段的时间复杂度是__________________。 s=0; for(i=0;i for(j=0;j s+=B[i][j]; sum=s; 11.下面程序段的时间复杂度是__________________。 i=1; while(i<=n) i=i*3; 12.衡量算法正确性的标准通常是____________________________________。 13.算法时间复杂度的分析通常有两种方法,即___________和___________的方法,通常我们对算法求时间复杂度时,采用后一种方法。 三、求下列程序段的时间复杂度。 1.x=0; for(i=1;i for(j=i+1;j<=n;j++) x++; 2.x=0; for(i=1;i for(j=1;j<=n-i;j++) x++; 3.inti,j,k; for(i=0;i for(j=0;j<=n;j++) {c[i][j]=0; for(k=0;k c[i][j]=a[i][k]*b[k][j] } 4.i=n-1; while((i>=0)&&A[i]! =k)) j--; return(i); 5.fact(n) {if(n<=1) return (1); else return(n*fact(n-1)); } 习题1参考答案 一、单项选择题 1.A2.C3.D4.B5.C、A6.C、B7.B8.D9.B10.B 二、填空题 1.线性结构,非线性结构 2.集合,线性,树,图 3.一对一,一对多或多对多 4.时间,空间 5.前趋,一,后继,多 6.有多个 7.一对一,一对多,多对多 8.O( ) 9.O( ) 10.O( ) 11.O(log n) 12.程序对于精心设计的典型合法数据输入能得出符合要求的结果。 13.事后统计,事前估计 三、算法设计题 1.O( )2.O( )3.O(n )4.O(n)5.O(n) 第2章线性表 讲课提要 【主要内容】 1.线性表的概念和基本运算 2.顺序表(线性表的顺序存储结构) 3.链表(线性表的链式存储结构) (1)单链表和循环单链表 (2)双向链表和循环双链表 4.线性表应用 (1)栈 (2)队列 【教学目标】 1.了解线性表的概念及其常用运算 2.熟悉顺序表的结构及基本算法描述 3.掌握单链表的结构及基本算法描述,了解双向链表及循环链表 4.掌握栈和队列的结构特点及其插入和删除算法 5.了解栈在程序设计中的实际应用 【所需课时】 7次课。 [第一次课] 1.线性表的定义及其运算 2.顺序表的存储结构 [第二次课] 3.顺序表的基本运算 4.顺序表的算法描述及算法分析 [第三次课] 5.单链表的结构及其算法实现 6.循环单链表的结构及其算法实现 [第四次课] 7.双向链表的结构及其算法实现 8.循环双链表的结构及其算法实现 [第五次课] 9.栈的定义及其结构特点 10.顺序栈的结构及其算法实现 [第六次课] 11.链栈的结构及其算法实现 12.栈的应用 [第七次课] 13.队列的定义及顺序存储 14.队列的链式存储 学习指导 1.线性表的定义 线性表是n个数据元素的有限序列,其中n(n≥0)为线性表的长度。 线性表中各个元素的类型相同。 对于线性表(a1,a2,…,ai,…,an)而言,数据元素a1没有直接前趋,an没有直接后继,表中的其它元素ai(2≤i≤n-1)有且仅一个直接前趋ai-1和直接后继ai+1。 2.顺序表 顺序表是指线性表的顺序存储结构,即用一组连续的存储单元依次存放线性表的数据元素。 在C语言中可用一维数组来表示。 在顺序表中,以数据元素在计算机内“物理位置相邻”来表示表中数据元素间的逻辑关系。 顺序表是一种随机存储结构,只要确定了存储顺序表的起始位置,则表中任一元素都可以随机存取。 所以在顺序表中可以方便的进行数据元素的查找及存取。 但是在进行插入和删除操作时,将会引起元素的大量移动,因而效率比较低,并且易产生空间浪费或“上溢”现象。 顺序表的操作还应注意元素的存储位置,即数组下标(C语言中下标从0开始)。 【例2-1】试编写出将两个顺序存储的有序表A和B合成一个有序表C的算法。 解: 假设A、B和C的类型为下述SqList类型: #definemaxlen1000 typedefintelemtype typedefstruct {elemtypeelem[maxlen]; intlen; }SqList; 设A和B的数据元素均为整数且为升序排列,设A的长度为m,B的长度为n,则合并后C的长度为m+n。 合并时进行A、B元素的比较,将较小的链入C中,算法描述如下: intmerge(SqList*A,SqList*B,SqList*C)//将两个有序表A和B合成一个有序表C {intm,n,i,j,k; m=(*A).len;n=(*B).len; if(m+n>maxlen-1) {printf("overflow"); exit(0); } i=0;j=0;//i和j分别作为扫描顺序表A和B的指针 k=0;//k指示顺序表C中当前位置 while((i<=m)&&(j<=n)) if((*A).elem[i]<=(*B).elem[j]) {(*C).elem[k]=(*A)elem[i]; i++;k++; } else {(*C).elem[k]=(*B)elem[j]; j++;k++; } while(i<=m)//表B已结束,表A没有结束,链入表A的剩余部分 {(*C).elem[k]=(*A).elem[i]; i++;k++; } while(j<=m)//表A已结束,表B没有结束,链入表B的剩余部分 {(*C).elem[k]=(*B).elem[j]; i++;k++; } return (1); } 3.链表 链表是线性表的链式存储结构。 链表是用一组任意的存储单元(可以是连续的,也可以是不连续的)存放线性表的数据元素。 在链表中,通过指针来表示元素之间的逻辑关系的,不再有逻辑顺序与物理存储顺序一致的特点,是非顺序存储结构。 在单链表中,每个结点由数据域和指针域组成。 数据域保存数据元素的信息,指针域存放其直接后继的存储位置。 其类型可描述为: typedefstructNode {elemtypedata; structNode*next; }LinkList; 单链表由头指针唯一确定。 为了便于操作,可在链表的第一个结点之前添加一个表头结点。 在链表中进行插入和删除操作只需要修改有关的指针内容,不需要移动元素。 因此,链表较顺序表的插入和删除操作更加方便、高效。 为了便于实现各种运算,若无特殊说明,均采用带头结点的链表。 【例2-2】写一算法实现单链表的逆置。 解: 假设单链表的表头指针用head表示,其类型为上面定义的LinkList,并且单链表不带头结点。 逆置后原来的最后一个结点成为第一个结点,于是从第一个结点开始逐个修改每个结点的指针域进行逆置,且刚被逆置的结点总是新链表的第一个结点,故令head指向它(如图2-1所示)。 具体算法描述如下: (b)第三个结点逆置 示示 图 voidcontray(LinkList*head) {//将head单链表中所有结点按相反次序链接 LinkList*p,*q; p=head;//p指向未被逆序的第一个结点,初始时指向原表头结点 head=NULL; while(p! =NULL) {q=p;//q指向将被逆序链接的结点 p=p->next; q->next=head; head=q; } } 【例2-3】假设有一个循环链表的长度大于1,且表中既无头结点也无头指针,已知p为指向链表中某结点的指针,设计在链表中删除p所指结点的前趋结点的算法。 解: 可引入一个指针q,当q->next=p时,说明此时q所指的结点为p所指结点的前趋结点,从而可得算法如下: voiddelete(LinkList*p) {//在链表中删除p所指结点的前趋结点 LinkList*q,*t; q=p; while(q->next->next! =p)//q->next不是p的前趋结点 q=q->next; t=q->next;//t指向要删除结点 q->next=p;//删除t结点 free(t); } 【例2-4】试设计实现删除单链表中值相同的多余结点的算法。 解: 该例可以这样考虑,先取开始结点的值,将它与其后的所有结点值一一比较,发现相同的就删除掉,然后再取第二结点的值,重复上述过程直到最后一个结点。 设单链表(其类型为LinkList)的头指针head指向头结点,则可按下列步骤执行: 首先,用一个指针p指向单链表中第一个表结点,然后用另一个指针q查找链表中其余结点元素,由于是单链表,故结束条件为p==NULL,同时让指针s指向q所指结点的前趋结点,当查找到结点具有q->data==p->data时删除q所指的结点,然后再修改q,直到q为空;然后使p指针后移(即p=p->next),重复进行,直到p为空时为止。 算法描述如下: del(LinkList*head) {//删除单链表中值相同的多余结点 LinkList*p,*s,*q; p=head->next; while(p! =NULL&&p->next! =NULL) {s=p;//s指向要删除结点的前趋 q=p->next; while(q! =NULL) {if(q->data==p->data)}//查找值相同的结点并删除 {s->next=q->next; free(q); q=s->next; } else {s=q; q=q->next; } } p=p->next; } } 4.栈 栈(Stack)是限定仅在表的一端进行插入或删除操作的线性表。 通常把允许插入和删除操作的一端称为栈顶(Top),而另一端称为栈底(Bottom)。 表为空时称为空栈。 在栈上的主要运算是入栈和出栈。 栈中元素如果按a1,a2,…,an的顺序进栈,则出栈顺序为an,an-1,…,a1。 因此,栈又称为“后进先出”(LastInFirstOut)的线性表,简称LIFO表。 同线性表相似,栈也有顺序栈和链栈两种存储结构。 顺序栈易产生“上溢”现象,而链栈不容易产生。 另外,注意对栈的操作只能在栈顶进行。 5.队列 队列(Queue)是限定只能在表的一端进行插入,在表的另一端进行删除的线性表。 通常把允许插入的一端称为队尾(rear),允许删除的一端称为队头(front)。 队列中元素如果按a1,a2,…,an的顺序进队,则出队的顺序仍为a1,a2,…,an。 因此,队列又称为“先进先出”(FirstInFirstOut)的线性表,简称FIFO表。 队列也有顺序队列和链队列两种存储结构。 在顺序队列中,为避免“假满”现象,一般采用循环队列(即首尾相接)。 链队列会因为队满而产生“上溢”现象。 习题2 一、单项选择题 1.线性表是________。 A.一个有限序列,可以为空B.一个有限序列,不可以为空 C.一个无限序列,可以为空D.一个无限序列,不可以为空 2.在一个长度为n的顺序表中删除第i个元素(0<=i<=n)时,需向前移动个元素。 A.n-iB.n-i+lC.n-i-1D.i 3.线性表采用链式存储时,其地址________。 A.必须是连续的B.一定是不连续的 C.部分地址必须是连续的D.连续与否均可以 4.从一个具有n个结点的单链表中查找其值等于x的结点时,在查找成功的情况下,需平均比较________个元素结点。 A.n/2B.nC.(n+1)/2D.(n-1)/2 5.在双向循环链表中,在p所指的结点之后插入s指针所指的结点,其操作是____。 A.p->next=s;s->prior=p; p->next->prior=s;s->next=p->next; B.s->prior=p;s->next=p->next; p->next=s;p->next->prior=s; C.p->next=s;p->next->prior=s; s->pr
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 数据结构 学习 指导 每章 习题