笔试真题刷题平台
精选近几年名企笔试真题，笔试之前刷刷真题，有备无患
一、不定项选择
1、在一个有8个int数据的数组中，找出最大和第二大元素至少需要进行（）次比较：
A、8 B、9 C、10 D、11
1、C
先取两个数 比较 1次， 找到 最大和第二大
然后取两个数， 这两个数先比较， 得到一大一小。 用大数去跟之前最大的比， 如果比之前最大的大， 就用小数再跟最大的比。 如果比之前最大的小， 就再跟第二大的比。总之 经过 这样的3次比较， 又可以找出最大的和第二大的。
以此类推。
8个数正好分成4组两个数， 所以总比较次数为 1+ 3+ 3+3 = 10
2、在关系数据库中，用来表示实体之间联系的是（）
A、树结构
B、网结构
C、线性表
D、二维表
2、D
关系数据库中用二维表来表示实体之间的联系
3、对于基本有序的序列，按照那种排序方式最快：
A、快速排序
B、冒泡排序
C、归并排序
D、基数排序
3、B
冒泡排序、快速排序、堆排序的性能比较对照
排序方法 比较次数 移动次数 稳定性 辅助空间
最好 最差 最好 最差 最好 最差
冒泡排序 n n^2 0 n^2 是 1 1
快速排序 nlogn n^2 logn n 否 logn n
堆排序 nlogn nlogn nlogn nlogn 否 1 1
而当待排序列已基本有序时，对冒泡排序来说是最好情况，对快速排序来说就是最差情况，而堆排序则最好最差都一样。因此本题答案是冒泡排序。
4、位示图的用处为：
A、主存空间的共享
B、文件的保护和加密
C、磁盘空间的管理
D、文件目录的查找
4、C
位示图是利用二进制的一位来表示磁盘中的一个盘块的使用情况。当其值为“0”时，表示对应的盘块空闲；为“1”时，表示已经分配。有的系统把"0"作为盘块已分配的标记，把“1”作为空闲标志。(它们的本质上是相同的，都是用一位的两种状态表示 空闲和已分配两种情况。)磁盘上的所有盘块都有一个二进制位与之对应，这样，由所有盘块所对应的位构成一个集合，称为位示图。
A 用于分页式存储管理中主存空闲块的分配和回收
D 用于文件存储空间的管理
5、16进制数值31B6和8进制数值73615的异或结果值（10进制）为：
A、18779
B、11503
C、17979
D、13561
5、C
1.分别将这两个数转换为二进制数：
31B6=11000110110110
73615 = 111011110001101
2.两者异或^，相同为0，不同为1则：
011000110110110
111011110001101
3.答案如下：
100011000111011 ==》17979
选c
6、若一棵二叉树具有10个度为2的结点，5个度为1的结点，则度为0的结点个数是：
A、10
B、11
C、12
D、13
6、B
所有点的入度和出度的和相等， 下面等式左边为出度， 右边为入度（根节点入度为0， 其他节点入度为1）
10 * 2 + 5 * 1 = 10 + 5 + x -1
x等于11
7、上网时候发现网页不能访问，QQ使用正常，出现此问题可能的原因是：
A、网线问题
B、DNS问题
C、IP地址冲突
D、网关错误
7、B
DNS是将域名解析成IP地址的服务。DNS发生问题时无法通过域名访问网页；但是直接通过IP地址连接的应用程序仍可以使用。
8、由权值为9,2,7,5的四个叶子节点构造一棵哈夫曼树，该树的带权路径长度为：
A、23
B、37
C、44
D、27
8、C
带权路径长=5*3+2*3+7*2+9*1=44
9、在一个单链表中，若p所指结点不是最后结点，在p之后插入s所指结点，则执行？
A、s->next=p ; p->next=s ;
B、s->next=p->next; p->next=s;
C、s->next=p->next ; p=s;
D、p->next=s ; s->next=p;
9、B
让s指向p的下一个节点；再让p指向x
二、解答题
10、对于非负序列a1、a2、……、an，在数轴上做垂线连接点（i，0）和（i，ai）。选择这样的两条线和x轴可以形成一个容器，我们以面积代表所装的水，求以这种方式构成的容器能装的最大面积。比如选择a2=3、a5=6，则所装的面积为9.
10、
int maxArea(int height[], int n) {
int head = 0, tail = n - 1;
int max = 0, temp = 0;
while (head < tail) {
temp = tail - head;
if (height[head] < height[tail]) {
temp *= height[head];
head++;
}
else {
temp *= height[tail];
tail--;
}
if (temp > max) {
max = temp;
}
}
return max;
}
或者
class Program
{
static void Main(string[] args)
{
int n;
int [] A=new int[]{};
int s = 0;
for (int i = 0; i < n; i++)
{
s = A[0] + A[n];
}
Console.WriteLine(s);
Console.ReadKey();
}
11、假设有如下一个链表：
struct Node
{
int value ;
struct Node *next ;
struct Node *random ;
}
其中，random指向该链表的任意一个节点或者NULL，请编程实现该链表的深拷贝。
Node *deepCopy (Node *head)
11、
struct Node
{
int value ;
struct Node *next ;
struct Node *random ;
}
struct pair
{
struct Node *one;
struct Node *two;
}
Node *deepCopy(struct Node *head)
{
vector<struct pair> pa;
struct Node *head1 = new struct Node;
head1->value = head->value;
struct pair pnode;
pnode.one = head;
pnode.two = head1;
pa.push_back(pnode);
struct Node *node = head->next;
struct Node *node1 = head1;
while (node)
{
struct Node *temp = new struct Node;
temp->value = node->value;
temp->next = NULL;
temp->random = NULL;
node1->next = temp;
pnode.one = node;
pnode.two = temp;
node = node->next;
node1 = temp;
}
node = head;
node1 = head1;
while (node)
{
if (node->random == NULL)
{
node1->random = NULL;
}
else
{
node1->random = find(node->random,pa);
}
node = node->next;
node1 = node1->next;
}
return head1;
}
struct Node *find(struct Node *node, vector<struct pair> &pa)
{
for (int i=0; i<pa.size(); i++)
{
if (node == pa[i].one)
{
return pa[i].two;
}
}
return NULL;
}
或者
Node *deepCopy (Node *head)
{
Node* now = head;
Node* next = head->next;
while( now != NULL )
{
Node * copy = new Node;
copy->value = now->value;
copy->next = now->next;
now ->next = copy;
now = next;
next = next->next;
}
now = head;
while( now != NULL )
{
now->next->random = now->random->next;
now = now->next->next;
}
Node* head2 = head->next;
Node* newHead = head->next;
while( head2->next != NULL )
{
head->next = head2->next;
head2->next = head2->next->next;
head = head->next;
head2 = head2->next;
}
return newHead;
}
