数据结构(本科)期末综合练习一(单选题).pdf

数据结构 本科 期末综合练习一 单选题 单选题 1 一个数组元素a i 与 的表示等价 A a i B a i C a i D i m i for int j 0 j n j a i j i j A O m2 B O n2 C O m n D O m n 4 执行下面程序段时 执行S语句的次数为 for int i 1 i n i for int j 1 jlink NULL C first link first D first NULL 29 带头结点的单链表first为空的判定条件是 A first NULL B first link NULL C first link first D first NULL 30 设单链表中结点的结构为 data link 已知指针q所指结点是指针p所指结点 的直接前驱 若在 q与 p之间插入结点 s 则应执行的操作是 A s link p link p link s B q link s s link p C p link s link s link p D p link s s link q 31 设单链表中结点的结构为 data link 已知指针p所指结点不是尾结点 若 在 p之后插入结点 s 则应执行的操作是 A s link p p link s B p link s s link p C s link p link p s D s link p link p link s 32 设单链表中结点的结构为 data link 若想摘除p link所指向的结点 则 应执行的操作是 A p link p link link B p p link p link p link link C p link p D p p link link 33 非空的循环单链表first的尾结点 由p所指向 满足的条件是 A p link NULL B p NULL C p link first D p first 34 设单循环链表中结点的结构为 data link 且rear是指向非空的带表头结点 的单循环链表的尾结点的指针 若想删除链表第一个结点 则应执行的操作是 A s rear rear rear link delete s B rear rear link delete rear C rear rear link link delete rear D s rear link link rear link link s link delete s 35 从一个具有n个结点的单链表中查找其值等于x结点时 在查找成功的情况下 需 要平均比较的结点数是 A n B n 2 C n 1 2 D n 1 2 36 在一个具有n个结点的有序单链表中插入一个新结点并仍然保持有序的时间复杂 度是 A O 1 B O n C O n2 D O nlog2n 37 给定有n个元素的向量 建立一个有序单链表的时间复杂度是 A O 1 B O n C O n2 D O nlog2n 38 单链表A长度为m 单链表B长度为n 若将B联接在A的末尾 其时间复杂度应为 A O 1 B O m C O n D O m n 39 利用双向链表作线性表的存储结构的优点是 A 便于单向进行插入和删除的操作 B 便于双向进行插入和 删除的操作 C 节省空间 D 便于销毁结构释放空 间 40 带表头的双向循环链表的空表满足 A first NULL B first rLink first C first lLink NULL D first rLink NULL 41 已知L是一个不带表头的单链表 在表首插入结点 p的操作是 A p L p link L B p link L p L C p link L L p D L p p link L 42 已知L是带表头的单链表 删除首元结点的语句是 A L L link B L link L link link C L L D L link L 43 栈的插入和删除操作在 进行 A 栈顶 B 栈底 C 任意位置 D 指定位置 44 当利用大小为n的数组顺序存储一个栈时 假定用top n表示栈空 则向这个栈 插入一个元素时 首先应执行 语句修改top指针 A top B top C top 0 D top 45 若让元素1 2 3依次进栈 则出栈次序不可能出现 种情况 A 3 2 1 B 2 1 3 C 3 1 2 D 1 3 2 46 在一个顺序存储的循环队列中 队头指针指向队头元素的 位置 A 前一个 B 后一个 C 当前 D 后面 47 当利用大小为n的数组顺序存储一个队列时 该队列的最大长度为 A n 2 B n 1 C n D n 1 48 从一个顺序存储的循环队列中删除一个元素时 首先需要 A 队头指针加一 B 队头指针 减一 C 取出队头指针所指的元素 D 取出队尾指针所指的元素 49 假定一个顺序存储的循环队列的队头和队尾指针分别为front和rear 则判断队 空的条件为 A front 1 rear B rear 1 front C front 0 D front rear 50 假定一个链式队列的队头和队尾指针分别为front和rear 则判断队空的条件为 A front rear B front NULL C rear NULL D front NULL 51 设链式栈中结点的结构为 data link 且top是指向栈顶的指针 若想在链 式栈的栈顶插入一个由指针s所指的结点 则应执行 操作 A top link s B s link top link top link s C s link top top s D s link top top top link 52 设链式栈中结点的结构为 data link 且top是指向栈顶的指针 若想摘除 链式栈的栈顶结点 并将被摘除结点的值保存到x中 则应执行 操作 A x top data top top link B top top link x top data C x top top top link D x top data 53 设循环队列的结构是 typedef struct DataType data MaxSize int front rear Queue 若有一个Queue类型的队列Q 试问判断队列满的条件应为 A Q front Q rear B Q front Q rear MaxSize C Q front Q rear MaxSize D Q front Q rear 1 MaxSize 54 设循环队列的结构是 const int MaxSize 100 typedef int DataType typedef struct DataType data MaxSize int front rear Queue 若有一个Queue类型的队列Q 则应用 表达式计算队列元素的个数 A Q rear Q front MaxSize MaxSize B Q rear Q front 1 C Q rear Q front 1 D Q rear Qfront 55 为增加内存空间的利用率和减少溢出的可能性 由两个栈共享一块连续的内存空 间时 应将两栈的 分别设在这块内存空间的两端 A 长度 B 深度 C 栈顶 D 栈底 56 递归是将一个较复杂的 规模较大的 问题转化为一个稍为简单的 规模较小 的 与原问题 的问题来解决 使之比原问题更靠近可直接求解的条件 A 相关 B 子类型相关 C 同类型 D 不相关 57 递归调用时系统需要利用一个 来实现数据的传递和控制的转移 A 队列 B 优先级队列 C 双端队列 D 栈 58 在系统实现递归调用时需利用递归工作记录保存 当递归调用程序执 行结束时通过它将控制转到上层调用程序 A 调用地址 B 递归入口 C 返回地址 D 递归出口 59 在递归执行过程中 当前执行的递归函数过程的递归工作记录一定是递归工作栈 中的栈顶记录 称之为 记录 A 活动 B 当前 C 日志 D 标记 60 将递归求解过程改变为非递归求解过程的目的是 A 提高速度 B 改善可读性 C 增强健壮性 D 提高可维护性 61 如果一个递归函数过程中只有一个递归语句 而且它是过程体的最后语句 则这 种递归属于 它很容易被改写为非递归过程 A 单向递归 B 回溯递归 C 间接递归 D 尾递归 62 设有一个递归算法如下 int fact int n n大于等于0 if n 0 return 1 else return n fact n 1 则计算fact n 需要函数调用的次数为 次 A n B n 1 C n 2 D n 1 63 设有一个递归算法如下 int X int n if n 0 的结点 其 双亲结点的编号为 A i 1 2 B i 1 2 C i 2 D i 2 1 79 在一棵树的左子女 右兄弟表示法中 一个结点的右子女是该结点的 结 点 A 兄弟 B 父子 C 祖先 D 子孙 80 在一棵树的静态双亲表示中 每个存储结点包含 个域 A 1 B 2 C 3 D 4 81 已知一棵二叉树的广义表表示为a b c d e g h f 则该二叉树的高度为 假定树根结点的高度为0 A 3 B 4 C 5 D 6 82 已知一棵树的边集表示为 则该树的深度为 假定树根结点的高度为0 A 2 B 3 C 4 D 5 83 利用n个值作为叶结点的权生成的霍夫曼树中共包含有 个结点 A n B n 1 C 2 n D 2 n 1 84 利用3 6 8 12这四个值作为叶子结点的权 生成一棵霍夫曼树 该树的带权路径 长度为 A 55 B 29 C 58 D 38 85 一棵树的广义表表示为a b c e f g d 当用左子女 右兄弟链表表示时 右 指针域非空的结点个数为 A 1 B 2 C 3 D 4 86 向具有n个结点的堆中插入一个新元素的时间复杂度为 A O 1 B O n C O log2n D O nlog2n 87 若搜索每个元素的概率相等 则在长度为n的顺序表上搜索任一元素的平均搜索 长度为 A n B n 1 C n 1 2 D n 1 2 88 对长度为10的顺序表进行搜索 若搜索前面5个元素的概率相同 均为1 8 搜索 后面5个元素的概率相同 均为3 40 则搜索任一元素的平均搜索长度为 A 5 5 B 5 C 39 8 D 19 4 89 对长度为3的顺序表进行搜索 若搜索第一个元素的概率为1 2 搜索第二个元素 的概率为1 3 搜索第三个元素的概率为1 6 则搜索任一元素的平均搜索长度为 A 5 3 B 2 C 7 3 D 4 3 90 对长度为n的单链有序表 若搜索每个元素的概率相等 则搜索任一元素的搜索 成功的平均搜索长度为 A n 2 B n 1 2 C n 1 2 D n 4 91 对于长度为n的顺序存储的有序表 若采用折半搜索 则对所有元素的搜索长度 中最大的为 的值向上取整 A log2 n 1 B log2n C n 2 D n 1 2 92 对于长度为n的顺序存储的有序表 若采用折半搜索 则对所有元素的搜索长度 中最大的为 的值的向下取整加1 A log2 n 1 B log2n C n 2 D n 1 2 93 对于长度为9的顺序存储的有序表 若采用折半搜索 在等概率情况下搜索成功 的平均搜索长度为 除以9 A 20 B 18 C 25 D 22 94 对于长度为18的顺序存储的有序表 若采用折半搜索 则搜索第15个元素的搜索 长度为 A 3 B 4 C 5 D 6 95 对具有n个元素的有序表进行折半搜索 则搜索任一元素的时间复杂度为 A O n B O n2 C O 1 D O log2n 96 在一棵高度为h的具有n个元素的二叉搜索树中 搜索一个元素的最大搜索长度为 A n B log2n C h 1 2 D h 1 97 从具有n个结点的二叉搜索树中搜索一个元素时 在等概率情况下进行成功搜索 的时间复杂度大致为 A O n B O 1 C O log2n D O n2 98 向具有n个结点的二叉搜索树中插入一个元素的时间复杂度大致为 A O 1 B O log2n C O n D O nlog2n 99 在一棵AVL树中 每个结点的平衡因子的取值范围是 A 1 1 B 2 2 C 1 2 D 0 1 100 向一棵AVL树插入元素时 可能引起对最小不平衡子树的调整过程 此调整分为 种旋转类型 A 2 B 3 C 4 D 5 101 向一棵AVL树插入元素时 可能引起对最小不平衡子树的左单或右单旋转的调整 过程 此时需要修改相关 个指针域的值 A 2 B 3 C 4 D 5 102 向一棵AVL树插入元素时 可能引起对最小不平衡子树的双向旋转的调整过程 此时需要修改相关 个指针域的值 A 2 B 3 C 4 D 5 103 设G1 V1 E1 和G2 V2 E2 为两个图 如果V1 V2 E1 E2 则称 A G1是G2的子图 B G2是G1的子图 C G1是G2的连通分量 D G2是G1的连通分量 104 有向图的一个顶点的度数等于该顶点的 A 入度 B 出度 C 入度与出度之和 D 入度 出度 105 一个连通图的生成树是包含图中所有顶点的一个 A 极小子图 B 连通子图 C 极小连通子图 D 无环子图 106 n个顶点的连通图中至少含有 A n 1条边 B n条边 C n n 1 2条边 D n n 1 条边 107 n个顶点的强连通图中至少含有 A n 1条有向边 B n条有向边 C n n 1 2条有向边 D n n 1 条有向边 108 在一个带权连通图G中 权值最小的边一定包含在G的 中 A 最小生成树 B 生成树 C 广度优先生成树 D 深度优先生成树 109 对于具有e条边的无向图 它的邻接表中有 个边结点 A e 1 B e C 2 e 1 D 2e 110 具有n个顶点的有向无环图最多可包含 条有向边 A n 1 B n C n n 1 2 D n n 1 111 一个有n个顶点和n条边的无向图一定是 A 连通的 B 不连通的 C 无环的 D 有环的 112 在n个顶点的有向无环图的邻接矩阵中至少有 个零元素 A n B n n 1 2 C n n 1 2 D n n 1 113 对于有向图 其邻接矩阵表示比邻接表表示更易于 A 查找一条边 B 求一个顶点的邻接点 C 进行图的深度优先遍历 D 进行图的广度优先遍历 114 在一个有向图的邻接矩阵表示中 删除一条边需要耗费的时间是 A O 1 B O i C O j D O i j 115 与邻接矩阵相比 邻接表更适合于存储 A 无向图 B 连通图 C 稀疏图 D 稠密图 116 设一个有n个顶点和e条边的有向图采用邻矩阵表示 要计算某个顶点的出度 所耗费的时间是 A O n B O e C O n e D O n2 117 为了实现图的广度优先遍历 BFS算法使用的一个辅助数据结构是 A 栈 B 队列 C 二叉树 D 树 118 设无向图的顶点个数为n 则该图最多有 条边 A n 1 B n n 1 2 C n n 1 2 D n n 1 119 在一个无向图中 所有顶点的度数之和等于所有边数的 倍 A 3 B 2 C 1 D 1 2 120 若采用邻接矩阵存储具有n个顶点的无向图 则该邻接矩阵是一个 A 上三角矩阵 B 稀疏矩阵 C 对角矩阵 D 对称矩阵 121 图的深度优先搜索类似于树的 次序遍历 A 先根 B 中根 C 后根 D 层次 122 图的广度优先搜索类似于树的 次序遍历 A 先根 B 中根 C 后根 D 层次 123 在用Kruskal算法求解带权连通图的最小 代价 生成树时 通常采用一个 辅助结构 判断一条边的两个端点是否在同一个连通分量上 A 位向量 B 堆 C 并查集 D 生成树顶点集合 124 采用Dijkstra算法求解带权有向图的最短路径问题时 要求图中每条边所带的 权值必须是 数 A 非零 B 非整 C 非负 D 非正 125 设有向图有n个顶点和e条边 采用邻接表作为其存储表示 在进行拓扑排序 时 总的计算时间为 A O nlog2e B O n e C O ne D O n2 126 若待排序对象序列在排序前已基本按排序码递增顺序排列 则采用 方法 比较次数最少 A 直接插入排序 B 快速排序 C 归并排序 D 直接选择排序 127 对待排序的元素序列进行划分 将其分为左 右两个子序列 再对两个子序列 施加同样的排序操作 直到子序列为空或只剩一个元素为止 这样的排序方法是 A 直接选择排序 B 直接插入排序 C 快速排序 D 起泡 排序 128 对5个不同的数据元素进行直接插入排序 最多需要进行 次比较 A 8 B 10 C 15 D 25 129 下列排序算法中 算法是不稳定的 A 起泡排序 B 直接插入排序 C 基数排序 D 快速排序 130 假设某文件经过内部排序得到100个初始归并段 那么如果要求利用多路平衡归 并在3 趟内完成排序 则应取的归并路数至少是 A 3 B 4 C 5 D 6 131 在基于排序码比较的排序算法中 算法在最坏情况下的时间复杂度不高 于O nlog2n A 起泡排序 B 希尔排序 C 堆排序 D 快速排序 132 在下列排序算法中 算法使用的附加空间与输入序列的长度及初始排列 无关 A 锦标赛排序 B 快速排序 C 基数排序 D 归并排序 133 一个对象序列的排序码为 46 79 56 38 40 84 采用快速排序 以位于 最左位置的对象为基准 所得到的第一次划分结果为 A 38 46 79 56 40 84 B 38 79 56 46 40 84 C 40 38 46 79 56 84 D 38 46 56 79 40 84 134 如果将所有中国人按照生日 不考虑年份 只考虑月 日 来排序 那么使用 下列排序算法中 算法最快 A 归并排序 B 希尔排序 C 快速排序 D 基数排序 135 设有一个含有200个元素的表待散列存储 用线性探查法解决冲突 按关键码查 询时找到一个元素的平均探查次数不能超过1 5 则散列表的长度应至少为 注 平均探查次数的计算公式为Snl 1 1 1 2 其中 为装填因子 A 400 B 526 C 624 D 676 136 5阶B树中 每个结点最多允许有 个关键码 A 2 B 3 C 4 D 5 137 在10阶B树中根结点所包含的关键码个数最少为 A 0 B 1 C 3 D 4 138 在一棵高度为h的B树中 叶结点处于第 层 注 树根结点为第0层 B树高度为失败结点所处层数 A h 1 B h C h 1 D h 2 139 在一棵高度为h的B树中 插入一个新关键码时 为搜索插入位置需读取 个结点 A h 1 B h C h 1 D h 2 140 当对一个线性表R 60 进行索引顺序搜索 分块搜索 时 若共分成了10个子 表 每个子表有6个表项 假定对索引表和数据子表都采用顺序搜索 则搜索每一个表项 的平均搜索长度为 A 7 B 8 C 9 D 10 141 当对一个线性表R 60 进行索引顺序搜索 分块搜索 时 若共分成了8个子 表 每个子表有6个表项 假定对索引表和数据子表都采用顺序搜索 则搜索每一个表项 的平均搜索长度为 A 7 B 8 C 9 D 10 142 既希望较快的搜索又便于线性表动态变化的搜索方法是 A 顺序搜索 B 折半搜索 C 散列搜索 D 索引顺序搜索 143 散列函数应该有这样的性质 即函数值应当以 概率取其值域范围内的每 一个值 A 最大 B 最小 C 平均 D 同等 144 设散列地址空间为0 m 1 k为表项的关键码 散列函数采用除留余数法 即 Hash k k p 为了减少发生冲突的频率 一般取p为 A m B 小于m的最大质数 C 大于m的最小质数 D 小于m的最大合数 145 在采用开散列法解决冲突时 每一个散列地址所链接的同义词子表中各个表项 的 值相同 A 关键码 B 非关键码 C 散列函数 D 某个域 146 解决散列法中出现的冲突问题常采用的方法是 A 数字分析法 除留余数法 平方取中法 B 数字分析法 除留余数法 线性探查法 C 数字分析法 线性探查法 双散列法 D 线性探查法 双散列法 开散列法 147 在闭散列表中 散列到同一个地址而引起的 堆积 问题是由于 引起的 A 同义词之间发生冲突 B 非同义词之间发生 冲突 C 同义词之间或非同义词之间发生冲突 D 散列表