算法概述试题.pdf

chap1算法概述

一.单选题（共1题，14.2分）

1.(单选题)集合的位向量表示法，合并集合操作的时间复杂度为()

A.与问题规模n无关

B.O(n)

C.O(1)

2

D.O(n)

答案解析：位向量表示法是一种常用于集合操作的技巧。在这种方法中，每个集合使用一个

位向量来表示，其长度等于全集的大小。每一位的值（0或1）表示该元素是否在集合中。

合并两个集合通常对应于对两个位向量进行按位或（OR）运算。这种操作涉及将两个相同

长度的位向量逐位进行逻辑或运算。

这种操作的时间复杂度主要取决于位向量的长度，也就是与问题规模n有关，具体地，当

位向量的长度为n时，需要对n位依次进行或运算。

二.多选题（共1题，14.3分）

2.(多选题)算法的重要特性()。

A确定性

B能行性

C输入

D输出

E有穷性

三.填空题（共1题，14.3分）

3.(填空题)

写一个算法交换两个变量x、y的值不使用第三个变量，使用三条语句如下：

——，——，——

正确答案：

(1)x=x+y

(2)y=x-y

(3)x=x-y

四.判断题（共4题，57.2分）

4.(判断题)语句returnsum(x,y);执行频度为1()

A对

B错

解析：如果在上下文中，returnsum(x,y);只在某个特定时刻被调用一次，那么其频度确实

是1。

但是，如果这个语句在函数内部或在循环中被频繁调用，则它的执行频度会大于1。

22

5.(判断题)T(n)=n+n+1的上界函数是n

A对

B错

6.(判断题)算法时间复杂度为O(1)说明算法执行时间是单位时间()

A对

B错

解析：因为O(1)并不意味着绝对的单位时间，而是指在规模变化时，时间复杂度保持常数，

不随输入规模的变化而改变。

7.(判断题)带加权规则的Union算法中，Parent(1)=-8,Parent(2)=-4，1、2代表的集合合并

后,集合的根是1,Parent(1)=-12,Parent(2)=1

A对

B错

解析：

概念回顾

1.Parent数组：在并查集的数据结构中，Parent[i]通常用来表示元素i的父节点。如

果Parent[i]是负数，通常表示i是根结点，并且负数的绝对值表示树的大小（即集

合中元素的数目）。

2.带加权合并规则：在执行Union操作时，通常会将较小的树（集合）合并到较大的

树（集合）中，以保持树的平衡，减少树的高度，提高查找效率。

给定数据分析

现在我们有：

oParent(1)=-8，意味着元素1是根节点，集合大小为8。

oParent(2)=-4，意味着元素2是根节点，集合大小为4。

如果我们要合并元素1和2，则根据带加权合并规则，我们应该将容量较小的集合（2的

集合，大小为4）合并进去容量较大的集合（1的集合，大小为8）。

合并过程

在合并过程中，因为1代表的集合较大，所以在合并后树的结构将是：

o1仍然是根节点。

o2将成为1的子节点。

根据合并后的规则：

新的Parent(1)代表的是新根节点的Parent值，表示树的总大小。原来集合1的

大小是8，原来集合2的大小是4，所以合并后的大小为8+4=12。

根据习惯，通常将根的Parent值设置为负的集合大小，所以Parent(1)应该是-12。

接下来，我们也要更新Parent(2)：

在合并中，元素2成为元素1的子节点，因此Parent(2)现在应该指向1，

即Parent(2)=1。

一、第一章（100分）

1.【判断题】（4分）

n

H(n)=2H(n-1)+1求解结果为H(n)={2-1}（）

对

错

解析：

1.初始条件：首先，我们需要一个初始条件。通常取H(0)=c（其中c是一个常数，

具体值在解释中不影响根本求解）。

2.展开递归关系：

oH(n)=2H(n-1)+1

oH(n-1)=2H(n-2)+1

o