安工大数据结构试卷(带完整答案)

………………………………装………………………………订…………………………………线………………………………课程________________________班级________________________姓名__________________________学号________________________………………………………密………………………………封…………………………………线………………………………安徽工业大学试题纸（一）安徽工业大学2012~2013学年第二学期期末考试《数据结构》试卷(A)一、单项选择题（110=10分）1、在数据结构中，从逻辑上可以把数据结构分为（C）。(A)动态结构和静态结构(B)紧凑结构和非紧凑结构(C)线性结构和非线性结构(D)内部结构和外部结构2.设某棵二叉树的中序遍历序列为ABCD，前序遍历序列为CABD，则后序遍历该二叉树得到序列为（A）。(A)BADC(B)BCDA(C)CDAB(D)CBDA3.将10阶对称矩阵压缩存储到一维数组A中，则数组A的长度最少为（C）。(A)100(B)40(C)55(D)804.设顺序循环队列Q[0：M-1]的头指针和尾指针分别为F和R，头指针F总是指向队头元素的前一位置，尾指针R总是指向队尾元素的当前位置，则该循环队列中的元素个数为（C）。(A)R-F(B)F-R(C)(R-F+M)％M(D)(F-R+M)％M5.设某棵三叉树中有40个结点，则该三叉树的最小高度为（B）。(A)3(B)4(C)5(D)66.设某强连通图中有n个顶点，则该强连通图中至少有（C）条边。(A)n(n-1)(B)n+1(C)n(D)n(n+1)7.设有5000个待排序的记录关键字，如果需要用最快的方法选出其中最小的10个记录关键字，则用下列（B）方法可以达到此目的。(A)快速排序(B)堆排序(C)归并排序(D)插入排序8.若某线性表中最常用的操作是取第I个元素和找第I个元素的前趋元素，则采用（D）存储方式最节省时间。（A）单链表(B)双链表（C）单向循环(D)顺序表9.设某无向图中有n个顶点e条边，则该无向图中所有顶点的入度之和为（D）。(A)n(B)e(C)2n(D)2e10.设有序表中有1000个元素，则用二分查找查找元素X最多需要比较（B）次。(A)25(B)10(C)7(D)1二、填空题（每空格1分，共17分）1.数据的物理结构主要包括__连续存储结构____和___非连续存储结构____两种情况。2.设一棵完全二叉树中有500个结点，则该二叉树的深度为_____9_____；若用二叉链表作为该完全二叉树的存储结构，则共有______501_____个空指针域。3.设输入序列为1、2、3，则经过栈的作用后可以得到____5_______种不同的输出序列。4.设哈夫曼树中共有99个结点，则该树中有____50_____个叶子结点；若采用二叉链表作为存储结构，则该树中有__100___个空指针域。5.设一棵完全二叉树的顺序存储结构中存储数据元素为ABCDEF，则该二叉树的中序遍历序列为_____DBEAFC______。题号一二三四五六七八九十十一十二十三十四十五十六十七十八十九二十总分得分………………………………装………………………………订…………………………………线………………………………课程________________________班级________________________姓名__________________________学号________________________………………………………密………………………………封…………………………………线………………………………安徽工业大学试题纸（二）6．设F和R分别表示顺序循环队列的头指针和尾指针，则判断该循环队列为空的条件为_______F==R______________。7．设二叉树中结点的两个指针域分别为lchild和rchild，则判断指针变量p所指向的结点为叶子结点的条件是_______p-lchild==NULL&&p-rchild==NULL______________________________________。8．简单选择排序和直接插入排序算法的平均时间复杂度为_____O(n^2)______。9．快速排序算法的空间复杂度平均情况下为____O(log2n)______，最坏的情况下为____O(n^2)______。10.散列表中解决冲突的两种方法是______开放地址法_______和___链地址法__________。11．平衡因子是指____左子树的深度减去右子树的深度____________________________________。12．数组A[0..6,0..8]的每个元素占4个字节，将其按行优先次序存储在起始地址为2000的内存单元中，元素A[5,6]的地址是_____2204________。三、应用题。（共35分）1．已知8个待排序的记录，其关键码分别为53，36，30，91，47，12，24，85，用希尔排序、快速排序和堆排序对其进行排序，写出第一趟排序后结果。(9分)答：希尔排序：1224309147533685(步长为5)快速排序：2436301247539185小堆排序：12365385473024912．假定有字符a1，a2，a3，a4，a5在一篇文章中出现的次数分别为{{3,2,4,5,1}}试以它们为叶子结点构造哈夫曼树，并计算WPL(8分)答：见三、2图WPL=（3+4+5）*2+（1+2）*3=333．已知广义表L=(a,(b,c),(d,e)),试画出其存储结构图并利用取头函数head和取尾函数tail求出原子e。((6分)答：见三、3图e=head(tail(head(tail(tail(L))))4．（共6分）设有下列带权无向图：请用PRIM求该图的一棵最小生成树。答：见三、4图5.设一棵二叉树的先序序列为ABDGECFH，中序序列为：DGBAECHF。试画出该二叉树。(6分)答：见三、5图四、判断题（1*10`=10分）1、顺序表结构适宜于进行顺序存取，而链表适宜于进行随机存取。（错）2、两个栈共享一片连续内存空间时，为提高内存利用率，减少溢出机会，应把两个栈的栈底分别设在这片内存空间的两端。。（对）3、一个栈的输入序列是12345，则栈的输出序列不可能是12345。（错）4、串是一种数据对象和操作都特殊的线性表。（对）5、数组可看成线性结构的一种推广，因此与线性表一样，可以对它进行插入，删除等操作。（错）6、对于一棵非空二叉树，它的根结点作为第一层，则它的第i层上最多能有2i-1个结点。（错）7、最小代价生成树是唯一的。（错）8、归并排序的空间复杂度为O(n)（对）9、为了方便操作，一般在二叉树排序树中插入一个新结点，总是作为叶结点。（对）10、在初始数据表已经有序时，快速排序算法的时间复杂度为O(nlog2n)。（错）五、编写算法（28分）1、试编写算法将两个有序的单链表归并成一个新的有序单链表。（10分）linklistMerge(linklistA,linklistB)/*将有序单链表合并后由函数带回*/答：LinkListMerge(LinkListA,LinkListB){LinkListp,q,r;p=A;q=B-next;while(p){if(q-next-dtatp-data){r=q;r-next=p-next;p-next=r;q=q-next;}else{p=p-next;q=q-next;}if(!p&&q)p=q;returnA;}2、试编写算法计算二叉树中度为1的结点数。（9分）intcount(bintreet)/*求二叉链表结构二叉树t度为1的结点数*/答:intcount(bintreet){intcount=0;PSeqStackS;bintreep=t;S=Init_SeqStack();while(p||Empty_SeqStack(S)){if(p){Push_SeqStack(S,p);p=p-lichild;}else{Pop_SeqStack(S,&p);if(((p-lchild!=NULL)&&(p-rchild==NULL))||((p-lchild==NULL)&&(p-rchild!=NULL)))count++;p=p-rchild;}}returncount;}3、试编写算法在二叉排序树T中查找值为X的算法。（9分）BinSTreeBSTSearch(BinSTreet,KeyTypeX,)/*二叉排序树T中查找值为X的算法*/答：BinStreeBSTSerach(BinSTreet,KeyTypeX){while(t){if(t-key==X)returnt;if(t-keyX)t=t-lchild;elset=t-rchild;}returnNULL;}三、2图三、3图三、4图三、5图