数据结构（C语言描述）学习通超星期末考试答案章节答案2024年

数据结构（C语言描述）学习通超星期末考试章节答案2024年设长度为n的链队用单循环链表表示,若设头指针,则入队出队操作的时间为何?若只设尾指针呢?

答案:若只设头指针,则入队出队操作的时间为O(n)。若只设尾指针,则入队出队操作的时间为O(1)。循环队列的优点是什么?如何判别它的空和满?

答案:循环队列的优点是:避免假上溢现象发生,不会造成存储空间的浪费。判别循环队列空和满的方法很多,比如:(1)设置标志变量flag,在Q->front==Q->rear的情况下,根据flag的值确定是空还是满。(2)一个元素的空间闲置不用,通过条件(Q->rear+1)%QueueSize==Q->front判断是否队空,Q->front==Q->rear判断是否队满。(3)设置一个计数器用来记录元素的个数,根据其值判断是空还是满。无表头结点的链队列Q为空的条件是()。

答案:Q.front==NULL带头结点的链队列Q为空的条件是()。

答案:Q.front==Q.rear在链队列执行入队操作()。

答案:限制在链表尾进行操作一个队列的入队序列是1,2,3,4,则队列的可能输出序列是()。

答案:1,2,3,4假设以数组A[60]存放循环队列的元素,其头指针是front=47,当前队列有50个元素,则队列的尾指针值为()。

答案:37若用一个大小为6的数组来实现循环队列,且当前rear和front的值分别为0和3时,当从队列中删除一个元素,再加上两个元素后,rear和front的值分别为()。

答案:2和4设循环队列的容量为50(序号从0到49),现经过一系列的入队和出队运算后,有front=29,rear=11,循环队列中的元素个数是()。

答案:32设循环队列的容量为50(序号从0到49),现经过一系列的入队和出队运算后,有front=11,rear=29,循环队列中的元素个数是()。

答案:18设以数组A[0...m-1]存放循环队列,front指向队头元素,rear指向队尾元素的下一个位置,则当前队列中的元素个数为()。

答案:(rear-front+m)%m已知循环队列的存储空间大小为m,队头指针front指向队头元素,队尾指针rear指向队尾元素的下一个位置,则从队列中删除元素时,修改指针的操作是()。

答案:front=(front+1)%m;已知循环队列的存储空间大小为m,队头指针front指向队头元素,队尾指针rear指向队尾元素的下一个位置,则向队列中插入新元素时,修改指针的操作是()。

答案:rear=(rear+1)%m;引起循环队列队尾位置发生变化的操作是()。

答案:入队引起循环队列队头位置发生变化的操作是()。

答案:出队假上溢现象通常出现在()。

答案:顺序队列的入队操作过程中可能发生假上溢现象的存储结构是()。

答案:顺序队列在队列中,允许进行删除操作的一端称为()。

答案:队头在队列中,允许进行插入操作的一端称为()。

答案:队尾队列的特点是()。

答案:只允许在表的一端进行插入,在另一端进行删除下列关于队列的叙述中,错误的是()。

答案:在链队列中进行入队操作时要判断队列是否为满队列操作数据的原则是()。

答案:先进先出在一棵含有n个结点的树中,只有k度结点和叶子结点,求该树中含有的k度结点和叶子结点的个数。

答案:设k度结点和叶子结点的个数分别为nk和n0,则孩子结点总数为n-1=knk,因此,nk=(n-1)/k。又由于n=n0+nk,所以,n0=n-nk=n-(n-1)/k。已知一棵度为m的树中有n1个度为1的结点,n2个度为2的结点,...,nm个度为m的结点,问该树中有多少片叶子?

答案:设该树中的叶子数为n0个。该树中的总结点数为n个,则有:n=n0+n1+n2+…+nm另一方面,1度结点有一个孩子,2度结点有两个孩子,...,m度结点有m个孩子,故树中孩子结点总数是:nl+2•n2+...+m•nm,而树中只有根结点不是任何结点的孩子,故树中的结点总数又可表示为:n=nl+2•n2+...+m•nm+1综合以上两个式子得到:n0=1+0•n1+1•n2+2•n3+...+(m-1)•nm即叶子结点数共有:1+n2+2•n3+...+(m-1)•nm个。在一棵度为3的含有16个结点的树中,度为2的结点个数是2,度为0的结点个数是7,则度为1的结点个数是()。

答案:5在一棵度为3的含有16个结点的树中,度为3的结点个数为2,度为2的结点个数为1,则度为1的结点个数为()。

答案:7在树的集合表示{(x,y)|结点x是结点y的双亲}中,叶结点一定是()。

答案:只在y的位置上出现的结点在树的集合表示{(x,y)|结点x是结点y的双亲}中,根结点一定是()。

答案:只在x的位置上出现的结点树可以用集合{(x,y)|结点x是结点y的双亲}表示,如T={(b,d),(a,b),(c,e),(c,g),(c,f),(a,c),(e,h)},则树T的深度是()。

答案:4树可以用集合{(x,y)|结点x是结点y的双亲}表示,如T={(b,d),(a,b),(c,e),(c,g),(c,f),(a,c),(e,h)},则树T的度是()。

答案:3树可以用集合{(x,y)|结点x是结点y的双亲}表示,如T={(b,d),(a,b),(c,e),(c,g),(c,f),(a,c),(e,h)},则树T的叶结点的个数是()。

答案:4树可以用集合{(x,y)|结点x是结点y的双亲}表示,如T={(b,d),(a,b),(c,e),(c,g),(c,f),(a,c),(e,h)},则树T的根结点是()。

答案:a高度为h的完全二叉树至少有多少个结点?至多有多少个结点?

答案:(1)高度为h的完全二叉树，其前h-1层是满二叉树，第h层只有1个结点时，结点数最少。前h-1层是满二叉树共有2h-1-1个结点，因此，至少有2h-1个结点。(2)高度为h的完全二叉树是满二叉树时，结点数最多。因此，至多有2h-1个结点。一棵含999个结点的完全二叉树的深度为()。

答案:10结点数为20的二叉树最小深度为()。

答案:5结点数为20的二叉树的最大深度为()。

答案:20设完全二叉树有n个结点,则其深度为()。

答案:∟lgn」+1除第一层外,满二叉树中每一层结点个数是上一层结点个数的()。

答案:2倍若一棵二叉树有11个叶子结点,则该二叉树中度为2的结点个数是()。

答案:10三个结点的二叉树共有()种。

答案:5二叉树共有()种基本形态。

答案:5在具有n个结点的二叉链表中,共有()个指针域为空。

答案:n+1在具有n个结点的二叉链表中,共有()个指针域用来指示结点的左、右孩子。

答案:n-1已知一棵完全二叉树中共有768结点,则该树中共有()个非叶子结点。

答案:384已知一棵完全二叉树中共有768结点,则该树中共有()个叶子结点。

答案:384已知一棵完全二叉树中共有768结点,则该树中共有()个2度结点。

答案:383在含有n个结点的完全二叉树中,1度结点的个数至多为()。

答案:1在含有n个结点的完全二叉树中,叶子结点的个数为()。

答案:n-[n/2]设含有n个结点的完全二叉树的结点ki的编号为i(3<2i+1答案:2i+1/star3/origin/8ac0f7c47d21f6f79fd48a2b6030208d.png

答案:ABDECF;先序遍历顺序存储的完全二叉树已知二叉树的先序序列和中序序列分别为ABDEHCFI和DBHEACIF。（1）画出该二叉树的二叉链表存储表示。（

）（2）写出该二叉树的后序序列。（

）

答案:该二叉树的后序序列为：DHEBIFCA已知一棵二叉树的中序序列和后序序列分别为BDCEAFHG和DECBHGFA。（1）请画出此二叉树。（

）（2）给出该二叉树的先序遍历序列。（

）

答案:该二叉树的先序遍历序列为：ABCDEFGH已知一棵二叉树的前序序列和中序序列分别为ABDGHCEFI和GDHBAECIF。(1)请画出此二叉树。（

）(2)给出该二叉树的后序遍历序列。（

）

答案:略;该二叉树的后序遍历序列为：GHDBEIFCA/star3/origin/491a42b1b1e0a2b9ea75f4b4ff824ce3.png

答案:RNL遍历序列为:FCEABD已知某二叉树的后序遍历序列是dabec,中序遍历序列是deabc,它的前序遍历序列是()。

答案:cedba已知二叉树的()不能唯一确定一棵二叉树。

答案:先序序列和后序序列在含有3个结点a,b,c的二叉树中,前序序列为abc且后序序列为cba的二叉树有()棵。

答案:4在任意一棵二叉树的前序序列和后序序列中,各叶子之间的相对次序关系()。

答案:都相同若一棵二叉树的后序遍历序列与中序遍历序列相同,则该二叉树可能的形状是()。

答案:树中非叶结点均只有左子树若一棵二叉树的前序遍历序列与中序遍历序列相同,则该二叉树可能的形状是()。

答案:树中非叶结点均只有右子树若一棵二叉树的前序遍历序列与后序遍历序列相同,则该二叉树可能的形状是()。

答案:树中只有一个根结点对含有()个结点的非空二叉树,采用任何一种遍历方式,其结点访问序列均相同。

答案:1/star3/origin/b10a192fe6326825429fcf4297b63c39.png

答案:DHEBFJIGCAn个顶点的非强连通图中至多含有()个强连通分量。

答案:nn个顶点的非强连通图中至少含有()个强连通分量。

答案:2n个顶点的强连通图中含有()个强连通分量。

答案:1n个顶点的强连通图中至少含有()条有向边。

答案:nn个顶点的非连通图中至多含有()个连通分量。

答案:nn个顶点的非连通图中至少含有()个连通分量。

答案:2n个顶点的连通图中含有()个连通分量。

答案:1一个具有n个顶点的无向连通图至少有()条边。

答案:n-1连通图是指图中任意两个顶点之间()。

答案:都连通的无向图在无向图中,若从顶点a到顶点b存在(),则称a与b之间是连通的。

答案:一条路径设G=(V,E)是一个图,V'是V的子集,E'是E的子集,如果()则G'=(V',E')为G的子图。

答案:E'中的边所关联的顶点均在V'中且G'也是一个图/star3/origin/ca347fc0792eebaba7a466e2f76dfaa9.png

答案:无向图或有向图设有向图中所有顶点的入