数据结构与stl课后答案.pdf

数据结构与st I 课后答案习题11 .填空题（1）（）是指数据之间的相互关系，即数据的组织形式。通常人们认为它包含三个方面的内容，分别为数据的（）、（）及其运算。答案：数据结构 逻辑结构 存储结构（2）（）是数据的基本单位，在计算机程序中通常作为一个整体进行处理。答案：数据元素（3）数据元素之间的不同逻辑关系代表不同的逻辑结构，常见的逻辑结构有（）、（）、（）和（）。答案：集合线形结构树结构图结构（4）数据的存储结构考虑的是如何在计算机中存储各个数据元素，并且同时兼顾数据元素间的逻辑关系。基本的存储结构通常有两大类：（）和（）。答案：顺序存储结构链式存储结构（5）通常个问题可以有多种不同的算法，但每个算法必须满足5个准则：输入、输出、（）、（）和（）。答案：有穷性确定性可行性（6）通常通过衡量算法的（）复杂度和（）复杂度来判定一个算法的好坏。答案：时间空间(7)常见时间复杂性的量级有：常数阶0()、对数阶0()、线性阶0()、线性对数阶0()、平方阶0()、和指数阶 0()。通常认为，当问题规模较大时，具 有()量级的算法是不可计算的。答案：1 logn n nlogn n2 2n 指数(8)STL提供的标准容器有顺序容器、()和()o答案：排序容器哈希容器(9)算法可认为是STL的精髓，所有算法都是采用()的形式提供的。答案：函数模版(10)通常认为STL由空间管理器、迭代器、泛函、适配器、()和()等六部分构成，其中前面四部分服务于后面两部分。答案：容器算法2.选择题(1)以下结构中，()属于线性结构。A.树 B.图 C.串 D.集合(2)算法描述的方法有很多种，常 常 将()称为算法语言。A.自然语言B.流 程 图 C.伪 代 码 D.程序设计语言(3)现实生活中的家族谱，可认为是一种()结构。A.树 B.图 C.集 合 D.线性表(4)手机中存储的电话号码簿，可认为是 种()结构。A.树 B.图 C.集 合 D.线性表(5)N P 问 题 是()。A.非多项式时间问题，即非P 问 题 B.非确定性多项式时间问题C.P 问题的子集D.与 P 问题不相交的(6)以 下()不属于STL的顺序容器。A.向 量(vector)B.列 表(list)C.队 列(queue)D.双端队列(deque)(7)下面带有 标记的语句的频度(n10)是(for(int i=0;in-1;i+)for(int j=i+1 ;jn;j+)cout ij endl;A.n*(n-1)/2 B.n*n/2 C.n*(n+1)/2 D.不确定CCADBCA分析：3.分析以下程序段的时间复杂度。(1)for(i=l;i=n;i+)k+;for(j=1;j=n;j+)m+=k;)(2)for(i=l;i=n;i+)k+;for(j=1;j=n;j+)m+=k;(3)i=l;while(i=n)i*=2;(4)i=l;while(i=n)i+=2;(5)k=100,i=10;do if(in)break;i+；while(i k);(6)for(i=0;i100;i+)for(j=0;ji;j+)sum+=j;(7)y=0;while(y*y*y=n)y+;(8)ini i=0;while(in&ai!=k)i+;return i=n?-1:i;答案:(1)0(n2)(2)0(n)(3)O(logn)(4)O(n)(5)0(1)(6)0(1)(7)0(n 1/3)(8)0(n)4.将整数设计为一个类，将整数相关的常见数学运算设计为类的接口并进行实现，如求与给定值的最大公约数、最小公倍数、枚举所有因子等。解：#include math.h#include vectorusing std:vector;定义自然数类class NaturalNumberpublic:NaturalNumber(unsigned long int n=0):num(n)unsigned long int GreatestCommonDivisor(NaturalNumber&nn);求解最大公约数unsigned long int LeaseCommonMultiple(NaturalNumber&nn);求解最小公约数int Getfectors(vector&factors);求所有因子，存储在 factors 中,函数返回因子个数unsigned long int GetNumber()return num;/其它外部接口private:unsigned long int EUCLI D(NaturalNumber&n);欧几里德算法求解最大公约数unsigned long int num;存储真正的自然数；返回欧几里德算法求解最大公约数unsigned long int NaturalNumber:EUCLI D(Natural Number&nn)(unsigned long int m=(num nn.num)?num:nn.num;较大的自然数赋值给 munsigned long int n=(num nn.num)?num:nn.num;较小的自然数赋值给 nunsigned long int r=m%n;while(r!=0)m=n;n=r;r=m%n;)return n;)返回最大公约数unsigned long int NaturalNumber:GreatestCommonDivisor(NaturalNumber&nn)(return EUCLID(nn);)返回最小公倍数unsigned long int NaturalNumber:LeaseCommonMultiple(NaturalNumber&nn)(unsigned long int temp=EUCLI D(nn);return num*nn.GetNumber()/temp;)int NaturalNumber:GetFactors(vector&factors)int t=0;int m=sqrt(double)num);vector bigfactors;for(unsigned long int i=1;im;i+)(if(0=num%i)t+=2;factors.push_back(i);bigfactors.push_back(num/i);)if(m*m=num)t+;factors.push_back(m);vector :iterator it=bigfactors.end();if(bigfactors.size()do(it-；factors.push_back(*it);while(it!=bigfactors.begin();return t;)void main()NaturalNumber p(1);int xx=p.GreatestCommonDivisor(NaturalNumber(120);int yy=p.LeaseCommonMultiple(NaturalNumber(120);vector f;int t=p.GetEactors(f);)习题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）顺序表多采用（）实现的，是一种随机存取结构，对表中任意结点存取操作的时间复杂度为（）。而查找链表中的结节，需要从头指针起顺着链扫描才能得到，平均时间复杂度为（）。因此，若线性表的操作主要是进行查找，很少进行插入或删除操作时，采 用（）表比较合适。答案：数 组。0（n）顺序（6）在链表某个位置上进行插入和删除操作，只需要修改（）即可，而无须移动大量元素，操作的时间复杂度为（）。而在顺序表中进行插入和删除操作,往往要移动大量元素，平 均 移 动 元 素 的 数 目 为（）,平均时间复杂度为（）。因此，若对线性表进行频繁的插入和删除操作时，采 用（）表相对合适。若插入和删除主要发生在表头和表尾，则 采 用（）表更为合适。答案：指 针 0（1）表长的一半0（n）链循环链（7）静态链表一般采用（）存储的链表结构。答案：数组（8）对 于 32位 计 算 机 环 境，若 单 链 表 中 的 数 据 类 型 为 整 性，则其存储密度为（）,而若为双链表，则存储密度为（）。若采用顺序表存储数据,则其存储密度为（）。答案：50%33%1（9）向量是最常用的容器，S T L中 向 量 使 用（）实现，因此向量具有（）表的所有特点，可以快速随机存取任意元素。答案：数组顺序（10）操作系统在运行之初，有一块很大的连续内存块供用户程序申请，通常称之为内存池 或（）o答案：堆（11）循环链表与单链表的区别仅仅在于其尾结点的链域值不是（）,而是一个 指 向（）的指针。答案：NULL（或空指针）头结点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）若链表是利用6+指针来存储结点的地址，结点空间的分配和收回都是由操作符new和 delete动态执行的，则称该链表为（）链表A.单 向 B.双向 C.静 态 D.动态（4）将线性表存储到计算机中可以采用多种不同的方法，按顺序存储方法存储的线性表称为（），按链式存储方法存储的线性表称为（）。A.数 组 单 链 表 B.顺序表链表C.向 量 静 态 链 表 D.静态链表动态链表（5）（）是 STL中线性表的链式存储形式，STL标准库中一般采用（）实现。A.vector数 组 B.lis t单链表C.lis t双向循环链表D.vector单链表（6）顺序表的类型定义可经编译转换为机器级。假定每个结点变量占用k（k=1 个字节，b 是顺序表的第一个存储结点的第一个单元的内存地址，那么，第 i 个结点a i的存储地址为（）。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 和 rearC.rear-next-next 和 rear D.rear 和 rear-next（8）有时为了叙述方便，可以对一些概念进行简称，以下说法错误的是（）。A.将“指针型变量”简称为“指针”B.将“头指针变量”简称为“头指针”C.将“修改某指针型变量的值”简称为“修改某指针”D.将“p 中指针所指结点”简称为“P值”（9）以下说法错误的是（A.对循环链表来说，从表中任一结点HI发都能通过向前或向后操作而扫描整个循环链表。B.对单链表来说，只有从头结点开始才能扫描表中全部结点。C.双链表的特点是找结点的前趋和后继都很容易。D.对双链表来说，结点*P的存储位置既存放在其前趋结点的后继指针域中，也存放在它的后继结点的前趋指针域中。（10）以下说法正确的是（）。A.顺序存储方式的优点是存储密度大、且插入、删除运算效率高。B.链表的每个结点中都至少包含一个指针。C.线性表的顺序存储结构优于链式存储结构。D.顺序存储结构属于静态结构，链式结构属于动态结构。说明:静态链表是链式结构，但属于静态存储结构.链友的每个结点中都至少包含个指针。原题中，“恰好”改为了“至少”。（11）单链表中，增加头结点的目的是为了（）A.使单链表至少有一个结点 B.标示表结点中首结点的位置C.方便运算的实现 D.说明单链表是线性表的链式存储实现CDDBC BBDABC3.程序选择题（1）已知L指向带表头结点的非空单链表的头结点，目.P结点既不是首结点，也不是尾结点，试从下列提供的答案中选择合适的语句序列:a.删除P结点的直接后继结点的语句序列是（）b.删除P结点的直接前驱结点的语句序列是（）c.删除P结点的语句序列是（）d.删除首结点的语句序列是（）e.删除尾结点的语句序列是（）(1)delete Q;(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=(14)while(P-next-next!=Q)P=P-next;P-next-next答案：a.5 8 1b.2 4 1458 1c.2 4 10 8 1d.4 5 8 1e.4 13 58 1(2)已知p 结点是某双向链表的中间结点，试从下面语句(1)(18)中选择合适的语句序列，完成ae 要求的操作。a.在 p 结点后插入s 结点的语句序列是 ob.在 p 结点前插入s 结点的语句序列是 oc.删除p 结点的直接后继结点的语句序列是 od.删除p 结点的直接前驱结点的语句序列是 oe.删除p 结点的语句序列是 o(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-priorp-prior;(6)s-prior=p;(15)q=p-next;(7)s-next=p-next;(16)q=p-prior;(8)s-prior=p-prior;(17)delete p;(9)p-prior-next=p-next;(18)delete q;答案:a.7 6 12 3b.5 8 13 4c.15 1 11 18d.162 10 18e.149 174.分析以下各程序段的执行结果。(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);for(it=ivec.begin();it!=ivec.end();it+)cout *it cout endl;答案:10 100 20分析:开始时容器中有 100 1 0 0,然后为 100 100 3,10 100 100 3,10 100 3,10 100,10100 20(2)程序段二int 却=123,4,5;vector ivec(a,a+5);cout l.size:*ivec.size()endl;ivec.resize(WO);cout H2.size:*ivec.size()endl;for(int j=0;j95;j+)ivec.insert(ivec.end()J);cout n3.size:*ivec.size()endl;ivec.resize(WO);ivec.reserve(20);cout H4.size:H ivec.size()endl;答案：1.size:52.size:1003.size:1954.size:100(3)程序段三int a=1,2,3,4,5);list ilist(3,2);ilist.assign(a,a+5);ilist.pop_back();/1 2 3 4ilist.insert(ilist.end(),7);/1 2 3 4 7ilist.popjront();/2 3 4 7ilist.front()=20;/20 3 4 7ilist.sort();/3 4 7 20for(list:iterator it=ilist.begin();it!=ilist.end();it+)cout *it*M;cout endl;答案：3 4 7205.算法设计（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）,则称A Bo试编写一个比较A 和 B 的算法，当 A B 是分别输出-1,。或者1。（3）假设有两个按数据元素值递增有序排列的线性表A 和 B,均以单链表作存储结构。编写算法将A 表 和 B 表归并成一个按元素值递减有序（即非递增有序，允许值相同）排列的线性表C,并要求利用原表（即 A 表和B 表的）结点空间存放表Co（4）试分别以顺序表和单链表作为存储结构，各写一个实现线性表的就地（即使用尽可能少的附加空间）逆置的算法，在原表的存储空间内将线性表（a1,a 2,，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;删J除 p-next指向的结点Node *q=p-next;p-next=s;delete q;)（6）已知一单链表中的数据元素含有三类字符（即:字母字符、数字字符和其它字符）。试编写算法，构造三个循环链表，使每个循环链表中只含同一类的字符，且利用原表中的结点空间作为这三个表的结点空间（头结点可另辟空间）。（7）Josephus环问题：任给正整数n、k,按下述方法可得排列1,2,，n 的一个置换:将数字1,2,，门环形排列（如图2-36所示），按顺时针方向从1开始计数，计满k 时输出该位置上的数字（并从环中删去该数字），然后从下一个数字开始继续计数，直到环中所有数字均被输出为止。例如，n=10,k=3时，输出的置换是3,6,9,2,7,1,8,5,10,4 o 试编写一算法，对输入的任意正整数n、k,输出相应的置换数字序列。习题31.填空题（1）栈的进出原则是（）,队列的进出原则是（）。答案：后进先出（LIFO）先进先出（FIFO）（2）设32位计算机系统中，空 栈 S 存 储 in t型数据，栈顶指针为1024H。经过操作序列push（1）,push（2）,pop,push（5）,push（7）,pop,push（6）之后，栈顶元素为（）,栈底元素为（）,栈的高度为（）,输出序列是（）,栈顶指针为（）H。答案：6 1 3 2,7 1030（3）两栈共享存储空间,其数组大小为1 0 0,数组下标从0开始。topi和 top2分别为栈1和栈 2 的 栈 顶 元 素 下 标，则 栈 1为 空 的 条 件 为（）,栈 2 为空的条件为（）,栈1或栈2满的条件为（）。空栈的条件答案：topi=-1 top2=100 topi+1 =top2（4）一个队列的入队顺序是1234,则队列的输出顺序是（）。答案：1234（5）设循环队列数组大小为1 0 0,队头指针为fro n t,队尾指针为rear；约 定 front指向队头元素的前一个位置，该位置永远不存放数据。则入队操作时，修 改 rear=（）,出队操作修改front=（）,队空的判别条件为（）,队满的判别条 件 为（）o 若 front=20,rear=60,则 队 列 长 度 为（）,若front=60,rear=20,则队列长度为（循环队列答案：（rear+1）%100（front+1）%100 rear=front（rear+1）%100=front 40 60（6）朴素模式匹配算法中，每个串的起始下标均为1,变量i=100,j=1 0,分别表示主串和模式串当前比较的字符元素下标，若本次比较两字符不同，贝 W 回 溯 为（）,j回 溯 为（）。答案：92 1（7）用循环链表表示的队列长度为n,若只设头指针，则出队和入队的时间复杂度分别为（）和（）。答案：0（1）0（n）2.选择题（1）将一个递归算法改为对应的非递归算法时，通常需要使用（A.数 组 B.栈 C.队 列 D.二叉树（2）四个元素1、2、3、4依次进栈，出栈次序不可能出现（）情况。A.1 2 3 4 B.4 1 3 2 C.1 4 3 2 D.4 3 2 1（3）设循环队列中数组的下标范围是1n,其头尾指针分别为f 和 r,则其元素个数为（）oA.r-f B.r-f+1 C.（r-f）mod n+1 D.（r-f+n）mod n说明：这里的数组不是指C+数组，也就说假定数组长度依然为n,而不是n+1。（4）10行100列的二维数组A 按 行 优 先 存 储,其 元 素 分 别 为 A10100,每个元素占4字节，已知 Loc（A67）=10000H,贝 ij Loc（A419）=（）。A.FC11H B.9248H C.2F00H D.FD10H（5）设有两个串S1和 s 2,求 s2在 s1中首次出现的位置的运算称为（）。A.连接 B.模式匹配 C.求子串 D.求串长（6）为了解决计算机主机和键盘输入之间速度不匹配问题，通常设置一个键盘缓冲区，该缓冲区应该是一个（）结构。A.栈 B.队列 C.数组 D.线性表（7）STL中的双端队列为（）。A.顺序容器B.容器适配器C.迭代器适配器D.泛函适配器（8）STL中 的（）允许用户为队列中的元素设置优先级。A.队列适配器B.双端队列C.优先级队列适配器D.栈适配器（9）string类型不支持以（）的方式操作容器,因此不能使用front、back和 pop_back操作。A.线 性 表 B.队 列 C.栈 D.串BBDDB BACC3.算法设计（1）设计一个算法判断算数表达式的圆括号是否正确配对。（2）假定用带头结点的循环链表表示队列，并且只设置一个指针指向队尾元素，试设计该队列类，完成相应的入队、出队、置空队、求队长等操作接口。（3）设计算法把个十进制数转换为任意指定进制数。（4）设有一个背包可以放入的物品重量为S,现 有 n 件物品，重量分别为w1,w 2,w n 问能否从这n 件物品中选择若干件放入此背包，使得放入的重量之和正好为S。如果存在一种符合上述要求的选择，则称此背包问题有解，否则此问题无解，试用递归和非递归两种方法设计解决此背包问题的算法。背包问题分析：背包问题是一个经典的NP问题，它既简单形象容易理解，又在某种程度上能够揭示动态规划的本质，故不少教材都把它作为动态规划部分的第一道例题。本题目是最简单的01背包问题，除此之外，还有许多由此衍生出来的很多复杂的背包问题。本题中，最容易想到的就是假定背包中已放入了部分物品，现将第i 件物品试着放入背包中，如果可以放进去，背包的重量在原来的基础上增加了 wi；如果不可以放进去，说明加入后太重了，换下一件物品。如果所有的剩余物品都不能放入，说明以前放入的物品不合适，拿出上一次放入的物品，继续试剩余的物品。递归解法：设背包函数为knapsack（int s,int n）,参 数 int s 为剩余重量，int n 为剩余物品数，返回值表示背包分配是否成功。（1）如果s=0,表示分配成功，返回1；（2）如果s 0 或 者 n 0,表示太重，或者物品分配完毕，返回0；(3)执行knapsack(s-wi,n-1),测试当前这件物品放入是否成功。(3.1)如果 成功，说明当前这件物品放入刚好最终分配成功。(4)返回knapsack(s,n-1),说明当前物品不合适，减小剩余物品数，继续测试。测试代码：/*简单的背包问题递归解*/#includestdio.h#define N 6/*物品数量*/#defines 8/*背包大小*/in t川泗+1=0,1,2,3,4,5,6;/*数据,各物品重量，W0不使用*/*背包函数knapsack()参数int s 剩余重量int n 剩余物品数返回in t背包分配是否成功int knapsack(int s,int n)(if(s=0)/*分配结束，成功3return 1;if(s 0&n 1)/*没有可用空间，或者物品分配完毕*/return 0;if(knapsack(s-Wn,n 1)/*递归*/printf(“-4d”,Wn);/*输出*/return 1;)return knapsack(s,n-1);)int main()if(knapsack(S,N)/*递归调用*/printf(nOK!n);elseprintf(Failed!);return 1;/*main*/非递归解法：一件一件的物品往包(即栈)里放，发现有问题，拿出来，放其他的物品。(1)i=1(2)从第i 件到第n 件测试每件物品，对于第j 次循环，测试第j 件物品(2.1)如果 该物品可以放，入栈(2.2)若栈 的容量刚好达到要求，成功，打印栈元素。(2.3)继续 测试j+1件物品(3)若没有成功(3.1)若栈 空，返回失败(3.2)将栈 顶物品(设第k 个)出栈(3.3)i=k+1,返 回(2)代码:#includestdio.h#define N 6/*物品数量*/#defines 8/*背包大小*/intWN+1=0,1,2,345,6;/*数据，各物品重量，W0不使用*/int stack1000=0;int value=O;int size=O;knapsackstack()(int i=1;while(1)(for(int j=i;j=N;j+)if(value+Wj=S)stacksize+=j;value+=Wj;if(value=S)printf(得到一组解：”)；for(int p=0;pS)break;)if(size=0)printf(Fnished!n);exit(O);stack-size+1;value-=Wi-1;)void main()(knapsackstack();)习题41.填空题（1）一般来说，数 组 不 执 行（）和（）操作，所以通常采用（）方法来存储数组。通常有两种存储方式：（）和（）。答案：删除插入顺序存储行优先存储列优先存储（2）设8行8列的二维数组起始元素为A 00,按行优先存储到起始元素下标为。的维数组 B 中，则元素B23在原二维数组中为（）。若该二维数组为上三角矩阵，按行优先压缩存储上三角元素到起始元素下标为。的 维 数 组 C 中，则元素C23即为原矩阵中 的（）元素。答案：A27 A35（3）设二维数组A 为6行8列，按行优先存储，每个元素占6字节，存储器按字节编址。已知 A 的起始存储地址为1000H,数组A 占用的存储空间大小为（）字节，数组A 的最后一个元素的下标为（）,该元素的第一个字节地址为（）H,元 素 的 第 一 个 字 节 的 地 址 为（）H。（提示：下标从0开始计）答案：288 A571 111AH 1048H（4）设 C+中存储三维数组A m np,则第一个元素为aOOO,若按行优先存储yehanglie,则 a ijk前面共有（）个元素；若按列优先存储，liehangye则 a ijk前面共有（）个元素。答案：inp+jp+k i+mj+mnk（5）常见的稀疏矩阵压缩方法有：（）和（）。答案：三元组表十字链表（6）广 义 表（a）,（b,c）,d）,（e）的长度为（）,表 头 为（）,表 尾 为（）。答案：3(a)(b,c),d),(e)(7)设广义表LS=(a),(b,c),d),(e),若用取表头操作GetHead()和取表尾操作 GetTail()进行组合操作，则取出元素b 的运算为()。答案：GetHead(GetHead(GetHead(GetTail(LS)(8)若广义表 A 满足 GetHead(A)=GetTail(A),则 人=()。答案：()2.问答题(1)根据下面的矩阵，写出矩阵转置后的三元组表，起始行列值为1。Row Col1 31 62 12 53 13 45 26 3矩阵行数：7矩阵列数：6非零元素个数：8Item151218913514(2)对于如下稀疏矩阵，请写出对应的三元组顺序表，若采用顺序取，直接存的算法进行转置运算，引入辅助数组numberU和 position，分别表示矩阵各列的非零元素个数和矩阵中各列第一个非零元素在转置矩阵中的位置，请写出数组中的各元素(所有数组起始元素下标为0)。原矩阵Col 0 12 3Numbercol 10 2 1Positioncol 0113RowColItem0 2 21 0 32 2-12 3 5行数：4列数：4非零元素个数：4(3)对于上题中的稀疏矩阵，写出对应的三元组表和十字链表。三元组表:Row Col Item0221032 2-12 3 5行数：4列数：4非零元素个数：4十字链表：3.算法设计（1）设计上三角矩阵存储类，实现如下接口:对于上三角矩阵A N N,可按行优先压缩存储和按列优先压缩存储。对于给定的一维数组BM,可根据行优先压缩存储或列优先压缩存储还原原始的上三角矩阵。（2）针对24位真彩色BMP图像文件，编写程序实现如卜功能:读 取 24位真彩色BMP图像文件。将原图像转换为24位灰度图像，并进行保存。转按公式如下：Grey=0.3*Fted+0.59*Blue+0.11*Green 将 24位灰度图像转换为8位灰度图像，并进行保存。将 8位灰度图像分别进行4邻域和8邻域平滑，并分别进行保存。习题51.填空题（1）已知二叉树中叶子数为50,仅有一个孩子的结点数为30,则总结点数为（）。答案：129（2）3个结点可构成（）棵不同形态的二叉树。答案：5（3）设树的度为5,其中度为15的结点数分别为6、5、4、3、2个，则该树共有（）个叶子。答案：31（4）在结点个数为n（nl）的各棵普通树中，高度最小的树的高度是（）,它有（）个叶子结点，（）个分支结点。高度最大的树的高度是（）,它 有（）个叶子结点，（）个分支结点。答案：2 n-1 1 n 1 n-1（5）深度为k 的二叉树，至 多 有（）个结点。答 案:2k-1（6）（7）有 n 个结点并且其高度为n 的二叉树的数目是（）答案：2n-1（8）设只包含根结点的二叉树的高度为0,则 高 度 为 k 的二叉树的最大结点数为（）,最小结点数为（）。答案：2k+1-1 k+1（9）将一棵有100个结点的完全二叉树按层编号，则编号为49的结点为X,其双亲PARENT（X）的编号为（）。答案：24（10）已知 棵完全二叉树中共有768个结点，则该树中共有（）个叶子结点。答 案:384（11）（12）已知一棵完全二叉树的第8层有8个结点，则其叶子结点数是（）。答案：68（13）深度为8（根的层次号为1）的满二叉树有（）个叶子结点。答案：128（14）棵 二 叉 树 的 前 序 遍 历 是 FC ABED,中 序 遍 历 是 AC BFED,则后序遍历是（）。答案：ABCDEF（15）某二叉树结点的中序遍历序列为ABCDEFG,后序遍历序列为BDCAFGE,则该二叉树结点的前序遍历序列为（）,该二叉树对应的树林包括（）棵树。答案：EACBDGF 22.选择题（1）在一棵度为3的树中，度为3的结点的个数为2,度为2的结点个数为1,则度为0的结点个 数 为（A.4 B.5 C.6 D.7（2）下列陈述中正确的是（）。A.二叉树是度为2的有序数B.二叉树中结点只有一个孩子时无左右之分C.二叉树中必有度为2的结点D.二叉树中最多只有两棵子树，并且有左右之分（3）在K叉树中，如果结点M有3个兄弟，而且N是M的双亲，则N的度是（）A.3 B.4 C.5 D.1（4）设高度为h的二叉树上只有度为0和度为2的结点，则此类二叉树中所包含的结点数至少 为（）。A.2h B.2 h-l C.2h+1 D.h+1（5）高度为5的完全二叉树至少有（）个结点。A.16 B.32 C.31 D.5（6）具有65个结点的完全二叉树的高度为（）。（根的层次号为0）A.8 B.7 C.6 D.5（7）对一个满二叉树，m 个树叶，n 个结点，深度为h,则（无）。A.n=h+m B.h+m=2nC.m=h-1 D.n=2h-1（8）任一棵二叉树，其叶子结点数为n 0,度为2的结点数为n 2,则存在关系（）。A.n2+1=n0 B.n0+1=n2C.2n2+1=n0 D.n2=2n0+1（9）某二叉树的前序遍历结点访问顺序是abdgcefh,中序遍历的结点访问顺序是dgbaechf,则其后序遍历的结点访问顺序是（）。A.bdgcefha B.gdbecfha C.bdgaechf D.gdbehfca（10）设 m、n 为一棵二叉树上的两个结点，在中序遍历时，n 在 m 前的条件是（）。A.n 在 m 右方 B.n 是 m 祖先C.n 在 m 左方 D.n是 m 子孙（11）一棵二叉树的广义表表示为a（b（c,d）,e（f（g）,则得到的层序遍历序列为（）。A.abcdefg B.cbdaegf C.cdbgfea D.abecdfg（12）若二叉树采用二叉链表作为存储结构，要交换其所有分支结点左右子树的位置，利用（）遍历方法最合适。A.前序 B.中序 C.后 序D.层序说明：显然，如果按前序或后序遍历，当访问某结点时，交换其左右孩子，则可完成要求。进行层序遍历时，当结点出队时，交换左右孩子，也可以完成题目要求。因此该题有3个答案，谈不上哪个最合适。建议该题目将“最合适”改 为“不合适”，这样答案应该是唯 的。（13）对二叉树进行（）遍历，可以得到该二叉树所有结点构成的排序序列。A.前序 B.中序 C.后 序D.层序（14）设F是一个森林，B是由F转换得到的二叉树，F中有n个非叶结点，则B中右指针域为空的结点有（）个。A.n-1 B.n C.n+1 D.n+2（15）利用3,6,8,12,5,7这6个值作为叶子结点的权，生成一棵哈夫曼树，该树的深度为（）。A.3 B.4 C.5 D.6（16）若度为m的哈夫曼树中，其叶结点个数为n,则非叶结点的个数为（A.n-1 B.n/m-1C.（n-1）/（m-1）D.n/（m-1）-1说明：在这里度为m的哈夫曼树是指仅含有度为0和m的结点的m叉树。因此有：（1）N=n+nm（2）N=1 +mnmCDBBA CDADC D(ACD)BCBC3.试分别画出具有3个结点的树和二叉树的所有不同形态。答案：树：二叉树：4 .试找出分别