2013年上半年软考指定教材

软考历年真题及参考答案专题

软考软件设计师在线辅导班招生

软件设计师考试培训面授班全国招生

5、线性链表

6、线性表的顺序存储和链式存储各有何有缺点？

答：顺序存储结构的优点：①有最佳的空间效率，因为无须存储元素数据以外的任何数据；但是，由于其存储特性的原因，常常要留有足够的自由节点空间以备长度伸展的需要，这又降低了空间效率；②节点定位计算与数据规模和节点大小无关。 缺点： ①当插入或删除节点时为保证位置比邻而要频繁地移动节点，这种移动有时是大量的；②因为初始存储空间的限制致使过多的插入产生“溢出”; ③未必能如愿地申请到足够大小的成片空间。

链式存储结构的优点：不要求连续成片的存储空间，同一数据结构中的诸节点可以任意散存在存储器任何位置，只要保证一个节点能完整存储就够了，且不要求预留任何自由节点空间而能保证长度的任意伸展，节点存储只受存储容量的限制；克服了顺序存储结构的几个致命缺点

缺点：（1）占用额外的空间以存储指针（浪费空间）（2）存取某个元素速度慢（3）插入元素和删除元素速度快（4）没有空间限制，存储元素的个数无上限，基本只与内存空间大小有关。

7、栈表是线性表吗？队列是线性表吗？它们各自的特点是什么？它们有那些存储形式？

有三个元素A、B、C,若入栈、入队次序均为A、B、C,则出栈、出队次序各是怎样的？循环队列见作业。

答：栈和队列都是线性表。 栈的特点：最后压入的节点最先弹出，最先压入的的节点只能最后弹出。 队列的特点：节点在队列中按进队时间先后次序排列；因此，新插入的节点总是排在队尾；删除时总是删除最先进入的队头结点；即有先进先出的特点。

略

8、串的基本概念。

串：是以单个字符为数据元素的线性表，一般只采用顺序存储结构。相关算法主要有串比较、取子串和串匹配等。

返回目录：软件设计师软件技术基础知识要点汇总

编辑推荐：软件设计师教程之计算机系统知识

软件设计师程序语言基础知识汇总