[东北师范大学]数据结构（高起专）（离线考核）

skystar

离线考核
《数据结构（高起专）》
满分100分
一、简答题（每小题8分，共40分。）
1．什么是有根的有向图？
2．什么是负载因子？
3．试分析顺序存储结构的优缺点。
4．算法的时间复杂度仅与问题的规模相关吗？
5．举例说明散列表的平均查找长度不随表中结点数目的增加而增加，而是随着负载因子的增大而增大。
二、图示题（每小题15分，共30分。）
1．设待排序文件的初始排序码序列为 { 32, 38, 10, 53, 80, 69, 32, 05 }，写出采用冒泡排序算法排序时，每趟结束时的状态。
2．设有关键字集合为 { 16,05,28,10,09,17 }，散列表的长度为8，用除留余数法构造散列函数，用线性探查法解决冲突，并按关键字在集合中的顺序插入，请画出此散列(哈希)表，并求出在等概率情况下查找成功的平均查找长度。
三、算法题（每小题15分，共30分。）
1. 二叉树以二叉链表(lchild-rchild表示法)作为存储结构，试编写计算二叉树中叶结点个数的算法(要求写出存储结构的描述)，并分析算法的时间复杂度。
2. 编写一个求单循环链表中结点个数的算法，并分析算法的时间复杂度(要求写出存储结构的描述)。