《数据结构与算法》复习题
应用简答题。
1.有下列几种用二元组表示的数据结构,画出它们分别对应的逻辑图形表示,并指出它们分别属于何种结构。
(1)A = {D,R},其中:D={a,b,c,d,e,f,g,h},R ={r},
r = {<a,b>,<b,c>,<c,d>,<d,e>,<e,f>,<f,g>,<g,h>}
(2)B = {D,R},其中:D={a,b,c,d,e,f,g,h},R ={r},
r = {<d,b>,<d,g>,<d,a>,<b,c>,<g,e>,<g,h>,<e,f>}
(3)C = {D,R},其中:D={1,2,3,4,5,6},R ={r},
r = {(1,2),(2,3),(2,4),(3,4),(3,5),(3,6),(4,5),(4,6)}
2.简述顺序表和链表存储方式的特点。
答:顺序表的优点是可以随机访问数据元素,缺点是大小固定,不利于增减结点(增减结点操作需要移动元素)。链表的优点是采用指针方式增减结点,非常方便(只需改变指针指向,不移动结点)。其缺点是不能进行随机访问,只能顺序访问。另外,每个结点上增加指针域,造出额外存储空间增大。
3.对链表设置头结点的作用是什么?(至少说出两条好处)
答:其好处有:
(1)对带头结点的链表,在表的任何结点之前插入结点或删除表中任何结点,所要做的都是修改前一个结点的指针域,因为任何元素结点都有前驱结点(若链表没有头结点,则首元素结点没有前驱结点,在其前插入结点和删除该结点时操作复杂些)。
(2)对带头结点的链表,表头指针是指向头结点的非空指针,因此空表与非空表的处理是一样的。
4.对于一个栈,给出输入项A,B,C。如果输入项序列由A,B,C组成,试给出全部可能的输出序列。
5.设有4个元素1、2、3、4依次进栈,而栈的操作可随时进行(进出栈可任意交错进行,但要保证进栈次序不破坏1、2、3、4的相对次序),请写出所有不可能的出栈次序和所有可能的出栈次序。
c语言的冒泡排序算法
版权声明:本站内容均来自互联网,仅供演示用,请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198,我们将在24小时内删除。
发表评论