哈工大数据结构2001.docVIP

哈尔滨工业大学 二00一 年研究生考试试题 考试科目：数据结构 报考专业：计算机科学与技术 填空（总分：10分，每一题2分） 对于一个具有n个结点的单链表，在已知的结点*p后插入一个新结点的时间复杂度为________, 在给定为x的结点后插入一个新结点的时间复杂度为________。 广义表（a，（a，b），d，e，( (I,j,), k) ）的长度是________, 深度是________。 对于一个具有n个结点的二员树，当它为一棵________二元树时具有最小高度，当它为一棵_______时，具有最大高度。 在顺序文件中，要存取第I个记录，必须先存取______个记录。 求最短路径的dijkstra算法的时间复杂度为________。 二．选择填空：（总分10分，每小题2分） 若某线性表最常用的操作是存取任意指定序号的元素和最后进行插入和删除运算，则利用______存储方式最节省时间。 顺序表； （2）双链表； 头结点的双循环链表； 单循环链表 在一棵三元树中度为3的结点数为2个，度为2的结点数为1个，度为1的结点数为2个，则度为0的结点数为______个 （1）4 （2）5 （3）6 （4）7 在一个图中，所有顶点的度数之和等于所有边数______倍，在一个有向图中，所有顶点的入度之和等于所有顶点出度之和的_____倍 1/2 （2）2 （3）1 （4）4 下列排序算法中，________,排序在某趟结束后不一定能选出一个元素放到其最终的位置上。 （1）选择 （2）冒泡 （3）归并 （4）堆 散列文件使用散列函数将记录的关键字值计算转化为记录的关键字值计算转化为记录的存放地址，因为散列函数是一对一的关系，则选择好的_______方法是散列文件的关键。 （1）散列函数 （2）除余法中的质数 （3）冲突处理 （4）散列函数和冲突处理 三 回答下列问题 （总分15分，每小题3分） 数据结构与数据类型有什么区别？ 什么是循环队列？ 简述线索二元树的概念。 何为有向图的遍历？ 什么是索引顺序文件？ 四．分别画出和下列树对应的各个二元树。 五．试设计一个算法，判断链表L是否是递减的。 六．判断以下序列是否为堆，如果不是，则把它调整为堆。 (12,24,33,65,33,56,48,92,86,70) (25,56,20,23,40,38,29,61,35,76,28,100) 七．设有两个栈S1,S2都采用顺序栈方式，并且共享一个存储区[O…maxsize-1],为了尽量利用空间，减少溢出的可能，可采用栈顶相向，迎面增长的存储方式。试设计S1,S2有关入栈和出栈的操作算法。 八．假设用于通讯的电文仅有6个字母abcdef组成，字母在电文中出现的频率分别为7，19，5，16，42，11。试为这6个字母设计哈夫曼编码 九．试写一算法，判断以邻接表方式存储的有向图中是否存在有顶点Vi到顶点Vj的路 （ij）。注意：算法中涉及的图的基本操作必须在存储结构上实现。