`
- 浏览:
16048721 次
- 性别:
- 来自:
济南
-
---------------------------------------------------------------------------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---------------------------------------------------------------------------
分享到:
Global site tag (gtag.js) - Google Analytics
相关推荐
《算法与数据结构考研试题精析》收集了自1992年以来国内60余所重点高校和科学院、所300多套硕士研究生入学“算法与数据结构”考试试卷的1600多道试题,并给出了参考答案和分析。《算法与数据结构考研试题精析》可以...
算法与数据结构历年考研试题分析与答案解析。主要就是拿来练练手
算法和数据结构试题(卷)与答案解析.doc
算法与数据结构考研试题精析(第二版)书和源代码答案
算法与数据结构考研试题精析【第3版】【书签完整】.zip
数据结构与算法考试复习试题和答案,很全面的试题和答案,考试必过
算法与数据结构考研试题精析(第二版) 传说中的1800题第二版
数据结构1800题 数据结构1800题
主要有以下的课件和pdf 1.杭州电子科技大学数据结构 2.数据结构-林大 ...4.数据结构-试题库 算法与数据结构_严蔚敏版_全部课件.ppt 数据结构与算法(JAVA语言版).pdf 数据结构与算法(JAVA语言版解密).pdf等
其实1800题是2001年推出来的,当时编者把电子版免费分享给大家,却很少有人知道它也有纸质版本就是《算法与数据结构考研试题精析》。第二版是2007年最新出版的,对里面的题目进行了大量的更新,去掉了一些比较过时和...
《高等院校计算机教材系列•算法与数据结构C语言版(第2版)》收集了自1992年以来国内60余所重点高校和科学院、所300多套硕士研究生入学“算法与数据结构”考试试卷的1600多道试题,并给出了参考答案和分析。...
数据结构和算法的的考研试题,你可以从中检验自己的数据结构和算法的掌握情况!
算法与数据结构考研试题精析第二版.rar算法与数据结构考研试题精析第二版.rar
本资源包括数据结构复习样题,往年试卷,数据结构试题三个文件,加上有详细解答,对于算法与数据结构的学习和备考都有帮助。