安徽大学数据结构试卷2010A

安徽大学安徽大学 20 09 20 10 学年第学年第 2 学期学期 数据结构数据结构 考试试卷 考试试卷 A 卷 卷 闭卷 闭卷 时间时间 120 分钟分钟 一 填空题 每空一 填空题 每空 1 1 分 共分 共 1515 分 分 1 在线性结构中 第一个结点 前驱结点 其余每个结点有且只有 个前驱 结点 最后一个结点 后续结点 其余每个结点有且只有 个后续结点 2 下面程序段的时间复杂度是 for i 0 i n i for j 0 jnext HL B p 一 next HL HL p C p 一 next HL p HL D p 一 next HL 一 next HL 一 next p 3 采用线性链表表示一个向量时 要求占用的存储空间地址 A 必须是连续的 B 部分地址必须是连续的 C 一定是不连续的 D 可连续可不连续 4 如果想在 4092 个数据中只需要选择其中最小的 5 个 采用 方法最好 A 起泡排序 B 堆排序 C 锦标赛排序 D 快速排序 5 在循环队列中用数组 A 0 m 1 存放队列元素 其队头和队尾指针分别为 front 和 rear 则当前队列中的元素个数是 A front rear 1 m B rear front 1 m C front rear m m D rear front m m 6 数组 A 0 5 0 6 的每个元素占五个字节 将其按列优先次序存储在起始地址为 1000 的 内存单元中 则元素 A 5 5 的地址是 A 1175 B 1180 C 1205 D 1210 7 已知广义表 LS a b c d e f 运用 head 和 tail 函数取出 LS 中原子 e 的运算是 A head tail LS B tail head LS C head tail head tail LS D head tail tail head LS 8 某二叉树的前序遍历结点访问顺序是 abdgcefh 中序遍历的结点访问顺序是 dgbaechf 则 其后序遍历的结点访问顺序是 A bdgcefha B gdbecfha C bdgaechf D gdbehfca 9 在一个无向图中 所有顶点的度数之和等于所有边数的 倍 A 1 2 B 1 C 2D 4 10 设串 s1 ABCDEFG s2 PQRST 函数 con x y 返回 x 和 y 串的连接串 subs s i j 返 回串 s 的从序号 i 的字符开始的 j 个字符组成的子串 len s 返回串 s 的长度 则 con subs s1 2 len s2 subs s1 len s2 2 的结果串是 A BCDEF B BCDEFGC BCPQRST D BCDEFEF 三 应用题 每小题三 应用题 每小题 8 8 分 共分 共 3232 分 分 1 一棵深度为 h 的满 m 叉树具有如下性质 第 h 层上的结点都是叶结点 其余各层 上每个结点都有 m 棵非空子树 若按层次从上到下 每层从左到右的顺序从 1 开始对全部结点编号 试计算 1 第 k 层结点数 1 k h 2 整棵树结点数 3 编号为 i 的结点的双亲结点的编号 4 编号为 i 的结点的第 j 个孩子结点 若有 的编号 得分得分 2 已知图 G 的邻接表如图 1 所示 请写出 1 其从顶点 v1 出发的深度有限搜索序列 2 其从顶点 v1 出发的广度优先搜索序列 图 1 图 G 的邻接表 3 以关键码序列 503 087 512 061 908 170 897 275 653 426 为例 手工执行快速排序 排序算法 写出每一趟排序结束时的关键码状态 答答 题题 勿勿 超超 装装 订订 线线 装装 订订 线线 v1 v2 v3 v4 v5 v6 V2V5V4 v3V5 V4V6V3 V6 4 使用哈希函数 H key key 11 把一个整数值转换成哈希表下标 现要把数据 1 13 12 34 38 33 27 22 插入到哈希表 表 1 中 1 使用线性探测再散列法构造哈希表 请在表 1 所示的哈希表中与哈希地址对应的位 置上 填写出相应的关键字值和元素插入时的探查次数 2 假设查找每个元素的概率相同 求出查找成功时的平均查找长度 表 1 哈希 地址 012345678910 关键 字值 探查 次数 四 算法阅读题 每小题四 算法阅读题 每小题 9 9 分 共分 共 1818 分 分 1 完成二叉树按层遍历的算法 void leveltravel struct treenode bt struct treenode p a n int rear front 1 p bt rear a rear p while rear front front p a front printf c p data If p left null rear rear 1 n a rear If p right null rear rear 1 n a rear 得分得分 答答 题题 勿勿 超超 装装 订订 线线 装装 订订 线线 2 下面算法是对直接插入排序算法的改进 请填写完整 void weizhisort struct node r n 1 int n int low high mid j i for i 2 i n i r 0 r i low high while low high mid low high 2 if r 0 key low j r j 1 r j r low r 0 五 算法设计题 每小题五 算法设计题 每小题 1010 分 共分 共 2020 分 分 1 已知二叉树中的结点类型 BinTreeNode 定义为 struct BinTreeNode ElemType data BinTreeNode left right 其中 data 为结点值域 left 和 right 分别为指向左 右子女结点的指针域 请写一函数 功能是返回二叉树 BT 中值为 x 的结点所在的层号 Int NodeLevel BinTreeNode BT