q
解：选C。若选D，则链表中没有了q的后继结点，但未删除。仅C选项可使q的后继结点
被删除，并按原有结点顺序重新拉链。
10设p为有头结点双向循环链表中某结点的指针，lLi
k为左链指针，rLi
k为右链指针，则
下述表达式中，
不恒为真。
A．prLi
klLi
kp
B．prLi
klLi
kplLi
krLi
k
C．plLi
krLi
kp
D．prLi
krLi
kplLi
klLi
k
解：选D。因为prLi
klLi
kpplLi
krLi
k，故只有D不一定为真。
11若某链表最常用的操作是在最后一个结点之后插入一个结点和删除最后一个结点，则采
用
存储方式最节省时间。
A．单链表B．双向链表C．带头结点的双循环链表D．单循环链表
解：选C。
12链表不具有的特点是
。
A．可随机访问任一元素
B．插入删除不需要移动元素
C．不必事先估计存储空间D．所需空间与线性表长度成正比
解：选A。
13线性表采用链式存储时，其地址
。
A．连续的
B．部分连续的
C．一定是不连续的D．连续与否均可
解：选D。
14设有一8×8下三角矩阵A88，采用按行压缩存储的方式存放在一维数组B中，则数
组B的容量至少需要B个元素空间。
A．32B．36
C．16
D．64
解：选B。矩阵的第1行有8个非零元素，第2行有7个非零元素，…，第8行有1个非零
元素，故需要存储的非零元素的个数为
87654321818236
三、填空题
1对于一个长度为
的顺序存储的线性表，在表头插入元素的时间复杂度为
，在表
尾插入元素的时间复杂度为
。
解：在表头（即第0个位置）插入元素，需移动的元素个数为
，然后再做1次赋值操作，
故T
1O
。在表尾插入元素无需移动表中已有元素，只需1次赋值操作，故
T
1O1。
2在线性表的单链接存储中，若一个元素所在结点的地址为p，则其后继结点的地址
为
，若假定p为一个数组a中的下标，则其后继结点的下标为
。
解：应填入pli
k，p1
3在单循环链表中，最后一个结点的指针指向
结点。
f解：表头结点。
4在双向链表中每个结点包含有两个指针域，一个指向其
结点，另一个指向
其
结点。
解：应填入前驱，后继。
5在双向循环链表中表头结点的左指针域指向
结点，最后一个结点的右指针域
指向
结点。
解：应填入表尾，表头。
6在以HL为表头指针的带附加表头结点的单链表和单循环链表中，链表为空的条件分别为
和
。
解：HLli
kNULLHLli
kHL
7在双循环链表L中，指针p所指结点为尾结点的条件为
。
解：pfirstpfirstlir