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

信息学奥赛：数据结构初步综合测试一、单选题（75分，30题每题2.5分）1、下列不属于线性结构的是（）。 A. 栈B. 队列C. 字符串D. 二叉树(正确答案)2、一个栈的入栈序列为ABCDE，则出栈序列不可能为（） A. E D C B AB. D E C B AC. D C E A B(正确答案)D. A B C D E3、以下（）是栈和队列的共同特点。 A. 在C+中可以用数组来实现(正确答案)B. 只允许在一端插入和删除元素C. 都是先进后出D. 没有共同点4、设有一个空栈，现有序列1、2、3、4依次进栈，若依次经过“进栈、进栈、出栈、进栈、出栈、进栈、出栈、出栈”操作后，出栈序列为( )。 A. 1 2 3 4B. 2 1 3 4C. 4 3 2 1D. 2 3 4 1(正确答案)5、设有一栈初始为空。已知进栈序列为A、B、C、D、E、F，出栈序列为B、D、C、F、E、A，则该栈的容量至少为（）。 A. 5B. 4C. 3(正确答案)D. 26、若a，b，c依次进栈，则可能得到的不同出栈序列的种数是（）。 A. 3B. 4C. 5(正确答案)D. 67、有6个元素6、5、4、3、2、1依次按顺序进栈，（）是不可能得到的出栈序列。 A. 5 4 3 6 1 2B. 4 5 3 1 2 6C. 2 3 4 1 5 6D. 3 4 6 5 1 2(正确答案)8、某个车站呈狭长形，宽度只能容下一台车，并且只有一个出入口。已知某时刻该车站状态为空，从这一时刻开始的出入记录为：“进，出，进，进，进，出，出，进，进，进，出，出”。假设车辆入站的顺序为1，2，3，则车辆出站的顺序为（）。 A. 1 2 3 4 5B. 1 4 3 7 6(正确答案)C. 1 4 3 7 2D. 1 4 3 7 59、设栈S的初始状态为空，元素a，b，c，d，e依次入栈，以下出栈序列不可能出现的有（）。 A. a b c e dB. b c a e dC. a e c b d(正确答案)D. d c e b a10、地面上有标号为A、B、C的3根细柱，在A柱上放有10个直径相同中间有孔的圆盘，从上到下依次编号为1，2，3，将A柱上的部分盘子经过B柱移入C柱，也可以在B柱上暂存。如果B柱上的操作记录为：“进，进，出，进，进，出，出，进，进，出，进，出，出”。那么，在C柱上，从下到上的盘子的编号为（）。 A. 2 4 3 6 5 7B. 2 4 1 2 5 7C. 2 4 3 1 7 6D. 2 4 3 6 7 5(正确答案)11、字符串是特殊的线性表，特殊在（）。 A. 字符串可以用数组进行存储B. 字符串中的每一个元素都是字符(正确答案)C. 除了第一个元素以外，字符串中每一个元素都有一个前驱D. 除了最后一个元素以外，字符串中每一个元素都有一个后继12、下列关于空串和空格串的说法中，表述正确的说法有（）个。 空格串表示只含空格的串。 空串表示所含字符数为0的串。 空格串指由空格组成的非空串，其长度为串中空格字符的个数。 空串指长度为零的串。 A. 4(正确答案)B. 3C. 2D. 113、定义字符数组ch101和sring类型的字符串st。要输入这样一行字符“123 abcd”，则下列输入方式中可以正确执行读入并进行存储的是（）。 A. cin>>ch;B. cin>>st;C. getline(cin,ch);D. getline(cin,st);(正确答案)14、设字符串S=“Olympic”，S的非空子串的数目是（）。 A. 28(正确答案)B. 29C. 16D. 1715、若串S="zuoceshi"，其子串的个数是（）。 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. 3B. 12(正确答案)C. 13D. 不存在19、已知6个结点的二叉树的先根遍历是1 2 3 4 5 6(数字为结点的编号，以下同)，后根遍历是3 2 5 6 4 1，则该二叉树的可能的中根遍历是（）。 A. 3 2 1 4 6 5B. 3 2 1 5 4 6(正确答案)C. 2 1 3 5 4 6D. 2 3 1 4 6 520、已知7个节点的二叉树的先根遍历是1 2 4 5 6 3 7(数字为节点的编号，以下同)，中根遍历是4 2 6 5 1 7 3，则该二叉树的后根遍历是（）。 A. 4 6 5 2 7 3 1(正确答案)B4 6 5 2 1 3 7C4 2 3 1 5 4 7D4 6 5 3 1 7 221、完全二叉树共有2N-1个结点，则它的叶结点数是（）。 A. N-1B. N(正确答案)C. 2ND. 2N-122、二叉树的先序遍历是1 2 4 3 5 7 6(数字为结点的编号，以下同)，中序遍历是2 4 1 5 7 3 6，则该二叉树的后根遍历是（）。 A. 4 2 5 7 6 3 1B. 4 2 7 5 6 3 1(正确答案)C. 7 4 2 5 6 3 1D. 4 2 7 6 5 3 123、设T是一棵有n个顶点的树，下列说法不正确的是（）。 A. T有n条边(正确答案)B. T是连通的C. T是无环的D. T有n-1条边24、表达式a(b+c)-d的后缀表达式是（）。 A a b c d + -B. a b c + d (正确答案)C. a b c + d D. - + a b c d25、前缀表达式 + 2 + 3 4 5的值为（）。 A. 11B. 17C. 27D. 37(正确答案)26、一个包含n个分支结点(非叶结点)的非空满k叉树，k>=1，它的叶结点数目为（）。 A. 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(n-1)/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的深度最多为_，最少为_。 空1答案：2020空2答案：103、有4个叶子结点的完全二叉树最多有_个结点。 _(答案：8)三、阅读程序写结果（共10分，每空5分）输入：1A2b3C4d5E6f7G输出的第一行： _(答案：6)输出的第二行： _(答案：1A2B3C4D5e6f7g)