如果你有梦想的话，就要去捍卫它。那些一事无成的人想告诉你你也成不了大器。

一、选择题

1、有1000个无序的整数，希望使用最快的方式找出前50个最大的，最佳的选择是（)

A、快速排序

B、冒泡排序

C、堆排序

D、基数排序

答案：C。分析：快排的时间复杂度是O(nlogn)，最坏的情况下是O(n^2)，堆排序的最差、最佳和平均都是O(nlogn)，这题如果只考虑最佳的情况下是没有意义的，要从最差时间复杂度来考虑。

2、循环队列的存储空间为Q(12000，初始状态为front=rear=200。经过一系列正常的入队与退队操作后，front=rear=1，则循环队列中的元素个数为（）。

A.0或200

B.1

C.2

D.199

答案：A。分析：循环队列只有空或者满的时候，才会出现入队位置和出队位置相同。

3、将一棵二叉树的根节点放入队列，然后非递归的执行如下操作：将出队节点的所有子节点入队。以上操作可以实现哪种遍历

A.前序遍历

B.中序遍历

C.后续遍历

D.层序编历

答案：D。分析：前序中序后序的非递归都是用栈实现的，层次遍历是用队列实现的。

4、下列关于线性链表的叙述中，正确的是（)

A、各数据结点的存储空间可以不连续，但它们的存储顺序与逻辑顺序必须一致

B、各数据结点的存储顺序与逻辑顺序可以不一致，但它们的存储空间必须连续

C、进行插入与删除时，不需要移动表中的元素

D、以上说法均不正确

答案：C。分析：链表在执行插入和删除操作时只需要改变指针指向，不需要移动表中的元素。

5、下列描述的不是链表的优点是（）

A、逻辑上相邻的结点物理上不必邻接

B、插进、删除运算操纵方便，不必移动结点

C、所需存储空间比线性表节省

D、无需事先估计存储空间的人小

答案：C。链表所需存储空间比线性表多，其他选项都是链表的优点。

二、牛客编程题

1、数根

思路：把每一次输入当作字符串来读人，因为n的范围非常大

代码示例：

#include<iostream>#include<string>#include<stack>#include<algorithm>usingnamespacestd;
intmain()
{
stringstr;
while (cin>>str)
    {
inta=0;
for (inti=0; i<str.size(); i++)
        {
a+=str[i] -'0';
        }
intsum=0, ans=0;
while (a>0)
        {
sum+=a%10;
a/=10;
        }
if (sum>=10)
        {
while (sum>0)
            {
ans+=sum%10;
sum/=10;
            }
cout<<ans<<endl;
        }
elsecout<<sum<<endl;
    }
return0;
}

2、星际密码

初始化斐波那契数列，每次获取对应数据，打印后4位即可。

代码示例：

#include<iostream>#include<vector>usingnamespacestd;
intmain()
{
vector<int>v= { 1, 1 };//初始化vectorfor (inti=2; i<10001; i++)
    {
v.push_back((v[i-1] +v[i-2]) %10000);//取最后四位    }
intn;
while (cin>>n)
    {
intx=0;
for (inti=0; i<n; i++)
        {
cin>>x;
printf("%04d", v[x]);
        }
printf("\n");
    }
return0;
}

总结

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