`
talin2010
  • 浏览: 512910 次
  • 性别: Icon_minigender_1
  • 来自: 河北
社区版块
存档分类
最新评论

算法和数据结构试题

阅读更多

---------------------------------------------------------------------------

1. 二叉排序树和哈希表那个查找效率高。

普遍而言,哈希表更快。但要看具体情况。
二叉排序树的查找复杂度一般为 O(logn)。但如果退化为链表,则复杂度为 O(n)。
哈希表的查找速度要看哈希函数,一般为 O(1)。但如果哈希表容量太小,或者哈希函数很容易导致冲突,将大大降低查找速度。极端情况下,哈希表的容量为 1,或者所有元素都被映射到哈希表中的同一项,此时哈希表也退化为链表,复杂度也为 O(n)。

---------------------------------------------------------------------------


2. 在一个已经排好序的数组里面把重复的值删除掉。

思路:用两个指针,前面的指针如果发现当前项和下一项值不同的话,就把下一项的值拷贝到后面指针的下一项中,两个指针同时后移;如果发现当前项和下一项值相同的话,前指针就向下移动,后指针不动。

#include <stdio.h>

int deduplicate(int arr[], int n)
{
int count;
int * tmp = arr;
int * end = arr + n - 1;

if (!arr)
{
return 0;
}

count = 0;
while (tmp != end)
{
if (*tmp != *(tmp + 1))
{
*arr++ = *tmp;
++count;
}
++tmp;
}

/*
* 如果 n=1,则 while 循环一次都没有执行,这里是复制数组中唯一的一个元素;
* 如果最后两个元素相等,则这里是复制最后相等的那个元素
* (在 while 循环中没有被复制);
* 如果最后两个元素不等,则这里是复制最后那个不等的元素。
*/
*arr = *end;
++count;

return count;
}

int main(int argc, char * argv[])
{
int i;
int arr1[] = {1};
int arr2[] = {1, 2, 2, 3, 3, 3, 4, 4, 4, 4, 5, 5, 5, 5, 5};
int arr3[] = {1, 2, 2, 3, 3, 3, 4, 4, 4, 4, 5, 5, 5, 5, 5, 6};
int len;

/* 测试只有一个元素的情况。 */
len = deduplicate(arr1, sizeof(arr1) / sizeof(arr1[0]));
printf("Length after deduplicate: %d\n", len);
for (i = 0; i < len; ++i)
{
printf("%d ", arr1[i]);
}
printf("\n");

/* 测试最后两个元素相同的情况。 */
len = deduplicate(arr2, sizeof(arr2) / sizeof(arr2[0]));
printf("Length after deduplicate: %d\n", len);
for (i = 0; i < len; ++i)
{
printf("%d ", arr2[i]);
}
printf("\n");

/* 测试最后两个元素不同的情况。 */
len = deduplicate(arr3, sizeof(arr3) / sizeof(arr3[0]));
printf("Length after deduplicate: %d\n", len);
for (i = 0; i < len; ++i)
{
printf("%d ", arr3[i]);
}
printf("\n");

return 0;
}


参考:http://www.it.com.cn/f/edu/0611/9/347299_5.htm

---------------------------------------------------------------------------

3. 在一个循环有序的数组里查找特定值。(循环有序就是指数组里的各项都是有序的,但是最小值不一定是数组的第 0 项,而可能是其中任意一项,然后逐项递增,到数组尾的时候再回到第 0 项)

在这样的数组中查找就不能直接使用二分法了。可以使用一个二分法的变形,除了判断中心值之外,还要判断两端的值,以此确定循环开始点在中点的哪一边,并判断所查找的值是否在循环起始点的哪边,并采用不同的处理方式。

#include <stdio.h>

int mysearch(int arr[], int s, int e, int value)
{
int m = (s + e) / 2;
for (; s < e; m = (s + e) / 2)
{
if (arr[m] == value)
{
return m;
}

/*
* s m e
* 1 2 3
*/
if (arr[s] <= arr[m] && arr[m] <= arr[e])
{
if (value < arr[m])
{
e = m - 1;
}
else
{
s = m + 1;
}
}
/*
* s m e
* 2 3 1
*/
else if (arr[s] <= arr[m] && arr[m] >= arr[e])
{
if (value < arr[m] && value >= arr[s])
{
e = m - 1;
}
else
{
s = m + 1;
}
}
/*
* s m e
* 3 1 2
*/
else
{
if (value > arr[m] && value <= arr[e])
{
s = m + 1;
}
else
{
e = m - 1;
}
}
}
if (arr[s] == value)
{
return s;
}

return -1;
}

int main(int argc, char * argv[])
{
int i;
int arr[] = {70, 80, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
int len = sizeof(arr) / sizeof(arr[0]);

for (i = 0; i < len; ++i)
{
printf("%d\n", mysearch(arr, 0, len - 1, arr[i]));
}

return 0;
}

---------------------------------------------------------------------------

4. 设 S1, S2, ..., Sk 是 k 个集合,每个集合均由 n 个整数组成。设计一个程序将所有的和 { x1+x2+...+xk | xi 属于 Si, i=1,...,k } 从小到大排序。

下面是一个思路,虽然不正确,但可以参考一下。先在这放着,等想出来了再更新。
(不正确的原因:请考虑 S1 = {0, 4, 5}, S2 = {1, 3, 6} 的情况)

把所有和按从小到大的顺序找出。

对每个集合先排序,定义 k 个指针 p1, p2, ..., pk。它们初始指向 k 个集合的最小元素。下面用 Sipi 表示 pi 在 Si 中指向的元素, pi+1 表示 pi 的下一个元素,(1<=i<=k)

最小元素是 A:A = S1p1 + S2p2 + ... + Skpk
1. 在 p1+1, p2+1, ..., pk+1 中找出使得 pi+1 - pi (1<=i<=k) 最小的元素,假设是 pj+1。
2. 更新 pj 的值:pj=pj+1
则此时的新和:S1p1 + S2p2 + ... + Sjpj + ... + Skpk 是比 A 大的最小元素

重复步骤 1 和 2 直到所有指针都指向集合的最后一个元素 (此时找到的必然是所有和中的最大值)。


参考:http://topic.csdn.net/t/20051004/13/4307070.html

---------------------------------------------------------------------------

5. 去掉整型数组中的重复数字。要求结果保留原数组的顺序。

思路一:
将原数组的下标值存在一个辅助数组中 (也就是说辅助数组为 {0, 1, 2, 3, ...})。然后根据下标指向的值对辅助数组排序,对排序后的辅助数组去重 (也是根据下标指向的值)。然后再按下标本身的值对去重后的辅助数组排序。之后顺次读出剩下的各下标指向的值即可。
例如:原数组为 {1, 2, 0, 2, -1, 999, 3, 999, 88},则辅助数组为 {0, 1, 2, 3, 4, 5, 6, 7, 8},对辅助数组按下标指向的值排序的结果为 {4, 2, 0, 1, 3, 6, 8, 5, 7},对辅助数组按下标指向的值去重的结果为 {4, 2, 0, 1, 6, 8, 5},对辅助数组按下标本身排序的结果为 {0, 1, 2, 4, 5, 6, 8},最后得到的结果为 {1, 2, 0, -1, 999, 3, 88}。
复杂度分析:主要的时间在两次排序,所以时间复杂度为 O(NlogN)。

思路二:
利用平衡二叉树。一开始建立一棵空平衡二叉树。然后顺次读取源数组,每读出一个整数,就在该平衡二叉树中查找该整数,若找到,则读取下一个整数,若找不到,则输出该整数,并将该整数插入到平衡二叉树中。
复杂度分析:平衡二叉树的插入和查找都是 O(logN) 的,所以总的时间复杂度为 O(NlogN)。
STL 中的 set 就是利用平衡二叉树实现的。下面是利用 set 的一个实现:

#include <iostream>
#include <set>

using namespace std;

int main(int argc, char * argv[])
{
set<int> p;
int array[] = {1, 2, 0, 2, -1, 999, 3, 999, 88};
int len = sizeof(array) / sizeof(array[0]);
int i;
cout << array[0];
p.insert(array[0]);
for (i = 1; i < len; ++i)
{
if (p.find(array[i]) == p.end())
{
p.insert(array[i]);
cout << " ," << array[i];
}
}
cout << endl;
p.clear();

return 0;
}


参考:http://community.csdn.net/Expert/TopicView3.asp?id=5603029

---------------------------------------------------------------------------

分享到:
评论

相关推荐

    算法与数据结构考研试题精析

    标题《算法与数据结构考研试题精析》和描述“算法与数据结构历年考研试题分析与答案解析。主要就是拿来练练手”表明本文将深入探讨算法与数据结构的核心知识点,并通过历年考研试题的形式加以练习和巩固。由于提供的...

    算法与数据结构考研试题精析第3版

    《算法与数据结构考研试题精析》收集了自1992年以来国内60余所重点高校和科学院、所300多套硕士研究生入学“算法与数据结构”考试试卷的1600多道试题,并给出了参考答案和分析。《算法与数据结构考研试题精析》可以...

    算法和数据结构试题(卷)与答案解析.doc

    【算法和数据结构试题(卷)与答案解析】 算法和数据结构是计算机科学中的核心概念,它们涉及到如何高效地处理和存储数据。本文件提供的是一份关于算法和数据结构的试题,涵盖了多个知识点: 1. **栈和队列**: - ...

    算法与数据结构考研试题精析(第三版)

    该书除了包含大量的算法和数据结构知识点讲解外,还提供了1800题的考研试题分析,帮助考生在备考研究生入学考试时能够更好地掌握这两门课程的核心内容和解题技巧。 算法与数据结构是计算机科学与技术专业的核心课程...

    算法与数据结构考研试题精析(第二版).

    《算法与数据结构考研试题精析(第二版)》是一本专为准备计算机科学研究生入学考试的学生设计的教材。本书涵盖了算法与数据结构的核心概念,旨在帮助学生深入理解和掌握这两个关键领域的知识。作为"1800题"的第二版,...

    算法与数据结构考研试题精析【第3版】【书签完整】

    《算法与数据结构考研试题精析》第三版是针对计算机科学与技术专业研究生入学考试的一本重要参考资料。这本书深入浅出地讲解了算法与数据结构的基础理论和实践应用,旨在帮助考生全面掌握这一核心领域的知识。书签...

    算法与数据结构考研试题精析(第二版)

    《算法与数据结构考研试题精析(第二版)》是一本专门为考研学子准备的教材,主要涵盖了算法和数据结构这两个核心计算机科学领域的知识。这本书不仅提供了详细的理论解析,还附带了源代码答案,帮助读者深入理解并掌握...

    算法与数据结构(C语言)试题与答案

    其次,“数据结构试题.doc”可能包含了更多复杂的题目,可能会涉及排序算法(如冒泡排序、快速排序、归并排序)和查找算法(如顺序查找、二分查找)。这些算法是解决实际问题的基础,通过这些题目,你可以锻炼自己的...

    算法与数据结构考研试题精选

    《算法与数据结构考研试题精选》是一本专为准备计算机科学与技术专业研究生入学考试的考生量身定制的复习资料。这份压缩包包含了1800道精心挑选的考研试题,覆盖了全国各地高校数据结构考试的重点和难点。通过这份...

    算法与数据结构 习题答案共十二套

    这份压缩包中包含了十套算法与数据结构的常规习题以及两套模拟试题,特别强调了模拟题的重要性,可能是因为它们能更好地检验学习者的综合应用能力和应试技巧。 1. **算法**:算法是解决问题的步骤或计算过程,是...

    算法与数据结构考研试题精析_第二版

    通过解析历年考研真题,本书旨在帮助学生深入理解算法与数据结构的基本概念,掌握算法分析与设计的方法,以及数据结构的选择与应用。以下是基于该书部分内容的知识点归纳: ### 算法的复杂度 1. **算法的计算量**...

    算法与数据结构考研试题精析 1800题

    《算法与数据结构考研试题精析 1800题》是一本专为准备考研的学子精心编纂的复习资料,涵盖了数据结构和算法两大核心主题。数据结构是计算机科学的基础,而算法则是解决问题的核心工具,这两部分知识在考研中占据着...

    算法与数据结构考研试题精析第二版.rar

    通过《算法与数据结构考研试题精析第二版》,读者不仅能学习到基本的算法和数据结构知识,还能了解如何将这些知识应用于实际问题,提升分析问题和解决问题的能力。在复习过程中,结合历年真题进行实战演练,对提高...

    算法与数据结构考研试题精析 第3版

    数据结构1800题 数据结构1800题

    武汉大学 C#数据结构与算法

    《武汉大学 C#数据结构与算法》是一门深入探讨计算机科学基础的课程,主要针对C#编程语言,涵盖了数据结构和算法这两个核心概念。在学习这门课程时,你将有机会掌握C#语言如何用于实现高效的数据管理和计算方法。 1...

Global site tag (gtag.js) - Google Analytics