数据结构试题A.doc

山东农业大学课程考试专用2008 -2009 学年第 2 学期 数据结构 试题（卷）A课程代码 BB002016 考试方式 闭卷 考试时长 100分钟姓名 学号 教学班号 专业 级 班题 号一二三四五六七八合计满 分1016341624100得 分阅卷人得分一、选择题：（10分，每题1分） 1算法的时间复杂度取决于（ ）A问题的规模 B. 待处理数据的初态 C. A和B2. 除第一层外，满二叉树中每一层结点个数是上一层结点个数的（ ）A2倍 B一半 C相同 D不能确定3已知串S=aabb,其Next数组值为（ ）A0123 B0113 C0111 D01214. 快速排序在最坏情况下的时间复杂度是（ ） A. O(n2log2n) B.O(n2) C. O(nlog2n) D. O(log2n) 5能进行折半查找的线性表 , 必须以（ ） A顺序方式存储,且元素按关键字有序 B链式方式存储 , 且元素按关键字有序 C顺序方式存储,且元素按关键字分块有序 D.链式方式存储,且元素按关键字分块有序 6.循环队列sq中，用数组elem0.25存放数据元素，sq.front指示队头元素的前一个位置，sq.rear指示队尾元素的当前位置，设当前sq.front为20，sq.rear为12，则当前队列中的元素个数为（ ）A.8 B.16C.17 D.187含有10个结点的二叉树中，度为0的结点数为4，则度为2的结点数为（ ） A.3 B.4C.5 D.68可以惟一地转化成一棵一般树的二叉树的特点是（ ）A.根结点无左孩子 B.根结点无右孩子C.根结点有两个孩子 9.排序算法中，第一趟排序后，任一元素都不能确定其最终位置的算法是（ ）A.选择排序 B.快速排序C.冒泡排序 D.插入排序10.有n个结点的有向完全图的弧数是（ ）A.n2 B.2nC.n(n-1) D.2n(n-1) 得分二、填空题：（16分，每空2分）1. 设二叉树中每个结点均用一个字母表示，若一个结点的左子树或右子树为空，用 表示，现前序遍历二叉树，访问的结点的序列为ABD.G.CE.H.F，则中序遍历二叉树时，访问的结点序列为_ _;后序遍历二叉树时，访问的结点序列为_ _。2. 从有序表（12，18，30，43，56，78，82，95）中依次折半搜索元素82时，其搜索长度为_.3. 一个连通图的生成树是该图的 连通子图。若这个连通图有n个顶点，则它的生成树有 条边。4. 用广义表的取表头 head 和取表尾 tail 的运算，从广义表 LS=(b,c,(f),(d) 中分解出原子 c 的操作为 _ _ 。5. 3 阶 B_树的根结点至少含有 _ 个关键字。6. 假设以行优先顺序存储三维数组 R696 ，其中元素 R000 的地址为 2100 ，且每个元素占 4 个存储单元，则存储地址为 2836 的元素是_.得分三、构造题（34分）1. 给定一组数据8，3， 6，11，5，18 以它构造一棵哈夫曼树，并计算带权路径长度（4分）。2. 对下边的无向加权图，按Prim算法求其最小生成树（从V1出发），并给出构造最小生成树过程中辅助数组的各分量值（6分）561v154v2v536v35v第2题图YClosedgeV2v3v4v5 U V.-U 输出adjVexLowcostadjVexLowcostadjVexLowcostadjVexLowcostadjVexLowcostadjVexLowcost3. 对于下面的有向无环图，写出它的四个不同的拓扑有序序列。（4）712846354. 设哈希(Hash)表的地址范围为018，哈希函数为：H (K)=K MOD 17, K为关键字，用线性探测再散列法处理冲突，输入关键字序列: (10,24,32,17,31,35,46,47,42,63,59)造出哈希表，试回答下列问题： (1) 画出哈希表示意图； （5分）(2) 若查找关键字63，需要依次与哪些关键字比较?（3分）(3) 假定每个关键字的查找概率相等，求查找成功时的平均查找长度。（2分）(1)散列地址0123456789101112131415161718关键字比较次数(2)(3) 5. 设有一个关键码的输入序列 5， 33， 18， 7， 46， 73， 3， 22，44，23 ，从空树开始构造平衡二叉搜索树，画出每加入一个新结点时二叉树的形态。若发生不平衡，指明需做的平衡旋转的类型及平衡旋转的结果。(5分)6. 给出一组关键字T=(12,2,16,30,8,28,4,10,20,6,18),写出用下列算法从小到大排序时第一趟结束时的序列（只写出最终的结果）； （1） 希尔排序（第一趟排序的增量为5） （2分）（2） 堆排序（3分）得分三、算法阅读（16分）1读下面的算法，分析算法所实现的功能。（注：链表是递增有序的、带头节点的、非空的单链表，L是单链表的头指针）（6分）algothm (Linklist &L,int a, int b) p=L;while(p-next &p-next-datanext;if(p-next)q=p-next;while(q-datanext;p-next=q; 2.算法填空：将二叉树bt中每一个结点的左右子树互换的算法如下，其中ADDQ(Q,bt),DELQ(Q),EMPTY(Q)分别为进队，出队和判别队列是否为空的函数，请填写算法中得空白处，完成其功能。（每空2分）typedef struct nodeint data ;struct node *lchild, *rchild; btnode; void EXCHANGE(btnode *bt)btnode *p, *q;if (bt)ADDQ(Q,bt); while(!EMPTY(Q)p=DELQ(Q); q=_ _;p-rchild=_ _;_ _=q;if(p-lchild) _;if(p-rchild) _; 得分四、算法设计（24分）（一）定义一个单链表类，链表中结点的数据类型为整型，该类的基本操作包括：1. 创建一个带头节点的递增有序的单链表 2. 把元素递增排列的链表A和B合并为C,且C中元素递减排列,使用原空间。（二）在一棵以二叉链表表示的二叉树上，试写出用按层