不会飞的章鱼

熟能生巧，勤能补拙；念念不忘，必有回响。

极客时间_7天算法体验营_Day5-算法体验营-结课考试题

发表于 更新于 分类于
本文字数： 5k 阅读时长 ≈ 5 分钟

数组相关

  • 1,数组作为函数参数传递的是（A）

A. 数组的首地址

B. 数组元素个数

C. 数组中各元素值

D. 数组的大小

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
【答案解析】：考察的是数组传递给函数作为参数的原理。

传递方式如下三种：每种方式都会告诉编译器要接收一个指针，及数组的地址（首元素地址）
void myFunction(int *param)
{
    //形式参数是一个指针
}
void myFunction(int param[10])
{
    //形式参数是一个已定义大小的数组
}
void myFunction(int param[])
{
    //形式参数是一个未定义大小的数组
}
  • 2,在一个长度为n的顺序表中删除第i个元素，要移动_______个元素。如果要在第i个元素前插入一个元素，要后移_________个元素。 （A）

A. n-i，n-i+1

B. n-i+1，n-i

C. n-i，n-i

D. n-i+1，n-i+1 

1
2
3
【答案解析】：删除第i个元素，要移动后面n-i个元素

在第i个元素之前插入，要移动包括i在内的n-i+1个元素

链表相关

3,带头结点head的单向循环链表L为空的判断条件是？（C）

A. head==NULL

B. head->next==NULL

C. head->next==head

D. head!=NULL 

1
【答案解析】：基础概念，单向循环链表且带有头节点，判断为空，即循环链表只有头节点，自己指向自己，head->next = head，因此选C。

栈、队列相关

4,队列和栈有什么区别？(A)

A. 队列先进先出，栈后进先出

B. 队列和栈都是先进先出

C. 队列和栈都是后进先出

D. 栈先进先出，队列后进先出 

1
2
3
4
5
6
7
答案解析】：相同点：从"数据结构"的角度看，它们都是线性结构，即数据元素之间的关系相同。

不同点：栈（Stack）是限定只能在表的一端进行插入和删除操作的线性表。 队列（Queue）是限定只能在表的一端进行插入和在另一端进行删除操作的线性表。它们是完全不同的数据类型。除了它们各自的基本操作集不同外，主要区别是对插入和删除操作的"限定"。

栈必须按"后进先出"的规则进行操作：比如说，小学老师批改学生的作业，如果不打乱作业本的顺序的话，那么老师批改的第一份作业一定是最后那名同学交的那份作业，如果把所有作业本看作是一个栈中的元素，那么最后一个同学交的作业本就是栈顶元素，而第一个同学交的，也就是最低端的作业本，就是栈底元素，这就是对栈的读取规则。

而队列必须按"先进先出"的规则进行操作：打个比方，一些人去银行办理业务，一定是先去排队的最先得到服务，当然他也是第一个走出银行的（假设这些人都在一个窗口排队）。如果把所有这些等候服务的人看作是队的元素，第一个人就是对头元素，相应的，最后一个人就是队尾元素。这是队的读取规则。

二叉树相关

5,已知某二叉树的前序为（1-2-3-4-5-6-7-8-9），中序为（2-3-1-6-7-8-5-9-4），则它的后续为？ （A）

A. 3-2-8-7-6-9-5-4-1

B. 1-2-6-5-4-3-8-7-9

C. 5-4-2-1-3-7-6-9-8

D. 2-3-5-4-6-7-9-1-8 

1
【答案解析】：根据前序遍历可以确定根节点为1，再根据中序遍历可以确定A的左侧为左子树23，其余为右子树，再根据前序遍历得到左子树的根节点为2，右子树的根节点为4，然后递归下去就能恢复二叉树，然后后续遍历得到结果328769541。

6,在任意一棵二叉树的前序序列和后序序列中，各叶子之间的相对次序关系（ B ）

A. 不一定相同

B. 都相同

C. 都不相同

D. 互为逆序 

1
2
3
4
5
6
7
【答案解析】：

前序序列：根结点 --> 左子树 --> 右子树    

后序序列：左子树 --> 右子树 --> 根结点   

根据题目结合前序、后续的遍历顺序规则，如下图：

  • 第一个二叉树叶子节点D、C 先序和后序顺序均为先D后C

  • 第二个二叉树叶子节点B、D 先序和后序属性均为先B后D

结论：叶子节点位于左右两个分支上，先序和后序的遍历属性均是左子树在右子树之前（相对次序一定相同），和二叉树的样式无关。

递归相关

  • 7,采用递归方式对顺序表进行快速排序，下列关于递归次数的叙述中，正确的是（D）

A. 递归次数与初始数据的排列次序无关

B. 每次划分后，先处理较长的分区可以减少递归次数

C. 每次划分后，先处理较短的分区可以减少递归次数

D. 递归次数与每次划分后得到的分区处理顺序无关 

1
2
3
【答案解析】递归次数，取决于递归树，而递归树取决于轴枢的选择。树越平衡，递归次数越少。

而对分区的长短处理顺序，影响的是递归时对栈的使用内存，而不是递归次数
  • 8,对递归程序的优化的一般的手段是？（A）

A. 尾递归优化

B. 循环优化

C. 堆栈优化

D. 停止值优化 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
【答案解析】：尾递归是指，在函数返回的时候，调用自身本身，并且return语句不能包含表达式。这样，编译器或者解释器就可以把尾递归做优化，使递归本身无论调用多少次，都只占用一个栈帧，不会出现栈溢出的情况。 尾递归调用时，如果做了优化，栈不会增长，因此，无论多少次调用也不会导致栈溢出。

以斐波那契数列为例子，普通的递归版本如下：

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

具有"线性迭代过程"特性的递归---尾递归过程

int fab(int n,int b1=1,int b2=1,int c=3){ 
    if(n<3) 
        return 1; 
    else { 
        if(n==c) 
             return b1+b2; 
        else 
             return fab1(n,b2,b1+b2,c+1); 
    } 以fab(4)为例子 
} 

普通递归fab(4)=fab(3)+fab(2)=fab(2)+fab(1)+fab(2)=3  6次调用 

尾递归fab(4,1,1,3)=fab(4,1,2,4)=1+2=3                2次调用

分治相关

9,在快速排序，归并排序，插入排序，选择排序，冒泡排序中，使用到分治思想的算法个数有几个（B）

A. 1

B. 2

C. 3

D. 4

【答案解析】：分治思想是很多高效算法的基础，如归并排序、快速排序、傅立叶变换（快速傅立叶变换）。

DFS相关

  • 10,图的Depth-First Search(DFS)遍历思想实际上是二叉树（A）遍历方法的推广。

A. 先序

B. 中序

C. 后序

D. 层序

【答案解析】：深度先序，广度层次。

BFS相关

  • 11,图的BFS生成树的树高比DFS生成树的树高(A)

A. 小或相等

B. 小

C. 大或相等

D. 大 

1
2
3
【答案解析】：BFS是广度优先遍历，DFS是深度优先遍历。

对于一些特殊的图，比如只有一个顶点的图，其BFS生成树的树高和DFS生成树的树高相等。 一般的图，根据图的BFS生成树和DFS树的算法思想，BFS生成树的树高比DFS生成树的树高小

排序相关

  • 12,假设你只有100M的内存，需要对1G的数据进行排序，最合适的算法是？（A）

A. 归并排序

B. 插入排序

C. 快速排序

D. 冒泡排序

【答案解析】：归并排序的典型例子，很简单的题目，应该做对。

  • 13,一个数据表有51233个元素，如果仅要求找出其中最大的12个元素，你觉得采用下列哪种算法比较节省时间？（A）

A. 堆排序

B. 希尔排序

C. 快速排序

D. 直接选择排序

【答案解析】：本题比较常见排序算法，TopK问题，堆排序，因此选A

堆、时间复杂度相关

  • 14,从n个数里面找最大的两个数理论上最少需要比较多少次？（C）

A. 2logn

B. 2logn -1

C. n+ logn -2

D. 2n-3

【答案解析】：在n个数中找到最大的两个数的最少比较次数，可以考虑堆排序，首先建堆是时间复杂度为O(n)或比较n-1次，找到最大的一个，然后调整堆，找到次大元素，比较logn-1，因此选C。

哈希相关

  • 15,下面关于哈希查找的说法正确的是？（C）

A. 哈希函数构造的越复杂越好，因为这样随机性好，冲突小

B. 除留余数法是所有哈希函数中最好的

C. 不存在特别好与坏的哈希函数，要视情况而定

D. 若需在哈希表中删去一个元素，不管用任何方法解决冲突都只要简单地将该元素删去即可

【答案解析】：考察哈希，关于哈希有xxx的构造方法，具体哈希算法的好坏需要看情况而定，没有绝对的好与坏。A. 对于数据结构中的哈希函数有两个特点：简单，均匀性。所谓简单就是可以很快的产生一个较好的hash值，均匀性是指所有的数据可以均匀的映射到各个hash值上，避免产生大部分数据映射到少数的hash值上。B.不同的hash函数有不同的适应场景，各有优缺点。主要的方法有，直接定址法，数字分析法，平方取中法，折叠法，随机数法，除留余数法。D.对于空域法，还需要把冲突记录去掉。

二分查找相关

  • 16,若有序表的关键字序列为（b,c,d,e,f,g,q,r,s,t)，则在二分查找关键字b的过程中，先后进行比较的关键字依次是？（A）

A. f,c,b

B. f,d,b

C. g,c,d

D. g,d,b 

1
2
3
4
5
6
7
8
9
【答案解析】：考察二分查找，对于(b,c,d,e,f,g,q,r,s,t)

第一次查找，left = 0, right = 9, mid = 4, 关键字是f, f != b && f > b

第二次查找，left = 0, right = 3, mid = 1, 关键字是c, c != b && c > b

第三次查找，left = 0, right = 0, mid = 0, 关键字是b, b == b 查找到

因此是关键字依次是(f,c,b)

时间复杂度、排序相关

  • 17,在最坏的情况下，下列排序方法中时间复杂度最小的是？（D）

A. 冒泡排序

B. 快速排序

C. 插入排序

D. 堆排序

【答案解析】：常见排序算法最坏时间复杂度比较，其中冒泡排序和插入排序O(n^2)，快速排序最坏情况为O(n^2)，只有堆排序比较稳定复杂度为O(nlogn)。

线性表，二叉平衡树，哈希，高级算法相关

  • 18,下列关于线性表，二叉平衡树，哈希表存储数据的优劣描述错误的是？ （D）

A. 哈希表是一个在时间和空间上做出权衡的经典例子。如果没有内存限制，那么可以直接将键作为数组的索引。那么所有的查找时间复杂度为O(1)；

B. 线性表实现相对比较简单

C. 平衡二叉树的各项操作的时间复杂度为O（logn）

D. 平衡二叉树的插入节点比较快 

1
2
3
【答案解析】：哈希表是一个在时间和空间上做出权衡的经典例子。如果没有内存限制，那么可以直接将键作为数组的索引。那么所有的查找时间复杂度为O(1)；如果没有时间限制，那么我们可以使用无序数组并进行顺序查找，这样只需要很少的内存。 

在平衡二叉树中插入结点要随时保证插入后整棵二叉树是平衡的，所以可能需要通过一次或多次树旋转来重新平衡这个树

动态规划相关

  • 19,下面关于动态规划说法正确的是 （A）

A. 他是利用子结构，进行自底而上的算法设计

B. 他需要后来多次计算的问题进行缓存，减少重复子问题的计算

C. 他所求问题的整体最优解可以通过一系列局部最优的选择

D. 他将分解后的子问题看成相互独立的.

【答案解析】：

  • 动态规划利用最优子结构，自底向上从子问题的最优解逐步构成整个问题的最优解

  • 用空间换时间只是一种技巧，不是动态规划的本质

  • 贪心选择是指所求问题的整体最优解可以通过一系列局部最优的选择,即贪心选择来达到。

  • 与分治法不同的是，适合于用动态规划法求解的问题，经分解得到的子问题往往不是互相独立的，它们可能共享更小的子问题，被称为重叠子问题。

字符串相关

  • 20,字符串 www.qq.com 所有非空子串（两个子串如果内容相同则只算一个）个数是（D）

A. 1024

B. 1018

C. 55

D. 50

【答案解析】：非空子串的个数共有n(n+1)/2个，n=10即55个，由于相同子串算一个，其中w(两次）, ww, q, ., 有重复。故 55 - 5 = 50。

个人感受

  • 基础还是有些薄弱，后期准备再系统学习以下数据结构和算法；
  • 不懂的一定要尽快搞清楚；
  • 多刷题，多总结。
------ 本文结束------
如果本篇文章对你有帮助，可以给作者加个鸡腿~(*^__^*)，感谢鼓励与支持！