数据结构1-4章习题答案

第1章概论习题参考解答一、填空题1、数据的逻辑结构是数据元素之间的逻辑关系，通常有下列4类：（）、（）、（）、（）。【答】集合、线性结构、树型结构和图状结构。2、数据的存储结构是数据在计算机存储器里的表示，主要有4种基本存储方法：（）、（）、（）、（）。【答】顺序存储方法、链接存储方法、索引存储方法和散列存储方法。二、选择题1、一个算法必须在执行有穷步之后结束，这是算法的（）。（A）正确性（B）有穷性（C）确定性（D）可行性【答】B。2、算法的每一步，必须有确切的定义。也就是说，对于每步需要执行的动作必须严格、清楚地给出规定。这是算法的（）。（A）正确性（B）有穷性（C）确定性（D）可行性【答】C。3、算法原则上都是能够由机器或人完成的。整个算法好像是一个解决问题的“工作序列”，其中的每一步都是我们力所能及的一个动作。这是算法的（）。（A）正确性（B）有穷性（C）确定性（D）可行性【答】D。三、简答题1、算法与程序有何异同？【答】尽管算法的含义与程序非常相似，但两者还是有区别的。首先，一个程序不一定满足有穷性，因此它不一定是算法。例如，系统程序中的操作系统，只要整个系统不遭受破坏，它就永远不会停止，即使没有作业要处理，它仍处于等待循环中，以待一个新作业的进入。因此操作系统就不是一个算法。其次，程序中的指令必须是计算机可以执行的，而算法中的指令却无此限止。如果一个算法采用机器可执行的语言来书写，那么它就是一个程序。2、什么是数据结构？试举一个简单的例子说明。【答】数据结构是指数据对象以及该数据对象集合中的数据元素之间的相互关系（即数据元素的组织形式）。例如，队列的逻辑结构是线性表（先进先出）；队列在计算机中既可以采用顺序存储也可以采用链式存储；对队列可进行删除、插入数据元素以及判断是否为空队列、将队列置空等操作。3、什么是数据的逻辑结构？什么是数据的存储结构？【答】数据元素之间的逻辑关系，也称为数据的逻辑结构。数据元素以及它们之间的相互关系在计算机存储器内的表示（又称映象），称为数据的存储结构，也称数据的物理结构。4、什么是算法？算法有哪些特性？【答】算法是对特定问题求解步骤的一种描述，它是指令的有限序列，其中每一条指令表示一个或多个操作；此外，一个算法还具有下列5个特性：①有穷性：一个算法必须在执行有穷步之后结束，即算法必须在有限时间内完成。②确定性：算法中每一步必须有确切的含义，不会产生二义性。并且，在任何条件下，算法只有唯一的一条执行路径，即对于相同的输入只能得出相同的输出。③可行性：一个算法是能行的，即算法中的每一步都可以通过已经实现的基本运算执行有限次得以实现。④输入：一个算法有零个或多个输入，它们是算法开始时对算法给出的初始量。⑤输出：一个算法有一个或多个输出，它们是与输入有特定关系的量。四、算法分析题1、将下列复杂度由小到大重新排序：2n、n!、n2、10000、log2n、n×log2n。【答】10000log2nn×log2nn22nn!。2、用大“O”表示法描述下列复杂度：⑴5n5/2+n2/5【答】O(n5/2)。⑵6×log2n+9n【答】O(n)。⑶3n4+n×log2n【答】O(n4)。⑷n×log2n+n×log3n【答】O(n×log2n)。3、设n为正整数，请用大“O”表示法描述下列程序段的时间复杂度。⑴i=1;k=0;⑵i=0;k=0;while(in)do{k=k+10*i;{k=k+10*i;i++;i++;}}while(in);【答】O(n)。【答】O(n)。⑶i=1;j=0;⑷x=n;/*n是常数且n1*/while(i+j=n)while(x=(y+1)*(y+1)){if(ij)j++;y++;elsei++}【答】O(n)。【答】O(n)。⑸for((i=1;i=n;i++)⑹x=91;y=100;for(j=1;j=i;j++)while(y0)for(k=1;k=j;k++){if(x100){x-=10;y--;}x+=c;(c为常数)elsex++;}【答】O(n3)。【答】O(n)。第2章线性表习题参考解答一、简答题1．试描述头指针、头结点、开始结点的区别、并说明头指针和头结点的作用。【答】头指针：是指向链表中的第一个结点的指针。头结点：在开始结点之前附加上的一个结点。开始结点：链表的第一个结点。头指针是一个指向地址的变量，用于表示一个链表的开始。引入头结点可以更加方便的进行链表是否为空的判断，同时方便了插入和删除结点。开始结点用于存储链表的第一个数据元素。2．何时选用顺序表、何时选用链表作为线性表的存储结构为宜?【答】顺序表中查找元素、获取表长非常容易，但是，要插入或者删除一个元素却需要移动大量的元素；相反，链表中却是方便插入或者删除元素，在查找元素的是，需要进行遍历。因此，当所涉及的问题常常进行查找等操作，而插入、删除相对较少的是，适合采用顺序表；当常常需要插入、删除的时候，适合采用链表。3．为什么在单循环链表中设置尾指针比设置头指针更好?【答】在单循环链表中，设置尾指针，可以更方便的判断链表是否为空。4．在单链表、双链表和单循环链表中，若仅知道指针p指向某结点，不知道头指针，能否将结点*p从相应的链表中删去?【答】本题分三种情况讨论：1、单链表：当知道指针p指向某结点时，能够根据该指针找到其直接后继，但是不知道头指针，因此不能找到该结点的直接前趋，因此，无法删除该结点。2、双链表：根据指针p可以找到该结点的直接前趋和直接后继，因此，能够删除该结点。3、单循环链表：和双链表类似，根据指针p也可以找到该结点的直接前趋和直接后继，因此，也可以删除该结点。5．下述算法的功能是什么?LinkListDemo(LinkList*L)/*L是无头结点单链表*/{LNode*Q,*P;if(L&&L-next){Q=L;L=L-next;P=L;while(P-next)P=P-next;P-next=Q;Q-next=NULL;}returnL;}/*Demo*/【答】将原来的第一个结点变成末尾结点，原来的第二个结点变成链表的第一个结点。二、算法设计题1．试分别用顺序表和单链表作为存储结构，实现将线性表(a0,a1,...an-1)就地逆置的操作，所谓就地指辅助空间应为O(1)。【答】分两种情况讨论如下。①顺序表：要将该表逆置，可以将表中的开始结点与终端结点互换，第二个结点与倒数第二个结点互换，如此反复，就可将整个表逆置了。算法如下：voidreverlist(sequenlist*L){datatypet;/*设置临时空间用于存放data*/inti;for(i=0;iL-length/2;i++){t=L-data[i];/*交换数据*/L-data[i]=L-data[L-length-1-i];L-data[L-length-1-i]=t;}}②链表：可以利用指针的指向转换来达到表逆置的目的。算法是这样的：LinkList*reverselist(LinkList*head)/*将head所指的单链表逆置*/{LNode*p,*q;/*设置两个临时指针变量*/if((head-next!=NULL)&&(head-next-next!=NULL))/*当链表不是空表或单结点时*/{p=head-next;q=p-next;p-next=NULL;/*将开始结点变成终端结点*/while(q)/*每次循环将后一个结点变成开始结点*/{p=q;q=q-next;p-next=head-next;head-next=p;}returnhead;}returnhead;/*如是空表或单结点表，直接返回head*/}2．顺序表L是一个递增有序表，试写一算法，将x插入L中，并使L仍是一个有序表。【答】因已知顺序表L是递增有序表，所以只要从头找起找到第一个比它大（或相等）的结点数据，把x插入到这个数所在的位置就是了。算法如下：voidInsertIncreaseList(Sequenlist*L,Datatypex){inti;for(i=0;iL-length&&L-data[i]x;i++);/*查找并比较,分号不能少*/InsertList(L,x,i);/*调用顺序表插入函数*/}3．顺序表L是一个递减有序表，试写一算法，将x插入其后仍保持L的有序性。【答】类似于第2题，读者可自行完成，这里不在赘述。4．知L1和L2分别指向两个单链表的头结点，且已知其长度分别为m和n。试写一算法将这两个链表连接在一起，请分析你的算法的时间复杂度。【答】算法如下：LinkList*Link(LinkList*L1,LinkList*L2){/*将两个单链表连接在一起*/LNode*p,*q;p=L1;q=L2;while(p-next)p=p-next;/*查找终端结点*/p-next=q-next;/*将L2的开始结点链接在L1之后*/returnL1;}本算法的主要操作时间花费在查找L1的终端结点上，与L2的长度无关，所以本算的法时间复杂度为：O(m)5．A和B是两个单链表，其表中元素递增有序。试写一算法将A和B归并成一个按元素值递减有序的单链表C，并要求辅助空间为O(1)，请分析算法的时间复杂度。【答】根据已知条件，A和B是两个递增有序表，所以我们可以以A表为基础，按照插入单个元素的办法把B表的元素插入A表中，完成后，将表逆置就得到了一个按元素值递减有序的单链表C了。算法如下：LinkList*MergeSort(LinkList*A,LinkList*B){/*归并两个递增有序表为一个递减有序表*/LNode*pa,*pb,*qa,*qb;pa=A;pb=B;qa=A-next;qb=B-next;while(qa&&qb){if(qb-dataqa-data){/*当B中的元素小于A中当前元素时，插入到它的前面*/pb=qb;qb=qb-next;/*指向B中下一元素*/pa-next=pb;pb-next=qa;pa=pb;}elseif(qb-data=pa-data&&qb-data=qa-data){/*当B中元素大于等于A中当前元素，且小于等于A中后一元素时，将此元素插入到A的当前元素之后*/pa=qa;qa=qa-next;/*保存A的后一元素位置*/pb=qb;qb=qb-next;/*保存B的后一元素位置*/a-next=pb;/*插入元素*/pb-next=qa;}else{/*如果B中元素总是更大,指针移向下一个A元素*/pa=qa;qa=qa-next;}}if(qb)/*如果A表已到终端而B表还有结点未插入*/{/*将B表接到A表后面*/pa-next=qb;}C=reverselist(A);/*调用前面所设计的逆置函数*/returnC;/*返回新的单链表C,已是递减排列*/}该算法的时间复杂度分析如下：算法中只有一个while循环，在这个循环中，按照最坏的情况是B元素既有插到A的最前的，也有插到最后的，也就是说需要把A中元素和B中元素全部检查比较过，这时的所费时间就是m+n.而新链表的长度也是m+n+1(有头结点)，这样逆置函数的执行所费时间为m+n+1。所以可得整个算法的时间复杂度为：m+n+m+n+1=2(m+n)+1=O(m+n)6．试编写一算法将单链表中值重复的结点删除，使所得的结果表中各结点值均不相同。已知由单链表表示的线性表中，含有三类字符的数据元素(如：字母字符、数字字符和其它字符)，试编写算法构造三个以循环链表表示的线性表，使每个表中只含同一类的字符，且利用原表中的结点空间作为这三个表的结点空间，头结点可另辟空间。【答】本题分为两个部分，第一部分是删除重复结点，第二部分链表的分解。首先看第一部分：要删除重复结点，有两种方式，第一种方式：先取开始结点中的值，将它与其后的所有结点值一一比较