《数据结构》试题 3.pdf

温温 州州 师师 范范 学学 院院 期期 末末 考考 试试 纸纸 数据结构 试题 数据结构 试题 3 一 一 选择题 每个 2 分 共 10 分 选择题 每个 2 分 共 10 分 1 下列关于数据结构的叙述中 正确的是 A 数组是同类型值的集合 B 递归算法的程序结构比迭代算法的程序结构更为精炼 C 树是一种线性结构 D 用一维数组存储二叉树 总是以先序遍历的顺序存储各结点 2 用直接插入排序方法对下面四个序列进行排序 由小到大 元素比较次数最少 的是 A 94 32 40 90 80 46 21 69 B 32 40 21 46 69 94 90 80 C 21 32 46 40 80 69 90 94 C 90 69 80 46 21 32 94 40 3 如果要求一个线性表既能较快地查找 又能适应动态变化的要求 则可采用的 方法是 A 分块法 B 顺序法 C 二分法 D 散列法 4 以下关于广义表的叙述中 正确的是 A 广义表是 0 个或多个单元素或子表组成的有限序列 B 广义表至少有一个元素是子表 C 广义表不可以是自身的子表 D 广义表不能为空表 5 在顺序表 3 6 8 10 12 15 16 18 21 25 30 中 用二分法查找关键码值 11 所 需的关键码比较次数为 A 2 B 3 C 4 D 5 二 填空题 每格 1 分 共 20 分 二 填空题 每格 1 分 共 20 分 1 结点在物理上的存储结构有四种 分别为顺序存储结构 和 2 数据结构是指数据的组织形式 它一般包括三个方面 它们是 和 3 有一个链表 头结点为 head 现在已建立一个新结点 q 把 q 插入到最前面的二 句语句为代码为 和 4 数据的逻辑结构被分为 和 四种 5 高度为 4 的二叉树中 结点数最多为 最少为 温温 州州 师师 范范 学学 院院 期期 末末 考考 试试 纸纸 6 在一个具有 n 个顶点的无向图中 要连通所有顶点则至少需要 条 边 7 假定一个图具有 n 个顶点和 e 条边 则采用邻接矩阵 邻接表数组表示时 其 应的空间复杂度分别为 和 8 快速排序在平均情况下的时间复杂度为 在最坏情况下的时间 复杂度为 该排序方法为 稳定 不稳定 三 分析题 每题 5 分 共 30 分 三 分析题 每题 5 分 共 30 分 1 有一棵二叉树 如下图所示 分别写出三种编历的顶点序列 A B E D G C F 2 假设下面程序里的栈 S 存放如下左图的数据 经过下面这段程序处理后 写出栈 里的内容 写在右图里 并说明该程序的功能 1000 800 600 400 200 100 void Demo SeqStack S int i int arr 64 n 0 while StackEmpty S arr n Pop S for i 0 i n i Push S arr i 温温 州州 师师 范范 学学 院院 期期 末末 考考 试试 纸纸 3 下面是一个有向图 从顶点 A 出发分别用深度遍历和广度遍历写出顶点序列 当有多个顶点可供选择时 先选择英语字母表中前一个顶点 A B C D E H G F 4 用拉链法构造散列表 存储空间为 10 个单元 散列函数为 h key key 11 数 据为 43 37 52 67 23 12 54 78 65 7 19 35 0 1 2 3 4 5 6 7 8 9 10 5 某个数组的初始状态为 12 43 21 54 56 32 75 83 23 是不是一个小顶堆 如 不是 则建立它的初始堆 用二叉树形表示 采用小顶堆 温温 州州 师师 范范 学学 院院 期期 末末 考考 试试 纸纸 6 有一个网格如下图所示 出发顶点为 用 prim 算法 求出最小生成树 要 画出其过程 A B C D E H G F 3 2 6 5 7 4 5 3 6 5 2 四 设计题 第 1 题 17 分 第 2 题 23 分 共 40 分 四 设计题 第 1 题 17 分 第 2 题 23 分 共 40 分 1 有一个顺序有 L 写一个函数 InsertList 在 L 中的第 i 个位置插入一个结点 x 值 该 x 的数据在主程序中输入 整个程序的结构如下 请完成整个程序 要符 合 C 语言格式 define ListSize 100 typedef struct StudInfo int number 学号 char name 20 姓名 int yw 语文 int math 数学 int total 总分 int order 名次 STUDINFO typedef STUDINFO DataType typedef struct DataType data ListSize 向量 data 用于存放表结点 int length 当前的表长度 SeqList main 温温 州州 师师 范范 学学 院院 期期 末末 考考 试试 纸纸 int i n DataType x printf 请输入实际人数 scanf d for i 1 i n i input 输入第 i 个同学了的数据 InsertList 把第 i 个同学插入到第 i 个位置 经过以上处理后 建立了顺序表 L 现在请同学们接着写程序求出每个 同学了的总分及名次 请同学们根据 main 函数中的调用形式写出 InsertList 函数 温温 州州 师师 范范 学学 院院 期期 末末 考考 试试 纸纸 2 哈夫曼树与哈夫曼编码 a 有 6 个叶子结点的分别为 a b c d e f 它们的权值相应为 0 1 0 50 0 12 0 18 0 07 0 03 画出哈夫曼及哈夫曼编码 要求左子树的权值小于右子树 且编码时 左子树为 0 右子树取 1 5 b 哈夫曼树的存储结构和部分程序如下所示 请完整写出 InitHuffmanTree InputWeight 和 SelectMin 三个函数 要求程序符合 C 语言的要 求 语法尽量正确 书写规范 3 分 5 分 10 分 共 18 分 define n 100 叶子数目 define m 2 n 1 树中结点总数 typedef struct 结点类型 float weight 权值 不妨设权值均大于零 int lchild rchild parent 左右孩子及双亲指针 HTNode typedef HTNode HuffmanTree m HuffmanTree 是向量类型 void CreateHuffmanTree HuffmanTree T 构造哈夫曼树 T m 1 为其根结点 int i p1 p2 InitHuffmanTree T 将 T 初始化 InputWeight T 输入叶子权值至 T 0 n 1 的 weight 域 for i n i m i 共进行 n 1 次合并 新结点依次存于 T i 中 SelectMin T i 1 p1 p2 p1 2 p2 3 在 T 0 i 1 中选择两个权最小的根结点 其序号分别为 p1 和 p2 T p1 p