1、离线考核数据结构（高起专）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，用除留余数法
2、构造散列函数，用线性探查法解决冲突，并按关键字在集合中的顺序插入，请画出此散列(哈希)表，并求出在等概率情况下查找成功的平均查找长度。三、算法题（每小题15分，共30分。）1. 二叉树以二叉链表(lchild-rchild表示法)作为存储结构，试编写计算二叉树中叶结点个数的算法(要求写出存储结构的描述)，并分析算法的时间复杂度。2. 编写一个求单循环链表中结点个数的算法，并分析算法的时间复杂度(要求写出存储结构的描述)。答一、简答题1什么是有根的有向图？答：在一个有向图中，若存在一个顶点V0，从该顶点有路经可以到达图中其他所有顶点，则称此有向图为有根的有向图，V0称作图的根。2什么是负载因子？
3、答：负载因子(load factor)，也称为装填因子，定义为： 3试分析顺序存储结构的优缺点。答：优点： 内存的存储密度高(d=1)； 可以随机地存取表中的结点,与i的大小无关。 缺点： 进行插入和删除结点的运算时，往往会造成大量结点的移动，效率较低； 顺序表的存储空间常采用静态分配，在程序运行前存储规模很难预先确定。估计过大将导致空间的浪费，估计小了，随着结点的不断插入，所需的存储空间超出了预先分配的存储空间，就会发生空间溢出。 4算法的时间复杂度仅与问题的规模相关吗？答：算法的时间复杂度不仅与问题的规模相关而且还与数据结构中的数据分布有关。5举例说明散列表的平均查找长度不随表中结点数目的
4、增加而增加，而是随着负载因子的增大而增大。答：加进了线索的lchild-rchild存储表示的二叉树称作线索二叉树(threaded binary tree)， 简称为线索树。二、图示题（每小题15分，共30分。）1设待排序文件的初始排序码序列为 32, 38, 10, 53, 80, 69, 32, 05 ，写出采用冒泡排序算法排序时，每趟结束时的状态。解：冒泡排序算法排序时，每趟结束时的状态如下：2设有关键字集合为 16,05,28,10,09,17 ，散列表的长度为8，用除留余数法构造散列函数，用线性探查法解决冲突，并按关键字在集合中的顺序插入，请画出此散列(哈希)表，并求出在等概率情况
5、下查找成功的平均查找长度。解：三、算法题（每小题15分，共30分。）1. 二叉树以二叉链表(lchild-rchild表示法)作为存储结构，试编写计算二叉树中叶结点个数的算法(要求写出存储结构的描述)，并分析算法的时间复杂度。解： #include#include#define ElemType char#define NodeNum 5using namespace std; /二叉树的双链表存储结构typedef struct BiTNodeElemType data;/数据域struct BiTNode *lchild, *rchild;/左右孩子指针BiTNode, *BiTree;
6、void CreateTree(BiTree &root)/建立二叉树int i=1, flag;BiTree node, pre, p;srand(unsigned)time(NULL);while(i+ lchild = NULL;node-rchild = NULL;if(NULL = root)root = node;elsep = pre = root;/*现在从树根出发, 走到指定树叶结点, 然后在树叶结点上插入新结点, 输入 0 表示向左走, 输入其它字符表示向右走*/cout(向左向右?)请输入:flag;pre = p;if(0 = flag)/向左走p = p-lchild
7、;else/向右走p = p-rchild;/*将新结点插入为当前叶结点的左孩子(输入 0 )或右孩子(输入其它字符):*/coutflag;设二叉树中有n个结点，因为是遍历运算，故此算法的时间复杂度为：O(n)。2. 编写一个求单循环链表中结点个数的算法，并分析算法的时间复杂度(要求写出存储结构的描述)。解： #include #include typedef struct nodeint data;struct node *next;NODE,*List;void initList(List L)L = NULL;List createList()List head, p, q;int f
8、lag;head = (List)malloc(sizeof(NODE);head-next = NULL;q = head;printf(请输入节点的值,输入字母终值输入: );flag = scanf(%d, &q-data);while(flag)p = (List)malloc(sizeof(NODE);printf(请输入节点的值: );flag = scanf(%d, &p-data);q-next = p;p-next = NULL;q = q-next;return head;int listLength(List L)int count = 0;List p = L;while (p-next != NULL)p = p-next;count+;return count;void displayList(List L)printf(链表中的元素为：n);while (L-next != NULL)printf(%d , L-data);L = L-next;printf(n);void main()List L;L = createList();printf(链表的长度为: %dn, listLength(L);displayList(L);设单循环链表中有n个结点，此算法的时间复杂度为：O(n)。
