北大17秋08281006-数据结构作业答案.doc

一、单选题(共30题，每题1分，共30分)每空有一个正确选择，请将正确的选择填在题号前边。（每空1分，共30分）1.（第一章）数据的逻辑结构被形式地定义为B=(K,R),其中K是 _的有限集合。A.存储B.数据操作C.数据元素D.操作E.逻辑结构F.映象G.算法H.关系试题编号：1.01.1试题类型：单选题标准答案：C试题难度：一般试题解析：*考生答案：C考生得分：*是否评分：未评分评价描述：*2.（第一章）数据的逻辑结构被形式地定义为B=(K,R),其中R是K上的_的有限集合。 A.存储B.数据操作C.数据元素D.操作E.逻辑结构F.映象G.算法H.关系试题编号：1.01.2试题类型：单选题标准答案：H试题难度：一般试题解析：*考生答案：H考生得分：*是否评分：未评分评价描述：*3.（第一章）以下关于算法的说法不正确的是_。A.一个算法应包含有限个步骤B.算法越简单越好C.算法中的所有操作都可以通过已经实现的基本操作运算有限次实现之D.算法中的每个步骤都能在有限时间内完成试题编号：1.02试题类型：单选题标准答案：B试题难度：一般试题解析：*考生答案：B考生得分：*是否评分：未评分评价描述：*4.（第一章）设某数据结构的二元组形式表示为A=(D，R)，D=01，02，03，04，05，06，07，08，09，R=r，r=，则数据结构A是_。A.线性结构B.树型结构C.物理结构D.图型结构试题编号：1.03试题类型：单选题标准答案：*试题难度：一般试题解析：*考生答案：B考生得分：*是否评分：未评分评价描述：*5.（第一章）下面程序段的时间复杂度为_ int sum=0; for(i=0; im;i+) for(j=i;jnext=r;t=r;B.r-next=s;s=r;C.s-next=r;s=r;D.r-next=t;试题编号：1.08试题类型：单选题标准答案：*试题难度：一般试题解析：*考生答案：B考生得分：*是否评分：未评分评价描述：*10.（第二章）链表不具备的特点是_。A.不必事先估计存储空间B.插入删除不需要移动元素C.可顺序访问任一结点 D.所需空间与其长度无关试题编号：1.09试题类型：单选题标准答案：*试题难度：一般试题解析：*考生答案：D考生得分：*是否评分：未评分评价描述：*11.（第二章）带附加头结点的双循环链表L为空表的条件是_。A.L=NULL B. L-next=NULL C. L-prior=L D.L-prior=NULL试题编号：1.10试题类型：单选题标准答案：*试题难度：一般试题解析：*考生答案：C考生得分：*是否评分：未评分评价描述：*12.（第三章）设广义表L=（a,（b,c,d）,则L的长度与深度分别为_。A.1和3B.1和2C.2和3D.2和2试题编号：1.11试题类型：单选题标准答案：*试题难度：一般试题解析：*考生答案：A考生得分：*是否评分：未评分评价描述：*13.（第四章）一个栈的输入序列为1，2，3，4，5，6下面哪一个序列不可能是这个栈的输出序列_A.1, 2, 3, 4, 5, 6B.3, 2, 6, 4, 5, 1C.2, 4, 6, 5, 3, 1D.6, 5, 4, 3, 2, 1试题编号：1.12试题类型：单选题标准答案：*试题难度：一般试题解析：*考生答案：B考生得分：*是否评分：未评分评价描述：*14.（第四章）循环队列用数组A0.m-1存放其元素值，已知其头尾指针分别是front和rear，则当前队列中的元素个数是_。A.(rear-front+m)%mB.rear-front+1 C.rear-front-1D.rear-front试题编号：1.13试题类型：单选题标准答案：*试题难度：一般试题解析：*考生答案：A考生得分：*是否评分：未评分评价描述：*15.（第四章）栈和队列的共同特点是_。A.只允许在端点处插入和删除元素B.都是先进后出C.都是先进先出D.没有共同点试题编号：1.14试题类型：单选题标准答案：*试题难度：一般试题解析：*考生答案：A考生得分：*是否评分：未评分评价描述：*16.（第四章）中缀表达式(A+B)*D+E/(F+A*D)+C的后缀形式是_A.AB+D*E/FA+*DC+B.ABD*+EFAD*+/C+C.ABDEFADC+*+/+*+ D.AB+D*EFAD*+/+C+试题编号：1.15试题类型：单选题标准答案：*试题难度：一般试题解析：*考生答案：D考生得分：*是否评分：未评分评价描述：*17.（第五章）如下图所示的4棵二叉树，_不是完全二叉树。A.B.C.D.试题编号：1.16.试题类型：单选题标准答案：*试题难度：一般试题解析：*考生答案：C考生得分：*是否评分：未评分评价描述：*18.（第五章）设某棵二叉树中有2000个结点，则该二叉树的最小高度为_。A.9B.10C.11D.12试题编号：1.17试题类型：单选题标准答案：*试题难度：一般试题解析：*考生答案：C考生得分：*是否评分：未评分评价描述：*19.（第五章）深度为6(根的层次为1)的二叉树至多有_结点A.64B.63C.31D.32试题编号：1.18试题类型：单选题标准答案：*试题难度：一般试题解析：*考生答案：B考生得分：*是否评分：未评分评价描述：*20.（第五章）二叉树的第k层的结点数最多为_。A.2k-1B.2k+1C.2k-1D.2k-1试题编号：1.19试题类型：单选题标准答案：*试题难度：一般试题解析：*考生答案：D考生得分：*是否评分：未评分评价描述：*21.（第五章）如果一棵二叉树的先序遍历序列和后序遍历序列正好相反，则该二叉树满足的条件是_。A.空或只有一个结点B.高度等于其结点数C.任一结点无右孩子D.任一结点无左孩子试题编号：1.20试题类型：单选题标准答案：*试题难度：一般试题解析：*考生答案：C考生得分：*是否评分：未评分评价描述：*22.（第五章）树的基本遍历策略分为先根遍历和后根遍历；二叉树的基本遍历策略可分为先序遍历、中序遍历和后序遍历。结论_是正确的。A.树的先根遍历序列与其对应的二叉树的先序遍历序列相同 B.树的后根遍历序列与其对应的二叉树的先序遍历序列相同 C.树的先根遍历序列与其对应的二叉树的中序遍历序列相同 D.以上都不对试题编号：1.21试题类型：单选题标准答案：*试题难度：一般试题解析：*考生答案：A考生得分：*是否评分：未评分评价描述：*23.（第六章）根据使用频率为5个字符设计的哈夫曼编码不可能是_。A.100，111，110，101，0 B.111，110，10，01，00C.000，001，010，011，01D.001，000，01，11，10试题编号：1.22试题类型：单选题标准答案：*试题难度：一般试题解析：*考生答案：B考生得分：*是否评分：未评分评价描述：*24.（第六章）下列数据结构中,不属于二叉树的是_A.堆B.哈夫曼树C.线索二叉树D.B树试题编号：1.23试题类型：单选题标准答案：*试题难度：一般试题解析：*考生答案：D考生得分：*是否评分：未评分评价描述：*25.（第七章）采用邻接表存储的图的广度优先遍历算法类似于二叉树的_。A.先序遍历B.中序遍历C.后序遍历D.层次遍历试题编号：1.24试题类型：单选题标准答案：*试题难度：一般试题解析：*考生答案：D考生得分：*是否评分：未评分评价描述：*26.（第七章）对用邻接表表示的图进行深度优先遍历时，通常是借助_来实现算法。A.队列 B.栈 C.树 D.图试题编号：1.25试题类型：单选题标准答案：*试题难度：一般试题解析：*考生答案：A考生得分：*是否评分：未评分评价描述：*27.（第七章）在一个图中，所有顶点的度数之和等于图的边数的_倍。A.1/2 B.1C.2D.4试题编号：1.26试题类型：单选题标准答案：*试题难度：一般试题解析：*考生答案：C考生得分：*是否评分：未评分评价描述：*28.（第九章）对线性表进行二分查找，要求线性表必须_。A.以顺序方式存储B.以顺序方式存储，且结点按关键字有序排序 C.以链接方式存储D.结点按关键字有序排序，存储方式无所谓试题编号：1.27试题类型：单选题标准答案：*试题难度：一般试题解析：*考生答案：B考生得分：*是否评分：未评分评价描述：*29.（第十章）排序方法中，每次从未排序序列中查找值最小的元素放到已排序序列（初始时为空）的末尾，该排序方法称为_。A.选择排序B.冒泡排序C.希尔排序 D.插入排序试题编号：1.28试题类型：单选题标准答案：*试题难度：一般试题解析：*考生答案：C考生得分：*是否评分：未评分评价描述：*30.（第十章）下列四种排序中，_是空间复杂度最大的。A.选择排序B.冒泡排序C.归并排序D.快速排序试题编号：1.29试题类型：单选题标准答案：*试题难度：一般试题解析：*考生答案：A考生得分：*是否评分：未评分评价描述：*二、填空题(共30题，每题1分，共30分)请将正确答案填在_上。（每空1分，共30分） 31.（第一章）数据结构分为和物理结构两种结构。试题编号：2.01试题类型：填空题标准答案：*试题难度：一般试题解析：*考生答案：逻辑结构考生得分：*是否评分：未评分评价描述：*32.（第一章）线性结构中元素之间存在一对一关系，而图形结构中元素之间存在关系。试题编号：2.02.1试题类型：填空题标准答案：*试题难度：一般试题解析：*考生答案：多对多考生得分：*是否评分：未评分评价描述：*33.（第一章）线性结构中元素之间存在一对一关系，而树形结构中元素之间存在关系。试题编号：2.02.2试题类型：填空题标准答案：*试题难度：一般试题解析：*考生答案：一对多考生得分：*是否评分：未评分评价描述：*34.（第一章）一个算法的最基本的原操作执行次数为(3n2+2nlog2n+4n-7)/(7n),则该算法的时间复杂度为。试题编号：2.03试题类型：填空题标准答案：*试题难度：一般试题解析：*考生答案：O（n)考生得分：*是否评分：未评分评价描述：*35.（第二章）链式存储结构用一组地址任意的存储单元依次存放数据元素，数据元素之间的逻辑关系通过间接地反映。试题编号：2.04试题类型：填空题标准答案：*试题难度：一般试题解析：*考生答案：指针考生得分：*是否评分：未评分评价描述：*36.（第二章）向一个长度为n的顺序表中的第i个元素(1in)之后插入一个元素时，需向后移动个元素。试题编号：2.05试题类型：填空题标准答案：*试题难度：一般试题解析：*考生答案：N-i+1考生得分：*是否评分：未评分评价描述：*37.（第二章）当线性表的元素总数不固定，且很少随机存取表中元素，但插入和删除操作较多时，应采用存储结构。试题编号：2.06试题类型：填空题标准答案：*试题难度：一般试题解析：*考生答案：链式考生得分：*是否评分：未评分评价描述：*38.（第二章）在单链表中，要删除某一指定的结点，必须找到该结点的结点。试题编号：2.07试题类型：填空题标准答案：*试题难度：一般试题解析：*考生答案：前驱考生得分：*是否评分：未评分评价描述：*39.（第二章）删除单链表中结点p所指向的下一个结点（假设不为空）时，应执行以下操作： 第一步 q=;试题编号：2.08.1试题类型：填空题标准答案：*试题难度：一般试题解析：*考生答案：P-next考生得分：*是否评分：未评分评价描述：*40.（第二章）第二步 p-next=;试题编号：2.08.2试题类型：填空题标准答案：*试题难度：一般试题解析：*考生答案：q-next考生得分：*是否评分：未评分评价描述：*41.（第二章）第三步 ;试题编号：2.08.3试题类型：填空题标准答案：*试题难度：一般试题解析：*考生答案：delete q的操作考生得分：*是否评分：未评分评价描述：*42.（第三章）设广义表L=（a,b,c）,则L的长度为。试题编号：2.09.1试题类型：填空题标准答案：*试题难度：一般试题解析：*考生答案：1考生得分：*是否评分：未评分评价描述：*43.（第三章）设广义表L=（a,b,c）,则L的深度为。试题编号：2.09.2试题类型：填空题标准答案：*试题难度：一般试题解析：*考生答案：2考生得分：*是否评分：未评分评价描述：*44.（第四章）栈的特点是，与之对应后进先出，队列的特点是。试题编号：2.10试题类型：填空题标准答案：*试题难度：一般试题解析：*考生答案：先进先出考生得分：*是否评分：未评分评价描述：*45.（第四章）在栈顶进行插入删除一个元素的时间复杂度是。试题编号：2.11试题类型：填空题标准答案：*试题难度：一般试题解析：*考生答案：O（1）考生得分：*是否评分：未评分评价描述：*46.（第四章）后缀算式9 2 3 +- 10 2 / -的值为。试题编号：2.12试题类型：填空题标准答案：*试题难度：一般试题解析：*考生答案：-1考生得分：*是否评分：未评分评价描述：*47.（第四章）一个环形队列中共有MaxSize个单元，那么队满时共有个元素。试题编号：2.13试题类型：填空题标准答案：*试题难度：一般试题解析：*考生答案：MaxSize-1考生得分：*是否评分：未评分评价描述：*48.（第四章）设栈S和队列Q的初始状态为空，元素a1,a2,a3,a4,a5,a6,a7,a8依次通过栈S，一个元素出栈后立即进入队列Q，若8个元素出队列的次序是a3,a5,a4,a8,a7,a6,a2,a1，则栈S的容量至少应该是。试题编号：2.14试题类型：填空题标准答案：*试题难度：一般试题解析：*考生答案：5考生得分：*是否评分：未评分评价描述：*49.（第五章）一棵高度为5的完全二叉树至少有个结点。试题编号：2.15.1试题类型：填空题标准答案：*试题难度：一般试题解析：*考生答案：2考生得分：*是否评分：未评分评价描述：*50.（第五章）一棵高度为5的完全二叉树最多有个结点。试题编号：2.15.2试题类型：填空题标准答案：*试题难度：一般试题解析：*考生答案：64考生得分：*是否评分：未评分评价描述：*51.（第五章）如果一个完全二叉树的叶子结点个数为n，则这棵二叉树的总结点数为或。试题编号：2.16试题类型：填空题标准答案：*试题难度：一般试题解析：*考生答案：2n|2n-1考生得分：*是否评分：未评分评价描述：*52.（第五章）设某棵二叉树的中序遍历序列为ABCD，后序遍历序列为BADC，则其前序遍历序列为。试题编号：2.17试题类型：填空题标准答案：*试题难度：一般试题解析：*考生答案：CABD考生得分：*是否评分：未评分评价描述：*53.（第七章）已知一个有向图的邻接矩阵表示，计算第i个结点的度的方法是。试题编号：2.18试题类型：填空题标准答案：*试题难度：一般试题解析：*考生答案：求矩形第i行非元素之和考生得分：*是否评分：未评分评价描述：*54.（第七章）一个图的三种存储方法中，表示法是唯一的。试题编号：2.19.1试题类型：填空题标准答案：*试题难度：一般试题解析：*考生答案：邻接矩阵考生得分：*是否评分：未评分评价描述：*55.（第七章）一个图的三种存储方法中，和表示法是不唯一的。试题编号：2.19.2试题类型：填空题标准答案：*试题难度：一般试题解析：*考生答案：邻接表|边集数组考生得分：*是否评分：未评分评价描述：*56.（第七章）一个有n个顶点的无向连通图最少有条边。试题编号：2.20.1试题类型：填空题标准答案：*试题难度：一般试题解析：*考生答案：n-1考生得分：*是否评分：未评分评价描述：*57.（第七章）一个有n个顶点的无向连通图最多条边。试题编号：2.20.2试题类型：填空题标准答案：*试题难度：一般试题解析：*考生答案：n(n-1)/2考生得分：*是否评分：未评分评价描述：*58.（第八章）设一个连通图G中有n个顶点e条边，则其最小生成树上有条边。试题编号：2.21试题类型：填空题标准答案：*试题难度：一般试题解析：*考生答案：n-1考生得分：*是否评分：未评分评价描述：*59.（第十章）外排序是指在排序前后，数据在上，排序时数据调入内存进行的排序方法。试题编号：2.22试题类型：填空题标准答案：*试题难度：一般试题解析：*考生答案：外存考生得分：*是否评分：未评分评价描述：*60.（第十章）在选择排序、冒泡排序、归并排序中，排序是空间复杂度最大的。试题编号：2.23试题类型：填空题标准答案：*试题难度：一般试题解析：*考生答案：选择排序考生得分：*是否评分：未评分评价描述：*三、简答题(共10题，每题4分，共40分)请不要使用附件方式作答。61.（第二章）简述顺序表和链表存储方式的特点。顺序表的优点势可以随机访问数据元素；缺点是大小固定，不利于增减结点（增减操作需要移动元素）。链表的优点是采用指针方式增减结点，非常方便（只需要改变指针指向，不移动结点）。其缺点是不能进行随机访问，只能顺序访问；另外，每个结点上增加指针域，造成额外存储空间增大。 试题编号：3.1试题类型：简答题标准答案：*试题难度：一般试题解析：*考生答案：顺序表的优点势可以随机访问数据元素；缺点是大小固定，不利于增减结点（增减操作需要移动元素）。链表的优点是采用指针方式增减结点，非常方便（只需要改变指针指向，不移动结点）。其缺点是不能进行随机访问，只能顺序访问；另外，每个结点上增加指针域，造成额外存储空间增大。 考生得分：*是否评分：未评分评价描述：*62.（第二章） 在一个单链表HL中删除指针p所指结点，应执行如下关键操作： if(_) HL = HL-next; else q = HL; while(_) q = q-next; _; delete p; 请将代码补充完整。 1、p = HL 2、q-next != p 3、q-next = p-next; 或q-next = q-next-next; 试题编号：3.2试题类型：简答题标准答案：*试题难度：一般试题解析：*考生答案：1、p = HL 2、q-next != p 3、q-next = p-next; 或q-next = q-next-next; 考生得分：*是否评分：未评分评价描述：*63.（第四章） 以下2个问题基于下面的环形队列： 设环形队列Q7的当前状态如下， 写出队列Q的队空、队满定条件及进队、出队操作的的描述语句。 空：rear = front 满：(rear+1)%MaxSize = front 进队操作：rear = (rear+1)%MaxSize; Q(rear)=x 出队操作：front = (front+1)%MaxSize; X=Q(front) 试题编号：3.3试题类型：简答题标准答案：*试题难度：一般试题解析：*考生答案：空：rear = front 满：(rear+1)%MaxSize = front 进队操作：rear = (rear+1)%MaxSize; Q(rear)=x 出队操作：front = (front+1)%MaxSize; X=Q(front) 考生得分：*是否评分：未评分评价描述：*64.（第四章）画出元素a0,a1,a2出队，元素a4,a5,a6,a7进队后队列Q的状态。 试题编号：3.4试题类型：简答题标准答案：*试题难度：一般试题解析：*考生答案： 考生得分：*是否评分：未评分评价描述：*65.（第五章）写出下图这棵二叉树的前序遍历、中序遍历、后序遍历和层次遍历序列。 前序遍历：ABDFCEGH 中序遍历：BFDACGEH 后序遍历：FDBGHECA 层次遍历：ABCDEFGH 试题编号：3.5试题类型：简答题标准答案：*试题难度：一般试题解析：*考生答案：前序遍历：ABDFCEGH 中序遍历：BFDACGEH 后序遍历：FDBGHECA 层次遍历：ABCDEFGH 考生得分：*是否评分：未评分评价描述：*66.（第六章）已知一组元素为(30,46,62,27,32,49,13,45)，画出按元素排列顺序输入生成的一棵二叉搜索树，并写出在这棵二叉搜索树中查找元素49所需的元素比较次数。二叉搜索树如下图，查找 49所需比较次数为 4 试题编号：3.6试题类型：简答题标准答案：*试题难度：一般试题解析：*考生答案：二叉搜索树如下图，查找 49所需比较次数为 4 考生得分：*是否评分：未评分评价描述：*67.（第六章）给定权值6,7,12,10,30,25，构造相应的哈夫曼树，要求写出构造步骤，并计算该树的带权路径长度。答 构造的哈夫曼树为： 带权路径长度为：(30+25)*2 + (6+7+10+12)*3 = 215 试题编号：3.7试题类型：简答题标准答案：*试题难度：一般试题解析：*考生答案：答 构造的哈夫曼树为： 带权路径长度为：(30+25)*2 + (6+7+10+12)*3 = 215 考生得分：*是否评分：未评分评价描述：*68.（第