文档介绍：该【数据结构(高起专) 】是由【花双韵芝】上传分享，文档一共【4】页，该文档可以免费在线阅读，需要了解更多关于【数据结构(高起专) 】的内容，可以使用淘豆网的站内搜索功能，选择自己适合的文档，以下文字是截取该文章内的部分文字，如需要获得完整电子版，请下载此文档到您的设备，方便您编辑和打印。离线核查
《数据结构(高起专)》
满分100分
一、简答题(每题8分,共40分。)
答:在一个有向图中,若存在一个极点V0,从该极点有路经能够抵达图中其余全部极点,则称此有向图为
有根的有向图,V0称作图的根。
答:负载因子(loadfactor),也称为装填因子,定义为:
散列表中已存入的结点个数n
基当地区所能容纳的结点个数m
。
答:长处:⑴内存的储蓄密度高(d=1);
⑵能够随机地存取表中的结点,与i的大小没关。
弊端:⑴进行插入和删除结点的运算时,常常会造成大批结点的挪动,效率较低;
⑵次序表的储蓄空间常采纳静态分派,在程序运转前储蓄规模很难开初确立。预计过大将致使空间的浪费,预计小了,跟着结点的不停插入,所需的储蓄空间高出了开初分派的储蓄空间,就会发生空间溢出。
答:算法的时间复杂度不只与问题的规模有关并且还与数据结构中的数据散布有关。
,而是跟着负载因子的增大而增大。
答:与其余鉴于比较的查找方法(如次序查找、折半查找等)比较,这是散列法的基本特点,它是一种与
负载因子有关的查找方法。
比方,当m=100,n=50时与当m=10000,n=5000时,α=n/m=,即二者的均匀查找长度同样。
因为均匀查找长度ASL(α)是对于负载因子α的递加函数,明显均匀查找长度随负载因子的增大而
增大。
二、图示题(每题15分,共30分。)
{32,38,10,53,80,69,32,05},写出采纳冒泡排序算法排
序时,每趟结束时的状态。
答:冒泡排序算法排序时,每趟结束时的状态以下:
{16,05,28,10,09,17},散列表的长度为8,用除留余数法结构散列函数,用线性
探查法解决矛盾,并按重点字在会合中的次序插入,请画出此散列(哈希)表,并求出在等概率状况下查找
成功的均匀查找长度。
答:
n=6;m=8;h(key)
=key%7
key
16
05
28
10
09
17
h(key)
02
05
0
03
02
03
比较次数
1
1
1
1
3
4
计算过程
01
234567
28
161009
0517
(b)散列表
ht[0
..
7]
用线性探查法解决矛盾
三、算法题(每题
15分,共
30分。)
(lchild-rchild
表示法)作为储蓄结构,试编写计算二叉树中叶结点个数的算法
(要
求写出储蓄结构的描绘
),并分析算法的时间复杂度。
答:储蓄结构描绘以下:
constintMaxSize=100;
typedefchardatatype;
typedefstructnode{
datatypedata;
structnode*lchild,*rchild;
}BTnode,*BinTree;BinTreeroot;BTnode*p;
intnum;
若p≠NULL
if(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)。
,并分析算法的时间复杂度(要求写出储蓄结构的描绘)。
答:型与变量说明及算法以下:
typedefintdatatype;
//结点的数据域的种类为整型
typedef
structnode{
//
结点种类定义
datatypedata;
//
结点的数据域
struct
node*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)。