CSP-J/S初赛选择题模拟和

请点击↑关注、收藏，本博客免费为你获取精彩知识分享！有惊喜哟！！

1、在8位二进制补码中，10101010表示的数是十进制下的（B）

A、176 B、-86 C、-85 D、-84

答案解析：补码=反码 1；反码=原码除符号位外各个位取反；原码是和十进制对应的；所以，现将补码10101010转化成原码：符号位不变，减1后得到10011111，然后按位取反得到11100000，最后按权展开求和得到十进制数-86。

2、中缀表达式A-(B C/D)*E的后缀表达式是（D）

A、AB-C D/E

B、ABC D/-E*

C、ABCD/E*±

D、ABCD/ E*-

答案解析：后缀表达式即操作符号在操作数的后面，所以括号内为BCD/ ，再加上括号外的结果为D。

3、若让元素1,2,3,4,5依次进栈，则出栈次序不可能出现（C）的情况

A、5,4,3,2,1 B、2,1,5,4,3 C、4,3,1,2,5 D、1,2,5,4,3

答案解析：栈是先进后出的数据结构，因此，1一定要比2后出栈，所以答案选择C

4、表达式（1 34）5-56/7的后缀表达式为（C）

A、1 345-56/7 B、- 1 34 5/56 7 C 、1 34 556 7/- D、1 34 5 56 7 -*/

5、在n个结点的顺序表中，算法的时间复杂度是O（1）的操作是（A）

A、访问第i个结点（1<=i<=n)和求第i个结点的直接前驱（2<=i<=n)

B、在第i个节点后插入一个新结点（1<=i<=n)

C、删除第i个结点（1<=i<=n)

D、将n个结点从小到大排序

解析：顺序表的特点是可以实现随机存取，也就是存取的时间复杂度为O（1）；而插入、删除比较耗费时间；链表是可以O（1）实现插入删除，存取耗费时间。

6、在以下各项中，（D）不是CPU的组成部分

A、控制器 B、运算器 C、寄存器 D、主板

解析：CPU 包括ＡＢＣ三个选项

7、在下列各项中，只有（C）不是计算机存储容量的常用单位。

A、Byte B 、KB C、UB D、TB

解析:1TB=1024GB；1GB=1024MB；1MB=1024KB，1KB=1024B；1B=8bit

8、ASCII码的含义是（B）

A、二–十进制转换码 B、美国信息交换标准代码

C、数字的二进制编码 D、计算机可处理字符的唯一编码

9、一个完整的计算机系统应包括（B）

A、系统硬件和系统软件 B、硬件系统和软件系统

C、主机和外部设备 D、主机、键盘、显示器和辅助存储器

10、IT的含义是（B）

A、通信技术 B、信息技术 C、网络技术 D、信息学

11、LAN的含义是（B）

A、因特网 B、局域网 C、广域网 D、城域网

12、以下断电后仍能保存数据的有（A）

A、硬盘 B、高速缓存 C、显存 D、RAM

13、在下列关于计算机语言的说法中，正确的有（C）

A、高级语言比汇编语言更高级，是因为它的程序的运行效率更高

B、随着Pascal、C等高级语言的出现，机器语言和汇编语言已经退出历史舞台

C、高级语言比汇编语言程序更容易从一种计算机上移植到另一种计算机上

D、C是一种面向对象的高级计算机语言

14、与十进制1770对应的八进制数（C）

A、3350 B、3351 C、3352 D、3540

解析：可以使用将1770除以8取余后逆向输出，或者将ABCD四个选项按权展开后看哪个是1770.

15、设Ａ＝Ｂ＝True,C=D=False,以下逻辑运算表达式值为假的有（D）。

A、(¬A⋀B)Ⅴ(C⋀DⅤA)

B、¬（（（A⋀B）ⅤC）⋀D）

C、A⋀（BⅤCⅤD）ⅤD

D、（A⋀（DⅤC）⋀B

解析：⋀是同为真才为真；否则为假；而Ⅴ是同为假才为假，否则为真

16、（2070）16 （34）8的结果是（A）

A、（8332）10

B、（208A）16

C、（100000000110）2

D、（20212）8

解析：将其统一化为一个进制后进行计算。

17、微型计算机中，控制器的基本功能是（A）

A、控制机器各个部件协调工作

B、实现算术运算和逻辑运算

C、获取外部信息

D、存放程序和数据

18、在以下各项中，（D）不是操作系统软件。

A、Solaris

B、Linux

C、Windows Vista

D、Sybase

19、设栈S的初始状态为空，元素a,b,c,d,e,f依次入栈S，出栈的序列b,d,f,e,c,a,则栈的容量至少应该是（C）

A、6

B、5

C、4

D、3

解析：b出栈则a，b一定已经入栈，所以栈容量至少为2；d出栈则a,c,d必定入栈,栈容量至少为3；f出栈a,c,e,f必定入栈，栈容量至少为4；

20、设字符串S=“01ympic”，S的非空子串的数目是（A）

A、28 B、29 C、16 D、17

解析：一个字符串的长度为n，则字符串非空子串的个数为n(n 1)/2.

21、递归过程或函数调用时，处理参数和返回地址，通常使用一种称为（D）的数据结构。

A、队列

B、多维数组

C、线性表

D、栈

22、在3232点阵的”字库“中，汉字”北“与”京“的字模占用字节数之和是（B）

A、512

B、256

C、384

D、128

解析：每个字节有8位二进制位，因此3232点阵有3232/8=64字节；一个汉字占用2个字节，所以”北京“两个字占用4个字节，464=256个字节。

23、设X、Y、Z分别代表三进制下的一位数字，若等式XY ZX=XYX在三进制下成立，那么同样在三进制下，等式XYZX=（B）也成立。

A、YXZ

B、ZXY

C、XYZ

D、XZY

解析:三进制只有0,1,2，所以可以暴力枚举等式XY ZX=XYX；10 21=101;则XYZX=10*21=210=ZXY。

24、主存储器的存取速度比中央处理器（CPU）的工作速度慢的多，从而使得后者的效率受到影响。而根据局部性原理，CPU所访问的存储单元通常都趋于聚集在一个较小的连续区域中。于是，为了提高系统整体的执行效率，在ＣＰＵ中引入了（B）

Ａ、寄存器

B、高速缓存

C、闪存

D、外存

25、体育课的铃声响了，同学们都陆续的奔向操场，按老师的要求从高到矮站成一排。每个同学按顺序来到操场时，都从排尾走到排头，找到第一个比自己高的同学，并站在他的后面。这种站队的方法类似于（B）算法。

A、快速排序

B、插入排序

C、冒泡排序

D、归并排序

26、一个正整数在二进制下有100位，则在16进制下有（C）位

A、7

B、13

C、25

D、不能确定

解析:每4位二进制位对应一位16进制位，每3位二进制位对应一位8进制位

27、目前计算机芯片（集成电路）制造的主要原料是（A），它是一种可以在沙子中提炼出的物质。

A、硅

B、铜

C、锗

D、吕

28、（B）是一种先进先出的线性表。

A、栈

B、队列

C、哈希表（散列表）

D、二叉树

29、计算机如果缺少（A），将无法正常启动。

A、内存

B、鼠标

C、U盘

D、摄像头

30、目前个人电脑的（B）市场占有率最靠前的厂商包括Intel、AMD等公司。

A、显示器

B、ＣＰＵ

C、内存

D、鼠标

31、使用冒泡排序对序列进行升序排列，每执行一次交换操作系统将会减少一个逆序对，因此，序列5,4,3,2,1需要执行（C）次操作，才能完成冒泡排序。

A、0

B、5

C、10

D、15

32、无论是ＴＣＰ/TP模型还是OSI模型，都可以视为网络的分层模型，每个网络协议都会被归入某一层中。如果用现实生活中的例子来比喻这些”层“，以下最恰当的是（A）

A、中国公司的经理与波兰公司的经理交互商业文件

B、军队发布命令

C、国际会议中，每个人都与他国地位对等的人直接进行会谈

D、体育比赛中，每一级比赛的优胜者晋级上一级比赛。

33、矢量图（Vector Image)图形文件所占的贮存空间比较小，并且无论如何放大、缩小或旋转等都不会失真，是因为它（B）

A、记录了大量像素块的色彩值来表示图像

B、用点、直线或者多边形等基于数学方程的几何图元来表示图像

C、每个像素点的颜色信息均用适量表示

D、把文件保存在互联网，采用在线浏览器的方式查看图像。

34、如果一个栈初始时为空，且当前栈中的元素从栈底到栈顶依次为a,b,c，另有元素d已经出栈，则可能的入栈顺序是（D）

A、a,d,c,b

B、b,a,c,d

C、a,c,b,d

D、d,a,b,c

35、（C）是目前互联网上常用的E-mail服务协议。

A、HTTP

B、FTP

C、POP3

D、Telnet

解析：SMTP是邮件传输协议，POP3是邮件接收协议

36、蓝牙和Wi-Fi都是（C）设备

A、无线广域网

B、无线城域网

C、无线局域网

D、无线路由器

37、在程序运行过程中，如果递归调用的层数过多，会因为（A）引发错误。

A、系统分配的栈空间溢出

B、系统分配的堆空间溢出

C、系统分配的队列空间溢出

D、系统分配的链表空间溢出

38、二进制数11.01在十进制下是（A）

A、3.25

B、4.125

C、6.25

D、11.125

39、将（2,6,10,17）分别存储到某个地址区间为0-10的哈希表中，如果哈希函数h(x)=(D),将不会产生冲突，其中a mod b表示a除以b的余数。

A、x mod 11

B、x^2 mod 11

C 、(2x) mod 11

D、 mod 11,向下取整

40、在十六进制表示法中，字母A相当于十进制中的（B）

A、9

B、10

C、15

D、16

41、IPv4协议使用32位地址，随着其不断被分配，地址资源日趋枯竭。因此，它正逐渐被使用（D）位地址的IPv6协议所取代。

A、40

B、48

C、64

D、128

42、中国的国家顶级域名是（A）

A、.cn

B、.ch

C、.chn

D、.china

43、1948年，（D）将热力学中的熵引入信息通信领域，标志着信息论研究的开端。

A、冯.诺依曼

B、图灵

C、欧拉

D、克劳德.香农

44、（B）是一种通用的字符编码，它为世界上绝大部分语言设定了统一并且唯一的二进制编码，以满足跨语言、平台的文本交换。目前它已经收录了超过十万个不同字符。

A、ASCII

B、Unicode

C、GBK 2312

D、BIG5

答案解析链接：

45、1TB代表的字节数是（D）

A、2的10次方

B、2的20次方

C、2的30次方

D、2的40次方

46、下列选项中不属于图像格式的是（B）

A、JPEG格式

B、TXT格式

C、GIF格式

D、PNG格式

47、下列各无符号十进制整数中，能用八位二进制表示的数中最大的是（D）

A、296

B、133

C、256

D、199

48、下列几个IP地址中，书写错误的是（C）

A、162.105.135.27

B、192.168.0.1

C、256.256.129.1

D、10.0.0.1

49、计算机届的最高奖是（C）

A、菲尔兹奖

B、诺贝尔奖

C、图灵奖

D、普利策奖

50、在计算机内部用来传送、存储、加工处理的数据或指令都是（A）形式进行的。

A、二进制码

B、八进制码

C、十进制码

D、智能拼音码

51、下列说法正确的是（A）

A、CPU的主要任务是执行数据运算和程序控制

B、存储器具有记忆能力，其中信息任何时候都不会丢失

C、两个显示器屏幕尺寸相同，则它们的分辨率必定相同

D、个人用户只能使用Wifi的方式连接到Internet

52、FTP可以用于（A）

A、远程传输文件

B、发送电子邮件

C、浏览网页

D、网上聊天

53、计算机病毒是（B）

A、通过计算机传播的危害人体健康的一种病毒

B、人为制造的能够侵入计算机系统并给计算机带来故障的程序或指令集合

C、一种由于计算机元器件老化而产生的对生态环境有害的物质

D、利用计算机的海量高速运算能力而研制出来的用于疾病预防的新型病毒

54、下列选项中不属于视频文件格式的是（A）

A、TXT

B、AVI

C、MOV

D、RMVB

55、与二进制小数0.1相等的十六进制数是（A）

A、0.8

B、0.4

C、0.2

D、0.1

56、周末小明和爸爸妈妈三个一起想动手做三道菜。小明负责洗菜、爸爸负责切菜、妈妈负责炒菜。假设每道菜的顺序都是：先洗菜10分钟，然后切菜10分钟，最后炒菜10分钟。那么做一道菜需要30分钟。注意：两道不同的菜的相同步骤不可以同时进行。例如第一道菜和第二道菜不能同时洗，也不能同时切。那么做完三道菜的最短时间需要（C）分钟

A、90

B、60

C、50

D、40

答案解析：此问题是一个贪心问题，保证每一个人尽量不空闲即可达到最短时间做三道菜。洗第一道菜10分钟；切第一道菜，洗第二道菜同时进行，花费10分钟；切第二道菜、洗第三道菜、炒第一道菜同时进行，花费10分钟；切第三道菜、炒第二道菜，花费10分钟；炒第三道菜10分钟；合计50分钟。

57、可以将单个计算机接入到计算机网络中的网络接入通讯设备有（A）

A、网卡

B、光驱

C、鼠标

D、显卡

58、分辨率800600、16位色的位图，存储图像信息所需的空间为（A）

A、937.5KB

B、4218.75KB

C、4320KB

D、2880KB

答案解析：一个图像的存储空间=图像分辨率色彩位数/8B；注意单位要转换成KB，因此要除以1024；80060016/8/1024=937.5KB

59、计算机应用的最早领域是（A）

A、数值计算

B、人工智能

C、机器人

D、过程控制

60、若串s=“copyright”，其子串的个数是（C）

A、72

B、45

C、46

D、36

答案解析：一个串的长度为n，则该串的子串的数目=（1 n)*n/2 1（空串）。

61、在n(n>3)枚硬币中有一枚质量不合格的硬币（质量过轻或质量过重），如果只有一架天平可以用来称重且称重的硬币数没有限制，下面是找出这枚不合格的硬币的算法。请把a-c三行代码补全到算法中。a.A←X∪Y b. A←Z c.n←|A| 算法Coin(A，n)

正确的顺序是(D)

A、b,c,a

B、c,b,a

C、c,a,b

D、a,b,c

62、对于入栈顺序为a,b,c,d,e,f,g的序列，下列（C）不可能是合法的出栈序列。

A、a,b,c,d,e,f,g

B、a,d,c,b,e,g,f

C、a,d,b,c,g,f,e

D、g,f,e,d,c,b,a

答案解析：c肯定要早于b出栈的

63、小明要去南美洲旅游，一共乘坐三趟航班才能到达目的地，其中第一个航班准点的概率是0.9，第2个航班准点的概率为0.8，第3个航班准点的概率为0.9.如果存在第i个（i=1,2)航班晚点，第i 1个航班准点，则小明赶不上第i 1个航班，旅行失败；除了这种情况，其他情况下旅行都能成功。请问小明此次旅行成功的概率是（D）

A、0.5

B、0.648

C、0.72

D、0.74

答案解析：第1、2航班晚点的概率为0.1、0.2；旅行失败情况分两种：第1个航班晚点，第2个正点；第1个航班正点，第2个航班晚点；所以成功的概率=1-失败的概率，则有下面的计算：1−0.1×0.8（情况1）−0.2×0.9（情况2）=1−0.26=0.74。

64、如果开始时计算机处于小写输入状态，现在有一致小老鼠反复按照CapsLock、字母键A、字母键S、字母键D、字母键F的顺序循环按键，即CapsLock、A、S、D、F、CapsLock、A、S、D、F、…，屏幕上输出的第81个字符用字母（A）

A、A

B、S

C、D

D、a

答案解析：第81个字符正好是循环输入CapsLock、A、S、D、F.20遍后的结果，此时键盘恢复到小写状态，然后按下CapsLock、A、S、D、F后第81个字符是字母A.

65、10000以内，与10000互质的正整数有（B）个。

A、2000

B、4000

C、6000

D、8000

答案解析：互质、容斥原理.公约数只有 1 的两个数互质。分解质因数10000 = 2 * 2 * 2 * 2 * 5 * 5 * 5 * 5。能被2整除的有：10000 / 2 = 5000（个）能被5整除的有：10000 / 5 = 2000（个）能被10整除的有：10000 / 10 = 1000（个）

一共有5000 2000 - 1000 = 6000个数不和10000互质，所以和10000互质的正整数有10000 - 6000 = 4000个。

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

A、1:2

B、2:1

C、1:3

D、1:1

答案解析：抽奖的人足够多，确保了红篮球被抽出的概率为1/2；因此，最终抽出的球中红蓝比例为1:1

66、新学期开学了，小胖想减肥，健身教练给小胖制定了两个训练方案。方案一：每次连续跑3公里可以消耗300千卡（耗时半小时）；方案二：每次连续跑5公里可以消耗600千卡（耗时1小时）。小胖每周周一到周四能抽出半小时跑步，周五到周日能抽出一小时跑步。另外，教练建议小胖每周最多跑21公里，否则会损伤膝盖，每周最多通过跑步消耗多少千卡（D）

A、2520

B、2500

C、3000

D、2400

答案解析：周五-周日每天跑1个小时，共跑35=15公里，消耗6003=1800千卡；本周还能跑21-15=6公里，周一到周四选择二天跑半个小时，共跑32=6公里，消耗3002=600千卡，合计消耗1800 600=2400；

68、100以内最大的素数是（C）

A、89

B、93

C、97

D、91

69、319和377的最大公约数是（D）

A、33

B、31

C、27

D、29

答案解析：可以用319和377分别除以选项；或者用短除法求得319和377的最大公约数。

70、一副纸牌除掉大小王有52张牌，四种花色，每种花色13张。假设从这52张牌中随机抽取13张纸牌，则至少（C）张牌的花色一致。

A、2

B、3

C、4

D、5

答案解析：13/4=3…1,说明最多四个花色各三张；余下的1张牌必定重复四个花色之一；则至少有4张花色一样。

71、有一个等比数列，共有奇数项，其中第一项和最后一项分别是2和118098，中间一项是486，请问以下那个数是可能的公比（B）。

A、5

B、3

C、2

D、4

答案解析：等比数列第n项公式为qn=a0qn-1,其中a0=2,则qn=2qn-1=486/2=243,即qn-1=243，则q只能是3

72、下列属于解释执行的程序设计语言是（D）

A、C

B、C

C、Pascal

D、Python

73、当你在网络上缴费购买了一个具有版权的软件时，你获得了这个软件的（C）

A、复制权

B、修改权

C、使用权

D、以上三项都包括

74、百度公司的主营业务与以下哪家公司类似（A）

A、谷歌公司谷歌

B、微软公司Microsoft

C、苹果公司Apple

D、亚马逊公司Amazon

75、英国计算机科学家艾伦.图灵于1950年提出了著名的“图灵测试”，用于判断计算机是否具有智能。“图灵测试”是通过（B）的方法进行判断的。

A、让两台计算机对话

B、让人类与计算机对话

C、给计算机出题

D、让计算机分辨图片

答案解析：智能是人类特有的，所以计算机具有智能，是看其是否具有人类特有的功能。

76、在用浏览器访问网站时，网址前显示的http://是一种（B）

A、服务器种类

B、传输协议

C、文件格式

D、三级域名

77、某班有38名同学，一次数学测验共有两题，答对第一题的有26人，答对第二题的有24人，两题都答对的有17人，则两题都答错的人数是（B）

A、3

B、5

C、6

D、7

答案解析：本题考察的是容斥定理，可以通过画饼图来完成，也可以通过公式来解题：U=38，A∪B=A B-AB=26 24-17=33；则两题都答错的人数为U-A∪B=38-33=5。

78、某科学家做了一项实验，通过向若干只狒狒提供不限量的香蕉和香肠以研究其食性。结果表明，90%的狒狒有进食，其中吃香蕉的狒狒是吃香肠的狒狒数量的3倍，而两种食物都吃的狒狒是只吃香肠的狒狒数量的2/3，则未进食的狒狒是只吃香蕉的狒狒数量的（C）

A、1/5

B、3/10

C、2/13

D、4/15

答案解析：设两种食物都吃的狒狒有2x只，则只吃香肠的有3x只，根据吃香蕉是吃香肠的3倍，可得吃香蕉的有（2x＋3x）×3＝15x只，进食的狒狒共15x＋3x＝18x只，占总数的90%，共计18x÷90%＝20x只狒狒，未进食的有2x只，是只吃香蕉的2/13。

79、在1和2015之间（包括1和2015在内）不能被4,5,6三个数任意一个数整除的数有（A）个

A、1075

B、940

C、1108

D、907

答案解析：容斥定理.4的倍数有2015/4=503；5的倍数有2015/5=403；6的倍数有2015/6=335；4、5的公倍数有2015/20=100；4、6的公倍数有2015/12=167；5、6的公倍数有2015/30=67；4、5、6的公倍数有2015/60=33；2015 -503-403-335 100 167 67 -33 = 1075.

80、某公司组织歌舞比赛，共68人参赛。其中，参加舞蹈比赛的有12人，参加歌唱比赛的有18人，45人什么比赛都没有参加。问其中参加歌唱比赛但不参加舞蹈比赛的有（B）人

A 、9

B、11

C、15

D、17

答案解析：参赛人数=68-45=A（舞蹈人数） B（歌唱人数）-AB=12 18-AB；则AB=7；所以参加歌唱不参加舞蹈人数18-7=11人。

81、二进制数111110000111转化为十六进制数是（B）

A、5FB

B、F87

C、FC

D、F45

答案解析：从右向左，每4位二进制数对应一位十六进制数，计算得B

82、大写字母B的ASCII码为66，那么69对应（C）

A、C

B、D

C、E

D、F

83、分辨率为19201080的真彩色位图图像所占用的存储空间为（A）

A、6075KB

B、4050KB

C、2025KB

D、8100KB

答案解析：图像存储空间=分辨率色彩位数/8/1024KB;1920108024/8/1024=6075KB

84、已知rand()可以生成一个0到32767的随机整数，如果希望得到一个范围在[a,b)的随机整数，a和b均为不超过100的正整数且a<b,那么可形的表达式是（A）

A、(rand()%(b-a)) a

B、(rand()%(b-a 1)) a

C、(rand()%(b-a)) a 1

D、(rand()%(b-a 1)) a 1

答案解析：可以使用具体值来判定，例如a=1,b=5;带入选项计算即可得知答案

85、AI是（B）的英文缩写

A 、Automatic Intelligence

B 、Artificial Intelligence

C、Automatic Information

D、ArtificialInformation

86、系列四个不同进制的数中，与其它三项数值上不相等的是（D）

A、（269）16

B、（617）10

C、（1151）8

D、（1001101011）2

答案解析:从右向左，每3位二进制数对应一位八进制数，可以明显看出CD选项不一样，每四位二进制数对应1位16进制，可以看出D与A不一样；所以断定D与其它三项不相同

87、在一条长度为1的线段上随机取两个点，则以这两个点位为端点的线段的期望长度是（B）

A、1/2

B、1/3

C、2/3

D、3/5

答案解析：因为在长度为1取两个点会将1分为3份，每份期望长度为1/3=1/3。

88、二进制数11 1011 1001 0111和01 0110 1110 1011进行逻辑与运算的结果是（B）

A、01 0010 1000 1011

B、01 0010 1000 0011

C、01 0010 1001 0011

D、01 0010 1000 0001

89、据说古希腊白拉图学院门口立了一块牌子，“不懂几何者禁止入内”。有一天来了一群人，他们都是懂几何的人，那么他们（A）

A、可能会被允许进入

B、一定会被允许进入

C、一定不会被允许进入

D、不可能不被允许进入

90、高度为n的均衡的二叉树是指，如果去掉叶结点及相应的树枝，它应该是高度为n-1的满二叉树。在这里，树高等于叶结点的最大深度，根节点的深度为0，如果某个均衡的二叉树共有2381个结点，则该树的树高为（B）

A、10

B、11

C、12

D、13

答案解析：2381大于211=2048，因此应该是12层高的树，但是根节点深度为0，所以树高为11.

91、关键字序列（8、9、10、4、5、6、20、1、2）只能是系列排序算法中（C）两趟排序后的结果

A、选择排序

B、冒泡排序

C、插入排序

D、快速排序

92、一颗二叉树具有10个度为2的结点，5个度1的结点，则度为0的结点的个数是（B）

A、9

B、11

C、15

D、不能确定

答案解析：画图即可

93、前序遍历序列与中序遍历序列相同的二叉树为（D）

A、根结点无左子树的二叉树

B、根结点无右子树的二叉树

C、只有根结点的二叉树或非叶子结点只有左子树的二叉树

D、只有根结点的二叉树或非叶子结点只有右子树的二叉树

94、关于拓扑排序，下面说法正确的是（D）

A、所有连通的有向图都可以实现拓扑排序

B、对一个图而言，拓扑排序的结果是唯一的

C、拓扑排序中入度为0的结点总会排在入度大于0的结点的前面

D、拓扑排序结果序列中的第一个结点一定是入度为0的点。

95、将2个红球，1个蓝球，1个白球放到10个编号不同的盒子中去，每个盒子最多放一个球。有（B）种放法。

A、5040

B、2520

C、420

D、1260

答案解析：因为盒子编号不同，因此是P102/2P81P71=2520,注意两个红球一样的，所以要除以2哦。

96、已知7个节点的二叉树的先根遍历是1 2 4 5 6 3 7（数字为节点的编号，以下同），中根遍历是4 2 6 5 1 7 3，则二叉树的后根遍历是（A）

A、4 6 5 2 7 3 1

B、4 6 5 2 1 3 7

C、4 2 3 1 5 4 7

D、4 6 5 3 1 7 2

答案解析：根据先根遍历可以确定根为1，则后根遍历最后遍历1，因此答案A

97、全完二叉树的顺序存储方案，是指将完全二叉树的结点从上至下、从左至右依次存放到一个顺序结构的数组中。假定根结点存放在数组的1号位置，则第K号节点的父节点如果存在的话，应当存放在数组的（C）号位置

A、2K

B、2K 1

C、k/2下取整

D、(k 1)/2下取整

答案解析：举一个具体的例子即可，如5个结点的完全二叉树

98、广度优先搜索时，需要用到的数据结构是（B）

A、链表

B、队列

C、栈

D、散列表

99、在使用高级语言编写程序时，一般提到的“空间复杂度”中的“空间”是指（A）

A、程序运行时理论上所占的内存空间

B、程序运行时理论上所占的数组空间

C、程序运行时理论上所占的硬盘空间

D、程序源文件理论上所占的硬盘空间

100、（C）就是把一个复杂的问题分成两个或更多的相同类似的子问题，再把子问题分解成更小的子问题…直到最后的子问题可以简单的直接求解。而原问题的解就是子问题的解的并。

A、动态规划

B、贪心

C、分治

D、搜索

101、地址总线的位数决定了CPU可直接寻址的内存空间大小，例如地址总线为16位，其最大的可寻址空间为64KB。如果地址总线是32位，则理论上最大可寻址的内存空间为（D）

A、128KB

B、1MB

C、1GB

D、4GB

答案解析：地址总线是16位时，最大可寻址空间为216(B)=26KB=64KB；当地址总线是32位时，最大可寻址空间为232(B )=222KB=212MB=22GB=4GB

102、如果对于所有规模为n的输入，一个算法均恰好进行（A）次运算，我们可以说该算法的时间复杂度为O(2n).

A、2(n 1)

B 、3n

C、n*2n

D、2(2n)

103、（A）的平均时间复杂度为O(nlogn)，其中n是待排序的元素个数。

A、快速排序

B、插入排序

C、冒泡排序

D、基数排序

104、T(n)表示某个算法输入规模为n时的运算次数。如果T(1)为常数，且有递归式T(n)=2*T(n/2) 2n,那么T(n)=(B).

A、O(n)

B、O(nlogn)

C、O(n2)

D、O(n2logn)

答案解析：根据主定理T(n) = a×T(n/b) f(n)，f(n)=2n,则f(n)复杂度为O( n^d),d=1;又a=2,b=2，logba=log22==d;所以，T(n) = O(n^d(logn ) ).

105、链表不具有的特点是（B）

A、不必事先估计存储空间

B、可随机访问任一元素

C、插入删除不需要移动元素

D、所需空间与线性表长度成正比

106、在无向图中，所有顶点的度数之和是边数的（C）倍。

A、0.5

B、1

C、2

D、4

107、同时查找2n个数中的最大值和最小值，最少比较次数为（C）

A、3(n-2)/2

B 、4n-2

C 、3n-2

D 、2n-2

108、答案解析：前两个数比较分出大小并记录max/min，用掉一次。后2(n-1)个数两两比较，大的和max比较并更新；小的和min比较并更新。用掉3(n-1)次。

共计3(n-1) 1=3n-2次。

109、某算法的计算时间表示为递推关系式T(n)=T(n-1) n(n为正整数)及T(0)=1，则该算法的时间复杂度为（D）

A、O（logn)

B、O(nlogn)

C、O(n)

D、O(n2)

答案解析：T(n)=T(n-1) n=T(n-2) (n-1) n=T(n-3) (n-2) (n-1) n…；可以推导出T(0) 1 2 … (n-2) (n-1) n=1 1 2 … (n-2) (n-1) n=1 (n 1)*n/2。所以为 O(n²)，选D。

109、线性表若采用链表存储结构，要求内存中可用存储单元地址（D）

A、必须连续

B、部分地址必须连续

C、一定不连续

D、连续不连续均可

110、双向链表中有两个指针域，llink和rlink,分别指向前驱和后继，设p指向链表中的一个结点，q指向一待插入结点，现要求在p前插入q,则正确的插入为（D）

A、p->llink=q;q->rlink=p;p->llink->rlink=q;q->llink=p>llink;

B、q->llink=p->llink; p->llink->rlink=q;q->rlink=p;p->llink=q->rlink;

C、q->rlink=p;p->rlink=q;p->llink->rlink=q;q->rlink=p;

D、p->llink->rlink=q;q->rlink=p;q->llink=p-llink;p->llink=q;

111、有7个一模一样的苹果，放到3个一样的盘子中，一共有（B）种方法。

A、7

B、8

C、21

D、37

答案解析：相当于将7个苹果分成3组，有几种分法。070、016、025、034、115、124、133、223.

112、假设某算法的计算时间表示为递推关系式T(n)=2T(n/4) sqrt(n),T(1)=1，则算法的时间复杂度为©

A、O(n)

B 、O(sqtr(n))

C、O(sqrt(n)logn)

D、O(n^2)

答案解析：根据主定理T(n) = a×T(n/b) f(n)，f(n)=sqrt(n),则f(n)复杂度为O( n^d),d=1/2;又a=2,b=4，logba=log42==d;所以，T(n) = O(n^d(logn ) ).

113、给定含有n个不同的数的数组L=<x1,x2,…xn>.如果L中存在xi(1<i<n)使得x1<x2<…<xi-1xi 1>…xn,则称L是单峰的，并称xi是L的“峰顶”。现在已知L是单峰的，请把a-c三行代码补全到算法中使得算法正确找到L的峰顶。

a.search(k 1,n)

b.search(1,k-1)

c.return L[k]

Search(1,n)

1.k←Ln/2」

2.If L[k]>L[k-1] and L[k]>L[k 1]

3.then

4.else if L[k]>L[k-1] and L[k]<L[k 1]

5.then

6.else

正确的填空顺序是（C）

A.c,a,b

B.c,b,a

C.a,b,c

D.b,a,c

114、向一个栈顶指针为hs的链式栈中插入一个指针s指向的结点时，应执行（B）

A.hs->next = s;

B.s->next = hs;hs=s;

C.s->next=hs->next;hs->next=s;

D.s->next=hs;hs=hs->next;

答案解析：注意结构为栈，而不是链表

115、若某算法的计算时间表示为递推关系是T(N)=2T(N/2) N log N,T(1)=1则该算法的时间复杂度为（C）

A、O(N)

B、O(NlogN)

C、O(N(logN)^2)

D、O(N^2)

答案解析：一共有logn 层， 每一层的时间复杂度是nlogn, 故总的时间复杂度为：O（nlogn*logn） = O(n(logn)^2)

116、由四个不同的点构成的简单无向连通图的个数是（C）

A、32

B、35

C、38

D、41

答案解析：4个不同点构成简单无向连通图，最多有n*（n-1）/2=6 条边（强联通图），最少有n-1=3 条边（树），但注意，不是所有的任选3条边都满足条件，有一种情况是三个点形成一个三角形而孤立一个点，这种情况共有4种

所以 ans=C（6，3）-4 C（6，4） C（6，5） C（6，6）=38。

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

A、(k^(h 1)-1)/(k-1)

B、k^(h-1)

C、k^h

D、(k^(h-1))/(k-1)

答案解析：举一个特殊例子带入选项进行验证即可。例如k=2;h=2的满二叉树有7个节点，符合A的计算公式

118、由四个没有区别的点构成的简单无向连通图的个数是（A）

A、6

B、7

C、8

D、9

答案解析：枚举连通图的边数：三条边的图有两个（单点的并，长为3的路星图；四条边的图有两个（圈和三角形 1条边）；五条边的图有一个（一条边的图的补图）；六条边的图有一个（4个点的完全图）

119、一些数字可以颠倒过来看，例如0,1,8颠倒过来还是本身，6颠倒过来是9,9颠倒过来看还是6，其他数字颠倒过来都不构成数字，类似的一些多位数也是可以颠倒过来看，比如106颠倒过来是901.假设某个城市的车牌只有5位数字组成，每一位都可以取0到9.请问这个城市最多有多少个车牌倒过来恰好还是原来的车牌（A）

A、75

B、100

C、125

D、60

答案解析：中间第三位只能填写0,1,8，第一、二位可以填写0,1,6,8,9；所以只要确定前三位就可以了，后两位由第1,2位决定；因此有553=75种。

120、假设一颗二叉树的后序遍历序列为DGJHEBIFCA,中序遍历序列为DBGEHJACIF,则前序遍历序列为（C）

A、ABCDEFGHIJ

B、ABDEGHJFIC

C、ABDEGHJCFI

D、ABDEGJHCFI

121、由数字1,1,2,4,8,8组成的不同的四位数数的个数是（C）

A、104

B、98

C、102

D、100

答案解析：（2019csp-s）要分情况讨论：(1)只有2个相同的数构成的4位数，1、1、2、4;1、1、2、8;1、1、4、8;1、2、8、8;1、4、8、8;2、4、8、8组成。每种有A(4,4)/A(2,2)=4×3=12(种)共有12×6=72种.(2)4个不同的数构成，只有1、2、4、8组成,有A(4,4)=4×3×2×1=24(种)(3)2个重复的数字构成，只有1、1、8、8,有C(4,2)=6(种)所以,共有72 24 6=102(种)

122、设A和B是两个长为n的有序数组，现在需要将A和B合并成一个排好序的数组，请问在归并算法中，在最坏情况下至少要做多少次比较（A）

A、2n-1

B、2n

C、n^2

D、nlogn

答案解析：考虑2个数组分别是（1,3,5）和（2,4,6），共需比较5次。因为结果数组大小是2n，先从两数组取第一个值比较，小的入结果数组，剩下的和另一个数组的下一个数比较，依次这样，直到一个数组为空。另一个数组剩下的元素直接进结果数组。最坏一个数组空，另一个数组还剩一个元素，比较次数就是2n-1.

123、独根树的高度为1，具有61个结点的完全二叉树的高度为（D）

A、7

B、8

C、5

D、6

答案解析；二叉树结点个数为2n-1。26=64>61,因此树高为6。

124、两公司为召开联欢晚会，分别编排了3个和2个节目，要求同一公司的节目不能连续出场，则安排节目出场顺序的方案共有（A）

A、12

B、18

C、24

D、30

答案解析：3个节目形成2个空，将2个节目进行插空即可。由于节目不同，因此需要排列。A33C22A22=12.

125、下列四个序列中，哪一个是堆（C）

A、75、65、30、15、25、45、20、10

B、75、65、45、10、30、25、20、15

C、75、45、65、30、15、25、20、10

D、75、45、65、10、25、30、20、15

答案解析：堆有大根堆和小根堆之分；看四个选项为大根堆。大根堆的左右孩子都比父节点小，只有c满足。

126、由3个不同结点构成的二叉树一共有几种（C）

A、5

B、6

C、30

D、36

答案解析：3个结点的二叉树有5种形态：根左左、根左右、左根右、根右右、根右左。由于结点不同，因此每种形态有A33=6种；所以答案有5*6=30种。

127、6个小朋友围成一圈做游戏，小华和小明需要挨在一起，问有多少种安排方法（D）

A、720

B、180

C、360

D、48

答案解析：将小华和小明捆绑在一起进行圈排列2*A55/5=48.

128、若要在1000个数中找到最小的10个数，最好采用（D）

A、快速排序

B、希尔排序

C、归并排序

D、堆排序

答案解析：堆排序不需要大量的递归或者多维的暂存数组。这对于数据量非常巨大的序列是合适的。比如超过数百万条记录，因为快速排序，归并排序都使用递归来设计算法，在数据量非常大的时候，可能会发生堆栈溢出错误。

129、若x,y是一二叉树上的两个结点，那么中序序列中x在y的前边的条件是（C）

A、x是y的祖先

B、x是y的子孙

C、x在y垂直位置的左边

D、x在y垂直位置的右边

130、某会议邀请10名专家参加，酒店住宿共安排了6个房间，要求甲专家与乙专家单独住一间（不再安排其他人入住），丙专家、丁专家安排住同一间，戊专家与已专家不安排在同一间。甲、乙、丙、戊、已专家房间均已确定，且每个房间均有两个床位，则此次住宿共有（C）种不同的安排？

A、6

B、9

C、12

D、24

答案解析：甲、乙、丙、戊、已专家房间均已确定。因此只需要考虑给戊、已专家从后面的四位专家里面挑选同住即可，4*3=12种。

131、在一个长度为n的数组中找到第K大的数字，平均的算法时间复杂度最低的是（A）

A、O(n)

B、O(nk)

C、O(logn)

D、O(n^2)

132、一个7个顶点的完全图需要至少删掉（A）条边才能变为森林

A、16

B、21

C、15

D、6

答案解析：7个点的完全图一共有 7*6/2=21条边；7个点组成一棵树只需要6条边。这6条边要去掉一条边才能变成2棵树，2棵树就是森林了。所以变成森林最多只能剩下5条边。21-5=16。

133、设G是有n个结点、m条边(n<=m)的连通图，必须删去G的（A）条边，才能使得G变成一棵树。

A、m-n 1

B、m-n

C、m n 1

D、n-m 1

答案解析：树的边数=点数-1=n-1，所以要删掉m-(n-1)=m-n 1条边。

134、G是一个非连通无向图（没有重边和自环），共有28条边，则该图至少有（A）个顶点。

A、9

B、11

C、8

D、10

答案解析：假设至少有N个顶点。由于是非连通图，并且要满足28条边，所以N=边为28的完全图（顶点最少）的顶点数 1（与完全图不连通）。完全图边数=28，解n(n-1)/2=28，得n=8，因此N=8 1=9.

135、某数列有1000个各不相同的数，由低到高按序排列，现要对该数列进行二分法检索，在最坏的情况下，需要检索（B）个数据。

A、1000

B、10

C、100

D、500

答案解析：10个2的10次方1024 所以检索二叉树最多10层

136、学号1到30的小朋友顺时针排成一圈，从1号小朋友开始顺时针报数，从数字1开始数下去，1,2,3，…,28,28,30,…，一圈又一圈，问当数到数字n，所在的小朋友的学号为多少（B）

A、(n-1)0

B、1 (n-1)0

C、(n 1)0 1

D、(n 1)0

答案解析：假设n=35;可知道B是正确的。

137、下列属于网络模型的名称是（B）

A、LAN

B、TCP/IP

C、FTP

D、SMTP

138、一次数学考试试题由两部分组成，结果全班有15人得满分，第一部分做对的有31人，第二部分做错的有19人，那么两部分都做错的有（A）

A、3

B、4

C、6

D、12

答案解析：因为有15人满分，且第一部分有31人做对，于是第二部分就有15人做对.又因为第二部分有19人做错。所以全班共有15 19=34人。所以第一部分有34-31=3人做错。第二部分错的19人，所以两部分都错的有3人。

139、两根粗细相同、材料相同的蜡烛，长度比是21:16，它们同时开始燃烧，18分钟后，长蜡烛与短蜡烛的长度比是15:11，则较长的那根蜡烛还能燃烧（A）

A、150分钟

B、225分钟

C、128分钟

D、9分钟

答案解析：设蜡烛燃烧的速度为x，则(21-18x)/(16-18x)=15/11,求得x=1/8;所以长蜡烛还能燃烧(21-18*1/8)/(1/8)=150。

140、将60个红球，8个白球排成一条直线，至少会有（C）个红球连在一起。

A、6

B、8

C、7

D、5

答案解析:相当于8个白球在红球队列中插空，所以均分红球60/8=7

1.以下关于CSP-J/S的描述错误的是() 分值2分

A.任何人都可以自愿报名参加CSP-J/S

B.CSP-J/S是CCF独立主办的认证，和任何其他机构主办的等级考试无关

C.CSP-J/S和NOIP有密切关系

D.CSP-J/S认证成绩优异者，可参加NOI省级选拔，省级选拔成绩优异者可参加NOIC

2.-128的补码表示为()分值2分

A.00000000

B.00000001

C.10000000

D.11111111

3.以下不属于TCP拥塞控制算法的是()  分值2分

A.慢启动

B.拥塞避免

C.快启动

D.快速重传

4.以下不是基于UDP协议的是()  分值2分

A.DNS

B.RIP

C.TELNET

D.TFTP

5.定义如下函数add_edge和全局变量：

int to[MAX],nxt[MAX],h[MAX],top;

void add_edge(int u,int v){

to[ top]=v,nxt[top]=h[u],h[u]=top;

}

如下图节点编号从1开始，按边的编号顺序，以前向星的方式存储，请问nxt[h[3]]的值为()

分值2分

A.6

B.3

C.8

D.7

6.如下图所示，从节点1走6步走到节点5的方案数有多少种()

A.5

B.8

C.7

D.6

7.同时查找 2n 个数中的最大值和最小值，最少比较次数为( )。 分值2分

A.3(n-2)/2

B.3n-2

C.4n-2

D.2n-2

8.设 A 和 B 是两个长为 n 的有序数组，现在需要将 A 和 B 合并成一个排好序的 数组，请问任何以元素比较作为基本运算的归并算法最坏情况下至少要做 ( )次比较。  分值2分

A.n2

B.nlog2n

C.2n

D.2n-1

9.G 是一个非连通简单无向图，共有 36 条边，则该图至少有( )个顶点  分值2分

A.10

B.9

C.8

D.7

10.由四个不同的点构成的简单无向连通图的个数是( )  分值2分

A.32

B.35

C.38

D.31

11.前缀表达式- * 4 2 3 1 5的值为()  分值2分

A.16

B.17

C.19

D.15

12.2 3*(4-(5 6))/7的逆波兰表达式为() 分值2分

A.2 3 4 5 6 - * 7 /

B.2 3 4 5 6 - * / 7

C.2 3 4 5 6 - * 7 /

D.2 3 4 5 6 * / 7 -

13.若某算法的计算时间表示为递推关系：

则该算法的复杂度为()  分值2分

A.O(n)

B.O(nlog2n)

C.O(nlog22n)

D.O(nlong23n)

14.若某算法的计算时间表示为递推关系：T(n)=3T(n/4) nlong2n则该算法的复杂度为()  分值2分

A.O(n)

B.O(nlog2n)

C.O(nlog22n)

D.O(nlong23n)

15. 现有变量a,b,c,d，取值范围均为[0,15]，假设每个值出现的概率相同，则表达式的值能被3整除的概率( )(为计算机中的异或运算符，结果用分数形式表达)  分值2分

A．3/8

B.1/2

C.1/4

D.1/8

二、阅读程序写结果(共4题，每题10分，共计40分)

1.#include

using namespace std;

int a,b,c;

int* cal(int *p,int &q,int r) {

      q =r;

      *p =q;

      return p;

}

int main() {

      cin>>a>>b>>c;

      c=*cal(&a,b,c);

      cout<<a<<" span=""></a<<">

}

1.1 cal函数中参数p使用指针传递，q和r则是值传递  分值2.5分

对

错

1.2 cal函数返回一个指向int类型存储空间的地址  分值2.5分

对

错

1.3 当输入1 2 3时，程序输出结果为()  分值2.5分

A.6 2 3

B.6 5 3

C.6 5 6

D.1 2 6

1.4 当输入23 45 11时，程序的输出结果为()  分值2.5分

A.79 56 11

B.79 56 79

C.44 56 79

D.79 56 44

2.#include

#include

#define MAX 1000

#define p sqrt(3)

using namespace std;

int n,dp[1000][3];

int h0=1,h1=3;

double ans1=(2 p)/(2*p),ans2=(-2 p)/(2*p);

int main() {

      cin>>n;

      dp[1][0]=dp[1][1]=dp[1][2]=1;

      for(int i=2,tmp; i<=n; i ) {

            dp[i][0]=dp[i-1][1] dp[i-1][2];

            dp[i][1]=dp[i-1][0] dp[i-1][1] dp[i-1][2];

            dp[i][2]=dp[i-1][0] dp[i-1][1] dp[i-1][2];

            tmp=h1;

            h1=2*(h1 h0);

            h0=tmp;

      }

      for(int i=1; i<=n; i ) {

            ans1=ans1*(1 p);

            ans2=ans2*(1-p);

      }

      cout<<h1<<endl;< span=""></h1<<endl;<>

      cout<<dp[n][0] dp[n][1] dp[n][2]<<endl;< span=""></dp[n][0] dp[n][1] dp[n][2]<<endl;<>

      cout<<ans1 ans2<<endl;< span=""></ans1 ans2<<endl;<>

}

2.1 上述程序的输出中h1和dp[n][0] dp[n][1] dp[n][2]的值相等  分值2.5分

对

错

2.2 上述程序的输出中dp[n][0] dp[n][1] dp[n][2]和ans1 ans2的值相等  分值2.5分

对

错

2.3 当n等于5时，第一行输出(即h1)结果为( )  分值2.5分

A.164

B.60

C.448

D.128

当n等于10时，第三行输出(即ans1 ans2)结果为()  分值2.5分

A.9136

B.68192

C.24960

D.3344

3.#include

#include

#define LL long long

using namespace std;

LL l,r;

LL f[12][10][10][2][2][2],a[20];

LL Dfs(LL now,LL p,LL pp,LL _4,LL _8,LL top,LL hw) {

      if(_4&&_8) return 0;

      if(!now) return hw;

      if(!top && f[now][p][pp][_4][_8][hw]!=-1) return f[now][p][pp][_4][_8][hw];

      LL Up=top?a[now]:9;

      LL ret(0);

      for(LL i=0; i<=Up; i)

            ret =Dfs(now-1,i,p, _4|(i==4),_8|(i==8), top&&(i==Up) ,hw|(i==pp&&i==p));

      if(!top) f[now][p][pp][_4][_8][hw]=ret;

      return ret;

}

inline LL Solve(LL x) {

      LL tot(0);

      while(x) {

            a[ tot]=x;

            x/=10;

      }

      if(tot!=11) return 0;

      LL ret(0);

      for(LL i=1; i<=a[tot]; i)

            ret =Dfs(tot-1,i,0,(i==4),(i==8),i==a[tot],0);

      return ret;

}

int main() {

      cin>>l>>r;

      memset(f,-1,sizeof(f));

      cout<<solve(r)-solve(l-1);< span=""></solve(r)-solve(l-1);<>

      return 0;

}

3.1 同时包含4和8的数字都不会被统计  分值2.5分

对

错

3.2 相邻数位中，超过3个数位相同的数字都不会被统计  分值2.5分

对

错

3.3 下列哪个是合法(会被统计)的数字()  分值2.5分

A.2323234823

B.1015400080

C.23333333333

D.10010012022

3.4当输入12121284000 12121285550时，程序输出结果为()  分值2.5分

A.5

B.457

C.455

D.6

4.

4.1 上述程序实现大整数加法 分值2.5分

对

错

4.2 上述程序的算法复杂度大于（其中n为max(s1.length(),s2.length())）  分值2.5分

对

错

4.3 当输入111 011时程序输出为()  分值2.5分

A.10

B.4

C.21

D.2

4.4 当输入10101 101010时程序输出为()  分值2.5分

A.441

B.882

C.1764

D.220

五、完善程序(每题15分，共计30分)

1.（链表反转）单向链表反转是一道经典算法问题，比如有一个链表是这样的，1->2->3->4->5，反转后成为 5->4->3->2->1。现给定如下链表节点的定义：

struct LinkNode{

int value;

LinkNode* next;};

非递归实现：

LinkNode* Reverse(LinkNode* header) {

      if (header == NULL || header->next == NULL) {

            return header;

      }

      LinkNode* pre = header, *cur = header->next;

      pre->next = NULL;

      while(cur != NULL) {

            LinkNode* next = ____1____;

            ___2____ = pre;

            pre = cur;

            cur = next;

      }

      return pre;

}

递归实现：

LinkNode * Reverse(LinkNode * head) {

      if (head == NULL || head->next == NULL) {

            return head;

      }

      LinkNode * newhead = ___3____;

      ___4_____ = head;

      head->next = ___5____;

      return newhead;

}

1.1上述程序___1___中应该填写()

 分值3分

A.pre-> next

B.cur-> next

C.header-> next

D.NULL

1.2上述程序___2___中应该填写()  分值3分

A.pre-> next

B.cur-> next

C.header-> next

D.NULL

1.3上述程序___3___中应该填写()  分值3分

A.ReverseList(head)

B.ReverseList(pre)

C.ReverseList(cur)

D.ReverseList(head->next)

1.4上述程序___4___中应该填写()  分值3分

A.pre-> next->next

B.cur-> next->next

C.header-> next->next

D.NULL

1.5上述程序___5___中应该填写()  分值3分

A.pre-> next

B.cur-> next

C.header-> next

D.NULL

2) (最小环问题)给定一张无向图，求图中一个至少包含 3 个点的环，环上的节点不重复，并且环上的边的长度之和最小。该问题称为无向图的最小环问题。在本题中，你需要输出最小环的方案，若最小环不唯一，输出任意一个均可。若无解，输出 No。

1.1上述程序___1___中应该填写（）  分值3分

A.j

B.pos[i][j]

C.i

D.pos[j][i]

1.2上述程序___2___中应该填写()  分值3分

A.j

B.pos[i][j]

C.i

D.pos[j][i]

1.3上述程序___3___中应该填写()  分值3分

A.D[i][j] G[k][j] G[i][k]

B.D[i][j] G[j][k] G[k][i]

C.D[i][k] G[k][j] G[i][j]

D.D[i][j] G[j][i] G[i][k]

1.4上述程序___4___中应该填写()  分值3分

A.D[k][j]>D[i][k] D[k][j]

B.D[i][j]>D[i][k] D[k][j]

C.D[i][j]<d[i][k] d[k][j]< span=""></d[i][k] d[k][j]<>

D.D[i][k]>D[i][k] D[k][j]

1.5上述程序___5___中应该填写()  分值3分

A.pos[i][i]

B.stk[i]

C.pos[1][i]

D.pos[i][1]

参考答案

1C 2C 3C 4C 5B 6B 7B 8D 9A 10C

11A 12C 13D 14B 15A

阅读1错对CB

2 对对AC

3对错CA

4错错CB

完善程序

1B 2B 3D 4C 5D

1B2A3B4B5B

这篇好文章是转载于：学新通技术网