数据结构复习题答案修订版.docxVIP

一、填空题 1、根据需要，数据元素又被称为__元素_、_结点_、__顶点_或记录。2、在一棵二叉有哪些信誉好的足球投注网站树中，每个分支结点的左子树上所有结点的值一定小于该结点的值，右子树上所有结点的值一定大于该结点的值。 3、通常从正确性、可读性、健壮性、高效性等几方面评价算法的(包括程序)质量。4、假定一棵二叉树的结点数为18，则它的最小深度为5，最大深度为18。 5、顺序存储结构是通过 物理上相邻表示元素之间的关系的;链式存储结构是通过指针表示元素之间的关系的。6、在线性结构中,第一个结点无前驱结点,其余每个结点有且只有1个前驱结点；最后一个结点无后续结点,其余每个结点有且只有1个后续结点。7、在树形结构中，树根结点没有前驱结点，每一个结点只有一个前驱结点，称为根结点。8、栈是操作受限的线性表，其运算遵循后进先出的原则。9、哈夫曼树是带权路径度长度最短的树，通常权值较大的结点离根较近。10、从数据结构的观点看，通常所说的数据应分成三个不同的层次，即数据、数据元素和数据项。11、一个运算的实现是指一个完成该运算功能的程序。运算实现的核心是处理步骤的规定，即算法设计。12、线性结构的基本特征是:若至少含有一个结点，则除起始结点没有直接前驱外，其他结点有且仅有一个直接前驱;除终端结点没有直接后续外，其它结点有且仅有一个直接后续。13、顺序表的特点是表中相邻的数据元素在内存中存储位置也相邻 。14、栈的基本运算至少应包括初始化、进栈、出栈、与读栈、判栈空五种。 15、从有序表(12，18，30，43，56，78，82，95)中依次二分查找43和56元素时，其查找长度分别为1和3。16、对于顺序栈而言，在栈满状态下，如果此时在作进栈运算，则会发生“上溢”。17、深度为k(k=1)的二叉树至多有2^k-1个结点。18、结点最少的树为只有一个结点，结点最少的二叉树为空二叉树。19、常见时间复杂性的量级有：常数阶O(1)、对数阶O(log2n)、线性阶O (n)、平方阶O(n^2)、和指数阶O(2^n)。20、数据结构的三要素是指数据元素、逻辑结构和存储结构。21、二叉树由根结点，左子树，右子树三个基本单元组成。22、向栈中压入元素的操作是先存入元素，后移动栈顶指针。23、一棵有n个结点的满二叉树有0个度为1的结点、有（n-1）/2个分支 （非 终端）结点和（n+1）/2个叶子，该满二叉树的深度为 log2(n) +1。 24、通常从四个方面评价算法的质量：正确性、易读性、强壮性和高效性。25、一个算法的时间复杂度为(n3+n2log2n+14n)/n2，其数量级表示为o（n）。26、假定一棵树的广义表表示为A（C，D（E，F，G），H（I，J）），则树中所含的结点数为9个，树的深度为3，树的度为3。27、后缀算式9 2 3 +- 10 2 / -的值为-1。中缀算式（3+4X）-2Y/3对应的后缀算式为3 4 X * + 2 Y * 3 / -。28、若用链表存储一棵二叉树时，每个结点除数据域外，还有指向左孩子和右孩子的两个指针。在这种存储结构中，n个结点的二叉树共有2n个指针域，其中有n-1个指针域是存放了地址，有n+1个指针是空指针。29、对于一个具有n个顶点和e条边的有向图和无向图，在其对应的邻接表中，所含边结点分别有e个和2e个。30、AOV网是一种有向无回路的图。31、在一个具有n个顶点的无向完全图中，包含有n*（n-1）/2条边，在一个具有n个顶点的有向完全图中，包含有n*（n-1)条边。32、在快速排序、堆排序、归并排序中，归并排序是稳定的。二、选择题1、关于逻辑结构，以下说法错误的是( B )A.逻辑结构与数据元素本身的形成、内容无关B.逻辑结构与数据元素的相对位置有关C.逻辑结构与所含结点个数无关D.一些表面上很不相同的数据可以有相同的逻辑结构2、对于单链表表示法，以下说法错误的是　 （ C　） A.数据域用于存储线性表的一个数据元素 B.指针域或链域用于存放一个指向本结点所含数据元素的直接后继所在结点的指针 C.所有数据通过指针的链接而组织成单链表 D.NULL称为空指针，它不指向任何结点，只起标志作用3、单链表中，增加头结点的目的是为了 ( C )A.使单链表至少有一个结点 B.标示表结点中首结点的位置C.方便运算的实现 D.说明单链表是线性表的链式存储实现4、线性表若采用链表存储结构时，要求内存中可用存储单元的地址( D)A.必需是联系的 B.部分地址必须是连续的C.一定是不连续的 D.连续不连续都可以5、如果以链表作为栈的存储结构,则退栈操作时 ( C )A.必须判别栈是否满 B.判别栈元素的类型C.必须判别栈是否空 D.