数据结构考题学习资料

《数据结构》试题（闭卷）（电信系本科2006级2008年1月）班级：____________姓名：______________学号：_____________题号一二三总分题分403030100得分得分得分一、回答下列问题(每题5分，共40分)1．某算法的空间花费s(n)=100n*log2n+0.5*n1.1+2000*n+5000，其空间复杂度是多少？2．冒泡排序在最好情况下时间复杂度是多少？3．对于一个具有n个结点的二叉树，若采用递归中序遍历，在什么情况下其辅助空间最大，辅助空间大小是多少？在什么情况下其辅助空间最小，辅助空间大小是多少？4．由1000个结点构成的完全二叉树，层次最大和次最大一层的叶子结点数分别是多少？5．给定25个结点的有序序列，建立二叉排序树，在等概率查找情况下二叉排序树其平均查找长度是多少？若采用折半查找方法进行查找，求出在等概率查找情况下其平均查找长度。6．设一模式串为“aabbccsabbccdbcv”，求其NEXT函数，NEXT函数值的大小与模式向右移动的距离有什么关系？7．给定序列(56，67，35，96，72，21，28，48)，给出初始堆。8．如果一个空栈的进栈序列为ABCDEFGHIJ，则出栈序列ABCDGEFHJI是否存在？如果存在，请说明进栈和出栈过程。9．对于一个有n个顶点的有向图，如果有n(n-1)条边，则这个图是完全有向图吗？为什么？10．给定6个字符（A，B，C，D，E，F），权值为（5，3，2，9，11，7），画出Huffman树。得分二、综合题（4小题，共32分）得分1．下图为一个图的逻辑结构ABＣDEFGH从下列答案中选择出正确的遍历结果深度优先搜索=1\*GB3①ABEFCGDH=2\*GB3②ACGBFEDH=3\*GB3③ADGCHBEF广度优先搜索=1\*GB3①ABDCFEHG=2\*GB3②ACDBHGEF=3\*GB3③ADCBHGEF请画出邻接矩阵（10分）2．已知待排序列为（86，53，31，22，16，05，03），用快速排序得到非递减序列，请完成以下工作：（10分）分别对序列写出第一、第二趟划分的结果，第一个元素为枢轴写出完成整个排序的关键字的比较次数如果递减序列有n个元素，快速排序的时间、空间复杂度是多少？如何改进？3．已知hash函数：H(k)=3kmod11(mod表示取余)，采用下列方法解决冲突：Hi=(H(k)+di)mod11，其中d1=1;di+1=(7di＋3)mod11(i>1)，请对下列线性表（6，8，10，17，20，23，53，41，54，57）构造一个长度为11的hash表，并求此表的平均查找长度ASL。（10分）得分得分三、算法设计题（3题，共30分）1．已知二叉树有n个结点，以顺序存储结构存放，试用类C语言设计算法计算树的深度。（10分）2．下面是某同学“树”这一章的作业，设计算法实现某种功能，其中p是二叉树的根节点，没有任何注释。请分析此算法的功能是什么？该算法是否正确？如不正确，分析不正确的原因，并给出正确算法的基本思路（不需用类c写出算法）（10分）Booleanabc(Bitreep){ifp==NULLreturn(TRUE);if(p->lchild==NULL)and(p->rchild!=NULL)return(FALSE)elsereturn(abc(p->lchild)andabc(p->rchild)