上半年程序员考试真题及答案下午卷.docx

上半年程序员考试真题及答案下午卷.docx

《上半年程序员考试真题及答案下午卷.docx》由会员分享，可在线阅读，更多相关《上半年程序员考试真题及答案下午卷.docx（21页珍藏版）》请在冰点文库上搜索。

上半年程序员考试真题及答案下午卷

试题一

（说明］

下K的流程图采用公式才-1牛?

1丰?

1%!

+£口"（/4!

+…他!

+…计算F的近值-

T）,再逐步累

设x位于区间（0,1），该流程图的算法要点是逐步累积计算每项的值（作为

加T值得到所需的结果S。

当T值小于10-5时，结束计算。

【流程图】

（1）S⑵x/n（3）T<0.00001⑷S+T⑸n+1

本题属于简单的数值计算应用。

人们经常需要近似计算初等函数的值。

在计算机内部，近似计算初等函数的值最常用的方法就是将初等函数按幕级数展开，再计算前若干项的和，直到计算误差满足要求为止。

在设计算法时应考虑，对于自变量的大致范围，如何展开级数，使级数收敛的速度比较快,在计算过程中，怎样估计计算的误差是否己经满足要求。

由于初等函数在计算机中需要频繁使用，因此设计髙效率的算法非常重要。

这种精益求

精的设计是全世界许多专家己经反复探索并实现了的。

对于一般程序员来说，只要求基本的、正确的算法设计，并实现编程就可以了。

本题中，为了计算指数函数ex的值，已经给出了基本的算法，以及计算过程中控制误差终

止计算的方法。

本题主要的重点是如何设计计算流程，实现级数前若干项的求和，以及判断终止计算的条件。

级数求和通常采用逐项累加的方法。

设S为累加的结果,T为动态的项值,那么,S+T

—S就能完成各项的累加。

由于本题中T=xn/n!

，如果每次都直接计算该项的值，则计算量会很大。

这种项的特

这是

殊性表明，后一项与前一项有简单的关充分利用前项的计算结果则会大大减少计算量。

程序员需要掌握的基本技巧。

本题的流程图中，一开始先输入自变量X,接着对一些变量赋初值。

1）处应填S。

流程图中

流程图中

（4）处需要累加S,实现S+T---S，因此，（4）处应填S+T。

5）处应对级数的项号n进行自增，因此，（5）处应填n+1—n。

试题二

【说明】

C语言常用整型（int）或长整型（Iong）来说明需要处理的整数，在一般情况下可以满

足表示及运算要求，而在某些情况下，需要表示及运算的整数比较大，即使采用更长的整型

（例如，Ionglong类型，某些C系统会提供）也无法正确表示，此时可用一维数组来表示

一个整数。

假设下面要处理的大整数均为正数，将其从低位到高位每4位一组进行分组（最后一组

可能不足4位），每组作为

【问题1】

【C函数】

if（⑴）p*B;

elsep*A;

lor（;i"}£"梅伶31零的其余畀粗摊&帶进ftS卿人数组

C[11-（p[i]+cf）%10000;cf-（ptij+ef）/lOOOOj

if{c£>0}C[i++]-cf;

⑸--I：

"标冉"和fir的外粗站甫*/

1个整数存入数组。

例如，大整数2543698845679015847在数组

（1）0

（4）A[i]=-1,或B[i]>-1，或其等价形式

（5）C[i],或其等价形式

本题考査C程序设计基本能力。

表示方式下进行两个大整数的相加运算时，主要考虑进位的处理。

0,因此空

（1）处应填入0。

由于相加时需要对齐，并且根据程序中c[i]=t%10000对t的使用，空

（2）处应填

入A[i]+B[i]+cf。

该运算同时产生下一步运算需要使用的进位值cf，因此空（3）处应填

入t/10000或（A[i]+B[i]+cf）/10000o

参与相加运算的两个整数位数不一定相同，因此，尚有剩余的那个整数的其余位数应带

进位记录下来，程序中设置的临时指针p指向保存这个整数的数组。

根据题中设置的标志若

数组A表示的整数已经结束，则满足A[i]=-1，否则满足B[i]=-1，因此考查if语句的逻

辑后，空（4）处应填入A[i]=-1，或B[i]>-1。

另外，当两个整数相加后产生进位，此时可能需要将此进位结果作为和数来记录，以

999999994567与5555相加为例说明，和数1000000000122比999999994567还要

多1位，并且在数组中表示时的分组数也多1个。

if语句if（cf>0）C[i++]=cf;

若要输出用数组表示的整数，则可用以下程序段：

voidp^rint^arr（intarE[],intnJ输出arr[n-ll的数整*丿

int1；

fox[i=n-2■l>=0;1--3I

RHirvt土dtt[il/lOOOj（dxrfiHIOCO）ZlOOJ;

printf（廿larr[LJfelOO}/lO.arrlijllOJi?

ppintf{）:

试题三

【说明】

二叉查找树又称为二叉排序树，它或者是一棵空树，或者是具有如下性质的二叉树:

若它的左子树非空，则其左子树上所有结点的键值均小于根结点的键值;

若它的右子树非空，则其右子树上所有结点的键值均大于根结点的键值;

左、右子树本身就是二叉查找树。

设二叉查找树采用二叉链表存储结构，链表结点类型定义如下:

J谎点的糙饥为非贲tt数”"S点的左，右子tw针可

typ?

int3cey_vaiue-

atcuctBiTnode•right;

BSTiee;

函数find_key（root,key）的功能是用递归方式在给定的二叉查找树（root指向根结点）

中查找键值为key的结点并返回结点的指针；若找不到，则返回空指针。

【问题1】

【C函数】

BSTreefirdkeyOSTreer

If[⑴）

fetutnNULLrelse

if«key—root—Akey_valuejreturn⑵;

亡Iseifgkey

return（3）;

eJtse

return（4）;

（1）!

root,或root==0，或root=NULL

（2）root⑶find_keyj（root->left,key）（4）find_key（root->right,key）

本题考查数据结构的应用、指针和递归程序设计。

根据二叉查找树的定义，在一棵二叉查找树上进行查找时，首先用给定的关键字与树根结点的关键字比较，若相等，则查找成功：

若给定的关键字小于树根结点的关键字，则接下

（1）处填

来到左子树上进行查找，否则接下来到右子树上进行查找。

如果在给定的二叉查找树上不存在与给定关键字相同的结点，则必然进入某结点的空的子树时结束查找。

因此，空

入!

root表明进入了空树；空

（2）处填入root表明返回结点的指针；空

显然，在二叉排序树上进行查找时，若成功，则查找过程是走了一条从根结点到达所找

比较。

因此，在树中查找一个关键字时,

需要比较的结点个数取决于该关键字对应结点在该

【问题2】

若某二叉查找树中有n个结点，则查找一个给定关键字时，需要比较的结点个数取决于

（5）。

（5）该关键字对应结点在该二叉査找树所在层次（数）或位置，或者该二叉树中从根

结点到该关键字对应结点的路径长度

本题考查数据结构的应用、指针和递归程序设计。

根据二叉查找树的定义，在一棵二叉查找树上进行查找时，首先用给定的关键字与树根

F来到左子树上进行查找，否则接下来到右子树上进行查找。

如果在给定的二叉查找树上不

处填入！

root表明进入了空树；空

（2）处填入root表明返回结点的指针；空（3）处填入

显然，在二叉排序树上进行查找时，若成功，则查找过程是走了一条从根结点到达所找

试题四

【说明1】

函数main（）的功能旨在对输入的一个正整数n,计算12+22+32+…+n2,但是对该函数进行测试后没有得到期望的结果。

ft码

2

3

4

5

6

7

S

void[r.dlnt}

（in-tKrrifsyzfJif

priritf{"inputaninteger:

"i;ftcarf£"■%（!

",n）;

for（E=1¥k<=n；<+4）T

sum2k*t;

print£（"result：

5urn>;

k输入5测试上述main朗数时.S示结果IH下所示它

2.将行号为7舸代码修改为？

prinU（"n=%d^rcsuk:

%dVi\n,sum）;并再次输入5测试显示结果如下所示•

inputAnintegers5a-2293631re&ult:

-50259Q9O9

【问题1】

请给出上述main函数中需要修改的代码行号，并给出修改后的整行代码。

it号

楼K后的fi行代码

本表中的解答无次序要求。

行号■

修改后的代利厅

2

intk.,n,sunv«=o：

或X,n,sunvsuift=0?

4

acanf{"ld'\

5

foE

注：

在第3行、第4行中增加语句SUm=O;,或者将sum=O加在第5行的正确位置也可

以，即

for（k=1,sum=0;k<=n;k++）或者for（sum=0,k=1;k<=n;k++）.

本题考查C程序的调试和排错能力。

分析】程序中的错误可分为语法错误和语义错误,其中语义错误又分为静态语义错误

和动态语义错误。

语法错误和静态语义错误可在编译时检测出，动态语义错误则

在程序运

行时才能表现出来。

C函数1所示代码已经通过编译，而运行结果不对。

虽然直接的运行结果为输出变量sum

的值，但其计算过程却与n和k的值相关。

因此，可以从每个变量初始值的设定、修改方式

和引用方式考査。

对于变量k，其初始值由语句表达式k=l确定，修改方式为k++,引用处为

循环条件k<=n和sum+=k*k，没有不当之处。

对于变量n,其初始值由scanf（"%d"，n）确定，引用处为循环条件k<=n,得到初始值

后不再进行修改。

然而从第2次测试main函数时显示的结果可知，n的值并不是为其输入

的值5,显然对n值的设定有误，仔细检查scanf函数的调用可知，其中的n之前缺少了取

地址运算符号&，正确的函数调用为scanf（"%d"，&n）。

对于变量sum,其修改和引用处分别为sum+=k*k、printf（"result:

%d\n",sum）,没有

对其进行初始化，而是在一个未知的数值上开始累加，因此，

sum最后的结果无法符合预期

的值。

另外，函数中还有一个比较隐蔽的错误，就是语句结束符号“

;”的不当使用，导致

循环语句for（k=1;k<=n;k++）只是将k的值从1递增到n+1，没有产生实质的运算结果,

使得sum的值不会随着sum+=k*k发生变化。

问题2】

说明2】

函数test_f2（）编译时系统报告有错,修改后得到函数f2_B（）。

对函数f2_B（）进行编

译时顺利通过，在某些C系统中执行时却由于发生异常而不能正确结束。

C函数2】

void2（}

ickar3tf（]*""testsLcing"fintt;

for（L=0;i<1+十『li

•atr»Vr

voidf2_B（）

（char*3tr正string"』

Int1；

for[1=0;i<4;L+rstr++）*9tr-'a';

【问题】

（1）请指出函数test_f2中不能通过编译的表达式;

⑵请指出可能导致函数f2_B运行异常的表达式。

（1）strf+

⑵*str='a'.

本题考查C程序的调试和排错能力。

【分析】函数teSt_f2（）编译时系统报告有错，检査其函数体，其中的charstr[]="test

string";表明str是一位数组名，因此，*str表示str[0]，通过*str='a';为str[0]赋

值显然是允许的。

出错的地方是strf+，在C语言中，数组名是指针（地址）常量，是不

允许修改的，strf+试图修改指针常量str，因此编译时会报告错误。

若将str修改为指针

变量，即在函数f2_B（）中定义为char*str="teststring"

，则可以通过strH?

修改str

的值，使得str可以指向f同的字符对象。

使某些C系统执行f2_B0时发生异常的表达式是

*str='a',该表达式要修改str所指对象的值，而定义char*str="teststring"

则令

str指向了一个字符串常量，由于此常量在运行过程中不可修改，因此试图通过指针

str

修改常量的动作导致了异常。

试题五

【说明】

C++标准模板库中提供了map模板类，该模板类可以表示多个“键-值”对的集合，其中

键的作用与普通数组中的索引相当，而值用作待存储和检索的数据。

此外，C++模板库还提

供了pair模板类，该类可以表示一个“键-值”对。

pair对象包含两个属性：

first和second.

其中first表示“键-值”中的“键”，而second表示“键-值”中的“值”。

map类提供了insert方法和find方法，用于插入和查找信息。

应用时,

将一个pair对

象插入（insert）到map对象后，根据“键”在map对象中进行査找（find）

，即可获得一

个指向pair对象的迭代器。

F面的C++代码中使用了map和pair模板类，将编号为1001、1002、

1003的员工信

息插入到map对象中，然后输入一个指定的员工编号，通过员工编号来获取员工的基本信息。

员工编号为整型编码，员工的基本信息定义为类employee。

map对象与员工对象之间的关系

及存储结构如图5-1所示。

employRJOO【

R3-1map对Stlj屁丄聲f®Z闾的关系^^储结构示«图

阅读以下说明和C++代码，将应填入（n）处的字句写在答题纸的对应栏内。

【C++代码】

★includflc；io5i；L代arnA

iinclude

^irtclAjdew$trtn3jA

usingnamespacestd.;

七丄aa吕employeel

⑴；

employeetstringstringphoneN'untber,stiingaddress）I

this-AfticTL乜Tran©J

-this->phon^NunJber=phoneHyirit>eij

T：

tit3->adiJrflfiE-address;

name；

phoneNLuiLber：

◎dd「音皐si

Sstringstungstring

i.ntmain（k

iDAp-cint,einplo/ee*>empioyeeHfl.p;

typedeEpairejnployee*>employg&P^air?

for（intomployTadex*IDOl?

employTndeK<-31口03fem（pLoyTndfiK++）{chartenp[10];"临忙存傭空|b]

_1tcs{employIndex,t«mp,10];"将einploylndcjt挣比肯字符串存橢在

"EP中stringtiTipi,O）I;//追过gnp构it吐匸丄口日对皐

召mplQy早eHap■femployeePair片employInxlex,

n<^ensployee（"employee-"十trap,''e5523?

27-"+i：

[iip,Haiddte手日p）

Az"将员工編号和员工信意jS入到employeeHap对蠡中

xrttsployseHe=0；

eoutX"请输入员工烷号：

叫

<■4）>?

■^mployeeNo;"从标准输入获得员工（8号

caapsintj（*rtipioyee*?

:

:

ccnat_lceratorLt;

it*（5）■£itid（ernploygeW&）JF/帳抠员王境号盘找为工信恳

ifirtempioyeeMap.end{}J|

cout«F该员工歸$芥存崔!

r«endi；

return-1;

CQUt

<<

■

CQUL

«

411

umjt

«

■

cout

■h

return0

4r

M«it->first<second->nEiJike<<

你所世询的员r般号为.

该员工姓电h"«

试员工电话吊"<<11->3econd->ptiocieNiml>ei<<卓ndl『该负工地屮匕■<5eCDnc3">siiiires,,si<.

（1）public

（2）temp（3）insert（4）cin（5）employeeMap

试题五分析

Map类和Pair类的

本题主要考查C++程序设计语言中类库的使用。

题干中己经给出了

使用方式，Map类主要用于存储一组员工的信息，而Pair类则主要用于建立员工号和员工

信息的对应关系，员工信息主要使用类employee的对象来存储。

C++语言的类生成对象时，

需要调用类的构造方法，因此，employee的构造方法应该为公有构造方法，空缺

（1）处的答案应该为public;空缺

（2）处的代码主要是根据学符数组temp[10]来构造一个string对象，参数应为temp;空缺（3）处的代码是构造员工对象，并将员工对象和员工编号放入—个

Pair对象中，再将Pair对象插入到employeeMap中，根据题干说明，Map类中insert方法

完成插入对象的功能，因此，空缺（3）处应该填入insert;空缺（4）处的目的是从标准输

员工编号，查取员工信息，Map类中的find方法可完成该功能，而当前员工的编号和员工

信息都存储在Map类的实例employeeMap中。

试题六

【说明】

HashMap实

java.util包中提供了HashMap模板类，该模板类可以表示多个“键-值”对的集合，其中“键”的作用与普通数组中的索引相当，而“值”用作待存储和检索的数据。

现了Map接口。

在Map接口中定义了put和get方法，put方法表示Map对象中加入一个“键

-值”对，get方在则通过“键”来获取其对应的“值”。

F面的Java代码中使用了HashMap模板类，将编号为1001、1002、1003的员工信息插

基本信

入到HashMap对象中，然后输入一个指定的员工编号，通过员工编号来获取员工的

HashMap对象与员工对象之间的关系及存储结构如下图所示。

HashM即府象与齟工対專上阎的关址存铺结构京S團

importjavi.util.

classemployest

&ipj}loyeetS'ringn&ote,stringphon^Huntb&irstringitidrtwE）|this.fiiwft=dur时

LhIft.ph$A*NLJ3ib4r“pKOhAHLilltbairi

this.s^Hfea*-AdJrMH；

J

StringfiAmZ

Strin亨

StringAddfftSBJ

publicclasrsjAvaUsin1

publicC彳工哎？

卜；

Map

耳epl口F耳专；

fort,jln^«g«r*T™pic-ylnd»M=lOOlr^'r^pLcylnd&x<=lOO3jenpiOyT_rtdejtt■牛>§

S牛匕trigtrp■employ工Tide工，（1「[],

enpjQvrrKap*_12〉tempiioylntlcis,__£33__（H^aipL&T^-*ttnip°

5,523蛇T，仁吨）*

"ed（irM3-"^tEip

S

i{"精机応号押为工佶葛ffl/S到ftPip.loy6cMdRM&中

IntenTilioyi^eJdo-0;

Syst^n；.cut,pi；Lnt[■请KIAjR工编号:

"jr

£匚inners-newScanner（S/steir..in）?

EiEpleyp鬪。

=s.next1Tit（>，:

〃从标滩输臨我鄭射工S号

r^sullc

MPioy*«Map*_（_!

）_I«tplo!

rft*：

«o）;

if4⑸=nuliii

syaten.cia*.prrriTlr.t*M

return;

Syetem^out^.prLiitln査卅的员工编号九+empioyeetH?

）;

S西tetnq口匕pr£n匕LiU■養员工妊名t啊Syatem^DutiprintIn（*^5T电话£*System-Oiit.printIn地址：

・

4resuLE-naiae）;

■hrenulttphonchumber）/+result.address）;

（1）toString

（2）put（3）newemployee⑷get（5）result

本题主要考查Java程序设计语言中类库的使用。

空缺

（1）处需要将employlndex转化为字符串，因此可以使用整型数的toString方法；空缺

（2）和（3）处的代码是希望构造出

HashMap类的实例employee

employee对象，并把新构造出的对象及其对应的编号加入到

-Map中，而HashMap的put方法可完成插入编号和员工对象的功能，因此空缺

（2）处需要

填写Put方法，空缺（3）处需要使用new构造一个新的employee对象；空缺（4）处主要是

使用empiyeeMap对象根据员工号码查找员工信息，可使用HashMap中的get方法，该方法

查询到员工信息后将放入result引用中，若没有査到，result将为空。