计算机专业(基础综合)模拟试卷110(题后含答案及解析).docVIP

计算机专业（基础综合）模拟试卷110(题后含答案及解析)

题型有：1.单项选择题2.综合应用题

单项选择题1-40小题，每小题2分，共80分。下列每题给出的四个选项中，只有一个选项是最符合题目要求的。

1．假设栈的容量为3，入栈的序列为1,2,3,4,5，则出栈的序列可能为()。

A．3,2,1,5,4

B．1,5,4,3,2

C．5,4,3,2,1

D．4,3,2,1,5

正确答案：A

解析：考查出入栈序列和栈深的关系。由于栈的容量只有3，故第一个出栈元素不可能是5或4，先排除C和D。接下来分析B，1入栈后出栈，然后2、3、4、5依次入栈，5出栈，才能得到序列B，但实现这种出栈序列，栈的容量至少为4，故仅有A满足。

2．当字符序列t3作为栈的输入时，则输出长度为3、且可用作C语言标识符的序列有()个。

A．4

B．5

C．3

D．6

正确答案：C

解析：考查栈的操作。标识符只能以字母或下划线开头，即由t、3、_能够组成的合法标识符只有：t3_、t_3、_3t、_t3，而当用t3_作为栈的输入时，_t3无法作为输出序列，所以输出的合法标识符有t3_；t_3；_3t，因此选C。

3．在下列遍历算法中，在遍历序列中叶结点之间的次序可能与其他算法不同的算法是()。

A．先序遍历算法

B．中序遍历算法

C．后序遍历算法

D．层次遍历算法

正确答案：D

解析：考查各种遍历算法的特点。先序、中序和后序遍历算法访问叶结点的顺序都一样，而层序遍历算法在二叉树的叶结点不在同一层上时，可能先遍历后面的叶结点。因此选D。

4．有关二叉树下列说法正确的是()。

A．二叉树的度为2

B．一棵二叉树的度可以小于2

C．二叉树中至少有一个结点的度为2

D．二叉树就是度为2的有序树

正确答案：B

解析：考查二叉树的定义和性质。二叉树的度至多为2，也可以小于2，所以A、C错误，B正确。当二叉树只有一个结点时，度为0。在度为2有序树中：①至少有一个结点的度为2；②孩子结点的左、右顺序是相对于其兄弟结点而言的，如果仅有一个孩子结点就无所谓左、右孩子了。而二叉树的左、右顺序是相对于根结点的，即使只有一个孩子结点也要指明是左孩子还是右孩子。由①②可知，D错误。

5．利用逐点插入建立序列(50,72,43,85,75,20,35,45,65,30)对应的二叉排序树后，要查找元素30要进行的元素间的比较次数是()。

A．4

B．5

C．6

D．7

正确答案：B

解析：考查二叉排序树的构造和查找。按题中数据的输入次序，建立的二叉排序树如右图所示。查找元素30需要依次比较的元素为50，43，20，35，30，比较次数为5次。

6．由4棵树组成的森林中，第一、第二、第三和第四棵树中的结点数分别为30、10、20、5，当把森林转换成二叉树后，对应二叉树中根结点的右子树的左子树的结点数为()。

A．29

B．9

C．25

D．19

正确答案：B

解析：考查森林与二叉树的转换。将这四棵树转换为二叉树后，第一棵树的根结点变成二叉树的根结点，第二棵树的根结点变成了根结点的右孩子，第二棵树中剩下的结点变成了其根结点的左子树。

7．无向图G有23条边，度为4的顶点有5个，度为3的顶点有4个，其余都是度为2的顶点，则图G最多有()个顶点。

A．11

B．12

C．15

D．16

正确答案：D

解析：考查图的性质。在无向图中，一条边连接两个顶点，故所有顶点的度之和等于边数的2倍。由于在具有n个顶点e条边的无向图中，有，故可求得度为2的顶点数为7个，从而最多有16个顶点(不排除多条边共享一对顶点，即多重边)。

8．假设有n个顶点e条边的有向图用邻接表表示，则删除与某个顶点v相关的所有边的时间复杂度为()。

A．0(n)

B．0(e)

C．0(n+e)

D．0(ne)

正确答案：C

解析：考查邻接表的性质。和顶点v相关的边包括出边和入边，对于出边，只需要遍历v的顶点表即可；对于入边，则需要遍历整个邻接表。删除与某顶点v相关的所有边过程如下：先删除下标为v的顶点表结点的单链表，出边数最多为，n一1，对应时间复杂度为O(n)，再扫描所有边表结点，删除所有的入边，对应时间复杂度为O(e)。故总的时间复杂度为O(n+e)。

9．折半查找有序表(2,10,25,35,40,65,70,75,81,82,88,100)，若查找元素75，需依次与表中元素()进行比较。

A．65,82,75

B．70,82,75

C．65,81,75

D．65,81,70,75

正确答案：D

解析：考查折半查找的查找过程。有序表长12，依据折半查找的思想，第一次查找第「(1+12)／2」=6个元素