牛客网-题目分享（4）
题目1：栈和链表是两种不同的数据结构（）。正确答案: A
正确 错误
解析：
栈和链表是两种不同的数据结构。 栈是逻辑结构的概念,是特殊殊线性表,而链表是存储结构概念,二者不是同 类项
题目2：
若有以下定义和语句：
|
1 |
|
则不能表示a数组元素的表达式是:() 。 正确答案: B
*p a[10] *a a[p-a]
解析：
A:相当于a[0]
B:以为数组的下标从0开始，所以10越界。
C:相当于a[0]
D:p和a指向同一个数组，可以做加减法（如果p和a不是指向同一数组则会出错），得到的值为整数。此题为0。所以D也相当于a[0]。
题目3：
在最好情况下，下列排序算法中 排序算法时间复杂度最低的是。
正确答案: B
基数排序 直接插入排序 快速排序 归并排序
解析：
题目4：
在二叉排序树（二叉搜索树）中，最小值结点的（ ）。
正确答案: A
左孩子一定为空指针 右孩子一定为空指针 左、右指针均为空 左、右指针均不为空
解析：
对于二叉树排序，左子树值一定比节点值小，右子树值一定比节点值大，因节点值是最小值，则其没有左子树
题目5：
对关键码序列28,16,32,12,60,2,5,72快速排序（最常用的快速排序，以第一个关键码为基准）,使用挖坑法，从小到大一次划分结果为()
正确答案: D
(2,5,12,16)28(60,32,72) (2,16,5,12)28(60,32,72) (2,16,12,5)28(60,32,72) (5,16,2,12)28(60,32,72)
解析：
原始为：
28 16 32 12 60 2 5 72
i是左到右找小于28数，j是右到左找小于28数，j先动。
j找到5，i动找到32。两者互换。有：
28 16 5 12 60 2 32 72
j找到2，i找到60互换有：
28 16 5 12 2 60 32 72
j i相遇，i和28换位子：
2 16 5 12 28 60 32 72
结果是B。
题目6：
某字符串满足:concat(head(s),head(tail(tail(s))))="ac",(head,tail的定义同广义表),则S=()
正确答案: C
aabc acba accc acac
解析：
概念解释：广义表L=(A,B,C),表头是A，表尾是（B,C)，这是定义。
tail()表示取字符串的尾部，head()表示取字符串的头，concat()表示字符串拼接。
取两次尾部一次头部，然后合并，答案是C。
题目7：
判断下列说法是否正确：设有两个串S1和S2,求S2在SI中首次出现位置的运算称为求子串。( )
正确答案: B
正确 错误
解析：
应属于模式匹配
题目8：
执行完下列语句段后,i值为()
|
1 2 3 4 5 |
|
正确答案: B
4 48 8 无限递归
解析：
f(x) 当x大于0时，返回x*f(x-1)，否则返回2
f(0) = 2
f(1) = 1 * f(0) = 2
f(2) = 2 * f(1) = 4
f(3) = 3 * f(2) = 12
f(4) = 4 * f(3) = 48
f(4) = f(f(2)) = 48
选B
题目9：
在一般情况下，采用压缩存储后，对称矩阵是所有特殊矩阵中存储空间节约最多的，这样的说法正确吗？
正确答案: B 你的答案: B (正确)
正确 不正确
解析：
稀疏矩阵，0元素远多于非0元素且非0元素分布没有规律。比如一个矩阵只有零散的两个1，其他元素都是0，那压缩存储的时候只需要记录这两个非0元素的位置（行，列）还有值（1）就可以了，其他元素都是0。
题目10：
将一个递归算法改为对应的非递归算法时，通常需要使用（ ）。
正确答案: D 你的答案: A (错误)
优先队列 队列 循环队列 栈
解析：
递归之所以可以采用非递归方法实现是因为可以用栈的方式
如果你采用递归时 是由系统管理函数栈
而要写成非递归时必须由你自已来管理一个栈.