2018年中国科学技术大学计算机科学与技术学院408计算机学科专业基础综合之数据结构考研核心题库
● 摘要
一、算法设计题
1． 令G=(V, E) 为一个有向无环图，编写一个给图G 中每一个顶点赋以一个整数序号的算法，并满足以下条件:若从顶点i 至顶点j 有一条弧，则应使i 【答案】算法如下: 对以邻接表存储的DAG 图g 重新编号, 使若有 记录结点的逆序序号 2． 假定用两个一维数组L 【N 】和R 【N 】作为有N 个结点1，2，…，N 的二叉树的存储结构。 和 分别指示结点i 的左儿子和右儿子， ，使 ) 表示i 的左(右) 儿子为空。试写一个 存放结点i 的父亲；然后再写一个判别结点u 是否 算法，由L 和R 建立一个一维数组为结点V 的后代的算法。 【答案】算法如下: 和 是含有N 个元素且指示二叉树结点i 左儿子和右儿子的一维数组 T 数组初始化 若结点i 的左子女是则结点L 的 第 2 页，共 37 页 ，则编号 求各顶点的入度 本算法据此建立结点i 的双亲数组T , 并判断结点U 是否是结点V 的后代 双亲是结点 i 若结点i 的右子女是R , 则R 的 双亲是 i 判断U 是否是V 的后代 3． 设给定关键字输入序列为(100，90，120，60，78，35，42，31，15) 用哈希法散列0-10的地址区间。要求设计一合理的哈希函数；冲突时用链表法解决，写出哈希算法，并构造出哈希表，在等概率查找情况下查找成功的平均查找长度是多少？ 【答案】算法如下: 关键字 链指针 用链地址法解决冲突，构造哈希表，哈希函数用 初始化 输入n(本例中n=9) 个关键字按题意x 互不相同 4等插入结点链入同义词表 构造的哈希表如图所示: 第 3 页，共 37 页 图构造的哈希表 查找成功时的平均查找长度 。 4． 请编写完整的程序。如果矩阵A 中存在这样的一个元素A[i，j]满足条件:A[i，j]是第i 行中值最小的元素，且又是第j 列中值最大的元素，则称之为该矩阵的一个马鞍点。请编程计算出m*n的矩阵A 的所有马鞍点。 【答案】算法如下: //A是的矩阵，本算法求矩阵A 中的马鞍点 //max数组存放各列最大值元素的行号，初始化为行号 //min数组存放各行最小值元素的列号，初始化为列号 0 //选各行最小值元素和各列最大值元素 //修改第j 列最大元素的 行号 " 修改第i 行最小元素的 列号 //第i 行最小元素的列号 是马鞍点， 元素值是 是马鞍点 // 第 4 页，共 37 页