2021年程序员模拟题3

试卷预览

1 单选题 1分

37支篮球队举行淘汰赛争夺冠军，每场球赛的胜者(无平局)或轮空者进入下一轮赛，共需进行( )比赛。

查看答案 开始考试

正确答案：D

本题解析：

本题考查应用数学基础知识。

淘汰赛没有平局，每场比赛淘汰 1 个队。总共 37 个队，需要掏汰 36 个队才能赛出

冠军，因此共需要比赛 36 场。各轮比赛的情况如下:

第 1 轮:共 37 队，比赛 18 场，轮空 1 队，赛后留下 19 队；

第 2 轮：共 19 队，比赛 9 场，轮空 1 队，赛后留下 10 队；

第 3 轮:共 10 队，比赛 5 场，赛后留下 5 队；

第 4 轮:共 5 队，比赛 2 场，轮空 1 队，赛后留下 3 队；

第 5 轮:共 3 队，比赛 l 场，轮空 1 队，赛后留下 2 队；

第 6 轮:共 2 队，比赛 1 场，赛后留下 1 个冠军队。

2 单选题 1分

已知字符串s='(X+Y)+Z'，其中，单引号不是字符串的内容，经过以下运算后，t3的值是( )。

t1=SubString(s,3,1)

t2=Concat('XY',t 1)

t3=Replace(s,SubString(s,1,5),t2)

注：SubString(s,k,n)表示从串s的第k个字符开始取出长度为n的子串，Concat(s,t)表示将串t连接在s之后，Replace(s,t,r)表示用r替换串s中的子串t。

查看答案 开始考试

正确答案：D

本题解析：

本题考查数据结构基础知识。

t1=SubString(s,3,1)=SubString('(X+Y)*Z',3,1)='+'

t2=Concat('XY',t1)=Concat('XY','+')='xY+'

t3=Replace(s,SubString(s,1,5),t2)=Replace('(X+Y)*Z','(X+Y)','xY+')='XY+*Z'

3 单选题 1分

含有n个元素的线性表采用顺序存储，等概率删除其中任一个元素，平均需要移动( )个元素。

查看答案 开始考试

正确答案：C

本题解析：

本题考查数据结构基础知识。

在表长为 n 的线性表中删除一个元素时，共有 n个可删除的元素。删除 a1时需要移 动n-1 个元素，删除 an 时不需要移动元素，因此，等概率下删除一个元素时平均的移动 元素个数 Edelete 为

其中 ，qi 表示删除第 i个元素 (aj) 的概率。

4 单选题 1分

若元素a、b、c、d、e、f依次进栈，允许进栈、出栈操作交替进行。但不允许连续三次进行出栈工作，则不可能得到的出栈序列是( )。

查看答案 开始考试

正确答案：D

本题解析：

本题考查数据结构基础知识。

对于选项A的出栈序列dcebfa，其操作序列为：push(a入)、push(b入)、push(c入)、push(d入)、pop(d出)、pop(c出)、push(e入)、pop(e出)、pop(b出)、push(f入)、pop(f出)、pop(a出)。

对于选项B的出栈序列cbdaef，其操作序列为：push(a入)、push(b入)、push(c入)、pop(c出)、pop(b出)、push(d入)、pop(d出)、pop(a出)、push(e入)、pop(e出)、push(f入)、pop(f出)。

对于选项C的出栈序列bcaefd，其操作序列为：push(a入)、push(b入)、pop(b出)、push(c入)、pop(c出)、pop(a出)、push(d入)、push(e入)、pop(e出)、push(f入)、pop(f出)、pop(d出)。

对于选项D的出栈序列afedcb，其操作序列为：push(a入)、pop(a出)、push(b入)、push(c入)、push(d入)、push(e入)、push(f入)、pop(f出)、pop(e出)、pop(d出)、pop(c出)、pop(b出)，存在连续5次的出栈操作，违背题中所述的运算要求。

5 单选题 1分

设有关键码序列(10，40，30，20)，根据该序列构建的二叉排序树是( )。

查看答案 开始考试

正确答案：C

本题解析：

本题考查数据结构基础知识。

二叉排序树又称为二叉查找树，它或者是一棵空树，或者是具有如下性质的二叉树: 若它的左子树非空，则左子树上所有结点的值均小于根结点的值:若它的右子树非空， 则右子树上所有结点的值均大于根结点的值:左、右子树本身就是二叉排序树 。

二叉查找树是通过依次输入数据元素并把它们插入到二叉树的适当位置上构造起 来的，具体的过程是:每读入 一个元素，建立一个新结点，若二叉查找树非空，则将新 结点的值与根结点的值相比较，如 果小于根结点的值， 则插入到左子树中，否则插入到 右子树中:若二叉查找树为空，则新结点作为二叉查找树的根结点 。

选项 A 所示的二叉树结点 30 与其右孩子的关系不满足二叉排序树的定义 。

选项 B 满足二叉排序树的定义，但与输入序列不符。根据输入序列，根结点应为 10。

选项 C 是正确的。

选项 D 不是二叉排序树 ，以10 为例， 显然 10 小于 20，它应该在20 的左子树上。

6 单选题 1分

某有向图G及其邻接矩阵如下所示。以下关于图的邻接矩阵存储的叙述中，错误的是( )。

查看答案 开始考试

正确答案：C

本题解析：

本题考查数据结构基础知识。

图中顶点 v 的度是指关联于该顶点的边的数目，若为有向图，顶点的度表示该顶点 的入度和出度之和。

图的邻接矩阵表示法利用一个矩阵来表示图中顶点之间的关系。矩阵元素的值设置 如下:

对于题中所给的图，各顶点的度如下表所示：

显然，邻接矩阵中每一行的非零元素个数对应一个顶点的出度，每一列的非零元素个数对应一个顶点的入度。

7 单选题 1分

若待排序记录按关键字基本有序，则宜采用的排序方法是( )。

查看答案 开始考试

正确答案：A

本题解析：

本题考查数据结构基础知识。

根据直接插入排序、堆排序、快速排序和简单选择排序各种方法的排序过程可知，在关键码序列基本有序的情况下，直接插入排序法最为适宜。

8 单选题 1分

( )不符合二叉排序树的定义。

查看答案 开始考试

正确答案：A

本题解析：

本题考查数据结构基础知识。

二叉排序树又称为二叉查找树，它或者是一棵空树，或者是具有如下性质的二叉树:

①若它的左子树非空，则左子树上所有结点的值均小于根结点的值 。

②若它的右子树非空，则右子树上所有结 点的值均大于根结点的值 。

③左、右子树本身就是两棵二叉排序树。

对于选项 A 所示的二叉树，以 30 为根的子树不符合二叉排序树的定义 。

9 单选题 1分

设数组A[1..m,1..n]的每个元素占用1个存储单元，对于数组元素A[i,j](1≤i≤m，1≤j≤n)，在按行存储方式下，其相对于数组空间首地址的偏移量为(请作答此空)；在按列存储方式下，其相对于数组空间首地址的偏移量为( )。

查看答案 开始考试

正确答案：B

本题解析：

本题考查数据结构基础知识。数组A[1..m,1..n]的元素排列如下。

解答该问题需先计算排列在a[i,j]之前的元素个数。

按行方式存储下，元素a[i,j]之前有i-1行，每行n个元素，在第i行上a[i,j]之前有j-1个元素，因此，a[i,j]之前共有(i-1)*n+j-1个元素。

在按列存储方式下，元素a[i,j]之前有i-1列，每列m个元素，在a[i,j]所在列(即第j列)，排在它之前的元素有i-1个，因此，a[i,j]之前共有(i-1)*m+i-1个元素。

数组中指定元素的存储位置相对于数组空间首地址的偏移量等于k*d，其中k为排在该元素前的元素个数，d为每个元素占用的存储单元数。

10 单选题 1分

以下关于字符串的叙述中，正确的是( )。

查看答案 开始考试

正确答案：A

本题解析：

本题考查数据结构基础知识。

选项 A 是正确的。一个线性表是 n 个元素的有限序列(n≥0)。由于字符串是由字符 构成的序列，因此符合线性表的定义。

选项 B 是错误的。长度为 0 字符串称为空串(即不包含字符的串)，而空白串是指

由空白符号(空格、制表符等)构成的串，其长度不为0。

选项 C 是错误的。串的模式匹配算法是指在串中查找指定的模式串是否出现及其位置。

选项 D 是错误的。两个字符串比较时，按照、对应字符(编码)的大小关系进行比较。