数据结构本科形成性考核册答案

1、作业1一、单项选择题I .C2.D3.B4.C5.D6.C7.B8.C9.A10.BII .C12.D13.C14.A15.B16.C17.C18.B19.B20.D二、填空题1 .n-i+12 .n-i3 .集合线性结构树形结构图状结构4 .物理结构存储结构5 .线性结构非线性结构6 .有穷性确定性可形性有零个或多个输入有零个或多个输出7 .图状结构8 .树形结构9 .线性结构10 .n-1O（n）11 .s->next=p->next;12 .head13 .q->next=p->next;14 .p->next=head;15 .单链表16 .顺序存储链式存

2、储17 .存储结构18 .两个直接后继直接前驱尾结点头结点19 .头结点的指针指向第一个结点的指针20 .链式链表三、问答题1 .简述数据的逻辑结构和存储结构的区别与联系，它们如何影响算法的设计与实现？答：若用结点表示某个数据元素，则结点与结点之间的逻辑关系就称为数据的逻辑结构。数据在计算机中的存储表示称为数据的存储结构。可见，数据的逻辑结构是反映数据之间的固有关系，而数据的存储结构是数据在计算机中的存储表示。尽管因采用的存储结构不同，逻辑上相邻的结点，其物理地址未必相同，但可通过结点的内部信息，找到其相邻的结点，从而保留了逻辑结构的特点。采用的存储结构不同，对数据的操作在灵活性，算法复杂度等

3、方面差别较大。2 .解释顺序存储结构和链式存储结构的特点，并比较顺序存储结构和链式存储结构的优缺点。答：顺序结构存储时，相邻数据元素的存放地址也相邻，即逻辑结构和存储结构是统一的，要求内存中存储单元的地址必须是连续的。优点：一般情况下，存储密度大，存储空间利用率高。缺点：（1）在做插入和删除操作时，需移动大量元素；（2）由于难以估计，必须预先分配较大的空间，往往使存储空间不能得到充分利用；（3）表的容量难以扩充。链式结构存储时，相邻数据元素可随意存放，所占空间分为两部分，一部分存放结点值，另一部分存放表示结点间关系的指针。优点：插入和删除元素时很方便，使用灵活。缺点：存储密度小，存储空间利用率

4、低。3 .什么情况下用顺序表比链表好？答：顺序表适于做查找这样的静态操作，链表适于做插入和删除这样的动态操作。如果线性表的变化长度变化不大，且其主要操作是查找，则采用顺序表；如果线性表的长度变化较大，且其主要操作是插入、删除操作，则采用链表。4 .解释头结点、第一个结点（或称首元结点）、头指针这三个概念的区别？答：头结点是在链表的开始结点之前附加的一个结点；第一个结点（或称首元结点）是链表中存储第一个数据元素的结点；头指针是指向链表中第一个结点（或为头结点或为首元结点）的指针。5 .解释带头结点的单链表和不带头结点的单链表的区别。答：带头结点的单链表和不带头结点的单链表的区别主要体现在其结构上

5、和算法操作上。在结构上，带头结点的单链表，不管链表是否为空，均含有一个头结点，不带头结点的单链表不含头结点。在操作上，带头结点的单链表的初始化为申请一个头结点。无论插入或删除的位置是地第一个结点还是其他结点，算法步骤都相同。不带头结点的单链表，其算法步骤要分别考虑插入或删除的位置是第一个结点还是其他结点。因为两种情况的算法步骤不同。四、程序填空题1.(1) p->data=i(2) p->next=NULL(3) q->next=p(4) q=p2.(1) head=pq=p(3) p->next=NULL(4) p->next=q->next(5) q-&

6、gt;next=p3.(1) p=q->next(2) q->next=p->next作业2一、单选CBAACAACCCBCBBCCBAADBAABDACDCAD二、填空1、堆栈2、加13、rear值+1fear值+14、假上溢5、队列是否已满sq->=MaxSize尾指针的值尾指针指向的数据单元队列是否为空sq->=sq->front队头指针加1返回front所指位置的元素。6、bceda7、终止条件递归条件8、LU->rear=Lu-front9、?ab+c/fdc/-10、s-next=h;11、h=h->next;12、 r->ne

7、xt=s;13、 f=f->next;14、 字符15、顺序存储链接存储160117、特殊稀疏18、（）（）219、（d,e,f）20、两串的长度相等，且对应位置上的字符相同。21、i（i-1）/2+j22、行号列号元素值三、简答1、一般线性表使用数组来表示的，线性表一般有插入、删除、读取等对于任意元素的操作。而栈只是一种特殊的线性表，栈只能在线性表的一端插入（称为入栈，push）或者读取栈顶元素或者称为“弹出、出栈"（pop）。栈在数组的基础上可以用一个指向栈顶的标识符来表示，如a表示栈，则atop就表示栈顶元素。2、队列是一种运算受限的线性表，它的运算限制与栈不同，是两头都

8、有限制，插入只能在表的一端进行（只进不出，而删除只能在表的另一端进行（只出不进）。而一般线性表是用数组来表示的，线性表一般有插入、删除、读取等对于任意元素的操作。3、如果你的栈有头结点且头结点不存储有效数据，且sq指向栈顶的有效数据，那么sq->next=NULL表示栈空。如果你的栈有头结点且头结点存储有效数据，且sq指向栈顶的有效数据，那么sq=NULL表示栈空。4、（1）CBA,ABC,BAC,BCA,ACB可根据栈的特点"后进先出”来的出结果，不可能白是：CAB（2）可能的输出序列：ABCD,ABDC,ACBD,ACDB,ADCB,BACD,BADC,BCAD,BCDA,

9、BDCACBAD,CBDA,CDBA,DCBA，共14种不可能的输出序歹U:ADBC,BDAC,CDAB,CABD,CADB,DCAB,DABC,DACB,DBCA,DBAC共10种。5、SXSSXSXX6、以元素C开头的有：CBADECBAEDCBDAECBDEACDBAECDBEACDEBACEDBA以元素D开头的有：DCBAEDCEBADCBEADECBA7、第一个有问题3x2x+1x/-5+AB+C*DEF+/-G+8、 一般线性表使用数组来表示的，线性表一般有插入、删除、读取等对于任意元素的操作。广义表是线性表的推广，也称为列表，也是一种线性结构；任何一个非空表，表头可能是原子，也可

10、能是列表；但表尾一定是列表.广义表中元素既可以是原子类型，也可以是列表；当每个元素都为原子且类型相同时，就是线性表.四、1、这个题目拿不准(11) q->front=p->next;(12) free(p);(13) elsefront=rear=p五、1、栈的特点是先进后出，而出队的序列e2首，即el肯定在栈中，然后是e4,这样，e1,e3,e4必须同时在栈中，才能保证e4出栈，然后是e3出栈，此时只有3。el在栈中，然后是e6出栈，这样，必须保证e1,e5,e6同时在栈中。因此，此栈容量最小为2、不会。作业3一、单选BBBCBABCADACCBBC1CABBBBBDDAC17题

11、答案，好像是1倍。二、填空1、非空子树2、树中所有结点的度的最大值3、分支结点非终端结点4、叶子结点分支结点5、后继孩子结点6、祖先7、树中结点的最大层数。8、(n+1)/29、根结点左子树右子树10、左子树根结点右子树11、第一个空不填左子树右子树根结点12、权13、带权路径长度之和14、最优二叉树最小的二叉树15、7616、2n-1个17、多对多18、所有的顶点一次19、先序20、按层21、n22、邻接矩阵邻接表23、2(n-1)24、n-125、一维数组三、综合1、(1)先序：fdbacegihj(2)中序:abcdefghij(3)后序:acbedhjigf2、此树如下：*表示分隔，-

12、表示靠左边的距离.只要斜线/,其它不要画。*A/*-B*C-/*/*-D*e*f-/*/*-G*H*I*J-/*八*GDBLHKMIEJFCA（A表示乘方），则X应为10,即树高为10。892/2=446个892个结点，892-1=891,为单数，故单支结点数为1个。:892/2=446。*L*K*M*其后序遍历：3、（1）树高为X,则2Ax>892>2Ax-1（2）叶子结点数为结点数一半：即（3）因为这是一棵完全二叉树，有（4）最后一个非终端结点的序号为4、（1）ABC(2)-ABCA5、不会6、不会7、(1)V1V2*|*/*|*/*V5*1*/*/*V4-V3(2)邻接矩阵为

13、本题目有错误,多了个（V3,V4）,划去一个。只画线，不要*。大括号要回到最后一行。v1a1=010v2v3v4v50v10邻接表:01(3)v2v3v4v5<-最后一行O（参照课本P130）v1至v5分别由0-4来编号。4A45A5A23A3A每个顶点的度：D(v1)=2D(v2)=3D(V3)=2D(v4)=3D(V5)=2四、1、(1)returnc1+;(2)NodeLevel(BT->right,x);(3)(c2>=1)returnc2+;2、(1)for(j=0;j<=n;j+)(2)dfstree(GA,j,n);五、还没做出来。作业4一、单选DCABA

14、ABDBDDDACDBBDDDCDCAADBAxC二、填空1、哈希查找2、数据项的值记录3、主关键字4、数学期望值5、顺序6、二分查找升序或降序排列7、顺序存储结构8、索引顺序查找顺序查找9、都小于它的根结点的值都大于它的根结点的值一棵二叉排序树10、自变量函数值11、8,13,15,1612、内部排序外部排序13、交换排序14、1615、4816、快速排序堆排序17、主关键字18、其中关键字相等的记录19、(n-1)(n-j)20、堆中最后一个堆顶元素交换三、综合1、解：取第一个元素：70第二趟：7083第三趟：7083100第四趟：7083100105第五趟：107083100105第六趟：71070831001052、解：初始10,18,4,3,6,12,1,9,15,8(1,1)归并后：10183461219815(2,2)归并后：34101816912815(4,4)归并后：134691012188153、解：初始状态:第一趟冒泡第二趟冒泡第三趟冒泡第四趟冒泡第五趟冒泡(8,2)归并后：1346891012151817，18，60，40，7，32，73，65，851718407326073658517187324060736585177183240607365857171832406073658571718324060657385