学步园

一、填空题：

1、表中一半  
表长和该元素在表中的位置 
2、n-i+1    3、n-i

4、O(1)     
随机存取  5、必定  不一定
6、其直接前驱结点的链域的值

7、前驱结点的地址  
O（n）   8、有限、一对一

二、判断题

1、链表的每个结点中都恰好包含一个指针。（
X  ） 

2、链表的物理存储结构具有同链表一样的顺序。（X ）

3、链表的删除算法很简单，因为当删除链中某个结点后，计算机会自动地将后续的各个单元向前移动。（
X ）

4、线性表的每个结点只能是一个简单类型，而链表的每个结点可以是一个复杂类型。（
X ）

5、顺序表结构适宜于进行顺序存取，而链表适宜于进行随机存取。（ 
X   ）

6、顺序存储方式的优点是存储密度大，且插入、删除运算效率高。（ 
X  ）

7、线性表在物理存储空间中也一定是连续的。（  
X   ）

8、线性表在顺序存储时，逻辑上相邻的元素未必在存储的物理位置次序上相邻。（X）

9、顺序存储方式只能用于存储线性结构。（ X ）

10、线性表的逻辑顺序与存储顺序总是一致的。（ 
X    ）

三、选择题

1、C、顺序存储结构 2、B、108
3、A、访问第i个结点（1≤i≤n）和求第i个结点的直接前驱（2≤i≤n）
4、B、63.5  5、A、
分两部分，一部分存放结点值，另一部分存放表示结点间关系的指针
6、B、链式 7、D、连续或不连续都可以 8、B
 9、C、小于1 10、B、单链表

四、简答题：

1、试比较顺序存储结构和链式存储结构的优缺点。在什么情况下用顺序表比链表好？

答：①
顺序存储时，相邻数据元素的存放地址也相邻（逻辑与物理统一）；要求内存中可用存储单元的地址必须是连续的。

优点：存储密度大（＝1），存储空间利用率高。缺点：插入或删除元素时不方便。

②链式存储时，相邻数据元素可随意存放，但所占存储空间分两部分，一部分存放结点值，另一部分存放表示结点间关系的指针

优点：插入或删除元素时很方便，使用灵活。缺点：存储密度小（<1），存储空间利用率低。

顺序表适宜于做查找这样的静态操作；链表宜于做插入、删除这样的动态操作。

若线性表的长度变化不大，且其主要操作是查找，则采用顺序表；

若线性表的长度变化较大，且其主要操作是插入、删除操作，则采用链表。

2、描述以下三个概念的区别：头指针、头结点、首元结点（第一个元素结点）。在单链表中设置头结点的作用是什么？

答：头指针是指向链表中第一个结点（或为头结点或为首元结点）的指针；头结点是在链表的首元结点之前附设的一个结点；数据域内只放空表标志和表长等信息；首元素结点是指链表中存储线性表中第一个数据元素a₁的结点。