北大2016秋季学期《数据结构》课程作业.doc

..WORD完美格式.. PAGE ..专业知识编辑整理.. 2015年秋季学期《数据结构》课程作业 一. 单选题，每空有一个正确选择，请将正确的选择填在题号前边。（每空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___（第一章） 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____。（第二章） a 一个线性表是 n 个数据元素的有限序列 b 线性表中任何一个元素有且仅有一个直接前驱 c 线性表中任何一个元素有且仅有一个直接后继 d 以上说法都不正确 6.在含有n个结点的顺序存储的线性表中，在任一位置插入一个结点所需移动结点的平均次数为___B___（第二章） a．n b．n/2 c．(n+1)/2 d．(n-1)/2 7.链表不具备的特点是______D___。（第二章） a不必事先估计存储空间 b 插入删除不需要移动元素 c 可顺序访问任一结点 d 所需空间与其长度无关 8.带附加头结点的双循环链表L为空表的条件是_______C_____。（第二章） a L==NULL b L-next==NULL c L-prior==L d L-prior==NULL 9.设广义表L=（（a,b,c））,则L的长度与深度分别为___D_________。（第三章） a 1和1 b 1和3 c 2和3 d 1和2 10. 若栈采用链式存储结构,则下面的说法中正确的是____A____（第四章） a.不需要判断栈满但需要判断栈是否为空 b.需要判断栈是否栈空与栈满 c.需要判断栈满但不需要判断栈空 d.栈满栈空都不需要判断 11. 在一个链栈中，已知s为栈顶指针（直接指向栈顶元素结点，无头结点），t为栈底指针，直接指向栈底元素，则插入r结点的操作为_____B_______。 （第四章） 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___（第四章） a. 1, 2, 3, 4, 5, 6 b. 3, 2, 6, 4, 5, 1 c. 2, 4, 6, 5, 3, 1 d. 6, 5, 4, 3, 2, 1 13. 循环队列用数组A[0..m-1]存放其元素值，已知其头尾指针分别是front和rear，则当前队列中的元素个数是_____A_______。（第四章） a (rear-front+m)%m b rear-front+1 c rear-front-1 d rear-front 14.栈和队列的共同特点是______A____。（第四章） a.只允许在端点处插入和删除元素 b.都是先进后出 c.都是先进先出 d.没有共同点 15.中缀表达式(A+B)*D+E/(F+A*D)+C的后缀形式是__D____（第四章） a．AB+D*E/