计算机二级office选择题笔记整理.pdfVIP

1、*堆排序最坏情况下时间复杂度为nlog2n(时间复杂度最小)

2、结点中两个指针分别指向前驱点和后继结点是线性结构，当指向两个不同的前驱或者后驱结点

时为非线性结构。线性结构的存储结点可以由多个指针只有保证有且只有指向一个前驱结点和

一个后继结点就是线性结构。

3、线性表的顺序存储结构的两个特点：（1）线性表中所有元素所占的存储空间是连续的；（2）

线性表中各数据元素在存储空间中是按逻辑顺序依次存放的。另在线性表中数据元素所占的字

节数都是一致的。

4、在二叉树中，度为0的结点个数总比度为2的结点个数多一个。

5、循环列表的第一个结点就是根结点，最后一个结点就是叶子结点。非空循环链表表示的数据结

构有根结点也有叶子结点。

6、*在排序过程中，每一次数据元素的移动会产生新的逆序的排序方法是快速排序。冒泡排序每

次只交换两个相邻的数据。

7、*程序可以作为算法的一种表达方式，算法的有穷性是指算法必须在有限的时间内结束；算法

的复杂度用来衡量算法的好坏；算法的效率与数据的存储结构和逻辑结构有关。

8、操作系统中的作业调度使用的是队列的思想。

9、*二叉链表为非线性结构，循环列表、双向链表、循环列队为线性结构。线性结构要求只有一

个根结点，只有一个叶子结点，一个前件一个后件。

10、*空数据结构可以是线性结构也可以是非线性结构，数据结构中的数据元素可以是另一数据结

构，非空数据结构可以没有根结点，数据结构中的元素可以是另外一种数据结构。

11、为了降低算法的空间复杂度，要求算法尽快采用原地工作。原地工作指：执行算法时所使用的

额外空间固定（即不随算法所处理的数据空间大小的变化而变化）。

12、二分查找法只适用于顺序存储的有序线性表，二分法称拆半查找，能使用二分法查找的线性表

必须满足两个条件：顺序存储结构以及线性表有序。循环链表和双向链表都不是顺序存储结构。

13、算法的时间复杂度是指执行算法所需要的计算工作量。算法所执行的基本运算次数与问题规模

有关。固定的规模，算法所执行的基本运算次数还可能与特定的输入有关。对于各种特定的输

入，算法的时间复杂度是固定不变的。

14、长度为n的顺序表中查找一个元素，最好情况的比较次数是1，最坏情况的比较次数是n，则

平均情况的比较次数为（n+1）/2。

15、根结点的值一定大于左子树的结点，并且一定小于右子树的结点，先左子树，再根结点，再右

子树，采用中序遍历。

16、*当头指针和尾针指向同一个元素时，循环队列为空或满。

17、算法中均以比较作为基本运算，则平均情况与最坏情况下的时间复杂度相同的是在顺序存储的

线性表中寻找最大项，平均情况和最坏情况的比较次数为n-1。

18、具有偶数个结点的完全二叉树，其叶子结点数和非叶子结点数各占一半。

19、*栈底指针不动，栈顶指针随着入栈和出栈操作而变化，所以栈顶指针的动态变化决定了栈中

元素个数。

20、空队列产生下溢错误。

21、在循环队列中，队头指针和队尾指针的动态变化决定队列的长度。队头指针和队尾指针动态变

化，循环列队中的元素个数由队头指针和队尾指针共同决定。

22、冒泡排序、快速排序、直接插入排序、简单选择排序最坏情况下n(n-1)/2，堆排序最小。

23、*长度为n，最坏情况下比较次数小于n的是二分查找法（log2n）

24、循环队列是队列的顺序存储结构，二叉链表是二叉树的存储结构；循环队列是队列的存储结构；

栈是线性结构。

25、最坏情况下比较次数小于n的是寻找最大项，顺序表中，（n-1）

26、算法的空间复杂度是指算法在执行过程中所需要的存储空间，对算法执行中的数据进行压缩存

储，会降低算法的空间复杂度。

27、所有结点都只有一个子结点的特殊二叉树可以用顺序存储结构存储。有的二叉树也能用顺序存

储结构表示。

28、解决一个问题可以有不同算法，且时间复杂度可以不同。

29、有一个以上根结点的数据结构一