软件水平考试《程序员》习题及答案.docx

软件水平考试程序员习题及答案习题1在Word的编辑状态打开了一个文档，对文档没作任何修改，随后 单击Word主窗口标题栏右侧的“关闭按钮或者单击“文件菜单 中的“退出”命令，则BA. 仅文档窗口被关闭B. 文档和Word主窗口全被关闭C. Word主窗口被关闭D. 仅文档和Word主窗口全未被关闭1. 在Word的编辑状态，文档窗口显示出水平标尺，拖动水平标 尺上沿的“首行缩进滑块，则BA. 文档中各段落的首行起始位置都重新确定B. 文档中被选择的各段落首行起始位置都重新确定C. 文档中各行的起始位置都重新确定D. 插入点所在行的起始位置被重新确定3 .在Word的编辑状态，打开了 “wl.doc文档，若要将经过编 辑后的文档以“w2.doc”为名存盘，应当执行“文件菜单中的命令 是CA. 保存B. 另存为HTMLC. 另存为D. 版本C. 网关D. 网桥36. 计算机中对数据进行加工与处理的部件，通常称为AA. 运算器B. 控制器C. 显示器D. 存储器37. 微型计算机中内存储器比外存储器AA. 读写速度快B. 存储容量大C. 运算速度慢D. 以上三种都可以38. 目前微型计算机中CPU进行算术运算和逻辑运算时，可以处 理的二进制信息长度是DA. 32 位B. 16 位C. 8位D. 以上三种都可以39. 微型计算机存储器系统中的Cache是BA. 只读存储器B. 高速缓冲存储器C. 可编程只读存储器D. 可擦除可再编程只读存储器40. 存储容量1GB等于CA. 1024BB. 1024KBC. 1024MB128MB习题2在从1到n的正数中1出现的次数题目：输入一个整数n,求从1到n这n个整数的十进制表示中 1出现的次数。例如输入12,从1到12这些整数中包含1的数字有1, 10, 11 和12, 1 一共出现了 5次。分析：这是一道广为流传的google面试题。用最直观的方法求 解并不是很难，但遗憾的是效率不是很高；而要得出一个效率较高的 算法，需要比较强的分析能力，并不是件很容易的事情。当然，google 的面试题中简单的也没有几道。首先我们来看最直观的方法，分别求得1到n中每个整数中1 出现的次数。而求一个整数的十进制表示中1出现的次数，就和本面 试题系列的第22题很相像了。我们每次判断整数的个位数字是不是 lo如果这个数字大于10,除以10之后再判断个位数字是不是lo基 于这个思路，不难写出如下的代码：int NumberOf1(unsigned int n)；/ Find the number of 1 in the integers between 1 and n/ Input： n - an integer/ Output: the number of 1 in the integers between 1 and n/int NumberOflBeforeBetweenlAndN_Solutionl(unsigned intn)int number = 0；/ Find the number of 1 in each integer between 1 and nfor (unsigned int i = 1； i = n； + i)number += NumberOfl(i)；return number；)/ / Find the number of 1 in an integer with radix 10/ Input： n - an integer/ Output: the number of 1 in n with radix/ /int NumberOf1(unsigned int n)int number = 0；while(n)(if(n % 10 = 1)number +；n = n / 10；)return number；)这个思路有一个非常明显的缺点就是每个数字都要计算1在该 数字中出现的次数，因此时间复杂度是0(n)。当输入的n非常大的 时候，需要大量的计算，运算效率很低。我们试着找出一些规律，来 避免不必要的计算。我们用一个稍微大一点的数字21345作为例子来分析。我们把从1到21345的所有数字分成两段，即1-1235和1346-21345。先来看1346-21345中1出现的次数。1的出现分为两种情况： 一种情况是1出现在最高位（万位）。从1到21345的数字中，1出现 在10000-19999这10000个数字的万位中，一共出现了 10000（104） 次；另外一种情况是1出现在除了最高位之外的其他位中。例子中 1346-21345,这20000个数字中后面四位中1出现的次数是2000次 （2*103,其中2的第一位的数值，103是因为数字的后四位数字其中 一位为1,其余的三位数字可以在0到9这10个数字任意选择，由 排列组合可以得出总次数是2*103）。至于从1到1345的所有数字中1出现的次数，我们就可以用递 归地求得了。这也是我们为什么要把1-21345分为1-1235和 1346-21345两段的原因。因为把21345的最高位去掉就得到1345, 便于我们采用递归的思路。分析到这里还有一种特殊情况需要注意：前面我们举例子是最高 位是一个比1大的数字，此时最高位1出现的次数104（对五位数而 言）o但如果最高位是1呢？比如输入12345,从10000到12345这些 数字中，1在万位出现的次数就不是104次，而是2346次了，也就 是除去最高位数字之后剩下的数字再加上lo基于前面的分析，我们可以写出以下的代码。在参考代码中，为 了编程方便，我把数字转换成字符串了。include string.h”include stdlib.h”int NumberOf1(const char* strN)；int PowerBaselO(unsigned int n)；/ / Find the number of 1 in an integer with radix 10/ Input: n - an integer/ Output: the number of 1 in n with radix/ /int NumberOfIBeforeBetweenlAndN_So1ution2(int n)if(n = 0)return 0；/ convert the integer into a stringchar strN50；sprintf(strN, %d, n)；return NumberOfl(strN)；)/ /习题3整数的二进制表示中1的个数题目：输入一个整数，求该整数的二进制表达中有多少个1。例 如输入10,由于其二进制表示为1010,有两个1,因此输出2。分析：这是一道很基本的考查位运算的面试题。包括微软在内的 很多公司都曾采用过这道题。一个很基本的想法是，我们先判断整数的最右边一位是不是lo 接着把整数右移一位，原来处于右边第二位的数字现在被移到第一位 了，再判断是不是lo这样每次移动一位，直到这个整数变成0为止。 现在的问题变成怎样判断一个整数的最右边一位是不是1 了。很简 单，如果它和整数1作与运算。由于1除了最右边一位以外，其他所 有位都为0。因此如果与运算的结果为1,表示整数的最右边一位是 1,否则是0。得到的代码如下：/ / Get how many Is in an integer1s binary expression/ /int NumberOfl_Solutionl(int i)int count = 0；while(i)(if(i & 1)count +；i = i 1；)return count；)可能有读者会问，整数右移一位在数学上是和除以2是等价的。 那可不可以把上面的代码中的右移运算符换成除以2呢?答案是最好 不要换成除法。因为除法的效率比移位运算要低的多，在实际编程中 如果可以应尽可能地用移位运算符代替乘除法。这个思路当输入i是正数时没有问题，但当输入的i是一个负数 时，不但不能得到正确的1的个数，还将导致死循环。以负数 0x80000000为例，右移一位的时候，并不是简单地把最高位的1移 到第二位变成0x40000000,而是OxCOOOOOOOo这是因为移位前是个 负数，仍然要保证移位后是个负数，因此移位后的最高位会设为lo 如果一直做右移运算，最终这个数字就会变成OxFFFFFFFF而陷入死 循环。为了避免死循环，我们可以不右移输入的数字i。首先i和1做与运算，判断i的最低位是不是为1。接着把1左移一位得到2,再 和i做与运算，就能判断i的次高位是不是1这样反复左移，每 次都能判断i的其中一位是不是1。基于此，我们得到如下代码：IIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIII / Get how many Is in an integer1s binary expression/ /int NumberOfl_Solution2(int i)int count = 0；unsigned int flag = 1；while(flag)if(i & flag)count +；flag = flag 1；)return count；另外一种思路是如果一个整数不为0,那么这个整数至少有一位 是1。如果我们把这个整数减去1,那么原来处在整数最右边的1就 会变成0,原来在1后面的所有的0都会变成1。其余的所有位将不 受到影响。举个例子：一个二进制数1100,从右边数起的第三位是 处于最右边的一个1。减去1后，第三位变成0,它后面的两位0变 成1,而前面的1保持不变，因此得到结果是1011O我们发现减1的结果是把从最右边一个1开始的所有位都取反 了。这个时候如果我们再把原来的整数和减去1之后的结果做与运 算，从原来整数最右边一个1那一位开始所有位都会变成0。如 1100&1011=1000o也就是说，把一个整数减去1,再和原整数做与运 算，会把该整数最右边一个1变成0。那么一个整数的二进制有多少 个1,就可以进行多少次这样的操作。这种思路对应的代码如下：IIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIII / Get how many Is in an integer1s binary expression/ /int NumberOfl_Solution3(int i)4. 在word的编辑状态，被编辑文档中的文字有“四号”、“五 号、“16”磅、“18磅四种，下列关于所设定字号大小的比较中, 正确的是AA. “四号”大于“五号B. “四号小于“五号C. “16磅大于“18”磅D. 字的大小一样，字体不同5. 0SI （开放系统互连）参考模型的最高层是CA. 表不层B. 网络层C. 应用层D. 会话层6. 微型计算机中使用最普遍的字符编码是DA. EBCDIC 码B. 国标码C. BCD 码D. ASCII 码7. 微型计算机中的内存储器，通常采用CA. 光存储器B. 磁表面存储器C. 半导体存储器D. 磁芯存储器int count = 0；while (i)(+ count；i = (i - 1) & i;return count；)习题4栈的push、pop序列题目：输入两个整数序列。其中一个序列表示栈的push顺序， 判断另一个序列有没有可能是对应的pop顺序。为了简单起见，我们 假设push序列的任意两个整数都是不相等的。比如输入的push序列是1、2、3、4、5,那么4、5、3、2、1 就有可能是一个pop系列。因为可以有如下的push和pop序列：push 1, push 2, push 3, push 4, pop, push 5, pop, pop, pop, pop, 这样得到的pop序列就是4、5、3、2、lo但序列4、3、5、1、2就 不可能是push序列1、2、3、4、5的pop序列。分析：这到题除了考查对栈这一基本数据结构的理解，还能考查 我们的分析能力。这道题的一个很直观的想法就是建立一个辅助栈，每次push的 时候就把一个整数push进入这个辅助栈，同样需要pop的时候就把该栈的栈顶整数pop出来。我们以前面的序列4、5、3、2、1为例。第一个希望被pop出来 的数字是4,因此4需要先push到栈里面。由于push的顺序已经由 push序列确定了，也就是在把4 push进栈之前，数字1, 2, 3都需 要push到栈里面。此时栈里的包含4个数字，分别是1, 2, 3, 4, 其中4位于栈顶。把4 pop出栈后，剩下三个数字1, 2, 3o接下来 希望被pop的是5,由于仍然不是栈顶数字，我们接着在push序列 中4以后的数字中寻找。找到数字5后再一次push进栈，这个时候 5就是位于栈顶，可以被pop出来。接下来希望被pop的三个数字是 3, 2, lo每次操作前都位于栈顶，直接pop即可。再来看序列4、3、5、1、2o pop数字4的情况和前面一样。把 4 pop出来之后，3位于栈顶，直接pop0接下来希望pop的数字是5, 由于5不是栈顶数字，我们到push序列中没有被push进栈的数字中 去搜索该数字，幸运的时候能够找到5,于是把5 push进入栈。此 时pop 5之后，栈内包含两个数字1、2,其中2位于栈顶。这个时 候希望pop的数字是1,由于不是栈顶数字，我们需要到push序列 中还没有被push进栈的数字中去搜索该数字。但此时push序列中所 有数字都已被push进入栈，因此该序列不可能是一个pop序列。也就是说，如果我们希望pop的数字正好是栈顶数字，直接pop 出栈即可;如果希望pop的数字目前不在栈顶，我们就到push序列中 还没有被push到栈里的数字中去搜索这个数字，并把在它之前的所 有数字都push进栈。如果所有的数字都被push进栈仍然没有找到这个数字，表明该序列不可能是一个pop序列。习题5最长公共子串题目：如果字符串一的所有字符按其在字符串中的顺序出现在另 外一个字符串二中，则字符串一称之为字符串二的子串。注意，并不 要求子串(字符串一)的字符必须连续出现在字符串二中。请编写一个 函数，输入两个字符串，求它们的最长公共子串，并打印出最长公共 子串。例如：输入两个字符串BDCABA和ABCBDAB,字符串BCBA和BDAB 都是是它们的最长公共子串，则输出它们的长度4,并打印任意一个 子串。分析：求最长公共子串(Longest Common Subsequence, LCS)是 一道非常经典的动态规划题，因此一些重视算法的公司像 MicroStrategy都把它当作面试题。完整介绍动态规划将需要很长的篇幅，因此我不打算在此全面讨 论动态规划相关的概念，只集中对LCS直接相关内容作讨论。如果对 动态规划不是很熟悉，请参考相关算法书比如算法讨论。先介绍LCS问题的性质：记Xm=xO, xl,xm-1和 Yn=yO,yl,，yn-1为两个字符串,而Zk=zO,zl, zkT是它们的 LCS,则：1. 如果 xml=yn-l,那么 zk-l=xm-l=yn-l,并且 ZkT 是 Xm-1和 Yn-1 的 LCS；2. 如果 xm-lyn-1,那么当 zk-lxm-1 时 Z 是 Xm-1 和 Y 的 LCS；3. 如果 xm-lyn-1,那么当 zk-lyn-1 时 Z 是 Yn-1 和 X 的 LCS； 下面简单证明一下这些性质：1. 如果泳-lxm-l,那么我们可以把xm-1 (yn-1)加到Z中得到 V ,这样就得到X和Y的一个长度为k+1的公共子串Z，o这就与 长度为k的Z是X和Y的LCS相矛盾了。因此一定有zk-l=xm-l=yn-lo既然zk-l=xm-l=yn-l,那如果我们删除zkT(xmT、ynT)得到 的Zk-1, Xm-l和Yn-1,显然Zk-1是Xm-1和Yn-1的一个公共子串， 现在我们证明Zk-1是Xm-1和Yn-1的LCS。用反证法不难证明。假 设有Xm-1和Yn-1有一个长度超过k-1的公共子串W,那么我们把加 到W中得到,那W就是X和Y的公共子串，并且长度超过k, 这就和已知条件相矛盾了。2. 还是用反证法证明。假设Z不是Xm-l和Y的LCS,则存在一 个长度超过k的W是Xm-1和Y的LCS,那W肯定也X和Y的公共子 串，而已知条件中X和Y的公共子串的最大长度为k。矛盾。3. 证明同2。有了上面的性质，我们可以得出如下的思路：求两字符串Xm=(xO, xl, xm-1)和 Yn=yO,yl,ynT的 LCS,如果 xm-l=yn-l,那么只 需求得XmT和Yn-1的LCS,并在其后添加xm-1 (ynl)即可;如果xmT 尹yn-1,我们分别求得Xm-1和Y的LCS和Yn-1和X的LCS,并且这 两个LCS中较长的一个为X和Y的LCS。如果我们记字符串Xi和Yj的LCS的长度为ci,j,我们可以/ 0 if i0 or j=0 and xi=xj max（ci,j if i,j=0 and xiKxj上面的公式用递归函数不难求得。但从前面求Fibonacci第n 项（本面试题系列第16题）的分析中我们知道直接递归会有很多重复 计算，我们用从底向上循环求解的思路效率更高。为了能够采用循环求解的思路，我们用一个矩阵（参考代码中的 LCS_length）保存下来当前已经计算好了的当后面的计算需 要这些数据时就可以直接从矩阵读取。另外，求取ci,j可以从 ciT,jT、ci, jT或者ciT,j三个方向计算得到,相当于在 矩阵 LCS_length 中是从 ciT, jT, ci, jT或者 ciT,j的某 一个各自移动到ci,j,因此在矩阵中有三种不同的移动方向：向 左、向上和向左上方，其中只有向左上方移动时才表明找到LCS中的 一个字符。于是我们需要用另外一个矩阵（参考代码中的 LCS_direction）保存移动的方向。参考代码如下：ttinclude string. hM/ directions of LCS generationenum decreaseDir （klnit = 0, kLeft, kUp, kLeftUp；/ Get the length of two stringsr LCSs, and print one of the LCSs/ Input： pStrl - the first string/ pStr2 - the second string/ Output: the length of two strings1 LCSs/ /int LCS(char* pStrl, char* pStr2)(if(IpStrl | !pStr2)return 0；size_t lengthl = strlen(pStrl)；size_t length2 = strlen(pStr2)；if(!lengthl | !Iength2)return 0；size_t i, j；/ initiate the length matrixint *LCS_length；LCS_length = (int*)(new intlengthl)；for(i = 0； i lengthl； + i)LCS_lengthi = (int*)new intlength2； for(i = 0； i lengthl； + i) for(j = 0； j length2； + j)LCS_lengthij = 0；/ initiate the direction matrixint *LCS_direction；LCS_direction = (int*)(new intlengthl)；for( i = 0； i lengthl； + i)LCS_directioni = (int*)new intlength2； for(i = 0； i lengthl； + i)for(j = 0； j length2； + j)LCS_directionij = klnit；for(i = 0； i lengthl； + i)(for(j = 0； j m_pNext；/ if the next node is null, the currect is the end oforiginal/ list, and its the head of the reversed listif(pNext = NULL)pReversedHead = pNode；/ reverse the linkage between nodespNode-m_pNext = pPrev；/ move forward on the the listpPrev = pNode；pNode = pNext；8. 微型计算机键盘上的Tab键是DA. 退格键B. 控制键C. 交替换档键D. 制表定位键9. 下列四种软件中，属于系统软件的是CA. WPSB. WordC. DOSD. Excel310. “计算机辅助制造”的常用英文缩写是DA. CADB. CAIC. CATD. CAM11. 在Word的编辑状态，选择了一个段落并设置段落的“首行缩 进设置为1厘米，则AA. 该段落的首行起始位置距页面的左边距1厘米B. 文档中各段落的首行只由“首行缩进确定位置C. 该段落的首行起始位置距段落的“左缩进位置的右边1厘米D. 该段落的首行起始位置在段落“左缩进”位置的左边1厘米12. 在Word的编辑状态，打开了 “wl.doc文档，把当前文档以return pReversedHead；扩展：本题也可以递归实现。习题7用两个栈实现队列题目：某队列的声明如下：template class CQueuepublic：CQueue () )CQueue() (void appendTail (const T& node) ； / append a element to tailvoid deleteHeadO； / remove a element from head private：Tm_stackl；Tm_stack2；);分析：从上面的类的声明中，我们发现在队列中有两个栈。因此 这道题实质上是要求我们用两个栈来实现一个队列。相信大家对栈和 队列的基本性质都非常了解了：栈是一种后入先出的数据容器，因此 对队列进行的插入和删除操作都是在栈顶上进行；队列是一种先入先 出的数据容器，我们总是把新元素插入到队列的尾部，而从队列的头部删除元素。我们通过一个具体的例子来分析往该队列插入和删除元素的过 程。首先插入一个元素a,不妨把先它插入到m.stacklo这个时候 m_stackl中的元素有a, m_stack2为空。再插入两个元素b和c, 还是插入到m_stackl中，此时m_stackl中的元素有a,b,c, m_stack2中仍然是空的。这个时候我们试着从队列中删除一个元素。按照队列先入先出的 规则，由于a比b、c先插入到队列中，这次被删除的元素应该是a。 元素a存储在m_stackl中，但并不在栈顶上，因此不能直接进行删 除。注意到m_stack2我们还一直没有使用过，现在是让m_stack2 起作用的时候了。如果我们把m_stackl中的元素逐个pop出来并 push进入m_stack2,元素在m_stack2中的顺序正好和原来在 m_stackl中的顺序相反。因此经过两次pop和push之后，m_stackl 为空，而m_stack2中的元素是c,b,a。这个时候就可以pop出 m_stack2 的栈顶 a 了。pop 之后的 m_stackl 为空，而 m_stack2 的 元素为c,b,其中b在栈顶。这个时候如果我们还想继续删除应该怎么办呢?在剩下的两个元 素中b和c, b比c先进入队列，因此b应该先删除。而此时b恰好 又在栈顶上，因此可以直接pop出去。这次pop之后，m_stackl中 仍然为空，而m_stack2为c。从上面的分析我们可以总结出删除一个元素的步骤：当 m_stack2中不为空时，在m_stack2中的栈顶元素是最先进入队列的元素，可以pop出去。如果m_stack2为空时，我们把m_stackl中的 元素逐个pop出来并push进入m_stack2o由于先进入队列的元素被 压到m_stackl的底端，经过pop和push之后就处于m_stack2的顶 端了，又可以直接pop出去。接下来我们再插入一个元素do我们是不是还可以把它push进 m.stackl?这样会不会有问题呢?我们说不会有问题。因为在删除元素 的时候，如果m_stack2中不为空，处于m_stack2中的栈顶元素是最 先进入队列的，可以直接pop；如果m_stack2为空，我们把m_stackl 中的元素pop出来并push进入m_stack2o由于m_stack2中元素的 顺序和m_stackl相反，最先进入队列的元素还是处于m_stack2的栈 顶，仍然可以直接pop。不会出现任何矛盾。习题8把字符串转换成整数题目：输入一个表示整数的字符串，把该字符串转换成整数并输 出。例如输入字符串”345”，则输出整数345。分析：这道题尽管不是很难，学过C/C+语言一般都能实现基本 功能，但不同程序员就这道题写出的代码有很大区别，可以说这道题 能够很好地反应出程序员的思维和编程习惯，因此已经被包括微软在 内的多家公司用作面试题。建议读者在往下看之前自己先编写代码, 再比较自己写的代码和下面的参考代码有哪些不同。首先我们分析如何完成基本功能，即如何把表示整数的字符串正 确地转换成整数。还是以”345”作为例子。当我们扫描到字符串的第一个字符3时，我们不知道后面还有多少位，仅仅知道这是第一位, 因此此时得到的数字是3O当扫描到第二个数字4时，此时我们已 经知道前面已经一个3 了，再在后面加上一个数字4,那前面的3相 当于30,因此得到的数字是3*10+4=34o接着我们又扫描到字符5, 我们已经知道了5的前面已经有了 34,由于后面要加上一个5,前 面的34就相当于340 了，因此得到的数字就是34*10+5=345o分析到这里，我们不能得出一个转换的思路：每扫描到一个字符, 我们把在之前得到的数字乘以10再加上当前字符表示的数字。这个 思路用循环不难实现。由于整数可能不仅仅之含有数字，还有可能以+ 或者开头, 表示整数的正负。因此我们需要把这个字符串的第一个字符做特殊处 理。如果第一个字符是+号，则不需要做任何操作;如果第一个字符 是-号，则表明这个整数是个负数，在最后的时候我们要把得到的 数值变成负数。接着我们试着处理非法输入。由于输入的是指针，在使用指针之 前，我们要做的第一件是判断这个指针是不是为空。如果试着去访问 空指针，将不可避免地导致程序崩溃。另外，输入的字符串中可能含 有不是数字的字符。每当碰到这些非法的字符，我们就没有必要再继 续转换。最后一个需要考虑的问题是溢出问题。由于输入的数字是以 字符串的形式输入，因此有可能输入一个很大的数字转换之后会超过 能够表示的最大的整数而溢出。现在已经分析的差不多了，开始考虑编写代码。首先我们考虑如何声明这个函数。由于是把字符串转换成整数，很自然我们想到：int StrToInt (const char* str)；这样声明看起来没有问题。但当输入的字符串是一个空指针或者 含有非法的字符时，应该返回什么值呢?0怎么样?那怎么区分非法输 入和字符串本身就是” 0”这两种情况呢？接下来我们考虑另外一种思路。我们可以返回一个布尔值来指示 输入是否有效，而把转换后的整数放到参数列表中以引用或者指针的 形式传入。于是我们就可以声明如下：bool StrToInt(const char *str, int& num)；这种思路解决了前面的问题。但是这个函数的用户使用这个函数 的时候会觉得不是很方便，因为他不能直接把得到的整数赋值给其他 整形变脸，显得不够直观。前面的第一种声明就很直观。如何在保证直观的前提下当碰到非 法输入的时候通知用户呢?一种解决方案就是定义一个全局变量，每 当碰到非法输入的时候，就标记该全局变量。用户在调用这个函数