北京大学2016年秋季学期《数据结构》课程作业【答案】

第１页共10页2016年秋季学期《数据结构》课程作业【答案】一.单选题，每空有一个正确选择，请将正确的选择填在题号前边。（每空1分，共30分）1.数据的逻辑结构被形式地定义为B=(K,R),其中K是__C____的有限集合，R是K上的__H____的有限集合。（第一章）a存储b数据操作c数据元素d操作e逻辑结构f映象g算法h关系2.以下关于算法的说法不正确的是______B________。（第一章）a一个算法应包含有限个步骤b算法越简单越好c算法中的所有操作都可以通过已经实现的基本操作运算有限次实现之d算法中的每个步骤都能在有限时间内完成3．设某数据结构的二元组形式表示为A=(D，R)，D={01，02，03，04，05，06，07，08，09}，R={r}，r={01，02，01，03，01，04，02，05，02，06，03，07，03，08，03，09}，则数据结构A是_______B_______。（第一章）a线性结构b树型结构c物理结构d图型结构4.下面程序段的时间复杂度为___C___（第一章）intsum=0;for(i=0;im;i++)for(j=i;jn;j++)s++;a.O(m+n)b.O(n*n)c.O(m*n)d.O(m*logn)5.下列有关线性表的叙述中，正确的是___A_____。（第二章）a一个线性表是n个数据元素的有限序列b线性表中任何一个元素有且仅有一个直接前驱c线性表中任何一个元素有且仅有一个直接后继d以上说法都不正确6.在含有n个结点的顺序存储的线性表中，在任一位置插入一个结点所需移动结点的平均次数为__C____（第二章）a．nb．(n-1)/2c．n/2d．(n+1)/2第２页共10页7.链表不具备的特点是_____D_______。（第二章）a不必事先估计存储空间b插入删除不需要移动元素c可顺序访问任一结点d所需空间与其长度无关8.带附加头结点的双循环链表L为空表的条件是______C______。（第二章）aL==NULLbL-next==NULLcL-prior==LdL-prior==NULL9.设广义表L=（（（a,b）,c）,d）,则L的长度与深度分别为_____B____。（第三章）a1和1b1和3c2和3d1和210.若栈采用链式存储结构,则下面的说法中正确的是____A____（第四章）a.不需要判断栈满但需要判断栈是否为空b.需要判断栈是否栈空与栈满c.需要判断栈满但不需要判断栈空d.栈满栈空都不需要判断11.在一个链栈中，已知s为栈顶指针（直接指向栈顶元素结点，无头结点），t为栈底指针，直接指向栈底元素，则插入r结点的操作为_____B_______。（第四章）at-next=r;t=r;br-next=s;s=r;cs-next=r;s=r;dr-next=t;12.一个栈的输入序列为1，2，3，4，5，6下面哪一个序列不可能是这个栈的输出序列___B___（第四章）a.1,2,3,4,5,6b.3,2,6,4,5,1c.2,4,6,5,3,1d.6,5,4,3,2,113.循环队列用数组A[0..m-1]存放其元素值，已知其头尾指针分别是front和rear，则当前队列中的元素个数是_____A_______。（第四章）a(rear-front+m)%mbrear-front+1crear-front-1drear-front14.栈和队列的共同特点是______A______。（第四章）a.只允许在端点处插入和删除元素b.都是先进后出c.都是先进先出d.没有共同点15.中缀表达式(A+B)*D+E/(F+A*D)+C的后缀形式是___D___（第四章）第３页共10页a．AB+D*E/FA+*DC+b．ABD*+EFAD*+/C+c．ABDEFADC+*+/+*+d．AB+D*EFAD*+/+C+16.如下图所示的4棵二叉树，____C_____不是完全二叉树。（第五章）17.设某棵二叉树中有2000个结点，则该二叉树的最小高度为____C_______（第五章）a9b10c11d1218.深度为6(根的层次为1)的二叉树至多有_____B_____结点（第五章）a.64b.63c.31d.3219.二叉树的第k层的结点数最多为______D______。（第五章）a.2k-1b.2K+1c.2K-1d.2k-120.如果一棵二叉树的先序遍历序列和后序遍历序列正好相反，则该二叉树满足的条件是_____B_____。（第五章）a空或只有一个结点b高度等于其结点数c任一结点无右孩子d任一结点无左孩子21.树的基本遍历策略分为先根遍历和后根遍历；二叉树的基本遍历策略可分为先序遍历、中序遍历和后序遍历。结论___A_______是正确的。（第五章）a.树的先根遍历序列与其对应的二叉树的先序遍历序列相同b.树的后根遍历序列与其对应的二叉树的先序遍历序列相同c.树的先根遍历序列与其对应的二叉树的中序遍历序列相同d.以上都不对22.根据使用频率为5个字符设计的哈夫曼编码不可能是____B________。（第六章）a100，111，110，101，0b111，110，10，01，00c000，001，010，011，01d001，000，01，11，1023.下列数据结构中,不属于二叉树的是_____D_______（第六章）a.堆b.哈夫曼树c.线索二叉树d.B树24.采用邻接表存储的图的深度优先遍历算法类似于二叉树的____D______。（第七章）第４页共10页a先序遍历b中序遍历c后序遍历d层次遍历25.对用邻接表表示的图进行深度优先遍历时，通常是借助___A______来实现算法。（第七章）a队列b栈c树d图26.在一个图中，所有顶点的度数之和等于图的边数的____C_____倍。（第七章）a.1/2b.1c.2d.427.对线性表进行二分查找，要求线性表必须_____B_______。（第九章）a以顺序方式存储b以顺序方式存储，且结点按关键字有序排序c以链接方式存储d结点按关键字有序排序，存储方式无所谓28.排序方法中，每次从未排序序列中查找值最小的元素放到已排序序列（初始时为空）的末尾，该排序方法称为_____C_______。（第十章）a选择排序b冒泡排序c希尔排序d插入排序29.下列四种排序中，____A________是最不稳定的。（第十章）a.选择排序b.冒泡排序c.归并排序d.快速排序二.填空题，请将正确答案填在____上。（每空1分，共30分）1.数据结构分为_逻辑结构___和物理结构两种结构。（第一章）2.线性结构中元素之间存在一对一关系，而图形结构中元素之间存在_多对多_关系，树形结构中元素之间存在一对多_关系。（第一章）3.一个算法的最基本的原操作执行次数为(3n2+2nlog2n+4n-7)/(7n),则该算法的时间复杂度为_O(n)______。（第一章）4.链式存储结构用一组地址任意的存储单元依次存放数据元素，数据元素之间的逻辑关系通过__指针________间接地反映。（第二章）5.向一个长度为n的顺序表中的第i个元素(1≤i≤n)之后插入一个元素时，需向后移动__N-i+1___个元素。（第二章）6.当线性表的元素总数不固定，且很少随机存取表中元素，但插入和删除操作较多时，应采用__链式__存储结构。（第二章）7.在单链表中，要删除某一指定的结点，必须找到该结点的__前驱___结点。（第二章）8.删除单链表中结点p所指向的下一个结点（假设不为空）时，应执行__q=____P-next__,p-next=__q-next_____和__deleteq_____的操作。（第二章）第５页共10页9.设广义表L=（（a,b,c））,则L的长度为____1____，深度为___2______。（第三章）10.栈的特点是，与之对应后进先出，队列的特点是___先进先出______。（第四章）11.在栈顶进行插入删除一个元素的时间复杂度是__O(1)______。（第四章）12.后缀算式923+-102/-的值为___-1____。（第四章）13.一个环形队列中共有MaxSize个单元，那么队满时共有_MaxSize–1__个元素。（第四章）14.设栈S和队列Q的初始状态为空，元素a1,a2,a3,a4,a5,a6,a7,a8依次通过栈S，一个元素出栈后立即进入队列Q，若8个元素出队列的次序是a3,a5,a4,a8,a7,a6,a2,a1，则栈S的容量至少应该是_____5_______。（第四章）15.一棵高度为5的完全二叉树至少有__2__个结点，最多有_64____个结点。（第五章）16.如果一个完全二叉树的叶子结点个数为n，则这棵二叉树的总结点数为_2n或2n-1_______。（第五章）17.设某棵二叉树的中序遍历序列为ABCD，后序遍历序列为BADC，则其前序遍历序列为___CABD____。（第五章）18.已知一个有向图的邻接矩阵表示，计算第i个结点的度的方法是__求矩形第i行非零元素之和_____。（第七章）19.一个图的三种存储方法中，_邻接矩阵____表示法是唯一的，_邻接表和边集数组___表示法是不唯一的。（第七章）20.一个有n个顶点的无向连通图最少有_n-1__条边，最多_n(n-1)/2__条边。（第七章）21.设一个连通图G中有n个顶点e条边，则其最小生成树上有__n-1___条边。（第八章）22.外排序是指在排序前后，数据在___外存__上，排序时数据调入内存进行的排序方法。（第十章）23.在选择排序、冒泡排序、归并排序中，___选择___排序是空间复杂度最大的。（第十章）三.简答题。（每小题4分，共40分）1.（第二章）简述顺序表和链表存储方式的特点。答顺序表的优点势可以随机访问数据元素；缺点是大小固定，不利于增减结点（增减操作需要移动元素）。链表的优点是采用指针方式增减结点，非常方便（只需要改变指针指向，不移动结点）。其缺点是不能进行随机访问，只能顺序访问；另外，每第６页共10页个结点上增加指针域，造成额外存储空间增大。2.（第二章）在一个单链表HL中删除指针p所指结点，应执行如下关键操作：if(________)HL=HL-next;else{q=HL;while(________)q=q-next;_____________;}deletep;答：1、p==HL2、q-next!=p3、q-next=p-next;或q-next=q-next-next;以下2个问题基于下面的环形队列：设环形队列Q[7]的当前状态如下，0123456a1a2a3a03.（第四章）写出队列Q的队空、队满定条件及进队、出队操作的的描述语句；空：rear==front满：(rear+1)%MaxSize==front进队操作：rear=(rear+1)%MaxSize;Q(rear)=x出队操作：front=(front+1)%MaxSize;X=Q(front)4.（第四章）画出元素a0,a1,a2出队，元素a4,a5,a6,a7进队后队列Q的状态。frontrear第７页共10页5.（第五章）写出下图这棵二叉树的前序遍历、中序遍历、后序遍历和层次遍历序列。答前序遍历：ABDFCEGH中序遍历：BFDACGEH后序遍历：FDBGHECA层次遍历：ABCDEFGH6.（第六章）给定权值{6,7,12,10,30,25}，构造相应的哈夫曼树，要求写出构造步骤，并计算该树的带权路径长度。答构造的哈夫曼树为：带权路径长度为：(30+25)*2+(6+7+10+12)*3=215BCFGHDEA第８页共10页7.（第七章）已知一个无向图的邻接表表示为：画出该图的图形表示，并写出在该邻接表存储结构下，以顶点v4为出发点进行深度优先遍历的遍历序列。答图形如下：以v4为出发点的遍历序列为：v4,v3,v5,v2,v18.（第八章）对如下的图，用Pri