湖南大学数据结构试卷.pdf

考试中心填写： 年 月 日 湖南大学课程考试试卷 考 试 用 课程名称： 数据结构 ；试卷编号： A ；考试时间：120 分钟 题 号 一 二 三 四 五 六 七 八 九 十 总 分 应得分 10 10 50 30 100 实得分 评分： 评卷人 得 一、填空题（每空 1 分，共 10 分） 分 ： 级 班 1、在具有n 个单元的循环队列中，队满时共有 个元素。 业 专 2、假设在有序线性表a[20]上进行折半查找，则比较3 次查找成功的结点数为 。 装 3、对有序数组进行二分查找的时间复杂度为 。 订 线 （ 4、设栈S 和队列Q 的初始状态为空，元素E1、E2、E3、E4、E5 和E6 依次通过栈S，一个元 答 题 素出栈后即进入队列Q，若6 个元素出列的顺序为E2、E4、E3、E6、E5 和E1，则栈S 的容量 不 至少应该是 。 得 超 过 5、当待排序的记录数较大，排序码较随机且对稳定性不作要求时，宜采用 排序。 此 线 ） 6、一棵结点数为N 的二叉树，其所有结点的度的总和是 。 ： 号 学 7、设一棵二叉树的前序遍历序列和中序遍历序列均为 ABC ，则该二叉树的后序遍历序列 为 。 ： 姓 名 8、散列法存储的基本思想是由 决定数据的存储地址。 9、对不带权图进行 遍历可求得单源最短路径。 10、设一个连通图G 中有n 个顶点e 条边，则其最小生成树上有 条边。 第 1 页（共4 页） 得 二、单选题（每小题 1 分，共 10 分，本题所给四个答案中只有一个是正确的） 分 1、若已知一个栈的入栈序列是1，2，3，…，n，其输出序列为p1，p2，p3，…，pn，若p1=n，则 pi 为（ ） （Ａ）i （Ｂ）n=i （Ｃ）n-i+1 （Ｄ）不确定 2、线性表若采用链式存储结构时，要求内存中可用存储单元的地址: （ ） （A）必须是连续的 （B）部分地址必须是连续的 （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、具有n(n0)个结点的完全二叉树的深度为（ ）。 (Ａ) log (n) (Ｂ) log (n) (Ｃ) log (n)+1 (Ｄ) log (n)+1 2