nbhkdz.com冰点文库

NOIP竞赛培训第四讲


Review:数据结构——树
0.8 0.7

0.6

0.5

0.4

0.3

0.2

0.1

0 1 2 3 4 5 6 7 8 9 10

Review:数据结构——树
【1】一个包

含n个分支结点(非叶结 点)的非空二叉树,它的叶结点数目最多 为()。 ? A. 2n + 1 B. 2n-1 C. n-1 D. n+1
?

Review:数据结构——树
【2】表达式a*(b+c)-d的后缀表达式是 ()。 ? A. abcd*+- B. abc+*dC. abc*+d- D. - + * abcd
?

Review:数据结构——树
【3】如果树根算第一层,那么一棵n层 的二叉树最多有()个结点。 ? A. 2n-1 B.2n C. 2n+1 D. 2n+1
?

Review:数据结构——树
【4】前缀表达式 “+ 3 * 2 + 5 12”的值 是()。 ? A. 23 B. 25 C. 37 D.65
?

Review:数据结构——树
【5】一棵二叉树的前序遍历序列是 ABCDEFG,后序遍历是CBFEGDA,则 根结点的左子树的结点个数可能是()。 ? A. 2 B. 3 C. 4 D. 5
?

Review:数据结构——树
【6】已知7个节点的二叉树的先根遍历 是1 2 4 5 6 3 7(数字为节点的编号,以 下同),中根遍历是4 2 6 5 1 7 3,则该 二叉树的后根遍历是( )。 ? A.4 6 5 2 7 3 1 B .4 6 5 2137 ? C.4 2 3 1 5 4 7 D .4 6 5 3172
?

Review:数据结构——树
【7】高度为 n 的均衡的二叉树是指:如 果去掉叶结点及相应的树枝,它应该是高 度为 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】完全二叉树的结点个数为11,则它 的叶结点个数为( )。 A. 4 B.3 C.5 D. 2 E. 6

Review:数据结构——树
【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. E
?

New:简单的排序算法
插入排序 ? 冒泡排序 ? 选择排序
?

2 New:插入排序-O(n )
?

稳定

void Insertsort (int data[], int n) ? { int i,j; ? for(i=2;i<=n;i++){
○ if(data[i]<data[i-1]){ ? data[0]=data[i];data[i]=data[i-1]; ? for (j=i-2; data[j]>data[0];j--) data[j+1]=data[j]; ? data[j+1]=data[0];

○}

?}

?

}

2 New:冒泡排序-O(n )
?

稳定

? ? ? ? ? ? ? ? ? ? ? ?

void Bubblesort (int data[], int n) { int i,j,tag; for(i=1,tag=1;tag==1&&i<n;i++){ tag=0; for(j=1;j<=n-i;j++) if(data[j]>data[j+1]){ data[0]=data[j]; data[j]=data[j+1]; data[j+1]=data[0]; tag=1; } } }

2 New:选择排序-O(n )
?

不稳定

?
? ? ? ? ? ? ? ? ?

void Selectsort (int data[], int n) { int i,j,k; for(i=1;i<n;i++){ k=i; for(j=i+1;j<=n;j++) if(data[j]<data[k]) k=j; if(k!=i){ data[0]=data[i];data[i]=data[k];data[k]=data[0]; } } }

Exeercise:闯关游戏
?

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

?

?
? ?

? ?
? ? ?

?

样例输入 10 20 40 32 67 40 20 89 300 400 15 样例输出 8 15 20 32 40 67 89 300 400

End


noip普及组复赛入门训练4(答案)

noip普及组复赛入门训练4(答案)_学科竞赛_初中教育_...第一行包含 10 个 100 到 200 之间 (包括 100 ...输入一个四位数数字(全相同的除外) ,均能得到 ...

竞赛辅导教案

noip初赛noip初赛隐藏>> 信息学奥林匹克竞赛辅导讲稿 目第一讲 第二讲 第三讲 第四讲 第五讲 第六讲 第七讲 第八讲 第九讲 第十讲 第十一讲 第十二讲 ...

NOIP2015普及组解题报告

NOIP2015普及组解题报告_学科竞赛_初中教育_教育专区。NOIP2015解题报告,by贴吧id...(第四、五、六天) ,每天收到三枚金币;之后四天,每天收到四 枚金币,以此类...

noip2015普及组解题报告

noip2015普及组解题报告_学科竞赛_初中教育_教育专区。noip2015普及组解题报告 ...(第四、五、六天) ,每天收到三枚金币;之后 四天(第七、八、九、十天) ,...

2014noip复赛模拟练习16(答案)

2014noip复赛模拟练习16(答案)_学科竞赛_初中教育_教育专区。喜羊羊运动会——...第一天 第二天 第三天 第四天 规定训练时间 14:30 8:00 13:10 7:25 到场...

NOIP2015普及组初赛试题及答案(Pascal)

NOIP2015普及组初赛试题及答案(Pascal)_学科竞赛_初中教育_教育专区。第二十一...输出: 第 5 页共 8 页 四. 完善程序 (前 4 空,每空 3 分,后 4 空...

2014noip复赛模拟练习18(答案)

2014noip复赛模拟练习18(答案)_学科竞赛_初中教育_教育...第二行 n 个数,从左到右表示这 n 个女生左边...6. 键盘输入一个含有括号的四则运算表达式,可能含有...

NOIP2015普及组初赛试题及答案(Pascal)

NOIP2015普及组初赛试题及答案(Pascal)_学科竞赛_初中教育_教育专区。第二十一...输出: 第 5 页共 8 页 四. 完善程序 (前 4 空,每空 3 分,后 4 空...

2014noip复赛模拟练习20(答案)

2014noip复赛模拟练习20(答案)_学科竞赛_初中教育_教育...在球桌上,台面四角以及两 长边中心位置各有一个...第一行是 N,M (N<=100000,M<=10000) , N ...

NOIP2015普及组复赛解题报告

NOIP2015普及组复赛解题报告_学科竞赛_初中教育_教育专区。NOIP2015普及组复赛解题...(第四、五、六天) ,每天收到三枚金币;之后四天(第七、八、九、十天) ,...