数据结构第二章参考答案.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)中选择合适的语句序列，完成ae要求的操作。 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