备战秋招 | 笔试强化22

目录

一、选择题

二、编程题

三、选择题题解

四、编程题题解

---

一、选择题

1、在有序双向链表中定位删除一个元素的平均时间复杂度为

A. O(1)

B. O(N)

C. O(logN)

D. O(N*logN)

2、在一个以 h 为头指针的单循环链表中，p 指针指向链尾结点的条件是( )

A. p->next==NULL

B. p->next==h

C. p->next->next==h

D. p->data==-1

3、在双向链表中指针p的结点前插入一个指针q的结点操作是()

A. p->Llink=q;q->Rlink=p;p->Llink->Rlink=q;q->Llink=q;

B. p->Llink=q;p->Llink->Rlink=q;q->Rlink=p;q->Llink=p->Llink;

C. q->Rlink=p;q->Llink=p->Llink;p->Llink->Rlink=q;p->Llink=q;

D. q->Llink=p->Llink;q->Rlink=q;p->Llink=q;p->Llink=q;

4、若用数组S[0…n]作为两个栈S1和S2的存储结构，对任何一个栈只有当S全满时才不能做入栈操作。为这两个栈分配空间的最佳方案是

A. S1的栈底位置为0，S2的栈底位置为n

B. S1的栈底位置为0，S2的栈底位置为n/2

C. S1的栈底位置为1，S2的栈底位置为n/2

5、循环队列的存储空间为 Q(1:200) ，初始状态为 front=rear=200 。经过一系列正常的入队与退队操作后， front=rear=1 ，则循环队列中的元素个数为（ ）

A. 0或200

B. 1

C. 2

D. 199

6、将一棵二叉树的根结点放入队列，然后递归的执行如下操作，将出队结点所有子结点加入队。以上操作可以实现哪种遍历（）

A. 前序遍历

B. 中序遍历

C. 后序遍历

D. 层序遍历

7、已知数据元素为(34,76,45,18,26,54,92,65),按照依次插入节点的方法生成一棵二叉排序树，则该树的深度为()

A. 7

B. 6

C. 4

D. 5

8、有 1000 个无序的整数，希望使用最快的方式找出前 50 个最大的，最佳的选择是（ ）

A. 冒泡排序

B. 基数排序

C. 堆排序

D. 快速排序

9、已知一个线性表（38，25，74，63，52，48），假定采用散列函数h（key) = key%7 计算散列地址，并散列存储在散列表A[0....6]中，若采用线性探测方法解决冲突，则 在该散列表上进行等概率成功查找的平均查找长度为（）

A. 1.5

B. 1.7

C. 2.0

D. 2.3

10、下面的排序方法中，关键字比较次数与记录的初始排列无关的是______。

A. 希尔排序

B. 冒泡排序

C. 直接插入排序

D. 直接选择排序

二、编程题

1、小易升级之路    题目链接

2、找出字符串中第一个只出现一次的字符    题目链接

三、选择题题解

1、在有序双向链表中定位删除一个元素的平均时间复杂度为

A. O(1)

B. O(N)

C. O(logN)

D. O(N*logN)

正确答案：B

题解：

         我们要是想在双向链表中删除一个元素，我们就必须知道删除结点的位置，因此需要遍历链表；时间复杂度为O（N）；

2、在一个以 h 为头指针的单循环链表中，p 指针指向链尾结点的条件是( )

A. p->next==NULL

B. p->next==h

C. p->next->next==h

D. p->data==-1

正确答案：B

题解：

         既然是循环链表，首尾必然相连，最后一个结点的下一个结点必然是头节点；故选B；

3、在双向链表中指针p的结点前插入一个指针q的结点操作是()

A. p->Llink=q;q->Rlink=p;p->Llink->Rlink=q;q->Llink=q;

B. p->Llink=q;p->Llink->Rlink=q;q->Rlink=p;q->Llink=p->Llink;

C. q->Rlink=p;q->Llink=p->Llink;p->Llink->Rlink=q;p->Llink=q;

D. q->Llink=p->Llink;q->Rlink=q;p->Llink=q;p->Llink=q;

正确答案：C

题解：

         对于此题，如若不清楚，建议采用画图的方式更加清晰明了；如下图所示；

4、若用数组S[0…n]作为两个栈S1和S2的存储结构，对任何一个栈只有当S全满时才不能做入栈操作。为这两个栈分配空间的最佳方案是

A. S1的栈底位置为0，S2的栈底位置为n

B. S1的栈底位置为0，S2的栈底位置为n/2

C. S1的栈底位置为1，S2的栈底位置为n/2

正确答案：A

题解：

         若想做到任意一个栈满都另一个栈都无法插入，必须使得他们的入栈增长方向不同，若一个向上增长，一个向下增加，此时他们任意一个满了，另一个都无法插入；

5、循环队列的存储空间为 Q(1:200) ，初始状态为 front=rear=200 。经过一系列正常的入队与退队操作后， front=rear=1 ，则循环队列中的元素个数为（ ）

A. 0或200

B. 1

C. 2

D. 199

正确答案：A

题解：

         此题循环队列并没有考虑少用一个空间区分空状态和满状态，因此此题选A；

6、将一棵二叉树的根结点放入队列，然后递归的执行如下操作，将出队结点所有子结点加入队。以上操作可以实现哪种遍历（）

A. 前序遍历

B. 中序遍历

C. 后序遍历

D. 层序遍历

正确答案：D

题解：

         妥妥的层序遍历，若不清楚，建议自己实现一次层序遍历；

7、已知数据元素为(34,76,45,18,26,54,92,65),按照依次插入节点的方法生成一棵二叉排序树，则该树的深度为()

A. 7

B. 6

C. 4

D. 5

正确答案：D

题解：

         注意，此题是二叉排序树，不是平衡二叉排序树，我们依次插入可以得到下图；

8、有 1000 个无序的整数，希望使用最快的方式找出前 50 个最大的，最佳的选择是（ ）

A. 冒泡排序

B. 基数排序

C. 堆排序

D. 快速排序

正确答案：C

题解：

         经典TopK问题，选择堆排序；

9、已知一个线性表（38，25，74，63，52，48），假定采用散列函数h（key) = key%7 计算散列地址，并散列存储在散列表A[0....6]中，若采用线性探测方法解决冲突，则 在该散列表上进行等概率成功查找的平均查找长度为（）

A. 1.5

B. 1.7

C. 2.0

D. 2.3

正确答案：C

题解：

         我们画出散列表分布并计算每个数据查找次数，最后便可求出平均查找次数，如下图所示；

10、下面的排序方法中，关键字比较次数与记录的初始排列无关的是______。

A. 希尔排序

B. 冒泡排序

C. 直接插入排序

D. 直接选择排序

正确答案：D

题解：

         直接插入排序的思想是每次都找出范围内最小值或最大值，然后放入相应位置，与数列中原本顺序无关；

四、编程题题解

1、小易升级之路 

思路：模拟题，若怪兽战力比小易低，我们直接加上该怪兽的战力；若怪兽战力比小易高，我们求出两者的最大公约数，然后加上该公约数；

#include <iostream>
#include <vector>
using namespace std;int get_divi(int a, int b)
{int c = a % b;while(c){a = b;b = c;c = a % b;}return b;
}int main() 
{int n, a;while(cin >> n >> a){vector<int> v(n, 0);for(int i = 0; i < n; i++){cin >> v[i];}for(auto e : v){if(e <= a){a += e;}else {a += get_divi(a, e);}}cout << a << endl;}return 0;
}

2、找出字符串中第一个只出现一次的字符

思路：我们采用计数排序的思想，开一个256大小的整型数组，将字符串中的每一个字符都一 一映射到数组中每一个位置，每次遇到字符串的字符，相应位置++，最后遍历字符串，找出第一个只出现一次的字符；

#include <iostream>
#include <string>
using namespace std;int main() 
{int count[256] = { 0 };string str;cin >> str;for(auto ch : str){count[ch]++;}// 遍历原字符串int i = 0;while(i < str.size()){if(count[str[i]] == 1){cout << str[i] << endl;break;}i++;}if(i == str.size())cout << -1 << endl;return 0;
}