转发迅雷2010校园招聘吉林大学第二次笔试题

scudong

迅雷2010校园招聘吉林大学第二次笔试题

答题时间: 2小时，请将答案写在答题纸上
一． 有n个文件的长度记载在一个无符号64 位整数数组中unsigned __int64 file_length[n]，把这n 个文件从逻辑上按序首尾拼接在一起形成一个逻辑上的大文件，然后以每块长度为unsigned block_length把这个逻辑上的大文件划分成大小相等的数据块（当然，最后一块有可能比block_length小），请定义和实现一个函数，把边界块的序号集合返回给函数的调用者（第一个数据块序号为0）。
注：边界块指的是跨多个文件的数据块。（30分）


二． 请实现一个函数，把两个从大到小的有序链表合并成一个链表，新的链表是一个从小到大的有序链表。
struct list
{
int value;
list* next;
};
list * merge (list *list1_head, list *list2_head);
(30分)


三． 如果两个英文单词，组成它们的字符集合相同，而且相同字符出现的次数也相同，则称这两个词匹配：比如说：同”abbc”与词”babc”是匹配的。有一个词典，存储在字符串数组const char* dictionary[n]中，数组的每一个元素是一个词。对于任意给出的句子。句子中的单词使用空格分割。请实现以下函数，判断句子中是否有词和词典中的词匹配。
bool is_matching( const char* dictionary[], int n, const char* sentence);
(40分)


注意：这一题需要先描述思路，再写程序，没写思路扣10分。


本文来自CSDN博客，转载请标明出处：http://blog.csdn.net/morre/archive/2009/09/01/4509390.aspx

OwnWaterloo

原帖由 scudong 于 2009-9-2 11:55 发表
unsigned __int64 file_length[n]

哟，迅雷雷是用vc开发的嘛

DQP

刚9月2号。 迅雷下手好早啊

aaaaa5aa

我搞下来慢慢研究

fuxiazhouxin

三． 如果两个英文单词，组成它们的字符集合相同，而且相同字符出现的次数也相同，则称这两个词匹配：比如说：同”abbc”与词”babc”是匹配的。有一个词典，存储在字符串数组const char* dictionary[n]中，数组的每一个元素是一个词。对于任意给出的句子。句子中的单词使用空格分割。请实现以下函数，判断句子中是否有词和词典中的词匹配。
bool is_matching( const char* dictionary[], int n, const char* sentence);
(40分)


俺的思路：
将字典中每个词按ascii码值相加作成哈希表，同时将字典中每个词包含的字母及字母个数统计到一个数据结构中，
对于每个句子，先分割出每个单词后，将每个单词首先计算出对应的哈希key值，然后通过定义好的数据结构来判断是否是匹配的词

ajianglaoka

第3题

把所有单词按照字母顺序排序，作为索引。
若两个词匹配，则索引相同。
索引相同，则两个词匹配。

这个 好像 在 编程珠玑  的里第二章出现过，它叫 “变位词”

jklei

和你思路类似。
不过我感觉如果给每个字母分配一个素数，计算各个字母的乘积就不会产生冲突。可以对于前26个素数，按照现有文献对于字母频率的统计，高频分配小素数，低频分配大素数。
这个想法的问题在于有可能乘积很大，涉及到大数乘积就很麻烦了。例如一个单词20个字母的话，这个值有可能就很大。

[ 本帖最后由 jklei 于 2009-9-2 16:15 编辑 ]

szjrabbit

都已经第二次笔试了啊？迅雷也太早了吧

hsc_hao

有好想法的最好把代码也贴进来，大家共同学习一下，呵呵。。

ispexceed

这个是第2题的实现，还有测试的样例。

#include <stdio.h>
#include <stdlib.h>

#define N 3
#define M 4

struct list
{
        int value;
        list *next;
};

list *merge(list *list1_head, list *list2_head);

list *insert_back(list *head, int value);
list *insert_front(list *head, int value);
void print_list(list *head);

int main()
{
        list *head1 = NULL, *head2 = NULL, *head3 = NULL;
        int x1[ N ] = { 9, 7, 5 };
        int x2[ M ] = { 8, 6, 4, 1 };
        int i;

        for (i = 0; i < N; ++i)
        {
                head1 = insert_back(head1, x1[ i ]);    // 这个是x1 [ i ] 有i下标的，显示时竟然显示不出来
        }

        for (i = 0; i < M; ++i)
        {
                head2 = insert_back(head2, x2[ i ]);    // 这个是x2 [ i ] 有i下标的，显示时竟然显示不出来
        }

        head3 = merge(head1, head2);

        print_list(head3);
       
        return 0;
}

list *merge(list *list1_head, list *list2_head)
{
        list *p1 = list1_head, *p2 = list2_head, *q = NULL;

        while (p1 != NULL && p2 != NULL)
        {
                if (p1->value >= p2->value)
                {
                        q = insert_front(q, p1->value);
                        p1 = p1->next;
                }
                else
                {
                        q = insert_front(q, p2->value);
                        p2 = p2->next;
                }
        }

        if (p1 == NULL && p2 != NULL)
        {
                while (p2 != NULL)
                {
                        q = insert_front(q, p2->value);
                        p2 = p2->next;
                }
        }

        if (p2 == NULL && p1 != NULL)
        {
                while (p1 != NULL)
                {
                        q = insert_front(q, p1->value);
                        p1 = p1->next;
                }
        }

        return q;
}

list *insert_back(list *head, int value)
{
        list *p = head, *q;

        q = (list *) malloc(sizeof(list));
        q->value = value;
        q->next = NULL;

        if (p == NULL)
        {
                head = q;
                return head;
        }

        while (p->next != NULL)
        {
                p = p->next;
        }

        p->next = q;

        return head;
}

list *insert_front(list *head, int value)
{
        list *p = head, *q;
       
        q = (list *) malloc(sizeof(list));
        q->value = value;

        if (p == NULL)
        {
                q->next = NULL;
                head = q;
                return head;
        }
        else
        {
                q->next = head;
                head =q;
                return head;
        }
}

void print_list(list *head)
{
        list *p = head;
       
        while (p != NULL)
        {
                printf("%d\n", p->value);

                p = p->next;
        }
}

[ 本帖最后由 ispexceed 于 2009-9-10 14:23 编辑 ]