简述武汉理工大学考试试题（B卷）.doc

武汉理工大学考试试题（B卷） 课程名称 数据结构 专业班级 题号 一 二 三 四 五 六 七 八 九 十 总分 题分 20 10 10 40 20 100 填空题（每空2分，共20分） 1．数据结构的研究的内容包括：数据的＿＿＿＿，数据的＿＿＿＿及数据的＿＿＿＿ 。 2．链式存储结构中，指针字段中只有一个指针的线性表称为＿＿＿＿。 3．对于队列，只能在＿＿＿插入元素，在＿＿＿删除元素。 4．当线性表很少做插入删除操作时，应采用＿＿＿＿存储结构为好。 5．内部排序的方法有＿＿＿＿和＿＿＿＿等。 6．在二叉树第h层上最多有＿＿＿＿个结点。 二、单项选择题（每小题1分，共20分） 1． 将长度为m的单链表接在长度为n的单链表之后的算法的时间复杂度为： A．O（m+n） B.O(n) C.O(m) D.(m*n) 2. 在一个具有10个顶点的有向图中，所有顶点的入度之和与所有顶点的出度之和的差为： A．10 B.20 C. 0 D.5 3．一个线性表第一个元素的存储地址是100,每个元素的长度是2,则第5个元素的地址是: A. 110 B. 108 C. 100 D. 120 4． 在具有n（nl）个结点的完全二叉树中，结点i（2i＞n）的左孩子结点______。 A．是2i B．是2i＋l C．不存在 D．是2i-l 5．在一个单链表中，已知Q所指结点是P所指结点的前趋结点，若在Q和P之间插入S结点，则执行： A．Q－＞next = S; S－＞next = P; B．P－＞next = S; S－＞next = Q; C．S－＞next = P－＞next; P－＞next = S; D．P－＞next = S－＞next; S－＞next = P; 6． 对二叉树从1开始进行连续编号，要求每个结点的编号大于其左右孩子的编号，同一个结点的左 右孩子中，其左孩子的编号小于其右孩子的编号，则可采用（ ）次序的遍历实现编号。 A．先序 B. 中序 C. 后序 D. 从根开始的层次遍历 7．二分查找要求结点______。 A．有序、顺序存储 B．有序、链接存储 C．无序、顺序存储 D．无序、链接存储 8．进栈序列是1234,下列哪个出栈序列不可能出现 A. 1432 B. 2431 C. 3142 D. 3421 9．设有100个元素，用折半查找法进行查找时，最大比较次数是______。 A．25 B．50 C．10 D．7 10．在下列排序方法中，______是不稳定的排序方法。 A．直接插入排序 B．简单选择排序 C．起泡排序 D．归并排序 三、问答题（每小题5分，共10分） 1．什么是算法？算法分析的目的是什么？算法分析主要涉及哪两个主要方面的内容？ 2．请简述广义表与线性表的区别？ 四、图表计算题（每小题8分，共40分） 1．已知某二叉树的结点的后序序列是BDC, 中序序列是BDAEGF。（1）画出该二叉树，（2）求前序遍历序列。以{20,13,24,37,90,53,12}构造二排序叉树，并进行中序遍历。 3 2 2 5 4 3 6 7 4 9 8 5 9 10 8 6 11 7 12 8 9 9 10 10 11 11 12 12 ^ 五、算法设计题（10分） 以顺序表为存储结构，在300000个任意排序的数据中选择前100个最大值。 以二叉链为存储结构，写一算法求二叉树的叶子结点个数。 试题标准答案及评分标准用纸 | 课程名称 数据结构 （ B 卷） 一、填空题（每空2分，共20分） 1．逻辑结构 存储结构 运算 2. 单链表 3. 队尾 队首 4. 顺序表 5．直接插入排序、简单选择排序、起泡排序、快速排序、基数排序、归并排序、堆排序中任选2种 6. 2h-1 二、单选题（每小题1分，共10分） 1.B 2.C 3. B 4.C 5. A 6.C 7.A 8. C 9. D 10.B 三、问答题（每小题5分，共10分） 1. 算法是解决给定问题的一种方法（策略），即为解决某一特定问题而由若干条指令组成的有