数据结构复习题整理(答案).doc

《数据结构复习题整理(答案).doc》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、<<数据结构>>复习题1.以NiklusWirth的观点，程序等于什么?算法+数据结构2.算法的重要特性。有穷性，确定性，可行性，输入，输出3.好算法的标准。正确性，可读性，健壮性，高效率低存储量的需求4.线性结构的特点。（一）存在唯一的一个称做"第一个"的数据元素（二）存在唯一的一个称做"最后一个"的数据元素（三）除了第一个外，其余的每个元素都有前驱（四）除了最后一个外，其余的每个元素只要一个后继5.线性结构与非线性结构的区别。在线性结构中，该数据结构中的元素是一对一的关系，非线性结构就不是了线性结构是最简单

2、最常用的一种数据结构,线性结构的特点是结构中的元素之间满足线性关系,按这个关系可以把所有元素排成一个线性序列.线性表,串,栈和队列都属于线性结构.非线性结构是指在该类结构中至少存在一个数据元素,它具有两个或者两个以上的前驱或后继.如树和二叉树等.6.列出所学过的线性结构与非线性结构。线性结构：线形表，链表，静态链表,栈，队列非线形结构：树，图,广义表7.头指针、头结点、首元结点的区别。头结点：表头结点，不含有数据头指针：一个指针变量，指向链表中的第一个结点首元结点：链上第一个含有数据的结点头指针指链表的指针，若

3、链表有头结点则是链表的头结点的指针，头指针具有标识作用，故常用头指针冠以链表的名字。头结点是为了操作的统一、方便而设立的，放在第一元素结点之前，其数据域一般无意义（当然有些情况下也可存放链表的长度、用做监视哨等等），有头结点后，对在第一元素结点前插入结点和删除第一结点，其操作与对其它结点的操作统一了。而且无论链表是否为空，头指针均不为空。首元结点也就是第一元素结点，它是头结点后边的第一个结点。6.带头结点和不带头结点的线性链表的区别。带头结点的线形链表：便于单个链表的操作，操作比较方便不带头结点的线形链表：便于

4、多个链表的收集（基数排序）头节点的作用（可参考）(1)对带头结点的链表，在表的任何结点之前插入结点或删除表中任何结点，所要做的都是修改前一结点的指针域，因为任何元素结点都有前驱结点。若链表没有头结点，则首元素结点没有前驱结点，在其前插入结点或删除该结点时操作会复杂些。(2)对带头结点的链表，表头指针是指向头结点的非空指针，因此空表与非空表的处理是一样的。7.单链表、双链表、循环链表的区别及各自的优缺点。单链表：每个结点中只包含一个指针域优点：插入和删除时候不需要移动大量的元素双链表：有两个指针域，其一指向直接后

5、继，其二指向直接前驱优点：查找直接前驱的时候，则从头指针出发，能够克服单链表这种单向性的缺点循环链表：最后一个结点的指针域指向头结点优点：使两个表连接起来就很简单，这个操作仅需两个指针即可，插入、删除时，不会断链等。8.栈和队列是什么样的线性表?栈与队列是操作受限制的线性表9.指出顺序线性表、顺序栈、顺序队列的区别。相同：他们都是线性表，都是一维数组，不相同：操作不同而已；线性表：任意位置操作栈：栈顶操作队列：尾进头出10.举出几个栈和队列的实例及用栈和队列所能解决的问题。栈：铁路中转站，餐厅的食物盘,子弹壳。

6、队列：操作系统作业排队，排队买东西栈解决的问题是：后进先出的数据（LIFO）队列解决的问题：先进先出的数据(FIFO)6.指出通常解决"队列"、"栈"的"溢出"时所能用到的方法。队列：双向队列，链队列，循环队列栈：双栈共享，多栈共享，链栈7.循环队列的循环是怎样实现的?比队列多两个分别指向队头元素和队尾元素，尾指针指向队尾元素的当前位置；头指针指向队头元素的前一个位置15.用十字链表存贮稀疏矩阵时,矩阵的每个元素同时在几条链上,分别被称为什么链？两条链：行链和列链16.给出树的不同的几种表示形式。（一）层次表示

7、法（二）嵌套表示法（三）广义表表示法（四）凹入法表示法17.在二叉树的第i层上至多有多少个结点。 2(I-1)个18.深度为K的二叉树至多有多少个结点。 2k-1=2*0+2*1+…+2*k-119.在一颗二叉树中,其终端结点数n0和度为二的结点数n2之间的关系。n0=n2+1;20.有n个结点的完全二叉树的深度。[Log2n]+121.在二叉树的顺序存贮结构中如何求结点的双亲、孩子?双亲：[i/2]；左孩子：2*i；右孩子：2*i+1；22.有n个结点的二叉树用二叉链表存贮时有多少个空链域，用三叉链表存贮时有

8、多少个空链域。 二叉：n+1个空链域三叉：n+2个空链域23.树的几种存贮结构(双亲表示法、孩子表示法、孩子兄弟表示法)的优缺点，各自适应的运算。双亲表示法：利用了每个结点只有一个双亲的性质,便于查找双亲，缺点：找孩子时要多次遍历整个数组孩子表示法：便于涉及到孩子的操作，缺点：找双亲比较麻烦。孩子兄弟法：二叉链表表示法，(一个指针是指向孩子，另一个指向兄弟)这个适用于各种树的操作，（左