正确答案：C

循环套循环就是m*n

2. 下列关于线性链表的叙述中，正确的是（ ）

A各数据结点的存储空间可以不连续，但它们的存储顺序与逻辑顺序必须一致
B 各数据结点的存储顺序与逻辑顺序可以不一致，但它们的存储空间必须连续
C 进行插入与删除时，不需要移动表中的元素
D 以上说法均不正确

正确答案：C

存储顺序与逻辑顺序可以完全没有关系，他们这件的有序靠的是指针
存储空间连续就不是链表了

3. 下列描述的不是链表的优点是（ ）

A 逻辑上相邻的结点物理上不必邻接
B 插进、删除运算操纵方便，不必移动结点
C 所需存储空间比线性表节省
D 无需事先估计存储空间的大小
正确答案：C

维护链表结构需要多申请一个链表空间，链表的空间利用率是比较低的

4. 向一个栈顶指针为h的带头结点的链栈中插入指针s所指的结点时,应执行()

A h->next=s;
B s->next=h;
C s->next=h;h->next=s;
D s->next=h->next;h->next=s;

正确答案：D

5.队列{a,b,c,d,e}依次入队，允许在其两端进行入队操作，但仅允许在一端进行出队操作，则不可能得到的出

队序列是（）
A b， a， c， d， e
B d， b， a， c， e
C d， b， c， a， e
D e， c， b， a， d

正确答案：C

6.若一棵二叉树具有12个度为2的结点，6个度为1的结点，则度为0的结点个数是（）

A 10
B 11
C 13
D 不确定

正确答案：C

n0=n2+1=12+1=13

7. 下列各树形结构中,哪些是平衡二叉查找树:

正确答案：C

8. 已知关键字序列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

根据堆的原则插入时从最后一个堆插入
向上调整，比它大就交换

9. 采用哈希表组织100万条记录，以支持字段A快速查找，则（）

A 理论上可以在常数时间内找到特定记录——产生冲突时不一定，常数时间内只能针对特殊数据
B 所有记录必须存在内存中——可以放在外层（磁盘中）
C 拉链式哈希曼最坏查找时间复杂度是O（n）——拉链式哈希表（顺序表+链表）最好是O(1)
D 哈希函数的选择跟A无关——A是整数用除留余数法，A是char，就是字符映射就不一定是除留余数法了

正确答案：C

10.假设你只有100Mb的内存，需要对1Gb的数据进行排序，最合适的算法是（）

A 归并排序
B 插入排序
C 快速排序
D 冒泡排序
正确答案：A

内存没有办法装这么多的数据，需要采用外部排序——归并排序

二. 编程

1. 微信红包

链接

春节期间小明使用微信收到很多个红包，非常开心。在查看领取红包记录时发现，某个红包金额出现的次数
超过了红包总数的一半。请帮小明找到该红包金额。写出具体算法思路和代码实现，要求算法尽可能高效。
给定一个红包的金额数组 gifts 及它的大小 n ，请返回所求红包的金额。
若没有金额超过总数的一半，返回0。

示例1:
输入
[1,2,3,2,2],5
输出
2

示例2:
输入
[1,1,2,2,3,3],6
输出
0

正确答案：

class Gift {
public:int getValue(vector gifts, int n) {// write code heresort(gifts.begin(),gifts.end());//超过一半的数排序之后必然排在中间int mid = gifts[n/2];int count = 0;for(int i = 0;i//统计排在中间的数的个数if(gifts[i] == mid)count++;}//如果个数大于一半，则存在超过一半的数if(count > n/2)return mid;elsereturn 0;}
};

class Gift {
public:int getValue(vector gifts, int n) {// write code heremap count;int mid = gifts.size()/2;for(const auto& e : gifts)++count[e];for(const auto& e : count){if(e.second >= mid)return e.first;}return 0;}
};

2.计算字符串的编辑距离

链接

Levenshtein 距离，又称编辑距离，指的是两个字符串之间，由一个转换成另一个所需的最少编辑操作次数。许可的编辑操作包括将一个字符替换成另一个字符，插入一个字符，删除一个字符。编辑距离的算法是首先由俄国科学家 Levenshtein 提出的，故又叫 Levenshtein Distance 。

例如：
字符串A: abcdefg
字符串B: abcdef
通过增加或是删掉字符 ”g” 的方式达到目的。这两种方案都需要一次操作。把这个操作所需要的次数定义
为两个字符串的距离。
要求：
给定任意两个字符串，写出一个算法计算它们的编辑距离。

输入描述：
每组用例一共2行，为输入的两个字符串
输出描述：
每组用例输出一行，代表字符串的距离

示例1:
输入
abcdefg
abcdef
输出
1

正确答案：

#include 
#include
#include
using namespace std;int Min(const string &s1,const string &s2)
{// word与空串之间的编辑距离为word的长度if(s1.empty() || s2.empty())return max(s1.size(),s2.size());int l1 = s1.size();int l2 = s2.size();vector> f(l1+1,vector(l2+1,0));for(int i = 0;i<=l1;i++)f[i][0] = i;for(int j = 0;j<=l2;j++)f[0][j] = j;for(int i = 1;i<=l1;i++){for(int j = 1;j<=l2;j++){// 判断word1的第i个字符是否与word2的第j个字符相等if(s2[j-1] == s1[i-1]){f[i][j] = 1+min(f[i-1][j], f[i][j-1]);//由于字符相同，所以距离不发生变化f[i][j] = min(f[i][j], f[i-1][j-1]);}else{f[i][j] = 1 + min(f[i-1][j], f[i][j-1]);//由于字符不相同，所以距离+1f[i][j] = min(f[i][j], 1+f[i-1][j-1]);}}}return f[l1][l2];}int main() {string s1,s2;while(cin>>s1>>s2)cout<