习题21.填空题（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.单向B.双向C.静态D.动态（4）将线性表存储到计算机中可以采用多种不同的方法，按顺序存储方法存储的线性表称为（），按链式存储方法存储的线性表称为（）。A.数组单链表B.顺序表链表C.向量静态链表D.静态链表动态链表（5）（）是STL中线性表的链式存储形式，STL标准库中一般采用（）实现。A.vector数组B.list单链表C.list双向循环链表D.vector单链表（6）顺序表的类型定义可经编译转换为机器级。假定每个结点变量占用k(k>=1)个字节，b是顺序表的第一个存储结点的第一个单元的内存地址，那么，第个结点的存储地址为iai（）。A.b+kiB.b+k(i-1)C.b+k(i+1)D.b-1+ki（7）在循环链表中，若不使用头指针而改设为