2005—2006学年第二学期考卷A.doc

第页

华东交通大学2005—2006学年第二学期考试卷承诺：我将严格遵守考场纪律，知道考试违纪、作弊的严重性，还知道请他人代考或代他人考者将被开除学籍和因作弊受到记过及以上处分将不授予学士学位，愿承担由此引起的一切后果。
专业班级学号学生签名：题号一二三四五六七八九总分分数评卷人试卷编号：_______(A)卷
数据结构课程课程类别：必闭卷（√）、：
考生注意事项：1、本试卷，总分100分，考试时间120分钟。
2、考试结束后，考生不得将试卷、答题纸和草稿纸带出考场。
所有答案必须写到答题纸上，写到试卷上无分
一、选择填空题（选择每空1分，填空每空2分共30分）
得分评阅人1.一个以整数为栈元素的栈，若元素进栈的次序A，B，C，D出栈可以发生在任何时刻，则下面的序列中，哪一个是不可能的出栈序列？（）
A.A,B,C,DB.D,C,B,AC.D,C,A,BD.A,B,D,C
2.下列陈述中正确的是()。
A.二叉树是度为2的有序树。
B.二叉树中结点只有一个孩子时无左右之分。
C.二叉树中必有度为2的结点。
D.二叉树中最多只有两棵子树，并且有左右之分。
3..在单链表中，指针p指向元素为x的结点，实现“删除x的后继”的语句是()
A.p=p->next;B.p->next=p->next->next;
C.p->next=p;D.p=p->next->next;
4..在头指针为head且表长大于1的单循环链表中，指针p指向表中某个结点，若p->next->next=head则()
A.p指向头结点B.p指向尾结点
C.*p的直接后继是头结点D.*P的直接后继是尾结点
5.串的长度是指（）。
A.串中不同字符的个数。
B.串中不同字母的个数。
C.串中所含字符的个数且字符个数大于0。
D.串中所含字符的个数。
6.已知二叉树的先序序列为ABDECF，中序序列为DBEAFC，则后序序列为
()

7.栈和队列的共同特点是_________.
(A)都是先进后出（B）都是先进先出
（C）没有共同点（D）只允许在端点处插入和删除
8.若一棵二叉树具有10个度为0的结点，则该二叉树度为2的结点个数是（）。(B)
A.9B.11C.12D.不确定
9.数据结构包括数据的________________即数据之间的相互关系和数据的________________即数据结构在计算机中的表示。
10.在如图所示的链表中，若在指针p所指的结点之后插入数据域值相继为a和b的两个结点，则可用下列两个语句实现该操作，它们依次是________________________(q->next->next=p->next)和________________________(p->next=q)。
q
b
a
….
p
第10题图

二．简答画图题（共64分）

A.DEBAFCB.DEFBCAC.DEBCFAD.DEBFCA
7.请指出在顺序表{2、5、7、10、14、15、18、23、35、41、52}中，用二分法查找关键码12需做多少次关键码比较。（）A、2B、3C、4D、5
8.对于只在表的首、尾两端进行插入操作的线性表，宜采用的存储结构为()。
A.顺序表B.用头指针表示的单循环链表
C.用尾指针表示的循环链表D.单链表
9.一棵高度为5的二叉树中最少含有_________个结点，最多含有________个结点；
10.具有n个结点的二叉树在用二叉链表作为存储结构时,有_______个空指针域.
11._______的特点是数据结构中元素的存储地址与其关键字之间存在某种映射关系。
A．树形存储结构B．链式存储结构C．索引存储结构D．散列存储结构
12.字符串f=‘你好’的长度为多少.
13.按照四则运算加、减、乘、除和幂运算（^）优先关系的惯例写出下列算术表达式A-B*(C-D/H)+F^E求值时操作数栈和运算符栈最多的时候栈内各有几个元素：操作数栈运算符栈。
14.在一个索引文件的索引表中，每个索引项包含对应记录的_________和___________两项数据。
15.表长为13的哈希表中已填有关键字为23，46，69,28的记录，用除留余数法构造哈希函数现有第5，6个记录，其关键字为35，39按二次探测再散列的方法处理冲突，将它填入表中相应的位置。

第15题图

二．简答画图题（共64分）
得分评阅人16.已知关键字序列为49，38，65，97，76，13，27，48，55，4，请对其进行一趟希尔排序，写出排序的过程。（5分）
17.有a,b,c,d,e,f,g,h,I,9个结点，其权值分别为w={5,29,7,8,14,23,1,10,3}，试：
构