1.1 序存储结构的存储结构和实现--考研乐学帮

1.1 序存储结构的存储结构和实现

1.1 顺序存储结构的存储结构和实现

一、选择题

　　1．选择题题目部分
　　● 线性表是具有n个（1）的有限序列（n>0）。
　　（1）A．表元素 B．字符 C．数据元素 D．数据项
　　● 下述（2）是顺序存储结构的优点？
　　（2）A．存储密度大 B．插入运算方便
　　C．删除运算方便 D．可方便地用于各种逻辑结构的存储表示
　　● 若长度为n的线性表采用顺序存储结构，在其第i个位置插入一个新元素的算法的时间复杂度为（3）（1≤i≤n+1）。
　　（3）A．O(0) B．O(1) C．O(n) D．O(n2)
　　● 线性表的顺序存储结构，设其长度为n，在任何位置插入和删除操作都是等概率的。删除一个元素时平均大约需要移动表中的（4）个元素。
　　（4）A．n/2 B．(n-1)/2 C．n+1 　　　 D．n-1
　　● 下面的叙述不正确的是（5）。
　　（5）A．线性表在链式存储时，查找第i个元素的时间同i的值成正比
　　B．线性表在链式存储时，查找第i个元素的时间同i的值无关
　　C．线性表在顺序存储时，查找第i个元素的时间同i的值成正比
　　D．线性表在顺序存储时，查找第i个元素的时间同i的值无关
　　2．选择题的答案与分析
　　题号（1）答案 C
　　习题分析：
　　这道题主要考查对线性表定义的理解。线性表是一个有n个数据元素的有限序列。数据元素是数据的基本单位，在计算机程序中，通常把数据元素作为基本单位进行处理。在复杂的数据结构中，一个数据元素又可以由若干个数据项组成，数据项是数据的最小单位。
　　题号（2）答案 A
　　习题分析：
　　这是一道基本概念题，主要考查对线性表顺序存储结构基本概念的理解。线性表的顺序存储结构就是指将线性表中的节点依次存放在计算机内存中一组地址连续的存储单元内。用C语言的数组即可实现线性表的顺序存储结构。在这种存储方式下，对线性表进行插入和删除运算需要移动大量的元素。对于一些比较复杂的逻辑结构，如树、图等，用顺序存储结构来实现时并不方便。因此，不难看出，正确答案为A。
　　题号（3）答案 C
　　习题分析：
　　这道题主要考查对于线性表顺序存储结构的插入操作的理解。假定在线性表的任何位置上插入元素的概率pi是相等的，则在长度为n的线性表中插入一个元素时所需要移动元素的平均次数为。由此可见，在长度为n的线性表中插入元素的时间复杂度为O(n)。同理，可以计算出在长度为n的线性表中删除一个元素的时间复杂度也为O(n)。对于这种题目，大家在复习时要能够计算出进行插入或删除操作时，平均需要移动元素的次数。
　　题号（4）答案 B
　　习题分析：
　　这道题与前一道题目类似，考查对于线性表的顺序存储结构的删除操作的理解。根据前一题的分析可知，在长度为n的线性表中删除一个元素时所需要移动元素的平均次数为。
　　题号（5）答案 B、C
　　习题分析：
　　这道题考查对于线性表的顺序存储结构和链式存储结构特点的理解。顺序存储结构的特点是“顺序存储、随机存取”，也就是说，线性表在顺序存储时，查找第i个元素的时间与i的值无关。
　　而链式存储结构的特点则是“随机存储，顺序存取”，即链式存储结构的数据元素可以随机地存储在内存单元中，但访问其中的任意一个数据元素时，都必须从其头指针开始逐个进行访问。因此，正确答案为B和C。
　　3．训练自测表（如表1-1所示）