admin 管理员组文章数量: 1086019
2024年4月21日发(作者：float的短语)
数据结构复习题
一、填空题
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）；还有一种时间复杂度为O(1)的巧妙删除方法，即把p的后继结点中数据拷贝到
p结点中，然后删除p的后继结点，删除语句应该是q=p->next; p->next=q->next;free(q);。
20. 向量、栈和队列都是 线性 结构，可以在向量的 任何 位置插入和删除元素；
对于栈只能在 栈顶 插入和删除元素；对于队列只能在 队尾 插入和 队首
删除元素。
21. 栈是一种特殊的线性表，允许插入和删除运算的一端称为 栈顶 。不允许插入和删
除运算的一端称为 栈底 。
22. 队列 是被限定为只能在表的一端进行插入运算，在表的另一端进行删除运算的线
性表。
23. 不包含任何字符（长度为0）的串 称为空串； 由一个或多个空格（仅由空格符）
组成的串 称为空白串。
24. 子串的定位运算称为串的模式匹配； 被匹配的主串 称为目标串， 子串 称为模
式。
25. 假设有二维数组A
6
×
8
，每个元素用相邻的6个字节存储，存储器按字节编址。已知A的
起始存储位置（基地址）为1000，则数组A的体积（存储量）为 288 B ；末尾元素
A
57
的第一个字节地址为 1282 ；若按行存储时，元素A
14
的第一个字节地址为 (8+4)
×6+1000=1072 ；若按列存储时，元素A
47
的第一个字节地址为 (6×7＋4)×6＋1000）
＝1276 。
26． 由３个结点所构成的二叉树有 5 种形态。
版权声明：本文标题：数据结构 复习题 内容由网友自发贡献，该文观点仅代表作者本人， 转载请联系作者并注明出处：http://www.roclinux.cn/p/1713679559a646634.html， 本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌抄袭侵权/违法违规的内容，一经查实，本站将立刻删除。
发表评论