习题

1.填空题

（1）已知一个顺序存储的线性表，设每个结点需占m个存储单元，若第0个元素的地址为address，则第i个结点的地址为_____。

（2）线性表有两种存储结构：顺序存储结构和链式存储结构，就两种存储结构完成下列填空：

_____存储密度较大，_____存储利用率较高，_____可以随机存取，_____不可以随机存取，_____插入和删除操作比较方便。

（3）顺序表中逻辑上相邻的元素在物理位置上_____，在链表中逻辑上相邻的元素的物理位置_____相邻。

（4）一个长度为n的顺序表中，在第i个元素（0≤i≤n）之前插入一个新元素，具有最坏时间复杂度，对应的i值是_____，具有最好时间复杂度，对应的i值是_____。

（5）在顺序表la的第i个元素前插入一个新元素，则有效的i值范围是_____；在顺序表lb的第j个元素之后插入一个新元素，则j的有效范围是_____；要删除顺序表lc的第k个元素，则k的有效范围是_____。

（6）在n个结点的顺序表中插入一个结点，平均需要移动_____个结点，具体的移动次数取决于_____和_____。

（7）在n个结点的单链表中要删除已知结点*p，需要找到_____，其时间复杂度为_____；在双链表中要删除已知结点*p，其时间复杂度为_____；

（8）在单链表中要在已知结点*p之前插入一个新结点，需找到_____，其时间复杂度为_____；而在双链表中，完成同样操作时其时间复杂度为_____。

（9）在单链表上，删除指针p所指结点的后继结点的语句是_____。

（10）带头结点的单链表（头结点由head指向），对其判空的条件是_____；不带头结点的单链表（第一个结点由head指向），对其判空的条件是_____；带头结点的单向循环链表（头结点由head指向），对其判空的条件是_____；不带头结点的单向循环链表（第一个结点由head指向），对其判空的条件是_____。

（11）删除带头结点的单链表（头结点由head指向）的第一个结点的语句是_____，删除不带头结点的单链表（第一个结点由head指向）的第一个结点的语句是_____。

（12）在一双向循环链表上，要交换指针p所指结点的前驱与后继结点的值，则相应的操作语句是_____。

（13）在双向循环链表中（头结点由head指向），指针p所指的结点是该链表的尾结点的条件是_____。

2.判断题

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

（2）链表中指向第一个结点的指针称为头指针。

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

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

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

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

（7）对单链表的插入运算，带头结点的单链表与不带头结点的单链表相比，前者对应的算法更简单。

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

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

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

3.简答题

（1）比较双向循环链表与单向循环链表，试简述各自的优缺点。

（2）描述下列算法的功能。

ListNode* Demo1(LinkList head,ListNode *p)
{  /* head是指向单链表的头指针 */
   q=head->next;
   while(q&&q->next!=p)
      q=q->next;
   return(q);
}

（3）描述下列算法的功能。

void Demo2(ListNode *p,ListNode *q)
{  temp=p->data;
   p->data=q->data;
   q->data=temp;
}

4.算法设计题

（1）试用顺序表作为存储结构，编写算法实现线性表就地逆置的操作，即在原表的存储空间中将线性表（a1,a2,…,an）逆置为（an,an-1,…,a1）。

（2）写一算法，从顺序表中删除自第i个元素开始的k个元素。

（3）若已建立一个带有头结点的单向链表，h为指向头结点的指针，且链表中存放的数据按由小到大的顺序排列。编写函数实现算法，把x值插入到链表中，插入后链表中结点数据仍保持有序。

（4）假设在长度大于1的单循环链表中，既无头结点也无头指针，p为指向该链表中某个结点的指针，编写算法实现删除该结点的前驱结点。

（5）设h为一指向单向链表头结点的指针，该链表中结点的值按非降序排列，设计算法删除链表中值相同的结点，使之只保留一个。

（6）对给定的带头结点的单链表，h为指向头结点的指针，编写一个删除表中值为x的结点的直接前驱结点的算法。

（7）如果以单链表表示集合，假设集合A用单链表la表示，集合B用单链表lb表示，设计算法求两个集合的差，即A-B。

（8）假设线性表a、b表示两个集合，即同一个线性表中的元素各不相同，且均以元素值递增有序排列，现要求构成一个新的线性表c，c表示集合a与b的交，且c中元素也递增有序。试分别以顺序表和单链表为存储结构，编写实现上述运算的算法。

（9）已知线性表的元素是无序的，且以带头结点的单链表作为存储结构，试编写算法实现删除表中所有值大于min且小于max的元素。

（10）已知在单链表表示的线性表中，含有两类字符的数据元素，如字母字符和数字字符，试编写算法构造两个以循环链表表示的线性表，使每个表中只含同一类的字符，且利用原表中的结点空间作为这两个表的结点空间，头结点可另辟空间。

（11）有两个双向循环链表，头指针分别为head1和head2，编写一个函数将链表 head1链接到链表 head2 ，链接后的链表仍是循环链表。

（12）已知一带头结点的双向循环链表，指向头结点的指针为head，p指针指向其中某一结点，写一算法删除p指向结点的前驱。