数据结构典型例题解析.doc

《数据结构典型例题解析.doc》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第2章线性表典型例题解析一、选择题1．线性表是具有n个（n≥0）的有限序列。A．表元素B．字符C．数据元素D．数据项【分析】线性表是具有相同数据类型的n（n≥0）个数据元素的有限序列，通常记为(a1,a2,…,an)，其中n为表长，n=0时称为空表。【答案】C2．顺序存储结构的优点是。A．存储密度大B．插入运算方便C．删除运算方便D．可方便地用于各种逻辑结构的存储表示【分析】顺序存储结构是采用一组地址连续的存储单元来依次存放数据元素，数据元素的逻辑顺序和物理次序一致。因此，其存储密度大。【答案】A3．带头结点的单链表head为空的判断条件是。A．head==NULLB．head->next=

2、=NULLC．head->next==headD．head!=NULL【分析】链表为空时，头结点的指针域为空。【答案】B4．若某线性表中最常用的操作是在最后一个元素之后插入一个元素和删除第一个元素，则采用存储方式最节省运算时间。A．单链表B．仅有头指针的单循环链表C．双链表D．仅有尾指针的单循环链表【分析】根据题意要求，该线性表的存储应能够很方便地找到线性表的第一个元素和最后一个元素，A和B都能很方便地通过头指针找到线性表的第一个元素，却要经过所有元素才能找到最后一个元素；选项C双链表若存为双向循环链表，则能很方便地找到线性表的第一个元素和最后一个元素，但存储效率要低些，插入和删除操作也略微

3、复杂；选项D可通过尾指针直接找到线性表的最后一个元素，通过线性表的最后一个元素的循环指针就能很方便地找到第一个元素。【答案】D5．若某线性表最常用的操作是存取任一指定序号的元素和在最后进行插入和删除运算，则利用存储方式最节省时间。A．顺序表B．双链表C．带头结点的双循环链表D．单循环链表【分析】某线性表最常用的操作是存取任一指定序号的元素和在最后进行插入和删除运算。因此不需要移动线性表种元素的位置。根据题意要求，该线性表的存储应能够很方便地找到线性表的任一指定序号的元素和最后一个元素，顺序表是由地址连续的向量实现的，因此具有按序号随机访问的特点。链表需要通过指针才能找到线性表的莫以指定序号的

4、元素，需要一定的时间开销。【答案】A6．设一个链表最常用的操作是在末尾插入结点和删除尾结点，则选用最节省时间。A.单链表B.单循环链表C.带尾指针的单循环链表D.带头结点的双循环链表【分析】根据题意要求，该线性表的存储应能够很方便地找到线性表的最后一个元素和最后一个元素的前驱元素，A和B都不能很方便地通过头指针找到线性表的第一个元素；选项C可以方便地找到最后一个元素，单不能很快地找到其前驱元素；选项D为双向循环链表，可以很方便地找到线性表的最后一个元素，通过其前驱指针，从而可以方便地找到其前驱元素。【答案】D7．静态链表中指针表示的是。A．内存地址B．数组下标C．下一元素地址D．左、右孩子地

5、址【分析】静态链表采用的是链式方式存储线性表，以数组方式存储链表的数据，指针域存储的是该结点逻辑上的后继结点的相对地址（即在数组中的下标），也称为静态指针。【答案】B8．链表不具有的特点是。A．插入、删除不需要移动元素B．可随机访问任一元素C．不必事先估计存储空间D．所需空间与线性长度成正比【分析】链表是通过一组任意的存储单元来存储线性表中的数据元素的，为建立起数据元素之间的线性关系，对每个数据元素，除了存放数据元素自身的信息之外，还需要和存放其后继元素所在的存储单元的地址。链表不具有按序号随机访问第i个元素的特点，必须通过标识链表的头指针（或尾指针）“顺藤摸瓜”才能找到第i个结点。【答案】

6、B9．线性表的静态链表存储结构与顺序存储结构相比优点是。A．所有的操作算法简单B．便于插入和删除C．便于利用零散的存储器空间D．便于随机存取【分析】静态链表采用的是链式方式存储线性表，因此其具有链式存储的特点。【答案】B10．若长度为n的线性表采用顺序存储结构，在其第i个位置插入一个新元素算法的时间复杂度为。A．O(log2n)B．O(1)C．O(n)D．O(n2)【分析】在第i个位置上插入新元素需要从最后一个元素开始后移直到第i个元素后移为止，后移元素的次数为n-i+1，即时间复杂度为O(n)。【答案】C11．线性表（a1,a2,…,an）以链接方式存储时，访问第i个位置元素的时间复杂性为

7、。A．O(i)B．O(1)C．O(n)D．O(i-1)【分析】线性表以链接方式存储时，访问第i个位置元素从第一个元素开始移动指针到第i个元素，移动指针的次数为n-i+1，即时间复杂度为O(n)。【答案】C12．将两个各有n个元素的有序表归并成一个有序表，其最少的比较次数是。A．nB．2n-1C．2nD．n-1【分析】当一个表的最小元素大于另一个表的最大元素时比较次数为最少，共需n次。【答案】A13．非空的循环