第六章

  1. 从概念上讲,树、森林和二叉树是三种不同的数据结构,将树、森林转化为二叉树的基本目的是什么?并指出树和二叉树的主要区别。

    树的孩子兄弟表示法和二叉树的二叉链表表示法,本质是一样的,只是解释不同,也就是说(树是森林的特例,即森林中只有一颗树的特殊情况) 可用二叉树唯一表示,并可使用二叉树的一些算法去解决树和森林的一些问题。 树和二叉树的区别有三点: 1) 二叉树的度至多为2,树无限制; 2)二叉树有左右子树之分,即使在只有一个分支的情况下,也必须指出是左子树还是右子树; 3)二叉树允许为空,树一般不允许为空(个别书上允许为空)。

  2. 树和二叉树之间有什么样的区别和联系?

    树和二叉树逻辑上都是树型结构,二叉树不是树的特例,区别有: 1) 二叉树的度至多为2,树无限制; 2)二叉树有左右子树之分,即使在只有一个分支的情况下,也必须指出是左子树还是右子树; 3)二叉树允许为空,树一般不允许为空(个别书上允许为空)。

  3. 设有一颗算术表达式树,用什么方法可以对该树所表达的表达式求值?

    方法有二: 1)对该算术表达式(二叉树)进行后序遍历,得到表达式的后序遍历序列,再按后缀表达式求值; 2)递归求出左子树的表达式值,在递归求出右子树的表达式值,最后按照根结点运算符(+、-、*、/ 等)进行最后的求值。

  4. 有n个结点并高度为n的二叉树的数目是多少?

    2n12^{n-1} (本题等价于高度为n的满二叉树有多少个叶子结点,从根结点到叶子结点的单枝树是不同的二叉树)

第七章

  1. 用邻接矩阵表示图时,矩阵元素的个数与顶点是否相关?与边的条数是否有关?

    设图的顶点个数为n(n>0),则邻接矩阵元素个数为n2n^2, 即顶点个数的平方,与图的边数无关。

  2. 对一个图进行遍历可以得到不同的遍历序列,那么导致得到的遍历序列不唯一的因素有哪些?

    开始遍历的顶点不同; 存储结构不同; 在邻接表的情况下邻接点的顺序不同;

  3. 在什么情况下Prim算法与Kruskual算法生成不同的MST(生成树)?

    在有相同权值边时生成的不同的MST。

  4. 一个带权无向图的最小生成树是否一定唯一?在什么情况下构造出的最小生成树可能不唯一?

    一个带权无向图的最小生成树不一定是唯一的。从Kruskual算法构造最小生成树的过程可以看出,当从图中选择当前权值最小的边,并且这些边与已经选取的边构成回路,此时这些边就不可能同时出现在一颗最小生成树中,对这些变得不同选择结果可能会产生不同的最小生成树。

查找

名词解释:

  1. 哈希表

    根据关键字而直接进行访问的数据结构。也就是说,散列表建立了关键字和存储地址之间的一种直接映射关系。

  2. 叙述B-树的定义,主要用途是什么?

    B树是为了存储设备或者磁盘设计的一种平衡查找树, m阶B树要满足如下特性: 1)若根结点不是终端结点,则至少有两棵子树。 2)每个结点最多有m棵子树,即最多有m-1个关键字。 3)除根点外的所有非叶子结点至少有m2\lceil \frac{m}{2} \rceil棵子树,即至少含有m21\lceil \frac{m}{2}\rceil-1个关键字。 4)所有叶子结点都出现同一层,并且不带信息。 B树是所有结点平衡因子等于0的多路平衡查找树。

  3. B-树和B+树的主要差异是什么?

    B+树是应数据库要求出现的一种B树的变形树, m阶B树与m阶B+树的主要差异如下: 1)在B+树中,具有n个关键字的结点只含n棵子树,即每个关键字对应一颗树; 而B树中,n个关键字的结点含义n+1棵子树。 2)在B+树中,每个结点(非根内部结点)的关键字个数n的范围是m2nm\lceil\frac{m}{2}\rceil\leq n \leq m(根结点:1nm1\leq n \leq m); 在B树中,每个结点(非根内部结点)的关键字个数n的范围是m21nm1\lceil\frac{m}{2}\rceil -1 \leq n \leq m-1(根结点:1nm11\leq n \leq m-1)。 3)在B+树中,叶结点包含信息,所有非也结点仅起索引作用,非叶结点中的每个索引项只含有对应子树的最大关键字和指向该子树的指针,不含该关键字对应记录的存储地址。 4)在B+树中,叶结点包含了全部关键字,即在非叶结点中出现的关键字也会出现在叶结点中; 而B树中,叶结点包含的关键字和其他结点包含的关键字不会重复。

  4. 平衡二叉树

    避免树的高度增长过快,降低二叉排序树的性能,规定在插入和删除二叉树结点时,要保证任意结点的左、右子树高度差的绝对值不超过1。

  5. 平衡因子

    某结点的左子树与右子树高度(深度)差即为该结点的平衡因子。 平衡因子只能为-1、0、1.

简答

  1. 散列表存储的基本思想是什么?

    关键字的值决定数据元素的存储地址。

  2. 散列存储中解决碰撞的基本方法有哪些? 其基本思想是什么?

    一. 开放定址法:形成地址序列公式为:Hi=(H(key)+di)%mH_i=(H(key)+d_i)\%m,其中m为表长,did_i是增量。根据did_i取法不同,又分为三种: 1)di=1,2,,m1d_i=1,2,···,m-1 称为线性探测再散列,其特点是逐个探测表空间。 2)di=12,12,22,22,,±k2(km/2)d_i=1^2,-1^2,2^2,-2^2,···,\pm k^2(k\leq m/2) 称为二次探测再散列,它减少了聚集,但不容易探测到所有的表空间,只有当表长如4j+3(j)4j+3(j为整数)的素数时才有可能。 3)did_i为伪随机数序列,称为随机探测再散列。 二. 再散列法 Hi=RHi(key)H_i=RH_i(key)i=1,2,,ki=1,2,···,k, 是不同的散列函数,即发生冲突时,用另一散列函数解决冲突。该方法不易聚集,但耗费计算时间。 三. 链地址法 将关键字为同义词的记录存储在同一链表中。这种方法元素个数不受表长限制,插入删除操作方便,但增加了指针空间的开销。 四. 建立公共溢出区 设H[0..m1]H[0..m-1]为基本表,凡关键字为同义词的记录,就放入溢出区。

  3. 用分离的同义词子表解决碰撞和有结合的同义词表解决碰撞属于哪种基本方法?他们各有何特点?

    这两种方法均属于链地址法,链地址向量空间中的每个元素不是简单的地址,而是关键字和指针两个域。 前者指针域为动态指针,具有元素个数不受表长限制,插入删除操作方便,但增加了指针空间的开销的特点。 后者实际是静态链表,同义词存在同一地址向量空间(从最后向前找空闲单元),以指针相连。节省了空间,但易产生“堆积”,查找效率低。

  4. 用线性探测法解决碰撞时,如何处理被删除的结点?为什么?

    要在被删除结点的散列地址处做标记,不能物理的删除。否则中断了查找通路。

  5. 散列法的平均检索长度不随( )的增加而增加,而是随( )的增大而增加。

    记录;负载因子

  6. 如何衡量hash函数的优劣?简要叙述hash表技术中的冲突概念,并指出三种解决冲突的方法。

    评价哈希函数优劣的因素有:能否将关键字均匀影射到哈希空间上,有无好的解决冲突的方法,计算哈希函数是否简单高效。 冲突是指新输入的关键字与哈希表内已有关键字哈希值重复。 解决冲突的方法有:开放定址法、再散列法、链地址法、建立公共溢出区。

  7. Hash方法的平均查找路长决定于什么?是否与结点个数N有关?

    哈希方法的平均查找长度主要取决于负载因子(表中实有元素与表长之比),它反映了哈希表的装满程度,该值一般取0.65~0.9。

  8. 在采用线性探测法处理冲突的散列表中,所有同义词在表中是否一定相邻?

    不一定,哈希地址为i(0im1)i (0\le i \le m-1)的关键字,和为解决冲突的探测序列都争夺哈希地址ii

  9. 在B-树和B+树中查找关键字有何不同?

    在B-树中查找关键字从根结点开始,从往下查找结点,然后在结点内查找关键字,得出查找成功与否的结论。 在B+树中非终端结点是索引部分,其查找从根开始,从根往下查到关键字后,要继续查到最下层结点,得到查找成功的结论。 此外,B+树还可以在最下层从最小关键字开始,从左往右进行顺序查找,B-树则不能做顺序查找。

  10. 查找算法中,设置监视哨的作用是什么?

    监视哨的作用是免去查找过程中每次都要检测整个表是否查找完毕,提高了查找效率。

  11. 顺序查找、二分查找、哈希查找的时间复杂度分别为O(n)O(n)O(2n)O(\log_2n)O(1)O(1)。既然有了高效的查找方法,为什么低效的方法还不放弃?

    时间复杂度是判断检索方法的一个重要指标,但不是唯一指标。使用什么检索方法要综合考虑。哈希检索时间O(1)O(1),查找速度最快,但需要构建哈希函数,计算哈希地址,插入时要有解决冲突的方法;二分法O(2n)O(\log_2n),需要元素有序且顺序存储; 顺序查找O(n)O(n),但对检索表无要求,数据有序无序均可,在数据较少时使用方便。

  12. 二分法查找适不适合链表结构的序列,为什么?用二分查找速度必然比线性查找的速度快,这种说法对吗?

    不适合,虽然有序链表顺序排列,但是查找结点无法随机访问,故不能。 二分查找速度一般情况下是快些,但是特殊时未必。例如所查数据位于首位时,线性查找更快。

  13. 用比较两个元素大小的方法在一个给定的序列中查找某个元素的时间复杂度下限是什么如果要求时间复杂度更小,你采用什么方法?此方法的时间复杂度是多少?

    查找某个元素的时间复杂度下限,如果理解为最短时间查找,则当关键字值与表头元素相同时,比较1次即可。想要降低时间复杂度,可以改用Hash查找,此方法时间复杂度为O(1)O(1)