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

华东交通大学2005—2006学年第二学期考试卷 承诺：我将严格遵守考场纪律，知道考试违纪、作弊的严重性，还知道请他人代考或代他人考者将被开除学籍和因作弊受到记过及以上处分将不授予学士学位，愿承担由此引起的一切后果。 专业 班级 学号 学生签名： 题号 一 二 三 四 五 六 七 八 九 总 分 分数 评卷人 试卷编号：_______ ( A )卷 数据结构 课程 课程类别：必 闭卷（√）、： 考生注意事项：1、本试卷共 4页，总分　100　分，考试时间　120　　分钟。 2、考试结束后，考生不得将试卷、答题纸和草稿纸带出考场。 所有答案必须写到答题纸上，写到试卷上无分 一、选择填空题（选择每空1分，填空每空2分共30分） 得分 评阅人 1. 一个以整数为栈元素的栈，若元素进栈的次序A，B，C，D出栈可以发生在任何时刻，则下面的序列中，哪一个是不可能的出栈序列？（ ） A. A,B,C,D B.D,C,B,A C. D,C,A,B D.A,B,D,C 2. 下列陈述中正确的是( )。 A.二叉树是度为2的有序树B.二叉树中结点只有一个孩子时无左右之分C.二叉树中必有度为2的结点D.二叉树中最多只有两棵子树，并且有左右之分.在单链表中，指针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. 串的长度是串中不同字符的个数串中不同字母的个数串中所含字符的个数且字符个数大于0串中所含字符的个数 6. 已知二叉树的先序序列为ABDECF，中序序列为DBEAFC，则后序序列为 ( ) 7.栈和队列的共同特点是_________. (A) 都是先进后出 （B）A. 9 B. 11 C. 12 D. 不确定 9. 数据结构包括数据的________________ 即数据之间的相互关系和数据的________________即数据结构在计算机中的表示。 10.在如图所示的链表中，若在指针p所指的结点之后插入数据域值相继为a和b的两个结点，则可用下列两个语句实现该操作，它们依次是________________________和________________________。 二．简答画图题（共64分） A.DEBAFC B.DEFBCA C.DEBCFA D.DEBFCA 7. 请指出在顺序表{2、5、7、10、14、15、18、23、35、41、52}中，用二分法查找关键码12需做多少次关键码比较。 （ ）A、2 B、3 C、4 D、5 对于只在表的首、尾两端进行插入操作的线性表，宜采用的存储结构为( )。 A.顺序表 B.用头指针表示的单循环链表C.用尾指针表示的循环链表 D.单链表 一棵高度为 5 的二叉树中最少含有 _________ 个结点，最多含有 ________ 个结点；n个结点的二叉树在用二叉链表作为存储结构时,有_______个空指针域. 11. _______的特点是数据结构中元素的存储地址与其关键字之间存在某种映射关系。A．树形存储结构　B．链式存储结构　C．索引存储结构　D．散列存储结构f = ‘你好’的长度为多少 . 13.按照四则运算加、减、乘、除和幂运算（^）优先关系的惯例写出下列算术表达式A-B*(C-D/H)+F^E求值时操作数栈和运算符栈最多的时候栈内各有几个元素：操作数栈 运算符栈 。 14. 在一个索引文件的索引表中，每个索引项包含对应记录的 _________ 和 ___________ 两项数据。 二．简答画图题（共64分） 得分 评阅人 16. 已知关键字序列为49，38，65，97，76，13，27，48，55，4，请对其进行一趟希尔排序，写出排序的过程。a, b, c, d, e, f, g, h ,I,9个结点，其权值分别为 w = {5, 29