国家二级MS Office高级应用机试（选择题）模拟试卷337
选择题
1.深度为5的完全二叉树的节点数不可能是( )。(A)
A. 15
B. 16
C. 17
D. 18
解析：设完全二叉树的节点数为n，根据深度为k的二叉树至多有2k－1个节点，再根据完全二叉树的定义可知，2k－1－1＜n≤2k－1。本题中完全二叉树的深度为5，则25－1－1＜n≤25－1，15＜n≤31。因此，节点数不能为15。
2.某二叉树的中序序列为DCBAEFG，后序序列为DCBGFEA，则该二叉树的深度(根结点在第1层)为(B)
A. 5
B. 4
C. 3
D. 2
解析：该二叉树的中序序列为DCBAEFG，后序序列为DCBGFEA，可知A为根结点，结点B、C、D位于根结点的左子树上，结点E、F、G位于根结点的右子树上；并且结点B、C、D在中序序列和后序序列中顺序未变，则说明这三个结点依次位于前一个结点的左子树上；结点E、F、G顺序颠倒，则说明这三个结点依次位于前_个结点的右子树上。根据以上分析，该二叉树的深度为4，所以选项B正确。
3.下列叙述中正确的是(A)
A. 算法的时间复杂度与运行算法时特定的输入有关
B. 算法的时间复杂度与计算机的运行速度有关
C. 算法的时间复杂度与算法程序中的语句条数成正比
D. 算法的时间复杂度与算法程序编制者的水平有关
解析：算法的时间复杂度，是指执行算法所需要的计算工作量，算法的工作量用算法所执行的基本运行次数来度量，所以与运行算法时特定的输入有关，选项A正确。
4.在具有2n个结点的完全二叉树中，叶子结点个数为(A)
A. n
B. n+1
C. n－1
D. n／2
解析：在具有2n个结点的完全二叉树中，叶子结点个数为：(2n+1)／2取整，其值等于n。所以选项A正确。
5.某完全二叉树按层次输出(同一层从左到右)的序列为ABCDEFGH。该完全二叉树的中序序列为(A)
A. HDBEAFCG
B. HDEBFGCA
C. ABDHECFG
D. ABCDEFGH
解析：完全二叉树的特点是除最后一层外，每一层上的节点数均达到最大值；在最后一层上只缺少右边的若干结点。
根据上述特点，完全二叉树按层次输出(同一层从左到右)的序列为ABCDEFGH。可以得到其结构如下，所以此完全二叉树的中序序列是HDBEAFCG。所以选项A正确。
6.下列叙述中正确的是(B)
A. 带链栈的栈底指针是固定的
B. 带链栈的栈底指针是随栈的操作而动态变化的
C. 若带链队列的队头指针与队尾指针相同，则队列为空
D. 若带链队列的队头指针与队尾指针相同，则队列中至少有一个元素
解析：栈(stack)又名堆栈，它是一种运算受限的线性表。其限制是仅允许在表的一端进行插入和删除运算。这一端被称为栈顶，相对地，把另一端称为栈底。向一个栈插入新元素又称作进栈、入栈或压栈，它是把新元素放到栈顶元素的上面，使之成为新的栈顶元素；从一个栈删除元素又称作出栈或退栈，它是把栈顶元素删除掉，使其相邻的元素成为新的栈顶元素。
带链栈的栈底指针是随栈的操作而动态变化的；若带链队列的队头指针与队尾指针相同，则队列可能为0也可能为1。
7.一个教师讲授多门课程，一门课程由多个教师讲授。则实体教师和课程间的联系是(D)
A. 1：1联系
B. 1：m联系
C. m：1联系
D. m：n联系
解析：一个教师可讲授多门课程，一门课程可由多个教师讲授，则实体教师和课程的联系是多对多的联系。
8.有三个关系R，S和T如下图所示，则由关系R和S得到关系T的运算是
(C)
A. 并
B. 自然连接
C. 除法
D. 差
解析：在关系代数中，除法运算可理解为笛卡尔积的逆运算。设被除关系R为m元关系，除关系S为n元关系，那么它们的商为m-n元关系，记为R÷S。商的构成原则是：将被除关系R中的m-n列，按其值分成若干组，检查每一组的n列值的集合是否包含除关系S，若包含则取m-n列的值作为商的一个元组，否则不取。本题中关系T是由关系R和S进行除法运算后的结果。
9.定义学生、教师和课程的关系模式S(S#,Sn,Sd,Dc,Sa)(其属性分别为学号、姓名、所在系、所在系的系主任、年龄)；C(C#,Cn,P#})(其属性分别为课程号、课程名、先修课)；SC(S#,C#,G)(其属性分别为学号、课程号和成绩)，则该关系为(A)
A. 第二范式
B. 第一范式
C. 第三范式
D. BCNF范式
解析：在关系模式S(S#,Sn,Sd,Dc,Sa)中把学号S#设置为主键，则其它列姓名、所在系、所在系的系主任、年龄都依赖主键学号S#。在C(C#,Cn,P#)中将C#课程号设置为主键，则课程名、先修课都依赖主键C#。在SC(S#,C#,G)中，将S#，C#设置为主键，则G成绩依赖于主键S#，C#。所以该关系模式是第二范式。选择A选项。
10.某企业需要在一个办公室构建适用于20多人的小型办公网络环境，这样的网络环境属于(B)
A. 城域网
B. 局域网
C. 广域网
D. 互联网
解析：局域网(Local Area Network，LAN)是指在某一区域内由多台计算机互联成的计算机组。一般是方圆几千米以内。局域网可以实现文件管理、应用软件共享、打印机共享、工作组内的日程安排、电子邮件和传真通信服务等功能。
局域网是封闭型的，可以由办公室内的两台计算机组成，也可以由一个公司内的上千台计算机组成。
11.算法的空间复杂度是指( )。(A)
A. 算法在执行过程中所需要的计算机存储空间
B. 算法所处理的数据量
C. 算法程序中的语句或指令条数
D. 算法在执行过程中所需要的临时工作单元数
解析：算法的空间复杂度是指算法在执行过程中所需要的内存空间，所以选择A选项。
12.下列关于栈叙述正确的是( )。(A)
A. 栈顶元素最先能被删除
B. 栈顶元素最后才能被删除
C. 栈底元素永远不能被删除
D. 栈底元素最先能被删除
解析：栈是“先进后出”的数据结构，因此栈顶元素最后入栈却最先被删除，栈底元素最先入栈却最后被删除，因此本题答案为A。
13.下列关于线性链表的叙述中，正确的是( )，(C)
A. 各数据结点的存储空间可以不连续，但它们的存储顺序与逻辑顺序必须一致
B. 各数据结点的存储顺序与逻辑顺序可以不一致，但它们的存储空间必须连续
C. 进行插入与删除时，不需要移动表中的元素
D. 各数据结点的存储顺序与逻辑顺序可以不一致，它们的存储空间也可以不一致
解析：一般来说，在线性表的链式存储结构中，各数据结点的存储序号是不连续的，并且各结点在
本文档预览：3600字符，共10505字符，源文件无水印，下载后包含无答案版和有答案版，查看完整word版点下载
