2024年6月13日发(作者：)

第1章

4．

答案：

（1）顺序存储结构

顺序存储结构是借助元素在存储器中的相对位置来表示数据元素之间的逻辑

关系，通常借助程序设计语言的数组类型来描述。

（2）链式存储结构

顺序存储结构要求所有的元素依次存放在一片连续的存储空间中，而链式存储

结构，无需占用一整块存储空间。但为了表示结点之间的关系，需要给每个结点附

加指针字段，用于存放后继元素的存储地址。所以链式存储结构通常借助于程序设

计语言的指针类型来描述。

5. 选择题

(1)~(6)：CCBDDA

6．

（1）O(1) （2）O(m*n) （3）O(n

2

)

（4）O(log

3

n) （5）O(n

2

) （6）O(

1

n

)

第2章

1．选择题

（1）~（5）：BABAD （6）~（10）： BCABD （11）~（15）：CDDAC

2．算法设计题

（1）将两个递增的有序链表合并为一个递增的有序链表。要求结果链表仍使用原

来两个链表的存储空间, 不另外占用其它的存储空间。表中不允许有重复的数据。

[题目分析]

合并后的新表使用头指针Lc指向，pa和pb分别是链表La和Lb的工作指针,

初始化为相应链表的第一个结点，从第一个结点开始进行比较，当两个链表La和

Lb均为到达表尾结点时，依次摘取其中较小者重新链接在Lc表的最后。如果两个

表中的元素相等，只摘取La表中的元素，删除Lb表中的元素，这样确保合并后

表中无重复的元素。当一个表到达表尾结点，为空时，将非空表的剩余元素直接链

接在Lc表的最后。

void MergeList(LinkList &La,LinkList &Lb,LinkList &Lc)

{//合并链表La和Lb，合并后的新表使用头指针Lc指向

pa=La->next; pb=Lb->next;

//pa和pb分别是链表La和Lb的工作指针,初始化为相应链表的第一个结点

Lc=pc=La; //用La的头结点作为Lc的头结点

while(pa && pb)

{ if(pa->datadata){pc->next=pa; pc=pa; pa=pa->next;}

//取较小者La中的元素，将pa链接在pc的后面，pa指针后移

else if(pa->data>pb->data) {pc->next=pb; pc=pb; pb=pb->next;}

//取较小者Lb中的元素，将pb链接在pc的后面，pb指针后移

else //相等时取La中的元素，删除Lb中的元素

{pc->next=pa;pc=pa;pa=pa->next;

q=pb->next; delete pb ; pb =q;

}

}

pc->next=pa?pa:pb; //插入剩余段

delete Lb; //释放Lb的头结点

}

（5）设计算法将一个带头结点的单链表A分解为两个具有相同结构的链表B、

C，其中B表的结点为A表中值小于零的结点，而C表的结点为A表中值大于零

的结点（链表A中的元素为非零整数，要求B、C表利用A表的结点）。

[题目分析]

B表的头结点使用原来A表的头结点，为C表新申请一个头结点。从A表的

第一个结点开始，依次取其每个结点p，判断结点p的值是否小于0，利用前插法，

将小于0的结点插入B表,大于等于0的结点插入C表。

[算法描述]

void DisCompose(LinkedList A)

2