NOIP竞赛培训第四讲

1、Review：数据结构树00.10.20.30.40.50.60.70.80.912345678910Review：数据结构树【1】一个包含n个分支结点（非叶结点）的非空二叉树，它的叶结点数目最多为（）。A 2n + 1 B 2n-1 C n-1 D n+1 Review：数据结构树【2】表达式a*(b+c)-d的后缀表达式是（）。A abcd*+- B abc+*d- C abc*+d- D - + * abcdReview：数据结构树【3】如果树根算第一层，那么一棵n层的二叉树最多有（）个结点。A 2n-1 B2n C 2n+1 D 2n+1Review：数据结构树【4】前缀表达式 “+

2、3 * 2 + 5 12”的值是（）。A 23 B 25 C 37 D65Review：数据结构树【5】一棵二叉树的前序遍历序列是ABCDEFG，后序遍历是CBFEGDA，则根结点的左子树的结点个数可能是（）。A 2 B 3 C 4 D 5Review：数据结构树【6】已知7个节点的二叉树的先根遍历是1 2 4 5 6 3 7（数字为节点的编号，以下同），中根遍历是4 2 6 5 1 7 3，则该二叉树的后根遍历是（ ）。A4 6 5 2 7 3 1 B4 6 5 2 1 3 7 C4 2 3 1 5 4 7 D4 6 5 3 1 7 2Review：数据结构树【7】高度为 n 的均衡的二叉树

3、是指：如果去掉叶结点及相应的树枝，它应该是高度为 n-1 的满二叉树。在这里，树高等于叶结点的最大深度，根结点的深度为 0，如果某个均衡的二叉树共有 2381 个结点，则该树的树高为（ ）。 A. 10 B. 11 C. 12 D. 13 Review：数据结构树【8】已知 6 个结点的二叉树的先根遍历是 1 2 3 4 5 6（数字为结点的编号，以下同），后根遍历是3 2 5 6 4 1，则该二叉树的可能的中根遍历是（ ） A. 3 2 1 4 6 5 B. 3 2 1 5 4 6 C. 2 1 3 5 4 6 D. 2 3 1 4 6 5 Review：数据结构树【9】完全二叉树的结点个数

4、为11，则它的叶结点个数为（ ）。A. 4 B.3 C.5 D. 2 E. 6Review：数据结构树【10】二叉树T的宽度优先遍历序列为A B C D E F G H I，已知A是C的父结点，D 是G 的父结点，F 是I 的父结点，树中所有结点的最大深度为3（根结点深度设为0），可知F的父结点是（ ）。A. 无法确定 B. B C. C D. D E. ENew：简单的排序算法插入排序冒泡排序选择排序New：插入排序-O(n2) 稳定void Insertsort (int data, int n) int i,j; for(i=2;i=n;i+)if(dataidata0;j-) data

5、j+1=dataj;dataj+1=data0;New：冒泡排序-O(n2) 稳定void Bubblesort (int data, int n) int i,j,tag; for(i=1,tag=1;tag=1∈i+)tag=0;for(j=1;jdataj+1) data0=dataj; dataj=dataj+1; dataj+1=data0;tag=1; New：选择排序-O(n2) 不稳定void Selectsort (int data, int n) int i,j,k; for(i=1;in;i+) k=i; for(j=i+1;j=n;j+) if(dataj

6、datak) k=j; if(k!=i) data0=datai;datai=datak;datak=data0; Exeercise：闯关游戏XX同学找到了一个闯关游戏，共要完成N关，每关的编号是个1到1000关之间的随机关卡（N100），对于其中重复的，只需通过一次即可，把其余相同的关卡数去掉，不同的数对应着不同的关卡号。然后再把这些数从小到大排序，按照排好的顺序依次进行闯关。XX同学想用计算机程序协助他完成“去重”与“排序”的工作。输入格式：输入有2行，第1行为1个正整数，表示所生成的要闯关的关卡个数：N第2行有N个用空格隔开的正整数，为所产生的关卡号码。输出格式输出也是2行，第1行为1个正整数M，表示不相同的关卡的个数。第2行为M个