文章目录

  • C/C++笔试练习
  • 选择部分
    • （1）双向循环链表
    • （2）循环链表特点
    • （3）双向链表插入
    • （4）栈的特点
    • （5）循环队列元素
    • （6）层序遍历
    • （7）二叉排序树的高
    • （8）堆排序
    • （9）散列表的查找长度
    • （10）选择排序
  • 编程题 day22
    • 小易的升级之路
    • 找出字符串中第一个只出现一次的字符

C/C++笔试练习

选择部分

（1）双向循环链表

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

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

  答案：B

  在有序双向链表中，我们不能像在有序数组中那样使用二分查找来快速定位元素。在链表中，我们必须从头开始遍历链表，直到找到要删除的元素或到达链表的末尾。这个过程的时间复杂度是 O(N)，其中 N 是链表的长度。

  删除一个元素的过程也是 O(1) 时间复杂度，因为它仅仅涉及更改一些链接，不涉及数据复制或移动。但由于定位元素的时间复杂度是 O(N)，因此总的时间复杂度是 O(N)。

  

（2）循环链表特点

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

  A. p->next== NULL
 B. p->next== h
 C. p->next->next== h
 D. p->data== -1

  答案：B

  p->next == p;这个条件检查 p 是否指向链表的尾部。在单循环链表中，尾节点的 next 指针指向头结点，即 h。因此，这个条件是正确的。

  

（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

  我们需要明确双向链表中插入一个节点的基本步骤：将新节点q的右链接指向p节点，将新节点q的左链接指向p节点的左链接，更新p节点的左链接的右链接指向新节点q，将p节点的左链接指向新节点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

  答案：A

  当S1的栈底位置为0，S2的栈底位置为n时，两个栈可以有最大的分配空间。

  

（5）循环队列元素

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

  A. 0或200
 B. 1
 C. 2
 D. 199

  答案：A

  在循环队列中，front 和 rear 分别表示队头和队尾的指针。初始状态为front=rear=200，表示队列为空。当 front 和 rear 相等时，队列可能为空（front 和 rear 指向同一个位置）或队列可能为满（front 和 rear 指向同一个位置，但队列中有一个元素）。

  通常我们为了避免这种情况，所以我们会浪费循环队列中的一个元素，以用来区分队列为空和队列为满的情况。

  

（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)，但它需要额外的空间来执行。由于我们只有1000个整数，而且要求前50个最大的数，基数排序可能不是最高效的方法。

  堆排序：这是一个非常高效的排序算法，其时间复杂度为O(nlogn)。它特别适合找出数组中的最大或最小元素。通过构建一个最大堆，我们可以快速找到前50个最大的整数。

  快速排序：这是一个常用的排序算法，其平均时间复杂度为O(nlogn)。但在最坏的情况下，其时间复杂度为O(n^2)。因此，对于这个特定的问题，快速排序可能不是最佳选择。

  

（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

  希尔排序：这是一种基于插入排序的算法，通过比较相隔一定间隔的元素来工作。关键字比较次数与记录的初始排列有关，因为间隔序列的选择会影响比较和交换的次数。

  冒泡排序：这是一种简单的排序算法，通过重复地遍历待排序的记录序列，比较相邻的两个记录，并根据需要交换它们的位置。关键字比较次数与记录的初始排列有关，因为需要多次遍历才能将最大（或最小）的元素移到正确的位置。

  直接插入排序：这是一种简单的排序算法，通过将每个记录逐个插入到已排序的子序列中来工作。关键字比较次数与记录的初始排列有关，因为插入位置和比较次数会受到初始排列的影响。

  直接选择排序：这是一种简单的排序算法，通过重复地遍历待排序的记录序列，找到最小（或最大）的元素，并将其放在已排序序列的末尾。 关键字比较次数与记录的初始排列无关，因为无论初始排列如何，我们都只需要进行n次比较和交换操作（n为记录数）。

            

编程题 day22

小易的升级之路

小易的升级之路

  解题思路：本题的能力值的累加分两种情况，一种是直接相加bi,一种是累加当前能力值于bi的最大公约数。最大公约数可以通过碾转相除法求得：a与b的最大公约数相当于b与a,b余数的最大公约数。如果求余结果为0， 则b为所求结果。

#include#includeusing namespace std;//辗转相除法int GCD(int a, int b) {int c;while (c = a % b) {a = b;b = c;}return b;}int getPowerValue(int n, int power) {vector<int> num(n);for (int i = 0; i < n; ++i) //输入敌人的防御值cin >> num[i];for (int i = 0; i < n; ++i) {if (power >= num[i])power += num[i];elsepower += GCD(power, num[i]);}return power;}int main() {int n, a, power;while (cin >> n >> a) {power = getPowerValue(n, a);cout << power << endl;}return 0;}

  

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

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

  解题思路：用一个数组的每一个位置表示对应的位置。对应的字符位置存放字符出现的次数。统计完之后，遍历输入字符，遇到第一个只出现一次的字符就停止。

#include#includeusing namespace std;//暴力法 O(n^2)char getFirstOneChar_1(const string& str) {int j;for (int i = 0; i < str.size(); ++i) {for (j = 0; j < str.size(); ++j) {if (j == i) //排除自己跟自己比较continue;if (str[j] == str[i])break;}if (j >= str.size())return str[i];}return -1;}//hash法 O(n)char getFirstOneChar_2(const string& str) {int hash[256] = {0};for (int i = 0; i < str.size(); ++i) //统计字符的次数hash[str[i]]++;for (int i = 0; i < str.size(); ++i) {if (hash[str[i]] == 1)return str[i];}return -1;}//string类函数查找法char getFirstOneChar_3(const string& str) {for (int i = 0; i < str.size(); ++i) {int 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 << endl;elsecout << res << endl;}return 0;}