武汉理工大学数据结构试题.docx

《武汉理工大学数据结构试题.docx》由会员分享，可在线阅读，更多相关《武汉理工大学数据结构试题.docx（5页珍藏版）》请在三一文库上搜索。

1、武汉理工大学考试试题(B卷)课程名称数据结构_专业班级题号-二二-三四五六七八九十总分题分2010104020100一、填空题(每空2分，共20分)1数据结构的研究的内容包括：数据的，数据的及数据的2链式存储结构中，指针字段中只有一个指针的线性表称为。3 对于队列，只能在插入元素，在删除元素。4 当线性表很少做插入删除操作时，应采用存储结构为好。5内部排序的方法有和等。6在二叉树第h层上最多有个结点。、单项选择题(每小题1分，共20分)1将长度为m的单链表接在长度为n的单链表之后的算法的时间复杂度为：2. A0(m+r)B.O(n)C.0(m)D.(m*n)在一个具有10个顶点的有向图中，所有

2、顶点的入度之和与所有顶点的出度之和的差为：A.10B.20C.0D.53一个线性表第一个元素的存储地址是100,每个元素的长度是2,则第5个元素的地址是4. A.110B.108C.100D.120在具有n(nI)个结点的完全二叉树中，结点i(2in)的左孩子结点。A.是2iB.是2i+l5 C.不存在D.是2i-l在一个单链表中，已知Q所指结点是P所指结点的前趋结点，若在Q和P之间插入S结点，则执行：A.Qnext=S;Snext=P;B.Pnext=S;Snext=Q;A.先序B.中序7.二分查找要求结点。A.有序、顺序存储C.无序、顺序存储C.Snext=Pnext;Pnext=S;D.

3、Pnext=Snext;Snext=P;6.对二叉树从1开始进行连续编号，要求每个结点的编号大于其左右孩子的编号，同一个结点的左右孩子中，其左孩子的编号小于其右孩子的编号，则可采用()次序的遍历实现编号。C.后序D.从根开始的层次遍历B.有序、链接存储D.无序、链接存储&进栈序列是1234,下列哪个出栈序列不可能出现9设有100个元素，用折半查找法进行查找时，最大比较次数是。A25B.50C.10D.710.在下列排序方法中，是不稳定的排序方法。1. A.直接插入排序B.简单选择排序C.起泡排序D.归并排序三、问答题（每小题5分，共10分）什么是算法？算法分析的目的是什么？算法分析主要涉及哪两

4、个主要方面的内容？2. 请简述广义表与线性表的区别？1. 四、图表计算题（每小题8分，共40分）已知某二叉树的结点的后序序列是BDCGFEA,中序序列是BCDAEGF。（1）画出该二叉树，（2）求前序遍历序列。2. 以20,13,24,37,90,53,12构造二排序叉树，并进行中序遍历。3. 以2,5,8,10,14,25,36构造haffman树，并求带权路径长度。4. 对下列数据表，写出采用基数排序算法排序的每一趟的结果。5. （60,820,331,1,125,44,545,761,200,308,806,150,4,29）图G的邻接表如下，求出其拓扑序列。1322.541367498

5、5910k8611712J899101011111212A1. 五、算法设计题（10分）以顺序表为存储结构，在300000个任意排序的数据中选择前100个最大值。2. 以二叉链为存储结构，写一算法求二叉树的叶子结点个数。试题标准答案及评分标准用纸|课程名称数据结构（B卷）一、填空题（每空2分，共20分）1逻辑结构存储结构运算单链表队尾队首4顺序表任选2种5直接插入排序、简单选择排序、起泡排序、快速排序、基数排序、归并排序、堆排序中6. h-12二、单选题（每小题1分，共10分）1.B2.C3.B4.C5.A6.C7.A8.C9.D10.B三、问答题（每小题5分，共10分）1. 算法是解决给定问

6、题的一种方法（策略），即为解决某一特定问题而由若干条指令组成的有穷序列。（2分）算法分析的目的是研究算法执行时间随问题规模变化的情况（问题规模是一个和输入有关的量，如n）,提高算法的效率。（1分）2. 算法分析主要涉及：时间复杂度和空间复杂度。（2分）线性表（a1,a2,an）中每个元素都具有相同的类型，它有两种存储结构：顺序表和链表。广义表（d1,d2,，dn）中每个元素可以是原子，也可以是子表。可以将广义表看作是线性表的推广。由于原子和子表的类型不同，所以只能用链式存储结构。四、图表计算题（每小题8分，共40分）中序堀历序列：丄乙1220f37.S3,90訂序踞历序列ACBDEFG3.构造的哈夫曼树如图所示:2. WPL-(2+5)4+(8+10+14)3+(25+36)12-24第一趟：060,820,200,150,331,001,761,044,004,125,545,806,308,029第二趟：200,001,004,806,308,820,125,029,331,044,545,150,060,7613. 第三趟：001,004,029,044,060,125,150,200,308,331,545,761,806,820其拓扑序列如下：I2458910376II12五、算法设计题略20分)