2014年上半年程序员下午题

1、2014年上半年程序员下午题试题一指定网页中， 某个关键词出现的次数除以该网页长度称为该关键词在此网 页中的词频。对新闻类网页，存在一组公共的关键词。因此，每个新闻网页都存 在一组词频，称为该新闻网页的特征向量。设两个新闻网页的特征向量分别为：甲(a1,a2,ak )、乙(b1,b2,bk)，则计算这两个网页的相似度时需要先计算它们的内积S=a1b1+a2b2+akbk。一般情况下，新同网页特征向量的维数是巨大的，但每个特征向量中非零元素却并不多。为了节省存储空间和计算时间，我们依次用特征向量中非零元素的序 号及相应的词频值来简化特征向量。为此，我们用(NA(i),A(i)|i=1,2,m和(

2、NB(j),B(j)|j=1,2,.,n)来简化两个网页的特征向量。其中：NA(i)从前到后描述了特征向量甲中非零元素A(i)的序号(NA(1)<NA(2) < .) , NB(j)从前到后描述了特征向量乙中非零元素B(j)的序号(NB<NB(2) <)。下面的流程图描述了计算这两个特征向量内积S的过程。（1）-s. trLj/璃出内积试题二【说明1】函数isPrime(int n) 的功能是判断n是否为素数。若是，则返回1,否则 返回0。素数是只能被1和自己整除的正整数。例如，最小的 5个素数是2, 3, 5， 7， 11。【C函数】int isPrime(intti

3、nt k# t;ifreturn 1;if (n<2 I _ (.)_) return 0;"小于2的數戒大于2的偶数不是素数/t (int)sqrt(nJ +1;for (k 3; k < t; k+=2 )if () return 0;return 1;【说明2】函数int minOne(int arr，int k)的功能是用递归方法求指定数组中前 k个元素中的最小者，并作为函数值返回。【C函数】int rt'inOne<int arr ), int k)int t;assert(k>0>if (k1)return (3);t = minOn

4、e(arr+l# <4);if (arr(0J<t)return arr0；return一;函数 areAnagrams （char*fstword , char*sndword ）的功能是判断 fstword 和 sndword 中的单词（不 区分大小写）是否互为变位词，若是则返回1，否则返回0。所谓变位词是指两个单词是由相同字母的不同排列得到的。例如，”triangle "与“integral ” 互为变位词，而“ dumbest ”与“ stumble ”不是。函数areAnagrarns的处理思路是检测两个单词是否包含相同的字母且每个字母出现的次数也相同。过程是先

5、计算第一个单词（即 fstword中的单词）中各字母的出现次数并记录在数组counter中，然后扫描第二个单词（即sndword中的单词）的各字母，若在第二个单词中遇到与第一个单词相同的字母，就将相应的计数变量值减 1，若在第二个单词中发现第一个单词中不存在的字母，则可断定这两个单词不构成变位词。最后扫描用于计数的数组counter各元素，若两个单词互为变位词，则counter的所有元素值都为0。函数areAnagrams中用到的部分标准库函数如下表所述。说明inf islcwer( int ch );若ch表顽一个小写英文宁阳”则返回一平井0盏敢，钩则返画0int isuppcrt int

6、ch若uh表示一个大写荚文字母”则返回一帯非0盞數"苦则返回0int halv>um( int ch；若ch炭奉一片英文字母醴敵字字苻.蒯iS回菲0整数.舌则返回。int isalpha ( ml ch若 訪表駅一午英文字毋.则返回-于非0巌敷.普则堰回£1int( int ch )；若di衷赤一牛敷宇字轉则返回一十非。矗數 否刈返回窈int crcuipC const char *strl const char 闿);荐血1対!rtr工决示的宇符申抬同*剧追回0.否则遊回一节丁墨«17负擠敵 分别谩示弧1表示的字符準毁大J较小char *s1rcat( q

7、hojr strl., ODnsc char *str2 >梅str2義示的字碎申连攪？表亦的宇符串之后，近回【C函数】Int ac eAnka(char atwordr ehar)t>ntinc12 6) (0 j / /* counter!i 字琲？牛字的?ScISd為成y*旳蕃0牛.为靈亍.Htit类橫"if (>retv rn 0;诃检曲眄平互为愁豈列（*fitwordJ 1/尹真期-牛录词屮各字母出現的感检*i f ti»dlphA*f*twcrd）月1 £(is upperooncer elsecounter(21 ；(fitword

8、 *'A'1+;I £jtword - 1 a'J+; / F个字苻/sndword) i It«anord) » finiSe* - 1 simper (*sniworcil t "irttiwerc) -; *an*3wox-d -* ait 4counterf index) > counter findex-;ala6i2 :"下一t字符"for 11tidex * 0jiftd*x + »)if C_t«turn 0;return 1;试题四【说明】函数ReverseList

9、（LinkList headptr ）的功能是将含有头结点的单链表就 地逆置。处理思路是将链表中的指针逆转，即将原链表看成由两部分组成：已经完成逆置的部分和未完成逆置的部分， 令s指向未逆置部分的第一个结点，并将 该结点插入已完成部分的表头（头结点之后），直到全部结点的指针域都修改完 成为止。例如，某单链表如图4-1所示，逆置过程中指针s的变化情况如图4-2所示。lieadptrheadptr齡4_2链表结点类型定义如下：typedef struct Node( int data;struct Node ext t Next 电# *Lir)kLi at；void ReverseL丄蓉t Li

10、nkList headptr/含头结点的单讎哀就地進” headptr为头措野if (工丿)return; p »< 2) t1f (p->next) return； & = p->nex t;-NULL；LinkLLst pt$i"空毬衰头给点）时无需处理2P推向第一牛元鴛统虑“懐衰中仅有一令元葉皓査时无需处理/3指向鼻二个元*箱点/ttWf元索结点的楷斟城为宇whlXe <9>(p - s；s -<4 )_;p r> next * headptr -> next; headptr -> next 一；令p指向

11、未处理健衰的第一6站点/精p所柑结点插入己宪成C3分的我头试题五【说明】对部分乐器进行建模，其类图如图5-1所示，包括:管乐器（Wind）、打击乐器（Percussi on ）、弦乐器（Woodwind、铜管乐器（Brass）。乐器（Instrument ）、 Stringed ）、木管乐器)： voidrWindPanutvton忧 n : Mote) 1 vod品血町：心K1T>ptey( n: N<u): vend 科皆0: voidUrtWdfp 剛 n: Note ): void +adjuil(): voidMusic）使用各类乐器下面是实现上述设计的C+弋码，其中音乐

12、类（Instrument ）进行演奏和调音等操作。【C+弋码】tinclude蜩Ln中 narespace std;的呃| /校宰善特青* /MJDCL£ Cf C SHARPr B i'LAl F ；c aqs XnatruMCnt /*/public：一 f/play口void adjust.) - Q;/fldjunt口卄claas Hind |public：void pl«y (Nota n) co虫叩“心刃苫学“n « 的打void) cout«pWind.Adjust()*«endl;IJ，咲 hr ugg ion SttL

13、ntfcd/Cidss Brds _(j)_ fpub 1”；voidnJ L cout«-Braqg. play( * « n « endl;void idju*t cout«"tarass.() *<<endl；)odwind i public Wind public：vflldn) ( coutcc"Woodwind.plyc " << n «endl; )iClASS Muaxc tpubl1c:廿心丄d tuneUnAtrumant* i) I i-*pU/MTDatB_C>

14、 jvoid adjust(ln*trumen£ 1) ii->ad3uit(>；)void tur.#Al 1(*U * iftt numlna> (/沖毎小乐H定谓 */for( int i D; 1 < auElnat i*+thi3->adju»tl【£|*J;“ 妙冃槽談电义一 6囲斂辭.讪晒數舞進财故帥鼻rr(的尤实民代州蜻vint min 门(Music* music U Music ()；Instrument* Qrohestra ( ( new Hindi)Woodwind 1 打music ->tuneAil