数据结构高起专

1、离线考核数据结构（高起专）满分100分一、简答题（每小题8分，共40分。）1什么是有根的有向图？答：在一个有向图中，若存在一个顶点V0，从该顶点有路经可以到达图中其他所有顶点，则称此有向图为有根的有向图，V0称作图的根。2 什么是负载因子？答：负载因子(load factor)，也称为装填因子，定义为：3 试分析顺序存储结构的优缺点。答：优点： 内存的存储密度高(d=1)； 可以随机地存取表中的结点,与i的大小无关。 缺点： 进行插入和删除结点的运算时，往往会造成大量结点的移动，效率较低； 顺序表的存储空间常采用静态分配，在程序运行前存储规模很难预先确定。估计过大将导致空间的浪费，估计小了，随

2、着结点的不断插入，所需的存储空间超出了预先分配的存储空间，就会发生空间溢出。 4 算法的时间复杂度仅与问题的规模相关吗？答：算法的时间复杂度不仅与问题的规模相关而且还与数据结构中的数据分布有关。5 举例说明散列表的平均查找长度不随表中结点数目的增加而增加，而是随着负载因子的增大而增大。答：与其他基于比较的查找方法(如顺序查找、折半查找等)相比，这是散列法的基本特征，它是一种与负载因子有关的查找方法。例如，当m = 100, n = 50时与当m = 10000, n = 5000时， = n/m = 0.5,即两者的平均查找长度相同。由于平均查找长度ASL()是关于负载因子的递增函数，显然平均

3、查找长度随负载因子的增大而增大。二、图示题（每小题15分，共30分。）1设待排序文件的初始排序码序列为 32, 38, 10, 53, 80, 69, 32, 05 ，写出采用冒泡排序算法排序时，每趟结束时的状态。答：冒泡排序算法排序时，每趟结束时的状态如下：2 设有关键字集合为 16,05,28,10,09,17 ，散列表的长度为8，用除留余数法构造散列函数，用线性探查法解决冲突，并按关键字在集合中的顺序插入，请画出此散列(哈希)表，并求出在等概率情况下查找成功的平均查找长度。答：三、算法题（每小题15分，共30分。）1. 二叉树以二叉链表(lchild-rchild表示法)作为存储结构，试

4、编写计算二叉树中叶结点个数的算法(要求写出存储结构的描述)，并分析算法的时间复杂度。答：存储结构描述如下：const int MaxSize =100;typedef char datatype;typedef struct node datatype data; struct node *lchild, *rchild; BTnode, *BinTree;BinTree root;BTnode* p;int num; / 统计二叉树中叶结点个数的变量进入算法时，指针root指向根结点 算法结束时，二叉树中分支结点个数保存在变量num中。（说明：下面的算法和C/C+ 程序只要给出其中一种形式即

5、可。）/ 调用为InOrderCount (root, num)，mun的初值为0。算法 计算二叉树中叶结点个数 C/C+ 程序： InOrderCount (p, num) InOrderCount (BinTree p, int &num) 1. 若pNULL if ( p!=NULL) 则 InOrderCount (p->lchild) InOrderCount (p->lchild); 若p->lchild = NULL 且 if (p->lchild = = NULL &&p->rchild = NULL p->rchil

6、d = = NULL)则 num num+1 num+; InOrderCount (p->rchild) InOrderCount (p->rchild); 2. 算法结束 设二叉树中有n个结点，因为是遍历运算，故此算法的时间复杂度为：O(n)。3 编写一个求单循环链表中结点个数的算法，并分析算法的时间复杂度(要求写出存储结构的描述)。答：型与变量说明及算法如下：typedef int datatype; / 结点的数据域的类型为整型typedef struct node / 结点类型定义 datatype data; / 结点的数据域 struct node *next; /

7、结点的指针域 ListNode, *LinkList;ListNode *p; LinkList rear;int n;（说明：下面的算法和C/C+ 程序只要给出其中一种形式即可。）算法 求单循环链表中结点个数 int LinkedListCount (LinkList rear)LinkedListCount (rear ) ListNode *p; 若 rear = NULL int n = 0;则 n 0; return n if (rear = = NULL) return n; p rear; n 1 p = rear; n = 1; 循环 当 p->next rear 时，执行 while (