数据结构复习资料

第第 1 章章 绪论绪论 一 填空题一 填空题 1 数据结构是一门研究非数值计算的程序设计问题中计算机的数据结构是一门研究非数值计算的程序设计问题中计算机的以及它以及它 们之间的们之间的和和等的学科 等的学科 2 数据结构被形式地定义为 数据结构被形式地定义为 D R 其中 其中 D 是是的有限集合 的有限集合 R 是是 D 上的上的 有限集合 有限集合 3 数据结构按逻辑结构可分为两大类 它们分别是数据结构按逻辑结构可分为两大类 它们分别是和和 若细 若细 分为分为 4 类 分别是类 分别是 和和 4 线性结构中元素之间存在线性结构中元素之间存在关系 树形结构中元素之间存在关系 树形结构中元素之间存在关关 系 图形结构中元素之间存在系 图形结构中元素之间存在关系 关系 5 在线性结构中 第一个结点在线性结构中 第一个结点前驱结点 其余每个结点有且只有前驱结点 其余每个结点有且只有个个 前驱结点 最后一个结点前驱结点 最后一个结点后继结点 其余每个结点有且只有后继结点 其余每个结点有且只有个后继个后继 结点 结点 6 在树形结构中 树根结点没有在树形结构中 树根结点没有结点 其余每个结点有且只有结点 其余每个结点有且只有个前驱个前驱 结点 叶子结点没有后继结点 其余每个结点的后继结点数可以任意 结点 叶子结点没有后继结点 其余每个结点的后继结点数可以任意 7 在图形结构中 每个结点的前驱结点数和后继结点数可以在图形结构中 每个结点的前驱结点数和后继结点数可以 8 数据结构包括数据的数据结构包括数据的 数据的 数据的 和数据的和数据的 这三个方面的内容 这三个方面的内容 9 数据的存储结构可用四种基本的存储方法表示 它们分别是数据的存储结构可用四种基本的存储方法表示 它们分别是 和和 10 数据的运算最常用的有数据的运算最常用的有 5 种 它们分别是种 它们分别是 11 一个算法的效率可分为一个算法的效率可分为效率和效率和效率 效率 二 单项选择题二 单项选择题 1 数据结构中 与所使用的计算机无关的是数据的 数据结构中 与所使用的计算机无关的是数据的 结构 结构 A 存储 存储 B 物理 物理C 逻辑 逻辑D 物理和存储 物理和存储 2 算法分析的目的是 算法分析的目的是 A 找出数据结构的合理性 找出数据结构的合理性 B 研究算法中的输入和输出的关 研究算法中的输入和输出的关 系系 C 分析算法的效率以求改进 分析算法的效率以求改进 D 分析算法的易懂性和文档性 分析算法的易懂性和文档性 3 算法分析的两个主要方面是 算法分析的两个主要方面是 A 空间复杂性和时间复杂性 空间复杂性和时间复杂性 B 正确性和简明性 正确性和简明性 C 可读性和文档性 可读性和文档性 D 数据复杂性和程序复杂性 数据复杂性和程序复杂性 4 计算机算法指的是 计算机算法指的是 A 计算方法 计算方法 B 排序方法 排序方法 C 解决问题的有限运算序列 解决问题的有限运算序列 D 调度方法 调度方法 5 计算机算法必须具备输入 输出和 计算机算法必须具备输入 输出和 等 等 5 个特性 个特性 A 可行性 可移植性和可扩充性 可行性 可移植性和可扩充性 B 可行性 确定性和有穷性 可行性 确定性和有穷性 C 确定性 有穷性和稳定性 确定性 有穷性和稳定性 D 易读性 稳定性和安全性 易读性 稳定性和安全性 三 判断下列叙述的对错 三 判断下列叙述的对错 1 数据元素是数据的最小单位 数据元素是数据的最小单位 2 数据结构是数据对象与对象中数据元素之间关系的集合 数据结构是数据对象与对象中数据元素之间关系的集合 3 数据结构是具有结构的数据对象 数据结构是具有结构的数据对象 4 算法和程序原则上没有区别 在讨论数据结构时二者是通用的 算法和程序原则上没有区别 在讨论数据结构时二者是通用的 5 所谓数据的逻辑结构是指数据元素之间的逻辑关系 所谓数据的逻辑结构是指数据元素之间的逻辑关系 6 数据的逻辑结构与数据元素本身的内容和形式无关 数据的逻辑结构与数据元素本身的内容和形式无关 7 数据结构是指相互之间存在一种或多种关系的数据元素的全体 数据结构是指相互之间存在一种或多种关系的数据元素的全体 8 从逻辑关系上讲 数据结构主要分为两大类 线性结构和非线性结构 从逻辑关系上讲 数据结构主要分为两大类 线性结构和非线性结构 四 设四 设 n 为正整数为正整数 分析下列各程序段中加下划线的语句的执行次数 分析下列各程序段中加下划线的语句的执行次数 1 for int i 1 i n i for int j 1 j n j c i j 0 0 for int k 1 k n k c i j c i j a i k b k j 2 x 0 y 0 for int i 1 i n i for int j 1 j i j for int k 1 k j k x x y 2 2 n n 1 4 n n 1 n i i j n i iij 111 2n 1 12 n n 1 3 2n 1 12 n n 1 n 2 6 n 3 k 0 for i 1 i n i for j i j n j k 4 i 1 j 0 while i jj j else i 5 x n y 0 while x y 1 y 1 y 6 x 91 y 100 while y 0 if x 100 x 10 y else x 五 分析下面各程序段的时间复杂度五 分析下面各程序段的时间复杂度 2 s 0 for i 0 i n i for j 0 j n j s B i j sum s 1 for i 0 i n i for j 0 j m j A i j 0 3 x 0 for i 1 i n i for j 1 j n i j x 4 i 1 while i n i i 3 六 设有数据逻辑结构六 设有数据逻辑结构 S D R 试按各小题所给条件画出这些逻辑结构的图示 并确 试按各小题所给条件画出这些逻辑结构的图示 并确 定相对于关系定相对于关系 R 哪些结点是开始结点 哪些结点是终端结点 哪些结点是开始结点 哪些结点是终端结点 1 D d1 d2 d3 d4 R d1 d2 d2 d3 d3 d4 2 D d1 d2 d9 R d1 d2 d1 d3 d3 d4 d3 d6 d6 d8 d4 d5 d6 d7 d8 d9 3 D d1 d2 d9 R d1 d3 d1 d8 d2 d3 d2 d4 d2 d5 d3 d9 d5 d6 d8 d9 d9 d7 d4 d7 d4 d6 第二章第二章 线性表线性表 一 填空一 填空 1 在顺序表中插入或删除一个元素 需要平均移动在顺序表中插入或删除一个元素 需要平均移动 元素 具体移动的元素元素 具体移动的元素 个数与个数与 有关 有关 2 向一个长度为向一个长度为 n 的向量的第的向量的第 i 个元素个元素 1 i n 1 之前插入一个元素时 需向后移动之前插入一个元素时 需向后移动 个元素 个元素 3 向一个长度为向一个长度为 n 的向量中删除第的向量中删除第 i 个元素个元素 1 i n 时 需向前移动时 需向前移动 个元个元 素 素 4 在顺序表中访问任意一结点的时间复杂度均为在顺序表中访问任意一结点的时间复杂度均为 因此 顺序表支持 因此 顺序表支持 访问 访问 5 顺序表中逻辑上相邻的元素的物理位置顺序表中逻辑上相邻的元素的物理位置 相邻 单链表中逻辑上相邻的相邻 单链表中逻辑上相邻的 元素的物理位置元素的物理位置 相邻 相邻 6 在带头结点的非空单链表中 头结点的存储位置由在带头结点的非空单链表中 头结点的存储位置由 指示 首元素结点的存储位指示 首元素结点的存储位 置由置由 指示 除首元素结点外 其它任一元素结点的存储位置由指示 除首元素结点外 其它任一元素结点的存储位置由 指示 指示 7 在在 n 个结点的单链表中要删除已知结点个结点的单链表中要删除已知结点 p 需找到它的 需找到它的 其时间 其时间 复杂度为复杂度为 8 循环单链表循环单链表 La 中 指针中 指针 P 所指结点为表尾结点的条件是所指结点为表尾结点的条件是 9 已知已知 L 是无表头结点的单链表 且是无表头结点的单链表 且 P 结点既不是首元素结点 也不是尾元素结点 结点既不是首元素结点 也不是尾元素结点 a a 在在 P 结点后插入结点后插入 S 结点的语句序列是 结点的语句序列是 b 在在 P 结点前插入结点前插入 S 结点的语句序列是 结点的语句序列是 c 在表首插入在表首插入 S 结点的语句序列是 结点的语句序列是 d 在表尾插入在表尾插入 S 结点的语句序列是 结点的语句序列是 二 判断正误二 判断正误 1 链表的每个结点中都恰好包含一个指针 链表的每个结点中都恰好包含一个指针 2 顺序存储结构只能用来存放线性结构 链式存储结构只能用来存放非线性结构 顺序存储结构只能用来存放线性结构 链式存储结构只能用来存放非线性结构 3 链表的删除算法很简单 因为当删除链中某个结点后 计算机会自动将后续各 链表的删除算法很简单 因为当删除链中某个结点后 计算机会自动将后续各 个单元向前移动 个单元向前移动 4 线性表的每个结点只能是一个简单类型 而链表的每个结点可以是一个复杂类 线性表的每个结点只能是一个简单类型 而链表的每个结点可以是一个复杂类 型 型 5 顺序表结构适宜于进行顺序存取 而链表适宜于进行随机存取 顺序表结构适宜于进行顺序存取 而链表适宜于进行随机存取 6 顺序存储方式的优点是存储密度大 且插入 删除运算效率高 顺序存储方式的优点是存储密度大 且插入 删除运算效率高 7 线性表在物理存储空间中也一定是连续的 线性表在物理存储空间中也一定是连续的 8 线性表在顺序存储时 逻辑上相邻的元素未必在存储的物理位置次序上相邻 线性表在顺序存储时 逻辑上相邻的元素未必在存储的物理位置次序上相邻 9 顺序存储方式只能用于存储线性结构 顺序存储方式只能用于存储线性结构 10 线性表的逻辑顺序与存储顺序总是一致的 线性表的逻辑顺序与存储顺序总是一致的 三 单项选择题三 单项选择题 1 数据在计算机存储器内表示时 物理地址与逻辑地址相同并且是连续的 称之 数据在计算机存储器内表示时 物理地址与逻辑地址相同并且是连续的 称之 为 为 A 存储结构 存储结构B 逻辑结构 逻辑结构C 顺序存储结构 顺序存储结构D 链式存 链式存 储结构储结构 2 在 在 n 个结点的顺序表中 算法的时间复杂度是个结点的顺序表中 算法的时间复杂度是 O 1 的操作是 的操作是 A 访问第 访问第 i 个结点 个结点 1 i n 和求第 和求第 i 个结点的直接前驱 个结点的直接前驱 2 i n B 在第 在第 i 个结点后插入一个新结点 个结点后插入一个新结点 1 i n C 删除第 删除第 i 个结点 个结点 1 i n D 将 将 n 个结点从小到大排序个结点从小到大排序 3 链表不具有的特点是 链表不具有的特点是 A 可随机访问任一个元素 可随机访问任一个元素B 插入删除不需要移动元素 插入删除不需要移动元素 C 不必事先估计存储空间 不必事先估计存储空间 D 所需空间与线性表的长度成正比 所需空间与线性表的长度成正比 4 链接存储的存储结构所占存储空间 链接存储的存储结构所占存储空间 A 分两部分 一部分存放结点值 另一部分存放表示结点间关系的指针 分两部分 一部分存放结点值 另一部分存放表示结点间关系的指针 B 只有一部分 存放结点值 只有一部分 存放结点值 C 只有一部分 存储表示结点间关系的指针 只有一部分 存储表示结点间关系的指针 D 分两部分 一部分存放结点值 另一部分存放结点所占单元数 分两部分 一部分存放结点值 另一部分存放结点所占单元数 5 对于只在表的首 尾进行插入操作的线性表 宜采用的存储结构为 对于只在表的首 尾进行插入操作的线性表 宜采用的存储结构为 A 顺序表 顺序表 B 用头指针表示的单循环链表 用头指针表示的单循环链表 C 用尾指针表示的单循环链表 用尾指针表示的单循环链表 D 单链表 单链表 6 线性表若采用链式存储结构时 要求内存中可用存储单元的地址 线性表若采用链式存储结构时 要求内存中可用存储单元的地址 A 必须是连续的 必须是连续的 B 部分地址必须是连续的 部分地址必须是连续的 C 一定是不连续的 一定是不连续的 D 连续或不连续都可以 连续或不连续都可以 7 线性表 在 线性表 在 情况下适用于使用链式结构实现 情况下适用于使用链式结构实现 需经常修改 中的结点值 需经常修改 中的结点值 需不断对 进行删除插入 需不断对 进行删除插入 中含有大量的结点 中含有大量的结点 中结点结构复杂 中结点结构复杂 8 单链表的存储密度 单链表的存储密度 大于 大于 1 等于 等于 1 小于 小于 1 D 不能确 不能确 定定 9 设 设 a1 a2 a3 为为 3 个结点 整数个结点 整数 P0 3 4 代表地址 则如下的链式存储结代表地址 则如下的链式存储结 构称为构称为 P034 P0 a13 a24 A30 循环链表 循环链表 单链表 单链表 双向循环链表 双向循环链表D 双向链 双向链 表表 10 若线性表最常用的操作是存取第 若线性表最常用的操作是存取第 i 个元素及其前驱的值 则采用个元素及其前驱的值 则采用 存储方式存储方式 节省时间 节省时间 A 单链表 单链表B 双链表 双链表C 单循环链表 单循环链表D 顺序表 顺序表 四 简答题四 简答题 1 试比较顺序存储结构和链式存储结构的优缺点 在什么情况下用顺序表比链表好 试比较顺序存储结构和链式存储结构的优缺点 在什么情况下用顺序表比链表好 2 在单链表和单循环链表中 若仅知道指针 在单链表和单循环链表中 若仅知道指针 p 指向某一结点 不知道表头指针 能否将指向某一结点 不知道表头指针 能否将 结点结点 p 从链表中删去 若可以 其时间复杂度各为多少 从链表中删去 若可以 其时间复杂度各为多少 五 阅读分析题五 阅读分析题 指出以下算法中的错误和低效 即费时 之处 并将它改写为一个既正确又高效的算法 指出以下算法中的错误和低效 即费时 之处 并将它改写为一个既正确又高效的算法 Status DeleteK SqList 参数不合法 else for count 1 count i 1 j a elem j 1 a elem j a length return OK DeleteK 注 上题涉及的类型定义如下 define LIST INIT SIZE 100 define LISTINCREMENT 10 typedef struct Elem Type elem 存储空间基址 Int length 当前长度 Int listsize 当前分配的存储容量 SqList 六 编程题六 编程题 1 已知 已知 L 是无表头结点的单链表 且是无表头结点的单链表 且 P 结点既不是首元结点 也不是尾元结点 请写出结点既不是首元结点 也不是尾元结点 请写出 在在 P 结点后插入结点后插入 S 结点的核心语句序列 结点的核心语句序列 2 试分别以不同的存储结构实现线性表的就地逆置算法 即在原表的存储空间将线性表 试分别以不同的存储结构实现线性表的就地逆置算法 即在原表的存储空间将线性表 a1 a2 an 逆置为 逆置为 an an 1 a1 1 以顺序表作存储结构 以顺序表作存储结构 2 以单链表作存储结构 以单链表作存储结构 3 已知带有头结点的循环链表中头指针为 已知带有头结点的循环链表中头指针为 head 试写出删除并释放数据域值为 试写出删除并释放数据域值为 x 的所有的所有 结点的结点的 c 函数 函数 4 已知有单链表表示的线性表中含有三类字符的数据元素 如字母字符 数字字符和其它 已知有单链表表示的线性表中含有三类字符的数据元素 如字母字符 数字字符和其它 字符 字符 试编写算法来构造三个以循环链表表示的线性表 使每个表中只含同一类的字符 试编写算法来构造三个以循环链表表示的线性表 使每个表中只含同一类的字符 且利用原表中的结点空间作为这三个表的结点空间 头结点可另辟空间 且利用原表中的结点空间作为这三个表的结点空间 头结点可另辟空间 第三章第三章 栈和队列栈和队列 一 选择题一 选择题 1 1 一个栈的输入序列为一个栈的输入序列为 A A B B C C D D 则借助一个栈所得到的输出序列不可能的是 则借助一个栈所得到的输出序列不可能的是 A A A A B B C C D D B B D D C C B B A A C C A A C C D D B B D D D D A A B B C C 2 2 S S 最多能容纳最多能容纳 4 4 个元素 现有个元素 现有 6 6 个元素按个元素按 A A B B C C D D E E F F 的顺序进栈的顺序进栈 问下列哪一问下列哪一 个序列是可能的出栈序列个序列是可能的出栈序列 A A E E D D C C B B A A F FB B B B C C E E F F A A D D C C C C B B E E D D A A F F D D A A D D F F E E B B C C 3 3 设链式栈中结点的结构为 设链式栈中结点的结构为 data data nextnext 且 且 toptop 是指向栈顶的指针 若想在链式栈的是指向栈顶的指针 若想在链式栈的 栈顶插入一个由指针栈顶插入一个由指针 s s 所指的结点 则应执行下列哪一个操作 所指的结点 则应执行下列哪一个操作 A A top nexttop next s s B B s nexts next top nexttop next top nexttop next s s C C s nexts next toptop toptop s s D D s nexts next toptop toptop top nexttop next 4 4 一个队列的入队序列是一个队列的入队序列是 1 1 2 2 3 3 4 4 则队列的输出序列是 则队列的输出序列是 A A 4 4 3 3 2 2 1 1B B 1 1 2 2 3 3 4 4C C 1 1 4 4 3 3 2 2D D 3 3 2 2 4 4 1 1 5 5 设循环队列的结构是设循环队列的结构是 constconst intint MaxSizeMaxSize 100100 typedeftypedef intint DataTypeDataType typedeftypedef structstruct DataTypeDataType data MaxSize data MaxSize intint front front rearrear QueueQueue 若有一个若有一个 QueueQueue 类型的队列类型的队列 Q Q 试问判断队列满的条件应是下列哪一个语句 试问判断队列满的条件应是下列哪一个语句 A A Q frontQ front Q rearQ rear B B Q frontQ front Q rearQ rear MaxSizeMaxSize C C Q frontQ front Q rearQ rear MaxSizeMaxSize D D Q frontQ front Q rear 1Q rear 1 MaxSizeMaxSize 6 6 设循环队列的结构是设循环队列的结构是 constconst intint MaxSizeMaxSize 100100 typedeftypedef intint DataTypeDataType typedeftypedef structstruct DataTypeDataType data MaxSize data MaxSize intint frontfront rearrear QueueQueue 若有一个若有一个 QueueQueue 类型的队列类型的队列 Q Q 试问应用下列哪一个语句计算队列元素个数 试问应用下列哪一个语句计算队列元素个数 A A Q rearQ rear Q frontQ front MaxSizeMaxSize MaxSizeMaxSize B B Q rearQ rear Q frontQ front 1 1 C C Q rearQ rear Q frontQ front 1 1 D D Q rearQ rear QfrontQfront 7 7 以下哪一个不是队列的基本运算 以下哪一个不是队列的基本运算 A A 从队尾插入一个新元素 从队尾插入一个新元素 B B 从队列中删除第 从队列中删除第 i i 个元素个元素 C C 判断一个队列是否为空 判断一个队列是否为空 D D 读取队头元素的值 读取队头元素的值 二 简答题二 简答题 1 1 简述栈和队列的共同点和不同点 它们与线性表有什么关系 简述栈和队列的共同点和不同点 它们与线性表有什么关系 2 2 按图按图 3 1 b 3 1 b 所示铁道 两侧铁道均为单向行驶道 进行车厢调度 回答 所示铁道 两侧铁道均为单向行驶道 进行车厢调度 回答 如进站的车厢序列为如进站的车厢序列为 123123 则可能得到的出站车厢序列是什么 则可能得到的出站车厢序列是什么 如进站的车厢序列为如进站的车厢序列为 123456123456 能否得到 能否得到 435612435612 和和 135426135426 的出站序列 并说明原因 的出站序列 并说明原因 即写出以 即写出以 S S 表示进栈 以表示进栈 以 X X 表示出栈的栈操作序列 表示出栈的栈操作序列 3 3 设有一个顺序栈设有一个顺序栈 S S 元素 元素 s1 s1 s2 s2 s3 s3 s4 s4 s5 s5 s6s6 依次进栈 如果依次进栈 如果 6 6 个元素的出栈顺个元素的出栈顺 序为序为 s2 s2 s3 s3 s4 s6 s4 s6 s5 s5 s1s1 则顺序栈的容量至少应为多少 则顺序栈的容量至少应为多少 4 4 简述以下算法的功能 其中栈和队列的元素类型均为简述以下算法的功能 其中栈和队列的元素类型均为 intint 1 1 voidvoid proc 1 Stackproc 1 Stack S S intint i i n n A 255 A 255 n 0 n 0 while EmptyStack S while EmptyStack S n n Pop for i 1 for i 1 i n i1 的各棵树中 高度最小的树的高度 根结点在第 的各棵树中 高度最小的树的高度 根结点在第 1 层 是多少 层 是多少 它有多少个叶结点 多少个分支结点 高度最大的树的高度 根结点在第它有多少个叶结点 多少个分支结点 高度最大的树的高度 根结点在第 1 层 是多少 层 是多少 它有多少个叶结点 多少个分支结点 它有多少个叶结点 多少个分支结点 2 若有若有 3 个数据个数据 1 2 3 由它们构造出来的中序遍历结果都为 由它们构造出来的中序遍历结果都为 1 2 3 的不同二叉的不同二叉 树有哪些 树有哪些 3 试分别找出满足以下条件的所有二叉树 试分别找出满足以下条件的所有二叉树 1 二叉树的前序序列与中序序列相同 二叉树的前序序列与中序序列相同 2 二叉树的中序序列与后序序列相同 二叉树的中序序列与后序序列相同 3 二叉树的前序序列与后序序列相同 二叉树的前序序列与后序序列相同 4 4 在前序线索树中 要找出结点在前序线索树中 要找出结点 P 的直接后继结点 请写出有关语句 的直接后继结点 请写出有关语句 LtagLcdataRtagRc 5 在中序线索树上 要找出结点在中序线索树上 要找出结点 P 的直接后继结点 请写出相关语句 的直接后继结点 请写出相关语句 ltaglcdatartagrc 四 构造题四 构造题 1 已知一棵二叉树的前序遍历结果是已知一棵二叉树的前序遍历结果是 ABECDFGHIJ 中序遍历结果是中序遍历结果是 EBCDAFHIGJ 试画出这棵二叉树 并写出它的后序遍历序列 试画出这棵二叉树 并写出它的后序遍历序列 2 假定用于通信的电文仅由假定用于通信的电文仅由 8 个字母个字母 c1 c2 c3 c4 c5 c6 c7 c8 组成 组成 各字母在电文中出现的频度分别为各字母在电文中出现的频度分别为 5 25 3 6 10 11 36 4 试为这 试为这 8 个字个字 母设计不等长母设计不等长 Huffman 编码 编码 并给出该电文的总码数 并给出该电文的总码数 3 3 画出和下列树对应的二叉树 画出和下列树对应的二叉树 五 算法设计题五 算法设计题 1 若用二叉链表作为二叉树的存储表示 试编写递归算法 统计二叉树中叶结点的个数 若用二叉链表作为二叉树的存储表示 试编写递归算法 统计二叉树中叶结点的个数 2 若用二叉链表作为二叉树的存储表示 试编写递归算法 交换每个结点的左孩子和右若用二叉链表作为二叉树的存储表示 试编写递归算法 交换每个结点的左孩子和右 孩子 孩子 3 3 设二叉树按二叉链表存放 写算法判别一棵二叉树是否是一棵正则二叉树 正则二叉设二叉树按二叉链表存放 写算法判别一棵二叉树是否是一棵正则二叉树 正则二叉 树是指 在二叉树中不存在子树个数为树是指 在二叉树中不存在子树个数为 1 1 的结点 的结点 4 设一颗二叉树以二叉链表为存储结构 设计一个算法求此二叉树上度为设一颗二叉树以二叉链表为存储结构 设计一个算法求此二叉树上度为 1 的结点个数 的结点个数 第七章第七章 一 选择题一 选择题 1 在一个图中 所有顶点的度数之和等于所有边数的 在一个图中 所有顶点的度数之和等于所有边数的 倍 倍 A 1 2B 1C 2D 4 2 在一个有向图中 所有顶点的入度之和等于所有顶点的出度之和的 在一个有向图中 所有顶点的入度之和等于所有顶点的出度之和的 倍 倍 A 1 2B 1C 2D 4 3 一个有 一个有 n 个顶点的无向图最多有 条边 个顶点的无向图最多有 条边 A nB n n 1 C n n 1 2D 2n 4 在一个具有 在一个具有 n 个顶点的无向图中 要连通全部顶点至少需要个顶点的无向图中 要连通全部顶点至少需要 条边 条边 A n B n 1C n 1D n 2 5 对于一个具有 对于一个具有 n 个顶点的无向图 若采用邻接矩阵表示 则该矩阵的大小个顶点的无向图 若采用邻接矩阵表示 则该矩阵的大小 A nB n 1 2C n 1D n2 6 对于一个具有 对于一个具有 n 个顶点和个顶点和 e 条边的无向图 若采用邻接表表示 则表头向量的大小为条边的无向图 若采用邻接表表示 则表头向量的大小为 所有邻接表中的结点总数是 所有邻接表中的结点总数是 A nB n 1C n 1D n e A e e 2B eC 2eD n e 7 采用邻接表存储的图的深度优先遍历算法类似于二叉树的 采用邻接表存储的图的深度优先遍历算法类似于二叉树的 A 先序遍历 先序遍历B 中序遍历 中序遍历C 后序遍历 后序遍历D 按层遍历 按层遍历 8 用 用 Prim 算法求下列连通的带权图的最小代价生成树 在算法执行的某刻 已选取的顶算法求下列连通的带权图的最小代价生成树 在算法执行的某刻 已选取的顶 点集合点集合 U 1 2 3 边的集合 边的集合 TE 1 2 2 3 要选取下一条权值最小的边 要选取下一条权值最小的边 应当从应当从 组中选取 组中选取 A 1 4 3 4 3 5 2 5 B 4 5 1 3 3 5 C 1 2 2 3 3 5 D 3 4 3 5 4 5 1 4 9 下面关于工程计划的事件结点网络的叙述中 下面关于工程计划的事件结点网络的叙述中 哪一个是不正确的哪一个是不正确的 A 关键活动不按期完成就会影响整个工程的完成时间 关键活动不按期完成就会影响整个工程的完成时间 B 任何一个关键活动提前完成 任何一个关键活动提前完成 那么整个工程将会提前完成 那么整个工程将会提前完成 C 所有的关键活动都提前完成 所有的关键活动都提前完成 那么整个工程才会提前完成 那么整个工程才会提前完成 D 某些关键活动若提前完成 某些关键活动若提前完成 那么整个工程将会提前完成 那么整个工程将会提前完成 E 任何一个关键活动延迟将会导致整个工程延迟 任何一个关键活动延迟将会导致整个工程延迟 1010 任何一个无向连通图的最小生成树 任何一个无向连通图的最小生成树 A 只有一棵 只有一棵 B 有一棵或多棵 有一棵或多棵C 一定有多棵 一定有多棵 D 可能不存在 可能不存在 二 填空题二 填空题 1 在无向图的邻接矩阵在无向图的邻接矩阵 A 中 若中 若 A i j 1 则 则 A j i 2 在一个无环有向图在一个无环有向图 G 中 若存在一条从顶点中 若存在一条从顶点 i 到顶点到顶点 j 的弧 则在顶点的拓扑序列中 的弧 则在顶点的拓扑序列中 顶点顶点 i 与顶点与顶点 j 的先后次序是的先后次序是 三 判断题 三 判断题 判断下列叙述的对错 如果正确 在题前的括号内填入判断下列叙述的对错 如果正确 在题前的括号内填入 否则填入 否则填入 1 用邻接矩阵存储一个图时 在不考虑压缩存储的情况下 所占用的存储空间大小 用邻接矩阵存储一个图时 在不考虑压缩存储的情况下 所占用的存储空间大小 只与图中的顶点个数有关 而与图的边数无关 只与图中的顶点个数有关 而与图的边数无关 2 对任何用顶点表示活动的网络 对任何用顶点表示活动的网络 AOV 网 进行拓扑排序的结果都是唯一的 网 进行拓扑排序的结果都是唯一的 3 有回路的有向图不能完成拓扑排序 有回路的有向图不能完成拓扑排序 4 有 有 n n 1 个顶点的无向连通图最少有个顶点的无向连通图最少有 n 1 条边 条边 5 在一个有向图中 所有顶点的入度之和等于所有顶点的出度之和 在一个有向图中 所有顶点的入度之和等于所有顶点的出度之和 6 图图 G 的一棵最小代价树的代价一定小于该图其它任何一棵生成树的代价 的一棵最小代价树的代价一定小于该图其它任何一棵生成树的代价 7 一个无向图的邻接矩阵中各元素之和与图中边的条数相等 一个无向图的邻接矩阵中各元素之和与图中边的条数相等 四 解答题四 解答题 1 用邻接矩阵表示有向图时 若图中有用邻接矩阵表示有向图时 若图中有 1000 个顶点 个顶点 1000 条边 则形成的邻接矩阵有多条边 则形成的邻接矩阵有多 少矩阵元素 有多少非零元素 少矩阵元素 有多少非零元素 2 若已给出一个有向图的邻接矩阵 则计算第若已给出一个有向图的邻接矩阵 则计算第 i 个顶点的入度的方法是什么 删除所有从个顶点的入度的方法是什么 删除所有从 第第 i 个顶点发出的边的方法是什么 个顶点发出的边的方法是什么 3 对于如下所示的有向图 试写出 对于如下所示的有向图 试写出 1 从顶点从顶点 出发进行深度优先搜索所得到的深度优先生成树 出发进行深度优先搜索所得到的深度优先生成树 2 从顶点从顶点 出发进行广度优先搜索所得到的广度优先生成树 出发进行广度优先搜索所得到的广度优先生成树 4 以下图为例 按以下图为例 按 Dijkstra 算法计算得到的从顶点算法计算得到的从顶点 到其它各个顶点的最短路径和最到其它各个顶点的最短路径和最 短路径长度 短路径长度 5 已知如下图所示的有向图 请给出该图的 已知如下图所示的有向图 请给出该图的 1 每个顶点的入度 出度 每个顶点的入度 出度 2 邻接矩阵 邻接矩阵 3 邻接表 邻接表 4 逆邻接表 逆邻接表 5 强连通分量 强连通分量 6 已知如图所示的已知如图所示的 AOE 网 试求 网 试求 1 每个事件的最早发生时间和最晚发生时间 每个事件的最早发生时间和最晚发生时间 2 每个活动的最早开始时间和最晚开始时间 每个活动的最早开始时间和最晚开始时间 3 给出关键路径 给出关键路径 7 已知如图所示的有向网 试利用已知如图所示的有向网 试利用 Dijkstra 算法求顶点算法求顶点 1 到其余顶点的最短路径 并到其余顶点的最短路径 并 给出算法执行过程中各步的状态 给出算法执行过程中各步的状态 8 已知无向图如图已知无向图如图 1 所示 所示 1 给出图的邻接表 给出图的邻接表 2 从 从 A 开始 给出一棵广度优先生成树 开始 给出一棵广度优先生成树 五 算法设计题五 算法设计题 1 编写算法 从键盘读入有向图的顶点和弧 创建有向图的邻接表存储结构 编写算法 从键盘读入有向图的顶点和弧 创建有向图的邻接表存储结构 2 无向图采用邻接表方式存储 要求编写图的广度优先搜索算法 无向图采用邻接表方式存储 要求编写图的广度优先搜索算法 3 无向图采用邻接表方式存储 要求编写图的深度优先搜索算法 无向图采用邻接表方式存储 要求编写图的深度优先搜索算法 第九章第九章 一 选择题一 选择题 1 1 从供选择的选项中选择与下面有关查找算法的叙述中各括号相匹配的词句 将其编号从供选择的选项中选择与下面有关查找算法的叙述中各括号相匹配的词句 将其编号 填入相应的括号内 填入相应的括号内 1 1 采用顺序查找算法查找长度为采用顺序查找算法查找长度为 n n 的线性表时 元素的平均查找长度为的线性表时 元素的平均查找长度为 2 2 采用折半查找算法查找长度为采用折半查找算法查找长度为 n n 的有序表时 元素的平均查找长度应的有序表时 元素的平均查找长度应 对应判定树的最大层次数 对应判定树的最大层次数 3 3 折半查找与二叉查找树 即二叉排序树 的时间性能折半查找与二叉查找树 即二叉排序树 的时间性能 4 4 顺序查找算法适合于存储结构为顺序查找算法适合于存储结构为 的线性表 的线性表 供选择的供选择的 A A n 2n 2B B n nC C n 1n 1 2 2D D n 1n 1 2 2 A A 小于 小于B B 大于 大于C C 等于 等于D D 大于等于 大于等于 A A 相同 相同B B 不相同不相同C C 有时不相同有时不相同 A A 散列存储 散列存储B B 顺序存储或链接存储顺序存储或链接存储 C C 压缩存储 压缩存储D D 索引存储 索引存储 2 2 既希望较快的查找又便于线性表动态变化的查找方法是既希望较快的查找又便于线性表动态变化的查找方法是 A A 顺序查找 顺序查找 B B 折半查找 折半查找 C C 索引顺序查找 索引顺序查找 D D 散列法查找 散列法查找 3 3 请指出在序列请指出在序列 2 2 5 5 7 7 10 10 14 14 15 15 18 18 23 23 35 35 41 41 5252 中 用折半查找法查中 用折半查找法查 找关键码找关键码 1212 时需做多少次关键码比较时需做多少次关键码比较 A A 2 2 B B 3 3 C C 4 4 D D 5 5 4 4 对包含对包含 n n 个元素的哈希表进行查找 平均查找长度为个元素的哈希表进行查找 平均查找长度为 A A O O loglog2 2n n B B O O n n C C O O nlognlog2 2n n D D 不直接依赖于 不直接依赖于 n n 5 5 表长为表长为 2525 的哈希表 用除留余数法 即按式的哈希表 用除留余数法 即按式 H H KeyKey Key Key modmod P P 建立哈希函数 建立哈希函数 P P 应取应取 A A 2626 B B 1515 C C 2424 D D 2323 6 6 对线性表进行二分查找时对线性表进行二分查找时 要求线性表必须要求线性表必须 A A 以顺序方式存储 以顺序方式存储B B 以链接方式存储 以链接方式存储 C C 以顺序方式存储 以顺序方式存储 且结点按关键字有序排序且结点按关键字有序排序 D D 以链接方式存储 以链接方式存储 且结点按关键字有序排序且结点按关键字有序排序 7 7 有一个有序表为有一个有序表为 1 3 9 12 32 41 45 62 75 77 82 95 100 1 3 9 12 32 41 45 62 75 77 82 95 100 当二分查找值为当二分查找值为 8282 的结的结 点时点时 次比较后查找成功 次比较后查找成功 A A 1 1 B B 2 2 C C 4 4 D D 8 8 8 8 设哈希表长设哈希表长 m 14 m 14 哈希函数哈希函数 H H keykey key 11 key 11 表中已有 表中已有 4 4 个结点个结点 addraddr 1515 4 4 addraddr 3838 5 5 addraddr 6161 6 6 addraddr 8484 7 7 其余地址为空 如用二次探测再散列处理 其余地址为空 如用二次探测再散列处理 冲突冲突 关键字为关键字为 4949 的结点的地址是的结点的地址是 A A 8 8 B B 3 3 C C 5 5 D D 9 9 9 9 有一个长度为有一个长度为 1212 的有序表的有序表 按二分查找法对该表进行查找按二分查找法对该表进行查找 在表内各元素等概率情况下在表内各元素等概率情况下 查找成功所需的平均比较次数为查找成功所需的平均比较次数为 A A 35 1235 12B B 37 1237 12 C C 39 1239 12 D D 43 1243 12 1010 采用分块查找时采用分块查找时 若线性表中共有若线性表中共有 625625 个元素个元素 查找每个元素的概率相同查找每个元素的概率相同 假设采用假设采用 顺序查找来确定结点所在的块时顺序查找来确定结点所在的块时 每块应分每块应分 个结点最佳 个结点最佳 A A 1010 B B 2525 C C 6 6 D D 625625 1111 设有一个长度为设有一个长度为 100100 的已排好序的表 用二分查找进行查找 若查找不成功 至的已排好序的表 用二分查找进行查找 若查找不成功 至 少比较少比较 次 次 A A 9 9 B B 8 8 C C 7 7 D D 6 6 1212 AVLAVL 树是一种平衡的二叉排序树 树中任一结点的树是一种平衡的二叉排序树 树中任一结点的 A A 左 右子树的高度均相同 左 右子树的高度均相同 B B 左 右子树高度差的绝对值不超过 左 右子树高度差的绝对值不超过 1 1 C C 左子树的高度均大于右子树的高度 左子树的高度均大于右子树的高度 D D 左子树的高度均小于右子树的高度 左子树的高度均小于右子树的高度 二 填空题二 填空题 1 1 设一哈希表表长设一哈希表表长 M M 为为 100100 用除留余数法构造哈希函数 即 用除留余数法构造哈希函数 即 H H K K K K MODMOD P P P MP M 为使函数具有较好性能 为使函数具有较好性能 P P 应选应选 2 2 在分块查找方法中在分块查找方法中 首先查找首先查找 然后再查找相应的然后再查找相应的 3 3 长度为长度为 255255 的表的表 采用分块查找法采用分块查找法 每块的最佳长度是每块的最佳长度是 4 4 假设在有序线性表假设在有序线性表 A 1 20 A 1 20 上进行二分查找上进行二分查找 则比较一次查找成功的结点数为则比较一次查找成功的结点数为 则比较二次查找成功的结点数为则比较二次查找成功的结点数为 则比较三次查找成功的结点数为则比较三次查找成功的结点数为 则比则比 较四次查找成功的结点数为较四次查找成功的结点数为 则比较五次查找成功的结点数为则比较五次查找成功的结点数为 平均查找平均查找 长度为长度为 5 5 在查找方法中 平均查找长度与结点个数无关的查找方法是在查找方法中 平均查找长度与结点个数无关的查找方法是 6 6 对于长度为对于长度为 n n 的线性表的线性表 若进行顺序查找若进行顺序查找 则时间复杂度为则时间复杂度为 若采用二分法查 若采用二分法查 找找 则时间复杂度为则时间复杂度为 若采用分块查找 假定总块数和每块长度均接近 若采用分块查找 假定总块数和每块长度均接近 则时间则时间 复杂度为复杂度为 7 7 己知一个有序表为 己知一个有序表为 12 18 20 25 29 32 40 62 83 90 95 9812 18 20 25 29 32 40 62 83 90 95 98 当二分查找值为当二分查找值为 2929 和和 9090 的元素时的元素时 分别需要分别需要 次和次和 次比较才能查找成功 若采用顺序查找时次比较才能查找成功 若采用顺序查找时 分别分别 需要需要 次和次和 次比较才能查找成功 次比较才能查找成功 8 8 假设假设 hashhash x x 为哈希函数 解决冲突用线性探测再散列法 为哈希函数 解决冲突用线性探测再散列法 typedeftypedef RecordTypeRecordType HashTable HashTable m m intint HashSearchHashSearch HashTableHashTable ht ht KeyTypeKeyType K K p0p0 ifif ht ht p0p0 keykey NULLKEYNULLKEY returnreturn 1 1 elseelse ifif ht ht p0p0 keykey K K returnreturn p0p0 elseelse forfor i 1 i 1 i i i i pipi p0p0 m m ifif ht ht pipi keykey NULLKEYNULLKEY returnreturn 1 1 elseelse ifif ht ht pipi keykey returnreturn pipi returnreturn 1 1 9 9 对二叉排序树进行对二叉排序树进行 遍历遍历 可得到结点的有序排列可得到结点的有序排列 三 简答题三 简答题 1 1 什么情况下二叉排序树的查找性能较好 什么情况下二叉排序树的查找性能最差 什么情况下二叉排序树的查找性能较好 什么情况下二叉排序树的查找性能最差 2 2 画出对长度为画出对长度为 1010 的有序表进行折半查找的判定树 并求其等概率时查找成功的平均的有序表进行折半查找的判定树 并求其等概率时查找成功的平均 查找长度 查找长度 3 3 选取哈希函数选取哈希函数H H k k 3 3k k 11 11 用线性探测再散列法处理冲突 试在 用线性探测再散列法处理冲突 试在 0 0 1010 的散的散 列地址空间中 对关键字序列 列地址空间中 对关键字序列 2222 4141 5353 4646 3030 1313 0101 6767 构造哈希表 并求等 构造哈希表 并求等 概率情况下查找成功与不成功时的平均查找长度 概率情况下查找成功与不成功时的平均查找长度 4 4 已知长度为已知长度为 1212 的表 的表 Jan Feb Mar Apr May June July Aug Sep Oct Nov DecJan