02笔试题-数据结构部分

if(m=k) break; for(j=j-1,j>m,j--) if(list[j]<=k) break; if(i

main() { int list[10]; int n=9, m=0,i; printf(\ for(i=0;i<10;i++) scanf(\ printf(\ improveqsort(list,m,n); for(i=0;i<10;i++) printf(\ printf(\ }

55.以下哪种排序属于稳定排序？

A) 归并排序 B) 快速排序

); ); C) 希尔排序D) 堆排序 56.用二分法查找一个长度为10的、排好序的线性表，查找不成功时，最多需要比较多少次？ A) 5 B) 2 C) 4 D) 1

57.下面那种排序法对 1234567 最快？

A) quick sort B) bubble sort C) merge sort

58.解释一下什么是哈夫曼编码问题？

59.假设执行语句Q的时间是O（1），则执行下列程序段的时间为（） for(int i = 1;i <= n;i++) for(int j = i; j <= n; j++) Q; A.O(n) B.O(n2) C.O(n*i) D.O(n+1)

61. 一棵有124个叶结点的完全二叉树，最多有（）个结点 A．247 B.248 C.249 D.250

63.下列排序算法中，在待排序数据有序的情况下，花费时间最多的是（） A．快速排序 B.希尔排序 C.冒泡排序 D.堆排序

64.有1000个无序的整数，希望使用最快的方式找出前50个最大的，最佳的选择是（） A.冒泡排序 B.基数排序 C.堆排序 D.快速排序

65.下列哪个不是用来解决哈希表冲突的开放地址法（） A.线性探测法 B.线性补偿探测法 C.拉链探测法 D.随机探测法

66.假设把整数关键码K散列到有N个槽的散列表，以下哪些散列函数是好的散列函数___。

A．h(k)= k/N;

B．h(k)=1; C．h(k)=k mod N;

D．h(k)=(k + Random(N))mod N,random(N)返回一个0到N-1的整数

68.下面算法的时间复杂度是____. int f(unsigned int n) {

if(n==0||n==1) return 1;

else return n*f(n-1); }

A.O(1) B.O(n) C.O(n^2) D.O(n!)

69. 对于一个具有n个顶点的无向图，若采用邻接表表示，则存放表头节点的数组大小为 A.n B.n+1 C.n-1 D.n+边数

70.考虑一个特殊的hash函数h,能将任一字符串hash成一个整数k，其概率为P(k)=2^(-k)。k=1,2?。对一个位未知大小的字符串集合S中的

每一个元素取hash值所组成的集合为h(S)。若h(S)中最大的元素max h(S)=10，那么S的大小的期望是___. A.5 B.10 C.512 D.1024

71.对于顺序存储的线性数组，访问结点和增加，删除结点的时间复杂度为____.

A.O(n),O(n) B.O(n),O(1) C.O(1),O(n) D.O(1),O(1)

75.递归式的先序遍历一个n节点，深度为d的二叉树，需要栈空间的大小为____.

A.O(n) B.O(d) C.O(logn) D.(nlogn)

76.关于排序算法的以下说法，错误的是____

A.快速排序的平均时间复杂度为O(nlogn)，最坏的时间复杂度为O(n2) B. 堆排序的平均时间复杂度为O(nlogn)，最坏的时间复杂度为O(nlogn) C. 冒泡排序的平均时间复杂度为O(n2)，最坏的时间复杂度为O(n2) D. 归并排序的平均时间复杂度为O(nlogn)，最坏的时间复杂度为O(n2)

77. 某二叉树的前序遍历序列为-+a*b-cd/ef，后序遍历序列为abcd-*+ef/-，问其中序遍历序列是_____.

78.某缓存系统采用LRU淘汰算法，假定缓存容量为4，并且初始为空，那么在顺序访问以下数据项的时候1,5,1,3,5,2,4,1,2出现缓存直接命中的次数是___________,最后缓存中即将准备淘汰的数据项是______.

79.有两个较长的单向链表a和b，为了找出结点node满足node in a并且node in b。请设计空间使用尽量小的算法。

80. 当存储数据量超出单节点数据管理能力的时候，可以采取的办法有数据库sharding的解决方案，也就是按照一定规律把数据

分散存储在多个数据管理结点N中（节点编号为0,1,2?N-1）.假设存储的数据是a，请完成为数据a计算存储节点的程序。 #define N 5

int hash(int element){ return element *2654435761; }

int shardingIndex(int a){ int p=hash(a);

________________________________ return p; }