20151910042-刘鹏-DSA思考题-06 - list abstraction1
需积分: 0 33 浏览量
2022-08-08
20:46:07
上传
评论
收藏 22KB DOCX 举报
云南大学数学与统计学院信息与计算科学
1 / 1
数据结构与算法
思考题
课程名称：数据结构与算法实验
年级：2015 级
成绩：
指导教师：陆正福
姓名：刘鹏
上机实践名称：表的抽象
学号：20151910042
日期：2017-07-03
思考题编号：No.06
组号：01-01
时间：上午 3、4 节
查阅资料，思考并回答下述问题：
1. 什 么 是 数 组 表 （ array list ） 或 向 量
（vector）？
答：数组表是一种概念，向量是一种数学概念。
2. 解释数组表的基本运算（提示：基于 index
的插删改取）。
答：按 index 进行存取。
3. 从概念上来讲，数组表与数组有何区别？
答：前者是一种概念，后者是一种实际的结构。
4. 数组实现的数组表中，分析实现插入和删除
操作的算法的时间复杂度。
答：常量。
5. 什么是位置（position）？
答：有相关变量存储位置。
6. 什么是结点表（node list）？
答：链表之类的，节点为元素，串起来。
7. 解释结点表的基本运算（提示：定位操作,移
位操作，基于 position 的插删改取）
答：
8. 一个非法位置（invalid position）通常会有哪
些情形？
答：
9. 删除一个节点通常需要释放存储资源。在
C/C++/Java 语言中是如何做到的？
答：free
10. 在双链表实现的结点表中，给出插入操作的
伪代码。
答：在 a，b 之间插入，需要先申请地址；然后 a
的下一个元素为 c，c 的下一个元素为 b。伪代码
基本如是。
11. 在双链表实现的结点表中，给出删除操作的
伪代码。
答：
12. ＊以可扩展数组为例，解释分摊设计模式。
答：必须是指数型的增长。常量增长最后时假的
分摊。
13. 课本第六章与课本第三章之间的联系。
答：根据第三章的知识，设计复杂度较低的结构。
14. 解释课本第五章的栈结构、队列结构、双端
队列结构与课本第六章的表结构之间的联系。
答：
评论0