《08数据结构试卷A (1)》由会员分享，可在线阅读，更多相关《08数据结构试卷A (1)（5页珍藏版）》请在金锄头文库上搜索。
1、课程名称数据结构专业班级信计06级题号二三四五六七八九十总分题分备注：学生不得在试题纸上答题（含填空题、选择题等客观题）、判断题（每小题2分，共20分）1. 数据的存贮结构是数据的逻辑结构的存贮映象。2. 用顺序表来存储线性表时，不需要另外开辟空间来保存数据元素之间的相互关系。3. 队列是一种插入与删除操作分别在表的两端进行的线性表，是一种先进后出型结构。4. 栈和队列的存储方式既可是顺序存储，也可是链式存储。5. 完全二叉树的某结点若无左孩子，则它必是叶子结点。6. 一棵赫夫曼树中不存在度为1的结点。7. 任何有向图的顶点都可以按拓扑排序。8. 平衡二叉排序树上任何一个结点的左、右子树的高度
2、之差的绝对值不大于1。9. 哈希表查找无需进行关键字的比较。10. 快速排序在最差情况下的时间复杂度是O（n2）,此时它的性能并不比冒泡排序更好。二、选择题（每小题3分，共15分）1. 对一个算法的评价，不包括如下（）方面的内容。A.健壮性和可读性B.并行性C.正确性D.时间和空间复杂度2. 若进栈序列为1，2，3，4,则不可能得到的出栈序列是（）A.3,2,1,4B.3,2,4,1C.4,2,3,1D.2,3,4,13. 在一个长度为n（n1）的单链表上，设有头和尾两个指针，执行（）操作与链表的长度有关。A.删除单链表中的第一个元素。B.删除单链表中的最后一个元素。C.在单链表第一个元素前插
3、入一个新元素。D.在单链表最后一个元素后插入一个新元素4. 对一棵有100个结点的完全二叉树按层编号，则编号为49的结点，它的父结点的编号为（）A.24B.25C.98D.995. 排序算法中，第一趟排序后，任一元素都不能确定其最终位置的算法是（）A.选择排序B.快速排序C.冒泡排序D.插入排序三、填空题(每小题3分，共21分)1. 在具有n个单元的循环队列中，队满时共有个元素。2. 在双循环链表中，删除指针P所指结点的语句序列。3. 一棵二叉树有67个结点，这些结点的度要么是0，要么是2。这棵二叉树中度为2的结点有个。4. 二叉排序树是一种特殊的有序表，若要保证输出序列其键值完全按递增排列，
4、则应对二叉排序树采用遍历。5. n个顶点的有向完全图具有条弧。6. 对于n个元素的数据序列，在等概率情况下采用顺序查找法，其平均查找长度为。7. 已知二叉树按先序遍历所得到的结点序列为ABCDEF,按中序遍历所得到的结点序列为CBAEDF,则叶子结点为。四、应用题(每小题9分，共36分)1. 阅读算法，回答下列问题：voidDivide(inta，intn)low=0;high=n-1;while(lowhigh)while(low=0)high-;alowv-ahigh;while(lowhigh&alow0)low+;alowahigh;/Divide(1) 指出该算法的功能；(2) 求出
5、该算法的时间复杂度；(3) 并讨论算法中记录的最大移动次数。2. 请画出后序和中序序列相同的二叉树的所有形态。3. 给定关键字序列32，13,49,55,22，38,21，其散列函数为H(k)=k%7，散列表的地址从0到6,用线性探查法解决冲突。(1)构造散列表(只画出表，不写算法)；(2)求出平均查找长度。4. 简述如何根据不同的实际情况和要求选择不同的排序算法。五、算法设计题(8分)已知连通图G以邻接矩阵为存储结构，其顶点个数是G.vexnum,试用类c语言编写图的深度优先遍历算法，并分析其时间复杂度。武汉理工大学教务处试题标准答案及评分标准用纸课程名称数据结构(A卷)一、判断题(每小题2
6、分，共20分)1、对2、对3、错4、对5、对6、对7、错8、对9、错10、对二、选择题(每小题3分，共15分)1、B2、C3、B4、A5、D三、填空题(每小题3分，共21分)1、n-12、p-prior-next=p-next;p-next-prior=p-prior;3、334、中序5、n(n-1)6、(n+1)/2或3(n+1)/47、CEF四、应用题(每小题9分，共36分)1、(1)将数组中的负数调到非负数之前3分6分(2) 只需对数组扫描一遍即可，故时间复杂度为O(n)(3) 最坏情况下：负数都位于非负数之后，需将负数与非负数对换，故记录的最大移动次9分数为n/22、中序遍历：LDR后
7、序遍历：LRD2分由中序遍历和后序遍历一致，则应该是LD,任一个结点没有右孩子O5分9分2分0123456哈希表为：495522383221135分3、32%7=4，13%7=6，49%7=0，55%7=6，22%7=1，38%7=3，21%7=0查找32，13，49，38需比较一次，查找22需比较两次，查找55需比较3次，查找21需比较6次8分故平均查找长度为：(1*4+2*1+3*1+6*1)/7=15/79分4、排序算法主要有简单排序、快速排序、堆排序、归并排序、基数排序。1分(1) 从平均性能而言，快速排序最佳，其所需时间最省，但快速排序在最坏情况下的时间性能不如堆排序和归并排序，在n
8、较大时，归并排序所需时间较堆排序省，但它所需的辅助存储量最多。3分(2) “简单排序”包括除希尔排序之外的所有插入排序，起泡排序和简单排序，其中直接插入排序最简单，当序列中的记录“基本有序”或n较小时，它是最佳排序方法，因此常将它和其他的排序方法，诸如快速排序、归并排序等结合在一起使用。5分(3) 基数排序的时间复杂度为O(d*n),适用于n很大而关键字较小的序列。若关键字也很大，而序列中大多数记录的“最高位关键字”均不同，则也可按“最高位关键字”不同将序列分成若干“小”的子序列，而后进行直接插入排序。7分(4) 从方法的稳定性来比较，基数排序是稳定的内排方法，所有时间复杂度为O(n2)的简单排序法也是稳定的，然而，快速排序、堆排序和希尔排序等时间性能较好的排序方法都是不稳定的。9分五、算法设计题(8分)voidDFS(GraphG,intv)/从顶点v出发，深度优先遍历Gvisitedv=TRUE;VisitFunc(v);1分for(w=FirstAdjVex(G,v);w!=0;w=NextAdjVex(G,v,w)3分f(!visitedw)DFS(Gw);/对v的尚未访问的邻接顶点w递归调用DFS/DFS6分用邻接矩阵来表示图，遍历图中每一个顶点都要从头扫描该顶点所在行，因此遍历8分全部顶点所需的时间为O(n2)。
