恒生电子笔试题3

恒生电子笔试题

Pay attention: Don't answer on the sheet, please answer on the blank answer-sheet.

1. Specify what does “func()” do with the list "ppList", and what are the errors.

struct NODE { int nValue; struct NODE* pLeft; struct NODE* pRight; };

struct NODE_LIST { const struct NODE* pNode; struct NODE_LIST* pNext; };

struct NODE_LIST* sub_func(const struct NODE* pTree, struct NODE_LIST* pList) { if (pList == NULL) { pList = malloc(sizeof(struct NODE_LIST)); if (pList == NULL) { return 0; } pList->pNode = pTree; pList->pNext = NULL; return pList; } else { while (pList->pNext) { pList = pList->pNext; } pList->pNext = malloc(sizeof(struct NODE_LIST)); if (pList->pNext == NULL) { return 0; } pList->pNext->pNode = pTree; pList->pNext->pNext = NULL; return pList->pNext; } }

int func(const struct NODE* pTree, struct NODE_LIST** ppList) { int nNum = 0; if (pTree == NULL) {

恒生电子笔试题

return nNum; } else { struct NODE_LIST* pNew = sub_func(pTree, *ppList); int nTemp = 0; if (pTree->pLeft != NULL) { nTemp += func(pTree->pLeft, &pNew); if (pNew == NULL) { return -1; } } if (pTree->pRight != NULL) { nTemp += func(pTree->pRight, &pNew); if (pNew == NULL) { return -1; } } return nTemp + 1; } }

2. please complete the standard C function: memmove(), here is the description ():

void * memmove (void *to, const void *from, unsigned int size)

memmove copies the size bytes at from into the size bytes at to. The value returned by memmove is the value of to.

3. Given a decimal number, return the number in string of specified base (The base of a system of numbers, such as 2 in the binary system and 10 in the decimal system). The base is bigger than 1 and less than 10. For example, the given number is 99 in decimal, and return string “143” of base 8 (char* GetNumber(unsigned int nNum, unsigned int nBase) { }

4. Find a path from start position to end position in maze. The maze's width is 8, and height is 8 too, it is expressed by an two-dimensional array, the start position of it is left-up corner and its coordinate is (0, 0), and the end position is right-down corner and coordinate (7, 7). Each integer element in array defines connectivity of a block, 0 if disconnected, others

connected. For example, a path is painted in different color in the following maze expressed

恒生电子笔试题

of actual code), the array "maze" is the map of a maze, the size is 8*8. Save found path in "maze" before function return non-zero, if you find. And return 0 if there is no path which can reach end point. The returned "maze" shall be cleared with "0" except the path, as

int path(int maze[8][8]);

恒生电子笔试题

1. 说明函数"func"对 链表"ppList"做了什么，并指出其中可能的错误。

先序遍历二叉树的方式将树转化为链表。（答不出“先序”也没关系）

struct NODE { int nValue; struct NODE* pLeft; struct NODE* pRight; };

struct NODE_LIST { const struct NODE* pNode; struct NODE_LIST* pNext; };

struct NODE_LIST** sub_func(const struct NODE* pTree, struct NODE_LIST** ppList) { if (*ppList == NULL) { *ppList = malloc(sizeof(struct NODE_LIST)); if (*ppList == NULL) { return 0; } (*ppList)->pNode = pTree; (*ppList)->pNext = NULL; return ppList; } else { struct NODE_LIST* pList = (*ppList); while (pList->pNext) { pList = pList->pNext; } pList->pNext = malloc(sizeof(struct NODE_LIST)); if (pList->pNext == NULL) { return 0; } pList->pNext->pNode = pTree; pList->pNext->pNext = NULL; return &(pList->pNext); } }

int func(const struct NODE* pTree, struct NODE_LIST** ppList) {

恒生电子笔试题

int nNum = 0; if (pTree == NULL) { return nNum; } else { struct NODE_LIST** pNew = sub_func(pTree, ppList); int nTemp = 0; if (pTree->pLeft != NULL) { nTemp += func(pTree->pLeft, pNew); if (*pNew == NULL) { return -1; } } if (pTree->pRight != NULL) { nTemp += func(pTree->pRight, pNew); if (*pNew == NULL) { return -1; } } return nTemp + 1; } }

2. 请完成标准C函数：memmove()

void *memmove(void *dest, const void *src, size_t count) {

char *tmp; const char *s;

if (dest == NULL || src == NULL) { return NULL; }

if (dest <= src) { tmp = (char *)dest; s = (const char *)src; while (count--) *tmp++ = *s++; } else { tmp = (char *)dest; tmp += count; s = (const char *)src; s += count;

恒生电子笔试题

while (count--) *--tmp = *--s; }

return dest; }

3. 将一个十进制数转换成指定进制，并返回它的字符串表达（系统数字进制，对于二进制系统就是2，十进制系统就是10）。指定的进制比1大比10小。例如，十进制99转换成8进制字符串就是"143"（函数中不可使用任何C标准函数，除了malloc()）。

#include <stdlib.h>

char* GetNumber(unsigned int nNum, unsigned int nBase) {

char* pRet = malloc(33); int* pNum = malloc(33 * 4); int nIndex = 0;

if (pRet == NULL | pNum == NULL) { pRet? free(pRet) : ; pNum? free(pNum) : ; return NULL; }

int nLeft = nNum; int nMod;

while (nLeft > 0) { nMod = nLeft % nBase; nLeft /= nBase; pNum[nIndex++] = nMod; }

int nC = 0;

for (; nC < nIndex; nC++) { pRet[nC] = pNum[nIndex - nC - 1] + '0'; }

pRet[nIndex] = 0;

free(pNum);

return pRet; }

4. 找出可以从开始位置至结束位置通过迷宫的路径。迷宫宽8，高也是8，由一个二维数组表示，开始位置是左上角，坐标(0, 0)，结束位置是右下角，坐标(7, 7)。每个数组元素定义一个方块的连通性，0表示不通，其它表示连通。例如，下表所表示的迷宫中用不同颜色标识了一条路径。

完成以下函数，数组"maze"是迷宫的地图，大小是8*8。将找到的路径保存在"maze"

恒生电子笔试题

中，并返回非0。如果没找到可以到达终点的路径，返回0。返回的"maze"中除了路径之外其它都清空为0。如下表：

struct NODE { int row; int col; int value; struct NODE* pNodes[8]; int nNeighborNum; };

struct PATH { struct NODE* pCur; struct NODE* pNext; };

void init_maze(int maze[8][8], struct NODE maze_map[8][8]) { // save maze info into maze_map }

int check_end(struct NODE* pNode) { // check if the end position is beside }

struct NODE* get_neighbor(struct NODE** pNode, struct PATH cur) { // get neighbor node which has not been checked }

void add_checked_neighbor(struct NODE** pNode, struct NODE* pNeighbor) { // add neighbor node to the checked node list, // the next time get_neighbor() will not choose it }

int path(int maze[8][8]) { struct PATH path[64] = {}; struct NODE maze_map[8][8] = {}; struct NODE* node_examed[64] = {}; init_maze(maze, maze_map); int nCurPath = 0; path[nCurPath].pCur = &maze_map[0][0]; path[nCurPath].pNext = NULL; add_checked_neighbor(node_examed, &maze_map[0][0]);

恒生电子笔试题

while (nCurPath >= 0) { // check if reach end position if (check_end(path[nCurPath].pCur)) { goto SavePath; } // find next neighbor, and continue the next turn search struct NODE* pNextNode = get_neighbor(node_examed, path[nCurPath]); if (pNextNode) { add_checked_neighbor(node_examed, pNextNode); path[nCurPath + 1].pCur = pNextNode; path[nCurPath + 1].pNext = NULL; nCurPath++; } else { nCurPath--; } } return 0;

SavePath: // save found path to "maze" return 1; }

本文来源：https://www.bwwdw.com/article/0llm.html