数据结构第二章参考答案

1习题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.选择题2（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+kiB.b+k(i-1)C.b+k(i+1)D.b-1+ki（7）在循环链表中，若不使用头指针而改设为尾指针（rear），则头结点和尾结点的存储位置分别是（）。A.real和rear-next-nextB.rear-next和rearC.rear-next-next和rearD.rear和rear-next（8）有时为了叙述方便，可以对一些概念进行简称，以下说法错误的是（）。A.将“指针型变量”简称为“指针”B.将“头指针变量”简称为“头指针”C.将“修改某指针型变量的值”简称为“修改某指针”D.将“p中指针所指结点”简称为“P值”（9）以下说法错误的是（）。A.对循环链表来说，从表中任一结点出发都能通过向前或向后操作而扫描整个循环链表。B.对单链表来说，只有从头结点开始才能扫描表中全部结点。C.双链表的特点是找结点的前趋和后继都很容易。D.对双链表来说，结点*P的存储位置既存放在其前趋结点的后继指针域中，也存放在它的后继结点的前趋指针域中。（10）以下说法正确的是（）。A.顺序存储方式的优点是存储密度大、且插入、删除运算效率高。B.链表的每个结点中都至少包含一个指针。C.线性表的顺序存储结构优于链式存储结构。D.顺序存储结构属于静态结构，链式结构属于动态结构。3说明:静态链表是链式结构,但属于静态存储结构.链表的每个结点中都至少包含一个指针。原题中,“恰好”改为了”至少”。（11）单链表中，增加头结点的目的是为了()A.使单链表至少有一个结点B.标示表结点中首结点的位置C.方便运算的实现D.说明单链表是线性表的链式存储实现3.程序选择题（1）已知L指向带表头结点的非空单链表的头结点，且P结点既不是首结点，也不是尾结点，试从下列提供的答案中选择合适的语句序列：a.删除P结点的直接后继结点的语句序列是（___________）b.删除P结点的直接前驱结点的语句序列是（___________）c.删除P结点的语句序列是（___________）d.删除首结点的语句序列是（___________）e.删除尾结点的语句序列是（___________）(1)deleteQ;(8)P-next=P-next-next(2)Q=P(9)P=P-next(3)L=L-next(10)while(P-next!=Q)P=P-next;(4)P=L(11)while(P!=NULL)P=P-next;(5)Q=P-next(12)while(Q-next!=NULL){P=Q;Q=Q-next;}(6)P-next=P(13)while(P-next-next!=NULL)P=P-next;(7)P=P-next-next(14)while(P-next-next!=Q)P=P-next;答案:a.581b.2414581c.241081d.4581e.413581（2）已知p结点是某双向链表的中间结点，试从下面语句((1)～(18))中选择合适的语句序列，完成a～e要求的操作。a.在p结点后插入s结点的语句序列是________________________________。b.在p结点前插入s结点的语句序列是________________________________。c.删除p结点的直接后继结点的语句序列是_____________________________。d.删除p结点的直接前驱结点的语句序列是_____________________________。e.删除p结点的语句序列是____________________________。4(1)p-next=p-next-next;(10)p-prior-next=p;(2)p-prior=p-prior-prior;(11)p-next-prior=p;(3)p-next=s;(12)p-next-prior=s;(4)p-prior=s;(13)p-prior-next=s;(5)s-next=p;(14)p-next-prior=p-prior;(6)s-prior=p;(15)q=p-next;(7)s-next=p-next;(16)q=p-prior;(8)s-prior=p-prior;(17)deletep;(9)p-prior-next=p-next;(18)deleteq;答案:a.76123b.58134c.1511118d.1621018e.149174．分析以下各程序段的执行结果。（1）程序段一vectorintivec(2,100);ivec.push_back(3);ivec.insert(ivec.begin(),10);vectorint::iteratorit=ivec.begin();ivec.erase(++it);ivec.pop_back();ivec.insert(ivec.end(),20);for(it=ivec.begin();it!=ivec.end();it++)cout*it;coutendl;答案:1010020分析:开始时容器中有100100，然后为1001003，101001003，101003，10100，1010020（2）程序段二inta[]={1,2,3,4,5};vectorintivec(a,a+5);cout1.size:ivec.size()endl;ivec.resize(100);cout2.size:ivec.size()endl;for(intj=0;j95;j++)ivec.insert(ivec.end(),j);cout3.size:ivec.size()endl;ivec.resize(100);ivec.reserve(20);cout4.size:ivec.size()endl;答案：1.size:52.size:10053.size:1954.size:100（3）程序段三inta[]={1,2,3,4,5};listintilist(3,2);ilist.assign(a,a+5);ilist.pop_back();//1234ilist.insert(ilist.end(),7);//12347ilist.pop_front();//2347ilist.front()=20;//20347ilist.sort();//34720for(listint::iteratorit=ilist.begin();it!=ilist.end();it++)cout*it;coutendl;答案：347205．算法设计（1）分别编程实现顺序表类和链表类，并设计完整的测试程序对每个接口进行测试。（2）设A=（a1,a2,a3,......an）和B=(b1,b2,...,bm)是两个线性表（假定所含数据元素均为整数）。若n=m且ai=bi(i=1,...,n),则称A=B;若ai=bi(i=1,...,j)且aj+1bj+1（jn=m）,则称AB;在其他情况下均称AB。试编写一个比较A和B的算法，当AB,A=B或AB是分别输出-1，0或者1。（3）假设有两个按数据元素值递增有序排列的线性表A和B，均以单链表作存储结构。编写算法将A表和B表归并成一个按元素值递减有序（即非