哈工大2003年数据结构考研真题 答案2

哈工大计算机考研全套视频和资料 真题 考点 典型题 命题规律独家视频讲解 哈工大计算机考研全套视频和资料 真题 考点 典型题 命题规律独家视频讲解 详见 网学天地 详见 网学天地 www e 咨询 咨询 QQ 2696670126 哈尔滨工业大学计算机学院2003年研究生入学试题数据结构答案 哈尔滨工业大学计算机学院2003年研究生入学试题数据结构答案 一 填空 1 头指针 2 BFAWEH BFWAEH FBHAEW AFBWEH 3 K路归并 并行操作的缓冲处理 初始归并段 4 最小 5 n 1 6 没有后继 二 单项选择与判断 一 1 A 2 D 3 D 4 A 二 5 错误 6 正确 7 正确 8 错误 9 错误 三 简答题 1 堆与二元查找树均满足任一节点的元素值小于其左右儿子的值 但是若按中根顺序遍历 一颗二元查找树 将得到最终结果既递增顺序 而堆无此性质 需经过整理才得到最终结 果 2 用克鲁斯卡尔 Kruskal 算法较好 该算法假设G V E 是一个具有n个顶点的连通 图 T V TE 是G的最小生成树 U的初值等于V 即包含有G中的全部顶点 TE的初值为 空集 该算法的基本思想是 将G中的边按权值从小到大的顺序依次选取 若选取的边使生 成树T形成回路 则将其舍弃 如此进行下去 直到TE中包含n 1条边为止 此时的T即为最 小生成树 3 算法思想 由于栈的特点是先进后出 为了模拟先进先出的队列 必须用两个栈 一个 栈 S1 用于插入元素 另一个栈 S2 用于删除元素 每次删除元素时应将前一个栈的 所有元素读出然后进入第二个栈中 这样才能达到模拟队列的效果 哈工大计算机考研全套视频和资料 真题 考点 典型题 命题规律独家视频讲解 哈工大计算机考研全套视频和资料 真题 考点 典型题 命题规律独家视频讲解 详见 网学天地 详见 网学天地 www e 咨询 咨询 QQ 2696670126 四 int DELETE HASH F keytype W int locate int yes 0 locate h W if locate 1 if F locate key W F locate key deleted yes 1 else ERROR 出错 return yes 五 设计思想 先对每个结点赋予一个层号 level域的最大值即为树的高度 struct BTREE int LC int RC int LEVEL 树的抽象数据型 哈工大计算机考研全套视频和资料 真题 考点 典型题 命题规律独家视频讲解 哈工大计算机考研全套视频和资料 真题 考点 典型题 命题规律独家视频讲解 详见 网学天地 详见 网学天地 www e 咨询 咨询 QQ 2696670126 int level BTREE T maxsize int i count LEVEL count LEVEL 1 for i 1 icount count T LC if T RC count count T RC 得到这颗树共有多少个结点 for i 1 i count i T level 0 T 1 LEVEL 1 for i 1 i count i if T LC 0 T T LC level T level 1 if T RC 0 T T RC level T level 1 完成对每个结点赋予层号 哈工大计算机考研全套视频和资料 真题 考点 典型题 命题规律独家视频讲解 哈工大计算机考研全套视频和资料 真题 考点 典型题 命题规律独家视频讲解 详见 网学天地 详见 网学天地 www e 咨询 咨询 QQ 2696670126 for i 1 iLEVEL LEVEL T level return LEVEL 返回树的高度 六 设计思想 若存在这样的顶点 该顶点到其他任一结点都有一条有向路 又因为该有向图 是无环路的 那么该顶点到这些结点之间的路构成一个树 此树上的结点数应该等于该图 的结点数 若不等于 小于 则不存在这样的结点 因此 从任意结点开始 遍历此图 先深 先广均可 若visited的结点数等于图的结点数 存在 否则不存在 设此有向图用邻接表表示 邻接表的抽象数据型如下所示 data firstarc adjrex next struct node int adjvex node next 结点的型 struct g vertexttype data node firstarc typedef g ADJLIST 邻接表的型 哈工大计算机考研全套视频和资料 真题 考点 典型题 命题规律独家视频讲解 哈工大计算机考研全套视频和资料 真题 考点 典型题 命题规律独家视频讲解 详见 网学天地 详见 网学天地 www e 咨询 咨询 QQ 2696670126 法一 广度优先遍历 使用队列 int rbfs ADJLIST g int vi vj int i count yes yes 0 count 1 QUEUE Q for i 0 iadjdata if visited w 0 visited w 1 count ENQUEUE w Q else p p next 哈工大计算机考研全套视频和资料 真题 考点 典型题 命题规律独家视频讲解 哈工大计算机考研全套视频和资料 真题 考点 典型题 命题规律独家视频讲解 详见 网学天地 详见 网学天地 www e 咨询 咨询 QQ 2696670126 if count V V为该有向图中结点总数 yes 1 return yes 法二 深度优先遍历 使用栈 int rdfs ADJLIST g int vi vj int i count yes yes 0 count 1 STACK S for i 0 iadjdata p p next if p NULL POP S else 哈工大计算机考研全套视频和资料 真题 考点 典型题 命题规律独家视频讲解 哈工大计算机考研全套视频和资料 真题 考点 典型题