2012贵州大学数据结构A卷(共5页).doc
精选优质文档-倾情为你奉上贵州大学2011-2012学年第二学期考试试卷 A数据结构注意事项：1. 请考生按要求在试卷装订线内填写姓名、学号和年级专业。2. 请仔细阅读各种题目的回答要求，在规定的位置填写答案。3. 不要在试卷上乱写乱画，不要在装订线内填写无关的内容。4. 满分100分，考试时间为120分钟。题 号一二三四总 分统分人得 分得 分评分人一、单项选择题（共20分,每小题2分）1不是四类基本逻辑结构之一的是（ ）A、集合B、链表结构C、树形结构D、网状结构2关于队列的描述，错误的是（ ）A、队列的头指针指下一个入队的位置B、普通队列要求满足“先进先出”C、使用一个队列可以模拟一个银行的多个同性质服务窗口的排队状况D、循环队列可以采用顺序表实现3在n个结点的顺序表中，算法的时间复杂度是O（1）的操作是 （ ）A、访问第i个结点（1in）和求第i个结点的直接前驱（2in）B、在第i个结点后插入一个新结点（1in）C、删除第i个结点（1in）D、将n个结点从小到大排序4下列关于串的叙述中，正确的是（ ）A、一个串的字符个数即该串的长度B、一个串的长度至少是1C、空串是由一个空格字符组成的串D、两个串S1和S2若长度相同，则这两个串相等5稀疏矩阵一般的压缩存储方法有两种，即（ ）A、二维数组和三维数组B、三元组和散列C、三元组和十字链表D、散列和十字链表6按照二叉树的定义,具有3个结点的二叉树有（ ）A、3种B、4种C、5种B、6种7不是图的存储结构的是 （ ）A、邻接多重表B、十字链表C、关联矩阵 D、可利用空间表8在关于动态存储管理，错误的说法是（ ）A、未被占用的连续地址空间称为空闲块B、可利用空间表一般采用链表C、针对内存申请块的大小范围较广时，应该采用首次拟合法D、针对内存申请块的大小较均匀时，应该采用最差拟合法9理想情况下，速度最快的查找结构的是（ ）A、分块索引B、二叉排序树C、二叉平衡树D、哈希表10. 关于各种排序方法，错误的说法是（ ）A、关键字大小相同的记录，排序后先后顺序不改变，则称为此排序为稳定的B、内部排序算法的性能由关键字比较次数和记录移动次数决定C、冒泡排序的时间复杂度为O(nlogn)D、堆排序使用的堆对应一棵完全二叉树得 分评分人二、概念填空题（共20分,每空2分）1若使用伙伴系统进行动态存储管理，若申请32个字，选中的空闲块有128个字，则这个空闲块会被分裂为_个块（最小块大小可以为4）。2在逻辑上相关的元素，在物理存储地址上不一定相邻，两种不同的存储结构分别称为：_存储结构和_存储结构。3快速排序在最坏情况下算法复杂度为_；在哈希表中，不同关键字得到相同哈希地址称为_。4数据结构可以形式化定义为一个二元组，Data_Structure=(D，S)，其中D是_的集合，S是_的集合。5进行深度优先搜索需要用到辅助数据结构是_。 6已知中缀表达式为(a+b)/(c-d)，对应的前缀表达式为_。7稀疏矩阵的行链表存储中，每行单链表的结点具有相同的_。得 分评分人三、数据操作和表示题（共40分,每小题5分）1 设待排序记录集合的关键字为（45,27,18,67,13,76,38,90,27,25），采用希尔排序算法，间隔增量d分别取5、3、1，请写出第一趟和第二趟希尔排序之后的结果。 2从一棵空的平衡二叉树开始，将以下关键码值依次插入：41,27,10,65,45,36,29，请画出插入每一个元素且调整平衡之后的平衡二叉树。3. 画出用Prim算法求出下图的最小生成树4画出下面稀疏矩阵的三元存储法表示。（行列下标从1开始）5顺序栈初始状态如下左图所示，经过入下入队和出队操作之后，请在右图中画出栈内容、top和base所指。操作顺序为：元素A、B相继压栈；然后出栈一个元素；又有元素C、 D、E入栈；然后出栈两个元素； 6已知一棵二叉树的先序遍历为：A B F D F F C E F F F G F F F，其中F表示叶子结点，请画出这棵二叉树。7假定一组记录的关键字为50,27,16,67,14,36,38,29,26,24，采用HASH表存储，HASH地址空间为HT15，若采用除留余数法构造HASH函数h(key)=key mod 13，用线性再探测法处理冲突，线性再探测序列为1,2,3,4,5n，请画出最后得到的HASH表，求出平均查找长度。8. 使用Floyd算法求出下图中顶点之间的最短路径，请填写求解过程邻接矩阵和路径矩阵。DD(0)D(1)D(2)D(3)ABCABCABCABCA0000B0000C0000PP(0)P(1)P(2)P(3)ABCABCABCABCA-B-C-得 分评分人四、程序题（共20分,每题10分）1请完成如下函数：void BInsertSort(SqList &L)/对顺序表L作折半插入排序for (i=2;i<=L.length;+i)_;/设置观察哨L.r0left=1;_right=_;/设置搜索范围while(left <=right)_;/计算折半位置if (LT(L.r0.key, L.rm.key) _;/向左折半elseleft=m+1;/向右折半for (j=i-1;j>=right+1;-j) _;/向后移动记录L.rright+1=L.r0;/插入2. 请用代码定义出有向图的邻接矩阵的有关数据结构，然后此基础上实现图的广度优先遍历（注意：不要求实现图的输入和输出，只需实现遍历函数,访问结点时输出该结点的顶点编号即可）。专心-专注-专业
