离线考核
《数据结构（高起专）》
2020年奥鹏东北师大考核试题标准答案
试读1页答案在最后
满分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. 编写一个求单循环链表中结点个数的算法，并分析算法的时间复杂度(要求写出存储结构的描述)。 答 一、简答题
1．什么是有根的有向图？
答：在一个有向图中，若存在一个顶点V0，从该顶点有路经可以到达图中其他所有顶点，则称此有向图为
有根的有向图，V0称作图的根。
2．什么是负载因子？
答：负载因子(load factor)，也称为装填因子，定义为：
3．试分析顺序存储结构的优缺点。 答：优点：⑴ 内存的存储密度高(d=1)；
⑵ 可以随机地存取表中的结点,与i的大小无关。
缺点：⑴ 进行插入和删除结点的运算时，往往会造成大量结点的移动，效率较低；
⑵ 顺序表的存储空间常采用静态分配，在程序运行前存储规模很难预先确定。估计过大将导致空间的浪费，估计小了，随着结点的不断插入，所需的存储空间超出了预先分配的存储空间，就会发生空间溢出。
4．算法的时间复杂度仅与问题的规模相关吗？
答：算法的时间复杂度不仅与问题的规模相关而且还与数据结构中的数据分布有关。
? ? 散列表中已存入的结点个数 n ? 基本区域所能容纳的结点个数 m
5．举例说明散列表的平均查找长度不随表中结点数目的增加而增加，而是随着负载因子的增大而增大。 答：加进了线索的lchild-rchild存储表示的二叉树称作线索二叉树(threaded binary tree)， 简称
为线索树。
二、图示题（每小题15分，共30分。）
1．设待排序文件的初始排序码序列为 { 32, 38, 10, 53, 80, 69, 32, 05 }，写出采用冒泡排序算法排序时，每趟结束时的状态。
解：冒泡排序算法排序时，每趟结束时的状态如下：
R[ ]初态12345678第1趟12345678第2趟12345678第3趟12345678第4趟1234567832381053806932050532381053806932flag=10510323832538069flag=10510323238536980flag=10510323238536980flag=0排排排排2．设有关键字集合为 { 16,05,28,10,09,17 }，散列表的长度为8，用除留余数法构造散列函数，用线性探查法解决冲突，并按关键字在集合中的顺序插入，请画出此散列(哈希)表，并求出在等概率情况下查找成功的平均查找长度。
解：
三、算法题（每小题15分，共30分。）
1. 二叉树以二叉链表(lchild-rchild表示法)作为存储结构，试编写计算二叉树中叶结点个数的算法(要求写出存储结构的描述)，并分析算法的时间复杂度。
解： #include
//二叉树的双链表存储结构
keyn = 6；m = 8； h(key) = key % 716050512801100310902317034h(key)02比较次数1(a) 计算过程0 1 2 3 4 5 6 7281610090517(b) 散列表 ht[0 ..7]用线性探查法解决冲突
2020年奥鹏东北师范大学《数据结构(高起专)》(离线考核)参考答案
