数据构造课后习题答案_2.docx

数据构造课后习题答案第1章绪论1简述下列概念：数据、数据元素、数据项、数据对象、数据构造、逻辑构造、存储构造、抽象数据类型。答案：数据：是客观事物的符号表示，指所有能输入到计算机中并被计算机程序处理的符号的总称。如数学计算中用到的整数和实数，文本编辑所用到的字符串，多媒体程序处理的图形、图像、声音、动画等通过特殊编码定义后的数据。数据元素：是数据的基本单位，在计算机中通常作为一个整体进行考虑和处理。在有些情况下，数据元素也称为元素、结点、记录等。数据元素用于完好地描绘一个对象，如一个学生记录，树中棋盘的一个格局状态、图中的一个顶点等。数据项：是组成数据元素的、有独立含义的、不可分割的最小单位。例如，学生基本信息表中的学号、姓名、性别等都是数据项。数据对象：是性质一样的数据元素的集合，是数据的一个子集。例如：整数数据对象是集合N=0，±1，±2，字母字符数据对象是集合C=A，B，Z，a，b，z，学生基本信息表可以是一个数据对象。数据构造：是互相之间存在一种或多种特定关系的数据元素的集合。换句话讲，数据结构是带“构造的数据元素的集合，“构造就是指数据元素之间存在的关系。逻辑构造：从逻辑关系上描绘数据，它与数据的存储无关，是独立于计算机的。因而，数据的逻辑构造能够看作是从详细问题抽象出来的数学模型。存储构造：数据对象在计算机中的存储表示，也称为物理构造。抽象数据类型：由用户定义的，表示应用问题的数学模型，以及定义在这个模型上的一组操作的总称。详细包括三部分：数据对象、数据对象上关系的集合和对数据对象的基本操作的集合。2试举一个数据构造的例子，叙述其逻辑构造和存储构造两方面的含义和互相关系。答案：例如有一张学生基本信息表，包括学生的学号、姓名、性别、籍贯、专业等。每个学生基本信息记录对应一个数据元素，学生记录按顺序号排列，构成了学生基本信息记录的线性序列。对于整个表来讲，只要一个开场结点(它的前面无记录)和一个终端结点(它的后面无记录)，其他的结点则各有一个也只要一个直接前趋和直接后继。学生记录之间的这种关系就确定了学生表的逻辑构造，即线性构造。这些学生记录在计算机中的存储表示就是存储构造。假如用连续的存储单元(如用数组表示)来存放这些记录，则称为顺序存储构造；假如存储单元不连续，而是随机存放各个记录，然后用指针进行链接，则称为链式存储构造。即一样的逻辑构造，能够对应不同的存储构造。3简述逻辑构造的四种基本关系并画出它们的关系图。答案：1集合构造数据元素之间除了“属于同一集合的关系外，别无其他关系。例如，确定一名学生能否为班级成员，只需将班级看做一个集合构造。2线性构造数据元素之间存在一对一的关系。例如，将学生信息数据根据其入学报到的时间先后顺序进行排列，将组成一个线性构造。3树构造数据元素之间存在一对多的关系。例如，在班级的管理体系中，班长管理多个组长，每位组长管理多名组员，进而构成树形构造。4图构造或网状构造数据元素之间存在多对多的关系。例如，多位同学之间的朋友关系，任何两位同学都能够是朋友，进而构成图形构造或网状构造。其中树构造和图构造都属于非线性构造。4存储构造由哪两种基本的存储方法实现？答案：1顺序存储构造顺序存储构造是借助元素在存储器中的相对位置来表示数据元素之间的逻辑关系，通常借助程序设计语言的数组类型来描绘。2链式存储构造顺序存储构造要求所有的元素依次存放在一片连续的存储空间中，而链式存储构造，无需占用一整块存储空间。但为了表示结点之间的关系，需要给每个结点附加指针字段，用于存放后继元素的存储地址。所以链式存储构造通常借助于程序设计语言的指针类型来描绘。5选择题1在数据构造中，从逻辑上能够把数据构造分成。A动态构造和静态构造B紧凑构造和非紧凑构造四类基本逻辑构造关系图C线性构造和非线性构造D内部构造和外部构造答案：C2与数据元素本身的形式、内容、相对位置、个数无关的是数据的。A存储构造B存储实现C逻辑构造D运算实现答案：C3通常要求同一逻辑构造中的所有数据元素具有一样的特性，这意味着。A数据具有同一特点B不仅数据元素所包含的数据项的个数要一样，而且对应数据项的类型要一致C每个数据元素都一样D数据元素所包含的数据项的个数要相等答案：B4下面讲法正确的是。A数据元素是数据的最小单位B数据项是数据的基本单位C数据构造是带有构造的各数据项的集合D一些外表上很不一样的数据能够有一样的逻辑构造答案：D解释：数据元素是数据的基本单位，数据项是数据的最小单位，数据构造是带有构造的各数据元素的集合。5算法的时间复杂度取决于。A问题的规模B待处理数据的初态C计算机的配置DA和B答案：D解释：算法的时间复杂度不仅与问题的规模有关，还与问题的其他因素有关。如某些排序的算法，其执行时间与待排序记录的初始状态有关。为此，有时会对算法有最好、最坏以及平均时间复杂度的评价。6下面数据构造中，是非线性数据构造A树B字符串C队列D栈答案：A6试分析下面各程序段的时间复杂度。1x=90;y=100;?while(y>0)if(x>100)x=x-10;y-;elsex+;答案：O(1)解释：程序的执行次数为常数阶。2for(i=0;inext=p->next;p->next=s->next;Ds->next=p->next;p->next=s;答案：D(14)在双向链表存储构造中，删除p所指的结点时须修改指针。Ap->next->prior=p->prior;p->prior->next=p->next;Bp->next=p->next->next;p->next->prior=p;Cp->prior->next=p;p->prior=p->prior->prior;Dp->prior=p->next->next;p->next=p->prior->prior;答案：A(15)在双向循环链表中，在p指针所指的结点后插入q所指向的新结点，其修改指针的操作是。Ap->next=q;q->prior=p;p->next->prior=q;q->next=q;Bp->next=q;p->next->prior=q;q->prior=p;q->next=p->next;Cq->prior=p;q->next=p->next;p->next->prior=q;p->next=q;Dq->prior=p;q->next=p->next;p->next=q;p->next->prior=q;答案：C2算法设计题1将两个递增的有序链表合并为一个递增的有序链表。要求结果链表仍使用原来两个链表的存储空间,不另外占用其它的存储空间。表中不允许有重复的数据。题目分析合并后的新表使用头指针Lc指向，pa和pb分别是链表La和Lb的工作指针,初始化为相应链表的第一个结点，从第一个结点开场进行比拟，当两个链表La和Lb均为到达表尾结点时，依次摘取其中较小者重新链接在Lc表的最后。假如两个表中的元素相等，只摘取La表中的元素，删除Lb表中的元素，这样确保合并后表中无重复的元素。当一个表到达表尾结点，为空时，将非空表的剩余元素直接链接在Lc表的最后。算法描绘voidMergeList(LinkList&La,LinkList&Lb,LinkList&Lc)3C想摘除栈顶结点，并将删除结点的值保存到x中,则应执行操作。Ax=top->data;top=top->link；Btop=top->link;x=top->link；Cx=top;top=top->link；Dx=top->link；答案：A解释：x=top->data将结点的值保存到x中，top=top->link栈顶指针指向栈顶下一结点，即摘除栈顶结点。5设有一个递归算法如下?intfact(intn)?3Cn存储，初始栈顶指针top设为n+1，则元素x进栈的正确操作是()。Atop+;Vtop=x;BVtop=x;top+;Ctop-;Vtop=x;DVtop=x;top-;答案：C解释：初始栈顶指针top为n+1，讲明元素从数组向量的高端地址进栈，又由于元素存储在向量空间V1.n中，所以进栈时top指针先下移变为n，之后将元素x存储在Vn。10设计一个判别表达式中左，右括号能否配对出现的算法，采用数据构造最佳。A线性表的顺序存储构造B队列C.线性表的链式存储构造D.栈答案：D解释：利用栈的后进先出原则。11用链接方式存储的队列，在进行删除运算时。A.仅修改头指针B.仅修改尾指针C.头、尾指针都要修改D.头、尾指针可能都要修改答案：D解释：一般情况下只修改头指针，但是，当删除的是队列中最后一个元素时，队尾指针也丢失了，因而需对队尾指针重新赋值。12循环队列存储在数组A0.m中，则入队时的操作为。A.rear=rear+1B.rear=(rear+1)%(m-1)C.rear=(rear+1)%mD.rear=(rear+1)%(m+1)答案：D解释：数组A0.m中共含有m+1个元素，故在求模运算时应除以m+1。13最大容量为n的循环队列，队尾指针是rear，队头是front，则队空的条件是。A.(rear+1)%n=frontB.rear=frontCrear+1=frontD.(rear-l)%n=front答案：B解释：最大容量为n的循环队列，队满条件是(rear+1)%n=front，队空条件是rear=front。14栈和队列的共同点是。A.都是先进先出B.都是先进后出C.只允许在端点处插入和删除元素D.没有共同点答案：C解释：栈只允许在栈顶处进行插入和删除元素，队列只允许在队尾插入元素和在队头删除元素。15一个递归算法必须包括。A.递归部分B.终止条件和递归部分C.迭代部分D.终止条件和迭代部分答案：B2算法设计题1将编号为0和1的两个栈存放于一个数组空间Vm中，栈底分别处于数组的两端。当第0号栈的栈顶指针top0等于-1时该栈为空，当第1号栈的栈顶指针top1等于m时该栈为空。两个栈均从两端向中间增长。试编写双栈初始化，判定栈空、栈满、进栈和出栈等算法的函数。双栈数据构造的定义如下：Typedefstructinttop2,bot2;09090090090IOIIOIOOB.IOOIOIIOC.IIIOIOIOD.IIIOOIOO通过对的分析，写出一个算法，断定所给的操作序列能否合法。若合法，返回true，否则返回false假定被断定的操作序列已存入一维数组中。答案：A和D是合法序列，B和C是非法序列。设被断定的操作序列已存入一维数组A中。intJudge(charA)00M-1实现循环队列，其中M是队列长度。设队头指针front和队尾指针rear，约定front指向队头元素的前一位置，rear指向队尾元素。定义front=rear时为队空，(rear+1)%m=front为队满。约定队头端入队向下标小的方向发展，队尾端入队向下标大的方向发展。算法描绘#defineM队列可能到达的最大长度typedefstructelemtpdataM;intfront,rear;cycqueue;elemtpdelqueue(cycqueueQ)012121111212C010102101C100,1.100，设每个数据元素占2个存储单元，基地址为10，则LOC5,5=。A808B818C1010D1020答案：B解释：以行序为主，则LOC5,5=5-1*100+5-1*2+10=818。7设有数组Ai,j，数组的每个元素长度为3字节，i的值为1到8，j的值为1到10，数组从内存首地址BA开场顺序存放，当用以列为主存放时，元素A5,8的存储首地址为。ABA+141BBA+180CBA+222DBA+225答案：B解释：以列序为主，则LOC5,8=8-1*8+5-1*3+BA=BA+180。8设有一个10阶的对称矩阵A，采用压缩存储方式，以行序为主存储，a11为第一元素，其存储地址为1，每个元素占一个地址空间，则a85的地址为。A13B32C33D40答案：C9若对n阶对称矩阵A以行序为主序方式将其下三角形的元素(包括主对角线上所有元素)依次存放于一维数组B1.(n(n+1)/2中，则在B中确定aijiAA8,5BA3,10C.A5,8DA0,9答案：B解释：设数组从内存首地址M开场顺序存放，若数组按行先存储，元素A8,5的起始地址为：M+8-0*10+5-1*1=M+84；若数组按列先存储，易计算出元素A3,10的起始地址为：M+10-1*9+3-0*1=M+84。故选B。11设二维数组A1.m，1.n即m行n列按行存储在数组B1.m*n中，则二维数组元素Ai,j在一维数组B中的下标为。A(i-1)*n+jB(i-1)*n+j-1Ci*(j-1)Dj*m+i-1答案：A解释：特殊值法。取i=j=1，易知A1,1的的下标为1，四个选项中仅有A选项能确定的值为1，故选A。12数组A0.4,-1.-3,5.7中含有元素的个数。A55B45C36D16答案：B解释：共有5*3*3=45个元素。13广义表A=(a,b,(c,d),(e,(f,g)，则Head(Tail(Head(Tail(Tail(A)的值为。A(g)B(d)CcDd答案：D解释：Tail(A)=(b,(c,d),(e,(f,g)；Tail(Tail(A)=(c,d),(e,(f,g)；Head(Tail(Tail(A)=(c,d)；Tail(Head(Tail(Tail(A)=(d)；Head(Tail(Head(Tail(Tail(A)=d。14广义表(a,b,c,d)的表头是，表尾是。AaB()C(a,b,c,d)D(b,c,d)答案：C、B解释：表头为非空广义表的第一个元素，能够是一个单原子，可以以是一个子表，(a,b,c,d)的表头为一个子表(a,b,c,d)；表尾为除去表头之外，由其余元素构成的表，表为一定是个广义表，(a,b,c,d)的表尾为空表()。15设广义表L=(a,b,c)，则L的长度和深度分别为。A1和1B1和3C1和2D2和3答案：C解释：广义表的深度是指广义表中展开后所含括号的层数，广义表的长度是指广义表中所含元素的个数。根据定义易知L的长度为1，深度为2。2应用题1已知形式串t=abcaabbabcab写出用KMP法求得的每个字符对应的next和nextval函数值。答案：2设目的为t=“abcaabbabcabaacbacba,形式为p=“abcabaa计算形式p的naxtval函数值；不写出算法,只画出利用KMP算法进行形式匹配时每一趟的匹配经过。答案：p的nextval函数值为0110132。p的next函数值为0111232。利用KMP(改良的nextval)算法，每趟匹配经过如下：第一趟匹配：abcaabbabcabaacbacbaabcab(i=5,j=5)第二趟匹配：abcaabbabcabaacbacbaabc(i=7,j=3)第三趟匹配：abcaabbabcabaacbacbaa(i=7,j=1)第四趟匹配：abcaabbabcabaacbacba(成功)abcabaa(i=15,j=8)3数组A中，每个元素Ai,j的长度均为32个二进位,行下标从-1到9，列下标从1到11，从首地址S开场连续存放主存储器中，主存储器字长为16位。求：存放该数组所需多少单元？存放数组第4列所有元素至少需多少单元？数组按行存放时，元素A7,4的起始地址是多少？数组按列存放时，元素A4,7的起始地址是多少？答案：每个元素32个二进制位，主存字长16位，故每个元素占2个字长，行下标可平移至1到11。12422223s+1824s+142(4)请将香蕉banana用工具H()Head()，T()Tail()从L中取出。L=(apple,(orange,(strawberry,(banana),peach),pear)答案：HHTHTHTL3算法设计题1写一个算法统计在输入字符串中各个不同字符出现的频度并将结果存入文件字符串中的合法字符为A-Z这26个字母和0-9这10个数字。