文章目录

• 一. 单选
• • 1. 在有序双向链表中定位删除一个元素的平均时间复杂度为
  • 2. 在一个以 h 为头指针的单循环链表中，p 指针指向链尾结点的条件是( )
  • 3. 在双向链表中指针p的结点前插入一个指针q的结点操作是()
  • 4. 若用数组S[0…n]作为两个栈S1和S2的存储结构，对任何一个栈只有当S全满时才不能做入栈操作。为这两
  • 5. 循环队列的存储空间为 Q(1:200) ，初始状态为 front=rear=200 。经过一系列正常的入队与退队操作后，front=rear=1 ，则循环队列中的元素个数为（ ）
  • 6.将一棵二叉树的根结点放入队列，然后递归的执行如下操作，将出队结点所有子结点加入队。以上操作可以
  • 7. 已知数据元素为(34,76,45,18,26,54,92,65),按照依次插入节点的方法生成一棵二叉排序树，则该树的深度为()
  • 8. 有 1000 个无序的整数，希望使用最快的方式找出前 50 个最大的，最佳的选择是（ ）
  • 9. 已知一个线性表（38，25，74，63，52，48），假定采用散列函数h（key) = key%7 计算散列地址，并散列存储在散列表A[0....6]中，若采用线性探测方法解决冲突，则在该散列表上进行等概率成功查找的平均查找长度为（）
  • 10. 下面的排序方法中，关键字比较次数与记录的初始排列无关的是______。
• 二. 编程
• • 1.小易的升级之路
  • 2. 找出字符串中第一个只出现一次的字符

一. 单选

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

A O(1)
B O(N)
C O(logN)
D O(N*logN)

正确答案：B

有序——二分查找——对数间
链表不能使用二分查找。线性间

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

A p->nextNULL
B p->nexth
C p->next->nexth
D p->data-1

正确答案：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

Llink前驱
Rlink后继

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

初始状态是为空状态。
不知道满了还是空，解决这种情况，循环队列会少用一个空间

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

排序都能找出。
除了堆排序都需要严格排序——需要数有序才能排序
堆排序借用堆结构——内部调整——弱排序
冒泡排序O(N^2)
基数排序O(d(n+radix))趟数+基数
堆排序O(NlongN)——数组——topK问题最值
快速排序O(NlongN)——递归（空间需求更多）
 

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.小易的升级之路

链接

小易经常沉迷于网络游戏.有一次,他在玩一个打怪升级的游戏,他的角色的初始能力值为 a.在接下来的一段时间内,他将会依次遇见n个怪物,每个怪物的防御力为b1,b2,b3…bn. 如果遇到的怪物防御力bi小于等于小易的当前能力值c,那么他就能轻松打败怪物,并 且使得自己的能力值增加bi;如果bi大于c,那他也能打败怪物,但他的能力值只能增加bi 与c的最大公约数.那么问题来了,在一系列的锻炼后,小易的最终能力值为多少?

输入描述：
对于每组数据,第一行是两个整数n(1≤n<100000)表示怪物的数量和a表示小易的初始能力值.
然后输入n行，每行整数,b1,b2…bn(1≤bi≤n)表示每个怪物的防御力
输出描述：
对于每组数据,输出一行.每行仅包含一个整数,表示小易的最终能力值

示例1:
输入
3 50
50 105 200
5 20
30 20 15 40 100
输出
110
205

正确答案：

#include 
#include 
using namespace std;//辗转相除法——求公约数
int GCD(int a,int b)
{int c;while(c = a % b){a = b;b = c;}return b;
}
int Get(int n,int power)
{vector num(n);for(int i = 0;icin>>num[i];}for(int i = 0;iif(power>=num[i])power += num[i];elsepower += GCD(power,num[i]);}return power;}int main() {int n,a,power;while(cin>>n>>a){power = Get(n,a);cout<

#include 
#include 
using namespace std;//暴力法
char getFirstOneChar_1(const string &str)
{int j;for(int i = 0;ifor(j = 0;jif(j==i)//排除自己跟自己比较continue;if(str[j]==str[i])break;}if(j>=str.size())return str[i];}return -1;
}//hash
char getFirstOneChar_2(const string &str)
{int hash[256] = {0};for(int i = 0;iif(hash[str[i]] == 1)return str[i];}return -1;
}//string类函数查找法
char getFirstOneChar_3(const string &str)
{for(int i = 0;iint index1 = str.find(str[i]);int index2 = str.rfind(str[i]);if(index1 == index2)return str[i];}return -1;
}int main() {string str;char res;while(getline(cin,str)){res = getFirstOneChar_3(str);if(res == -1)cout<<-1<