2011-2012学年第二学期《数据结构与Java集合框架》试题.doc

《2011-2012学年第二学期《数据结构与Java集合框架》试题.doc》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、2011-2012学年第二学期期末考试《数据结构与Java集合框架》试题一、单项选择题（本题共15题，每小题2分，共30分）每题只有一个正确的答案，将答案填入下列的表格中：题号123456789101112131415答案1．以下数据结构中，（）是非线性数据结构。A.树B.字符串C.队D.栈2．下面算法的时间复杂度为（）intf(intn)if(n==0

2、

3、n==1)return1;elsereturnn*f(n-1);A.O(1)B.O(n)C.O(n2)D.O(n!)3．若某数据结构最常用的操作是存取任一指定序号的元素和在尾部进行插入和删除运算，则利

4、用（）存储方式最节省时间。A.ArrayB.双链表C.带头结点的双循环链表D.单循环链表4．非空的循环单链表的尾结点p满足（）。A.p.next==headB.p.next==nullC.p==nullD.p==head5．在单链表引用为p的结点之后插入引用为s的结点，正确的操作是（）A.p.setNext(s);s.setNext(p.next);B.s.setNext(p.next);p.setNext(s);C.p.setNext(s);p.setNext(s.next);D.p.setNext(s.next);p.setNext(s);6．有六个

5、元素6,5,4,3,2,1.顺序进栈。问下列哪一个不是合法的出栈序列？（）A.543612B.453126C.346521D.2341567．树最适合用来表示（）A.有序数据元素B.无序数据元素C.元素之间具有分支层次关系的数据D.元素之间无联系的数据3．下列叙述中，正确的是（）A．线性链表中的各元素在存储空间中的位置必须是连续的B．线性链表中的表头元素一定存储在其他元素的前面C．线性链表中的各元素在存储空间中的位置不一定是连续的，但表头元素一定存储在其他元素的前面D．线性链表中的各元素在存储空间中的位置不一定是连续的，且各元素的存储顺序也是任意的。4．

6、已知一棵二叉树前序遍历和中序遍历分别为ABDEGCFH和DBGEACHF，则该二叉树的后序遍历为（）A．GEDHFBCAB．DGEBHFCAC．ABCDEFGHD．ACBFEDHG10．下列关于栈的描述中错误的是（）　A、栈是先进后出的线性表　B、栈只能顺序存储　C、栈具有记忆作用　D、对栈的插入与删除操作中，不需要改变栈底引用11．对于长度为n的线性表，在最坏情况下，下列各排序法所对应的比较次数中正确的是（）A、冒泡排序为n/2B、冒泡排序为nC、快速排序为nD、快速排序为n(n-1)/212．栈和队列的共同特点是()。A.只允许在端点处插入和删除元素

7、B.都是先进后出C.都是先进先出D.没有共同点13．对于循环队列，下列叙述中正确的是（）A.队头引用是固定不变的B.队头引用一定大于队尾引用C.队头引用一定小于队尾引用D.队头引用可以大于队尾引用，也可以小于队尾引用14．下列数据结构中，能用二分法进行查找的是（）A、顺序存储的有序线性表B、线性链表C、二叉链表D、有序线性链表15．链表不具有的特点是（）A．不必事先估计存储空间           B．可随机访问任一元素C．插入删除不需要移动元素           D．所需空间与线性表长度成正比二、填空题（本题共20个空，每空1分，共20分）1．递归算

8、法一般需要利用实现。2．应用程序在执行过程中，需要通过打印机输出数据时，一般先形成一个打印作业，将其存放在硬盘中的一个指定中，当打印机空闲时，就会按照的方式从中取出待打印的作业进行打印。3.与单向链表相比，双向链表的优点之一是。4．数据结构分为与，线性链表属于。5．在一个长度为n的顺序表中第i个元素（1<=i<=n）之前插入一个元素时，需向后移动元素。6．向空队列中插入15，25，35和45.然后移除三个数据项，队列中剩下的数据项是。7．当线性表的元素总数基本稳定，且很少进行插入和删除操作，但要求以最快的速度存取线性表中的元素时，应采用存储结构。8．对于

9、一个栈作进栈运算时，应先判别栈是否为，作退栈运算时，应先判别栈是否为，当栈中元素为m时，作进栈运算时发生上溢，则说明栈的可用最大容量为。9．算法的特点为有穷性、、、输出、可行性。10.采用插入排序算法对数列“10,14,29,37,13”进行排序，第二趟的结果为。11．数据结构算法中，通常用时间复杂度和__________________两种方法衡量其效率。12、设数组A[m]为循环队列Q的存储空间，font为头引用，rear为尾引用，判定Q为空队列的条件。13．下面程序段的功能是实现冒泡排序算法，请在下划线处填上正确的语句。voidbubble(int

10、r[n]){for(i=1;i<=n-1;i++){for(exchange=0