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

数据结构第二章参考答案
习题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
(1) p->next = p->next->next; (2) p->prior = p->prior->prior; (3) p->next = s; (4) p->prior = s; (5) s->next = p; (6) s->prior = p; (7) s->next = p->next; (8) s->prior = p->prior; (9) p->prior->next = p->next; 答案:
a. 7 6 12 3 b. 5 8 13 4 c. 15 1 11 18 d. 16 2 10 18 e. 14 9 17
4．分析以下各程序段的执行结果。 （1）程序段一

vector ivec(2,100); ivec.push_back (3);
ivec.insert (ivec.begin (),10);
vector ::iterator it = ivec.begin(); ivec.erase (++it); ivec.pop_back();
ivec.insert(ivec.end(),20);
(10) p->prior->next = p; (11) p->next->prior = p; (12) p->next->prior = s; (13) p->prior->next = s; (14)p->next->prior = p->prior; (15) q=p->next; (16) q=p->prior; (17) delete p; (18) delete q; for ( it = ivec.begin (); it != ivec.end(); it++ ) cout ivec(a, a+5);
cout ilist(3,2); ilist.assign(a,a+5);

//1 2 3 4 7
ilist.pop_back (); //1 2 3 4 ilist.insert (ilist.end(),7); ilist.pop_front (); //2 3 4 7 ilist.front ()=20; //20 3 4 7 ilist.sort(); //3 4 7 20
for ( list::iterator it = ilist.begin (); it != ilist.end(); it++ )
cout B。试编写一个比较A和B的算法，当AB是分别输出-1，0或者1。
（3）假设有两个按数据元素值递增有序排列的线性表A和B，均以单链表作存储结构。编写算法将A表和B表归并成一个按元素值递减有序（即非递增有序，允许值相同）排列的线性表C，并要求利用原表(即A表和B表的)结点空间存放表C。
（4）试分别以顺序表和单链表作为存储结构，各写一个实现线性表的就地（即使用尽可能少的附加空间）逆置的算法，在原表的存储空间内将线性表（a1，a2,，??，an-1，an)逆置为（an，an-1，??，a2，a1)。
（5）假设在长度大于1的循环链表中，既无头结点也无头指针。s为指向链表中某个结点的指针，试编写算法删除结点*s的直接前趋结点。 答案：
template
void DeletePreNode (Node * s) {
Node * p = s;
//得到s的结点的前一个结点的前一个结点 while (p->next->next != s) p=p->next; //删除p->next指向的结点 Node * q = p->next; p->next = s; delete q; }
（6）已知一单链表中的数据元素含有三类字符(即:字
5
5 / 5