东师19秋学期《数据结构（高起专）》离线考核（纸考转离线）

离线考核
《数据结构（高起专）》
东北师范大学
作业答案联系QQ 515224986

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

东北师范大学
答案联系QQ 515224986