专业 学号 姓名
字key1或者基于关键字key2的查找，可以使用一种类似于二叉树的结构——2-d树。但是在一棵2-d树中，偶数层用key1进行分叉，奇数层用key2进行分叉(根结点层数为0)。图中就是一棵2-d树的示例，以名（first name）和姓（last name）作为两个关键字对二战以后的美国总统进行查找。总统的姓名是按照年代顺序插入的（Truman、Eisenhower、Ford、Carter、Reagan、Bush、Clinton）。请根据上述描述，编写实现2-d树的插入操作。
算法设计思想：
从根结点开始，从上往下搜索元素X合适的插入位置，搜索过程中，记录当前结点current所在层次（根结点层次为0），若current的层次为奇数时，用key2进行比较，当current->key2>x->key2，则搜索current的左子树，否则搜索其右子树；同理，若current的层次为偶数时，用key1进行比较，当current->key1>x->key1，则搜索current的左子树，否则搜索其右子树。搜索过程中要记录当前结点current的父结点，以便找到一个空指针的时候，可以直接在这个位置插入新的结点，并将元素x存储在这个新结点中。
算法设计题酌情给分 2、（8分）现有一个计算机网络和一个双向连接表，每一个连接A－B表示文件可以在计算机A和B之间传送，如果存在M个连接和N台计算机，设计一个有效的算法帮助判定能否将一个文件从网络上任意一台计算机发送到任意的另外一台计算机上。 要求：算法时间复杂性为O(M+N)
算法设计思想：将每一台计算机视为某一张无向图G中的结点，每一个连接A－B表示结点A和B之间存在一条边。可通过图的连通性判断是否能将一个文件从网络上任意一台计算机发送到任意的另外一台计算机上。由于这样的一张图具有N个结点和M条边，为了满足时间复杂性的要求，采用邻接表的方式实现图，并对图进行深度优先搜索
也可以初始将每一台计算看成一个个独立的集合，将每一个连接A－B看成是一个等价关系，对于所有的连接进行处理，测试A和B是否处于同一个集合中，若非同一集合，则合并两个集合，当且仅当所有的计算机最终都位于同一个集合中，才能确定可将一个文件从网络上任意一台计算机发送到任意的另外一台计算机上。使用大小求并和路径压缩的方法，存在2M次Find和至多N-1次Union，实际时间复杂性可视为O(M+N)
算法设计题酌情给分