2009年 金山笔试试题

注意：共8题，答题时间为2.5小时；程序题请说明解题思路，这个非常重要。

 

一、在C语言的for循环中，break和continue有什么区别。

 

二、请列举三种你最熟悉的排序算法，并说明它们的时间复杂度是多少。

 

三、请用位移和加法改写表示式：a * 36;

 

四、有如下一棵二叉树，请写出它的前序遍历、中序遍历和后续遍历的结果。

      A

     /  \

    B   C

  /   \    \

 D   E    F

 

五、有如下两段代码：

代码一：

#define MaxRow  10

#define MaxCol   10

void TestFunc_1()

{

char** pArr = NULL;

pArr = new char*[MaxRow];

for (int i = 0; i < MaxRow; i++)

pArr[i] = new char[MaxCol];

...... // 对pArr的使用代码

}

代码二：

#define MaxRow 10

#define MaxCol  10

void TestFunc_2()

{

char Arr[MaxRow][MaxCol];

...... // 对Arr 的使用代码；

}

请对比分析代码一和二的优劣;

计算代码一和二的内存实际占用的字节数是多少;

代码一还不完整，请指出存在的问题，并补全必要的代码。

 

六、按要求编写以下函数。

函数声明：int ChangeToTail(BYTE* pSz, UINT nSize)

功能 ：将给定缓冲区中的#字符移到字符串尾部

入口参数：pSZ指向缓冲区的指针, nSize缓冲区长度

出口 ：pSZ所指缓冲区中的#字符被移到缓冲区尾部

返回值 ：在出口缓冲区中第一个#的位置,若缓冲区中无#字符则返回-1

说明 ：如传入(#W#W#W#WW#， 10) 则传出时应转换为WWWWW#####并且返     回值为5

 

七、给定一个介于0与1之间的小数，以及分母的最大位数（1-6位）。请构造一个程序，寻找分母在指定位数之内，与给定小数最接近的分子——分母对（显然，分子、分母须为整数）。例如，黄金分割比0.618...，分母限定为2位时，最接近的分数为55/89；分母限定为3位时，为 610/987。

 

八、有一个双向循环链表，它的节点定义如下：

struct Node

{

int data;

Node* pPre;

Node* pNext;

}

请实现一个函数完成把链表中等于指定值的节点都删除掉。函数声明如下

Node* DeleteNode(Node* pCurNode, const int delData);