数据结构和算法选择题
一、单选题(每道题2分，满分50分)
第 1 题
1、以下案例中适合用枚举算法的是哪一项（ ）
{{ select(1) }}
- 10位同学需要按照身高由小到大排序。
- 有无穷多个数字，找出里面的质数。
- 有一筐苹果（个数不确定），为所有苹果贴标签。
- 35个人的班级里，找出身高在120cm以上的同学。
第 2 题
2、使用二分算法，在1~500（包含1和500）之间猜数字77，依次取出的中间值是？( ) 中间值=(最小值+最大值)/2。
{{ select(2) }}
- 250, 125, 187, 218, 77
- 251, 125, 63, 94, 77
- 250, 125, 62, 93, 77
- 125, 63, 94, 77
第 3 题
3、观察下方数字序列，第一次二分处理时中间值mid为5，要找的数字为8，L、R的值要如何变化（ ）
{{ select(3) }}
- R=mid+1
- R=mid-1
- L=mid+1
- L=mid-1
第 4 题
4、二分查找算法适用于哪种数据结构？ （ ）
{{ select(4) }}
- 有序数组
- 链表
- 二叉树
- 哈希表
第 5 题
5、二分查找的循环条件通常是什么？（ ）
{{ select(5) }}
- left <= right
- left < right
- left >= right
- left > right
第 6 题
6、有向图每个结点的度等于该结点的（ ）
{{ select(6) }}
- 入度
- 出度
- 入度和出度之和
- 入度和出度之差
第 7 题
7、插入排序的基本思路是？
{{ select(7) }}
- 反复交换相邻元素
- 从无序部分取元素插入到有序部分
- 选择最值元素排列
- 分桶后再合并
第 8 题
8、大整数通常采用哪种方式存储以方便运算？
{{ select(8) }}
- 单个整数变量直接存储
- 字符串或数组，每位存储一个数字
- 浮点数存储
- 二进制文件加密存储
第 9 题
9、对于递推关系 a(n)=2*a(n−1)+1，初始条件 a(1)=1，则 a(3)的值为？
{{ select(9) }}
- 7
- 15
- 3
- 5
第 10 题
10、斐波那契数列从第 3 项开始，每一项等于前两项之和，其递推公式中，F (5) 的值为（ ）（已知 F (1)=1，F (2)=1）
{{ select(10) }}
- 3
- 5
- 8
- 13
第 11 题
11、有一个递推关系 f (n) = f (n-1) + n，f (1)=1，则 f (4) 的值是（ ）
{{ select(11) }}
- 10
- 11
- 12
- 13
第 12 题
12、计算 1+2+3+…+n，其递推公式可以表示为 （ ）
{{ select(12) }}
- S (n) = S (n-1) + n
- S (n) = S (n-1) × n
- S (n) = S (n-1) - n
- S (n) = S (n-1) ÷ n
第 13 题
13、使用链表存储数据，内存中可用存储单元地址（ ）
{{ select(13) }}
- 必须连续
- 部分地址必须连续
- 一定不连续
- 连续不连续均可
第 14 题
14、单链表的结点有几部分组成（ ）
{{ select(14) }}
- 两部分，一部分存储结点值，另一部分存放指针
- 只有一部分，存放结点值
- 只有一部分，存放指针
- 两部分，一部分存放结点值，另一部分存放结点所占内存
第 15 题
15、在链表中，若p所指向的结点不是最后结点，在p之后插入s所指结点，则执行（ ）
{{ select(15) }}
- p->next=s; s->next=p;
- s->next=p->next; p->next=s;
- s->next=p->next; p=s;
- s->next=p; p->next=s;
第 16 题
16、在一个链表中，结点只有指向后继的指针，若删除p所指结点的后继结点，则执行（ ）
{{ select(16) }}
- p->next=p->next->next;
- p=p->next; p->next=p->next->next;
- p->next=p->next;
- p=p->next->next;
第 17 题
17、有一空栈S，入栈序列为a、b、c、d、e、f，依次进行：入栈、入栈、出栈、入栈、入栈、出栈的操作，完成操作后栈底的元素是 ( ）
{{ select(17) }}
- b
- a
- d
- c
第 18 题
18、对于入栈序列为a、b、c、d、e、f、g的序列，下列（ ）不是合法的出栈序列。
{{ select(18) }}
- a、b、c、d、e、f、g
- a、d、c、b、e、g、f
- a、d、b、c、g、f、e
- g、f、e、d、c、b、a
第 19 题
19、已知队列（13,2,11,34,41,77,5,7,18,26,15,），第一个进入队列的元素是13，则第五个出队的元素是（ ）
{{ select(19) }}
- 5
- 41
- 77
- 13
第 20 题
20、设循环队列的数组长度为n，其头尾指针分别为f和r，则其元素个数为（ ）
{{ select(20) }}
- r-f
- r-f+1
- (r-f)%n+1
- (r-f+n)%n
第 21 题
21、对表达式a+(b-c)*d的前缀表达式为( ),其中+、-、*是运算符。
{{ select(21) }}
- *+a-bcd
- +a*-bcd
- abc-d*+
- abc-+d
第 22 题
22、一棵具有5层的满二叉树的结点个数为( )
{{ select(22) }}
- 31
- 32
- 33
- 16
第 23 题
23、根结点的高度为1，具有61个结点的完全二叉树的高度为（ ）
{{ select(23) }}
- 7
- 8
- 5
- 6
第 24 题
24、一棵二叉树的后序序列为DGJHEBIFCA，中序序列为DBGEHJACIF，则其先序序列为（ ）
{{ select(24) }}
- ABCDEFGHIJ
- ABDEGHJCFI
- ABDEGJHCFI
- ABDEGHJFIC
第 25 题
25、一棵二叉树的层次序列为ABECDFG，中序序列为CBDAFEG，则其后序序列为（ ）
{{ select(25) }}
- ABCDEFG
- CBDFGEA
- CBDFEGA
- CDBFGEA
二、程序代码填空题（每空2分，共30分）
1、上船问题
【题目描述】 有 n 个人，需要过河，第 i 个人的体重为wi，河边有很多船，每艘船的最大载重为m且最多可以上两个人，问最少需要多少艘船。 【输入描述】 第一行输入两个整数 n 和 m，表示人数和船的载重。 第二行 n 个整数，用空格隔开，表示体重。 【输出描述】 一个整数，表示需要的最少船只。 【样例输入】 6 120 15 17 102 70 90 68 【样例输出】 4 【数据范围与提示】 1≤n,m≤200，1≤wi≤100，wi≤m
#include<bits/stdc++.h>
using namespace std;
int main(){
int n,m,a[201];
cin>>n>>m;//变量n存储人数，m船载重
for(int i=0;i<n;i++) cin>>a[i];//定义数组存储每个人的体重并输入
sort(a,a+n);//对体重进行从小到大的排序
int i=0,j=___① ___,ans=0;
while(i<=j) {//使用循环获取最少用船数量。
if(i___②___j){
ans++;break;
}
if(a[i]+a[j]___③ __m){
i___④___;
}
j___⑤___;
ans++;
}
cout<<ans;
return 0;
}
填写说明：以下填写内容中不要加空格
第 26 题 ①处应该填写{{ input(26) }}
第 27 题 ②处应该填写{{ input(27) }}
第 28 题 ③处应该填写{{ input(28) }}
第 29 题 ④处应该填写{{ input(29) }}
第 30 题 ⑤处应该填写{{ input(30) }}
2、快速排序
快速排序比普通排序算法速度快，每次快排都可以把序列分成两部分，一部分小于基准值，一部分大于基准值。
快速排序操作流程 1、取基准值，做左右标记 2、移动元素。（升序） j元素与基准值比较，小了往i上面放（往左放） i元素与基准值比较，大了往j上面放（往右放） 3、固定基准值 基准值被固定好时就完成了一次快速排序。
有数字序列：4、1、6、3、2、5，现在对序列做升序排列。这里选择用快速排序来实现。 以上就是快速排序在完成一次次排序时体现的层级关系。 递归思想：快速排序可用递归处理。
#include<iostream>
using namespace std;
int a[101];
void qsort(int left,int right){
if(left>=right) return ;
int x=a[__①__],i=left,j=right;
while(i<j){
while(__②__&&a[j]>=x) j--;
a[i]=a[__③__];
while(i<j&&a[i]<=x) __④__;
a[j]=a[i];
}
a[i]=__⑤__;
qsort(left,i-1);
qsort(i+1,right);
}
int main(){
for(int i=1;i<=6;i++) cin>>a[i];
qsort(1,6);
for(int i=1;i<=6;i++) cout<<a[i]<<" ";
return 0;
}
填写说明：以下填写内容中不要加空格
第 31 题 ①处应该填写{{ input(31) }}
第 32 题 ②处应该填写{{ input(32) }}
第 33 题 ③处应该填写{{ input(33) }}
第 34 题 ④处应该填写{{ input(34) }}
第 35 题 ⑤处应该填写{{ input(35) }}
3、利用先序和中序字符串构建树
【问题描述】
给定一棵二叉树的先序遍历和中序遍历，求其后序遍历。
【输入格式】
读入 2 个两个字符串，每个一行，长度均小于等于 26。
第一行为先序遍历，第二行为中序遍历。
二叉树中的结点名称以大写字母表示： A，B，C... 。
【输出格式】
输出一行，为后序遍历的字符串。
【输入样例】
ABCDE
BADCE
【输出样例】
BDECA
#include<bits/stdc++.h>
using namespace std;
struct node{
char data;
int left,right;
}BTree[30];
string pre,mid;//pre先序遍历字符序列，mid中序遍历的字符序列
int p=0;//全局变量，代表接下来向BTree数组里存储数据的位置（下标）
/*getTree函数功能：利用先序和中序构建二叉树，存储二叉树数据到BTree结构体数组里
参数：pre字符串中目标树的先序遍历字符串字符左边界和右边界，中序遍历字符串字符的左边界和右边界
返回值：构建好的这棵树的根结点编号（在BTree里的数组下标）
*/
int getTree(int pl,int pr,int ml,int mr){
if(ml>mr) return -1;//-1代表空树 if(ml>mr)也可以换成if(pl>pr) ---递归结束条件！
int t=p++;//t是本次要存储的位置，p++的意思是下次要往下一个位置存储
BTree[t].data=pre[__①__];//1、把先序序列根结点数据存储在BTree相应位置的data数据域里
int i=__②__;//从中序序列的开头处开始往后进行查找
while(i<=mr&&mid[i]!=pre[pl]) i++;//2、中序序列字符串中查找根结点位置，记录在变量i里
int len=i-ml;//计算左子树中结点个数
BTree[t].left = getTree(pl+1, __③__, ml, __④__);//3、构建左子树，返回值赋值给当前根结点的left域
BTree[t].right = getTree(pl+len+1, pr, __⑤__, mr);//4、构建右子树，返回值赋值给当前根结点的right域
return t;//返回构建好的这棵树的根结点编号（在BTree里的数组下标）
}
void postOrder(int root){//后序遍历
if(root>=0){
postOrder(BTree[root].left);
postOrder(BTree[root].right);
cout<<BTree[root].data;
}
}
int main(){
cin>>pre>>mid;//输入先序遍历字符序列和中序遍历的字符序列 (要求：两个字符串长度相等)
int n=pre.size();//先序遍历字符序列里字符的个数，也就是代表一共有多少个结点
int root=getTree(0,n-1,0,n-1);
postOrder(root);//后序遍历
return 0;
}