习题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. 单向 B. 双向 C. 静态 D. 动态
（4）将线性表存储到计算机中可以采用多种不同的方法，按顺序存储方法存储的线性表称为（ ），按链式存储方法存储的线性表称为（ ）。
A. 数组 单链表 B. 顺序表 链表 C. 向量 静态链表 D. 静态链表 动态链表 （5）（ ）是STL中线性表的链式存储形式，STL标准库中一般采用（ ）实现。
A. vector 数组 B. list 单链表 C. list 双向循环链表 D. vector 单链表
（6）顺序表的类型定义可经编译转换为机器级。假定每个结点变量占用k(k>=1)个字节，b是顺序表的第一个存储结点的第一个单元的内存地址，那么，第i个结点ai的存储地址为（ ）。 A. b+ki B. b+k(i-1) C. b+k(i+1) D. b-1+ki （7）在循环链表中，若不使用头指针而改设为尾指针（rear），则头结点和尾结点的存储位置分别是（ ）。
A. real和rear->next->next B. rear->next 和rear C. rear->next->next和rear D. rear和rear->next
（8）有时为了叙述方便，可以对一些概念进行简称，以下说法错误的是（ ）。 A. 将“指针型变量”简称为“指针” B. 将“头指针变量”简称为“头指针”
C. 将“修改某指针型变量的值” 简称为“修改某指针” D. 将“p中指针所指结点” 简称为“P值” （9）以下说法错误的是（ ）。
A. 对循环链表来说，从表中任一结点出发都能通过向前或向后操作而扫描整个循环链表。 B. 对单链表来说，只有从头结点开始才能扫描表中全部结点。 C. 双链表的特点是找结点的前趋和后继都很容易。
D. 对双链表来说，结点*P的存储位置既存放在其前趋结点的后继指针域中，也存放在它的后继结点的前趋指针域中。
（10）以下说法正确的是（ ）。
A. 顺序存储方式的优点是存储密度大、且插入、删除运算效率高。 B. 链表的每个结点中都至少包含一个指针。 C. 线性表的顺序存储结构优于链式存储结构。
D. 顺序存储结构属于静态结构，链式结构属于动态结构。
2
说明:静态链表是链式结构,但属于静态存储结构.链表的每个结点中都至少包含一个指针。原题中,“恰好”改为了”至少”。
（11）单链表中，增加头结点的目的是为了 ( )
A. 使单链表至少有一个结点 B. 标示表结点中首结点的位置
C. 方便运算的实现 D. 说明单链表是线性表的链式存储实现
3. 程序选择题
（1）已知L指向带表头结点的非空单链表的头结点，且P结点既不是首结点，也不是尾结点，试从下列提供的答案中选择合适的语句序列：
a.删除P结点的直接后继结点的语句序列是（___________） b.删除P结点的直接前驱结点的语句序列是（___________） c.删除P结点的语句序列是（___________） d.删除首结点的语句序列是（___________） e.删除尾结点的语句序列是（___________） (1) delete Q; (2) Q = P (3) L = L->next (4) P = L (5) Q = P->next (6) P->next = P 答案: a. 5 8 1
b. 2 4 14 5 8 1 c. 2 4 10 8 1 d. 4 5 8 1 e. 4 13 5 8 1
（2）已知p结点是某双向链表的中间结点，试从下面语句((1)～(18))中选择合适的语句序列，完成a～e要求的操作。
a. 在p结点后插入s结点的语句序列是________________________________。 b. 在p结点前插入s结点的语句序列是________________________________。 c. 删除p结点的直接后继结点的语句序列是_____________________________。
d. 删除p结点的直接前驱结点的语句序列是_____________________________。 e. 删除p结点的语句序列是____________________________。
(8) P->next = P->next->next (9) P = P->next (10) while(P->next != Q) P = P->next; (11) while(P != NULL) P = P->next; (12) while(Q->next != NULL) { P = Q ; Q = Q->next;} (13) while(P->next->next != NULL) P = P->next; (7) P = P->next->next (14) while(P->next->next != Q) P = P->next; 3
北邮C++数据结构课后习题 习题2参考答案
