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

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

1、2011-2012学年第二学期期末考试《数据结构与Java集合框架》试题（补考）一、单项选择题（本题共15题，每小题2分，共30分）每题只有一个正确的答案，将答案填入下列的表格中：题号123456789101112131415答案1．以下数据结构中，（）是非线性数据结构。A.树B.字符串C.队D.栈2．若让元素1,2,3依次进栈，则出栈次序不可能出现________种情况。A.3,2,1B.2,1,3C.3,1,2D.1,3,23．非空的循环单链表的尾结点p满足（）。A.p.next==headB.p.ne

2、xt==nullC.p==nullD.p==head4．下列叙述中，正确的是（）A．线性链表中的各元素在存储空间中的位置必须是连续的B．线性链表中的表头元素一定存储在其他元素的前面C．线性链表中的各元素在存储空间中的位置不一定是连续的，但表头元素一定存储在其他元素的前面D．线性链表中的各元素在存储空间中的位置不一定是连续的，且各元素的存储顺序也是任意的。5．线性链表不具有的特点是________。A.随机访问B.不必事先估计所需存储空间大小C.插入与删除时不必移动元素D.所需空间与线性表长度成正比6．栈的插

3、入和删除操作在＿＿＿进行．A．栈顶　B．栈底C．任意位置D.指定位置7．在一个顺序循环队列中，队首指针指向队首元素的________位置。A.后两个B.后一个C.当前D.前一个8．下列关于栈的描述中错误的是（）　A、栈是先进后出的线性表　B、栈只能顺序存储　C、栈具有记忆作用　D、对栈的插入与删除操作中，不需要改变栈底引用9．在单链表引用为p的结点之后插入引用为s的结点，正确的操作是（）A.p.setNext(s);s.setNext(p.next);B.s.setNext(p.next);p.setNex

4、t(s);C.p.setNext(s);p.setNext(s.next);D.p.setNext(s.next);p.setNext(s);10．队列操作的原则是(A)A.先进先出B.后进先出C.只能进行插入D.只能进行删除11．对于循环队列，下列叙述中正确的是（）A.队头引用是固定不变的B.队头引用一定大于队尾引用C.队头引用一定小于队尾引用D.队头引用可以大于队尾引用，也可以小于队尾引用12．下列数据结构中，能用二分法进行查找的是（）A、顺序存储的有序线性表B、线性链表C、二叉链表D、有序线性链表13

5、．栈和队列的共同特点是()。A.只允许在端点处插入和删除元素B.都是先进后出C.都是先进先出D.没有共同点14．链式栈与顺序栈相比，一个比较明显的优点是________。A.插入操作更加方便B.通常不会出现栈满的情况C.不会出现栈空的情况D.删除操作更加方便15．链表不具有的特点是（）A．不必事先估计存储空间           B．可随机访问任一元素C．插入删除不需要移动元素           D．所需空间与线性表长度成正比二、填空题（本题共20个空，每空2分，共40分）1．某带头结点的单链表的头指针h

6、ead，判定该单链表非空的条件____________。2．若频繁地对线性表进行插入与删除操作，该线性表应采用____________存储结构。3．在非空线性表中除第一个元素外，集合中每个数据元素只有一个_______；除最后一个元素之外，集合中每个数据元素均只有一个_________。4．应用程序在执行过程中，需要通过打印机输出数据时，一般先形成一个打印作业，将其存放在硬盘中的一个指定中，当打印机空闲时，就会按照的方式从中取出待打印的作业进行打印。5．数据结构分为与，线性链表属于。6．在一个长度为n的顺序

7、表中第i个元素（1<=i<=n）之前插入一个元素时，需向后移动元素。7．在双向链表中，每个结点含有两个指针域，一个指向______结点，另一个指向________结点。8．向空队列中插入15，25，35和45.然后移除三个数据项，队列中剩下的数据项是。9．算法的特点为有穷性、、、输出、可行性。10、栈结构允许进行删除操作的一端为_____________。11．当线性表的元素总数基本稳定，且很少进行插入和删除操作，但要求以最快的速度存取线性表中的元素时，应采用存储结构。12.采用插入排序算法对数列“10,1

8、4,29,37,13”进行排序，第二趟的结果为。13．数据结构算法中，通常用______________和空间复杂度两种方法衡量其效率。14．在栈的顺序实现中，栈顶引用top，栈为空条件______________。三、判断题（本题共10题，每小题1分，共10分。对打“√”，错的打“×”）1．线性表的逻辑顺序与物理顺序总是一致的。()2．线性表的顺序存储表示优于链式存储表示。()3．线性表中的每个结点最多只有一个