1.假设线性表的长度为n，则最坏情况下:
冒泡排序: 需要经过n/2遍的从前往后扫描和n/2遍从后往前扫描，需要比较的次数为n(n-1)/2。总的时间复杂度为O(n的平方)。
快速排序: 比较次数也是n(n-1)/2。总的时间复杂度为O(n的平方)。
直接插入排序: 所需要比较的次数为n(n-1)/2。总的时间复杂度为O(n的平方)。
希尔排序所需要比较的次数为O(n的1.5次方)。(时间复杂度小于以上三种)
堆排序: 最坏情况下，其时间复杂度为O(nlogn)。(小于O(n的平方))。
2.根据数据结构中各元素之间前后关系的复杂程度，一般数据结构分为两大类: 线性结构和非线性结构。
如果一个非空的数据结构满足下列两个条件，①有且只有一个根结点 ②每个结点最多有一个前件，也最多有一个后件。则称该数据结构为线性结构，又称线性表。
3.算法时间复杂度与空间复杂度没有关系。
4.所谓算法的时间复杂度，是指执行算法所需要的计算工作量。
为了能够比较客观的反映出一个算法的效率，在度量一个算法的工作量时，不仅应该与所用的计算机程序设计语言，以及程序编制者无关，而且还应该与算法实现过程中的许多细节无关。
5.同一问题可用不同算法解决，而一个算法的质量优劣将影响到算法乃至程序的效率。
算法分析的目的在于选择合适算法和改进算法。
6.堆排序在平均情况下的时间复杂度与最坏情况下的时间复杂度都是O(nlogn)。
7.二叉链表: 以二叉链表作为树的存储结构。链表中结点的两个链域分别指向该结点的第一个孩子结点和第一个孩子下的一个兄弟结点。
循环链表是链式存储结构，循环队列是线性存储结构。( 【×】循环链表是循环队列的链式存储结构)
双向链表也叫双链表，是链表的一种，它的每个数据结点都有两个指针，分别指向直接后继和直接前驱，所以从双链表中的任意一个结点开始都可以很方便地访问它的前驱结点和后继结点。
8.数据的逻辑结构由两个要素: 一是数据元素的集合，通常记为D。二是D上的关系，它反映了D中各元素之间的前后件关系，通常记为R。
即一个数据结构可以表示成B=(D,R)，其中B表示数据结构，为了反映D中各元素之间的前后件关系，一般用二元组来表示。例如，假如a与b是D中的两个数据，则二元组表示a是b的前件，b是a的后件。
线性结构用图形表示更加直观。例如: R=｛(5,1)，(7,9)，(1,7)，(9,3)｝，结构为: 5→1→7→9→3
9.快速排序法是一种互换类的排序方法，但由于比冒泡排序的速度快，因此称为快速排序。
其基本思想是从线性表中选择一个元素设为t，将线性表后面小于t的元素移到前面，而前面大于t的元素移到后面，结果就将线性表分成了两部分，t插入到分界线的位置处，这个过程称为线性表的分割。
简单插入排序法，是指将无序序列中的各元素依次插入到已经有序的线性表中。
冒泡排序法是一种最简单的交换类排序方法，它是通过相邻数据元素的交换，逐步将线性表变为有序。
后两种元素的移动过程中不会产生新的逆序。
10.程序可作为算法的一种描述。
11.为了降低算法的空间复杂度，要求算法尽量采用原地工作，所谓的原地工作是指执行算法时所使用的额外空间固定。
一个算法的空间复杂度一般是指执行这个算法所需要的内存空间，一个算法所占用的存储空间包括程序所占的空间，输入的初始数据所占的空间以及算法执行过程中所需要的额外空间。
12.能从任意一个结点开始没有重复的扫描到所有结点的数据结构是循环链表。
13.循环队列是队列的一种存储结构
14.算法的设计要求包括效率与低存储量，即要考虑算法的时间复杂度与空间复杂度。
算法的复杂度包括时间复杂度和空间复杂度。
时间复杂度: 是指执行算法所需要的计算工作量。
空间复杂度: 一般是指执行这个算法所需要的内存空间。
15.栈是一种特殊的线性表。链式结构把每一个存储结点分为数据域与指针域，带链的栈可以通过指针域的变化改变原有的栈的组织数据原则; 而顺序栈的栈底指针不变，栈顶指针改变。
16.堆排序在最坏的情况下需要比较nlogn次。
快速排序，在最坏情况下需要比较n(n-1)/2次。
顺序查找，在最坏情况下需要比较n次。
最坏情况下，二分查找需要log2n(小于n-1)
在长度为n的顺序表中寻找最大项/最小项时，比较次数最少为1，最多为n-1。
17.如果一个非空的数据结构满足下列两个条件，①有且只有一个根节点 ②每一个结点最多有一个前件，也最多有一个后件，则称该数据结构为线性结构。如果一个数据结构不是线性结构，则称为非线性结构。
18.带链栈空的条件是 top=bottom=NULL
19.满二叉树也是完全二叉树，完全二叉树不一定是满二叉树。对于满二叉树和完全二叉树来说，可以按照程序进行顺序存储，不仅节省了空间，又能方便地确定每一个结点的父结点等于左右子结点的位置，但顺序存储结构对于一般的二叉树不适用。
20.带链栈队头指针与队尾指针相同，且不为空时，队列元素个数为1; 若为空时，队列元素个数为0。
带链栈的栈底指针是随栈的操作而动态变化的。
21.二叉树的链式存储结构，也称为二叉链表。在二叉树中，由于每一个元素可以有两个后件，因此用于存储二叉树的存储结点的指针域有两个，所以二叉链表属于非线性结构。
22.线性表由一组元素数据元素构成，各元素的数据类型必须相同，矩阵是一个比较复杂的线性表，线性表除了插入和删除运算之外，还可以查找，排序，分解，合并等。数组是长度固定的线性表。
23.冒泡排序中，在互换两个相邻元素时，只能消除一个逆序; 快速排序及希尔排序中，一次交换可以消除多个逆序。
24.二分法检索的效率比较高，设线性表有n个元素，则最多的比较次数为log2n，最少检索次数为1。
25.循环链表的结构具有以下两个特点。一，在循环链表中，增加了一个表头结点，其数据域为任意或者根据需要来设置指针域指向线性表的第一个元素的结点。循环链表的头指针指向表头结点。二、循环链表中最后一个节点的指针域不是空，而是指向表头结点，即在循环链表中所有的结点指针构成一个环状链。
26.二叉树的存储结构是非线性结构，而完全二叉树是特殊形态的二叉树。采用顺序存储的完全二叉树属于非线性结构。
27.时间复杂度和计算机运行速度以及存储空间无关。
算法的空间复杂度和存储结构无关。
数据处理效率与数据的存储结构有关。
28.线性表，向量，栈，队列都属于线性结构的顺序存储。
29.循环队列是队列的存储结构。
循环链表是另一种形式的念式存储结构。
(✘循环链表是循环队列的链式存储结构。✘)
30.完全二叉树的总结点为奇数时，叶子结点是总结点加一再除以二。
31.在实际处理中，可以用一位数组来存储堆序列中的元素，也可以用完全二叉树来直观的表示堆的结构。在用完全二叉树表示堆时，树中所有非叶子结点值均不小于其左，右子树的根结点值，因为堆顶元素必须为序列的n个元素的最大项，因此其中序并不是有序序列。
多重链表指表中每个结点由两个或两个以上的指针域的链表。如果一个非空的数据结构满足下列两个条件，①有且只有一个根结点，②每个结点最多有一个前件，也最多有一个后件，则称该数据结构为线性结构，所以多重链表不一定是非线性结构。
在计算机中二叉树通常采用链式存储结构，对于满二叉树和完全二叉树来说，可以按层次进行顺序存储。
排序二叉树的中序遍历序列是有序序列。
32.对于一个固定的规模，算法所执行的基本运算次数还可能与特定的输入有关。
33.在线性表中寻找最大项时，平均情况下和最坏情况下比较次数都是n-1。
34.在长度为n的顺序表中查找一 个元素， 假没需要查找的元素有一半的机会在表中，并且如果元素在表中，则出现在表中每个位置上的可能性是相
同的。则在平均情況下需要比较的次数大约为_
A.3n/4 B.n C.n/2 D.n/4
本题的考查知识点是顺序表的存储结构。
因为需要查找的元素有一半机会在表中，所以二分之一的情况下平均比较次数为n/2，另二分之一的情况下平均比较次数为n。总的平均比较次数为(n/2+n) /2-3n/4。
故本题答案为A。
35.设数据结构B=(D, R)，其中
D={a,b,c,d，e，f}
R={(a，b)，(b，c)，(c，d)，(d，e)，(e，f)，(f,a)}该数据结构为
A.线性结构 B.循环队列
C.循环链表 D.非线性结构
本题的考查知识点是数据结构。
如果一个非控的数据结构满足下列两个条件: 1) 有且只有一个根节点; 2) 每一一个结点最多有一一个前件，也最多有一一个后件。则称该数据结构为线性结构。如果一个数据结构不是线性结构，则称之为非线性结构。
数据结构B=(D, R)中， 每一个结点均有一个前件，不符合“有且只有一个根节点”的条件，所以为非线性结构。故本题答案选D。
36.某带链的队列初始状态为front=rear=NULL。经过一系列正常的入队与退队操作后，front=rear=10。 该队列中的元素个数为_
A.1 B.0 C.1或0 D.不确定
本题的考查知识点是带链队列。
在初始状态为front=rear=NULL的带链队列入队时，如果插入的结点既是队首结点又是队尾结点，则rear和front同时指向这个结点;否则在循环队列的队尾加入一一个新元素，rear指向新增结点的数据域，rear+1, front不变。 退队时，在循环队列的排头位置退出一个元素并赋给指定的变量，front指向第二个结点的数据域，front+1, rear不变。当front=rear=10时， front和rear同时指向这个唯一 元素，所以该队列中的元素个数为1。
故本题答案为A。
37.若二叉树没有叶子结点，则为空二叉树。
38.某带链栈的初始状态为top=bottom=NULL, 经过一系列正 常的入栈与退栈操作后，top=10, bottom=20。 该栈中的元素个数为_____。
A.不确定 B. 10 C.1 D.0
本题考查的知识点是栈。
带链的栈是具有栈属性的链表，线性链表的存储单元是不连续的，为把存储空间中一-些离散的空闲存 储结点利用起来，把所有空闲的结点组织成一个带链的栈，称为可利用栈。
线性链表执行删除操作运算时， 被删除的结点可以”回收到可利用栈，对应于可利用栈的入栈运算;线性链表执行插入运算时，需要一个新的结点，可以在可利用栈中取栈顶结点，对应于可利用栈的退栈运算。
可利用栈的入栈运算和退栈运算只需要改动top指针即可。因为是不连续的存储空间，所以top指针将不会有规律地连续变化，因此无法据此判断栈中的元素个数。
所以本题答案为A。
网友评论