《数据结构辅导线性结构》由会员分享，可在线阅读，更多相关《数据结构辅导线性结构（17页珍藏版）》请在金锄头文库上搜索。
1、数据结构辅导201003A第一章绪论基本知识点：数据结构与算法的概念。重点： 数据结构的逻辑结构、存储结构、数据运算三方面的概念及相互关系；算法时间复杂度分析。难点：分析算法的时间复杂度。知识要点：数据：在计算机科学中数据是指所有能输入到计算机中并被计算机处理的符号的总称。数据元素：数据的基本单位，是数据的一个元素。数据对象：性质相同的数据元素的集合，是数据的一个子集。数据结构：相互之间存在一种或多种特定关系的数据元素的集合，一般包括三个方面的内容，即数据的逻辑结构、存储结构和数据的运算。数据类型：一个值的集合和定义在这个值集上的一组运算的总称。数据结构是一门研究非数值计算的程序设计问题中计算
2、机的操作对象（数据元素） 以及它们之间关系和操作（运算）的学科。数据的逻辑结构是指数据元素之间逻辑关系的整体。数据的存储结构是指数据结构在计算机内的表示。四种基本数据结构：集合、线性结构、树形结构、图结构。算法具有的五个基本特性是：有穷性、可行性、确定性、输入和输出。算法执行的时间是问题规模的函数。算法的时间复杂度是指，随着问题规模n 的增大，算法执行时间的增长率和f(n) 的增长率相同时，则称该算法的时间复杂度为O(f(n) 。算法的时间复杂度与问题的规模有关。例题： 编写一个算法， 求一个整数数组中的最大元素和最小元素，并指出该算法的时间复杂度。解：对应的算法如下：void MaxMin(
3、int a,int n, int &max, int &min)/该算法求数组 a0.n-1 的最大元素 max 和最小元素 min 。 max=min=a0 ;for(int i=1 ;imax) max=ai ;else if(aia1) max1=a0 ;max2=a1 ;else max1=a1; max2=a0;for(int i=2;imax1)max2=max1; max1=ai;else if(aimax2) max2=ai;该算法的时间复杂度为O(n) 。例题： 编写一个算法， 求一个整数数组中的最小元素和次小元素，度。解：对应的算法如下：并指出该算法的时间复杂void Mi
4、n12(int a, int n, int &min1, int &min2)/该算法求数组a0n-1 的最小元素min1和次小元素min2。 if(a0a1) min1=a0; min2=a1;else min1=a1;min2=a0;for(int i=2;i=n-1;i+)if(aimin1) min2=min1;min1=ai;else if(aimin2) min2=ai;该算法的时间复杂度为例题： 选择题 O(n) 。1、数据结构是一门研究程序设计中数据的_以及它们之间的关系和运算等的学科。(A) 元素 (B) 计算方法 (C) 逻辑存储 (D) 映像2、在数据结构中，从逻辑上可以
5、把数据结构分为_两类。(A) 动态结构和静态结构(B) 紧凑结构和非紧凑结构(C) 线性结构的非线性结构(D) 内部结构和外部结构3、数据的逻辑结构是_关系的整体。(A) 数据数据之间逻辑(B) 数据项之间逻辑(C) 数据类型之间(D) 存储结构4、在链式存储结构中，一个存储结点存储一个_。(A) 数据项(B) 数据元素(C) 数据结构(D) 数据类型5、数据结构在计算机内存中的表示是指_ 。(A) 数据的存储结构(B) 数据结构(C) 数据的逻辑结构(D) 数据元素之间的关系6、在数据结构中，与所使用的计算机无关的是_。(A) 逻辑结构(B) 存储结构(C) 逻辑结构和存储结构(D) 物理结
6、构7、数据采用链式存储结构时，要求_。(A) 每个结点占用一片连续的存储区域(B) 所有结点占用一片连续的存储区域(C) 结点的最后一个数据域是指针类型(D) 每个结点有多少个后继，就设多少个指针域8、算法的时间复杂度与_ 有关。(A) 问题规模(B) 计算机硬件性能(C) 编译程序质量(D) 程序设计语言9、算法分析的目的是_。(A) 找出数据结构的合理性(B) 研究算法中输入与输出的关系(C) 分析算法的效率以求改进(D) 分析算法的易读性和文档性10、某算法的时间复杂度为O(n2) ，表明该算法的_。(A) 问题的规模是 n2(B) 执行时间等于 n2(C) 执行时间与 n2 成正比(D
7、) 问题规模与 n2 成正比第 2 章线性表基本知识点：线性表的逻辑结构特征，线性表的基本运算，线性表的两种存储结构，以及在这两种存储结构下线性表的基本运算算法的实现，顺序表和链表的优缺点比较。重点：掌握线性表的定义和特点，线性表的存储结构；顺序表和链表的组织方法和算法设计。难点：单链表和双链表的各种算法设计。例题 1、已知顺序表L，请设计一算法，在L 的第i 个位置插入x。解：存储结构如下：解：存储结构如下：typedef struct SqList ElemType *elem; int length;int listsize;SqList;在顺序表L 的第 i 个位置 (下标为 i-1)
8、 上插入 x 的算法如下：void InsertSqList(SqList &L, int i, ElemType x)ElemType *p, *q;if(iL.length) return; /插入位置不合法。p=&L.elemi-1; q=&L.elemL.length-1;while(q=p) *(q+1)=*q; q-;后移*p=x;/ 插入L.length+;例题 2、已知顺序表解：存储结构如下：L，请设计一个算法，删除L 中所有值为x 的结点。typedef struct SqList ElemType *elem;int length;int listsize;SqList;算
9、法如下：void DeleteAllx(SqList &L, ElemType x) int num=0; int i, j;i=0; j=0; while(j=0 & xL.elemk) L.elemk+1=L.elemk; k=k-1;L.elemk+1=x;L.length+;例题 4、编写一个算法逆置顺序表。解：存储结构如下：typedef struct SqList ElemType *elem; int length;int listsize;SqList;算法如下：void Reverse(SqList &L) ElemType *p, *q;p=&L.elem0; q=&L.e
10、lemL.length-1;while(pq) ElemType *temp=*p; *p=*q; *q=temp;例题 5、编写一个算法，归并两个有序的顺序表。解：存储结构如下：typedef struct SqList ElemType *elem; int length;int listsize;SqList;算法如下：void MergeSqList(SqList &L1, SqList &L2, SqList &L3) int i, j, k; i=j=k=0; while(iL1.length & jL2.length)if(L1.elemi=L2.elemj) L3.elemk+=L1.elemi+; else L3.elemk+=L2.elemj+;while(iL1.length) L3.elemk+=L1.elemi+; while(jL2.length) L3.elemk+=L2.elemj+; L3.length=k;例题 6、
