数据结构练习2(线性表)

数据结构基础练习 线性表 数据结构基础练习 线性表 一 选择题一 选择题 1 算法的时间复杂度取决于 A A 问题的规模 B 变量的多少 C 问题的难度 D A 和 B 2 算法能正确的实现预定功能的特性为算法的 A A 正确性 B 易读性 C 健壮性 D 高效性 3 数据的物理结构主要包含 A 这几种结构 A 顺序结构和链表结构 B 线性结构和非线 性结构 C 动态结构和静态结构 D 集合 线性结构 树形结构 图形结构 4 数据在计算机内存中的表示是指 A A 数据的存储结构 B 数据结构 C 数据的逻辑结构 D 数据元素之间的 关系 5 数据结构被形式化定义为二元组 D S 其中 D 是 B 的有限集合 A 算法B 数据元素C 数据操作D 数据关系 6 算法效率的度量是 D A 正确度和简明度B 数据复杂 度和程序复杂度 C 高的速度和正确度D 时间复杂度和空间复杂度 7 在下列存储结构中 最适合实现在线性表中进行随机访问的是 A A 数组 B 双向链表 C 单向链表 D 循环链表 8 与单链表相比 双链表的优点之一是 D A 可以由最后一个结点找到头结点 B 可随机访问 C 插入 删除操作更加简单 D 访问前驱结 点更加方便 9 如果对线性表的运算只有 2 种 即删除第一个元素 在最后一 个元素的后面插入新元素 则最好使用 D A 顺序表 B 单链表C 双向链表 D 具有表尾指针的循环单链表 10 在表头指针为 head 且表长大于 1 的单向循环链表中 指针 p 指向表中的某个结点 若 p next next head 则 D A p 指向头结点 B p 指向尾结点 C p 的直接后继是头结点 D p 的直接后 继是尾结点 11 带表头附加结点的单链表 head 为空的判断条件是 C A head NULL B head next NULL C head next head D head NULL 12 对线性表 在下列情况下应当采用链表表示的是 B A 经常需要随机地存取元素 B 经常需要进行插入和删除操作 C 表中元素需要占据一片连续的存储空间 D 表中的元素个数不变 13 如果最常用的操作是取第 i 个结点及前驱 则采用 A 存储方式最节省时间 A 顺序表 B 双链表 C 单循环链表 D 单链表 14 可以用带表头附加结点的链表表示线性表 也可以用不带表头 附加结点的链表表示线性表 前者最主要的好处是 B A 可以加快对表的遍历 B 使空表和非空 表的处理统一 C 节省存储空间 D 可以提高存取 表元素的速度 15 一个顺序表所占存储空间的大小与 D 无关 A 顺序表长度 B 结点类型 C 结点中个数据域的类型 D 结点的存放次序 16 从一个具 n 个结点的单链表中查找其值等于 x 的结点时 在查 找成功的情况下 需平均比较 D 个结点 A n B n 2 C n 1 2 D n 1 2 17 单链表中 q 在前 p 在后的指向相邻的两个结点 要在 q p 之 间插入 s 所指的结点应是 D A s next p next p next s B p next s next s next p C p next s s next q D q next s s next p 18 不带表头附加结点的单链表 head 为空的判断条件是 B A head next NULL B head NULL C head next head D head NULL 19 一个循环单链表中 若要在指针 q 所指结点的后面插入一个由 指针 P 所指向的结点 则执行 D A q next p p next q next B p next q next q p C q next p next p next q D p next q next q next p 20 在循环双链表的指针 p 所指结点之前插入指针 q 所指结点的操 作是 D A p left q q right p p left right q q left p left B p left q p left right q q right p q left p left C q right p q left p left p left q p left right q D q right p q left p left p left right q p left q 二 算法设计题二 算法设计题 1 设有一个顺序表 L 其元素为整型数据 下列算法将 L 中所有小 于 0 的整数放在前半部分 大于 0 的整数放在后半部分 提示 从 L 的两端查找 前端找大于 0 的数据 后端找小于 0 的数据 然后 将两位置的数据交换 void MoveList SeqList while i j while L list i 0 j if inext if p NULL cout 线性表为空 操作无效 data while p NULL if p data max max p data p p next return max 3 设 h 为不带头结点的单链表 写出和下列递归过程等价的非递 归程序 void func LNode h if h NULL func h next cout data 算法的功能 逆序输出链表各结点的信息 void func LNode while q NULL r q next q next p p q q r h p 4 编写一个在带头结点的单链表中删除一个最小值节点的算法 假 设该链表中每个节点的值不重复 bool DeleteMin LNode LNode m n if q NULL cerr 线性表为空 操作无效 data while q NULL if q datadata m p n q else p q q q next m next n next return true 5 假设有一个循环链表的长度大于 1 且表中既无头结点也无头指