1.3 章真题解析

　　例题8
　　如果单链表中最常用的操作是在最后一个结点后插入一个结点和删除最后一个结点，则 （8） 存储方式最节省运行时间。
　　（8）A．单链表 B．带头结点的单链表
　　　　C．单循环链表 D．带头结点的双向循环链表
　　例题8分析
　　在最后一个结点后插入一个结点，则需要获取最后一个结点的指针；删除最后一个结点，则需要获取最后一个结点前驱结点的指针。因此，采取带头结点的双向循环链表的存储方式最节省运行时间。
　　例题8答案
　　（8）D
　　例题9
　　以下关于线性表的描述，正确的是 （9） 。
　　（9）A．线性表中并不是所有的元素都有一个直接前驱和一个直接后继
　　　　B．线性表的顺序存储结构插入和删除时效率太低，因此，它不如链式存储结构好
　　　　C．线性表的链式存储结构的元素随机访问效率太低，因此，它不如顺序存储结构好
　　　　D．顺序存储方式的优点是存储密度大，且插入、删除运算效率高
　　例题9分析
　　线性表的首结点没有直接前驱，尾结点没有直接后继，选项A正确。
　　线性表的顺序存储结构和链式存储结构各有优缺点，不同的需求适用于不同的存储结构，不能直接断言谁好谁坏，选项B、C错误。
　　线性表的顺序存储结构存储密度随数据元素的增加而增大，其插入和删除操作需要移动数据元素，相对于链式存储结构而言效率低，选项D错误。
　　例题9答案
　　（9）A
　　例题10
　　若要在O(1)的时间复杂度上实现两个循环链表头尾相接，则对应两个循环链表各设置一个指针，分别指向 （10） 。
　　（10）A．各自的头结点 B．各自的尾结点
　　　　　C．各自的第一个元素结点 D．一个表的头结点，另一个表的尾结点
　　例题10分析
　　在O(1)的时间复杂度上实现两个循环链表头尾相接时，需要把头结点和尾结点之间的指针改变指向，而这个指针是从尾结点指向头结点的，所以，只有将两个指针指向自己循环链表的尾结点才能完成操作。
　　例题10答案
　　（10）B
　　例题11
　　若长度为n的线性表采用顺序存储结构，在其第i个位置插入一个新元素的算法的时间复杂度为（11） (1≤i≤n+1)。
　　（11）A．O(0) B．O(1) C．O(n) D．O( n²)
　　例题11分析
　　假定在线性表的任何位置上插入元素的概率pi是相等的，则在长度为n的线性表中插入一个元素时所需要移动元素的平均次数为。由此可见，在长度为n的线性表中插入元素的时间复杂度为O(n)。同理，可以计算出在长度为n的线性表中删除一个元素的时间复杂度也为O(n)。
　　对于这类题目，考生在复习时要能够计算出进行插入或删除操作时，平均需要移动元素的次数。
　　例题11答案
　　（11）C
　　例题12
　　线性表的顺序存储结构，设其长度为n，在任何位置插入和删除操作都是等概率的。删除一个元素时平均大约需要移动表中的 （12） 个元素。
　　（12）A．n/2 B．(n-1)/2
　　　　　C．n+1 D．n-1
　　例题12分析
　　在长度为n的线性表中删除一个元素时，所需要移动元素的平均次数为 。
　　例题12答案
　　（12）B
　　例题13
　　下列叙述中，不正确的是 （13） 。
　　（13）A．线性表在链式存储时，查找第i个元素的时间与i的值成正比
　　　　　B．线性表在链式存储时，查找第i个元素的时间与i的值有关
　　　　　C．线性表在顺序存储时，查找第i个元素的时间与i的值成正比
　　　　　D．线性表在顺序存储时，查找第i个元素的时间与i的值无关
　　例题13分析
　　顺序存储结构的特点是“顺序存储，随机存取”，也就是说，线性表在顺序存储时，查找第i个元素的时间与i的值无关。
　　链式存储结构的特点则是“随机存储，顺序存取”，也就是说，链式存储结构的数据元素可以随机地存储在内存单元中，但访问其中的任意一个数据元素时，都必须从其头指针开始逐个进行访问。
　　例题13答案
　　（13）C
　　例题14
　　对于一个头指针为head的带头结点的双向循环链表，可以作为判定该线性表为空表的条件是 （14） 。
　　（14）A．head==NULL B．head->next==NULL
　　　　　C．head->next==head D．head!=NULL
　　例题14分析
　　头指针为head的带头结点的双向循环链表为空的判断条件为：head->next=head。
　　例题14答案
　　（14）C
　　例题15
　　以下关于静态链表的描述中，正确的是 （15） 。
　　（15）A．静态链表既有顺序存储的优点，又有动态链表的优点。所以，它存取表中第i个元素的时间与i无关
　　　　　B．静态链表不需要一开始就分配所有的存储空间，可以在插入数据元素时再申请
　　　　　C．静态链表与动态链表在元素的插入、删除操作上类似，不需移动元素
　　　　　D．静态链表的指针域存储的是数据元素的内存地址
　　例题15分析
　　静态链表使用了一片连续的存储空间，因此，必须一次性分配其所需要的存储空间。静态链表中第i个数据元素不一定存储在第i块存储单元中，因此，不能被随机访问。事实上，为了访问静态链表的第i个数据元素，仍然需要从首元素开始遍历i个数据元素。
　　静态链表中每个结点都有指针域，执行插入和删除操作时，只需更改指针域即可，无须移动数据元素。静态链表的指针域中保存的是数组的下标，而不是数据元素的绝对存储地址。
　　例题15答案
　　（15）C
　　例题16
　　双向循环链表中，在p所指向的结点之后插入s指向的结点，其修改指针的操作是 （16） ，其中p指向的不是最后一个结点。
　　（16）A．p->next=s; s->prev=p; p->next->prev=s; s->next=p->next;
　　　　　B．p->next->prev=s; p->next=s; s->prev=p; s->next=p->next;
　　　　　C．s->prev=p; s->next=p->next; p->next=s; p->next->prev=s;
　　　　　D．s->prev=p; s->next=p->next; p->next->prev=s; p->next=s;
　　例题16分析
　　其插入方法如图1-13所示。
　　一般情况下，做此类题的一个捷径是判断代码“p->next=s”后是否还有通过指针“p->next”访问p以前的直接后继的引用，有则错误。因为一旦执行完代码“p->next=s”，p的直接后继就更改为s，此后，“p->next”不再是p以前的直接后继。例如，试题中A、B和C选项均在“p->next=s”之后使用了“p->next”，所以选项A、B和C错误，根据排除法，选项D正确。另外，建议考生在编写插入代码时，将“p->next=s”写成插入算法的最后一步。

　　例题16答案
　　（16）D