数据结构期末复习题整理PPT课件

1、20、在一个单链表中的p所指结点之前插入一个s所指结点时，可执行如下操作： s-next=_； p-next=s； t= p-data； p-data=_； s-data=_； SP解答：解答：因为这是一个单链表，需要向p点之前插入一个数字，而单链表只有向后的箭头，而没有向前的箭头，所以不能直接插入，可以采用如下方法：在p所指结点的后面插入一个结点s，然后把p和s所指的结点上面的数字调换位置，即可达到预期的效果。所以答案为： s-next=p-next；/将s结点插入到p结点的后面 p-next=s； t= p-data；/将p所指结点的数字保存在变量 t 上 p-data=s-data；/将

2、s结点数字放在p结点上面 s-data=t； /将变量 t 上面的数字放在s结点上第1页/共14页1.一个长度为n的顺序存储线性表中，向第i个元素（1=i=n+1）之前插入一个新元素时，需要从后向前依次后移（ ）个元素An-i Bn-i+1 Cn-i-1 DI2.一个长度为n的顺序存储线性表中，删除第i个元素（1=inext Bx = HS-data CHS=HS-next; x = HS-data Dx = HS-data; HS=HS-next第2页/共14页16、在一链队中，设f和r分别为队头和队尾指针，则插入s所指结点的运算是（B）Af-next=s;f=s Br-next =s; r

3、=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解答：如图所示：datanexttop栈顶栈底s所以答案为：

4、 s-next= Top-next; Top-next=s 选B第3页/共14页12容量是10的循环队列的头指针的位置Sq-front= 2，则队列的头元素的位置是（A）A2 B3 C1 D013、循环队列的队满条件是（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.front2、如果进栈元素序列为A，B，C，D，则所有可能得到的出栈序列为多少？答案：ABCD,ABDC,ACBD,ACDB,

5、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! =null10、判断一个栈ST（最多元素为m0）为空的条件是_ST.front=ST.rear_ 11、判断一个队列QU（最多元素为m0）为空的条件是_QU.front=QU.rear第4页/共14页7.赫夫曼树是访问叶结点的外部路径长（ ）A. 最短 B.

6、最长 C. 可变 D. 不定解答：赫夫曼树又称最优二叉树，他的一个特点就是带权路径长度最短。所以答案为：D8.以下说法错误的是（ ）A. 赫夫曼树是带权路径长度最短的树，路径上的权值较大的结点离根较近 B. 已知二叉树的前序遍历和后序遍历不能唯一确定这棵树，因为不能确定树的根结点 C. 在前序遍历二叉树的序列中，任何结点的子树的后继结点都是直接跟在该结点之后 D. 若一个二叉树的树叶是某子树的中序遍历序列中的第一个结点，则它必是该子树的后序遍历序列中的第一个结点解答：A，这句话，是最优二叉树的特点，记下来就好。B，已知二叉树的前序遍历和后序遍历的确不能确定这棵树，但是却不是因为不能确定根节点，

7、相反的，他只能确定根节点，而左右孩子却不能确定，所以不能确定这个树。C，前序遍历是根左右，所以任何结点的子树的后继结点都是直接跟在该结点之后 。D，中序遍历是左根右，后序遍历是左右根，他们第一个都是左，所以，该选项也是正确的。所以答案选:B第5页/共14页9.设森林中有三棵树，第一、二、三棵树的结点个数分别是n1，n2，n3，那么当把森林转换成一棵二叉树后，其根结点的右子树有（ ）个结点A. n1 B. n1+ n2 C. n1+ n2+n3 D. n2+n3解答：森林与二叉树的转换对应关系如下例子；ABCDEFGHIJABCDEFGHIJ森林 树只要是兄弟就放在右边。只要是孩子就放在左边，图

8、中，AEG是兄弟，所以都放在右边，排成一排。其他的也都是如此排列。题中问其根节点的右子树有多少结点，其右子树都是根节点在森林中的兄弟或者兄弟的孩子。所以答案为n2+n3，所以选：D第6页/共14页12.二叉树通常有_存储结构和_存储结构两类存储结构。解答：二叉树的存储结构有：顺序存储和链式存储两部分。所以该题的答案是：顺序、链式15.有m个叶子结点的赫夫曼树上的结点数是_。 解答：因为赫夫曼树中没有度为1的结点，则一颗又n个叶子结点的赫夫曼树共有2n-1个结点，可以存储在一个大小为2n-1的一维数组中。所以该题的答案为：2m-110.设有13个值，用它们组成一棵赫夫曼树，则该赫夫曼树中共有（

9、）个结点解答：该类型的题，公式：2*n-1，即2*13-1=25，也即有13个叶子结点的赫夫曼树中共有（ ）个结点课本P1556、由树转化得到的二叉树是非空的二叉树，则二叉树形状是 根结点无右子树的二叉树 解答：因为树的根结点是不存在兄弟的，所以由树转化而成的二叉树就不存在右子树 第7页/共14页1.设高度为K的二叉树上只有度为0和度为2的结点，则此类二叉树中所包含的结点数至少为（ ）AK+1 B2K C2K-1 D2K+1解答：这个题不知道该怎么做，但是可以用排除法，因为这个二叉树只有度为0和度为2的结点，所以这个二叉树是最简单的那种，如图所示，若高度为k=2，结点数为3，所 以可以把B，D

10、选项排除。如图所示，若高度 为k=3，则结点数为5，从而把A排除， 答案为：C5.树最适合用来表示（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第8页/共14页16.观察如图所示的树，回答下列问题。 哪些是H的祖先？ /沿H往上走到根节点所经过的结点都是他的祖先，答案：E,B,A 结点J的兄弟是那些？ /和她同一个双亲的都是

11、兄弟，答案： F,G 树的深度是多少？/就是他的层次 ，答案： 4 树的度是多少？ /某个结点最多有几个孩子，那个数字就是度，答案： 3 结点H和结点J的层次分别是多少？ /答案：4 ,3ABCDEFGJHI第9页/共14页20.画出如图所示二叉树对应的森林解答：如图所示ABEDHGCFIJ第10页/共14页low mid high 5131921375664758088921234567891011找找21high low mid low high mid 第11页/共14页第第 9 章章 排序方法排序方法时间复杂度时间复杂度空间复杂度空间复杂度稳定性稳定性直接插入排序直接插入排序O(n)O

12、(1)稳定稳定折半插入排序折半插入排序O(n)O(1)稳定稳定冒泡排序冒泡排序O(n)O(1)稳定稳定快速排序快速排序O(nlogn) O(n)O(logn)不稳定不稳定简单选择排序简单选择排序O(n)O(1)不稳定不稳定堆排序堆排序O(nlogn)O(1)不稳定不稳定归并排序归并排序O(nlogn)O(n)稳定稳定基数排序基数排序O(d(n+rd)O(rd)第12页/共14页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, 9 2, 3, 4, 5, 6, 7, 8, 9 直接选择：直接选择： 5, 9,