2020年《数据结构(高起专)》(离线考核)参考答案

离线考核《数据结构（高起专）》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．什么是负载因子？答：负载因子(loadfactor)，也称为装填因子，定义为：3．试分析顺序存储结构的优缺点。答：优点：⑴内存的存储密度高(d=1)；⑵可以随机地存取表中的结点,与i的大小无关。缺点：⑴进行插入和删除结点的运算时，往往会造成大量结点的移动，效率较低；⑵顺序表的存储空间常采用静态分配，在程序运行前存储规模很难预先确定。估计过大将导致空间的浪费，估计小了，随着结点的不断插入，所需的存储空间超出了预先分配的存储空间，就会发生空间溢出。4．算法的时间复杂度仅与问题的规模相关吗？答：算法的时间复杂度不仅与问题的规模相关而且还与数据结构中的数据分布有关。5．举例说明散列表的平均查找长度不随表中结点数目的增加而增加，而是随着负载因子的增大而增大。答：加进了线索的lchild-rchild存储表示的二叉树称作线索二叉树(threadedbinarytree)，简称为线索树。二、图示题（每小题15分，共30分。）1．设待排序文件的初始排序码序列为{32,38,10,53,80,69,32,05}，写出采用冒泡排序算法排序时，每趟结束时的状态。解：冒泡排序算法排序时，每趟结束时的状态如下：2．设有关键字集合为{16,05,28,10,09,17}，散列表的长度为8，用除留余数法构造散列函数，用线性探查法解决冲突，并按关键字在集合中的顺序插入，请画出此散列(哈希)表，并求出在等概率情况下查找成功的平均查找长度。解：三、算法题（每小题15分，共30分。）1.二叉树以二叉链表(lchild-rchild表示法)作为存储结构，试编写计算二叉树中叶结点个数的算法(要求写出存储结构的描述)，并分析算法的时间复杂度。解：#include<iostream>#include<time.h>#defineElemTypechar#defineNodeNum5usingnamespacestd;//二叉树的双链表存储结构typedefstructBiTNode{ ElemTypedata;//数据域 structBiTNode*lchild,*rchild;//左右孩子指针}BiTNode,*BiTree;voidCreateTree(BiTree&root){//建立二叉树 inti=1,flag; BiTreenode,pre,p; srand((unsigned)time(NULL)); while(i++<=NodeNum) { node=newBiTNode; node->lchild=NULL; node->rchild=NULL; if(NULL==root) { root=node; } else { p=pre=root; /*现在从树根出发,走到指定树叶结点,然后在树叶结点上插入新结点,输入0表示 向左走,输入其它字符表示向右走*/ cout<<"(向左向右?)请输入:"<<endl; while(NULL!=p) { cin>>flag; pre=p; if(0==flag) {//向左走 p=p->lchild; } else {//向右走 p=p->rchild; } } /*将新结点插入为当前叶结点的左孩子(输入0)或右孩子(输入其它字符):*/ cout<<"选择插入方向:"; cin>>flag;设二叉树中有n个结点，因为是遍历运算，故此算法的时间复杂度为：O(n)。2.编写一个求单循环链表中结点个数的算法，并分析算法的时间复杂度(要求写出存储结构的描述)。解：#include<stdio.h>#include<stdlib.h>typedefstructnode{intdata;structnode*next;}NODE,*List;voidinitList(ListL){L=NULL;}ListcreateList(){Listhead,p,q;intflag;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;}returnhead;}intlistLength(ListL){intcount=0;Listp=L;while(p->next!=NULL){p=p->next;count++;}returncount;}voiddisplayList(ListL){printf("链表中的元素为：\n");while(L->next!=NULL){printf("%d",L->d