数据结构期末复习试题.doc

. . . 练习题： 填空题 1、元素项是数据的最小单位，数据元素是讨论数据结构时涉及的最小数据单位。 2、设一棵完全二叉树具有100个结点，则此完全二叉树有49个度为2的结点。 3、在用于表示有向图的邻接矩阵中，对第i列的元素进行累加，可得到第i个顶点的出度。 4、已知一棵度为3的树有2个度为1的结点，3个度为2的结点，4个度为3的结点，则该树中有12个叶子的结点。 n=n0+n1+n2+…+nm (1)又有除根结点外,树中其他结点都有双亲结点,且是唯一的(由树中的分支表示),所以,有双亲的结点数为：n-1=0*n0+1*n1+2*n2+…+m*nm (2)联立(1)(2)方程组可得：叶子数为：n0=1+0*n1+1*n2+2*n3+...+(m-1)*nm 5、有一个长度为20的有序表采用二分查找方法进行查找，共有4个元素的查找长度为3。 6、对于双向链表，在两个结点之间插入一个新结点需要修改的指针共4个。 删除一个结点需要修改的指针共2个。 7、已知广义表LS=(a,(b,c,d),e)，它的深度是2，长度是3。 8、循环队列的引入是为了克服假溢出。 9、表达式a*(b+c)-d/f的后缀表达式是abc+*df/-。 10、数据结构中评价算法的两个重要指标是时间复杂度和空间复杂度。 11、设r指向单链表的最后一个结点，要在最后一个结点之后插入s所指的结点，需执行的三条语句是r-next=s; r=s; r-next=null; 12、设有一个空栈，栈顶指针为1000H(十六进制)，现有输入序列为1，2，3，4，5，经过PUSH,PUSH,POP,PUSH,POP,PUSH,PUSH之后，输出序列是23，而栈顶指针值是1012_H。设栈为顺序栈，每个元素占4个字节。 13、模式串P=‘abaabcac’的next函数值序列 14、任意连通图的连通分量只有一个，即是自身。 15、栈的特性是先进后出。 16、串的长度是包含的元素个数。 17、如果一个有向图中没有回路，则该图的全部顶点可能排成一个拓扑序列。 18、在具有n个叶子结点的哈夫曼树中，分支结点总数为n-1。176 19、在线性表的散列存储中，装填因子a又称为装填系数，若用m表示散列表的长度，n表示待散列存储的元素的个数，则a等于n/m。 20、排序的主要目的是为了以后对已排序的数据元素进行 查找。 21、对于一个具有n个结点的单链表，在已知的结点*p后插入一个新结点的时间复杂度为O(1),在给定值为x的结点后插入一个新结点的时间复杂度为O(n)。 22、线性表L=（a1,a2,…,an）用数组表示，假定删除表中任一元素的概率相同，则删除一个元素平均需要移动元素的个数是 n/2。 23、两个栈共享空间时栈满的条件top1=top2-1。 24、深度为H 的完全二叉树至少有H个结点；至多有2^H-1个结点；H和结点总数N之间的关系是 H=[log2n]+1 。150 25、在有序表A[1…20]中，按二分查找方法进行查找，查找长度为4的元素的下标从小到大依次是1 3 6 8 11 13 16 19 26、设查找表中有100个元素，如果用二分法查找方法查找数据元素X，则最多需要比较7次就可以断定数据元素X是否在查找表中。 26、数据结构被形式地定义为（D,R），其中D和R 的含义是（D是数据元素的集合，R是数据关系的集合）。数据的逻辑结构包括哪四种类型（集合类型，线性结构，树形结构，图状结构）。从存储结构的概念上讲，顺序表是线性表的（顺序存储结构），链表是（链式存储结构）。 27、根据初始关键字序列(17，25，3，39，12)建立的二叉排序树的高度为3。 27、算法的五个重要特性有哪些。（有穷性、确定性、可行性、输入、输出）。抽象数据类型是指一个（数学模型）以及定义在该模型上的（一组操作）。 28、设有一个n阶的下三角矩阵A，如果按照行的顺序将下三角矩阵中的元素（包括对角上元素）存放在n(n+1)个连续的存储单元中，则A[i][j]与A[0][0]之间有((i＋１)＊ｉ／２＋ｊ个数据元素。 栈的插入和删除只能在栈的栈顶进行，后进栈的元素必定先出栈，所以又把栈称为FILO；队列的插入和删除运算分别在队列的两端进行，先进队列的元素必定先出队列，所以又把队列称为FIFO表。 设一棵完全二叉树的顺序存储结构中存储数据元素为ABCDEF，则该二叉树的前序遍历序列为ABDEF，中序遍历序列为DBEAFC，后序遍历序列为DEBFCA。 如果以链栈为存储结构，则出栈操作时(必须判别栈是否空)，与顺序栈相比，链栈有一个明显的优势是(通常不会出现栈满的情况)。 循环队列采用数组data[1．．n]来存储元素的值，并用fro