第二章 线性表
一、选择题
1.一个顺序表第一个元素的存储地址是100,每个元素的长度为2,则第5个元素的地址是( )
（A）110 （B）108（C）100 （D）120
2. 向一个有127个元素的顺序表中插入一个新元素并保持原来顺序不变，平均要移动（ ）个元素。
（A）64（B）63 （C）63.5 （D）7
3.线性表采用链式存储结构时，其地址（ ）。
(A) 必须是连续的 (B) 部分地址必须是连续的
(C) 一定是不连续的 (D) 连续与否均可以
4. 在一个单链表中，若p所指结点不是最后结点，在p之后插入s所指结点，则执行（ ）
（A）s->next=p;p->next=s; （B）
s->next=p->next;p->next=s;
（C）s->next=p->next;p=s; （D）p->next=s;s->next=p;
5.在一个单链表中，若删除p所指结点的后续结点，则执行（ ）
（A）p->next=p->next->next; （B）p=p->next;
p->next=p->next->next;
（C）p->next=p->next; （D）p =p->next->next;
6.下列有关线性表的叙述中，正确的是（ ）
（A）线性表中的元素之间是线性关系 （B）线性表中至少有一个元素
（C）线性表中任何一个元素有且仅有一个直接前趋
（D）线性表中任何一个元素有且仅有一个直接后继
7.线性表是具有n个（ ）的有限序列（n≠0)
（A）表元素 （B）字符 （C）数据元素 （D）数据项
二、判断题
1.线性表的链接存储，表中元素的逻辑顺序与物理顺序一定相同。（ ）
2.如果没有提供指针类型的语言，就无法构造链式结构。（ ）
3.线性结构的特点是只有一个结点没有前驱，只有一个结点没有后继，其余的结点只有一个前驱和后继。（ ）
4.语句p=p->next完成了指针赋值并使p指针得到了p指针所指后继结点的数据域值。（ ）
第2章 线性表 自测卷
一、填空
1,在顺序表中插入或删除一个元素，需要平均移动 元素，具体移动的元素个数与 有关。
2,线性表中结点的集合是 的，结点间的关系是 的。
3,向一个长度为n的向量的第i个元素(1≤i≤n+1)之前插入一个元素时，需向后移动 个元素。
4,向一个长度为n的向量中删除第i个元素(1≤i≤n)时，需向前移动 个元素。
5,在顺序表中访问任意一结点的时间复杂度均为,因此，顺序表也称为 的数据结构。
6,顺序表中逻辑上相邻的元素的物理位置 相邻。单链表中逻辑上相邻的元素的物理位置 相邻。
7,在单链表中，除了首元结点外，任一结点的存储位置由 指示。
8,在n个结点的单链表中要删除已知结点*p，需找到它的,其时间复杂度为 。
二、判断正误
（ ）1,链表的每个结点中都恰好包含一个指针。
（ ）2,链表的物理存储结构具有同链表一样的顺序。
（ ）3,链表的删除算法很简单，因为当删除链中某个结点后，计算机会自动将后续各个单元向前移动。
（ ）4,线性表的每个结点只能是一个简单类型，而链表的每个结点可以是一个复杂类型。
（ ）5,顺序表结构适宜于进行顺序存取，而链表适宜于进行随机存取。
（ ）6,顺序存储方式的优点是存储密度大，且插入、删除运算效率高。
（ ）7,线性表在物理存储空间中也一定是连续的。
（ ）8,线性表在顺序存储时，逻辑上相邻的元素未必在存储的物理位置次序上相邻。
（ ）9,顺序存储方式只能用于存储线性结构。
（ ）10,线性表的逻辑顺序与存储顺序总是一致的。
三、单项选择题
（ ）1．数据在计算机存储器内表示时，物理地址与逻辑地址相同并且是连续的，称之为：
（A）存储结构 （B）逻辑结构 （C）顺序存储结构 （D）链式存储结构
（ ）2,一个向量第一个元素的存储地址是100，每个元素的长度为2，则第5个元素的地址是
（A）110 （B）108 （C）100 （D）120
数据结构与算法上机作业
第二章 线性表
计软1601-1405160112-郭伟
一、选择题
1、若长度为n的线性表采用顺序存储结构，在其第i个位置插入一个新的元素算法的时间复杂度为 C 。
A. O(log2n) B. O(1) C. O(n) D. O(n2)
2、以下关于线性表的说法中，不正确的是 C 。
A. 线性表中的数据元素可以是数字、字符、结构等不同类型
B. 线性表中包含的数据元素个数不是任意的
C. 线性表中的每一个结点都有且只有一个直接前驱和直接后继
D. 存在这样的线性表：表中各结点都没有直接前驱和直接后继
3、在有n个结点的顺序表上做插入、删除结点运算的时间复杂度为 B 。
A. O(1) B. O(n) C. O(n2) D. O(log2n)
4、等概率情况下，在有n个结点的顺序表上做插入结点操作，需平均移动的结点数目为
C 。提示：插入的位置有n+1个，移动总数为：1+2+3+……+n
A. n B. (n-1)/2 C. n/2 D. (n+1)/2
5、在一个长度为n的顺序存储的线性表中查找值为x的元素时，平均查找长度(及x同元素的平均比较次数，假定查找每个元素的概率都相等)为 C 。
A. n B. n/2 C. (n+1)/2 D. (n-1)/2
6、在顺序表中，只要知道 D ，就可以求出任一结点的存储地址。
A. 基地址 B. 结点大小 C. 向量大小 D. 基地址和结点大小
7、将两个各有n个元素的有序表归并为一个有序表，其最少的比较次数是 A 。
A. n B. 2n-1 C. 2n D. n-1
8、线性表采用链表存储时其存储地址要求 D 。
A. 必须是连续的 B. 部分地址必须是连续的
第二章 线性表
线性结构：在数据元素的非空集中，
①存在唯一的一个首元素，
②存在唯一的一个末元素，
③除首元素外每个元素均只有一个直接前驱，
④除末元素外每个元素均只有一个直接后继。
第一节 逻辑结构
形式定义：
Linear_list=(D，S，P)
D = {ai| ai∈ElemSet, i=0,1,2,…,n-1}
S = {| ai-1,ai∈D, i=1,2,…,n-1}
为序偶，表示前后关系
基本操作P：
①插入、删除、修改，存取、遍历、查找。
void ListAppend(List L, Elem e) ;
void ListDelete(List L, int i) ;
int SetElem(List L, int i, Elem e);
int GetElem(List L, int i, Elem &e);
int ListLength(List L);
void ListPrint(List L);
int LocateElem(List L, Elem e);
②合并、分解、排序
基本操作的用途：
集合的并、交、差运算
有序线性表的合并、多项式的运算
例：利用线性表LA和LB分别表示集合A和B，求A=A∪B。
void union(List &La，List Lb)
{ int La_len, Lb_len;
La_len=ListLength(La); // 计算表长 Lb_len=ListLength(Lb);
for(i=1; i<=Lb_len; i++)
{ GetElem(Lb, i, e); // 取Lb的第i个元素
if(!LocateElem(La, e)) // 在La中查找e
