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