第二章 线性表 （答案版）

第二章 线性表 一、填空题 1、在顺序表中插入或删除一个元素，需要平均移动 n/2 元素，具体移动的元素个数与 插入位置 有关。 2、在顺序表中访问任意一结点的时间复杂度均为 O（C）/ O（1） ，因此，顺序表也称为 随机访问 的数据结构。 3、顺序表中逻辑上相邻的元素的物理位置 必定 相邻，单链表中逻辑上相邻的元素的物理位置 不一定 相邻。 4、在单链表中，除了首元结点外，任一结点的存储位置由 此逻辑前驱结点的指针 指示 。 5、 在n个结点的单链表中要删除已知结点*p，需找到它的 前驱结点 ，其时间复杂度为 O(n) 。 二、判断正误 （ F ）1、链表的每个结点中都恰好包含一个指针。 （ F ）2、链表的物理存储结构具有同链表表达的逻辑结构有一样的顺序。 （ F ）3、线性表的每个结点只能是一个简单类型，而链表的每个结点可以是一个复杂类型。 （ F ）4、顺序表结构适宜于进行顺序存取，而链表适宜于进行随机存取。 （ F ）5、顺序存储方式的优点是存储密度大，且插入、删除运算效率高。 （ F ）6、线性表在物理存储空间中也一定是连续的。 （ F ）7、线性表在顺序存储时，逻辑上相邻的元素未必在存储的物理位置次序也相邻。 （ F ）8、线性表的逻辑顺序与存储顺序总是一致的。 三、单项选择题 1、数据在计算机存储器内表示时，物理地址与逻辑地址相同并且是连续的,称之为：C A、存储结构 B、逻辑结构 C、顺序存储结构 D、链式存储结构 2、一个向量第一个元素的存储地址是100，每个元素的长度为2，则第5个元素的地址是 B A、110 B、108 C、100 D、120 3、在n个结点的顺序表中，算法的时间复杂度是O（1）的操作是： A A、访问第i个结点（1≤i≤n）和求第i个结点的直接前驱（2≤i≤n） B、在第i个结点后插入一个新结点（1≤i≤n） C、删除第i个结点（1≤i≤n） D、将n个结点从小到大排序 4、向一个有127个元素的顺序表中插入一个新元素并保持原来顺序不变，平均要移动多少个元素： B A、8 B、63.5 C、63 D、7 5、链接存储的存储结构所占存储空间： A A、分两部分，一部分存放结点值，另一部分存放表示结点间关系的指针 B、只有一部分，存放结点值 C、只有一部分，存储表示结点间关系的指针 D、分两部分，一部分存放结点值，另一部分存放结点所占单元数 6、线性表若采用链式存储结构时，要求内存中可用存储单元的地址: D A、必须是连续的 B、部分地址必须是连续的 C、一定是不连续的 D、连续或不连续都可以 7、线性表Ｌ在那种情况下适用于使用链式结构实现。 B A、需经常修改Ｌ中的结点值 B、需不断对Ｌ进行删除插入 C、Ｌ中含有大量的结点 D、Ｌ中结点结构复杂 8、在非空双向循环链表(节点指针域分别为pre 和next)中q所指的结点前插入一个由p所指的链结点的过程依次为: D A、q->pre=p; p->next=q; B、t=q->pre; t->next=p; p->next=q; C、t=q->pre; t->next=p; p->pre=t; p->next=q; D、t=q->pre; t->next=p; p->next=q; q->pre=p; p->pre=t; 9、带头结点的单链表L为空的判定条件是： B A、L==NULL B、 L->next==NULL C、 L->next==L D、 L!=NULL 10、若某表最常用的操作是在最后一个结点之后插入一个结点或删除第一个结点。则采用什么存储方式最节省运算时间：C A、带头结点的单链表 B、不带头结点的双向链表 C、头指针指向最后一个结点的单循环链表 D、带头结点的双循环链表 四、简答题 1、试比较顺序存储结构和链式存储结构的优缺点。在什么情况下用顺序表比链表好？ 顺序表需要在内存中预先开辟一个连续的、足够大的空间进行保存， 顺序表的特点是逻辑上相邻的元素在内存结点位置也要相邻，即逻辑相邻物理也相邻。存储密度高，为1， 顺序表在定位查找比较快捷，但插入删除需要移动大量元素，所以时间效率不高。 链表由于采用指针表示数据元素原先的逻辑关系，因此，链表不需要预先开辟空间，每需要一个存储单元就申请一个， 链表中元素的逻辑关系依赖指针保持，因