计算机二级Msoffice第一部分公共基础知识——数据结构与算法
1.下列叙述中正确的是()。（）
A、算法的复杂度与问题的规模无关
B、算法的优化主要通过程序的编制技巧来实现
C、对数据进行压缩存储会降低算法的空间复杂度(正确答案)
D、数值型算法只需考虑计算结果的可靠性
答案解析：参考解析：为了降低算法的空间复杂度，主要应减少输入数据所占的存储空间以及额外空间，通常采用压缩存储技术，C选项叙述正确。算法的计算工作量是用算法所执行的基本运算次数来度量的，而算法所执行的基本运算次数是问题规模(通常用整数)表示的函数，A选项叙述错误。算法的复杂度与程序的编制无关，B选项叙述错误。算法需要考虑可行性、确定性、有穷性等，D选项叙述错误。
2.设有一个栈与一个队列的初始状态均为空。现有一个序列A,B,C,D，E,F,G,H。先分别将序
列中的前4个元素依次入栈，后4个元素依次入队；然后分别将栈中的元素依次退栈，再将队列中的元素依次退队。最后得到的序列为()。（）
A、A,B,C,D,E,F,G,H
B、A,B,C,D,H,G,F,E
C、D,C,B,A,H,G,F,E
D、D,C,B,A,E,F,G,H(正确答案)
答案解析：参考解析：栈按先进后出的原则组织数据，所以入栈最早的元素最后出栈。队列按先进先出的原则组织数据,所以入队最早的元素最先退队。入栈的顺序为A，B，C，D,则退栈的顺序为D，C，B，A；入队的顺序为E，F，G，H，退队的顺序为E，F，G，H。
3.设某棵树的度为3，其中度为3,2,1的结点个数分别为3,0,4。则该树中的叶子结点数为()。（）
A、6
B、7(正确答案)
C、8
D、不可能有这样的树
答案解析：参考解析:假设叶子结点个数为n。这棵树的总结点数为度为3的结点数+度为2的结点数+度为1的结点数+度为0的结点数，即为3+0+4+n。再根据树的性质:树的总的结点数为树中所有结点的度数之和再加1，则总结点数为3x3+2x0+1x4+0xn+1。3x3+1x4+1-3+4+n,则n=7，叶子结点数为7。
4.下列叙述中正确的是()。（）
A、循环队列是队列的一种顺序存储结构(正确答案)
B、循环队列是队列的一种链式存储结构
C、循环队列中的队尾指针一定大于队头指针
D、循环队列中的队尾指针一定小于队头指针
答案解析：参考解析：循环队列是队列的一种顺序存储结构，用队尾指针rear指向队列中的队尾元素，用排头指针front指向排头元素的前一个位置。因此，从排头指针front指向的后一个位置直到队尾指针rear指向的位置之间所有的元素均为队列中的元素。在循环队列中队头指针可以大于队尾指针，也可以小于队尾指针。
5.设栈与队列初始状态为空。将元素A,B,C,D,E,F,G,H依次轮流入栈和入队，然后依次轮流出栈和退队，则输出序列为()。（）
A、A,B,C,D,H,G,F,E
B、B,G,D,E,F,C,H,A
C、D,C,B,A,E,F,G,H
D、G,B,E,D,C,F,A,H(正确答案)
答案解析：参考解析：栈按先进后出的原则组织数据，所以入栈最早的元素最后出栈；队列按先进先出的原则组织数据，所以入队最早的元素最先退队。将元素A,B,C,D,E,F,G,H依次轮
流入栈和入队，则入栈的顺序为A,C,E,G,入队的顺序为B,D,F,H,然后依次轮流出栈和退队，则G先出栈，然后B退队，出栈的顺序为G,E,C,A,退队的顺序为B,D,F,H,输出顺序为G,B,E,D,C,F,A,H。
6.设二叉树的前序序列为ABDEGHCFI，中序序列为DBGEHACIFJ。则按层次输出(从上到下，同一层从左到右)的序列为()。（）
A、ABCDEFGHIJ(正确答案)
B、DGHEBUFCA
C、JIHGFEDCBA
D、GHIUDEFBCA
答案解析：参考解析：二叉树遍历可以分为3种:前序遍历(访问根结点在访问左子树和访问右子树之前)、中序遍历(访问根结点在访问左子树和访问右子树两者之间)、后序遍历(访问根结点在访问左子树和访问右子树之后)。本题中二叉树的前序序列为ABDEGHCFIJ，可确定根
结点为A,按层次输出(从上到下，同一层从左到右)时访问的第一个结点也应该是A,所以可排除B、C、D三项。
7.下列叙述中错误的是()。（）
A、循环链表中有一个表头结点
B、循环链表的存储空间是连续的(正确答案)
C、循环链表的表头指针与循环链表中最后一个结点的指针均指向表头结点
D、循环链表实现了空表与非空表运算的统一
答案解析：参考解析：线性表链式存储结构的特点是，用一组不连续的存储单元存储线性表中的各个元素。线性链表的存储单元是任意的，即各数据结点的存储序号可以是连续的，也可以是不连续的。循环链表采用链式存储结构，因此存储空间也可以是不连续的。
8.设栈的存储空间为S(1:50)，初始状态为top=51。现经过-系列正常的入栈与退栈操作后，top=50,则栈中的元素个数为()。（）
A、0
B、1(正确答案)
C、50
D、49
答案解析：参考解析：栈的存储空间为S(1:50)，初始状态为top=51,即栈的初始状态为空。当第一个元素进栈后，top=50,第二个元素进栈后，top=49，第三个元素进栈后，top=48,以此类推；若第三个元素出栈后，top=48,第二个元素出栈后，top=50。即每进栈一个元素，top-1;每出栈一个元素，top+1。当top=50时，栈中只有一个元素。
9.某二叉树共有399个结点，其中有199个度为2的结点，则该二叉树中的叶子结点数为()。（）
A、不存在这样的二叉树
B、198
C、199
D、200(正确答案)
答案解析：参考解析：根据二叉树的性质:对任何一棵二叉树，度为的结点(即叶子结点)总是比度为2的结点多一个。本题中，度为2的结点个数为199,则叶子结点数为199+1=200。199+200=399,即这棵二叉树中只存在度为0和度为2的结点，不存在度为1的结点。
10.在长度为的有序链表中进行查，最坏情况下需要比较的次数为()。（）
A、n-1先序中序后序遍历二叉树
B、n/2
C、n(正确答案)
D、与有序顺序表的对分查相同
答案解析：参考解析：最坏情况为:查的元素为表中最后一个元素或查的元素不在表中，则需要比较表中所有元素，所以最坏情况下需要比较次数为n。

版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。