数据结构：笔记-链表_c. 所需空间与线性表长度成正比

1、链表不具有的特点是( )。
正确答案: B 你的答案: B (正确)
插入、删除不需要移动元素
可随机访问任一元素
不必事先估计存储空间
所需空间与线性长度成正比

2、下列叙述中正确的是
正确答案: C 你的答案: C (正确)
线性表链式存储结构的存储空间一般要少于顺序存储结构
线性表链式存储结构与顺序存储结构的存储空间都是连续的
线性表链式存储结构可以使连续的,也可以是不连续的
以上说法均错误

3、某线性表中最常用的操作是在最后一个元素之后插入一个元素和删除第一个元素,则采用（）存储方式最节省运算时间。
正确答案: D 你的答案: C (错误)
单链表
仅有头指针的单循环链表
双链表
仅有尾指针的单循环链表

解析：操作基本上只与尾元素有关。

4、下列哪些容器可以使用数组，但不能使用链表来实现?

正确答案: D 你的答案: D (正确)
队列
栈
优先级队列
Map或者Dict

解析：先队列一般利用堆来实现,堆用数组来做的话,确实可以快很多,体现在用数组可以很快定位到父子节点,而链表的话,就没有那么方便了,但是这并不意味着链表不能做,可以,只是时间复杂度会比较高而已.

说一下字典吧,字典一般要求最好能在O(1)的时间就定位到要查询的值,如果采用链表的话,是不可能有这个好的时间复杂度的,字典一般用hash表来实现,在不碰撞的情况下,能够达到这么好的复杂度,用红黑树实现的map,查找的复杂度在log(N)左右. 用链表的话,硬要说的话,可以实现字典,但是效率不够,它在查找,插入等各种操作上都没有优势.

5、带头结点的单链表head为空的判定条件（ ）
正确答案: B 你的答案: B (正确)
headNULL
head->nextNULL
head->nexthead
head!=NULL
解析：1、带头结点单链表：head->nextNULL
2、带头结点循环链表：head->nexthead
3、不带头结点单链表：headNULL

6、某线性表中最常用的操作是在最后一个元素之后插入一个元素和删除第一个元素,则采用()存储方式最节省运算时间
正确答案: D 你的答案: 空 (错误)
单链表
仅有头指针的单循环链表
双链表
仅有尾指针的单循环链表

7、下列叙述中正确的是？
正确答案: D 你的答案: D (正确)
循环队列有队头和队尾两个指针，因此，循环队列是非线性结构
在循环队列中，只需要队头指针就能反映队列中元素的动态变化情况
在循环队列中，只需要队尾指针就能反映队列中元素的动态变化情况
循环队列中元素的个数是有队头指针和队尾指针共同决定

8、若某线性表最常用的操作是存取任一指定序号的元素和在最后进行插入和删除运算,则利用（）存储方式最节省时间。

正确答案: A 你的答案: A (正确)
顺序表
双链表
带头结点的双循环链表
单循环链表

9、下列叙述中正确的是（ ）。

正确答案: D 你的答案: C (错误)
每一个结点有两个指针域的链表一定是非线性结构
所有结点的指针域都为非空的链表一定是非线性结构
循环链表是循环队列的链式存储结构
线性结构的存储结点也可以有多个指针

10、现有线性表（16，37, 43，55, 73，97，110，100），对其进行散列存储， 若选用H(K)=K%9作为散列函数，则散列地址为1的元素有（）个。
正确答案: D 你的答案: C (错误)
1
2
3
4
解析：把上面元素mod9运算 结果为1的有4个。 说人话就是除以9余数为1

11、判断下列说法是否正确：F=(a,F)是一个递归的广义表，它的深度是1,长度是2。( ）
正确答案: B 你的答案: A (错误)
正确
错误
解析：选B。考察的是广义表以及递归广义表的原理。
广义表是由n个元素组成的序列，n是广义表的长度。
广义表的深度： 广义表中括号的最大层数叫广义表的深度。
F=(a,F)的长度为2，由于属于递归表，所以深度为无穷，F相当于一个无限的表(a,(a,(a,(…))))。

12、从一个具有 n 个结点的单链表中查找其值等于 x 结点时，在查找成功的情况下，需平均比较（ ）个结点。
正确答案: D 你的答案: D (正确)
n
n/2
(n-1)/2
(n+1)/2
解析：n=1和n=n，1+n的和除以2

13、采用二叉链表作为存储结构,树的前序遍历和其相应的二叉树的前序遍历的结果是一样的()
正确答案: A 你的答案: B (错误)
对
错
解析：选A，这句话是对，树的前序遍历对应二叉树的前序遍历，树的后序遍历和二叉树的中序遍历一致

14、若广义表A满足Head(A) = Tail (A), 则A为

正确答案: B 你的答案: C (错误)
( )
( ( ) )
( ( ), ( ) )
（ ），（ ），（ ））

解析：广义表第一个元素是表头，其余元素是表尾，如果只有一个元素，那么表尾为空即（），
B中head(A)=();tail(A)=();
但是在选项C中，head(A)=();tail(A)=（（））;
D中head(A)=);tail(A)=((),());
所以重点是求表尾时不要遗忘最外面的那一层括号

15、对长度为无穷大的广义表,由于存储空间的限制,不能在计算机中实现()
正确答案: A 你的答案: B (错误)
对
错
解析：长度为无穷大的广义表不能在计算机中实现，但是无限递归的广义表可以在计算机中实现~

16、邻接表是图的一种顺序存储结构，这种说法（）
正确答案: B 你的答案: B (正确)
正确
错误

17、下列叙述中错误的是（ ）
正确答案: B 你的答案: C (错误)
二叉链表是二叉树的存储结构
循环链表是循环队列的存储结构
栈是线性结构
循环队列是队列的存储结构

18、单向链表不满足的描述是（ ）

正确答案: A D 你的答案: A C D (错误)
可以随机访问任意结点
删除头节点的时间复杂性是O（1）
空间开销与链表长度成正比
插入数据的时间开销比数组更大

19、以下关于链表和数组说法正确的是（）
正确答案: A B C 你的答案: A B C (正确)
数组从栈中分配空间，链表从堆中分配空间
数组插入或删除元素的时间复杂度O(n)，链表的时间复杂度O(1)
数组利用下标定位，时间复杂度为O(1)，链表定位元素时间复杂度O(n）
对于add和remove，ArrayList要比LinkedList快