信息学奥赛：数据结构初步综合测试.docx

信息学奥赛：数据结构初步综合测试
一、单项选择题（75分，30题每题2. 5分）
1、以下不属于线性结构的是（）。
A. 栈
B. 队列
C. 字符串
D. 二叉树（正确答案）
2、一个栈的入栈序列为ABCDE,那么出栈序列不可能为（）
A.
E
D
C
B
A
B.
D
E
C
B
A
C.
D
C
E
A
B （正确答案）
D.
A
B
C
D
E
3、
以下（
：）
是栈和队列的共同特点。
A. 在C++中可以用数蛆来实现（正确答案）
B. 只允许在一端插入和删除元素
C. 都是先进后出
D. 没有共同点
4、设有一个空栈，现有序列1、2、3、4依次进栈，假设依次经过“进栈、进 栈、出栈、进栈、出栈、进栈、出栈、出栈"操作后，出栈序列为（）。
A.
1 2 3
4
B.
2 1 3
4
C.
4 3 2
1
D.
2 3 4
1 （正确答案）
5、
设有一
•栈初始为空。进栈序列为A、B、C、D、E、F,出栈序列为B、
D、C、F、E、A,那么该栈的容量至少为（）o
输入：1A2b3C4d5E6f7G
输出的第一行：
（答案：6）
输出的第二行：
（答案：1A2B3C4D5e6f7g）
A. 5
B. 4
C. 3（正确答案）
D. 2
6、假设a, b, c依次进栈，那么可能得到的不同出栈序列的种数是（）。
A. 3
B. 4
C. 5（正确答案）
D. 6
7、有6个元素6、5、4、3、2、1依次按顺序进栈，（）是不可能得到的出栈序列。
A. 5
B. 4
C. 2D. 3

D. 3
2（正确答案）

8、某个车站呈狭长形，宽度只能容下一台车，并且只有一个出入口。某时刻该车站状态为空，从这一时刻开始的出入记录为：“进，出，进，进，进,
出，出，进，进，进，出，出"。假设车辆入站的顺序为1, 2, 3,出站的顺序为

出站的顺序为
()O
A.
B.
6（正确答案）

C.
D.
9、
设栈S的初始状态为空，元素a, b, c, d, e依次入栈，以下出栈序列不
可能出现的有
()O

A. a b c
B. b c aC. a e c

C. a e c
b d （正确答案）

D. d c e b a
10、地面上有标号为A、B、C的3根细柱，在A柱上放有10个直径相同中间有孔的圆盘，从上到下依次编号为1, 2, 3,……，将A柱上的局部盘子经过B柱 移入C柱，也可以在B柱上暂存。如果B柱上的操作记录为：“进，进，出，进， 进，出，出，进，进，出，进，出，出"。那么，在C柱上，从下到上的盘子的编 号为（）。
A.
B.
C.
D.
5（正确答案）
11、字符串是特殊的线性表，特殊在（）。
A. 字符串可以用数组进行存储
B. 字符串中的每一个元素都是字符（正确答案）
C. 除了第一个元素以外，字符串中每一个元素都有一个前驱
D. 除了最后一个元素以外，字符串中每一个元素都有一个后继
12、以下关于空串和空格串的说法中，表述正确的说法有（）个。
① 空格串表示只含空格的串。
② 空串表示所含字符数为0的串。
③ 空格串指由空格组成的非空串，其长度为串中空格字符的个数。
④ 空串指长度为零的串。
A. 4（正确答案）
B. 3
C. 2
D. 1
13、定义字符数组ch[101]和sring类型的字符串st。要输入这样一行字符 “123 abed”，那么以下输入方式中可以正确执行读入并进行存储的是（）。
A. cin»ch;
B. cin»st;
C. get I ine （cin, ch）;
D. get I ine （cin, st）;（正确答案）
14、设字符串S二“Olympic”，S的非空子串的数目是（）。
A. 28（正确答案）
B. 29
C. 16
D. 17
15、假设串S="zuoceshiM,其子串的个数是（）。
A.
36
B.
37（正确答案）
C.
38
D.
39

16、假设串S=”xinxixue”，其子串的个数是（）。
A.
35
B.
34
C.
33（正确答案）
D.
32

17、设根结点的深度为1,那么深度为6的满二叉树有（）个分支姑点。
A.
31 （正确答案）
B.
32
C.
63
D.
64

18、有一个深度为3的满二叉树（根结点深度为0）。假设将结点按层次从上到下从左到右从1开始逐一编号，那么6号结点的左儿子是（）号结点。
A.
B.
12（正确答案）
C.
13

D.不存在
19、6个结点的二叉树的先根遍历是1 2 3 4 5 6（数字为结点的编号,以下同），
后根遍历是3 2 5 6 4 1,那么该二叉树的可能的中根遍历是（）。
A.
B.
6（正确答案）C.
D.
20、7个节点的二叉树的先根遍历是1 2 4 5 6 3 7（数字为节点的编号，以下同），
中根遍历是4 2 6 5 1 7 3,那么该二叉树的后根遍历是（）。
A.
1 （正确答案）B.
C.
D.
21、完全二叉树共有2N-1个结点，那么它的叶结点数是（）。
A. N-1N （正确答案）
B. 2N2N-1
22、二叉树的先序遍历是1 2 4 3 5 7 6（数字为结点的编号，以下同），中序遍历是2 4 1 5 7 3 6,那么该二叉树的后根遍历是（）。
A.
B.
1 （正确答案）C.
D.
23、设T是一棵有n个顶点的树，以下说法不正确的选项是（）。
A. T有n条边（正确答案）T是连通的
B. T是无环的T有n-1条边

24、表达式a（b+c）-d的后缀表达式是（）。
A. abed + -
B. a b c + d -（正确答案）
C. a b c + d -
D. - + abed
25、前缀表达式+ 2 + 3 4 5的值为（）。
A. 11
B. 17
C. 27
D. 37（正确答案）
26、一个包含n个分支结点（非叶结点）的非空满k叉树，k>=1,它的叶结点数 目为（）O
A. nk+1
B. nk-1
C. （k+1）n-1
D. （k-1）n+1 （正确答案）
27、n个顶点的有向图，假设该图是强连通的（从所有顶点都存在路径到达 其他顶点），那么该图中最少有（）条有向边。
A. n （正确答案）
B. n+1
C. n-1
D. n（n-1）
28、以下能够一笔写出的汉字有（）个。
① 日甲
② 田中
A. 0
B. 1
C. 2（正确答案）
D. 3
29、一个具有n个顶点的有向图G,最多有（）条弧。
A. n （n~1）/2
B. n（n+1）
C. 2n
D. n（n-1）（正确答案）
30、图G是一个有4个顶点的无向完全图，假设要使它不再是连通图，至少要删 去其中的（）条边。
A. 1
B. 2
C. 3（正确答案）
D. 4
二、填空题（3题，共15分，遍历每空3分，后三空每空2分）
1、写出以下二叉树的三序遍历（先中后序遍历）。

（1）先序遍历（答案：ABDECF）
（2）中序遍历（答案：DBEACF）
（3）后序遍历（答案：DEBFCA）
2、二叉树T有2021个结点，假设令其根结点深度为0,那么二叉树T的深度最多
为, 最少为O
空1答案：2020
空2答案：10
3、有4个叶子结点的完全二叉树最多有个结点。
（答案：8）三、阅读程序写结果（共10分，每空5分）
#include <iostream>#include <string>
using namespace std;int main()(
string s;
int i,j,k,ans=0;
cin>>s;
for(i=0;i<=s.length()/2;i++) I if(s[i]>=*a, && s[i]<=*z,) | s[i]=s[i]-,a,+'A,;
for(j=i+l;j<s.length();j++)| if(s[j]>='A, && s[j]<=*Z,) I s[j]=s[j]-,A,+'a,;
for(k=l;k<s•length();k++)| if(s[k]>=l01 && s[k]<=,91) ans++;
:i
cout<<ans<<endl; cout<<s;
return 0;
1
2
3
4甲
5
6
7
8
910
1112
1314
1516
1718
1920-
}