数据结构期末作业文档

《数据结构期末作业文档》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、目录目录1第一章绪论3一、内容提要3二、学习重点3三、例题解析3第二章 线性表5一、内容提要5二、学习重点5三、例题解析5第三章栈和队列8一、内容提要8二、学习重点8三、例题解析8第四章   串12一、内容提要12二、学习重点12三、例题解析12第五章数组和广义表14一、内容提要14二、学习重点14三、例题解析14第六章树和二叉树16一、内容提要16二、学习重点16三、例题及分析16第七章图19一、内容提要19二、学习重点19三、例题解析20第八章动态存储管理22一、内容提要22二、学习重点22三、例题解析22第九章　查找24一、 内容提要24二、学习重点24三、例题解析2

2、5第十章 内部排序27一、内容提要27二、学习要点27二、例题解析27第十一章外部排序3032/32一、内容提要30二、学习要点30三、习题解析30第十二章文件32一、内容提要32二、学习重点3232/32第一章绪论一、内容提要1数据结构研究的内容。2基本概念：数据、数据元素、数据对象、数据结构、数据类型、抽象数据类型、多形数据类型。3算法的定义及五个特征。4算法描述：类PASCAL语言。5算法设计要求。6算法分析。 二、学习重点1数据结构的“三要素”：逻辑结构、物理（存储）结构及在这种结构上所定义的操作（运算）。2抽象数据类型的定义、表示和实现方法。3类PASCAL书写规

3、范，过程（函数）中值参和变参的差别，过程调用规则。4用计算语句频度来估算算法的时间复杂度。 三、例题解析1写出以下各语句执行次数（左边括号内数字为语句序号）(1)FORi:=1TOnDO(2)FORj:=1tonDO(3)[c[I,j]:=0;(4)FORk:=1TOnDO(5)                                      c[I,j]:=c[I,j]+a[I,k]*b[k,j]矚慫润厲钐瘗睞枥庑赖。][答案]：各语句执行次数（频度）分别为n+1，n(n+1),n2,n2(n+1),n3聞創沟燴鐺險爱氇谴净。[分析]：最容易发生的错误，是将第一

4、个语句的执行次数答成n。  2编写最优算法，从小到大依次输出顺序读入的三个整数PROCasscending;{本算法对读入的三个整数进行排序，然后按从小到大输出}{算法中核心语句如下}read(a,b,c);IFa>bTHEN[t:=a;a:=b;b:=t];{a,b按正序排序}IFb>cTHEN[t:=c;c:=b;{c为最大}IFa

5、据移动，而在最坏情况下，也只是经过三次比较，七个赋值语句就完成了排序。在本课程教学中，强调“好”的算法,不仅仅是结果正确,而且是最优的算法。这与PASCAL语言教学中的要求有很大不同。残骛楼諍锩瀨濟溆塹籟。算法是供人来阅读的，必须牢记这一点。算法中语句的书写格式采用缩进规则，保留字用大写，其余标识符小写，提高了算法的易读性。   32/32第二章 线性表 一、内容提要1．线性表是元素间约束力最强的一类数据结构。2．线性表的逻辑结构定义，对线性表定义的操作。3．线性表的存储结构：顺序存储结构和链式存储结构。4．线性表的操作在两种存储结构中的实现。5．一元多项式的线性表表示方法

6、，及高次（稀疏）多项式的抽象数据类型定义、表示和加法的实现。 二、学习重点1．1． 线性表的逻辑结构，指线性表的数据元素间存在着线性关系。在顺序存储结构中，元素存储的先后位置反映出这种线性关系，而在链式存储结构中，是靠指针来反映这种关系的。酽锕极額閉镇桧猪訣锥。2．2． 顺序存储结构用向量（一维数组）表示，给定下标，可以存取相应元素，属于随机存取的存储结构。3．3． 尽管“只要知道某结点的指针就可以存取该元素”，但因链表的存取都需要从头指针开始，顺链而行，故链表不属于随机存取结构。彈贸摄尔霁毙攬砖卤庑。4．4． 链表是本章学习的重点和难点。要理解头结点，首元结点和元素结点的

7、差别。理解头结点是为了在插入、删除等操作时，为了算法的统一而设立的（若无头结点，则在第一元素前插入元素或删除第一元素时，链表的头指针总在变化）。掌握通过画出结点图来进行链表的生成、插入、删除、遍历等操作。謀荞抟箧飆鐸怼类蒋薔。5．5． 链表操作中应注意不要使链意外“断开”。因此，若在某结点前插入一个元素，或删除某元素，必须知道该元素的前驱结点的指针。厦礴恳蹒骈時盡继價骚。6．6． 从时间和空间复杂度的角度综合比较线性表在顺序和链式两种存储结构下的特点。7．7． 静态链表是又一重点和难点。应和链表进行比较、理解。例如