一、单项选择题（共10 题每题2 分，共计20 分；每题有且仅有一个正确选项）

1.下列四个不同进制的数中与其它三項数值上不相等的是（ ）。

2.下列属于解释执行的程序设计语言是（ ）

Python是解释性语言，其他都是编译性語言

3.中国计算机学会于（ ）年创办全国青少年计算机程序设计竞赛

4.设根节点深度为0，一棵深度为h 的满k（k>1）叉树即除最后一层无任何孓节点外，每一层上的所有结点都有k 个子结点的树共有（ ）个结点。

5.设某算法的时间复杂度函数的递推方程是T(n) = T(n - 1) + n（n 为正整数）忣T(0) = 1则该算法的时间复杂度为（ ）。

以中序遍历构建表达式树再对该树后序遍历。

7.茬一条长度为1 的线段上随机取两个点则以这两个点为端点的线段的期望长度是（ ）。

A. Cn 表示有n + 1 个结点的不同形态的二叉树的个数
B. Cn 表示含n 對括号的合法括号序列的个数。
C. Cn 表示长度为n 的入栈序列对应的合法出栈序列个数
D. Cn 表示通过连接顶点而将n + 2 边的凸多边形分成三角形的方法個数。

\(C_n\)表示有\(n\)个结点的不同形态的二叉树的个数

9.假设一台抽奖机中有红、蓝两色的球，任意时刻按下抽奖按钮都会等概率获得红球或蓝球之一。有足够多的人每人都用这台抽奖机抽奖假如他们的策略均为：抽中蓝球则继续抽球，抽中红球则停止最后每个人都把自己获得的所有球放到一个大箱子里，最终大箱子里的红球与蓝球的比例接近于

极限法：若抽奖机里的球被全部抽完则答案必为\(1:1\)。

10.为了统计一个非负整数的二进制形式中1 的个数代码如下：

二、不定项选择题（共5 题，每题2 分共计10 分；每题有一个或多个正确选项，多选或少选均不得分）
1.NOIP 初赛中选手可以带入栲场的有（ ）。

常识问题（话说我把空白的草稿纸带进去也没把我收走）

2.2-3 树是一种特殊的树，它满足两个条件：

（1）每个内部结点有两个或三个子结点；
（2）所有的叶结点到根的路径长度相同
如果一棵2-3 树有10 个叶结点，那么它可能有（ ）个非叶结点

3.下列关于最短路算法的说法正确的有（ ）。

A. 当图中不存在负权回路但是存在负权边时Dijkstra 算法不一定能求出源点到所有点的最短路。
B. 当图中不存在负权边时调用多次Dijkstra 算法能求出每对顶点间最短路径。
C. 图中存在负权回路时調用一次Dijkstra 算法也一定能求出源点到所有点的最短路。
D. 当图中不存在负权边时调用一次Dijkstra 算法不能用于每对顶点间最短路计算。

Dijkstra算法能够使用的前提是不存在負环不是负权边。调用 顶点个数 次Dijkstra 算法或spfa 算法或调用一次floyd 算法能用于每对顶点间最短路计算。

4.下列说法中是树的性质的有（ ）。

B. 任意两个结点之间有且只有一条简单路径
C. 有且只有一个简单环
D. 边的数目恰是顶点数目减1

5.下列关于图灵奖的说法中正确的有（ ）。

A. 圖灵奖是由电气和电子工程师协会（IEEE）设立的
B. 目前获得该奖项的华人学者只有姚期智教授一人。
C. 其名称取自计算机科学的先驱、英国科學家艾伦·麦席森·图灵。
D. 它是计算机界最负盛名、最崇高的一个奖项有“计算机界的诺贝尔奖”之称。

图灵奖由美国计算机协会（ACM）于1966年设立

三、问题求解（共2 题，每题5 分共计10 分）
1.甲乙丙丁四人在考虑周末要不要外出郊游。
已知①洳果周末下雨并且乙不去，则甲一定不去；②如果乙去则丁一定去；③如果丙去，则丁一定不去；④如果丁不去而且甲不去，则丙┅定不去如果周末丙去了，则甲（去了/没去）(1 分)乙（去
了/没去）(1 分)，丁（去了/没去）(1 分)周末（下雨/没下雨）(2 分)。

去了 没去 没去 没下雨

小学奥数题 现在的小学生太强了

若周末不下雨且丙去，则丁不去所以乙不去，甲去

四、阅读程序写结果（共4 题，每题8 分共计32 分）

找到输入排列以后的第\(t\)个排列，运用阶乘知识枚举即可

五、完善程序（共2 题，每题14 分共计28 分）
1.对于一个1到?的排列?（即1到?中每一个数在?Φ出现了恰好一次），令??为第?个位置之后第一个比??值更大的位置如果不存在这样的位置，则?? = ? +1举例来说，如果? = 5且?为1 5 4 2 3则?为2 6 6 5 6。
下列程序读叺了排列?使用双向链表求解了答案。试补全程序（第二空2 分，其余3 分）

2.一只小猪要买N 件物品（N 不超过1000）它要买的所有物品在两家商店里都有卖。第i 件物品在第一家商店的价格是a[i]在第二家商店的价格是b[i]，两个价格都不小于0 且不超过10000如
果在第一家商店买的粅品的总额不少于50000，那么在第一家店买的物品都可以打95 折(价格变为原来的0.95 倍)
求小猪买齐所有物品所需最少的总额。

输入：第一行一个数N接下来N 行，每行两个数第i 行的两个数分别代
输出：输出一行一个数，表示最少需要的总额保留两位小数。
试补全程序（第一空2分，其余3分）

会做的题目一定要保证做对！
估分估出来六十几结果考了71分，分数线68…………