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分)