数据结构课后练习第2章.ppt

第二章线性表 2 1线性表的类型定义2 2线性表的顺序表示和实现2 3线性表的链式表示和实现2 4一元多项式的表示及相加 学习要点 了解线性表的逻辑结构特性 即数据元素之间存在着线性关系 在计算机中表示这种关系两类不同的存储结构 顺序存储结构和链式存储结构 用前者表示的线性表简称为顺序表 用后者表示的线性表简称为链表 熟练掌握这两类存储结构的描述方法 如一维数组中一个区域 i j 的上 下界和长度之间的变换公式 L j i 1 i j L 1 j i L 1 链表中指针p和结点 p的对应关系 结点 p next 是结点 p的后继等 链表中头结点 头指针和首元结点 第一个元素的结点 的区别及循环链表 双向链表的特点等 链表是本章的重点和难点 掌握指针操作和内存动态分配的编程技术 学习要点 熟练掌握在顺序存储结构上线性表的基本操作 如查找 插入和删除的算法 熟练掌握在各种链表结构中线性表的基本操作 能在实际应用中选用适当的链表结构 能够从时间与空间复杂度方面综合比较线性表两种存储结构的不同特点及其适用场合 一 判断对错题 1 线性表中的元素可以是各种各样的 但同一线性表中的数据元素具有相同的特性 因此属于同一数据对象 2 线性表的链式存储结构优于顺序存储 3 在单链表中 任何两个元素的存储位置之间都有固定的联系 所以可以从头结点开始查找任何一个元素 4 顺序存储的线性表可以实现随机存取 二 单项选择题 1 用单链表方式存储的线性表 存储每个结点需要两个域 一个数据域 另一个是 A 当前结点所在的地址域B 指针域C 空指针域D 空闲域2 在具有n个结点的单链表中 实现 的操作 其算法的时间复杂度都是O n A 遍历链表和求链表的第i个结点B 在地址为p的结点之后插入一个结点C 删除开始结点D 删除地址为p的结点的后继结点 B A 二 单项选择题 3 已知一个顺序存储的线性表 设每个结点需占m个存储单元 若第一个结点的地址为da1 则第i个结点的地址为 A da1 i 1 mB da1 i mC da1 i mD da1 i 1 m4 在n个结点的顺序表中 算法的时间复杂度是O 1 的操作是 A 访问第i个结点 1 i n 和求第i个结点的直接前驱 2 i n B 在第i个结点之后插入一个新结点 1 i n C 删除第i个结点 1 i n D 将n个结点从小到大排序 A A 二 单项选择题 5 两个指针p和q 分别指向单链表的两个元素 p所指元素是q所指元素前驱的条件是 A p next q nextB p next qC q next pD p q B 三 填空题 1 在链表中逻辑上相邻的元素的物理位置 相连 2 在n个结点的顺序表中删除一个结点平均需要移动 个结点 具体的移动次数取决于 3 在单链表中要在已知结点 p之前插入一个新结点 需找到 不一定 n 1 2 顺序表的长度与被删元素在表中的位序 结点 p的直接前驱结点 的地址 四 简答题 1 简述线性表的存储结构及各自的优点 何时选用顺序表 何时选用链表作为线性表的存储结构为宜 从空间上来看 当线性表的长度变化较大 难以估计其规模时 选用动态的链表作为存储结构比较合适 但链表除了需要设置数据域外 还要额外设置指针域 因此当线性表长度变化不大 易于事先确定规模时 为了节约存储空间 宜采用顺序存储结构 四 简答题 1 简述线性表的存储结构及各自的优点 何时选用顺序表 何时选用链表作为线性表的存储结构为宜 从时间上来看 若线性表的操作主要是查找 很少进行插入和删除操作时 应选用顺序表 对于频繁进行插入和删除操作的线性表 宜采用链表作为存储结构 四 简答题 2 什么是头指针 头结点 首元结点 首元结点 链表中存储的线性表中的第一个数据元素的结点 头结点 为了操作的方便 通常在链表的首元结点之前附设一个结点 称头结点 头指针 指向链表中的第一个结点 或为头结点或为首元结点 的指针 四 简答题 3 在顺序表中插入和删除一个结点需平均移动多少个结点 具体的移动次数取决于哪两个因素 插入结点 移动元素次数n i 1 删除结点 移动元素次数n i 决定因素 顺序表的长度以及插入 删除元素在表中的位序 4 分析下述三个算法的具体功能 ListNode Demo1 LinkListL ListNode p L是有头结点的单链表ListNode q L next while q 算法功能 寻找 p结点的直接前驱结点 q 4 分析下述三个算法的具体功能 voidDemo2 ListNode p ListNode q p q是链表中的两个结点DataTypetemp temp p data p data q data q data temp 算法功能 p结点和 q结点的值互换 4 分析下述三个算法的具体功能 LinkListtest1 LinkListL L是无头结点的单链表LinkList q p if L 算法功能 如果表长度大于1 则将首元结点删除并插入到表尾 或者可以这么说 把表 a1 a2 ai an 改成 a2 a3 ai an a1 5 设有多项式 请画出的单链表存储表示 设 求得并画出的单链表存储表示 五 程序设计题 1 对给定的带头结点的单链表L 编写一个删除L中值为x的结点的直接前驱结点的算法 StatusListDelete L LinkListL ElemTypex 在带头结点的单链表L中 删除值为x的结点 LNode p q p L while p next 线性表的结构定义 线性表的动态分配顺序存储结构 defineLIST INIT SIZE100 顺序表的初始分配量 defineLISTINCREMENT10 顺序表的分配增量typedefstruct ElemType elem 存储空间基址 即数组的起始地址intlength 顺序表的当前长度 实际的元素个数intlistsize 当前分配的存储容量 以sizeof ElemType 为单位 SqList 2 将一个顺序表中从第i个结点开始的k个结点删除 StatusListDelete Sq SqList 从最后一个元素开始 if k q p 1 第i个元素后的所有元素均被删除 L length i 1 returnOK elsefor k 1 k 1 k for p p q p p 1 p 到第i 1个元素平移p L length q L elem L length 1 returnOK 返回删除元素成功标志 有没有更快的方法 比如若干元素依次前移k位 如何实现 五 程序设计题 3 设顺序表L是一个递增 允许有相同的值 有序表 试写一算法将x插入L中 并使L仍为一个有序表 3 设链表L是一个递增 允许有相同的值 有序表 试写一算法将x插入L中 并使L仍为一个有序表 算法分析 先找到x的正确插入位置 插入位i的确定 然后在链表中最后一个小于或等于x的元素结点以及第一个大于x的元素结点之间插入新的元素结点x 单链表的插入操作 StatusLinkListInsert LinkListL ElemTypex 在升序链表L 带头结点 中插入一个新元素结点xq L p q next 找到插入位置while p NULL LinkListInsert 线性单链表存储结构 typedefstructLNode ElemTypedata 数据域structLNode next 指针域 LNode LinkList LinkList应该为指向线性单链表结点的指针 结束