考研专业课之统考计算机蓝宝书(8)

来源：跨考网 2008-11-26 19:14

1.7 习题答案

1. A 2. B 3. C 4. D 5. A 6.B 7. C 8. C

9 采用链式存储结构，它根据实际需要申请内存空间，而当不需要时又可将不
用结点空间返还给系统。在链式存储结构中插入和删除操作不需要移动元素。

订阅收藏考研专业课之统考计算机蓝宝书

10 在线性表的链式存储结构中，头指针指链表的指针，若链表有头结点则是链
表的头结点的指针，头指针具有标识作用，故常用头指针冠以链表的名字。头结点是为了操作的统一、方便而设立的，放在第一元素结点之前，其数据域一般无意义（当然有些情况下也可存放链表的长度、用做监视哨等等），有头结点后，对在第一元素结点前插入结点和删除第一结点，其操作与对其它结点的操作统一了。而且无论链表是否为空，头指针均不为空。首元结点也就是第一元素结点，它是头结点后边的第一个结点。

[算法讨论]本算法先找结果链表的第一个元素，这是因为题目要求结果表要递增有序（即删除重复元素）。这就要求当前待合并到结果表的元素要与其前驱比较。由于初始pre=A（头结点的头指针），这时的data域无意义，不能与后继比较元素大小，因此就需要确定第一个元素。当然，不要这样作，而直接进入下面循环也可以，但在链入结点时，必须先判断pre是否等于A，这占用了过多的时间。因此先将第一结点链入是可取的。
算法中的第二个问题是要求时间复杂度为O（|A|+|B|+|C|）。这就要求各个表的工作指针只能后移（即不能每次都从头指针开始查找）。本算法满足这一要求。
最后一个问题是，当B，C有一表为空（即B和C已无公共元素时），要将A的剩余部分链入结果表。

14 [题目分析] 本题实质上是一个模式匹配问题，这里匹配的元素是整数而不是
字符。因两整数序列已存入两个链表中，操作从两链表的第一个结点开始，若对应数据相等，则后移指针；若对应数据不等，则A链表从上次开始比较结点的后继开始，B链表仍从第一结点开始比较，直到B链表到尾表示匹配成功。A链表到尾B链表未到尾表示失败。操作中应记住A链表每次的开始结点，以便下趟匹配时好从其后继开始。