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

《北大2015年秋季学期《数据结构》课程作业》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、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算法中的每个步骤都能

2、在有限时间内完成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;i

3、O(n*n)c.O(m*n)d.O(m*logn)5.下列有关线性表的叙述中，正确的是____A____。（第二章）a一个线性表是n个数据元素的有限序列b线性表中任何一个元素有且仅有一个直接前驱c线性表中任何一个元素有且仅有一个直接后继d以上说法都不正确6.在含有n个结点的顺序存储的线性表中，在任一位置插入一个结点所需移动结点的平均次数为___B___（第二章）a．nb．n/2c．(n+1)/2d．(n-1)/2第１１页共8页7.链表不具备的特点是______D___。（第二章）a不必事先估计存储空间b插入删除不需要移动元素c可

4、顺序访问任一结点d所需空间与其长度无关8.带附加头结点的双循环链表L为空表的条件是_______C_____。（第二章）aL==NULLbL->next==NULLcL->prior==LdL->prior==NULL9.设广义表L=（（a,b,c））,则L的长度与深度分别为___D_________。（第三章）a1和1b1和3c2和3d1和210.若栈采用链式存储结构,则下面的说法中正确的是____A____（第四章）a.不需要判断栈满但需要判断栈是否为空b.需要判断栈是否栈空与栈满c.需要判断栈满但不需要判断栈空d.栈满栈空

5、都不需要判断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

6、]存放其元素值，已知其头尾指针分别是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____（第四章）第１１页共8页a．AB+D*E/FA+*DC+b．ABD*+EFAD*+/C+

7、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.如果一棵二叉树的先序遍历序列和后序遍历

8、序列正好相反，则该二叉树满足的条件是____B___。（第五章）a空或只有一个结点b高度等于其结点数c任一结点无右孩子d任一结点无左孩子21.树的基本遍历策略分为先根遍历和后根遍历；二叉树的基本遍历策略可分为先序遍历、中序遍历和后序遍历。结论_______A__