算法与数据结构期末复习重点总结

算法与数据结构

数据结构:逻辑结构、物理结构、运算

逻辑结构:数据元素之间的相互关系,集合、线性、树、图

物理结构(存储结构);顺序存储结构、链式存储结构、索引存储结构、

散列存储结构

线性结构(线性表):两种存储结构及其特点,堆栈、队列,

字符串(模式匹配KMP算法)、多维数组、

矩阵(特殊矩阵、稀疏矩阵)

广义表:求表头元素、求尾表、求元素个数、求深度、复制建立广义表 树和二叉树:二叉树的存储结构、二叉树的性质、二叉树的遍历及其应用、 线索二叉树、二叉树与树的转换、二叉树的计数、哈夫曼树及编码、 完全二叉树、满二叉树、二叉排序树、平衡二叉树

图:图的存储结构、图的遍历极其应用、图的连通性、最小代价生成树, DAG图的拓扑排序、关键路径,最短路径、距离

算法:查找和排序

查找:静态表的查找(无序表、有序表)、静态树表的查找(非等概率) 动态树表的查找(二叉排序树、平衡二叉树)

B树、B+树的查找、数字查找树的查找,散列表的建立、查找 平均查找长度ASL

内部排序:插入排序(直接插入排序、折半插入排序、二路插入排序、希尔) 交换排序(冒泡排序、快速排序)

选择排序(简单的选择排序、锦标赛排序、堆排序)

归并排序(又称合并排序)

多关键字排序(MSD、LSD),基数排序(又称桶排序) 外部排序:归并排序,要减少排序时间就要减少读取外存的次数

加大归并的路数k,减少归并趟数,败者树,

减少初始归并段的个数m,置换-选择排序

 

第二篇:数据结构期末复习总结

一、填空题

4. 数据结构按逻辑结构可分为两大类,它们分别是 线性结构 非线性结构

4. 算法分析的两个主要方面是:

12. 在顺序表中插入,需要移动元素。具体移动的元素个数与 表长和该元素在表中的位置 有关。

13. 线性表中结点的集合是的。

14. 向一个长度为n的向量的第i个元素(1≤i≤n+1)之前插入一个元素时,需向后移动个元素。

15. 向一个长度为n的向量中删除第i个元素(1≤i≤n)时,需向前移动个元素。

16. 在顺序表中访问任意一结点的时间复杂度均为因此,顺序表也称为的数据结构。

17. 顺序表中逻辑上相邻的元素的物理位置相邻。单链表中逻辑上相邻的元素的物理位置 相邻。

18.在单链表中,除了首元结点外,任一结点的存储位置由 其直接前驱结点的链域的值 指示。

19. 在n个结点的单链表中要删除已知结点*p,需找到它的,其时间复杂度为。

20. 向量、栈和队列都是 结构,可以在向量的 位置插入和删除元素;对于栈只能在 栈顶 插入和删除元素;对于队列只能在 队尾 插入和 队首 删除元素。

23. 不包含任何字符(长度为0)的串 称为空串; 由一个或多个空格(仅由空格符)组成的串 称为空白串。

24. 子串的定位运算称为串的模式匹配; 被匹配的主串 称为目标串, 子串 称为模式。

25. 假设有二维数组A6×8,每个元素用相邻的6个字节存储,存储器按字节编址。已知A的起始存储位置(基地址)为1000,则数组A的体积(存储量)为 288 B ;末尾元素A57的第一个字节地址为 ;若按行存储时,元素A14的第一个字节地址为 ;若按列存储时,元素A47的第一个字节地址为 (6×7+4)×6+1000)=1276 。

26. 由3个结点所构成的二叉树有种形态。 课本P127,128

27. 一棵深度为6的满二叉树有 126-1个叶子。

注:满二叉树没有度为1的结点,所以分支结点数就是二度结点数。或总结点数可算,叶子结点数可算,两个相减

28. 一棵具有257个结点的完全二叉树,它的深度为( 注:用? log2(n) ?+1= ? 8.xx ?+1=9

29.设一棵完全二叉树有700个结点,则共有答:最快方法:用叶子数=[n/2]=350

30. 设一棵完全二叉树具有1000个结点,则此完全二叉树有个叶子结点,有个度为2的结点,有 1 个结点只有非空左子树,有 0 个结点只有非空右子树。

答:最快方法:用叶子数=[n/2]=500 ,n2=n0-1=499。 另外,最后一结点为2i属于左叶子,右叶子是空的,所以有1个非空左子树。完全二叉树的特点决定不可能有左空右不空的情况,所以非空右子树数=0.

31.在数据的存放无规律而言的线性表中进行检索的最佳方法是。

32. 线性有序表(a1,a2,a3,?,a256)是从小到大排列的,对一个给定的值k,用二分法检索表中与k相等的元素,在查找不成功的情况下,最多需要检索 8 次。设有100个结点,用二分法查找时,最大比较次数是 7 。即树高

33. 假设在有序线性表a[20]上进行折半查找,则比较一次查找成功的结点数为1;比较两次查找成功的结点数为 2 ;比较四次查找成功的结点数为 8 ;平均查找长度为 3.7 。

解:显然,平均查找长度=O(log2n)<5次(2)。即第一层第二层第三层的结点数。但具体是多少次,则

不应当按照公式

ASL?n?1m)。因为这是在假设n=2-1的情况下log2(n?1)来计算(即(21×log221)/20=4.6次并不正确!n5

推导出来的公式。应当用穷举法罗列:

全部元素的查找次数为=(1+2×2+4×3+8×4+5×5)=74; ASL=74/20=3.7 !!!

34.折半查找有序表(4,6,12,20,28,38,50,70,88,100),若查找表中元素20,它将依次与表中元素 28,6,12,20 比较大小。

二、判断正误(在正确的说法后面打勾,反之打叉)

( × )1. 链表的每个结点中都恰好包含一个指针。

答:错误。链表中的结点可含多个指针域,分别存放多个指针。例如,双向链表中的结点可以含有两个指针域,分别存放指向其直接前趋和直接后继结点的指针。

( × )2. 链表的物理存储结构具有同链表一样的顺序。错,链表的存储结构特点是无序,而链表的示意图有序。

( × )3. 链表的删除算法很简单,因为当删除链中某个结点后,计算机会自动地将后续的各个单元向前移动。错,链表的结点不会移动,只是指针内容改变。

( × )5. 顺序表结构适宜于进行顺序存取,而链表适宜于进行随机存取。

错,正好说反了。顺序表才适合随机存取,链表恰恰适于“顺藤摸瓜”

( × )6. 顺序存储方式的优点是存储密度大,且插入、删除运算效率高。

错,前一半正确,但后一半说法错误,那是链式存储的优点。顺序存储方式插入、删除运算效率较低,在表长为n的顺序表中,插入和删除一个数据元素,平均需移动表长一半个数的数据元素。

( × )7. 线性表在物理存储空间中也一定是连续的。

错,线性表有两种存储方式,顺序存储和链式存储。后者不要求连续存放。

( × )9. 顺序存储方式只能用于存储线性结构。

错误。顺序存储方式不仅能用于存储线性结构,还可以用来存放非线性结构,例如完全二叉树是属于非线性结构,但其最佳存储方式是顺序存储方式。(后一节介绍)

( × )10. 线性表的逻辑顺序与存储顺序总是一致的。

错,理由同7。链式存储就无需一致。

( √ )13. 栈是一种对所有插入、删除操作限于在表的一端进行的线性表,是一种后进先出型结构。 ( √ )14. 对于不同的使用者,一个表结构既可以是栈,也可以是队列,也可以是线性表。 正确,都是线性逻辑结构,栈和队列其实是特殊的线性表,对运算的定义略有不同而已。

( × )15. 栈和链表是两种不同的数据结构。

错,栈是逻辑结构的概念,是特殊殊线性表,而链表是存储结构概念,二者不是同类项。

( √ )17. 栈和队列的存储方式既可是顺序方式,也可是链接方式。

( √ )18. 两个栈共享一片连续内存空间时,为提高内存利用率,减少溢出机会,应把两个栈的栈底分别设在这片内存空间的两端。

( √ )21. 若二叉树用二叉链表作存贮结构,则在n个结点的二叉树链表中只有n—1个非空指针域。 ( √ )23.二叉树中每个结点的两棵子树是有序的。

( × )26.二叉树中所有结点个数是2k-1-1,其中k是树的深度。(应2i-1)

( × )27.二叉树中所有结点,如果不存在非空左子树,则不存在非空右子树。

( √ )29.用二叉链表法(link-rlink)存储包含n个结点的二叉树,结点的2n个指针区域中有n+1个为空指针。

三、单项选择题

( B )1. 非线性结构是数据元素之间存在一种:

A)一对多关系 B)多对多关系 C)多对一关系 D)一对一关系

( C )2. 数据结构中,与所使用的计算机无关的是数据的 结构;

A) 存储 B) 物理 C) 逻辑 D) 物理和存储

( C )3. 算法分析的目的是:

A) 找出数据结构的合理性 B) 研究算法中的输入和输出的关系

C) 分析算法的效率以求改进 D) 分析算法的易懂性和文档性

( B )17. 判定一个栈ST(最多元素为m0)为空的条件是

A.ST->top<>0 B.ST->top=0 C.ST->top<>m0 D.ST->top=m0

( B )22.在表长为n的链表中进行线性查找,它的平均查找长度为

A. ASL=n; B. ASL=(n+1)/2;

C. ASL=n+1; D. ASL≈log2(n+1)-1

( C )24.对22个记录的有序表作折半查找,当查找失败时,至少需要比较 次关键字。 公式p229 A.3 B.4 C.5 D. 6

相关推荐