1.3 章真题解析

1.3 本章真题解析

　　在本章的知识中，需要考生重点掌握的对象是顺序存储结构和链式存储结构，以及线性表的应用。本节按照研究生入学考试的试题样式，参考历年的真题和全国40所高校的研究生入学试题，组织了相关的真题及解析，供读者学习。

1.3.1 单项选择题

　　例题1
　　某算法将长度为n的单链表链接在长度为m的单链表之后，则该算法的时间复杂度为 （1） 。
　　（1）A．O(1) B．O(n)
　　　　C．O(m) D．O(m+n)
　　例题1分析
　　由于将长度为n的单链表链接在长度为m的单链表之后的操作，需要把长度为m的单链表遍历一次，找到最后一个结点，所以时间复杂度为O(m)。
　　例题1答案
　　（1）C
　　例题2
　　链表不具有的特点是 （2） 。
　　（2）A．可随机访问任一个元素 B．插入和删除时不需要移动元素
　　　　C．不必事先估计存储空间 D．所需空间与线性表的长度成正比
　　例题2分析
　　“可随机访问任一个元素”不是链表的特点，而是顺序表的特点。链表的元素不可以直接随机访问，一般是通过从链表的起始依次搜索得到的。
　　例题2答案
　　（2）A
　　例题3
　　在非空的循环单链表中，first是头结点，尾结点由p所指向，则满足 （3） 。
　　（3）A．p->next==NULL B．p==NULL
　　　　C．p->next==first D．p==first
　　例题3分析
　　由于是循环单链表，最后一个结点的指针指向头结点，即p->next==first。
　　例题3答案
　　（3）C
　　例题4
　　将两个各有N1和N2个元素的有序表（递增）归并成一个有序表，仍保持其递增顺序，则最少的比较次数是 （4） 。
　　（4）A．N1 B．N2 C．N1+N2-1 D．MIN(N1,N2)
　　例题4分析
　　当一个表中的所有元素都大于另外一个表中的所有元素时，比较次数最少。此时，需要比较的次数是MIN(N1,N2)。
　　例题4答案
　　（4）D
　　例题5
　　静态链表中指针表示的是 （5） 。
　　（5）A．下一元素的地址 B．内存储器的地址
　　　　C．下一元素在数组中的位置 D．左链或者右链指向的元素地址
　　例题5分析
　　静态链表就是数组表，其指针表示的就是下一元素在数组中的位置。
　　例题5答案
　　（5）C
　　例题6
　　以下关于线性表采用链式存储时删除结点运算的描述，正确的是 （6） 。
　　（6）A．带头结点的线性链表删除结点时，不需要更改头指针
　　　　B．带头结点的线性链表删除第一个结点时，需要更改头指针
　　　　C．不带头结点的线性链表删除结点时，需要更改头指针
　　　　D．不带头结点的线性链表删除第一个结点时，不需要更改头指针
　　例题6解析
　　带头结点的线性链表的头指针指向其头结点，而该头结点是不能被删除的，所以头指针的值不需要更改。不带头结点的线性链表在删除第一个结点后，需要将头指针指向新的第一个结点，而如果删除其他结点，则不需要更改头指针。
　　例题6答案
　　（6）A
　　例题7
　　线性链表中各链接点之间的地址 （7） 。
　　（7）A．必须连续 B．部分地址必须连续
　　　　C．不一定连续 D．和头结点的存储地址相连续
　　例题7分析
　　线性链表结构的特点是用一组任意的存储单元存储线性表的数据元素，这组存储单元可以是连续的，也可以是不连续的，所以，线性链表中各链接点之间的地址不一定连续。
　　例题7答案
　　（7）C