数据结构模拟试题及答案3

数据结构数据结构 模拟试题模拟试题 3 3 一 一 单项选择题单项选择题 1 带头结点的单向链表为空的判断条件是 设头指针为 head A head NULL B head NULL C head next head D head next NULL 2 非空的单向循环链表的尾结点满足 设头指针为 head 指针 p 指向尾结点 A p next NULL B p NULL C p head D p next head 3 算法的时间复杂度与 有关 A 所使用的计算机 B 计算机的操作系统 C 算法本身 D 数据结构 4 设有一个长度为 n 的顺序表 要删除第 i 个元素需移动元素的个数为 A n i 1 B n i C n i 1 D i 5 在一个单链表中 p 所指结点之后插入一个 s 所指的结点时 可执行 A p s next B p next s next C s next p next p next s D p next s s next p next 6 在一个链队中 假设 f 和 r 分别为队头和队尾指针 则删除一个结点的运算为 A r f next B r r next C f f next D f r next 7 元素 1 3 5 7 按顺序依次进栈 则该栈的不可能输出序列是 进栈出栈可以 交替进行 A 7 5 3 1 B 7 5 1 3 C 3 1 7 5 D 1 3 5 7 8 在 C 语言中 顺序存储长度为 3 的字符串 需要占用 个字节 A 4 B 3 C 6 D 12 9 在一棵二叉树中 若编号为 i 的结点存在左孩子 则左孩子的顺序编号为 A 2i B 2i 1 C 2i 1 D 2i 2 10 一棵具有 35 个结点的完全二叉树 最后一层有 个结点 A 4 B 6 C 16 D 8 11 在一个无向图中 所有顶点的度数之和等于边数的 倍 A 3 B 2 C 2 5 D 1 5 12 已知如图 3 所示的一个图 若从顶点 V1出发 按广度优先法进行遍历 则可能得到的 一种顶点序列为 A V1V2V4V8V5V3V6V7 B V1V2V4V5V8V3V6V7 C V1V2V4V8V3V5V6V7 D V1V3V6V7V2V4V5V8 V6V7 V1 V2V3 V8 V4V5 图 3 13 对二叉排序树进行 遍历 可以使遍历所得到的序列是有序序列 A 按层次 B 后序 C 中序 D 前序 14 设已有 m 个元素有序 在未排好序的序列中挑选第 m 1 个元素 并且只经过一次元素 的交换就使第 m 1 个元素排序到位 该方法是 A 折半排序 B 冒泡排序 C 归并排序 D 简单选择排序 15 一组记录的关键字序列为 47 80 57 39 41 46 利用堆排序 堆顶元素是最小 元素 的方法建立的初始堆为 A 39 47 46 80 41 57 B 39 41 46 80 47 57 C 41 39 46 47 57 80 D 39 80 46 47 41 57 二 填空题二 填空题 1 算法的 5 个特征为 2 要求在 n 个数据元素中找其中值最大的元素 设基本操作为元素间的比较 则比较的次 数和算法的时间复杂度分别为 和 3 在一个单向链表中 p 所指结点之后插入一个 s 所指向的结点时 应执行 s next p next 和 的操作 4 在一个单向链表中 要删除 p 所指结点 已知 q 指向 p 所指结点的前驱结点 则可以用 操作 5 向一个栈顶指针为 h 的链栈中插入一个 s 所指结点时 可执行 s next h 和 操 作 结点的指针域为 next 6 在一个链队中 设 f 和 r 分别为队头和队尾指针 则插入 s 所指结点的操作为 r next s 和 结点的指针域为 next 7 两个串相等的充分必要条件是 8 在二叉树的链式存储结构中 通常每个结点中设置三个域 它们是 9 一棵二叉树中有 2n 2 条边 结点间的连线 其中每一个非叶结点的度数都为 2 则该 树共有 个非叶结点 10 如图 1 所示的二叉树 其中序遍历序列为 11 如图 1 所示的二叉树 其后序遍历序列为 12 哈希函数是记录关键字值与该记录存储地址之间所构造的对应关系 13 n 个元素进行冒泡法排序 通常需要进行 趟冒泡 第 j 趟冒泡要进行 次 元素间的比较 三 综合题三 综合题 1 已知序列 11 19 5 4 7 13 2 10 1 试给出用归并排序法对该序列作升序排序时的每一趟的结果 2 对上述序列用堆排序的方法建立初始堆 要求小根堆 以二叉树描述建堆过程 2 设查找表为 7 15 21 22 40 58 68 80 88 89 120 元素的下标依次为 1 2 3 11 1 画出对上述查找表进行折半查找所对应的判定树 树中结点用下标表示 2 说明成功查找到元素 40 需要经过多少次比较 3 求在等概率条件下 成功查找的平均比较次数 3 1 如果二叉树中任一结点的值均大于其左孩子的值 小于其右孩子的值 则该树为二 叉排序树 这种说法是否正确 若认为正确 则回答正确 若认为不正确 则举例说明 2 设有数据集合 40 29 7 73 101 4 55 2 81 92 39 依次取集合中各数 据 构造一棵二叉排序树 4 1 一棵二叉树若它的根结点的值大于左子树所有结点的值 小于右子树所有结点的值 则该树一定是二叉排序树 该说法是否正确 若认为正确 则回答正确 若认为不正确则 说明理由 2 设有查找表 7 16 4 8 20 9 6 18 5 依次取表中数据构造一棵二叉排序树 对上述二叉树给出后序遍历的结果 5 1 对给定权值 2 1 3 3 4 5 构造哈夫曼树 2 同样用上述权值构造另一棵哈夫曼树 使两棵哈夫曼树有不同的高度 并分别求 两棵树的带权路径长度 四 程序填空题四 程序填空题 1 以下是用尾插法建立带头结点且有 n 个结点的单向链表的程序 结点中的数据域从前向 图 1图 2 ef g i bc h dg f a b d e c 后依次为 1 2 3 n 完成程序中空格部分 NODE create n NODE head p q int i p NODE malloc sizeof NODE head p next NULL 建立头结点 for i 1 idata i p next NULL q next return head 2 设线性表为 6 10 16 4 以下程序用说明结构变量的方法建立单向链表 并输出 链表中各结点中的数据 define NULL 0 void main NODE a b c d head p a data 6 b data 10 c data 16 d data 4 d 是尾结点 head a next b next c next 以上结束建表过程 p head p 为工作指针 准备输出链表 do printf d n while 3 以下程序是中序遍历二叉树的递归算法的程序 完成程序中空格部分 树结构中左 右 指针域分别为 left 和 right 数据域 data 为字符型 BT 指向根结点 void Inorder struct BTreeNode BT if BT NULL 4 以下程序是中序遍历二叉树的递归算法的程序 完成程序中空格部分 树结构中左 右 指针域分别为 left 和 right 数据域 data 为字符型 BT 指向根结点 void Inorder struct BTreeNode BT if BT NULL 1 2 Inorder BT right 利用上述程序对右图进行遍历 结果是 综合练习题答案综合练习题答案 一 单项选择题一 单项选择题 1 D 2 D 3 C 4 B 5 C 6 C 7 B 8 A 9 A 10 A 11 B 12 A 13 C 14 D 15 B 二 填空题二 填空题 1 有穷性 确定性 可行性 零个或多个输入 一个或多个输入 2 n 1 O n 3 s next p next 4 q next p next 5 s next h 6 r next s 7 串长度相等且对应位置的字符相等 8 值域 左指针 右指针 9 n 1 10 dgbaechif 11 gdbeihfca 12 存储地址 13 n 1 n j 三 综合题三 综合题 1 1 初始 11 19 5 4 7 13 2 10 第一趟 11 19 4 5 7 13 2 10 第二趟 4 5 11 19 2 7 10 13 第三趟 2 4 5 7 11 10 11 13 2 ef a bc d 2 1 2 4 次 3 ASL 1 2 2 3 4 4 4 11 3 47 11 852 10 1 39 6 2 10 11 519 7413135 10 11 19 7 2 4 713 10 13 19 11 2 5 4 19 2 4 710 5 11 3 1 不正确 例 2 4 1 不正确 二叉排序树要求其子树也是二叉排序树 2 后续遍历 5 6 4 9 8 18 20 16 7 1 5 4 2 3955 92 814 1017 2 40 73 5 29 4 68 95 20