北大2015年秋季学期数据结构课程作业

1、7. 链表不具备的特点是D_。（第二章）2015 年秋季学期数据结构课程作业. 单选题, 每空有一个正确选择, 请将正确的选择填在题号前边。 （每空 1分,共 30分）1. 鼓励独立完成作业,严惩抄袭！ 数据的逻辑结构被形式地定义为 B=（K,R）, 其中 K是C_的有限集合，R是K上的_H_的有限集合。（第一章）a 存储数据操作c 数据元素 d 操作e 逻辑结构映象g 算法h 关系2. 以下关于算法的说法不正确的是。（第一章）a 一个算法应包含有限个步骤b 算法越简单越好c 算法中的所有操作都可以通过已经实现的基本操作运算有限次实现之d 算法中的每个步骤都能在有限时间内完成3设某数据结构的二

2、元组形式表示为 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是。（第一章）a 线性结构 b 树型结构 c 物理结构 d 图型结构4. 下面程序段的时间复杂度为 _C_（第一章）int sum=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。（第二章）一个线性表是 n 个数据元素的有限序列 线

3、性表中任何一个元素有且仅有一个直接前驱 线性表中任何一个元素有且仅有一个直接后继 以上说法都不正确6. 在含有 n 个结点的顺序存储的线性表中,在任一位置插入一个结点所需移动结点的平均次数为 _B_（第二章）anbn/2c(n+1)/2d(n-1)/2a不必事先估计存储空间b 插入删除不需要移动元素c 可顺序访问任一结点d 所需空间与其长度无关8. 带附加头结点的双循环链表L 为空表的条件是C。（第二章）a L=NULLb L->next=NULLc L->prior=Ld L->prior=NULL9.设广义表L= （a,b,c ）,则L的长度与深度分别为 D.。（第三章）

4、a 1 和110. 若栈采用链式存储结构 , 则下面的说法中正确的是A（第四章）a. 不需要判断栈满但需要判断栈是否为空b. 需要判断栈是否栈空与栈满c. 需要判断栈满但不需要判断栈空d. 栈满栈空都不需要判断11.在一个链栈中，已知s为栈顶指针（直接指向栈顶元素结点，无头结点），t为栈底指针，直接指向栈底元素，则插入 r 结点的操作为第四章）a t->next=r;t=r;b r->next=s;s=r;c s->next=r;s=r;d r->next=t;12. 一个栈的输入序列为 1 ，2，3， 4， 5， 6 下面哪一个序列不可能是这个栈的输出序列 _B_（第

5、四章）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. 循环队列用数组 A0.m-1则当前队列中的元素个数是。（第四章）a (rear-front+m)%mb rear-front+1c rear-front-1d rear-front14. 栈和队列的共同特点是A。（第四章）a. 只允许在端点处插入和删除元素b. 都是先进后出c. 都是先进先出d.没有共同点存放其元素值，已知其头尾指针分别是 front 和 rear ，15. 中缀表达式 （A+B）*D+E/（F+A*D）+C 的后

6、缀形式是 _D （第四章）a. AB+D*E/FA+*DC+b. ABD*+EFAD*+/C+c. ABDEFADC+*+/+*+d. AB+D*EFAD*+/+C+16. 如下图所示的4棵二叉树,C不是完全二叉树。（第五章）。（第b 10c 11d 1218.深度为6（根的层次为1）的二叉树至多有 B结点（第五章）a.64b.63C.31d.3219.二叉树的第k层的结点数最多为ka. 2 -1 b. 2K+1 c. 2K-1D_。（第五章）d. 2 k-120.如果一棵二叉树的先序遍历序列和后序遍历序列正好相反，则该二叉树满足的条件是B_。（第五章）空或只有一个结点b高度等于其结点数任一结

7、点无右孩子d任一结点无左孩子17. 设某棵二叉树中有2000个结点，则该二叉树的最小高度为五章）21.遍历、中序遍历和后序遍历。结论A正确的。（第五章）树的基本遍历策略分为先根遍历和后根遍历；二叉树的基本遍历策略可分为先序a.树的先根遍历序列与其对应的二叉树的先序遍历序列相同b.树的后根遍历序列与其对应的二叉树的先序遍历序列相同C.树的先根遍历序列与其对应的二叉树的中序遍历序列相同d.以上都不对22.根据使用频率为5个字符设计的哈夫曼编码不可能是.。（第六章）a 111，110，10,01，00b 000，001,010， 011， 01c 001，000，01,11，10d 100，111,

8、110， 101, 023.下列数据结构中，不属于二叉树的是（第六章）a.堆b.哈夫曼树c.线索二叉树d. B树D。（第七章）24.采用邻接表存储的图的广度优先遍历算法类似于二叉树的a先序遍历b中序遍历c后序遍历d层次遍历25.对用邻接表表示的图进行深度优先遍历时，通常是借助来实现算法。（第七章）b 队列26.在一个图中，所有顶点的度数之和等于图的边数的C倍。（第七章）a. 1/2b. 1c. 2d. 427.对线性表进行二分查找,要求线性表必须B0 （第九章）a以顺序方式存储b以顺序方式存储，且结点按关键字有序排序c以链接方式存储d结点按关键字有序排序，存储方式无所谓28.排序方法中，每次从

9、未排序序列中查找值最小的元素放到已排序序列（初始时为空）的末尾，该排序方法称为C0 （第十章）a希尔排序b冒泡排序c选择排序d插入排序29.下列四种排序中,C的空间复杂度最大。（第十章）a.插入排序b.冒泡排序 c.归并排序 d.快速排序.填空题，请将正确答案填在上。（每空1分，共30 分）1.数据结构分为逻辑结构和物理结构两种结构。（第一章）2. 线性结构中元素之间存在一对一关系，而树形结构中元素之间存在一对多_关系,图形结构中元素之间存在 多对多关系。（第一章）3. 一个算法的最基本的原操作执行次数为（3n 2+2nlog ,+4n-7）/（5n）.则该算法的时间复杂度为 0（n）0 （第

10、一章）4. 链式存储结构用一组地址任意的存储单元依次存放数据元素，数据元素之间的逻辑关系通过指针间接地反映。（第二章）5. 向一个长度为n的顺序表中的第i个元素（1 < i < n）之前插入一个元素时，需向后移动N-i+1个元素。（第二章）6. 当线性表的元素总数不固定，且很少随机存取表中元素,但插入和删除操作较多时,应米用链式 储结构。（第二章）7.在单链表中，要删除某一指定的结点，必须找到该结点的前驱结点。（第二章）8.删除单链表中结点P所指向的下一个结点（假设不为空）时，应执行q=P->next,p->next=_ q->next和_ delete q_ _

11、的操作。（第二章）9.设广义表L= （a, （b,c,d ）,则L的长度为1，深度为30 （第。（第四章）11.在栈顶进行插入删除一个元素的时间复杂度是0（1）。（第四章）12.后缀算式9 2 3 +- 10 2 / - 的值为_-10 （第四章）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，贝U栈S的容量至少应该是0 （第四章

12、）15. 一棵高度为6的完全二叉树至少有 32个结点，最多有_63_个结点。（第五章）16.如果一个完全二叉树的叶子结点个数为n，则这棵二叉树的总结点数为 _2n或2n-1_。（第五章）17.设某棵二叉树的中序遍历序列为 ABCD后序遍历序列为BADC则其前序遍历序列为CABD_。（第五章）18. 已知一个有向图的邻接矩阵表示，计算第i个结点的度的方法是求矩形第i行非 零元素之和_。（第七章）19. 一个图的三种存储方法中，1、令B接矩阵，邻接表和边集数组2、表示法是不唯一的。（第七章）20. 一个有n个顶点的无向连通图最少有_n-1 _条边，最多_ n（n-1）/2条边。（第七章）21.设一

13、个连通图G中有n个顶点e条边，则其最小生成树上有n-1_条边。（第八章）22.外排序是指在排序前后，数据在_卜存 上,排序时数据调入内存进行的排序方法。（第十章）23.在选择排序、冒泡排序、归并排序中,选择 卡序是不稳定的。（第十章）简答题。（每小题4分，共40分）1.简述顺序表和链表存储方式的特点。（第二章）顺序表的优点势可以随机访问数据元素；缺点是大小固定，不利于增减结点（增减操作需要移动元素）。链表的优点是采用指针方式增减结点， 非常方便（只需要改变指针指向，不三章）10.队列的特点是先进先出，与之对应，栈的特点是后进先出移动结点）。其缺点是不能进行随机访问，只能顺序访问；另外，每个结点

14、上增加指针域,造成额外存储空间增大。2.在一个单链表HL中删除指针p所指结点，应执行如下关键操作:if（）HL = HL->n ext;elseq = HL;while（）q = q->n ext;（第二章）delete p;答案：1、2、3、P = HLq->n ext != pq->n ext = p->n ext;或 q->n ext = q->n ext- >n ext;以下2个问题基于下面的环形队列:设环形队列Q7的当前状态如下,0ai1aO2a36aorearfront3.写出队列Q的队空、队满定条件及进队、出队操作的的描述语句；（第

15、四章）空: rear = front满：（rear+1）%MaxSize = front进队操作：rear = （rea 叶1）%MaxSize; Q（rear）=x出队操作：front = （fron t+1）%MaxSize; X=Q（fro nt）4.画出元素a0,a1,a2出队，元素a4,a5,a6,a7进队后队列Q的状态。（第四章）0123456a3a4a5a6 1a7frontrear5.写出下图这棵二叉树的前序遍历、中序遍历、后序遍历和层次遍历序列。（第五章）前序遍历: 中序遍历: 后序遍历: 层次遍历:ABDFCEGH BFDACGEH FDBGHECA ABCDEFGH,画出

16、按元素排列顺序输入生成的一6.已知一组元素为(30,46,62,27,32,50,13,45)棵二叉搜索树，并写出在这棵二叉搜索树中查找元素50所需的元素比较次数。（第 六章）二叉搜索树如下图，查找50所需比较次数为4.7. 给定权值6,7,12,10,30,25，构造相应的哈夫曼树，要求写出构造步骤，并计算该树的带权路径长度。（第六章）构造的哈夫曼树为：8. 已知一个无向图的邻接表表示为:画出该图的图形表示，并写出在该邻接表存储结构下，以顶点v4为出发点进行深度优先遍历的遍历序列。（第七章）图形如下：以v4为出发点的遍历序列为：v4,v3,v5,v2,v19. 对如下的图，用Prim算法从顶点5开始求最小生成树，写出按次序产生的边。采用Kruscal算法产生的边次序是哪些？画出最小生成树。（第八章）Prim(5,6)(4,6)(1,4)(3,4)(1,2)Kruscal(1,4)(5,6)(3,4)(4,6)(