2009 年真题

---

---

注意看题目中要求的是
时间上高效，
时空上高效
尽可能高效

typedef int ElemType;
typedef struct LNode{ //定义单链表节点类型ElemType data：		//数据域struct LNode *link；//指针域
}*LinkList；int Search_k(LinkList list，int k){LinkList p,q;int count=0; //计数器赋初值p=q=list->link;//p和q指向链表表头结点的下一个结点while(p!=NULL){if(count<k)	count++；//计数器+1else q=q->link； //q移到下一个结点p=p->link； //p移到下一个结点}if(count<k)	return 0; //如果链表的长度小于k，查找失败//比如链表长count=5，要找倒数第k=8的元素，那么就算遍历完整个链表，count还是小于kelse{printf(”％d”，q->data)；/*查找成功*/return 0;}
}

2010 年真题

题目一：

查找不成功的平均查找长度计算思路：
对于每一个不存在的元素都是先乘3再对7取余，所以这些元素最终都会落在0-6这个区间内。
这样的话只需要对0-6的元素进行探测

个人思路：
需要借助一个额外的数组空间res[n]：
先将R中从p到n-1的元素复制到新的数组res的前n-p个位置，再将R中从0到p-1的元素复制到res的后面。

2011 年真题

---

2012年真题

2013 年真题

2018 年真题