［程序员日记］编程题

2017-06-20 本文已影响381人 KeyLiu7

前言：这是曾经公司的笔试题，现在做起来仍很有意思，遂分享出来，感兴趣的一起来挑战吧！

1.在最短的计算时间和最小的存储空间限制下完成下面这函数：

void reverse_words(char *sentence)
//
// 输入串: 一个以空格分隔的字符串，字符串中只包含英文字母和空格
// 输出串: 一个与输入完全颠倒的字符串，但每个单词保持原样
//
// 例子: 
//
//     char test[]= "Now is the winter of our discontent made glorious summer by this son of York";
//
//     reverse_words(test);
//
//     printf(“%s\n”, test);
//
// 输出结果:
//
//     York of son this by summer glorious made discontent our of winter the is Now

注意事项：

比如说一个需要O(n)计算时间和O(1)存储空间的算法要比一个需要O(n^2)计算时间和O(n)存储空间的算法要好。
你可以用任何ANSI C库里的字符串函数来解决问题。

2.已知一个数据结构：

struct s_node
{
    struct s_node *next;
    struct s_node *reference;
};

在最短的时间和最小的空间限制下完成下面这函数：

struct s_node *duplicate_list(struct s_node *list)
//
// 输入: 一个单项链接的列表，每个节点都包含该链表中随机的一个节点的引用
// 输出: 一个输入链表一摸一样的链表，并且输出链表中的任何一个节点都和输入链表不相关

注意事项：

比如说一个需要O(n)计算时间和O(1存储空间)空间的算法要比一个需要O(n^2)计算时间和O(n)存储空间的算法要好。
你可以在计算过程中修改原始链表，只要你能在算法完成时恢复原始链表就好。
最终得到的链表必须符合链表原始的数据结构定义，并且必须在一个与原始链表分离的内存空间。

3.写一个函数来找到Boggle填字游戏中的所有单词。

如果你不知道什么是Boggle，你可以先baidu或者google一下，他们会解释得比我清楚，但我在这里还是以例子解释下：

比如说一个3x3的Boggle表：

y o x
r b a
v e d

根据规则你可以把相邻的字母在不重复的情况下串联起来组成单词，比如说：

bred, yore, byre, abed, oread, bore, orby, robed, broad, byroad, robe
bored, derby, bade, aero, read, orbed, verb, aery, bead, bread, very, road

但是robbed或者rober不在其中，因为他们需要重新用到Boggle表中的字母。board和dove也不在其中，因为他们需要不相邻的字母。

#define MAX_ROWS 3
#define MAX_COLUMNS 3
#define MAX_WORDS 27
#define MAX_WORD_LENGTH MAX_ROWS*MAX_COLUMNS
#define MIN_WORD_LENGTH 4

typedef struct
{
    char letter[MAX_ROWS][MAX_COLUMNS];
}
BoggleBoard;

typedef struct
{
    char *words[MAX_WORDS];
    int numberOfWords;
}
Dictionary;

void BoggleSover(int rows, int columns, BoggleBoard *boggleBoard, char ** dictionary,Dictionary* answer)

4.分别列出数组(array)和链表(list)的优缺点。

5.面向对象编程出现之后，继承这种设计模式被越来越多的应用于软件工程当中。但现在却有人提出要少用继承多用组合这种设计模式，这是为什么呢？

6.下面这个陈述是正确的吗？为什么？

我们知道TCP是一种面向连接的、可靠的、基于字节流的传输层通信协议，所以每当传输层通过TCP协议向另一端发出一个包，另一端的传输层就一定会收到完整并且顺序正确的包，要么就整包都没有收到。

答案后续更新

［程序员日记］编程题

猜你喜欢

热点阅读