厦门理工学院12级数据结构期末试卷与答案

第 1 页 共 5 页 厦门理工学院试卷厦门理工学院试卷 20122012 20132013 学年学年 第第 一一 学期学期 课程名称数据结构与算法数据结构与算法 试卷 卷别 A B 专业专业 2011 级级 班级班级 考试 方式 闭卷 开卷 考考 生生 信信 息息 栏栏 系 专业 级 班级 姓名 学号 装 订 线 本试卷共本试卷共 四四 大题大题 4 4 页页 满分 满分 100100 分 考试时间分 考试时间 120120 分钟 分钟 请在答题纸上作答 在试卷上作答无效 请在答题纸上作答 在试卷上作答无效 第 2 页 共 5 页 一 选择题 本题共一 选择题 本题共 20 小题 每题小题 每题 2 分 共分 共 40 分 分 1 链式存储的存储结构所占存储空间 A 分两部分 一部分存放结点的值 另一部分存放表示结点间关系的指 针 B 只有一部分 存放结点的值 C 只有一部分 存储表示结点间关系的指针 D 分两部分 一部分存放结点的值 另一部分存放结点所占单元素 2 已知一个顺序存储的线性表 设每个结点占 m 个存储单元 若第一个结点的 地址为 B 则第 i 个结点的地址为 A B i 1 m B B i m C B i m D B i 1 m 3 两个指针 P 和 Q 分别指向单链表的两个元素 P 所指元素是 Q 所指元素前 驱的条件是 A P next Q next B P next Q C Q next P D P Q 4 下面关于线性表的叙述中 错误的是 关系 A 顺序表必须占一片地址连续的存储单元 B 顺序表可以随机存取任一元素 C 链表不必占用一片地址连续的存储单元 D 链表可以随机存取任一元素 5 等概率情况下 在有 n 个结点的顺序表上做插入结点运算 需平均移动结点 的数目为 A nB n 1 2 C n 2 D n 1 2 6 设数组 data m 作为循环队列 SQ 的存储空间 front 为队头指针 rear 为 队尾指针 则执行出队操作后其头指针 front 值为 A front front 1 B front front 1 m 1 C front front 1 m D front front 1 m 第 3 页 共 5 页 7 下列算法的时间复杂度是 for i 0 i n i for j 0 jnext B top top next x top data C x top data D x top data top top next 9 经过下列栈的运算后 x的值是 InitStack s 初始化栈 Push s a Push s b ReadTop s Pop s x A a B b C 1 D 0 10 一个栈的入栈次序 ABCDE 则栈的不可能的输出序列是 A EDCBA B DECBA C DCEAB D ABCDE 11 设某棵二叉树中有 2000个站点 则该二叉树的最小高度为 A 9 B 10 C 11 D 12 12 若用一个大小为6的数组来实现循环队列 且当前front和rear的值分别为3和0 当从队列中 删除一个元素 再加 入两个元素后 front和rear的值分别为 A 5和1 B 4和2 C 2和4 D 1和5 13 根据二叉树的定义 具有 3 个结点的二叉树有 种树型 A 3 B 4 C 5 D 6 第 4 页 共 5 页 14 如右图所示的二叉树 后序遍历的序列是 A A B C D E F G H I B A B D H I E C F G C H D I B E A F C G D H I D E B F G C A 15 下列陈述正确的是 A 二叉树是度为 2 的有序树B 二叉树中结点只有一个孩子时无左右之分 C 二叉树中必有度为 2 的结点 D 二叉树中最多只有两棵子树 且有左右子树之分 16 在有 n 个叶子结点的哈夫曼树中 非叶子结点的总数是 n 1 n 2n 1 2n A B A DE C FG HI 第 5 页 共 5 页 17 对于一个具有 n 个顶点的有向图的边数最多有 A n B n n 1 C n n 1 2 D 2n 18 对于一个具有 n 个顶点和 e 条边的无向图 采用邻接表表示 则表头向量大小为 A n 1B n 1 C n D n e 19 下面关于图的存储结构的叙述中正确的是 A 用邻接矩阵存储图 占用空间大小只与图中顶点数有关 而与边数无关 B 用邻接矩阵存储图 占用空间大小只与图中边数有关 而与顶点数无关 C 用邻接表存储图 占用空间大小只与图中顶点数有关 而与边数无关 D 用邻接表存储图 占用空间大小只与图中边数有关 而与顶点数无关 20 二叉树为二叉排序树的 条件是其任一结点的值均大于其左孩子的值 小于其右孩子 的值 A 充分不必要 B 必要不充分 C 充分必要 D 既不充分也不必要 二 分析运算题 本题共二 分析运算题 本题共 6 小题 每题小题 每题 5 分 共分 共 30 分 分 1 如果输入序列为 1 2 3 先进入栈结构后进入队列结构 试写出所有的出队列序列 2 假设一棵二叉树的前序 先序 遍历序列为 ABDECF 和中序序列为 DBEAFC 画出二叉树并写 出后序遍历序列 图图 1 图图 2 图图 3 3 用二叉树表示算术表达式如图 1 所示 第 6 页 共 5 页 按图画出对应的算术表达式 写出后序 后缀 表达式 4 请写出有向图 2 中顶点 1 6 的入度和出度 5 给定一组项及其权值 假定项都存放于二叉树的树叶结点 则具有最小带权外部路径长度的树 称为 huffman 赫夫曼 树 给定项及相应的权如下表 画出相应的 huffman 树 序号序号 1 1 2 2 3 3 4 4 5 5 6 6 7 7 8 8 9 9 项项 A A B B C C D D E E F F G G H H I I 权值权值 1515 6 6 7 712122525 4 4 6 6 1 11515 6 已经邻接矩阵如图 3 所示 判断该图是有向图还是无向图 用顶点 1 6 画出该图 第 7 页 共 5 页 三 程序填空题 本题共三 程序填空题 本题共 5 空 每空空 每空 2 分 共分 共 10 分 分 1 1 下面程序段的功能是在单链表中查找元素数据 下面程序段的功能是在单链表中查找元素数据 x x 若找到 返回指向该结点的指 若找到 返回指向该结点的指 针 否则返回空指针 请在下划线处填上正确的内容 针 否则返回空指针 请在下划线处填上正确的内容 在单链表 L 中查找元素 x typedeftypedef structstruct LNodeLNode DataTypeDataType data data structstruct LNodeLNode next next LNode LNode LinkList LinkList LinkListLinkList FindFind LinkListLinkList L L DataTypeDataType x x p p L next L next L L 为带头节点的单链表为带头节点的单链表 whilewhile 1 1 ifif p datap data x x returnreturn p p 找到找到 x x 2 2 returnreturn NULL NULL 未找到未找到 2 2 下面程序段的功能实现删除队列中的队头数据 若队列不空 下面程序段的功能实现删除队列中的队头数据 若队列不空 并用 并用 x x 返回其值 返回其值 要求在下划线处填上正确的语句 要求在下划线处填上正确的语句 typedeftypedef structstruct QNodeQNode DataTypeDataType data data structstruct QNodeQNode next next QNode QNode QueuePtr QueuePtr typedeftypedef structstruct LQ LQ 线 订 装 第 8 页 共 5 页 QueuePtrQueuePtr front front QueuePtrQueuePtr rear rear LinkQueue LinkQueue intint DeQueueDeQueue LinkQueueLinkQueue ERROR p p Q front next Q front next x p data x p data 4 4 ifif Q rear Q rear p p 5 5 free p free p returnreturn OK OK 第 9 页 共 5 页 第 10 页 共 5 页 考考 生生 信信 息息 栏栏 系系 专业专业 级级 班级班级 姓名姓名 学号学号 装装 订订 线线 四 算法设计题 本题共四 算法设计题 本题共 2 小题 共小题 共 20 分 分 1 10 分 已知一个顺序表 每个元素都是整数 试设计用最少时间把所有值为分 已知一个顺序表 每个元素都是整数 试设计用最少时间把所有值为 负数的元素移动到全部正数值元素前面的算法 负数的元素移动到全部正数值元素前面的算法 typedef struct int elem int length int listSize sqlist 2 10 分 以二叉链表为存储结构 编写计算二叉树中叶子结点数目的递归函数 分 以二叉链表为存储结构 编写计算二叉树中叶子结点数目的递归函数 typedef struct BiTNode int data struct BiTNode lchild rchild BiTNode BiTree 第 11 页 共 5 页 数据结构与算法数据结构与算法 A 卷答案卷答案 12 13 学年第一学期学年第一学期 一 选择题 本题共一 选择题 本题共 20 小题 每题小题 每题 2 分 共分 共 40 分 分 1 5 AABDC 6 10 DDDBC 11 15 CBCDD 16 20 ABCAB 二 分析运算题 本题共二 分析运算题 本题共 6 小题 每题小题 每题 5 分 共分 共 30 分 分 1 如果输入序列为如果输入序列为 1 2 3 先进入栈结构后进入队列结构 试写出所有的出队列序列 先进入栈结构后进入队列结构 试写出所有的出队列序列 输出序列 1 2 3 1 分 输出序列 1 3 2 1 分 输出序列 2 1 3 1 分 输出序列 2 3 1 1 分 输出序列 3 2 1 1 分 输出序列 3 1 2 扣 3 分 2 假设一棵二叉树的前序假设一棵二叉树的前序 先序先序 遍历序列为遍历序列为 ABDECF 和中序序列为和中序序列为 DBEAFC 画出二叉树并写出 画出二叉树并写出 后序遍历序列 后序遍历序列 3 分 后序遍历 DEBFCA 2 分 第 12 页 共 5 页 3 用二叉树表示算术表达式如图用二叉树表示算术表达式如图 1 所示 所示 按图画出对应的算术表达式按图画出对应的算术表达式 写出后序 后缀 表达式写出后序 后缀 表达式 算术表达式算术表达式 a b c d e f g h 2 分 后序表达式后序表达式 ab cde f gh 3 分 4 请写出有向图请写出有向图 2 中顶点中顶点 1 6 的入度和出度的入度和出度 1 入度 3 出度 0 2 入度 2 出度 2 3 入度 1 出度 2 4 入度 1 出度 3 5 入度 2 出度 1 6 入度 2 出度 3 入度 2 5 分 出度 2 5 分 5 给定一组项及其权值 假定项都存放于二叉树的树叶结点 则具有最小带权外部路径长度的树称给定一组项及其权值 假定项都存放于二叉树的树叶结点 则具有最小带权外部路径长度的树称 为为 huffman 赫夫曼赫夫曼 树 给定项及相应的权如下表 画出相应的树 给定项及相应的权如下表 画出相应的 huffman 树 树 5 分分 91 38 53 2328 1113 15 I 12 D 25 E 15 A 第 13 页 共 5 页 6 已经邻接矩阵如图已经邻接矩阵如图 3 所示 判断该图是有向图还是无向图 用顶点所示 判断该图是有向图还是无向图 用顶点 1 6 画出该图 画出该图 有向图 2 分 3 分 三 程序填空题 本题共三 程序填空题 本题共 5 空 每空空 每空 2 分 共分 共 10 分 分 1 1 p NULLp NULL 2 2 p p p next p next 3 3 Q front Q front Q rear Q rear 5 1 H 4 F 6 B 6 G 7 C 第 14 页 共 5 页 4 4 Q f