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

信息学奥赛：数据结构初步综合测试一、单项选择题（75分，30题每题2. 5分）1、以下不属于线性结构的是（）。A. 栈B. 队列C. 字符串D. 二叉树（正确答案）2、一个栈的入栈序列为ABCDE,那么出栈序列不可能为（）A.EDCBAB.DECBAC.DCEAB （正确答案）D.ABCDE3、以下（：）是栈和队列的共同特点。A. 在C+中可以用数蛆来实现（正确答案）B. 只允许在一端插入和删除元素C. 都是先进后出D. 没有共同点4、设有一个空栈，现有序列1、2、3、4依次进栈，假设依次经过“进栈、进 栈、出栈、进栈、出栈、进栈、出栈、出栈操作后，出栈序列为（）。A.1 2 34B.2 1 34C.4 3 21D.2 3 41 （正确答案）5、设有一栈初始为空。进栈序列为A、B、C、D、E、F,出栈序列为B、D、C、F、E、A,那么该栈的容量至少为（）o输入：1A2b3C4d5E6f7G输出的第一行：（答案：6）输出的第二行：（答案：1A2B3C4D5e6f7g）A. 5B. 4C. 3（正确答案）D. 26、假设a, b, c依次进栈，那么可能得到的不同出栈序列的种数是（）。A. 3B. 4C. 5（正确答案）D. 67、有6个元素6、5、4、3、2、1依次按顺序进栈，（）是不可能得到的出栈序列。A. 5B. 4C. 2D. 3D. 32（正确答案）8、某个车站呈狭长形，宽度只能容下一台车，并且只有一个出入口。某时刻该车站状态为空，从这一时刻开始的出入记录为：“进，出，进，进，进,出，出，进，进，进，出，出。假设车辆入站的顺序为1, 2, 3,出站的顺序为出站的顺序为()OA.B.6（正确答案）C.D.9、设栈S的初始状态为空，元素a, b, c, d, e依次入栈，以下出栈序列不可能出现的有()OA. a b cB. b c aC. a e cC. a e cb d （正确答案）D. d c e b a10、地面上有标号为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. 3C. 2D. 113、定义字符数组ch101和sring类型的字符串st。要输入这样一行字符 “123 abed”，那么以下输入方式中可以正确执行读入并进行存储的是（）。A. cinch;B. cinst;C. get I ine （cin, ch）;D. get I ine （cin, st）;（正确答案）14、设字符串S二“Olympic”，S的非空子串的数目是（）。A. 28（正确答案）B. 29C. 16D. 1715、假设串S=zuoceshiM,其子串的个数是（）。A.36B.37（正确答案）C.38D.3916、假设串S=”xinxixue”，其子串的个数是（）。A.35B.34C.33（正确答案）D.3217、设根结点的深度为1,那么深度为6的满二叉树有（）个分支姑点。A.31 （正确答案）B.32C.63D.6418、有一个深度为3的满二叉树（根结点深度为0）。假设将结点按层次从上到下从左到右从1开始逐一编号，那么6号结点的左儿子是（）号结点。A.B.12（正确答案）C.13D.不存在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-122、二叉树的先序遍历是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. - + abed25、前缀表达式+ 2 + 3 4 5的值为（）。A. 11B. 17C. 27D. 37（正确答案）26、一个包含n个分支结点（非叶结点）的非空满k叉树，k=1,它的叶结点数 目为（）OA. nk+1B. nk-1C. （k+1）n-1D. （k-1）n+1 （正确答案）27、n个顶点的有向图，假设该图是强连通的（从所有顶点都存在路径到达 其他顶点），那么该图中最少有（）条有向边。A. n （正确答案）B. n+1C. n-1D. n（n-1）28、以下能够一笔写出的汉字有（）个。 日甲 田中A. 0B. 1C. 2（正确答案）D. 329、一个具有n个顶点的有向图G,最多有（）条弧。A. n （n1）/2B. n（n+1）C. 2nD. n（n-1）（正确答案）30、图G是一个有4个顶点的无向完全图，假设要使它不再是连通图，至少要删 去其中的（）条边。A. 1B. 2C. 3（正确答案）D. 4二、填空题（3题，共15分，遍历每空3分，后三空每空2分）1、写出以下二叉树的三序遍历（先中后序遍历）。（1）先序遍历（答案：ABDECF）（2）中序遍历（答案：DBEACF）（3）后序遍历（答案：DEBFCA）2、二叉树T有2021个结点，假设令其根结点深度为0,那么二叉树T的深度最多为, 最少为O空1答案：2020空2答案：103、有4个叶子结点的完全二叉树最多有个结点。（答案：8）三、阅读程序写结果（共10分，每空5分）#include #include using namespace std;int main()(string s;int i,j,k,ans=0;cins;for(i=0;i=*a, & si=*z,) | si=si-,a,+A,;for(j=i+l;j=A, & sj=*Z,) I sj=sj-,A,+a,;for(k=l;k=l01 & sk=,91) ans+;:icoutansendl; couts;return 0;1234甲567891011121314151617181920-