资源描述：
《华中科技大学计算机学院数据结构(计算机专业)试题》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、华中科技大学计算机学院《数据结构》试卷(A卷)2010—2011年度第二学期计算机学院班级______学号___________姓名_________考试时间：2011年月日考试形式：闭卷题号一二三四五六七八总分核对人题分101010123210610100得分得分评卷人一、单项选择题(从下列各题四个备选答案中选出一个正确答案,将其代号(A,B,C,D)写在下表中,每小题1分,共10分)题号12345678910答案1．对于栈的进栈和出栈运算，采用______存储结构时运算效率最高。A．单链表B．容量足够大的顺序表C．单
2、向循环链表D．双向循环链表2．链式队列和顺序队列比较，具有_____这个优势。A．进队操作方便B．出队操作方便C．通常不会出现满队列情况D．求队列元素个数方便3．下列关于串的叙述中，正确的是_____。A．2个串的长度相等，则2个串相等B．空串至少包一个空格C．替换操作可以实现字符的删除D．一个串的长度至少是14．二叉树在线索化后，下列问题中相对难解决的是____。A．先根线索二叉树中求先根后继B．中根线索二叉树中求中根前趋C．中根线索二叉树中求中根后继D．后根线索二叉树中求后根后继5．对序列（30，26，18，16，5
3、，66）进行2遍________排序后得到序列（5，16，18，26，30，66）。A．选择B．冒泡C．插入D．归并1010华中科技大学计算机学院6．在下列排序算法中，_______算法可能出现如下情况：在最后一趟排序之前，所有元素均不在其最终的位置上。A．堆排序B．快速排序C．冒泡排序D．插入排序7．由4个结点可以组成______棵不同形态的二叉树。A．10B．12C．14D．168．对包含n个元素的散列表进行检索，平均查找长度为____。A．O(logn)B．O(n)C．O(nlogn)D．不直接依赖于n9．广义表(
4、(a,(b),c),((),(d)),(((((e)),f))),())的长度是____。A．2B．3C．4D．510．对某无向图进行一次深度优先搜索遍历，如果能访问到所有的顶点，则该无向图一定是________。A．连通图B．树图C．有回路的连通图D．完全图得分评卷人二、填空题(在下表中填写正确的答案,每空1分,共10分)题号12345678910答案1．具有n个单元、用首尾指针、无标志位的循环队列中，队满时共有_______个元素。2．设顶点数为n，弧数为e的有向图的用邻接表存储，求顶点值为V的顶点的入度的算法时间复
5、杂度为_____。3．某哈夫曼树有11个结点，则它有____个度为2的结点。4．设森林T中有三棵树，第一、二、三棵树的结点个数分别是n1，n2，n3，那么当把森林转换成二叉树后，其根结点的右子树上有______个结点。5．当线性表经常进行插入和删除操作时，应该选择使用________存储结构。6．设栈S和队列Q的初始状态为空，元素a、b、c、d、e、f依次通过栈S，一个元素出栈后即进入队列Q。若这6个元素出队列的顺序是b、d、c、f、e、a，则栈S的容量至少应该是______。7．满足先根遍历序列为a、b、c，后根序列为
6、c、b、a的二叉树共有______棵。8．按广度优先搜索遍历图的算法需要借助的辅助数据结构是_____。9．高度为4的平衡二叉树至少有_____个结点。10．对n个元素的序列进行简单选择排序，最多进行______次元素的交换。1010华中科技大学计算机学院得分评卷人三、判断题(判断下列各题叙述的正确性,用√表示正确，×表示错误，每小题1分,共10分)题号12345678910答案1．可以以随机方式访问以三元组方式存放的稀疏矩阵的非零元素。2．对完全二叉树，如已知高度h和第h层的结点数，一定能求二叉树的结点数。3．算法分析
7、的目的之一是分析算法的效率以求改进。4．正确性是算法的特征之一。5．线性表的逻辑结构与存储顺序总是一致的。6．在循环链表中，任何一个结点的指针部分都指向其直接后继元素的结点。7．将递归算法改写成非递归算法时，通常需要使用的数据结构为栈。8．有n个顶点，n2-2n+2条弧的有向图不一定是强连通图。9．某二叉树的中根遍历序列得到的关键字序列是递增有序的，则该二叉树一定是二叉排序树。10．快速排序方法的每一趟都能找到一个元素把它放到最终的位置上。得分评卷人四、存储结构图(要求标明各结点的数据域、指针域、权值等，每小题6分，共1
8、2分)1．如下图所示为二叉树排序树T的一种线索二叉树逻辑结构图，试画出插入结点48后的线索二叉树的物理存储结构图。2．试画出如下图所示无向网的邻接多重表存储结构图。1010华中科技大学计算机学院得分评卷人五、求解问题(每小题8分，共32分)1．如下图所示为n行2n-1列矩阵A[1..n，1..2n-1]，现以行为主序
