Blog47 全国大学生智能大赛【算法赛项】

算法赛项模拟试卷

1、一个顺序存储地线性表，设每个结点需占m个存储单元，假设第一个结点地地址为da1，那么第I个结点的地址为：

1
2
3

答案：da1 + (I - 1)*m
解析：
	第I个结点的地址就是第一个结点的地址加上前I-1个结点占用的存储单元总数

*2、设有广义表D(a, b, D)，其深度为：

1
2
3

答案：∞
解析：
	广义表的深度定义为表的最大嵌套层次，由题D是一个嵌套的广义表，其中包含了2个原子a和b，以及广义表D自身，这就形成了递归结构。由于广义表D包含自身，因此该广义表会不断地嵌套下去，形成无限递归的嵌套结构。因此广义表D(a, b, D)的深度为∞，即无限深度

3、在一棵二叉树上第5层的结点数最多是：

1
2
3

答案：16
解析：
	满二叉树第五层结点最多为：1->2->4->8->16

4、在带有头节点的单链表HL中，要向表头插入一个由指针p指向的结点，则执行：

答案：p->next=HL->next;HL->next=p;
解析：
	为了向表头插入结点，需要调整链表中结点的链接关系：
	1）将新结点p的next指针指向当前头结点HL的下一个结点(即HL->next)
	2）然后将头结点HL的next指针指向新结点p，这样新结点就被插入到了链表的头部

*5、广义表A(a)，那么表尾为：

答案：空表
解析：
	表尾是去掉表头元素后的剩余部分，广义表A(a)的表头是元素a，表尾是去掉表头a后的部分
	由于A(a)中只有一个元素a，因此去掉这个元素后，剩下的部分就是空表

6、栈和队列的共同特点是：

答案：只允许在端点处插入和删除
解析：
	共同特点是都是线性表，并且都允许在端点处进行插入和删除操作
	1）栈是一种"后进先出"(LIFO)的数据结构，插入和删除操作只能在同一端进行，即栈顶
	2）队列是一种"先进先出"(FIFO)的数据结构，插入操作在队尾进行，删除操作在队首进行

7、一个栈的入栈序列为a, b, c，那么出栈序列不可能是：

1
2
3

答案：c, a, b
解析：
	c必须在a和b入栈之后出栈，但c已经是最后入栈的元素，它不可能先出栈并且在a和b之后再出栈

8、设有两个串t和p，求p在t中首次出现的位置的运算叫做：

1
2
3

答案：模式匹配
解析：
	常见的模式匹配算法有暴力匹配、KMP算法、BM算法等

9、设有一个递归算法如下：

int fact(int n){
    if (n <= 0) return 1;
    else return n * fact(n - 1);
}

下面正确的表达是：

1
2
3

答案：以上结论都不对
解析：
	计算fact(n)需要n-1次递归

*10、AOV网是一种：

答案：有向无环图
解析：
	AOV(Activity on Vertex)是一个表示顶点活动的有向图，通常用于表示任务之间的依赖关系。为了保证任务的依赖关系是可行的，AOV网中的边代表了任务之间的顺序关系，而图中不能存在环(环意味着循环依赖，任务无法完成)
	因此AOV网是一种有向无环图(DAG, Directed Acyclic Graph)

11、在数据构造的讨论中把数据构造从逻辑上分为：

答案：线性结构和非线性结构
解析：
	线性结构：数据元素之间是一对一的关系，比如：数组、链表、队列、栈等
	非线性结构：数据元素之间存在一对多或者多对多的关系，比如：树结构、图结构等

12、栈的数组表示中，top为栈顶指针，栈空的条件是：

1
2
3

答案：top = -1
解析：
	在栈的数组表示中，top是指向栈顶元素的指针，栈空的条件是栈中没有任何元素，即top指向的位置表示栈中没有有效元素。在数组实现的栈中，通常初始化时，top被设置为-1，表示栈为空，因为当栈为空时，栈顶没有有效元素，而数组的下标从0开始，因此top = -1表示栈中没有元素

13、假定一个顺序存储的循环队列的队头和对尾指针分别为f和r，那么判断队空的条件为：

答案：f == r
解析：
	在顺序存储的循环队列中，队列头指针f和队列尾指针r分别表示队列的头和尾位置，循环队列的一个重要特性是：队尾指针可以绕回队列的起始位置，而不会超过队列的容量。
	判断队列是否为空的条件是：队头指针和队尾指针相等，也就是说当f == r时队列为空，这意味着此时队列中没有有效的元素。

14、算法分析的目的是：

1
2
3

答案：分析算法的效率以求改良
解析：
	算法分析的主要目的是评估算法的效率，以便进行改进和优化。通过分析算法的时间复杂度和空间复杂度，我们可以了解算法在处理不同规模的问题时的性能表现，从而为算法的改良提供依据。

*15、设单循环链表中结点的构造为[data, link]，且rear是指向非空的带表头结点的单循环链表的尾结点的指针。假设想删除链表第一个结点，那么应执行以下哪一个操作：

1
2
3

答案：s = rear;rear = rear->link;delete s;
解析：
	在单循环链表中，尾指针rear指向最后一个结点，而最后一个结点的link指针则指向链表的头结点。为了删除头节点，首先要将尾结点的link改为指向新的头结点(即原头节点的下一个节点)，然后删除原头节点

16、下面程序段的时间复杂度为：

int f(unsigned int n){
    if (n == 0 || n == 1) return 1;
    else return n * f(n - 1);
}

1
2
3

答案：O(n!)
解析：
	给定的递归函数是用来计算n!，递归调用的深度为n，每次递归调用中还会进行一次乘法运算

17、顺序搜索算法适合于存储构造为【】的线性表：

1
2
3

答案：顺序存储或存储
解析：
	顺序搜索的特点是依次遍历每一个元素，直到找到目标元素或遍历完所有元素。因此，无论是顺序存储还是链式存储，都可以进行顺序搜索。

18、算法一般都可以用哪几种控制结构组合而成：

答案：顺序、选择、循环
解析：
	算法通常可以由3种基本的控制结构组合而成：
	1）顺序：按照先后顺序执行操作
	2）选择：根据条件判断执行不同的操作
	3）循环：重复执行某段操作，直到满足条件
	这3种控制结构式编写任何算法的基础，所有复杂的算法都可以通过它们的组合实现

19、试问计算x(x(8))需要计算【】次x函数：

int x(int n){
    if (n <= 3) return 1;
    else return x(n - 2) + x(n - 4) + 1;
}

答案：9次

*20、对于一个具有n个顶点和e条边的无向图，进展拓扑排序时，总的时间为：

答案：n+e
解析：
	拓扑排序的时间复杂度取决于遍历图的所有顶点和边的操作，在一个具有n个顶点和e条边的有向图种，拓扑排序通常通过广度优先搜索BFS或深度优先搜索DFS实现。
	遍历所有顶点的时间复杂度为O(n)
	遍历所有边的时间复杂度为O(e)
	因此总的时间复杂度为O(n+e)

21、将一个递归算法改为对应的非递归算法时，通常需要使用：

1
2
3

答案：栈
解析：
	通常需要使用栈(Stack)来模拟递归调用过程，递归函数调用的过程本质上是一个后进先出的过程，而栈的结构正好符合这一特性。通过栈来保存每次递归调用的状态，就可以实现非递归的算法。

*22、判断一个有向图是否存在回路，除了可以利用拓扑排序方法外，还可以利用：

答案：深度优先遍历算法
解析：
	1）求最短路径的Dijkstra方法：这个方法主要用于求解图中最短路径，不能直接用于判断是否存在回路
	2）广度优先遍历算法：可以用于遍历图，但不专门用于检测回路
	3）深度优先遍历算法：可以通过判断在遍历过程种是否遇到已经访问过的节点来检测回路
	4）求关键路径的方法：这个方法与回路检测无关，主要用于项目管理种的时间优化问题

23、在数组A种，每一个数组元素A[i][j]占用3个存储字，行下标i从1到8，列下标j从1到10。所有数组元素相继存放于一个连续的存储空间中，那么存放该数组至少需要的存储字数是：

1
2
3

答案：240
解析：
	所需存储字节数 = 行数 * 列数 * 每个元素占用的字节数

24、在循环队列中用数组A[0...m-1]存放队列元素，其队头和队尾指针分别为front和rear，那么当前队列中的元素个数是：

1
2
3

答案：(rear - front + 1) % m
解析：
	能够处理环绕情况，也就是当队尾指针在数组的前面而队头指针在数组的后面时，仍然能正确计算出队列的元素个数

25、如果想在4092个数据中只需要选择其中最小的5个，采用【】方法最好：

答案：堆排序
解析：
	1）冒泡排序：不适合大规模数据的部分排序，时间复杂度较高
	2）快速排序：是一种全排序方法，虽然效率高，但对只选最小的5个不够优化
	3）锦标赛排序：用于寻找极值，但效率不及堆排序
	4）堆排序：特别适合这种场景，可以维护一个大小为5的最小堆，高效地选出最小的5个

26、采用线性链表表示一个向量时，要求占用的存储空间地址：

1
2
3

答案：可连续可不连续
解析：
	线性链表可以分散存储，不要求任何部分连续

27、设单链表中结点构造为(data, link)，指针q所指结点是指针p所指结点的直接前驱，假设在*q与*p之间插入结点*s，那么应指向以下哪一个操作：

答案：s->link = p->link;p->link = s;
解析：
	1）让s的指针指向p，即s->link = p->link;
	2）让p的指针指向s，即p->link = s;

28、采用顺序搜索方法查找长度为n的顺序表时，搜索成功的平均搜索长度为：

答案：(n + 1)/2
解析：
	对于顺序搜索，假设每个元素被查找到的概率是相等的，那么成功的平均搜索长度为：
	(1 + 2 + ... + n)/n = (n + 1)/2

29、递归表、再入表、纯表、线性表之间的关系为：

答案：递归表 > 再入表 > 纯表 > 线性表
解析：
	1）递归表表示可以递归调用的表
	2）再入表允许重入操作，即可以再多线程或中断的情况下安全调用
	3）纯表表示不含任何递归或再入特性
	4）线性表是最基础的表结构，简单、顺序存储

30、二维数组是其数组元素为线性表的线性表【√】

1 2	解析：二维数组实际上是线性表的数组，因此每个元素也是线性表

31、线性表的顺序存储构造的特点是逻辑关系上相邻的两个元素在物理位置上也相邻【√】

*32、任一棵二叉搜索树的平均搜索时间都小于用顺序搜索法搜索同样结点的顺序表的平均搜索时间【√】

1	二叉搜索树在平均情况下，查找效率高于顺序搜索表

33、二叉排序树可以是一棵空树【√】

*34、带权连通图的最小生成树的权值之和一定小于它的其它生成树的权值之和【√】

1	最小生成树是指权值之和最小的生成树

35、n个结点的有向图，假设它有n(n-1)条边，那么它一定是强连通的【×】

1	即使有n(n-1)条边，也不一定是强连通的，需要确保每个结点都能通过有向路径到达其他结点

36、空串与由空格组成的串没有区别【×】

1	空串是长度为0的字符串，而由空格组成的字符串是包含一个或多个空格字符的串，它们在计算机中是不同的

37、从逻辑关系上讲，数据构造主要分为两大类：线性构造和非线性构造【√】

1	数据结构可以分为线性结构(入数组、链表)和非线性结构(如树、图)

38、二叉树是树的一种特殊情况【√】

1	二叉树是树的特殊形式，每个结点最多由两个子结点

39、线性表的逻辑顺序与物理顺序总是一致的【×】

1	在线性表的顺序存储结构中，逻辑顺序与物理顺序一致，但在链式存储结构中，逻辑顺序和物理存储位置可能并不一致

*40、矩阵连乘问题的算法可由【】设计实现

动态规划

*41、在稀疏矩阵的带行指针向量的链接存储中，每个单链表中的结点都具有相同的【】

列号

*42、使用回溯法进行状态空间树裁剪分支时一般有两个标准：约束标准和目标函数的界，N皇后问题和0/1背包问题正好是两种不同的类型，其中同时使用约束条件和目标函数的界进行裁剪的是【】

0/1背包问题

*43、拉斯维加斯算法找到的解一定是【】

正确

44、算法的空间复杂度指的是算法运行所需的【】

辅助存储空间

45、栈是一种【】的数据结构

线性/后进先出

46、从二叉搜索树中查找一个元素时，其时间复杂度大致为【】

$O(log2n)$

47、快速排序在最坏情况下的时间复杂度为【】

$O(n^2)$

*48、以广度优先或以最小耗费方式搜索问题解的算法称为【】

分支限界法

49、【】是贪心算法可行的第一个基本要素，也是贪心算法与动态规划算法的主要区别

1	最优子结构/贪心选择性质

算法赛项模拟试卷

❤日拱一卒，功不唐捐❤