北航10秋学期《算法与数据结构》模拟题二

北北航航1 10 0 秋秋学学期期 算算法法与与数数据据结结构构 模模拟拟题题 二二 一 单项选择题 本大题共一 单项选择题 本大题共 1515 小题 每小题小题 每小题 2 2 分 共分 共 3030 分 分 1 下列关于栈的叙述正确的是 A 栈是非线性结构 B 栈是一种树状结构 C 栈具有先进先出的特征 D D 栈具有后进先出的特征栈具有后进先出的特征 2 以下关于数据的存储结构的叙述哪一条是正确的 A 数据的存储结构是数据间关系的抽象描述 B B 数据的存储结构是逻辑结构在计算机存储器中的实现数据的存储结构是逻辑结构在计算机存储器中的实现 C 数据的存储结构分为线性结构和非线性结构 D 数据的存储结构对数据运算的具体实现没有影响 3 线性链表不具有的特点是 A A 随机访问随机访问 B 不必事先估计所需存储空间大小 C 插入与删除时不必移动元素 D 所需空间与线性表长度成正比 4 向二叉排序树中插入一个元素时 其时间复杂度大致为 A A O log2n O log2n 其中其中 2 2 是底数是底数 B O n C O 1 D O n log2n 其中 2 是底数 5 向一个有 127 个元素的顺序表中插入一个新元素并保持原来顺序不变 平均要移动 个元素 A 8 B B 63 563 5 C 64 D 7 6 一个队的入队序列是 1 2 3 4 则队列的输出序列是 A 4 3 2 1 B B 1 1 2 2 3 3 4 4 C 1 4 3 2 D 3 2 1 4 7 下列数据组织形式中 的各个结点可以任意邻接 A 集合 B 树形结构 C 线性结构 D D 图状结构图状结构 8 在含 n 个顶点和 e 条边的无向图的邻接矩阵中 零元素的个数为 A e B 2e C n 的平方 e D D n n 的平方 的平方 2e2e 9 由权值分别为 3 6 7 2 5 的叶子结点生成一棵哈夫曼树 它的带权路径长度为 A 23 B B 5151 C 53 D 74 10 线性表是一个具有 n 个 的有限序列 A 表元素 B 字符 C C 数据元素数据元素 D 数据项 11 已知二叉树后序遍历序列是 dabec 中序遍历序列是 debac 它的前序遍历序列是 A acbed B decab C deabc D D cedbacedba 12 下列数据结构中 能用折半查找的是 A A 顺序存储的有序线性表顺序存储的有序线性表 B 线性链表 C 二叉链表 D 有序线性链表 13 完成堆排序的全过程需要 个纪录大小的辅助空间 A A 1 1 B n C nlog2n D nlog2n 14 下列说法正确的是 A A 树的先根遍历序列与其对应的二叉树的先根遍历序列相同 树的先根遍历序列与其对应的二叉树的先根遍历序列相同 B 树的先根遍历序列与其对应的二叉树的后根遍历序列相同 C 树的后根遍历序列与其对应的二叉树的先根遍历序列相同 D 树的后根遍历序列与其对应的二叉树的后根遍历序列相同 15 下列说法中正确的是 A 任何一棵二叉树中至少有一个结点的度为 2 B 任何一棵二叉树中每个结点的度都为 2 C 任何一棵二叉树中的度肯定等于 2 D D 任何一棵二叉树中的度可以小于 任何一棵二叉树中的度可以小于 2 2 二 判断题 本大题共二 判断题 本大题共 1010 小题 每小题小题 每小题 1 1 分 共分 共 1010 分 分 16 链式栈与顺序栈相比 一个明显的优点是通常不会出现栈满的情况 17 在一个顺序存储的循环队列中 队头指针指向队头元素的后一个位置 18 栈和队列都是顺序存取的线性表 但它们对存取位置的限制不同 19 在使用后缀表示实现计算器类时用到一个栈的实例 它的作用是暂存运算器对象 20 在用循环单链表表示的链式队列中 可以不设队头指针 仅在链尾设置队尾指针 21 若让元素 1 2 3 依次进栈 则出栈次序 1 3 2 是不可能出现的情况 22 在用单链表表示的链式队列 Q 中 队头指针为 Q front 队尾指针为 Q rear 则队空条件为 Q front Q rear 23 递归定义的数据结构通常用递归算法来实现对它的操作 24 递归的算法简单 易懂 容易编写 而且执行效率也高 25 递归调用算法与相同功能的非递归算法相比 主要问题在于重复计算太多 而且调用本身需要分配 额外的空间和传递数据和控制 所以时间与空间开销通常都比较大 三 填空题 本大题共三 填空题 本大题共 6 6 小题 每空小题 每空 2 2 分 共分 共 3030 分 分 26 在线性表的散列存储中 若用 m 表示散列表的长度 n 表示待散列存储的元素的个数 则装填因子 a 等于 n mn m 27 对于顺序表的插入算法 insert sqlist 来说 若以结点移动为标准操作 则插入算法的最坏时间复 杂性为 n n 量级是 O n O n 插入算法的平均时间复杂性为 n 2n 2 平均时间复杂性量级是 O n O n 28 以下为直接插入排序的算法 请分析算法 并在 上填充适当的语句 void straightsort list r for i 2 2 i n i r 0 r i j i 1 while r 0 key 逻辑结构逻辑结构 存储结构存储结构 31 一个有顺序表有 255 个对象 采用顺序搜索法查表 平均搜索长度为 128128 四 简答与应用题 本大题共四 简答与应用题 本大题共 5 5 小题 每小题小题 每小题 6 6 分 共分 共 3030 分 分 32 算法的设计要求有哪些 考核知识点 算法设计要求 参见 P13 14 答 1 正确性 2 可读性 3 健壮性 4 效率与低存储量需求 每一个再简单描述下即可 33 请用类 C 语言描述双链表的类型定义 并予以解释说明 考核知识点 双链表的类型定义 参见 P35 39 答 typedef struct dnode dpointer struct dnode datatype data dpointer prior next typedaf dpinter dlklist 链域 prior 和 next 分别指向本结点数据域 data 所含数据元素的直接前趋和直接后继所在的结点 所有结点通过前趋和后继指针链接在一起 再加上起标识作用的头指针 就得到双向循环链表 34 图的存储有几种方式 考核知识点 图的存储结构 参见 161 167 答 1 数组表示法 2 邻接表表示法 3 十字链表 4 链接多重表 每一种分别描述下即可 35 简述开散列表的组织方式及类型定义 考核知识点 散列表 参见 P251 263 答 开散列表的组织方式如下 设选定的散列函数为 H H 的值域 即散列地址的集合 为 0 n 1 设置一个 地址向量 pointer HP n 其中的每个指针 HP i 指向个单链表用于存储所有散列地 址为 i 的数据元素 即所有散列地址为 ii 的同义词 每一个样的单链表称为一个同义词子表 由地址向 量以及向量中的每个指针所指的同义词子表构成存储结构称为开散列表 这种开散列解决冲突的方法又 称 拉链法 开散列表类型定义如下 typedef struct tagnode keytype key struct tagnode next 其他其他域 pinter nod tyedef poiner openhah n 36 01 02 03 04 05 06 07 08 09 10 11 12 13 14 15 16 006 087 155 188 220 465 505 508 511 586 656 670 700 766 897