|
哈尔滨工业大学 2001 年数据结构考研试题
考试科目：数据结构 报考专业：计算机科学与技术
一． 填空（总分：10 分，每一题 2 分）
1． 对于一个具有 n 个结点的单链表，在已知的结点*p 后插入一个新结点的时
间复杂度为________, 在给定为 x 的结点后插入一个新结点的时间复杂度为
________。
2． 广义表（a，（a，b），d，e，( (I,j,), k) ）的长度是________, 深度
是________。
3． 对于一个具有 n 个结点的二员树，当它为一棵________二元树时具有最小高
度，当它为一棵_______时，具有最大高度。
4． 在顺序文件中，要存取第 I 个记录，必须先存取______个记录。
5． 求最短路径的 dijkstra 算法的时间复杂度为________。
二．选择填空：（总分 10 分，每小题 2 分）
1．若某线性表最常用的操作是存取任意指定序号的元素和最后进行插入和删除
运算，则利用______存储方式最节省时间。
（1） 顺序表； （2）双链表；
（3） 头结点的双循环链表；
（4） 单循环链表
2． 在一棵三元树中度为 3 的结点数为 2 个，度为 2 的结点数为 1 个，度为 1
的结点数为 2 个，则度为 0 的结点数为______个
（1）4 （2）5 （3）6 （4）7
3． 在一个图中，所有顶点的度数之和等于所有边数______倍，在一个有向图中，
所有顶点的入度之和等于所有顶点出度之和的_____倍
（1） 1/2 （2）2 （3）1 （4）4
4． 下列排序算法中，________,排序在某趟结束后不一定能选出一个元素放到
其最终的位置上。
（1）选择 （2）冒泡 （3）归并 （4）堆
5．散列文件使用散列函数将记录的关键字值计算转化为记录的关键字值计算转
化为记录的存放地址，因为散列函数是一对一的关系，则选择好的_______方法
是散列文件的关键。
（1）散列函数 （2）除余法中的质数
（3）冲突处理 （4）散列函数和冲突处理
三 回答下列问题 （总分 15 分，每小题 3 分）
1 数据结构与数据类型有什么区别？
2 什么是循环队列？
3 简述线索二元树的概念。
4 何为有向图的遍历？
5 什么是索引顺序文件？
，更多更新年份持续更新，请在本站的考博信息网|www.kaoboinfo.com中的“考研试卷库”学校栏目中查询下载。
|
您现在的位置： 
