资源描述：
《数据结构试题A.doc》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、山东农业大学课程考试专用2008-2009学年第2学期《数据结构》试题（卷）A课程代码BB002016考试方式闭卷考试时长100分钟姓名 学号 教学班号 专业级班题号一二三四五六七八合计满分1016341624100得分阅卷人得分一、选择题：（10分，每题1分）1．算法的时间复杂度取决于（）A．问题的规模B.待处理数据的初态C.A和B2.除第一层外，满二叉树中每一层结点个数是上一层结点个数的（ ）A．2倍B．一半C．相同D．不能确定3．已知串S=‘aabb’,其Next数组值为（）A．012
2、3B．0113C．0111D．01214.快速排序在最坏情况下的时间复杂度是（ ）A.O(n2log2n)B.O(n2)C.O(nlog2n)D.O(log2n)5．能进行折半查找的线性表,必须以（ ）A．顺序方式存储,且元素按关键字有序B．链式方式存储,且元素按关键字有序C．顺序方式存储,且元素按关键字分块有序D.链式方式存储,且元素按关键字分块有序6.循环队列sq中，用数组elem［0...25］存放数据元素，sq.front指示队头元素的前一个位置，sq.rear指示队尾元素的当前位置，设
3、当前sq.front为20，sq.rear为12，则当前队列中的元素个数为（ ）A.8B.16C.17D.187．含有10个结点的二叉树中，度为0的结点数为4，则度为2的结点数为（ ）A.3B.4C.5D.68．可以惟一地转化成一棵一般树的二叉树的特点是（ ）A.根结点无左孩子B.根结点无右孩子C.根结点有两个孩子9.排序算法中，第一趟排序后，任一元素都不能确定其最终位置的算法是（ ）A.选择排序B.快速排序C.冒泡排序D.插入排序10.有n个结点的有向完全图的弧数是（ ）A.n2B.2nC.n
4、(n-1)D.2n(n-1)注：考试期间试卷不允许拆开。第8页共8页山东农业大学课程考试专用得分二、填空题：（16分，每空2分）1.设二叉树中每个结点均用一个字母表示，若一个结点的左子树或右子树为空，用．表示，现前序遍历二叉树，访问的结点的序列为ABD.G...CE.H..F．．，则中序遍历二叉树时，访问的结点序列为___;后序遍历二叉树时，访问的结点序列为___。2.从有序表（12，18，30，43，56，78，82，95）中依次折半搜索元素82时，其搜索长度为_________.3.一个连通
5、图的生成树是该图的连通子图。若这个连通图有n个顶点，则它的生成树有条边。4.用广义表的取表头head和取表尾tail的运算，从广义表LS=(b,c,(f),((d)))中分解出原子c的操作为_________。5.3阶B_树的根结点至少含有_________个关键字。6.假设以行优先顺序存储三维数组R[6][9][6]，其中元素R[0][0][0]的地址为2100，且每个元素占4个存储单元，则存储地址为2836的元素是_________.得分三、构造题（34分）1.给定一组数据{8，3，6，11
6、，5，18}以它构造一棵哈夫曼树，并计算带权路径长度（4分）。注：考试期间试卷不允许拆开。第8页共8页山东农业大学课程考试专用1.对下边的无向加权图，按Prim算法求其最小生成树（从V1出发），并给出构造最小生成树过程中辅助数组的各分量值（6分）561v154v2v536v35v第2题图YClosedge V2 v3 v4 v5 U V.-U 输出adjVexLowcost adjVexLowcost adjVexLowcost adjVexLowcost
7、 adjVexLowcost adjVexLowcost2.对于下面的有向无环图，写出它的四个不同的拓扑有序序列。（4）71284635注：考试期间试卷不允许拆开。第8页共8页山东农业大学课程考试专用1.设哈希(Hash)表的地址范围为0～18，哈希函数为：H(K)=KMOD17,K为关键字，用线性探测再散列法处理冲突，输入关键字序列:(10,24,32,17,31,35,46,47,42,63,59)造出哈希表，试回答下列问题：(1)画出哈希表示意图；（5分）(2)若查找关
8、键字63，需要依次与哪些关键字比较?（3分）(3)假定每个关键字的查找概率相等，求查找成功时的平均查找长度。（2分）(1)散列地址0123456789101112131415161718关键字比较次数(2)(3)5.设有一个关键码的输入序列{5，33，18，7，46，73，3，22，44，23}，从空树开始构造平衡二叉搜索树，画出每加入一个新结点时二叉树的形态。若发生不平衡，指明需做的平衡旋转的类型及平衡旋转的结果。(5分)注：考试期间试卷不允许拆开。第8页共8页山东农业大学课程考试专用6.给出
