满足线性表的四个基本特征：

(1).有且仅有一个头结点

(2).有且仅有一个尾结点

(3).头结点以外每个结点有且仅有一个前驱

(4).头结点以外每个结点有且仅有一个后继

1.设数据集合为D{1，2，3，4，5}，下列结构B（D,B）中为非线性结构的是【BC】

(A).R={(1,2),(2,3),(3,4),(4,5)}

(B).R={(1,2),(2,3),(4,3),(3,5)}

(C).R={(5,4),(4,3),(2,2),(2,1)}

(D).R={(2,5),(5,4),(3,2),(4,3)}

时间复杂度和空间复杂度的混淆：

(1).程序不等于算法，但算法包括程序。

(2).时间复杂度和空间复杂度与程序执行的效率成反比

(3).算法的时间复杂度与空间复杂度没有直接关系

(4).衡量一个算法的时间复杂度，看的是执行这个算法当中某个程序的次数

(5).算法的空间复杂度是指算法在执行过程中所需要的计算机存储空间

1、在一个长度为N的顺序表中，向第i个元素位置插入一个新元素时，时间复杂度为【D】

(A).-1

(B).i

(C).n-i-1

(D).n-i+1

栈的特征：

(1).栈的操作顺序是“先进后出”，FILO===》“first in last out”

(2).在栈中只能在栈顶插入或删除元素

(3).栈的元素个数由栈顶指针的动态变化而变化

(4).在栈的入栈操作和退栈操作中，栈底指针bottom维持不变

(5).因为栈能保存数据，因此栈具有记忆功能

(6).栈内元素个数计算公式：

　　　　　　|top-bottom|+1

　　　　　　如果栈中top=bottom=0，说明栈是空栈（NULL）

1、设栈的存储空间为S(1：50)，初始状态为top=51，现经过一系列正常的入栈与退栈操作后top=20，则栈中的元素个数为【A】

(A).31　　(B).30

(C).21　　(D).20

2、设栈的顺序存储空间为S（1：50），初始状态为top=0，现经过一系列入栈和退栈运算后，top=20，则当前栈中的元素个数为【D】

(A).29　　(B).30

(C).19　　(D).20

3、某带链栈的初始状态为top=bottom=NULL，经过一系列正常的入栈和退栈操作后，top=bottom=20，该栈中的元素个数为【A】

(A).1

(B).20

(C).不确定

(D).0

4、设栈的顺序存储空间为S（1：m），初始状态为top=m+1，现经过一系列入栈与退栈运算后，top=20，则当前栈中的元素个数为【B】

(A).20　　(B).m-19

(C).m-20　　(D).30

队列：

(1).队列是”先进先出“，入口和出口不是同一个口。

(2).循环队列是队列的一种顺序存储结构，因此存储空间是按顺序连续定义的。

(3).在队列中，只能在队尾插入元素，只能在对头删除元素。

(4).循环队列元素个数的计算方法：

　　循环队列中元素的个数=rear（尾）-front（头）

　　rear-front为正数时，便是循环队列的元素个数

　　rear-front为负数时，元素个数是：rear-front+总容量

　　rear-front为0时，可能是空队或者满队

1、循环队列的存储空间为Q（1：50），初始状态为front=rear=50，经过一系列正常的入队与退队后，front=rear=1，此后又插入两个元素，则循环队列的元素个数是【A】

(A).2　　(B).1

(C).3　　(D).52

2、循环队列的存储空间为Q（1：40），初始状态为front=rear=40，经过一系列正常的入队与退队后，front=rear=15，此后又正常退出一个元素，则循环队列的元素个数是【D】

(A).9　　(B).14

(C).16　　(D).39

3、设循环队列的存储空间为Q（1：50），初始状态为front=rear=50，经过一系列正常的操作后，front=rear-1，为了在队列中寻找最大的元素，在最坏的情况下需要的比较的次数【A】

(A).0　　(B).1

(C).50　　(D).49