文档库

最新最全的文档下载
当前位置:文档库 > 数据结构期末22

数据结构期末22

数据结构期末22

4、给定序列{100, 86, 48, 73, 35, 39, 42, 57, 66, 21}, 按堆结构的定义, 则它是一个______堆。

5、 在进行直接插入排序时, 其数据比较次数与数据的初始排列________关;而在进行直接

选择排序时,其数据比较次数与数据的初始排列__________关。

6、 结点关键字转换为该结点存储单元地址的函数H 称为_________或叫___________。

7、对n 个关键字的序列进行快速排序,平均情况下的空间复杂度为_______。

三、选择题:(共20分,每题2分)

数据结构期末22

1、将一棵有100个结点的完全二叉树从上到下,从左到右依次对结点进行编号,根结点的编号为1,则编号为49的结点的左孩子的编号为______。

A.98

B.99

C.50

D.48

2、堆的形状是一棵_______。

A.二叉排序树

B.满二叉树

C.完全二叉树

D.平衡二叉树

3、对于哈希函数H(key)=key MOD 13,被称为同义词的关键字是_______

A.35和41

B.23和39

C.15和44

D.25和51

4、指出在顺序表{2、

5、7、10、14、15、18、23、35、41、52}中,用二分法查找12,需做多少次比较。 ______

A 、2

B 、3

C 、4

D 、5

5、假设一个有n 个顶点和e 条弧的有向图用邻接表表示,则删除与某个顶点vi 相关的边时间复杂度是:________

A.O (n )

B.O (e )

C.O (n+e )

D.O (n*e )

6、从二叉排序树中查找一个元素时,其时间复杂度大致为________。

A、 O(n)

B、 O(1)

C、 O(log

2

n) D、 O(n2)

7、由权值分别为3,8,6,2,5的叶子结点生成一棵赫夫曼树,它的带权路径长度为________。

A、 24

B、 48

C、 72

D、 53

8、设有字符序列{Q、H、C、Y、P、A、M、S、R、D、F、X},一趟排序的结果为{F、H、C、D、

P、A、M、Q、R、S、Y、X},则是下列哪个排序算法。_____

A、起泡排序

B、初始步长为4的shell的排序

C、二路归并排序

D、以第一个元素为分界元素的快速排序

9、一个无向连通图的生成树是含有该连通图的全部顶点的_______。

A.极小连通子图

B.极小子图

C.极大连通子图

D.极大子图

10、图的广度优先遍历类似于二叉树的_______。

A.先序遍历

B.中序遍历

C.后序遍历

D.层次遍历

四、应用题:(共24分,每题6分)

1、如图所示的二叉树完成中序遍历、后序遍历、先序遍历,并画出后序线索化的二叉树。

数据结构期末22

数据结构期末22

2、请给出下图的邻接矩阵和邻接表。

3、对于下图请画出其用普里姆(prim)和克鲁斯卡尔(kruskal)两种不同算法生成最小生成树的各条边的并入顺序。画出最小生成树。

数据结构期末22

4、已知一组键值序列为(41,66,73,52,40,37,65,43),试采用快速排序法对该组序列作升序排序,并给出每一趟的排序结果。

a

b

e

d

c

f

5、关键码的输入序列{ 55, 31, 11, 37, 46, 73, 63, 02, 07 }请计算在二分法查找、平衡的二叉排序树两种的情况下等概率下查找成功的平均查找长度。

6、已知一组关键字为(19,14,23,01,68,20,84,27,55,11,10,79),则按哈希函数H(key)=key MOD 13和链地址法解决冲突构造这组关键字的哈希表。

五、程序题(共26分)1、阅读下列算法,并回答下列问题:(8分)

完善程序,并回答该算法完成什么功能?算法中r[n+1]的作用是什么?void sort (elemtype r[],int n)

{int k,i;

for(k=n-1;k>=1;k- -)

if(r[k]>r[k+1])

{ r[n+1]=r[k];

for(i=k+1;r[i]

r[i-1]=r[i];

;}

}}

2、完成下列程序,并说出该算法所完成的功能。(8分)

void weizhisort(struct node r[ n],int n)

{ int low,high,mid,j,i;

for(i=2;i<=n;i++)

{ r[0]=r[i];

low=__________;

high=_________;

while(low<=high)

{ mid=(low+high)/2;

if(r[0].key

_______________;

else low=mid+1; }

for(j=i-1;j>=l;j--)

r[j+1]=r[j];

r[high+1]=r[0];

}}

其中数据类型定义为:

struct node

{ int key;

数据结构期末22

} Infotype otherinfo;

}

3、说出下面算法完成的功能。(2分)void delete( int a[n],int i)

{if (i<0)||(i>=n) printf(“error”);

else

{for (j=i-1;j

a[j]=a[j+1];

n=n-1;}

}

4.完善程序,说明其功能(8分)

#define NULL 0;

typedef struct Bitnode{

char data;

Struct Bitnode *lchild,*rchild;

} Bitreptr;

void inorder_notrecursive(Bitreptr *bt)

{ Bitreptr *q,*s[20];

int top=0;

int bool=1;

q=bt;

do

{while(q!=NULL)

{ ;

s[top]=q;q=q->lchild;}

if(top==0) bool=0;

else

{q=s[top];top--;

printf(“%c”, );

;}

}while(bool);