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

《2022年数据结构知识点复习资料.docx》由会员分享，可在线阅读，更多相关《2022年数据结构知识点复习资料.docx（8页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、精选学习资料 - - - - - - - - - 学习必备 欢迎下载数据结构复习资料一、填空题1. 数据结构是一门讨论非数值运算的程序设计 问题中运算机的 操作对象 以及它们之间的 关系 和运 算 等的学科；2. 数据结构被形式地定义为（D, R ）,其中 D是 数据元素 的有限集合,R是 D上的 关系 有限集合；3. 数据结构包括数据的 规律结构、数据的 储备结构 和数据的 运算 这三个方面的内容；4. 数据结构按规律结构可分为两大类,它们分别是 线性结构 和 非线性结构；5. 线性结构中元素之间存在 一对一 关系, 树形结构中元素之间存在 一对多 关系, 图形结构中元素之间存在 多对多关系

2、；6 在线性结构中,第一个结点 没有 前驱结点,其余每个结点有且只有 1 个前驱结点；最终一个结点 没有后续结点,其余每个结点有且只有 1 个后续结点；7. 在树形结构中,树根结点没有 前驱 结点,其余每个结点有且只有 1 个前驱结点；叶子结点没有 后续结点,其余每个结点的后续结点数可以 任意多个；8. 在图形结构中,每个结点的前驱结点数和后续结点数可以 任意多个；9数据的储备结构可用四种基本的储备方法表示,它们分别是 次序、 链式 、 索引 和 散列；10. 数据的运算最常用的有 5 种,它们分别是 插入 、 删除、修改、查找 、排序 ；11. 一个算法的效率可分为 时间 效率和 空间 效率

3、；12. 在次序表中插入或删除一个元素,需要平均移动 表中一半 元素,详细移动的元素个数与 表长和该元素在表中的位置 有关；13. 线性表中结点的集合是 有限 的,结点间的关系是 一对一 的；14. 向一个长度为 n 的向量的第 i 个元素 1 i n+1 之前插入一个元素时,需向后移动 n-i+1 个元素；15. 向一个长度为 n 的向量中删除第 i 个元素 1 i n 时,需向前移动 n-i 个元素；16. 在次序表中拜访任意一结点的时间复杂度均为 O1 ,因此,次序表也称为 随机存取 的数据结构；17. 次序表中规律上相邻的元素的物理位置 必定 相邻；单链表中规律上相邻的元素的物理位置

4、不肯定 相邻；18在单链表中,除了首元结点外,任一结点的储备位置由 其直接前驱结点的链域的值 指示；名师归纳总结 第 1 页,共 7 页- - - - - - -精选学习资料 - - - - - - - - - 学习必备 欢迎下载19 在 n 个结点的单链表中要删除已知结点 *p,需找到它的 前驱结点的地址,其时间复杂度为 O（n）；20. 向量、栈和队列都是 线性 结构,可以在向量的 任何 位置插入和删除元素；对于栈只能在 栈顶插入和删除元素；对于队列只能在 队尾 插入和 队首 删除元素；21. 栈是一种特别的线性表,答应插入和删除运算的一端称为 栈顶；不答应插入和删除运算的一端称为栈底；2

5、2. 队列 是被限定为只能在表的一端进行插入运算,在表的另一端进行删除运算的线性表；23. 不包含任何字符（长度为 0）的串 称为空串；由一个或多个空格（仅由空格符）组成的串 称为空白串；24. 子串的定位运算称为串的模式匹配；被匹配的主串 称为目标串,子串 称为模式；25. 假设有二维数组 A6 8,每个元素用相邻的 6 个字节储备,储备器按字节编址；已知 A 的起始储备位置（基地址）为 1000,就数组 A 的体积（储备量）为 288 B ；末尾元素 A57的第一个字节地址为 1282 ；如按行储备时,元素 A14的第一个字节地址为 8+4 6+1000=1072 ；如按列储备时,元素 A

6、47 的第一个字节地址为 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 的

7、结点,有 1 个结点只有非空左子树,有 0 个结点只有非空右子树；答：最快方法：用叶子数n/2500 ,n2=n0-1=499 ； 另外,最终一结点为 2i 属于左叶子,右叶子是空的,所以有 1 个非空左子树；完全二叉树的特点打算不行能有左空右不空的情形,所以非空右子树数0. 31在数据的存放无规律而言的线性表中进行检索的正确方法是 次序查找（线性查找）；32. 线性有序表（ a1,a2,a3, , a256 是从小到大排列的,对一个给定的值 k,用二分法检索表中与 k 相等的元素,在查找不胜利的情形下,最多需要检索 8 次；设有 100 个结点,用二分法查找时, 最大比较次数是 7 ；33.

8、 假设在有序线性表 a20 上进行折半查找,就比较一次查找胜利的结点数为 1；比较两次查找胜利的结点数为2 ；比较四次查找胜利的结点数为 8 ；平均查找长度为 3.7 ；解：明显,平均查找长度O（log2n ）top0 ST-top=0 ST-topm0 ST-top=m0 18. 在一个图中,全部顶点的度数之和等于图的边数的倍； A1/2 B. 1 C. 2 D. 4 名师归纳总结 - - - - - - -精选学习资料 - - - - - - - - - 学习必备 欢迎下载19. 在一个有向图中,全部顶点的入度之和等于全部顶点的出度之和的 倍； A1/2 B. 1 C. 2 D. 4 20

9、. 有 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随机名师归纳总结 - - - - - - -