在双向循环链表中，在p指针所指的节点后插入一个指针q所指向的新节点，修改指针的操作是（）
A. p->next=q;q->prior=p;p->next->prior=q;q->next=q;
B. p->next=q;p->next->prior=q;q->prior=p;q->next=p->next;
C. q->prior=p;q->next=p->next;p->next->prior=q;p->next=q;
D. q->next=p->next;q->prior=;p->next=q;p->next=q;
答案：C
对于序列16 14 10 8 7 9 3 2 4 1，以下说法正确的是（）
A. 大顶堆
B. 小顶堆
C. 不是堆
D. 二叉排序树
答案：A
对于线性表（7，34，55，25，64，46，20，10）进行散列存储时，若使用H（K)=K%9作为散列函数，则散列地址为1的元素有（）个
A. 1
B. 2
C. 3
D. 4
答案：D
采用递归方式对顺序表进行快速排序，下列关于递归次数的叙述中，正确的是（）
A. 递归次数与初始数据的排列次序无关
B. 每次划分后，先处理较长的分区可以减少递归次数
C. 每次划分后，先处理较短的分区可以减少递归次数
D. 递归次数与每次划分后得到的分区处理顺序无关
答案：D
一棵完全二叉树第六层有9个叶结点（根为第一层），则结点个数最多有（）
A. 112
B. 111
C. 107
D. 109
答案：D
对数组A[]={4,78,3,64,32,89,43,12}进行Hash存储时，选用H(K)=K%7作为Hash函数，则Hash地址为1的元素有（）个
A. 1
B. 2
C. 3
D. 4
答案：C
已知关键字序列5,8,12,19,28,20,15,22是最小堆，插入关键字3，调整后得到的最小堆是（） A. 3,8,12,5,20,15,22,28,19
B. 3,5,12,19,20,15,22,8,28
C. 3,12,5,8,28,20,15,22,19
D. 3,5,12,8,28,20,15,22,19
答案：D
已知一个线性表（38，25，74，63，52，48），假定采用散列函数h（key) = key%7 计算散列地址，并散列存储在散列表A[0....6]中，若采用线性探测方法解决冲突，则 在该散列表上进行等概率成功查找的平均查找长度为（）
A. 1.5
B. 1.7
C. 2.0
D. 2.3
答案：C
以30为基准，设一组初始记录关键字序列为 (30,15,40,28,50,10,70)，则第一趟快速排序结果为（）
A. 10，28，15，30，50，40，70
B. 10，15，28，30,50，40，70
C. 10，28，15，30，40，50，7
0 D. 10，15，28，30，40，50，70
答案：B
一棵二叉树的先序遍历为EFHIGJK，中序遍历为HFIEJKG，则后序遍历为（ ）
A. HIFJKGE
B. FHIJKGE
C. HIFGJKE
D. HIFKJGE
答案：D
微信红包
题目描述：春节期间小明使用微信收到很多个红包，非常开心。在查看领取红包记录时发现，某个红包金额出现的次数超过了红包总数的一半。请帮小明找到该红包金额。 写出具体算法思路和代码实现，要求算法尽可能高效。
给定一个红包的金额数组 gifts 及它的大小 n ，请返回所求红包的金额。 若没有金额超过总数的一半，返回0。
数据范围：1<=n<=1000,红包金额满足1<=gift<=100000
方法1：
public class Gift {
public int getValue(int[] gifts,int n){
//数组排序
Arrays.sort(gifts);
//获取中间数据
int mid=gifts[n/2];
int count=0;
//统计中间位置的数据出现的次数
for (int g : gifts) {
if (g==mid){
count++;
}
}
//判断计算器值 > n/2
if (count >n/2){
return mid;
}else {
return 0;
}
}
}
方法2：
public class Gift {
//方法2
public int getValue(int[] gifts,int n){
Map<Integer,Integer> map=new HashMap<>();
for ( int g : gifts) {
if (map.containsKey(g)){
map.put(g,map.get(g)+1);
}else {
map.put(g,1);
}
if (map.get(g) >n/2){
return g;
}
}
return 0;
}
}
计算字符串的编辑距离
题目描述：Levenshtein 距离，又称编辑距离，指的是两个字符串之间，由一个转换成另一个所需的最少编辑操作次数。许可的编辑操作包括将一个字符替换成另一个字 符，插入一个字符，删除一个字符。编辑距离的算法是首先由俄国科学家 Levenshtein 提出的，故又叫 Levenshtein Distance 。
例如： 字符串A: abcdefg 字符串B: abcdef
通过增加或是删掉字符 ”g” 的方式达到目的。这两种方案都需要一次操作。把这个操作所需要的次数定义为两个字符串的距离。
要求： 给定任意两个字符串，写出一个算法计算它们的编辑距离。
数据范围：给定的字符串长度满足1<=len(str)<=1000
输入描述：每组用例一共2行，为输入的两个字符串
输出描述：每组用例输出一行，代表字符串的距离
public class Main38 {
//计算字符串的编辑距离
public static void main(String[] args)throws Exception {
BufferedReader reader=new BufferedReader(new InputStreamReader(System.in));
String str1;
while ((str1=reader.readLine()) !=null){
String str2=reader.readLine();
System.out.println(getDistance(str1,str2));
}
}
public static int getDistance(String str1,String str2){
char[] wd1=str1.toCharArray();
char[] wd2=str2.toCharArray();
int len1=wd1.length;
int len2=wd2.length;
//定义一个矩阵
int[][] dist=new int[len1+1][len2+1];
//初始状态 F(i,0)=i; F(0,j)=j
for (int i = 0; i <=len1; ++i) {
dist[i][0]=i;
}
for (int i = 0; i <=len2; ++i) {
dist[0][i]=i;
}
for (int i = 1; i <=len1; ++i) {
for (int j = 1; j <=len2; ++j) {
//F(i,j) =min(F(i-1,j)+1
//F(i,j-1)+1,F(i-1,j-1)+(wd1[i]==wd2[j] ? 0:1))
//首先求出插入和删除的最小值
dist[i][j]= Math.min(dist[i-1][j],dist[i][j-1])+1;
//再和替换进行比较
if (wd1[i-1]==wd2[j-1]){
//不需要进行替换
dist[i][j]=Math.min(dist[i][j],dist[i-1][j-1]);
}else {
dist[i][j]=Math.min(dist[i][j],dist[i-1][j-1]+1);
}
}
}
return dist[len1][len2];
}
}
