搜索
2010-6-7数据结构复习题1.以NiklusWirth的观点，程序等于什么?算法+数据结构2.算法的重要特性。有穷性，确定性，可行性，输入，输出3.好算法的标准。正确性，可读性，健壮性，高效率低存储量的需求4.线性结构的特点。（一）存在唯一的一个称做第一个的数据元素（二）存在唯一的一个称做最后一个的数据元素（三）除了第一个外，其余的每个元素都有前驱（四）除了最后一个外，其余的每个元素只要一个后继5.线性结构与非线性结构的区别。在线性结构中，该数据结构中的元素是一对一的关系，非线性结构就不是了线性结构是最简单最常用的一种数据结构,线性结构的特点是结构中的元素之间满足线性关系,按这个关系可以把所有元素排成一个线性序列.线性表,串,栈和队列都属于线性结构.非线性结构是指在该类结构中至少存在一个数据元素,它具有两个或者两个以上的前驱或后继.如树和二叉树等.6.列出所学过的线性结构与非线性结构。线性结构：线形表，链表，静态链表,栈，队列非线形结构：树，图,广义表7.头指针、头结点、首元结点的区别。头结点：表头结点，不含有数据头指针：一个指针变量，指向链表中的第一个结点首元结点：链上第一个含有数据的结点头指针指链表的指针，若链表有头结点则是链表的头结点的指针，头指针具有标识作用，故常用头指针冠以链表的名字。头结点是为了操作的统一、方便而设立的，放在第一元素结点之前，其数据域一般无意义（当然有些情况下也可存放链表的长度、用做监视哨等等），有2010-6-7头结点后，对在第一元素结点前插入结点和删除第一结点，其操作与对其它结点的操作统一了。而且无论链表是否为空，头指针均不为空。首元结点也就是第一元素结点，它是头结点后边的第一个结点。8.带头结点和不带头结点的线性链表的区别。带头结点的线形链表：便于单个链表的操作，操作比较方便不带头结点的线形链表：便于多个链表的收集（基数排序）头节点的作用（可参考）(1)对带头结点的链表，在表的任何结点之前插入结点或删除表中任何结点，所要做的都是修改前一结点的指针域，因为任何元素结点都有前驱结点。若链表没有头结点，则首元素结点没有前驱结点，在其前插入结点或删除该结点时操作会复杂些。(2)对带头结点的链表，表头指针是指向头结点的非空指针，因此空表与非空表的处理是一样的。9.单链表、双链表、循环链表的区别及各自的优缺点。单链表：每个结点中只包含一个指针域优点：插入和删除时候不需要移动大量的元素双链表：有两个指针域，其一指向直接后继，其二指向直接前驱优点：查找直接前驱的时候，则从头指针出发，能够克服单链表这种单向性的缺点循环链表：最后一个结点的指针域指向头结点优点：使两个表连接起来就很简单，这个操作仅需两个指针即可，插入、删除时，不会断链等。10.栈和队列是什么样的线性表?栈与队列是操作受限制的线性表11.指出顺序线性表、顺序栈、顺序队列的区别。相同：他们都是线性表，都是一维数组，不相同：操作不同而已；线性表：任意位置操作栈：栈顶操作队列：尾进头出12.举出几个栈和队列的实例及用栈和队列所能解决的问题。栈：铁路中转站，餐厅的食物盘,子弹壳。2010-6-7队列：操作系统作业排队，排队买东西栈解决的问题是：后进先出的数据（LIFO）队列解决的问题：先进先出的数据(FIFO)13.指出通常解决队列、栈的溢出时所能用到的方法。队列：双向队列，链队列，循环队列栈：双栈共享，多栈共享，链栈14.循环队列的循环是怎样实现的?比队列多两个分别指向队头元素和队尾元素，尾指针指向队尾元素的当前位置；头指针指向队头元素的前一个位置15.用十字链表存贮稀疏矩阵时,矩阵的每个元素同时在几条链上,分别被称为什么链？两条链：行链和列链16.给出树的不同的几种表示形式。（一）层次表示法（二）嵌套表示法（三）广义表表示法（四）凹入法表示法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个结点的二叉树用二叉链表存贮时有多少个空链域，用三叉链表存贮时有多少个空链域。二叉：n+1个空链域三叉：n+2个空链域23.树的几种存贮结构(双亲表示法、孩子表示法、孩子兄弟表示法)的优缺点，各自适应的运算。2010-6-7双亲表示法：利用了每个结点只有一个双亲的性质,便于查找双亲，缺点：找孩子时要多次遍历整个数组孩子表示法：便于涉及到孩子的操作，缺点：找双亲比较麻烦。孩子兄弟法：二叉链表表示法，(一个指针是指向孩子，另一个指向兄弟)这个适用于各种树的操作，（左指针为空就是叶子）找孩子容易实现缺点：找双亲需遍历整个二叉链表24.哪种存贮结构可将森林转为二叉树。对此种结构的各个域给予注释。说明在这个结构中怎样找到森林的n棵树。孩子兄弟表示法，左指针是第一个孩子，右指针是第一个兄弟，最右的为第n棵树25.树的先根遍历、后根遍历对应其二叉树的哪种遍历，森林的先根遍历、中根遍历对应其二叉树的哪种遍历?树的先根遍历对应二叉树的先序遍历；树的后根遍历对应二叉树的中序遍历；森林的先根遍历对应于二叉树的先序遍历；森林的中根遍历对应于二叉树的中序遍历。26.写算法求树中结点的度；树的度；树中的叶子结点数；树中的非终端结点数；树中某结点的兄弟、祖先、子孙、层次、堂兄弟；树的高度；森林中树的数目。树中某结点的兄弟、祖先、子孙、层次、堂兄弟；树的高度；森林中树的数目。27.何为完全图、稀疏图、稠密图。完全图：有n*(n-1)/2条边的无向图稀疏图：有很少条边的图(enlogn)稠密图：有很多条边的图(e=nlogn)28.写算法求无向图中结点的度；有向图中结点的入度和出度。（这里只给思想，不给算法，邻接矩阵存图）无向图：邻接矩阵的一行或一列的数值和，代表对应定点的度。有向图：邻接矩阵的行代表对应顶点的出度，列代表入度。29.图的数组表示法、邻接表存贮结构各自的优缺点，适应的运算。图的数组表示法（邻接矩阵表示法）：二维数组存储图2010-6-7优点：容易求各个顶点的度缺点：当图为稀疏图时浪费空间邻接表表示法：优点：容易找到第一个邻接点和下一个邻接点，30.顺序查找、折半查找、分块查找算法适合的关键字结构。顺序查找：关键字结构要求不高，混乱都可折半查找：关键字整体有序分块查找：关键字局部有序31.怎样从二叉排序树得到有序表。中序遍历32.指出希尔排序，归并排序，快速排序，堆排序，基数排序中稳定的排序方法，并对不稳定的举出反例。不稳定的是三中：快速，堆，希尔排序33.堆排序算法选用什么样的存贮结构，按此算法得到的有序表是递增还是递减的。一维数组存储，是递减的34.指出直接插入排序，冒泡排序，快速排序，堆排序，基数排序算法各适合的关键字结构。归并排序：快速排序：混乱的情况堆排序：非常多的情况基数排序：多关键字排序