一、单项选择题(共 15 题，每题 2 分，共计 30 分；每题有且仅有一个正确选项)
1. 以下哪些不是属于国家顶级域名的是（）
A..au
B..cn
C.com
D..jp
2. 一棵完全二叉树，共有 1234 个节点，其叶子结点的个数为（）
A.615
B.616
C.617
D.210
3. 已知循环队列空间为 30，队头位置编号为 12，队尾元素下一个空位置编号为 5，则队伍中元素个数为（）
A.22
B.23
C.7
D.8
4. 甲箱中有 200 个螺杆，其中有 160 个 A 型螺杆:乙箱中有 240 个螺母，其中有 180 个 A 型的。现从甲乙两箱中各任取一个，则能配成 A 型螺栓的概率为多少?（）
A.1/20
B.19/20
C.3/5
D.15/16
5. 设二维数组 A 的行下标为 0 至 5，列下标为 1 至 5，F 的每个数据元素均占 2 个字节。在按行存贮的情况下，已知数据元素 A[3][3]的第一个字节是 2019，则 A[4][4]的第一个字节的地址为（）
A.2029
B.2025
C.2027
D.2031
6. 以下哪个不属于应用层的（）
A.HTTP
B.FTP
C.TELNET
D.UDP
7. 计算机的运算速度取决于给定的时间内，它的处理器所能处理的数据量。处理器一次能处理的数据量叫字长。已知 64 位的奔腾处理器一次能处理 64 个信息，相当于（）字节
A.8 个
B.1 个
C.16 个
D.2 个
8.设栈 S 的初始状态为空，现有 5 个元素组成的序列{1，2，3，4, 5}，对该序列在 S 栈上依次进行如下操作(从序列中的 1 开始，出栈后不再进栈):进栈、进栈、进栈、出栈进栈、出栈、进栈。试问出栈的元素序列是（）
A.{5，4，3，2，1}
B.{2，1}
C.{2，3}
D.{3，4}
9. 设循环队列中数组的下标范围是 n,其中头尾指针分别是 f 和 r，则其元素个数是（）
A.r-f
B.r-f+1
C.(r-f) MOD n+1
D.(r-f+n) MOD n
10. 对一个满二叉树，m 个树叶，l 分支结点，n 个结点，则（）
A. n=l+m
B. B.l+m=2n
C. C.m=l-1
D. D.n=2l-1
11.假设我们用 d=(a1,a2....,a5), 表示无向图 G 的 5 个顶点的度数，下面给出的哪组 d 值合理
（）。
A.{2，2，2，2，2}
B.{1，2，2，1，1}
C.{3，3，3，2，2}
D.{5，4，3，2，1}
12. 在数据结构中，链表是( )。
A.顺序存储的线性表结构
B.非顺序存储的线性表结构
C.非师序在储的非线性表结构
D.顺序存储的非线性表结构
13.在一个图中，所有顶点的度数之和等于所有边数的( )倍。
A.1/2
B.1
C.2
D.4
14. 一棵树 T 有 2 个度数为 2 的结点、有 1 个度数为 3 的结点、有 3 个度数为 4 的结点，那么树 T 有( )个树叶。
A.14
B.6
C.18
D.7
15.排序算法是稳定的，这句话的意思是关键码相同的记录排序前后相对位置不发生改变，以下排序算法不稳定的是( )。
A.直接插入排序
B.快速排序
C.冒泡排序
D.归并排序
二、阅读程序(程序输入不超过数组或字符串定义的范围;除特殊说明外，判断题 1.5 分，选择题 3 分，共计 40 分)
1. 1.
判断题
1) (1 分)把第 13 行与第 15 行互换位置，结果不会改变。()
A.正确
B.错误
2) (1 分)第 14 行把 if(x[i]<x[j]) 删掉效果一样。()
A.正确
B.错误
3) 第 11 行把 i+1 改成 1，数组 y 每个元素的值增加 1 倍。()
A.正确
B.错误
4) 数组 y[i]中存的是 x[i]在数列中从大到小的次序。()
A.正确
B.错误
选择题 5) 此程序的时间复杂度是( )
A. O(log n)
B. O(n log n)
C. O(n^2)
D. O(n)
6) 此程序如果 n 输入 4，然后输入 2 4 1 3，输出结果是( )。
A.1 2 3 4
B.2 0 3 1
C.4 3 2 1 D.1 3 0 2
2.
判断题
1) (1 分)输入的 x 值应在[0，n-1]的范围内。
A.正确
B.错误
2) (1 分)把第 12 行改成“d[x]++”，不影响程序运行结果。( )
A.正确
B.错误
3) 对任意在[1,9]之间的数 i，都有 d[i-1]<d[i]<d[i+1]。( )
A.正确
B.错误
4) 把第 18 行改成“if(d[i]> d[i-1])”，程序运行的结果会发生改变。( )
A.正确
B.错误
选择题
5) 输人 n=10 后，接着输入:1 3 4 5 2 4 3 5 2 3 后，程序输出结果为( )。
A.1:1 2:2 3:3 4:2 5:3
B.1:1 2:2 3:4 4:7 5:9
C.1:0 2:1 3:2 4:1 5:2
D.1:1 2:2 3:3 4:4 5:5
6) 把程序第 19 行改成“print("%3d" ,i);"后，输入 n=10 后，接首输入: 1 3 4 1 5 4 4 3 5 1 后，程序输出结果为( )。
A.1 2 3 4 5
B.3 2 3 2
C.4 3 4 3 D.1 3 4 5
3.
判断题
1) 程序结束时，a[2]的值一定是数组 a 中的最大值。( )
A.正确
B.错误
2) 第 21 行“m==0”成立时，数组 a[i] (2≤i≤6)从大到小排序: ( )
A.正确
B.错误
3) 程序输出时，a 数组满足:对任意的 2≤i<6，有 a[i]>a[i+1]。( )
A.正确
B.错误
4) 删除第 16 行代码“m=1"程序结果会发生改变。( )
A.正确
B.错误
选择题
5) 程序的输出结果为( )
A.58
B.59
C.61
D.60
6) 此程序的时间复杂度是( )。
A. O(n^3)
B. O(n log n)
C. O(n^2)
D. O(n)
三、完善程序(单选题，每题 3 分，共计 30 分)
1.
菲波拉契数列为 1,1,2,3,5,8,13,21,...其元素产生的规则是前两个数为 1，从第三个数开始每个数等于它前面两个数之和。已知任意一个正整数可以表示为若干个互不相同的菲波拉契数之和。例如:36=21+13+2。
下面的程序是由键盘输入一个正整数 n，输出组成 n 的互不相同的菲波拉契数。算法说明:(1)寻找小于等于 n 的最大菲波拉契数 a，并以 a 作为组成 n 的一个数。
若 n≠a，则以 n-a 作为 n 的新值，重复步骤(1)。若 a=n，则结束。
选择题
1) ①处应填( )
A.a=c;b=a
B.a=b;b=c
C.a==c;b==a
D.n==b;b==c
2) ②处应填( )
A.b==n
B.b
C.a==n
D.a
3) ③处应填( )
A.return c
B.return b
C.return a+b
D.return a
4) ④处应填( )
A.printf(“%4d ”,a);
B.printf(“+%4d”,a);
C.printf(“%4d ”,n);
D.printf(“+%4d”,n);
5) ⑤处应填( )
A. p(a)
B. p(b)
C. p(n-a)D.p(n-b) 2.
现在政府计划在某个区城的城市之间建立高速公路，以使得其中任意两个城市之间都有直接或间接的高速公路相连。费用为每千米为一个单位价格，求最小费用。输入:n(n< = 100，表示城市数目)。
接下来 n 行，每行两个数 xi.yi.表示第个城市的坐标，(单位:千米)。)rp 2 输出:最小费用(保留 2 位小数)。程序如下:
选择题
1) ①处应填( )
A.sqrt((c[i].x-c[i].y)*(c[i].x-c[i].y)+(c[j].x-c[j].y)*(c[i].x-[j].y));
B.sqrt((c[i].x-c[j].x)*(c[j].x-c[i].x)+(c[i].y-c[j].y)*(c[j].y-[i].y));
C.sqrt((c[i].x-c[j].x)*(c[i].x-c[j].x)+(c[i].y-c[j].y)*(c[i].y-[j].y));
D.sqrt((c[i].x-c[i].y)*(c[j].x-c[j].y)+(c[i].x-c[i].y)*(c[j].x-[j].y))
2) ②处应填( )
A. p[i]=1;
B. p[i]=0;
C. p[n-i]=0;
D. p[n-i]=0;
3) ③处应填( )
A. p[i]==0&&d[p[j]][j]< minf
B. p[j]!=0&&d[p[j]][j]
C. p[j]==0‖d[p[j]][j]
D. p[i]!=0‖d[p[j]][j]
4) ④处应填( )
A.k=minf;
B.k=0;
C.k=i;
D.k=j;
5) ⑤处应填( )
A. d[p[j]][j]>d[k][j]
B. d[p[j]][j]
C. d[p[i]][j]>d[k][j]
D. d[p[i]][j]