2243计算机软件基础(一)复习资料4

51、同时间复杂度一样，算法的空间复杂度粗略的来讲是            算法消耗空间的程度。

52、空间复杂度为O（1），即所耗辅助空间与问题的规模无关。

53、同一线性表中的   数据节点   具有相同的属性。

54、线性表的存储结构有两种：顺序存储结构、链式存储结构

55、可以看出线性表的这种顺序存储结构使得  线性表中逻辑上相邻的数据节点在物理上也相邻。

56、线性表中数据节点在一连续空间中存放，所以很容易计算出各节点存储地址，其地址为：Loc(a_i)=Loc(a₀)+i*d (0≤i≤n-1)

√57、顺序表上顺序查找成功的平均查找次数为   （ 表长+1）/2     

58、在线性表中插入一个数据节点的平均需移动线性表中一半节点。

59、插入运算的时间复杂度与n有关。O（n）= T（n）

60、线性表中删除一个节点，约平均需移动线性表中一半节点    。

61、单链表中每个节点有两个成员：   数据域和指针域  。

62、单链表只能沿链从前向后访问表中节点,无法找到某节点前面的其他节点.而循环单链表可以通过任一点 来访问表中的其他节点。

63、若经常进行的运算为查找运算，以      顺序存储 为宜。

64、若经常进行的运算为插入、删除运算，以链式存储        为宜。

65、顺序存储结构在程序执行之前必须给出空间长度，对数据量事先固定的问题用顺序存储为好。

66、顺序存储  空间利用率    高，而链式相应少一些。

67、栈是一种     先进后出    的线性表。

68、栈也有顺序存储结构和链式存储结构，分别称为顺序栈和链栈。

69、进栈和退栈的运算：答：进栈有以下步骤

1）、先判断栈是否已满，若满，则进行上溢处理，否则进行2）。

2）、栈顶指针上移1个节点。3）将X加入到top所指位置。

退栈有以下步骤：1）、检查栈是否为空，若栈空，则进行下溢处理，否则进行2）。2）保留被删元素到变量X中。

3）栈顶指针下移1个节点。

70、队列是一种    先进先出     的线性表。

71、入队和出队的运算 答：入队运算：

1）、先判断队列满吗？若满则退出；否则进行第二步；

2）、队尾指针后移一个节点位置。3）、在队尾指针的位置加入X。

出队运算：1）、判断队列为空？若空则退出；否则进行第二步。

2）、保留队头元素内容到X变量中。3）、队头指针后　　移1个节点位置。

72、计算机系统用牺牲一个空间的办法来解决当front=rear时，既是循环队列为空，又是循环队列为满这一矛盾的。