数据结构习题答案[高等教育]

《数据结构习题答案[高等教育]》由会员分享，可在线阅读，更多相关《数据结构习题答案[高等教育]（41页珍藏版）》请在金锄头文库上搜索。

1、习题 1 一 单项选择题 1 数据结构是指 A 数据元素的组织形式B 数据类型 C 数据存储结构D 数据定义 2 数据在计算机存储器内表示时 物理地址与逻辑地址不相同的 称之为 A 存储结构B 逻辑结构 C 链式存储结构D 顺序存储结构 3 树形结构是数据元素之间存在一种 A 一对一关系B 多对多关系 C 多对一关系D 一对多关系 4 设语句 x 的时间是单位时间 则以下语句的时间复杂度为 for i 1 i n i for j i j n j x 1 2 n n 3 n 5 算法分析的目的是 1 算法分析的两个主要方面是 2 1 A 找出数据结构的合理性B 研究算法中的输入和输出关系 C 分

2、析算法的效率以求改进D 分析算法的易懂性和文档性 2 A 空间复杂度和时间复杂度B 正确性和简明性 C 可读性和文档性D 数据复杂性和程序复杂性 6 计算机算法指的是 1 它具备输入 输出和 2 等五个特性 1 A 计算方法B 排序方法 C 解决问题的有限运算序列D 调度方法 2 A 可行性 可移植性和可扩充性B 可行性 确定性和有穷性 C 确定性 有穷性和稳定性D 易读性 稳定性和安全性 7 数据在计算机内有链式和顺序两种存储方式 在存储空间使用的灵活性上 链式存 储比顺序存储要 A 低B 高C 相同D 不好说 8 数据结构作为一门独立的课程出现是在 年 B 1953 9 数据结构只是研究数

3、据的逻辑结构和物理结构 这种观点 A 正确B 错误 C 前半句对 后半句错D 前半句错 后半句对 10 计算机内部数据处理的基本单位是 A 数据B 数据元素C 数据项D 数据库 二 填空题 1 数据结构按逻辑结构可分为两大类 分别是 和 2 数据的逻辑结构有四种基本形态 分别是 和 3 线性结构反映结点间的逻辑关系是 的 非线性结构反映结点间 的逻辑关系是 的 4 一个算法的效率可分为 效率和 效率 5 在树型结构中 树根结点没有 结点 其余每个结点的有且只有 个前趋驱结点 叶子结点没有 结点 其余每个结 点的后续结点可以 6 在图型结构中 每个结点的前趋结点数和后续结点数可以 7 线性结构中

4、元素之间存在 关系 树型结构中元素之间存在 关系 图型结构中元素之间存在 关系 8 下面程序段的时间复杂度是 for i 0 i n i for j 0 j n j A i j 0 9 下面程序段的时间复杂度是 i s 0 while s n i s i 10 下面程序段的时间复杂度是 s 0 for i 0 i n i for j 0 j n j s B i j sum s 11 下面程序段的时间复杂度是 i 1 while i n i i 3 12 衡量算法正确性的标准通常是 13 算法时间复杂度的分析通常有两种方法 即 和 的方法 通 常我们对算法求时间复杂度时 采用后一种方法 三 求下

5、列程序段的时间复杂度 1 x 0 for i 1 i n i for j i 1 j n j x 2 x 0 for i 1 i n i for j 1 j n i j x 3 int i j k for i 0 i n i for j 0 j n j c i j 0 for k 0 k 0 return i 5 fact n if n 1 return 1 else return n fact n 1 习题 1 参考答案 一 单项选择题 1 A 2 C 3 D 4 B 5 C A 6 C B 7 B 8 D 9 B 10 B 二 填空题 1 线性结构 非线性结构 2 集合 线性 树 图 3

6、一对一 一对多或多对多 4 时间 空间 5 前趋 一 后继 多 6 有多个 7 一对一 一对多 多对多 8 O 2 n 9 O n 10 O 2 n 11 O log3n 12 程序对于精心设计的典型合法数据输入能得出符合要求的结果 13 事后统计 事前估计 三 算法设计题 1 O 2 n 2 O 2 n 3 O n 3 4 O n 5 O n 习题 2 一 单项选择题 1 线性表是 A 一个有限序列 可以为空B 一个有限序列 不可以为空 C 一个无限序列 可以为空D 一个无限序列 不可以为空 2 在一个长度为n 的顺序表中删除第i 个元素 0 inext s s prior p p next

7、 prior s s next p next B s prior p s next p next p next s p next prior s C p next s p next prior s s prior p s next p next D s prior p s next p next p next prior s p next s 6 设单链表中指针p 指向结点m 若要删除m 之后的结点 若存在 则需修改指针 的操作为 A p next p next next B p p next C p p next next D p next p 7 在一个长度为n 的顺序表中向第i 个元素

8、0 inext p next p next s B q next s s next p C p next s next s next p D p next s s next q 9 以下关于线性表的说法不正确的是 A 线性表中的数据元素可以是数字 字符 记录等不同类型 B 线性表中包含的数据元素个数不是任意的 C 线性表中的每个结点都有且只有一个直接前趋和直接后继 D 存在这样的线性表 表中各结点都没有直接前趋和直接后继 10 线性表的顺序存储结构是一种 的存储结构 A 随机存取B 顺序存取C 索引存取D 散列存取 11 在顺序表中 只要知道 就可在相同时间内求出任一结点的存储地址 A 基地址

9、B 结点大小 C 向量大小D 基地址和结点大小 12 在等概率情况下 顺序表的插入操作要移动 结点 A 全部B 一半 C 三分之一D 四分之一 13 在 运算中 使用顺序表比链表好 A 插入B 删除 C 根据序号查找D 根据元素值查找 14 在一个具有n 个结点的有序单链表中插入一个新结点并保持该表有序的时间复杂 度是 A O 1 B O n C O n2 D O log2n 15 设有一个栈 元素的进栈次序为A B C D E 下列是不可能的出栈序列 A A B C D E B B C D E A C E A B C D D E D C B A 16 在一个具有n 个单元的顺序栈中 假定以地

10、址低端 即 0 单元 作为栈底 以 top 作为栈顶指针 当做出栈处理时 top 变化为 A top 不变B top 0 C top D top 17 向一个栈顶指针为hs 的链栈中插入一个s 结点时 应执行 A hs next s B s next hs hs s C s next hs next hs next s D s next hs hs hs next 18 在具有 n 个单元的顺序存储的循环队列中 假定front 和 rear 分别为队头指针和 队尾指针 则判断队满的条件为 A rear n front B front l n rear C rear n 1 front D re

11、ar l n front 19 在具有 n 个单元的顺序存储的循环队列中 假定front 和 rear 分别为队头指针和 队尾指针 则判断队空的条件为 A rear n front B front l rear C rear front D rear l n front 20 在一个链队列中 假定 front 和 rear 分别为队首和队尾指针 则删除一个结点的操 作为 A front front next B rear rear next C rear front next D front rear next 二 填空题 1 线性表是一种典型的 结构 2 在一个长度为n 的顺序表的第i 个元

12、素之前插入一个元素 需要后移 个元素 3 顺序表中逻辑上相邻的元素的物理位置 4 要从一个顺序表删除一个元素时 被删除元素之后的所有元素均需 一个位 置 移动过程是从 向 依次移动每一个元素 5 在线性表的顺序存储中 元素之间的逻辑关系是通过 决定的 在线性表的 链接存储中 元素之间的逻辑关系是通过 决定的 6 在双向链表中 每个结点含有两个指针域 一个指向 结点 另一个指向 结点 7 当对一个线性表经常进行存取操作 而很少进行插入和删除操作时 则采用 存储结构为宜 相反 当经常进行的是插入和删除操作时 则采用 存储结构为宜 8 顺序表中逻辑上相邻的元素 物理位置 相邻 单链表中逻辑上相邻的元

13、素 物理位置 相邻 9 线性表 栈和队列都是 结构 可以在线性表的 位置插入和删除元素 对于栈只能在 位置插入和删除元素 对于队列只能在 位置插入元素和在 位置删除元素 10 根据线性表的链式存储结构中每个结点所含指针的个数 链表可分为 和 而根据指针的联接方式 链表又可分为 和 11 在单链表中设置头结点的作用是 12 对于一个具有n 个结点的单链表 在已知的结点p 后插入一个新结点的时间复杂 度为 在给定值为x 的结点后插入一个新结点的时间复杂度为 13 对于一个栈作进栈运算时 应先判别栈是否为 作退栈运算时 应先判别 栈是否为 当栈中元素为m 时 作进栈运算时发生上溢 则说明栈的可用最大

14、容 量为 为了增加内存空间的利用率和减少发生上溢的可能性 由两个栈共享一片连 续的内存空间时 应将两栈的 分别设在这片内存空间的两端 这样只有当 时才产生上溢 14 设有一空栈 现有输入序列1 2 3 4 5 经过 push push pop push pop push push 后 输出序列是 15 无论对于顺序存储还是链式存储的栈和队列来说 进行插入或删除运算的时间复 杂度均相同为 三 简答题 1 描述以下三个概念的区别 头指针 头结点 表头结点 2 线性表的两种存储结构各有哪些优缺点 3 对于线性表的两种存储结构 如果有 n 个线性表同时并存 而且在处理过程中各表 的长度会动态发生变化

15、线性表的总数也会自动改变 在此情况下 应选用哪一种存储结 构为什么 4 对于线性表的两种存储结构 若线性表的总数基本稳定 且很少进行插入和删除操 作 但要求以最快的速度存取线性表中的元素 应选用何种存储结构试说明理由 5 在单循环链表中设置尾指针比设置头指针好吗为什么 6 假定有四个元素A B C D依次进栈 进栈过程中允许出栈 试写出所有可能的出栈 序列 7 什么是队列的上溢现象一般有几种解决方法 试简述之 8 下述算法的功能是什么 LinkList Demo LinkList L 设计在无头结点的单链表中删除第i 个结点的算法 2 在单链表上实现线性表的求表长ListLength L 运算

16、 3 设计将带表头的链表逆置算法 4 假设有一个带表头结点的链表 表头指针为head 每个结点含三个域 data next 和 prior 其中 data 为整型数域 next 和 prior 均为指针域 现在所有结点已经由next 域连 接起来 试编一个算法 利用prior 域 此域初值为NULL 把所有结点按照其值从小到大 的顺序链接起来 5 已知线性表的元素按递增顺序排列 并以带头结点的单链表作存储结构 试编写一 个删除表中所有值大于min 且小于 max 的元素 若表中存在这样的元素 的算法 6 已知线性表的元素是无序的 且以带头结点的单链表作为存储结构 设计一个删除 表中所有值小于max 但大于 min 的元素的算法 7 假定用一个单循环链表来表示队列 也称为循环队列 该队列只设一个队尾指针 不设队首指针 试编写下列各种运算的算法 1 向循环链队列插入一个元素值为x 的结点 2 从循环链队列中删除一个结点 8 设顺序表L 是一个递减有序表 试写一算法 将x 插入其后仍保持L的有序性 习题 2 参考答案 一 单项选择题 1 A 2 A 3 D 4 C 5 D 6 A 7 B 8