数据结构(c语言版)复习资料.pdf
19 浏览量
2024-04-26
22:31:06
上传
评论
收藏 178KB PDF 举报
1
数据结构复习资料
一、填空题
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. 在顺序表中访问任意一结点的时间复杂度均为 O(1) ，因此，顺序表也称为 随机存取 的数据结构。
17. 顺序表中逻辑上相邻的元素的物理位置 必定相邻。单链表中逻辑上相邻的元素的物理位置 不一定
相邻。
18．在单链表中，除了首元结点外，任一结点的存储位置由 其直接前驱结点的链域的值 指示。
19． 在 n 个结点的单链表中要删除已知结点*p，需找到它的前驱结点的地址，其时间复杂度为 O（n）。
20. 向量、栈和队列都是 线性 结构，可以在向量的 任何 位置插入和删除元素；对于栈只能在
栈顶 插入和删除元素；对于队列只能在 队尾 插入和 队首 删除元素。
资源评论
