数据结构期末练习

DSDS 练习练习 一 选择题一 选择题 1 是不可分割的并且具有独立含义的最小数据单位 A 数据 B 数据元素 C 数据项 D 数据对象 2 设某数据结构的二元组形式表示为 A D R D 01 02 03 04 05 06 07 08 09 R r r 则数据结构 A 是 A 线性结构 B 树型结构 C 物理结构 D 图型结构 3 以下算法 违背了算法特性中的 void exam1 n 2 while n 2 0 n n 2 printf d n n A 有限性 B 确定性 C 可行性 D 算法必须有输出 4 对线性表 在下列哪种情况下应当采用链表表示 A 经常需要随机地存取元素 B 经常需要进行插入和删除操作 C 表中元素需要占据一片连续的存储空间 D 表中元素的个数不变 5 设顺序线性表中有 n 个数据元素 则删除表中第 i 个元素需要移动 个元素 A n i B n l i C n 1 i D i 6 在一个单链表中 若要删除指针 p 所指的结点的后继结点 则执行 A p next p next next B p p next p next p next next C p next p next D p p next next 7 设输入序列是 1 2 3 n 经过栈的作用后输出序列的第一个元素是 n 则输出序列 中第 i 个输出元素是 A n i B n 1 i C n 1 i D 不能确定 8 一个队列的输入序列为 1 2 3 4 则其输出序列为 A 1 2 3 4 B 4 3 2 1 C 不唯一 D 1 2 3 4 或 4 3 2 1 9 串是一种特殊的线性表 其特殊性表现在 A 可以顺序存储 B 数据元素是一个字符 C 可以连接存储 D 数据元素可以是多个字符 10 二叉排序树中具有最大值的结点在树的 A 左子树 B 右子树 C 根结点 D 不一定 11 一组记录为 46 79 56 38 84 40 则采用直接插入排序法按升序排列时第一趟排序 结果是 A 46 79 56 38 84 40 B 38 79 56 46 84 40 C 38 40 46 56 84 79 D 46 56 38 79 40 84 12 深度为 k 的完全二叉树至多有 个结点 A k B 2k 1 1 C 2k 1 D 2k 1 13 在有 n 个结点的三叉链表中 值为非空的链域的个数 A n 1 B 2n 2 C n 1 D n 2 14 某二叉树共有叶结点 15 个 没有度为 1 的结点 则该树共有 个结点 A 29 B 28 C 27 D 不能确定 15 遍历一棵二叉树时 先遍历根结点 再遍历左子树 再遍历右子树的遍历方 法是 A 先序遍历 B 中序遍历 C 后序遍历 D 层次遍历 16 一棵完全二叉树中根结点的编号为 l 而且 23 号结点有左孩子但没有右孩子 则完全二叉 树总共有 个结点 A 24 B 45 C 46 D 47 17 在含 n 个顶点和 e 条边的无向图的邻接矩阵中 零元素的个数为 A e B 2e C n2 e D n2 2e 18 设有 6 个结点的无向图 该图至少应有 条边才能确保是一个连通图 A 5 B 6 C 7 D 8 19 可以判断一个有向图中是否含有回路的方法为 A 广度优先遍历 B 深度优先遍历 C 拓扑排序 D 最短路径 20 在一个无向图中 所有顶点的度数之和等于所有边数的 倍 A 2 B 3 C 4 D 不确定 二 判断题二 判断题 1 数据结构 是一门研究非数值计算的程序设计问题中计算机的操作对象以及 它们之间关系和操作的学科 2 线性表中 除第一个元素外 其他每一个元素有且仅有一个直接前驱 除最 后一个元素外 其他每一个元素有且仅有一个直接后继 3 哈夫曼编码树中没有度为 1 的结点 4 完全二叉树一定是满二叉树 5 对线性表进行折半查找时 必须要求线性表以链接方式存储 且结点按 关键字有序排列 6 对矩阵进行压缩存储主要是是为了操作方便 7 栈是一种先进先出的线性表 8 有向图中 所有结点的出度之和等于入度之和 9 当待排序记录的关键字均不相同时 排序的结果是唯一的 否则排序的结果不一定唯一 10 图的邻接表是一种顺序分配和链式分配相结合的存储方法 三 综合题三 综合题 1 写出下列左图稀疏矩阵的三元组顺序表 三元组以行序为主序排列 行列号从 1 开始 0 1 0 0 1 4 0 0 0 0 A 0 0 0 7 0 0 6 0 0 0 8 0 9 0 0 0 0 0 0 0 2 已知二叉排序树的各结点的值依次是 1 9 请标出上面右图树中各结点的值 3 根据以下邻接表给出其对应的图形结构和邻接矩阵的存储形式 下左图 4 二叉树的后序和中序序列如下 构造出该二叉树 并写出其前序序列 后序序列 ABCDEFG 中序序列 ACBGEDF 5 一组待排序序列为 98 88 78 38 18 28 给出采用选择排序法按升序排序的全过程 6 用克鲁斯卡尔算法求下面右图带权无向图的最小生成树 7 1 给定权值 4 3 16 9 22 10 5 构造相应的哈夫曼树 2 设上述权值分别代表 7 个字母 A B C D E F 和 H 出现的频率 试为这 7 个字母设 计哈夫曼编码 左分支上标以 1 右分支上标以 0 8 下表是某计算机专业前 4 个学期的相关课程及其先修课程状况 利用所学知识根据表中内容 排出课程表 要求每门课程都不能与其先修课程在同一学期开设 课程代码课程名称先修课程 C1 高等数学 C2 程序设计基础 C3 离散数学C1 C2 C4 数据结构C3 C2 C5 高级语言程序设计 C2 C6 编译方法C5 C4 C7 操作系统C4 C9 C8 普通物理 C1 C9 计算机原理 C8 四 算法设计题四 算法设计题 1 建立顺序表存储线性表中的数据 要求设计算法 ListInsert 在顺序表 L 中的第 i 个元素前 插入新的元素 e 顺序表的存储结构定义如下 Typedef struct int data MAXSIZE int last SeqList 2 某线性表包含 10 个数据 10 20 30 40 50 60 70 80 90 100 要求 设计算法 CreateList 建立单链表存储数据 单链表结点的存储结构描述 struct node 定义单链表结点类型 int data struct node next 指向后继结点 3 设计算法 Treehigh 确定某二叉树 T 指向二叉树根结点的指针 的深度 二叉树结点的类型定义如下 typedef struct node int data struct node lchild rchild BTNode BTNode T 4 写出折半查找算法 BinarySearch 返回 kx 在有序表 L 升序排序 中的位序 查找表 L 定义如下 typedef struct int data MaxSize 1 int length SqList SqList L 假设数据存放在 L data 1 L data n 中 5 写出快速排序算法 QuickSort 实现待排序表 L 按关键字的由小到大排序 待排序的顺序表 L 类型定义如下 define MAXSIZE 100 typedef int KeyType 定义关键字类型 typedef struct KeyTy