数据结构(高起专)

离线考核《数据结构（高起专）》满分100分一、简答题（每小题8分，共40分。）1．什么是有根的有向图？答：在一个有向图中，若存在一个顶点V0，从该顶点有路经可以到达图中其他所有顶点，则称此有向图为有根的有向图，V0称作图的根。2．什么是负载因子？答：负载因子(loadfactor)，也称为装填因子，定义为：3．试分析顺序存储结构的优缺点。答：优点：⑴内存的存储密度高(d=1)；⑵可以随机地存取表中的结点,与i的大小无关。缺点：⑴进行插入和删除结点的运算时，往往会造成大量结点的移动，效率较低；⑵顺序表的存储空间常采用静态分配，在程序运行前存储规模很难预先确定。估计过大将导致空间的浪费，估计小了，随着结点的不断插入，所需的存储空间超出了预先分配的存储空间，就会发生空间溢出。4．算法的时间复杂度仅与问题的规模相关吗？答：算法的时间复杂度不仅与问题的规模相关而且还与数据结构中的数据分布有关。5．举例说明散列表的平均查找长度不随表中结点数目的增加而增加，而是随着负载因子的增大而增大。答：与其他基于比较的查找方法(如顺序查找、折半查找等)相比，这是散列法的基本特征，它是一种与负载因子有关的查找方法。例如，当m=100,n=50时与当m=10000,n=5000时，α=n/m=0.5,即两者的平均查找长度相同。由于平均查找长度ASL(α)是关于负载因子α的递增函数，显然平均查找长度随负载因子的增大而增大。二、图示题（每小题15分，共30分。）1．设待排序文件的初始排序码序列为{32,38,10,53,80,69,32,05}，写出采用冒泡排序算法排序时，每趟结束时的状态。答：冒泡排序算法排序时，每趟结束时的状态如下：mn点个数基本区域所能容纳的结个数散列表中已存入的结点2．设有关键字集合为{16,05,28,10,09,17}，散列表的长度为8，用除留余数法构造散列函数，用线性探查法解决冲突，并按关键字在集合中的顺序插入，请画出此散列(哈希)表，并求出在等概率情况下查找成功的平均查找长度。答：三、算法题（每小题15分，共30分。）1.二叉树以二叉链表(lchild-rchild表示法)作为存储结构，试编写计算二叉树中叶结点个数的算法(要求写出存储结构的描述)，并分析算法的时间复杂度。答：存储结构描述如下：constintMaxSize=100;typedefchardatatype;typedefstructnode{datatypedata;structnode*lchild,*rchild;}BTnode,*BinTree;BinTreeroot;BTnode*p;intnum;//统计二叉树中叶结点个数的变量进入算法时，指针root指向根结点16052810091702050030203111134key比较次数(a)计算过程h(key)(b)散列表ht[0..7]用线性探查法解决冲突281610090517n=6；m=8；h(key)=key%701234567算法结束时，二叉树中分支结点个数保存在变量num中。（说明：下面的算法和C/C++程序只要给出其中一种形式即可。）//调用为InOrderCount(root,num)，mun的初值为0。算法计算二叉树中叶结点个数C/C++程序：InOrderCount(p,num)InOrderCount(BinTreep,int&num){1.若p≠NULLif(p!=NULL){则⑴InOrderCount(p-lchild)InOrderCount(p-lchild);⑵若p-lchild=NULL且if(p-lchild==NULL&&p-rchild=NULLp-rchild==NULL))则num←num+1num++;⑶InOrderCount(p-rchild)InOrderCount(p-rchild);}2.[算法结束]▍}设二叉树中有n个结点，因为是遍历运算，故此算法的时间复杂度为：O(n)。3．编写一个求单循环链表中结点个数的算法，并分析算法的时间复杂度(要求写出存储结构的描述)。答：型与变量说明及算法如下：typedefintdatatype;//结点的数据域的类型为整型typedefstructnode{//结点类型定义datatypedata;//结点的数据域structnode*next;//结点的指针域}ListNode,*LinkList;ListNode*p;LinkListrear;intn;（说明：下面的算法和C/C++程序只要给出其中一种形式即可。）算法求单循环链表中结点个数intLinkedListCount(LinkListrear){LinkedListCount(rear)ListNode*p;⒈若rear=NULLintn=0;则n←0;returnnif(rear==NULL)returnn;⒉p←rear;n←1p=rear;n=1;⒊循环当p-next≠rear时，执行while(p-next!=rear){n←n+1;n++;p←p-nextp=p-next;⒋returnn}⒌[算法结束]▍returnn;}设单循环链表中有n个结点，此算法的时间复杂度为：O(n)。