计算机二级Ms-office-第一部分-公共基础知识——数据结构与算法.pdf

计算机二级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