数据结构第二章参考答案.pdfVIP

习题2

1.填空题

（1）在一个单链表中，已知每个结点包含data和next两个域，q所指结点是p所指结点的

直接前驱，若在q和p之间插入s所指结点，则执行（___________）和（___________）操

作。

答案：q-next=s;s-next=p;或s-next=q-next;q-next=s;

（2）表长为n的顺序表，当在任何位置上插入或删除一个元素的概率相等时，插入一个元

素所需移动元素的平均个数为（___________），删除一个元素需要移动元素的平均个数为

（___________）。

答案：n/2(n-1)/2

（3）表长为0的线性表称为（___________）。

答案：空表

（4）动态内存管理是操作系统的基本功能之一，其作用是响应用户程序对内存的

（___________）和（___________）请求。

答案：申请释放

（5）顺序表多采用（___________）实现的，是一种随机存取结构，对表中任意结点存取操

作的时间复杂度为（___________）。而查找链表中的结节，需要从头指针起顺着链扫描才

能得到，平均时间复杂度为（___________）。因此，若线性表的操作主要是进行查找，很

少进行插入或删除操作时，采用（___________）表比较合适。

答案：数组O(1)O(n)顺序

（6）在链表某个位置上进行插入和删除操作，只需要修改（___________）即可，而无须移

动大量元素，操作的时间复杂度为（___________）。而在顺序表中进行插入和删除操作，

往往要移动大量元素，平均移动元素的数目为（___________），平均时间复杂度为

（___________）。因此，若对线性表进行频繁的插入和删除操作时，采用（___________）

表相对合适。若插入和删除主要发生在表头和表尾，则采用（___________）表更为合适。

答案：指针O(1)表长的一半O(n)链循环链

（7）静态链表一般采用（___________）存储的链表结构。

答案：数组

（8）对于32位计算机环境，若单链表中的数据类型为整性，则其存储密度为（___________），

而若为双链表，则存储密度为（___________）。若采用顺序表存储数据，则其存储密度为

（___________）。

答案：50%33%1

（9）向量是最常用的容器，STL中向量使用（___________）实现，因此向量具有

（___________）表的所有特点，可以快速随机存取任意元素。

答案：数组顺序

（10）操作系统在运行之初，有一块很大的连续内存块供用户程序申请，通常称之为内存池

或（___________）。

答案：堆

（11）循环链表与单链表的区别仅仅在于其尾结点的链域值不是（___________），而是一个

指向（___________）的指针。

答案：NULL(或空指针)头结点

2.选择题

1

（1）线性表的顺序存储结构是一种（）的存储结构，线性表的链式存储结构是一

种（）的存储结构。

A.随机存取索引存取B.顺序存取随机存取

C.随机存取顺序存取D.索引存取散列存取

（2）在双向链表p所指结点之前插入s所指结点的操作是（）。

A.p-left=s;s-right=p;p-left-right=s;s-left=p-left;

B.p-right=s;p-right-left=s;s-left=p;s-right=p-right;

C.s-right=p;s-left=p-left;p-left=s;p-left-right=s;

D.s-right=p;s-left=p-left;p-left-right=s;p-left=s;

（3）若链表是利用C++指针来存储结点的地址，结点空间的分配和收回都是由操作符new

和delete动态执行的，则称该链表为（）链表

A.单向