数据结构习题线性表
17页1、第 2 章 线性表 课后习题讲解 1. 填空 在顺序表中,等概率情况下,插入和删除一个元素平均需移动( )个元素,具体移动元素的个数与( )和( )有关。【解答】表长的一半,表长,该元素在表中的位置 顺序表中第一个元素的存储地址是100,每个元素的长度为2,则第5个元素的存储地址是( )。【解答】108【分析】第5个元素的存储地址=第1个元素的存储地址(51)2=108 设单链表中指针p 指向结点A,若要删除A的后继结点(假设A存在后继结点),则需修改指针的操作为( )。【解答】p-next=(p-next)-next 单链表中设置头结点的作用是( )。【解答】为了运算方便【分析】例如在插入和删除操作时不必对表头的情况进行特殊处理。 非空的单循环链表由头指针head指示,则其尾结点(由指针p所指)满足( )。【解答】p-next=head【分析】如图2-8所示。 在由尾指针rear指示的单循环链表中,在表尾插入一个结点s的操作序列是( );删除开始结点的操作序列为( )。【解答】s-next =rear-next; rear-next =s; rear =s;q=rear-next-n
2、ext; rear-next-next=q-next; delete q;【分析】操作示意图如图2-9所示: 一个具有n个结点的单链表,在指针p所指结点后插入一个新结点的时间复杂度为( );在给定值为x的结点后插入一个新结点的时间复杂度为( )。【解答】(1),(n)【分析】在p所指结点后插入一个新结点只需修改指针,所以时间复杂度为(1);而在给定值为x的结点后插入一个新结点需要先查找值为x的结点,所以时间复杂度为(n)。 可由一个尾指针唯一确定的链表有( )、( )、( )。【解答】循环链表,循环双链表,双链表2. 选择题 线性表的顺序存储结构是一种( )的存储结构,线性表的链接存储结构是一种( )的存储结构。 A 随机存取 B 顺序存取 C 索引存取 D 散列存取【解答】A,B【分析】参见2.2.1。 线性表采用链接存储时,其地址( )。A 必须是连续的 B 部分地址必须是连续的C 一定是不连续的 D 连续与否均可以【解答】D【分析】线性表的链接存储是用一组任意的存储单元存储线性表的数据元素,这组存储单元可以连续,也可以不连续,甚至可以零散分布在内存中任意位置。 单循环链表的主要优
3、点是( )。A 不再需要头指针了 B 从表中任一结点出发都能扫描到整个链表;C 已知某个结点的位置后,能够容易找到它的直接前趋;D 在进行插入、删除操作时,能更好地保证链表不断开。【解答】B 链表不具有的特点是( )。A 可随机访问任一元素 B 插入、删除不需要移动元素C 不必事先估计存储空间 D 所需空间与线性表长度成正比【解答】A 若某线性表中最常用的操作是取第i 个元素和找第i个元素的前趋,则采用( )存储方法最节省时间。A 顺序表 B 单链表 C 双链表 D 单循环链表【解答】A【分析】线性表中最常用的操作是取第i 个元素,所以,应选择随机存取结构即顺序表,同时在顺序表中查找第i个元素的前趋也很方便。单链表和单循环链表既不能实现随机存取,查找第i个元素的前趋也不方便,双链表虽然能快速查找第i个元素的前趋,但不能实现随机存取。 若链表中最常用的操作是在最后一个结点之后插入一个结点和删除第一个结点,则采用( )存储方法最节省时间。A 单链表 B 带头指针的单循环链表 C 双链表 D 带尾指针的单循环链表【解答】D【分析】在链表中的最后一个结点之后插入一个结点需要知道终端结点的地址,
4、所以,单链表、带头指针的单循环链表、双链表都不合适,考虑在带尾指针的单循环链表中删除第一个结点,其时间性能是O(1),所以,答案是D 。 若链表中最常用的操作是在最后一个结点之后插入一个结点和删除最后一个结点,则采用( )存储方法最节省运算时间。A 单链表 B 循环双链表 C单循环链表 D 带尾指针的单循环链表【解答】B【分析】在链表中的最后一个结点之后插入一个结点需要知道终端结点的地址,所以,单链表、单循环链表都不合适,删除最后一个结点需要知道终端结点的前驱结点的地址,所以,带尾指针的单循环链表不合适,而循环双链表满足条件。 在具有n个结点的有序单链表中插入一个新结点并仍然有序的时间复杂度是( )。A O(1) B O(n) C O(n2) D O(nlog2n)【解答】B【分析】首先应顺序查找新结点在单链表中的位置。 对于n个元素组成的线性表,建立一个有序单链表的时间复杂度是( )。A O(1) B O(n) C O(n2) D O(nlog2n)【解答】C【分析】该算法需要将n个元素依次插入到有序单链表中,而插入每个元素需O(n)。 使用双链表存储线性表,其优点是可以( )。A
《数据结构习题线性表》由会员新**分享,可在线阅读,更多相关《数据结构习题线性表》请在金锄头文库上搜索。
回迁安置房建设开工奠基仪式县领导致欢迎辞
2022年大学毕业实习工作总结
污水处理达标承诺书
辽宁省沈阳市中等学校招生考试模拟语文试卷十五
第一次旅程作文
绿化施工组织设计1
副部长竞选演讲稿范文
在中国移动公司实习的报告
2023年河南省三门峡市灵宝市阳平镇香什村社区工作人员考试模拟题含答案
升降压斩波电路matlab仿真
南开大学22春《平面设计方法与技术》补考试题库答案参考99
幼儿园教育笔记《老师我爱你》
生命生命教学设计 (1)
新建年产50000台小型工程运输车项目建议书写作模板立项备案审批
农村生活污水处理站建设总结
油库规章制度
艾滋病性病基本知识
大盘精选证券投资基金年度报告摘要
住宅工程质量通病防治专项技术方案设计(DOC 31页)
金属非金属矿山安全检查作业(露天矿山)安全生产考前(难点+易错点剖析)押密卷附答案35
2023-11-02 3页
2023-05-09 1页
2022-08-13 8页
2022-07-27 14页
2023-01-13 3页
2023-03-09 3页
2023-12-22 4页
2022-12-01 3页
2022-11-30 4页
2023-03-30 5页