数据结构(高起专)

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

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

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

4、h(key)比较次数（a）计算过程n =6 ； m = 8； h(key) = key %7012 3 4 5 6 7281610090517（b）散列表 ht0 . 7用线性探查法解决冲突三、算法题（每小题 15分，共30分。）1.二叉树以二叉链表（Ichild-rchild 表示法）作为存储结构，试编写计算二叉树中叶结点个数的算法（要求写出存储结构的描述），并分析算法的时间复杂度。答：存储结构描述如下：const int MaxSize =100; typedef char datatype; typedef struct node datatype data;struct node *l

5、child, *rchild; BTn ode, *Bi nTree;Bi nTree root;BTn ode* p;则 InOrderCount (p->lchild)In OrderCou nt (p->lchild);int num;若 pz NULLif ( p!=NULL) 若 p->lchild = NULL 且p->rchild = NULL贝 V num j nu m+1if(p->lchild = = NULL &&p->rchild = = NULL) nu m+; In OrderCou nt (p->rchil

6、d)In OrderCou nt (p->rchild);2.算法结束I设二叉树中有n个结点，因为是遍历运算，故此算法的时间复杂度为：O(n)。(要求写出存储结构的描述)。3编写一个求单循环链表中结点个数的算法，并分析算法的时间复杂度答：型与变量说明及算法如下：设单循环链表中有 n个结点，此算法的时间复杂度为：O(n)。typedef int datatype;typedef struct node datatype data;structnode *n ext; ListNode, *Li nkList;ListNode *p;Lin kList rear;int n;/结点的数据域的类型为整型/结点类型定义/结点的数据域/结点的指针域(说明：下面的算法和C/C+程序只要给出其中一种形式即可。)1.2.3.算法求单循环链表中结点个数Lin kedListCo unt若 rear = NULL贝V n j 0; return np j rear; n j 1intLin kedListCo unt(Lin kList rear)(rear )int n =ListNode *p;0;if (rearNULL) retur n n;rear; n