数据结构练习题2练习题一、填空题1、__数据项_是数据的最小单位，_数据元素_____是讨论数据结构时涉及的最小数据单位。2、设一棵完全二叉树具有100个结点，则此完全二叉树有49个度为2的结点。3、在用于表示有向图的邻接矩阵中，对第i列的元素进行累加，可得到第i个顶点的__入____度。4、已知一棵度为3的树有2个度为1的结点，3个度为2的结点，4个度为3的结点，则该树中有_____12___个叶子的结点。根据二叉树性质3的证明过程，有n0=n2+2n3+1。5、有一个长度为20的有序表采用二分查找方法进行查找，共有＿4＿＿＿＿＿个元素的查找长度为3。6、对于双向链表，在两个结点之间插入一个新结点需要修20161/18改的指针共_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个字节。20162/1813、模式串P=‘abaabcac’的next函数值序列为_01122312_______。14、任意连通图的连通分量只有一个，即是其自身。15、栈的特性是后进先出。16、串的长度是串中所包含的字符数。17、如果一个有向图中没有＿回路＿＿＿＿＿，则该图的全部顶点可能排成一个拓扑序列。18、在具有n个叶子结点的哈夫曼树中，分支结点总数为n-1。19、在线性表的散列存储中，装填因子?又称为装填系数，若用m表示散列表的长度，n表示待散列存储的元素的个数，则?等于____n/m____。20、排序的主要目的是为了以后对已排序的数据元素进行查找。21、对于一个具有n个结点的单链表，在已知的结点*p后插入一个新结点的时间复杂度为___O(1)_____,在给定值为x的结点后插入一个新结点的时间复杂度为_O_______。22、线性表L=用数组表示，假定删除表中任一元素的概率相同，则删除一个元素平均需要移动元素的个数是_表长的一半_______。23、两个栈共享空间时栈满的条件_____top2=top1+1__。20163/1824、深度为H的完全二叉树至少有_2^__个结点；至多有_2^H-1__个结点；H和结点总数N之间的关系是H=log2N+1__。25、在有序表A[1?20]中，按二分查找方法进行查找，查找长度为4的元素的下标从小到大依次是_______136811131619___。26、设查找表中有100个元素，如果用二分法查找方法查找数据元素X，则最多需要比较_____7___次就可以断定数据元素X是否在查找表中。27、根据初始关键字序列(17，25，3，39，12)建立的二叉排序树的高度为___3_________。28、设有一个n阶的下三角矩阵A，如果按照行的顺序将下三角矩阵中的元素存放在n(n+1)个连续的存储单元中，则A[i][j]与A[0][0]之间有_______个数据元素。29、栈的插入和删除只能在栈的栈顶进行，后进栈的元素必定先出栈，所以又把栈称为__________表；队列的插入和删除运算分别在队列的两端进行，先进队列的元素必定先出队列，所以又把队列称为_________表。30、设一棵完全二叉树的顺序存储结构中存储数据元素为ABCDEF，则该二叉树的前序遍历序列为___________，中序遍历序列为___________，后序遍历序列为___________。31、设一棵完全二叉树有128个结点，则该完全二叉20164/18树的深度为________，有__________个叶子结点。32、设有向图G的存储结构用邻接矩阵A来表示，则A中第i行中所有非零元素个数之和等于顶点i的________，第i列中所有