数据结构总复1.doc

数据结构总复习-彭绪成作1 填空题：1、 根据数据元素之间关系的不同特性，通常有_线性结构_、_树形结构_、_图_、_集合_四类基本逻辑结构，它们反映了四类基本的数据组织形式。2、 数据结构=( 数据元素 )+ （ 关系 ）.3、 程序=（ 数据结构 ）+（ 算法 ）4、 一个算法的效率可分为（ 时间复杂度 ）和（ 空间复杂度）； 5、 ） 效率。5、算法的特点有5个，分别是（ 确定性 ）、（ 有限性 ）、输入、输出和（ 有效性 ）.6、算法是：对特定问题求解步骤的一种描述。7、常见时间复杂性的量级有：常数阶O(_1_)、对数阶O(_log2n_)、线性阶O (_n_)、平方阶O(_n2_)、和指数阶O(_2n_)。8、为了便于讨论，有时将含n(n=0)个结点的线性结构表示成(a1，a2,an)，其中每个ai代表一个 数据元素_。a1称为_头_结点，an称为_尾_结点，i称为ai在线性表中的_下标_或_索引_。对任意一对相邻结点ai、ai1(1=in),ai称为ai1的直接_前驱_ai1称为ai的直接_后继_。9、.线性结构的基本特征是:若至少含有一个结点，则除起始结点没有直接_前驱_外，其他结点有且仅有一个直接_前驱_;除终端结点没有直接_后继_外，其它结点有且仅有一个直接_后继_.10、 所有结点按1对1的邻接关系构成的整体就是_线性_结构。11、栈修改的原则是_先进后出_或称_后进先出_。在栈顶进行插入运算，被称为_进栈_或_入栈_，在栈顶进行删除运算，被称为_出栈_或_栈_。12、在队列中，新插入的结点只能添加到_队尾_，被删除的只能是排在_队头_的结点。13、 顺序队的出、入队操作会产生“_溢出_”。14、 上三角矩阵中，主对角线上的第t行(1=t=1)层上至多有_2i-1_个结点。17、深度为k(k=1)的二叉树至多有_2i-1_个结点。18、对任何二叉树，若度为2的节点数为n2，则叶子数n0=_n2+1_。19、满二叉树上各层的节点数已达到了二叉树可以容纳的_最大值_。满二叉树也是_完全_二叉树，但反之不然。20、 具有n个结点的完全二叉树的深度为_log2n +1_。21树的主要遍历方法有_先序遍历_、_中序遍历_、_后序遍历_等三种。22、若二叉树的一个叶子是某子树的中根遍历序列中的第一个结点，则它必是该子树的后根遍历序列中的_1_个结点。23、在_先序_遍历二叉树的序列中，任何结点的子树上的所有结点，都是直接跟在该结点之后。24、 具有n个结点的完全二叉树，若按层次从上到下、从左到右对其编，号（根结点为1号），则编号最大的分支结点序号是_n/2_，编号最小的分支结点序号是_1_，编号最大的叶子结点序号是_n_，编号最小的叶子结点序号是_2log2n_。25、哈夫曼树是带权路径度_最小_的树，通常权值较大的结点离根_较近_。26、有m个叶子结点的哈夫曼树，其结点总数为_2m-1_ 27.图的存储结构主要有_邻接表_和_邻接矩阵_两种。28.邻接表表示法是借助_单链表_来反映顶点间的邻接关系，所以称这个单链表为邻接表。29.对无向图，若它有n顶点e条边，则其邻接表中需要_2e+n_个结点。其中，_2e_个结点构成邻接表，_n_个结点构成顶点表。30.对有向图，若它有n顶点e条边，则其邻接表中需要_n+e_个结点。其中，_e_个结点构成邻接表，_n_个结点构成顶点表。31、遍历图的基本方法有_广度_优先搜索和_深度_优先搜索两种。32、深度优先搜索遍历类似于树的_先序_遍历，它所用到的数据结构是_栈_；广度优先搜索遍历类似于树的_层次_遍历，它所用到的数据结构是_队列_。33、 在有向图的邻接矩阵上，由第i行可得到第_i_个结点的出度，而由第j列可得到第_j_个结点的入度 2 选择题：1、以下说法错误的是 ( 4 )所谓数据的逻辑结构指的是数据元素之间的逻辑关系的整体数据的逻辑结构是指各数据元素之间的逻辑关系，是用户按使用需要而建立的数据结构、数据元素、数据项在计算机中的映象分别称为存储结构、结点、数据域数据项是数据的基本单位2、通常要求同一逻辑结构中的所有数据元素具有相同的特性，这意味着 ( 2 )数据元素具有同一特点不仅数据元素所包含的数据项的个数要相同，而且对应数据项的类型要一致每个数据元素都一样数据元素所包含的数据项的个数要相等3、线性结构中的一个结点代表一个 （ 1 ） 数据元素 数据项 数据 数据结构4、顺序表的一个存储结点仅仅存储线性表的一个 （ 1 ） 数据元素 数据项 数据 数据结构 5、顺序表是线性表的 （ 2 ） 链式存储结构 顺序存储结构 索引存储结构 散列存储结构6、对于顺序表，以下说法错误的是 （ 1 ） 顺序表是用一维数组实现的线性表，数组的下标可以看成是元素的绝对地址 顺序表的所有存储结点按相应数据元素间的逻辑关系决定的次序依次排列 顺序表的特点是:逻辑结构中相邻的结点在存储结构中仍相邻 顺序表的特点是:逻辑上相邻的元素，存储在物理位置也相邻的单元中7、链表不具有的特点是 ( A )。 A) 可随机访问任一个元素B) 插入删除不需要移动元素 C) 不必事先估计存储空间D) 所需空间与线性表的长度成正比8、在长度为n的顺序表的第i个位置上插入一个元素（1 i n+1），元素的移动次数为：（ A ） A) n i + 1 B) n I C) i D) i 1 9、以下说法正确的是（3）线性结构的基本特征是：每个结点有且仅有一个直接前趋和一个直接后继线性表的各种基本运算在顺序存储结构上的实现均比在链式存储结构上的实现效率要低在线性表的顺序存储结构中，插人和删除元素时，移动元素的个数与该元素位置有关顺序存储的线性表的插人和删除操作不需要付出很大的代价，因为平均每次操只有近一半的元素需要移动10、以下说法错误的是 （ 4 ）求表长、定位这二种运算在采用顺序存储结构时实现的效率不比采用链式存储结构时实现的效率低顺序存储的线性表可以随机存取由于顺序存储要求连续的存储区域，所以在存储管理上不够灵活线性表的链式存储结构优于顺序存储结构11、以下说法错误的是 （ 2 ）线性表的元素可以是各种各样的，逻辑上相邻的元素在物理位置上不一定相邻在线性表的顺序存储结构中，逻辑上相邻的两个元素在物理位置上不一定相邻在线性表的链式存储结构中，逻辑上相邻的元素在物理位置上不一定相邻线性表的链式存储结构的特点是用一组任意的存储单元存储线性表的数 12、以下说法正确的是 (1 ) 因链栈本身没有容量限制,故在用户内存空间的范围内不会出现栈满情况 因顺序栈本身没有容量限制,故在用户内存空间的范围内不会出现栈满情况 对于链栈而言,在栈满状态下,如果此时再作进栈运算，则会发生“上溢” 对于顺序栈而言在栈满状态下如果此时再作迸栈运算，则会发生“下溢” 13、设有一顺序栈S，元素s1,s2,s3,s4,s5,s6依次进栈，如果6个元素出线的顺序是s2,s3,s4, s6 , s5,s1,则栈的容量至少应该是 （ 2 ） 2 3 5 614、一个栈的入栈序列是a,b,c,d,e,则栈的不可能的输出序列是 （ 3 ） e d c b a d e c b a d c e a b a b c d e15、一个队列的人列序是1，2，3，4，则队列的输出系列是 （ 2 ） 4，3，2，1 1，2，3，4， 1，4，3，2 3，2，4，116、设计一个判别表达式中左、右括号是否配对出线的算法，采用（ 2 ）数据结构最佳。 线性标的顺序存储结构 栈 队列 线性表的链式存储结构 17、深度为6的二叉树最多有( )个结点 ( 2 ) 64 63 32 3118、将含有83个结点的完全二叉树从根结点开始编号，根为1号，后面按从上到下、从左到右的顺序对结点编号，那么编号为41的双结点编号为 ( 4 ) 42 40 21 2019、设二叉树有n个结点，则其深度为 ( 4 ) n-1 n 5floor(log2n) 无法确定20、设深度为k的二叉树上只有度为0和度为2的节点，则这类二叉树上所含结点总数最少（ 3 ）个 k+1 2k 2k-1 2k+121、.已知某二叉树的后续遍历序列是dabec,中序遍历序列是deabc,它的前序遍历序列是（ ）acbed deabc decab cedba22、某二叉树的前序遍历结点访问顺序是abdgcefh,中序遍历的结点访问顺序是dgbaechf,则其后序遍历的结点访问顺序是 （ ） bdgcefha gdbecfha bdgechfa gdbehfca23、在无向图中，所有顶点的度数之和是所有边数的（ 2 ）倍。 0.5 1 2 4 24、7.在有向图中，所有顶点的入度之和是所有顶点出度之和的（ 1 ）倍。 0.5 1 2 4 25、以下说法错误的是 （ 2 ） 用相邻矩阵法存储一个图时，在不考虑压缩存储的情况下，所占用的存储空间大小只与图中结点个数有关，而与图的边数无关。 邻接表法只能用于有向图的存储，而相邻矩阵法对于有向图和无向图的存储都适用。 存储无向图的相邻矩阵是对称的，因此只要存储相邻矩阵的下（或上）三角部分就可以了 （4）用相邻矩阵A表示图，判定任意两个结点Vi和Vj之间是否有长度为m的路径相连，则只要检查A的第 i行第j列的元素是否为0即可。 26、设有序表的关键字序列为1，4，6，10，18，35，42，53，67，71，78，84，92，99，当用二分查找法查找健值为84的结点时，经（ 3 ）次比较后查找成功。2 3 4 1227、静态查找表与动态查找表两者