第2章测试题(1)

一 选择题 1 从一个具有 n 个结点的单链表中查找值为 x 的结点 在查找成功情况下 需平均比较 d n 个节点 单链表 如果 x 等于第一个元素的值 则要比较 1 次 x 等于第二个元素的值 则要比较 2 次 最不巧 x 值刚好等于第 n 个元素 则要比较 x 次 所以总次数是 1 2 3 n 1 n n 1 n 2 所以平均需要 n 1 2 次 顺序数组可以用折半查找 需要 log2 为低 N 次个结点 A nB n 2C n 1 2D n 1 2 2 a 插入 删除速度快 但查找速度慢 链表只需要修改前驱或者前驱与后继的指针就可以 查找时链表需要顺序查找 并且由于 读取指针耗费时间 A 链表B 顺序表C 有序顺序表D 上述三项无法比较 3 若希望从链表中快速确定一个结点的前驱 则链表最好采用 c 方式 双链表在结点前驱后继查找上的时间复杂度是 O 1 A 单链表B 循环单链表C 双向链表D 任意 4 在一个单链表中 若删除 p 所指结点的后继结点 则执行 d p next 指向 p 指针的后继结点 p next next 指向后继结点的后继结点 A p next p nextB p p next next C p p next p next p next next D p next p next next 5 带头结点的单链表 head 为空的判定条件是 b A head NULLB head next NULL C head next headD head NULL 6 在循环双向链表的 p 所指结点之后插入 s 所指结点的操作是 d A p next s s prior p p next prior s s next p next B p next s p next prior s s prior p s next p next C s prior p s next p next p next s p next prior s D s prior p s next p next p next prior s p next s 7 若某线性表最常用的操作是存取任一指定序号的元素和在最后进行插入和删除运算 则 利用 a 存储方式最节省时间 想要存取任一指定序号的元素 链表实现这个功能的代价很大 本来顺序表的弱点在于插入和删除元素 但是题目要求只最后进行插入和删除运算 所有 顺序表是最好的选择 A 顺序表B 双向链表C 带头结点的双循环链表 D 单循环链表 二 填空题 1 对于采用顺序存储结构的线性表 当随机插入或删除一个数据元素时 平均约需移动表 中 一半 元素 2 当对一个线性表经常进行的是插入和删除操作时 采用 链式 存储结构为宜 因为采用链式结构存储线性表 插入和删除操作需要从头结点起查找被插入或删除结点的 前驱结点 并修改这些结点的指针域 查找过程平均移动指针域为表长的一半 3 当对一个线性表经常进行的是存取操作 而很少进行插入和删除操作时 最好采用 顺序 存储结构 它的特点是逻辑关系上相邻的两个元素在物理位置上也相邻 因此可以随机存取表中任一 元素 它的存储位置可用一个简单 直观的公式来表示 4 在一个长度为 n 的顺序存储结构的线性表中 向第 i 个元素 1 i n 1 之前插入一 个新元素时 需向后移动 n i 1 个元素 这道题 可以进行举例来验证 比如要是在第一个元素前插入元素 需要移动 n 个元素 i 1 时 需要移动 n 个 进行验证 5 从长度是 n 的采用顺序存储结构的线性表中删除第 i 个元素 1 i n 需向前移动 n i 个元素 6 对于长度是 n 的顺序存储结构的线性表 插入或删除元素的时间复杂度为 0 n 7 在具有 n 个结点的有序单链表中插入一个新结点并仍然有序的时间复杂度是 0 n 因为单链表保存的信息只有表头 如果要在特定位置插入一个节点 需要先从表头一路找到 那个节点 这个过程是 O n 的 8 在双向链表中 每个结点共有两个指针域 一个指向 前驱 结点 另一个则 指向 后继 结点 三 判断题 1 链表中的头结点仅起到标识的作用 f 头结点的数据域还可以存储一些必要的数据 如表长 2 顺序存储结构的主要缺点是不利于插入和删除操作 t 3 线性表采用链表存储时 结点和结点内部的存储空间可以是不连续的 f 结点内部空间是连续的 4 顺序存储方式插入和删除时效率太低 因此它不如链式存储方式好 f 还有其他比较参数 如空间利用率 难易程度 存取快捷等 5 对任何数据结构链表存储结构一定优于顺序存储结构 f 还有其他比较参数 如空间利用率 难易程度 存取快捷等 6 顺序存储方式只能用于存储线性结构 f 也可用于树 二叉树等 7 循环链表不是线性表 f 8 为了很方便地插入和删除数据 可以使用双向链表存放数据 t 9 线性表的特点是每个元素都有一个前驱和一个后继 f 第一个结点无前驱 最后一个结点无后继 10 取线性表的第 i 个元素的时间与 i 的大小有关 f 看线性表的存储机构 链表有关 顺序表无关 四 应用题 1 线性表有两种存储结构 一是顺序表 二是链式表 试问 如果有 n 个线性表同时并存 并且在处理过程中各表的长度会动态变化 线性表的总数 也会自动地改变 在此情况下 应选用哪种存储结构 为什么 链表 理由是链表能够高效的执行插入删除操作 适用于元素变化较多的情形 若线性表的总数基本稳定 且很少进行插入和删除 但要求以最快的速度存取线性表中 的元素 那么应采用哪种存储结构 为什么 顺序存储结构 顺序表可以随机存取 时间复杂度为 O 1 2 线性表的顺序存储结构具有三个弱点 其一 在进行插入或删除操作时 需移动大量元 素 其二 由于难以估计 必须预先分配较大的空间 往往使存储空间不能得到充分的利 用 线性表的链式存储结构是否一定都能克服以上缺点 试讨论之 链式存储结构一般说克服了顺序存储结构的三个弱点 首先 插入 删除不需移动元素 只修改指针 时间复杂度为 O 1 其次 不需要预先分配空间 可根据需要动态申请空间 其三 表容量只受可用内存空间的限制 其缺点是因为指针增加了空间开销 当空间不允 许时 就不能克服顺序存储的缺点 3 线性表 a1 a2 an 用顺序映射表示时 ai和 ai 1 1 inext p p p next e p data for q p next q if e q data s q p next q next q q next free s else q q next 2 将数据元素 x 插入到递增有序的顺序表的适当位置 使插入后的顺序表仍为递增有序 struct list p q s head p head while p NULL if x p data q p p p next else s struct list malloc sizeof struct list s data x q next s s next p 3 假设有两个按元素值递增次序排列的线性表 均以单链表形式存储 请编写算法将这 两个单链表归并为一个按元素值递减次序排列的单链表 并要求利用原来两个单链表 的结点存放归并后的单链表 include stdio h include malloc h struct list int data struct list next struct list head1 head2 p1 p2 q1 q2 void main int n 0 void unionlist p1 q1 struct list malloc sizeof struct list printf 请输入第一个链表的信息 n scanf d while p1 data 0 n n 1 if n 1 head1 q1 else q1 next p1 q1 p1 p1 struct list malloc sizeof struct list scanf d q1 next NULL n 0 p2 q2 struct list malloc sizeof struct list printf 请输入第二个链表的信息 n scanf d while p2 data 0 n n 1 if n 1 head2 q2 else q2 next p2 q2 p2 p2 struct list malloc sizeof struct list scanf d q2 next NULL unionlist void unionlist struct list head p int i 0 p1 head1 p2 head2 head p struct list malloc sizeof struct list p data 0 while p1 p p1 p1 p1 next else p next p2 p p2 p2 p2 next p next p1 p1 p2 p head printf 合并后的链表为如下 n while p i i 1 if i 1 p p next printf 3d p data p p next printf n free head1 free head2 4 已知递增有序的两个单链表 A B 分别存储了一个集合 设计算法实现求两个集合的 并集的运算 A A B 无头链表 define data data int include head h struct LNode char data 10 int data struct LNode next typedef struct LNode LinkList void InitList L LinkList L next NULL void PrintList L LinkList L L next while 1 cout data value is data next if L NULL return void Insert L LinkList LinkList p L int i 0 if n 0 n 1 while p next NULL p p next n else if n 1 cout error endl return for i 0 inext NULL cout error next p new LNode cout p data p next L next L next p LinkList bing LinkList LinkList a LinkList b LinkList c LinkList nc LinkList t InitList L c nc c a a next while a NULL 复制 a 到 c t new LNode t data a data nc next t t next NULL nc nc next a a next b b next while b NULL nc c while nc next NULL if nc next data b data break nc nc next if nc next NULL t new LNode t data b data nc next t t next NULL nc nc next b b next return c void main LinkList a b c int i 0 InitList L a co