资源描述：
《05-06安徽大学数据结构试卷》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、安徽大学2005-2006学年第1学期《数据结构》期末考试试卷（A卷）一、单项选择（在备选答案中选出一个正确答案，并将其号码填在题后的括号内。每题2分，共20分）01．以下序列不是堆的是()。A.(100,85,98,77,80,60,82,40,20,10,66)B.(100,98,85,82,80,77,66,60,40,20,10)C.(10,20,40,60,66,77,80,82,85,98,100)D.(100,85,40,77,80,60,66,98,82,10,20)02．当采用分快查找时，数据的组织方式为()A．数据分成若
2、干块，每块内数据有序B．数据分成若干块，每块内数据不必有序，但块间必须有序，每块内最大（或最小）的数据组成索引块C．数据分成若干块，每块内数据有序，每块内最大（或最小）的数据组成索引块D．数据分成若干块，每块（除最后一块外）中数据个数需相同03.二叉树中序序列为A,B,C,D,E,F,G，后序序列为B,D,C,A,F,G,E则前序序列是()A．E,G,F,A,C,D,BB．E,A,C,B,D,G,FC．E,A,G,C,F,B,DD．以上答案都不对04.有n个叶子的哈夫曼树的结点总数为（）。A．2n-1B．2nC．2n+1D．不确定05.有一
3、个具有n个顶点的连通图生成的最小生成树中,具有()条边A、nB、n-1C、n+1D、2n-106.下面的二叉树中，（ ）不是平衡二叉树。A B C D07.知U=‘xyxyxyxxyxy’；t=‘xxy’；依次执行下列运算后，ASSIGN（S，U）；ASSIGN（V，SUBSTR（S，INDEX（s，t），LEN（t）+1））；ASSIGN（m，‘ww’），则REPLACE（S，V，m）结果为()。A．’xyxywwyxy’B．’xyxyxywwy’C．’xyxyxwwxy’D．’xyxyw
4、wxyx’.08.设有数组A[i,j]，数组的每个元素长度为5字节，i的值为0到5，j的值为0到6，数组从内存首地址BA开始顺序存放，当用以行为主序存放时，元素A[5，5]的存储首地址为()。A.BA+180B.BA+175C.BA+200D.BA+20509.依次读入数据元素序列{a,b,c,d,e,f}进栈,每进一个元素机器可要求下一个元素进栈和出栈.如此进行,则栈空时弹出的元素构成的序列不可能出现()A、{c,d,b,e,f,a}B、{d,c,e,b,f,a}C、{b,d,c,e,a,f}D、{b,e,d,a,c,f}10.从具有n个
5、结点的二叉排序树中查找一个元素时,在最坏情况下的时间复杂度为()A、0(n)B、0(1)C、0(logn)D、O(n²)二、填空题（每空2分，共20分） 1.与链式存储结构不同，顺序存储结构是通过________表示元素之间的逻辑关系的。2.若二叉树采用二叉链表存储结构，要交换其所有分支结点左、右子树的位置，利用遍历方法最合适。3.在完全二叉树中，编号为i和j的两个结点处于同一层的条件是______。共6页，第13页4.对于17个元素的有序表A[1]-A[17]作二分查找,在查找其等于A[8]的元素时需比较_____次.5.树
6、的三种存储结构是双亲表示法、孩子表示法和。6.若不考虑基数排序，则在内部排序过程中，主要进行的两种基本操作是关键字的比较和记录的。7.一个“好”的算法要考虑以下标准：正确性、可读性、 和效率与低存储量需求。8.已知一个无向图的邻接表如下图所示:则从顶点1出发进行深度优先搜索遍历得到的顶点序列为_____________和广度优先搜索得到的顶点序列为_______________。9.在含有n个结点的二叉链表中，其空链域个数是。第二题，第8小题图三、分析计算题（1、3、5每题8分,2题6分,4题10分，共40分）1．对于如下的连通图，请给
7、出从顶点0出发，利用普里姆（Prim）算法求出它的最小生成树的过程中得到的顶点集和边集及最小生成树的权，并画出所得到的最小生成树。40511268151361641292010235（第三大题第1题图）2．设F={T1，T2，T3}是森林（如下图所示），试将它转换为二叉树，画出所对应的二叉树。GHIJKEDCFBAT1T2T3森林（第三大题第2题图）3.记录的关键字集合K={23，9，39，5，68，12，62，48，33}，请给出采用快速排序法进行排序时每趟划分后的排序结果（选第一个记录为枢轴（支点）分割）。4．给定关键字序列15,38,
8、61,84,49,60,71,33,24,29,36，试分别用顺序查找、二分查找、二叉排序树查找、散列查找(其中，散列函数H(k)=k%11，用线性探查法和拉链法来解决冲突)共6
