2015年软件水平考试程序员考点整理（3）
发布时间：2012/5/26 23:43:41 来源：城市网学院 编辑：ziteng
-
2、线性表
(1) 性表的链式存储体例及以下几种常用链表的特点和运算：单链表、轮回链表，双向链表，双向轮回链表。
(2)单链表的合并算法、轮回链表的合并算法、双向链表及双向轮回链表的插入和删除算法等都是较为常见的考绩体例。
(3)单链表中设置头指针、轮回链表中设置尾指针而不设置头指针以及索引存储结构的各自益处。
3、栈与队列
你可以问一下自己是不是已经知道了以下几点：
(1)栈、队列的界说及其相关数据结构的概念，搜罗：挨次栈，链栈，共享栈，轮回队列，链队等。栈与队列存取数据(请注重搜罗：存和取两部门)的特点。
(2)递归算法。栈与递归的关系，以及借助栈将递归转向于非递归的经典算法：n!阶乘问题，fib数列问题，hanoi问题，背包问题，二叉树的递归和非递归遍历问题，图的深度遍历与栈的关系等。此鱿脯涉及到树与图的问题，多半会在树与图的相关章节中进行考绩。
(3)栈的应用：数值表达式的求解，括号的配对等的事理，只作事理性体味，具体要求考绩此为问题问题的算法设计题不多。
(4)轮回队列中判队空、队满前提，轮回队列中入队与出队(轮回队列在插入时也要判定其是否已满，删除时要判定其是否已空)算法。
【轮回队列的队空队满前提
为了便利起见，商定：初始化建空队时，令
front=rear=0,
当队空时：front=rear，
当队满时：front=rear 亦成立，
是以只凭等式front=rear无法判定队空仍是队满。
有两种体例措置上述问题：
(1)另设一个标识表记标帜位以区别队列是空仍是满。
(2)少用一个元素空间，商定以“队列头指针front在队尾指针rear的下矣闽位置上”作为队列“满”状况的标识表记标帜。
队空时： front=rear，
队满时： (rear+1)%maxsize=front】
如不美观你已经对膳缦沔的几点了如指掌，栈与队列一章可以不看书了。注重，我说的是可以不看书，并不是可以不作题哦。
轮回队列的首要操作：
(1)建树轮回队列
(2)初始化轮回队列
(3)判定轮回队列是否为空
(4)判定轮回队列是否为满
(5)入队、出队
//空出头尾之间的一个元素不用
