计算机系《数据结构》试题2002.6.

《计算机系《数据结构》试题2002.6.》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、计算机系《数据结构》试题2002.6.班级姓名学号一、填空题（每空2分，共20分）1．归并排序算法的时间复杂性为。2．对于具有300个记录的文件，采用分块索引查找法查找，其中用二分查找法查找索引表，用顺序查找法查找块内元素，假定每块长度均为30个元素，则平均查找长度为。3．设某二叉树的前序和中序序列均为ABCDE，则它的后序序列是。4．Kruskal算法的功能是。5．用n个权构成Huffman树，该Huffman树有结点。6．要将失去平衡的二叉树转变为平衡二叉树，需进行操作。7．设源串S=“bcdcdcb”，模式串P=“cdcb”，按KMP算法进行模式匹配，当“S2S3S4

2、”=“P1P2P3”，而S5≠P4时，S5应与比较。8．下列算法的功能是在二叉排序树中查找关键字为key的结点，请完善。BiTreesearch(BiTreet,Keytypekey){p=t;while()if(p->data==key)break;elseif(p->data>key);else;return(p);}二、根据要求解答下列问题。（每小题4分，共20分）1．画出广义表D=(()，x，(a，(b，c)))的存储结构。62．画出下列图的邻接表。3．判断循环队列是否“满”，有哪两种方法？请写出判断表达式。4．判断有向图是否存在回路有哪些方法？试加以解释。5．设无

3、序序列为（49，38，66，98，76，12，25，50），试将该序列建立一个堆。6三．设一组关键字为（7，15，20，31，48，53，64，76，82，99），Hash函数H（key）=keymod11，Hash表表长m=11，用线性探测法解决冲突，试构造Hash表，并分别求出查找成功和查找失败情况下的平均查找长度。（12分）四、试编写一个算法对顺序表L中的数据进行快速排序的算法。（12分）6五、已知二叉树T的结点形式为leftdatarightbal其中，bal存储结点的平衡因子（bal=左子树高度-右子树高度），试编写一算法求树T中各结点的平衡因子。（12分）6六、

4、试编写对有向图进行拓扑排序的算法。（12分）6七、分别写出顺序栈、循环队列、二叉链表、邻接表的类型定义。（12分）6