数据结构期末复习题整理.ppt

8、在具有n个单元的循环队列中，队满时共有_个元素。 解答：队列满的约定条件：队列头指针在队列尾指针的下一位置（指环状的下一位置）上。也就是说，队尾的指针永远指向最后一个元素的下一个结点，当队尾指针的下下个元素是对头指针指向的元素的时候，即可断定该队列是满了所以该题答案为：n-1 15、在循环双链表的p所指结点之后插入s所指结点的操作是_,a,b,x,p,s,解答：如图：将s结点插入p所指结点之后，可分为四部 ：s-prior=p; : s-next= p-next; : p-next-prior=s; : p-next=s; 答案即为上面的四部,18、在栈顶指针为HS的链栈中，判定栈空的条件是_,top,base,解答：栈的初始化操作为按设定的厨师分配量进行第一次存储分配，base的值为NULL，则表明栈结构不存在。称 top 为栈顶指针，其初值指向栈底，即 top=base 可作为栈空的标记 所以答案为：HS=base,19、在一个单链表中删除p所指结点但不知p的前一个结点时，应执行以下操作： q=p-next； p-data= p-next-data； p-next=_； free(q)；,p,q,解答：因为是单链表，所以如果删除所在的那个箭头的话，整个链表就断了，就不能找到下一个位置了。所以可以采用另一种方法来实现删除p所指结点，就是将p的下一个结点（这里给他赋值为q）所指的数字放在p所指的结点那里。然后再将q结点删除就可以了。 所以答案为：q-next,/定义一个指针q令他指向p的下一个结点,/将p的下一个结点的数值放在p所指的结点之上,/删除q所指结点,/释放q,20、在一个单链表中的p所指结点之前插入一个s所指结点时，可执行如下操作： s-next=_； p-next=s； t= p-data； p-data=_； s-data=_；,S,P,解答：因为这是一个单链表，需要向p点之前插入一个数字，而单链表只有向后的箭头，而没有向前的箭头，所以不能直接插入，可以采用如下方法：在p所指结点的后面插入一个结点s，然后把p和s所指的结点上面的数字调换位置，即可达到预期的效果。所以答案为： s-next=p-next；/将s结点插入到p结点的后面 p-next=s； t= p-data；/将p所指结点的数字保存在变量 t 上 p-data=s-data；/将s结点数字放在p结点上面 s-data=t； /将变量 t 上面的数字放在s结点上,1.一个长度为n的顺序存储线性表中，向第i个元素（1next Bx = HS-data CHS=HS-next; x = HS-data Dx = HS-data; HS=HS-next,16、在一链队中，设f和r分别为队头和队尾指针，则插入s所指结点的运算是（B） Af-next=s;f=s Br-next =s; r=s Cs-next = r; r =s Ds-next = f; f = s解释：插入元素与队头没有关系 19、在一链队中，设f和r分别为队头和队尾指针，则删除一结点的运算是（ C） Ar=f-next Br=r-next Cf=f-next Df=r-next 删除元素与队尾没有关系 9、向一个栈顶指针为Top的链栈中插入一个s所指结点时，其操作步骤是（B） ATop-next=s Bs-next= Top-next; Top-next=s Cs-next= Top; Top =s Ds-next= Top; Top = Top-next 解答：如图所示：,data,next,top,栈顶,栈底,s,所以答案为： s-next= Top-next; Top-next=s 选B,12容量是10的循环队列的头指针的位置Sq-front= 2，则队列的头元素的位置是（A） A2 B3 C1 D0 13、循环队列的队满条件是（C） A(Sq.rear+1)%maxsize= =(Sq.front+1)%maxsize B(Sq.rear+1)%maxsize= =Sq.front+1 C(Sq.rear+1)%maxsize= =Sq.front DSq.rear = =Sq.front 2、如果进栈元素序列为A，B，C，D，则所有可能得到的出栈序列为多少？ 答案：ABCD,ABDC,ACBD,ACDB,ADCB, BACD,BADC,BCAD,BCDA,BDCA, CBAD,CBDA,CDBA, DCBA 一共有十四种。 6、不带头结点的单链表head为空的判定条件是（A）、带头结点的单链表head为空的判定条件是（B） A、head= =null B、head-next= =null C、head-next= =head D、head! =null 10、判断一个栈ST（最多元素为m0）为空的条件是_ST.front=ST.rear_ 11、判断一个队列QU（最多元素为m0）为空的条件是_QU.front=QU.rear,7.赫夫曼树是访问叶结点的外部路径长（ ） 最短 B. 最长 C. 可变 D. 不定 解答：赫夫曼树又称最优二叉树，他的一个特点就是带权路径长度最短。所以答案为：D,8.以下说法错误的是（ ） A. 赫夫曼树是带权路径长度最短的树，路径上的权值较大的结点离根较近 B. 已知二叉树的前序遍历和后序遍历不能唯一确定这棵树，因为不能确定树的根结点 C. 在前序遍历二叉树的序列中，任何结点的子树的后继结点都是直接跟在该结点之后 D. 若一个二叉树的树叶是某子树的中序遍历序列中的第一个结点，则它必是该子树的后序遍历序列中的第一个结点 解答：A，这句话，是最优二叉树的特点，记下来就好。B，已知二叉树的前序遍历和后序遍历的确不能确定这棵树，但是却不是因为不能确定根节点，相反的，他只能确定根节点，而左右孩子却不能确定，所以不能确定这个树。C，前序遍历是根左右，所以任何结点的子树的后继结点都是直接跟在该结点之后 。D，中序遍历是左根右，后序遍历是左右根，他们第一个都是左，所以，该选项也是正确的。所以答案选:B,9.设森林中有三棵树，第一、二、三棵树的结点个数分别是n1，n2，n3，那么当把森林转换成一棵二叉树后，其根结点的右子树有（ ）个结点 n1 B. n1+ n2 C. n1+ n2+n3 D. n2+n3 解答：森林与二叉树的转换对应关系如下例子；,A,B,C,D,E,F,G,H,I,J,A,B,C,D,E,F,G,H,I,J,森林 树,只要是兄弟就放在右边。只要是孩子就放在左边，图中，AEG是兄弟，所以都放在右边，排成一排。其他的也都是如此排列。 题中问其根节点的右子树有多少结点，其右子树都是根节点在森林中的兄弟或者兄弟的孩子。所以答案为n2+n3，所以选：D,12.二叉树通常有_存储结构和_存储结构两类存储结构。 解答：二叉树的存储结构有：顺序存储和链式存储两部分。所以该题的答案是：顺序、链式 15.有m个叶子结点的赫夫曼树上的结点数是_。 解答：因为赫夫曼树中没有度为1的结点，则一颗又n个叶子结点的赫夫曼树共有2n-1个结点，可以存储在一个大小为2n-1的一维数组中。所以该题的答案为：2m-1 10.设有13个值，用它们组成一棵赫夫曼树，则该赫夫曼树中共有（ ）个结点 解答：该类型的题，公式：2*n-1，即2*13-1=25，也即有13个叶子结点的赫夫曼树中共有（ ）个结点课本P155 6、由树转化得到的二叉树是非空的二叉树，则二叉树形状是 根结点无右子树的二叉树 解答：因为树的根结点是不存在兄弟的，所以由树转化而成的二叉树就不存在右子树,1.设高度为K的二叉树上只有度为0和度为2的结点，则此类二叉树中所包含的结点数至少为（ ） AK+1 B2K C2K-1 D2K+1 解答：这个题不知道该怎么做，但是可以用排除法，因为这个二叉树只有度为0和度为2的结点，所以这个二叉树是最简单的那种，如图所示，若高度为k=2，结点数为3，所 以可以把B，D选项排除。如图所示，若高度 为k=3，则结点数为5，从而把A排除， 答案为：C 5.树最适合用来表示（D） A元素之间无联系的数据 B有序数据元素 C无序数据元素 D元素之间具有分支层次关系的数据 对一棵满二叉树，有m个叶子结点，n个结点，深度为h，则（ ） An=h+m Bn=2h-1 C2n=m+h Dm=n-h 解答：这个题带入数字，是最快最准确的方法了。如图 显然m=2，n=3，h=2.带入ABCD中显然答案为：B,16.观察如图所示的树，回答下列问题。 哪些是H的祖先？ /沿H往上走到根节点所经过的结点都是他的祖先，答案：E,B,A 结点J的兄弟是那些？ /和她同一个双亲的都是兄弟，答案： F,G 树的深度是多少？/就是他的层次 ，答案： 4 树的度是多少？ /某个结点最多有几个孩子，那个数字就是度，答案： 3 结点H和结点J的层次分别是多少？ /答案：4 ,3,A,B,C,D,E,F,G,J,H,I,20.画出如图所示二叉树对应的森林,解答：如图所示,A,B,E,D,H,G,C,F,I,J,找21,第 9 章,5, 9, 3, 4, 6, 2, 8, 7,直接插入： （ ）5, 9, 3, 4, 6, 2, 8, 7 （ ）5, 9, 3, 4, 6, 2, 8, 7 （3）3, 5, 9, 4, 6, 2, 8, 7 （4）3, 4, 5, 9, 6, 2, 8, 7 （6）3, 4, 5, 6, 9, 2, 8, 7 （2）2, 3, 4, 5, 6, 9, 8, 7 （8）2, 3, 4, 5, 6, 8, 9, 7 （7）2, 3, 4, 5, 6, 7, 8, 9,冒泡： 5, 9, 3, 4, 6, 2, 8, 7 5, 3, 4, 6, 2, 8, 7, 9 3, 4, 5, 2, 6, 7, 8, 9 3, 4, 2, 5, 6, 7, 8, 9 3, 2, 4, 5, 6, 7, 8