自信人生二百年，会当水击三千里！

一、选择题

1、下面的排序方法中，关健字比较次数与初始排列无关的是()

A、直接选择排序

B、希尔排序

C、直接插入排序

D、冒泡排序

答案：A。分析：

元素的移动次数与关键字的初始排序无关的是：归并排序、基数排序

元素的比较次数与初始序列无关的是：选择排序、基数排序

算法的时间复杂度与初始序列无关的是：堆排序、归并排序、选择排序、基数排序

2、在有序双向链表中定位删除一个元素的平均时间复杂度为（)

A.0(1)

B.O(N)

C.0(logN)

D.0(N*logN)

答案：B。分析：链表只能顺序查找，O（N）的单次查找，O（1）的删除时间复杂度。所以综合就是O（N）。

3、在一个以 h 为头指针的单循环链表中，p指针指向链尾结点的条件是()

p->data==-1

p->next==NULL

p->next->next==h

p->next==h

答案:D。分析：p->next==head时，就代表p指针指向链尾结点的条件是。

4、已知一个线性表(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

已知一个线性表(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

5、若用数组SI...n]作为两个找S1和S2的存储结构，对任何一个栈只有当S全满时才不能做入找操作。为这两个栈分配空间的最佳方案是

A. S1的栈底位置为0，s2的栈底位置为n

B.S1的栈底位置为0，s2的找底位置为n/2

C.S1的栈底位置为1，S2的栈底位置为n/2

答案：A。分析：两个栈的栈底一个在数组第一个元素，朝着数组正方向增长另一个在数组最后一个元素，朝着数组索引减小的方向增长。当两个栈的栈顶相等是，表明数组满了，不能继续入栈。

二、编程题

1、小易的升级之路

代码分析：

#include<iostream>#include<algorithm>usingnamespacestd;
constintN=1e5+10;
ints[N] = {0};
intmain()
{
intn, a;
while (cin>>n>>a)
{
intsum=a;
for (inti=0; i<n; i++)
{
cin>>s[i];
}
for (inti=0; i<n; i++)
{
if (a>=s[i])
{
a+=s[i];
}
else{
intd=0;
intm=a;
while (a)
{
d=s[i] %a;
s[i] =a;
a=d;
}
a=m;
a+=s[i];
}
}
cout<<a<<endl;
}
return0;
}

2、找出字符串中第一次只出现一次的字符

代码示例：

#include<iostream>#include<string>usingnamespacestd;
constintN=1e6+10;
ints[N];
inta[300] = {0};
intmain()
{
stringc;
cin>>c;
intflag=0;
for (inti=0; i<c.size(); i++)
{
a[c[i]] ++;
}
for (inti=0; i<c.size(); i++)
{
if (a[c[i]] ==1)
    {
cout<<c[i] ;
flag=1;
break;
    }
}
if (flag==0) cout<<-1;
return0;
}

总结

本文总共讲了5题选择题，以及两道牛客编程题，希望大家读后能够有所收获！