江苏师范大学数据结构总复习总结ppt课件.ppt

《江苏师范大学数据结构总复习总结ppt课件.ppt》由会员分享，可在线阅读，更多相关《江苏师范大学数据结构总复习总结ppt课件.ppt（61页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、本章要点：（1）有关数据结构的基本概念，包括：数据、数据对象、数据元素或者数据成员、数据结构、数据类型等；数据抽象、抽象数据类型、数据结构的抽象层次等。（2）算法设计与分析：算法的定义和算法的特性 算法的设计方法：包括问题解决的基本思路、算法设计的基本步骤、算法的实现 算法的性能分析：包括算法的性能标准，算法的后期测试；算法的事情估计；空间复杂度度量；时间复杂度度量；时间复杂度的渐进表示法1、顺序存储结构中数据元素间的逻辑结构是由（）来表示的，链接存储结构中数据元素间的逻辑关系是由（）表示。A 指针 B 逻辑顺序 C 存储位置 D 问题上下文2、算法的时间复杂度与（）有关。A 问题规模 B 计

2、算机硬件的运行速度 C 源程序的长度 D 编译后执行程序的质量3、某算法的时间复杂度为O(n2)，表明该算法（）A 问题规模是n2 B 问题规模与n2成正比 C 执行时间等于n2 D 执行时间与n2成正比CAAD4、算法是一个有穷的指令集，它为解决某一特定任务规定了一个运算序列。它应当具有输入、输出、（）、有穷和可行性等特性。5、算法效率的度量分为（）和（）。前者主要通过在算法的某些部位插装时间函数来测定算法完成某一个规定功能所需要的时间。而后者不实际运行算法，它是分析算法中语句的执行次数来度量算法的时间复杂度。6、程序所需要的存储空间包含两个部分（）和（）。前者空间的大小与输入输出数据的个数

3、多少，数值大小无关。后者空间主要包括其大小与问题规模有关的成分变量所占空间等等。确定性事后测量 事前估计固定部分可变部分7、有实现同一功能的两个算法A1 和A2，其中A1 的渐进时间复杂度是，A2 的渐进时间复杂度为。仅就时间复杂度而言，具体分析这两个算法哪个好。比较算法好坏，需要比较两个函数2n和n2当n=1 时，2112，算法A2 好于A1当n=2 时，22=22，算法A2 与A1 相当当n=3 时，2342，算法A2 好于A1当n4 时，24n2，算法A2 好于A1当n 时，算法A2 在时间上好于A1本章要点：（1）线性表的定义和特点，包括：线性表的定义，注意几个关键词：有穷、序列、数据

4、元素；线性表特点：唯一前驱和唯一后继。线性表元素类型 线性表与向量（一维数组）的关系，注意它们间的异同 线性表的操作归类：包括访问操作（搜索，遍历）、维护操作（插入、删除），设置操作（初始化或者置空），判断操作（判空、判满）、游标操作（前驱、后继）本章要点：（2）线性表的顺序存储表示：顺序表的静态和动态的C 结构定义，以及C+类定义 顺序表的特点：即元素的逻辑顺序和物理顺序的一致性 顺序表的主要操作，如插入、删除、搜索等的实现算法 掌握主要功能的关键语句：如遍历整个顺序表、遍历到指定节点的语句；插入、删除时成片移动元素的语句等掌握简单的效率分析，包括搜索算法中数据比较次数的计算，插入、删除的数

5、据移动次数的计算本章要点：（3）线性表的链接存储表示：单链表的C 结构定义，以及C+类定义 单链表的特点：即元素的逻辑顺序和物理顺序的不一致性 单链表的主要操作，如插入、删除、搜索等的实现算法。注意无附加头结点和带附加头结点的单链表上操作实现的差异 掌握主要功能的关键语句：如遍历整个顺序表、遍历到指定节点的语句；无头结点单链表的表头插入、删除；带头结点单链表的搜索操作；带头结点单链表的插入、删除运算以及单链表的创建、释放、逆置、分裂、合并等运算有序单链表的主要操作：如搜索、插入、删除等，以及分裂，合并，剔除重复元素等运算1、在下列关于线性表的叙述中正确的是（）A 线性表的逻辑顺序和物理顺序总是

6、一致的 B 线性表的顺序存储表示优于链式存储表示 C 线性表若采用链式存储表示时，所有存储单元的地址可连续或者可不连续 D 每种数据结构都应具备三种基本运算插入、删除和查找2、若长度为n 的非空线性表采用顺序存储结构，在表的i 个位置插入一个数据元素，i 的合法值应该是（）A i0 B 1=i=n C 0=i=n-1 D 0=i=n 3、对于顺序存储的线性表，其算法的时间复杂度为O(1)的运算应（）A 将n 个元素从小到大排序 B 从线性表中删除第i 个元素（1=i=n）C 查找第i 个元素（1=i=n）D 在第i 个元素（1=i=n）后插入一个新元素4、若长度为n 的顺序表的表尾插入一个新元

7、素的渐进时间复杂度为（）A O(n)B O(1)C O(n2)D O(log2n)5、已知L 是带表头的单链表，L 是表头指针，则摘除首元结点的语句是（）A L=L-link B L-link=L-link-link C L=L-link-link D L-link=L6、已知单链表A 长度为m，单链表B 长度为n，若将B接在A 的末尾，在没有链尾指针的情形下，算法的时间复杂度应为（）A O(1)B O(m)C O(n)D O(m+n)7、从一个具有n 个结点的有序单链表中查找其值等于x的结点时，在查找成功的情况下，平均需要比较（）个结点。A n B n/2 C(n-1)/2 D(n+1)/2

8、8、在一个具有n 个结点的单链表中插入一个新结点，并可以不保持原有顺序的算法的时间复杂度是（）A O(1)B O(n)C O(n2)D O(nlog2n)9、给定有n 个元素的一维数组，建立一个有序单链表的时间复杂度是（）。A O(1)B O(n)C O(n2)D O(nlog2n)判断一个带附加头结点的双向循环链表L 是否对称相等的算法如下所示，请在算法中的_中填入正确的语句bool symmetry(DblList DL)bool sym=true;DblNode*p=DL-rLink,*q=DL-lLink;while(p!=q|p-lLink!=q|)if(p-data=q-data)

9、_ _ else sym=false;return sym;sym=truep=p-rLinkq=q-lLink本章要点：（1）栈的队列定义和特点，包括：栈的定义，注意栈顶进出、栈底不能进出，顺序存取的概念，栈的先进后出的特点 队列的定义，注意队头出、队尾进、顺序存取的概念，队列的先进先出的特点 注意区分栈、队列、向量。栈的队列是顺序存取，向量是直接存取 进栈、出栈、判空、置空操作的使用栈空、队空在实际使用时不算出错，它标志某种处理的结束 栈满、队满在实际使用时用力判断可能的出错（2）栈的存储表示及其基本运算的实现：顺序栈的类结构定义 顺序栈的栈顶指针实际指示的位置，以及如何用栈顶指针表示顺序

10、栈的栈空、栈满条件 顺序栈的进栈、出栈运算的实现。注意操作的前置条件和后置条件，以及在参数表中应用参数的作用双栈共用一个数组的进栈、退栈、置空栈、判栈空算法以及栈满、栈空条件链式栈的结构定义，注意链式栈的栈顶指针实际指示的位置 链式栈的进栈、出栈运算的实现，注意链式栈的栈空条件 栈满时的扩充算法（3）队列的存储表示及其基本运算的实现 循环队列的雷结果定义，注意对头指针和队尾指针进退的方向，以及如何用这两个指针判对空和队列满 循环队列的进队、出队的取模操作的实现 使用对头指针front 和队列长度length 实现循环队列时进队列和出队列的操作 链式队列的类结构定义链式队列的进队和出队列操作的实

11、现 双端队列的进队、出队运算的实现 优先级队列的存储结构（4）栈的应用1、已知一个栈的进栈序列为1,2,3，,n，其输出序列的第一个元素是i，则第j 个出战元素是（）A j-i B n-i C j-i+1 D 不确定2、已知一个栈的进栈序列为1,2,3，,n，其输出序列是p1,p2,p3,pn。若p1=n，则pi 的值是（）A i B n-i C n-i+1 D 不确定3、已知一个栈的进栈序列为1,2,3，,n，其输出序列是p1,p2,p3,pn。若p1=3，则p2 的值是（）A 一定是2 B 一定是1 C 可能是1 D 可能是24、将递归算法转换成对应的非递归算法时，除了单向递归和尾递归的情

12、况外，通常需要使用（）保存中间结果 A 链表 B 栈 C 队列 D 顺序表5、设求解某问题的递归算法如下void F(int n)if(n=1)Move(1);elseF(n-1);Move(n);F(n-1);求解算法的计算时间，仅考虑算法move 所作的计算，且move 为常数级算法。则算法F 的计算时间T(n)的递推关系为（）A T(n)=T(n-1)+1 B T(n)=2T(n-1)C T(n)=2T(n-1)+1 D T(n)=2T(n+1)+16、一个队列的进队顺序是1,2,3,4，则该队可能的输出序列是（）A 1,2,3,4 B 1,3,2,4 C 1,4,2,3 D 4,3,2

13、,17、牺牲一个单元区分队空、队满条件的循环队列的队满条件是（）A(q.rear+1)%maxSize=(q.front+1)%maxSize B(q.front+1)%maxSize=q.rear C(q.rear+1)%maxSize=q.front D q.frong=q.rear8、设循环队列存储数组的下标是0maxSize-1，其队尾指针和队头指针分别为rear 和front，则队列中的元素个数为（）A q.rear-q.front B q.rear-q.front+1 C(q.rear-q.front)%maxSize+1 D q.rear-q.front+maxSize)%maxSize9、设栈S 的队列Q 的初始状态为空，元素a,b,c,d,e,f,g依次进栈栈S。如果每个元素出栈后立即进入队列Q，且7个元素出队的顺序为b,d,e,f,e,a,g，则栈S 的容量至少是（）A 1 B 2 C 3 D 4