2022年数据结构知识点复习资料.docx

精选学习资料 - - - - - - - - - 学习必备 欢迎下载数据结构复习资料一、填空题1. 数据结构是一门讨论非数值运算的程序设计 问题中运算机的 操作对象 以及它们之间的 关系 和运 算 等的学科；2. 数据结构被形式地定义为（D, R ）,其中 D是 数据元素 的有限集合,R是 D上的 关系 有限集合；3. 数据结构包括数据的 规律结构、数据的 储备结构 和数据的 运算 这三个方面的内容；4. 数据结构按规律结构可分为两大类,它们分别是 线性结构 和 非线性结构；5. 线性结构中元素之间存在 一对一 关系, 树形结构中元素之间存在 一对多 关系, 图形结构中元素之间存在 多对多关系；6 在线性结构中,第一个结点 没有 前驱结点,其余每个结点有且只有 1 个前驱结点；最终一个结点 没有后续结点,其余每个结点有且只有 1 个后续结点；7. 在树形结构中,树根结点没有 前驱 结点,其余每个结点有且只有 1 个前驱结点；叶子结点没有 后续结点,其余每个结点的后续结点数可以 任意多个；8. 在图形结构中,每个结点的前驱结点数和后续结点数可以 任意多个；9数据的储备结构可用四种基本的储备方法表示,它们分别是 次序、 链式 、 索引 和 散列；10. 数据的运算最常用的有 5 种,它们分别是 插入 、 删除、修改、查找 、排序 ；11. 一个算法的效率可分为 时间 效率和 空间 效率；12. 在次序表中插入或删除一个元素,需要平均移动 表中一半 元素,详细移动的元素个数与 表长和该元素在表中的位置 有关；13. 线性表中结点的集合是 有限 的,结点间的关系是 一对一 的；14. 向一个长度为 n 的向量的第 i 个元素 1 i n+1 之前插入一个元素时,需向后移动 n-i+1 个元素；15. 向一个长度为 n 的向量中删除第 i 个元素 1 i n 时,需向前移动 n-i 个元素；16. 在次序表中拜访任意一结点的时间复杂度均为 O1 ,因此,次序表也称为 随机存取 的数据结构；17. 次序表中规律上相邻的元素的物理位置 必定 相邻；单链表中规律上相邻的元素的物理位置 不肯定 相邻；18在单链表中,除了首元结点外,任一结点的储备位置由 其直接前驱结点的链域的值 指示；名师归纳总结 第 1 页,共 7 页- - - - - - -精选学习资料 - - - - - - - - - 学习必备 欢迎下载19 在 n 个结点的单链表中要删除已知结点 *p,需找到它的 前驱结点的地址,其时间复杂度为 O（n）；20. 向量、栈和队列都是 线性 结构,可以在向量的 任何 位置插入和删除元素；对于栈只能在 栈顶插入和删除元素；对于队列只能在 队尾 插入和 队首 删除元素；21. 栈是一种特别的线性表,答应插入和删除运算的一端称为 栈顶；不答应插入和删除运算的一端称为栈底；22. 队列 是被限定为只能在表的一端进行插入运算,在表的另一端进行删除运算的线性表；23. 不包含任何字符（长度为 0）的串 称为空串；由一个或多个空格（仅由空格符）组成的串 称为空白串；24. 子串的定位运算称为串的模式匹配；被匹配的主串 称为目标串,子串 称为模式；25. 假设有二维数组 A6× 8,每个元素用相邻的 6 个字节储备,储备器按字节编址；已知 A 的起始储备位置（基地址）为 1000,就数组 A 的体积（储备量）为 288 B ；末尾元素 A57的第一个字节地址为 1282 ；如按行储备时,元素 A14的第一个字节地址为 8+4× 6+1000=1072 ；如按列储备时,元素 A47 的第一个字节地址为 6× 74 × 61000） 1276 ；26 由个结点所构成的二叉树有 5 种形状；27. 一棵深度为 6 的满二叉树有 n1+n2=0+ n2= n0-1=31 个分支结点和 2 6-1 =32 个叶子；注：满二叉树没有度为 1 的结点,所以分支结点数就是二度结点数；28 一棵具有个结点的完全二叉树,它的深度为 9 ；注：用 log2n+1=8.xx+1=929设一棵完全二叉树有 700 个结点,就共有 350 个叶子结点； 答：最快方法：用叶子数n/2350 30 设一棵完全二叉树具有 1000 个结点,就此完全二叉树有 500 个叶子结点,有 499 个度为 2 的结点,有 1 个结点只有非空左子树,有 0 个结点只有非空右子树；答：最快方法：用叶子数n/2500 ,n2=n0-1=499 ； 另外,最终一结点为 2i 属于左叶子,右叶子是空的,所以有 1 个非空左子树；完全二叉树的特点打算不行能有左空右不空的情形,所以非空右子树数0. 31在数据的存放无规律而言的线性表中进行检索的正确方法是 次序查找（线性查找）；32. 线性有序表（ a1,a2,a3, , a256 是从小到大排列的,对一个给定的值 k,用二分法检索表中与 k 相等的元素,在查找不胜利的情形下,最多需要检索 8 次；设有 100 个结点,用二分法查找时, 最大比较次数是 7 ；33. 假设在有序线性表 a20 上进行折半查找,就比较一次查找胜利的结点数为 1；比较两次查找胜利的结点数为2 ；比较四次查找胜利的结点数为 8 ；平均查找长度为 3.7 ；解：明显,平均查找长度O（log2n ）<5 次（ 25）；但详细是多少次,就不应当根据公式名师归纳总结 第 2 页,共 7 页- - - - - - -精选学习资料 - - - - - - - - - ASLnn1log2n1学习必备欢迎下载n2m-1 的情形来运算（即（ 21× log221 ）/20 4.6 次并不正确！ ）；由于这是在假设下推导出来的公式；应当用穷举法排列：全部元素的查找次数为（12× 24× 38× 45× 5） 74； ASL74/20=3.7 ！ 28,34折半查找有序表 （4,6,12,20,28,38,50,70,88,100）,如查找表中元素20,它将依次与表中元素6, 12,20 比较大小；35. 在各种查找方法中,平均查找长度与结点个数n 无关的查找方法是散列查找；36. 散列法储备的基本思想是由关键字的值打算数据的储备地址；二、判定正误（在正确的说法后面打勾,反之打叉）（× ） 1. 链表的每个结点中都恰好包含一个指针；答：错误；链表中的结点可含多个指针域,分别存放多个指针；例如,双向链表中的结点可以含有两个指针域,分别存放指向其直接前趋和直接后继结点的指针；（× ） 2. 链表的物理储备结构具有同链表一样的次序；错,链表的储备结构特点是无序,而链表的示意图有序；（× ） 3. 链表的删除算法很简洁,由于当删除链中某个结点后,运算机会自动地将后续的各个单元向前移动；错,链表的结点不会移动,只是指针内容转变；（× ） 4. 线性表的每个结点只能是一个简洁类型,而链表的每个结点可以是一个复杂类型；错,混淆了规律结构与物理结构,链表也是线性表！且即使是次序表,也能存放记录型数据；（× ） 5. 次序表结构相宜于进行次序存取,而链表相宜于进行随机存取；错,正好说反了；次序表才适合随机存取,链表恰恰适于“ 顺藤摸瓜”（× ） 6. 次序储备方式的优点是储备密度大,且插入、删除运算效率高；错,前一半正确, 但后一半说法错误,那是链式储备的优点；次序储备方式插入、删除运算效率较低,在表长为 n 的次序表中,插入和删除一个数据元素,平均需移动表长一半个数的数据元素；（× ） 7. 线性表在物理储备空间中也肯定是连续的；错,线性表有两种储备方式,次序储备和链式储备；后者不要求连续存放；（× ） 8. 线性表在次序储备时,规律上相邻的元素未必在储备的物理位置次序上相邻；名师归纳总结 - - - - - - -第 3 页,共 7 页精选学习资料 - - - - - - - - - 学习必备 欢迎下载错误；线性表有两种储备方式,在次序储备时,规律上相邻的元素在储备的物理位置次序上也相邻；（× ） 9. 次序储备方式只能用于储备线性结构；错误；次序储备方式不仅能用于储备线性结构,仍可以用来存放非线性结构,例如完全二叉树是属于非线性结构,但其正确储备方式是次序储备方式；（后一节介绍）（× ） 10. 线性表的规律次序与储备次序总是一样的；错,理由同 7；链式储备就无需一样；（× ） 11. 线性表的每个结点只能是一个简洁类型,而链表的每个结点可以是一个复杂类型；错,线性表是规律结构概念,可以次序储备或链式储备,与元素数据类型无关；（× ） 12. 在表结构中最常用的是线性表,栈和队列不太常用；错,不肯定吧？调用子程序或函数常用,CPU中也用队列；（） 13. 栈是一种对全部插入、删除操作限于在表的一端进行的线性表,是一种后进先出型结构；（） 14. 对于不同的使用者,一个表结构既可以是栈,也可以是队列,也可以是线性表；正确,都是线性规律结构,栈和队列其实是特别的线性表,对运算的定义略有不同而已；（× ） 15. 栈和链表是两种不同的数据结构；错,栈是规律结构的概念,是特别殊线性表,而链表是储备结构概念,二者不是同类项；（× ） 16. 栈和队列是一种非线性数据结构；错,他们都是线性规律结构,栈和队列其实是特别的线性表,对运算的定义略有不同而已；（） 17. 栈和队列的储备方式既可是次序方式,也可是链接方式；（ ）18. 两个栈共享一片连续内存空间时,为提高内存利用率,削减溢出机会,应把两个栈的栈底分别设在这片内存空间的两端；（× ） 19. 队是一种插入与删除操作分别在表的两端进行的线性表,是一种先进后出型结构；错,后半句不对；（× ） 20. 一个栈的输入序列是12345,就栈的输出序列不行能是12345；错,有可能；（） 21. 如二叉树用二叉链表作存贮结构,就在n 个结点的二叉树链表中只有n1 个非空指针域；第 4 页,共 7 页名师归纳总结 - - - - - - -精选学习资料 - - - - - - - - - 学习必备1；欢迎下载（× ） 22. 二叉树中每个结点的两棵子树的高度差等于（） 23. 二叉树中每个结点的两棵子树是有序的；（× ） 24. 二叉树中每个结点有两棵非空子树或有两棵空子树；（× ） 25. 二叉树中每个结点的关键字值大于其左非空子树（如存在的话）全部结点的关键字值,且小于其右非空子树（如存在的话）全部结点的关键字值；（应当是二叉排序树的特点）（× ） 26. 二叉树中全部结点个数是 2 k-1-1 ,其中 k 是树的深度； （应 2 i-1 ）（× ） 27. 二叉树中全部结点,假如不存在非空左子树,就不存在非空右子树；（× ） 28. 对于一棵非空二叉树,它的根结点作为第一层,就它的第 i 层上最多能有 2 i 1 个结点；（应 2 i-1 ）（） 29. 用二叉链表法 （link-rlink）储备包含 n 个结点的二叉树, 结点的 2n 个指针区域中有 n+1 个为空指针；（） 30. 具有 12 个结点的完全二叉树有 5 个度为 2 的结点；三、单项挑选题1. 非线性结构是数据元素之间存在一种：A）一对多关系 B）多对多关系 C）多对一关系 D）一对一关系2. 数据结构中,与所使用的运算机无关的是数据的 结构；A 储备 B 物理 C 规律 D 物理和储备3. 算法分析的目的是：A 找出数据结构的合理性 B 讨论算法中的输入和输出的关系C 分析算法的效率以求改进 D 分析算法的易懂性和文档性4. 算法分析的两个主要方面是：A 空间复杂性和时间复杂性 D B 正确性和简明性C 可读性和文档性数据复杂性和程序复杂性5. 运算机算法指的是：A 运算方法 B 排序方法C 解决问题的有限运算序列 D 调度方法6. 运算机算法必需具备输入、输出和等 5 个特性；A 可行性、可移植性和可扩充性 B 可行性、确定性和有穷性C 确定性、有穷性和稳固性 D 易读性、稳固性和安全性7数据在运算机储备器内表示时,物理地址与规律地址相同并且是连续的,称之为：名师归纳总结 （A）储备结构（B）规律结构（ C）次序储备结构（D）链式储备结构第 5 页,共 7 页- - - - - - -精选学习资料 - - - - - - - - - 学习必备 欢迎下载8. 一个向量第一个元素的储备地址是 100,每个元素的长度为 2,就第 5 个元素的地址是（A）110 （ B）108（C）100 （D）120 9. 在 n 个结点的次序表中,算法的时间复杂度是 O（1）的操作是：（A）拜访第 i 个结点（ 1i n）和求第 i 个结点的直接前驱（2i n）（B）在第 i 个结点后插入一个新结点（1i n）（C）删除第 i 个结点（ 1i n）（D）将 n 个结点从小到大排序10. 向一个有 127 个元素的次序表中插入一个新元素并保持原先次序不变,平均要移动 个元素（A）8 （B）63.5 （C）63 （ D）7 11. 链接储备的储备结构所占储备空间：（A）分两部分,一部分存放结点值,另一部分存放表示结点间关系的指针（B）只有一部分,存放结点值C） 只有一部分,储备表示结点间关系的指针（D） 分两部分,一部分存放结点值,另一部分存放结点所占单元数12. 链表是一种采纳 储备结构储备的线性表；（A）次序（B）链式（C）星式（D）网状13. 线性表如采纳链式储备结构时,要求内存中可用储备单元的地址 : （A）必需是连续的（B）部分地址必需是连续的（C）肯定是不连续的（D）连续或不连续都可以14 线性表在 情形下适用于使用链式结构实现；（）需常常修改中的结点值（）需不断对进行删除插入（）中含有大量的结点（）中结点结构复杂15. 栈中元素的进出原就是先进先出后进先出栈空就进栈满就出第 6 页,共 7 页16. 如已知一个栈的入栈序列是1,2,3, , n,其输出序列为p1,p2,p3, , pn,如 p1=n,就 pi 为 i n=i n-i+1不确定17. 判定一个栈ST（最多元素为m0）为空的条件是 ST->top<>0 ST->top=0 ST->top<>m0 ST->top=m0 18. 在一个图中,全部顶点的度数之和等于图的边数的倍； A1/2 B. 1 C. 2 D. 4 名师归纳总结 - - - - - - -精选学习资料 - - - - - - - - - 学习必备 欢迎下载19. 在一个有向图中,全部顶点的入度之和等于全部顶点的出度之和的 倍； A1/2 B. 1 C. 2 D. 4 20. 有 8 个结点的无向图最多有 条边； A14 B. 28 C. 56 D. 112 21. 有 8 个结点的有向完全图有 条边； A14 B. 28 C. 56 D. 112 22在表长为的链表中进行线性查找,它的平均查找长度为. ; . （） ; . n ; . （）23折半查找有序表 （4,6,10,12,20,30,50,70,88,100）；如查找表中元素 58,就它将依次与表中 比较大小,查找结果是失败；A20,70,30,50 B 30,88,70,50 C20,50 D 30,88,50 第 7 页,共 7 页24对 22 个记录的有序表作折半查找,当查找失败时,至少需要比较次关键字；A3 B 4 C 5 D 6 25. 链表适用于查找A次序 B二分法 C次序,也能二分法 D随机名师归纳总结 - - - - - - -