对一棵平衡二叉树,当且仅当该树是一心二叉树

判断题:

判断题:

1-1

1-1

N2logN和NlogN2装有相同的增长速度。
(2分)

N2logN和NlogN2具有相同的增速。

1-2

1-2

对一棵平衡二叉树,全部非叶结点的平衡因子都是0,当且仅当该树是一心二叉树。(2分) 

对一棵平衡二叉树,全部非叶结点的平衡因子都以0,当且仅当该树是一心二叉树。

1-3

1-3

无向连通图全体终端的度之和为偶数。 (2分) 

无向连通图全体终端的度之和为偶数。

1-4

1-4

对N个区别的数据接纳冒泡排序实行从大到小的排序,当成分基本不变时沟通到分次数肯定最多。
(2分) 

对N个差异的多寡应用冒泡排序举行从大到小的排序,当成分基本铁定的事情时调换到分次数肯定最多。

1-5

1-5

若用平方探测法化解冲突,则插入新因素时,若散列表体积为质数,插入就一定能够成功。
(2分) 

若用平方探测法解决争辩,则插入新因素时,若散列表体积为质数,插入就必定能够成功。

 

选择题:

选择题:

2-1

2-1

设栈S和队列Q的发端状态均为空,成分a、b、c、d、e、f、g依次进入栈S。若每种成分出栈后立马进入队列Q,且三个因素出队的一一是b、d、c、f、e、a、g,则栈S的体量至少是:

设栈S和队列Q的发端状态均为空,成分a、b、c、d、e、f、g依次进入栈S。若各种元素出栈后立刻进入队列Q,且九个要素出队的逐条是b、d、c、f、e、a、g,则栈S的体量至少是:
(2分)
A、1

A、1

B、2

B、2

C、3

C、3

D、4 

D、4

2-2

2-2

在下列所示的平衡二叉树中,插加入关贸总协定协会键字48后获得一棵新平衡二叉树。在新平衡二叉树中,关键字37所在结点的左、右子结点中保存的首要性字分别是:
(伍分)
图片 1

在下列所示的平衡二叉树中,插加入关贸总协定组织键字48后拿走一棵新平衡二叉树。在新平衡二叉树中,关键字37所在结点的左、右子结点中保留的主要字分别是:

A、13、48

图片 2

B、24、48

A、13、48

C、24、53

B、24、48

D、24、90 

C、24、53

2-3

D、24、90

线性表、堆栈、队列的重庆大学差异是什么?(2分)

2-3

A、线性表用指针,堆栈和队列用数组

线性表、堆栈、队列的严重性差距是怎么着?

B、堆栈和队列都以插入、删除受到约束的线性表

A、线性表用指针,堆栈和队列用数组

C、线性表和队列都足以用循环链表实现,但堆栈不可能

B、堆栈和队列都以插入、删除受到约束的线性表

D、堆栈和队列都不是线性结构,而线性表是 

C、线性表和队列都足以用循环链表实现,但堆栈不能够

2-4

D、堆栈和队列都不是线性结构,而线性表是

对N(N≥2)
个权值均不等同的字符构造哈夫曼树。下列关于该哈夫曼树的叙说中,错误的是:
(2分)
A、树中必然没有度为1的结点
B、树中五个权值最小的结点一定是手足结点
C、树中任一非叶结点的权值一定十分的大于下一层任一结点的权值
D、该树一定是一棵完全二叉树 

2-4

2-5

对N(N≥2)个权值均不均等的字符构造哈夫曼树。下列关于该哈夫曼树的叙述中,错误的是:
A、树中必将没有度为1的结点
B、树中多少个权值最小的结点一定是手足结点
C、树中任一非叶结点的权值一定一点都不小于下一层任一结点的权值
D、该树一定是一棵完全二叉树

在并查集难题中,已知集合成分0~8所以对应的父结点编号值分别是{ 1, -4, 1,
1, -3, 4, 4, 8, -2
}(注:−n代表树根且对应集合大小为n),那么将成分6和8所在的成团合并(需要必须将小集合并到大集合)后,该集合对应的树根和父结点编号值分别是有个别?
(6分)
A、1和-6

2-5

B、4和-5

在并查集难点中,已知集合成分0~8所以对应的父结点编号值分别是{ 1, -4, 1,
1, -3, 4, 4, 8, -2
}(注:−n代表树根且对应集合大小为n),那么将成分6和8所在的聚合合并(供给必须将小集合并到大集合)后,该集合对应的树根和父结点编号值分别是不怎么?

C、8和-5

A、1和-6

D、8和-6 

B、4和-5

2-6

C、8和-5

要认清二个整数N(>10)
是不是素数,大家须求检查3到√N之间是或不是留存奇数能够整除N 。则这些算法的时辰复杂度是:(2分) 
A、O(N/2)
B、O(√NlogN)
C、O(√N)
D、O(0.5logN)
 

D、8和-6

2-7

2-6

在1个有权无向图中,如若顶点b到顶点a的最短路径长度是10,顶点c与顶点b里面存在一条长度为3的边。那么下列说法中有几句是不利的?
(2分)

要一口咬定四个整数N(>10)是还是不是素数,我们须求检查3到√N之间是或不是留存奇数能够整除N。则这些算法的光阴复杂度是:
A、O(N/2)
B、O(√NlogN)
C、O(√N)
D、O(0.5logN)

1.c与a的最短路径长度正是13

2-7

2.c与a的最短路径长度正是7

在三个有权无向图中,假如顶点b到顶点a的最短路径长度是10,顶点c与顶点b之间存在一条长度为3的边。那么下列说法中有几句是未可厚非的?

3.c与a的最短路径长度不超越13

1.c与a的最短路径长度便是13

4.c与a的最短路径不低于7
A、1句

2.c与a的最短路径长度正是7

B、2句

3.c与a的最短路径长度不领先13

C、3句

4.c与a的最短路径不低于7
A、1句

D、4句 

B、2句

2-8

C、3句

将MMM个要素存入用长度为SSS的数组表示的散列表,则该表的装满因子为: (2分)

D、4句

A、S+M
B、M−S
C、M×S
D、M/S  

2-8

2-9

将MMM个因素存入用长度为SSS的数组表示的散列表,则该表的回填因子为:

给定输入体系 {4371, 1323, 6173, 4199, 4344, 9679, 1987} 以及散列函数
h(X)=X %
10
。假如用大小为10的散列表,并且用分离链接法化解抵触,则输入各项经散列后在表中的下标为:(-1意味着相应的插入非常小概得逞)(2分)
A、1, 3, 3, 9, 4, 9, 9
B、1, 3, 4, 9, 7, 5, -1
C、1, 3, 4, 9, 5, 0, 8
D、1, 3, 4, 9, 5, 0, 2 

A、S+M
B、M−S
C、M×S
D、M/S

2-10

2-9

在拓扑排序算法中用堆栈和用队列爆发的结果会不一样啊?(2分)

给定输入类别 {4371, 1323, 6173, 4199, 4344, 9679, 一九八六} 以及散列函数
h(X)=X%
10。借使用大小为10的散列表,并且用分离链接法化解争辨,则输入各项经散列后在表中的下标为:(-1意味相应的插入无法得逞)
A、1, 3, 3, 9, 4, 9, 9
B、1, 3, 4, 9, 7, 5, -1
C、1, 3, 4, 9, 5, 0, 8
D、1, 3, 4, 9, 5, 0, 2

A、是的肯定差异

2-10

B、肯定是千篇一律的

在拓扑排序算法中用堆栈和用队列发生的结果会不一样吧?

C、有恐怕会分裂

A、是的听其自然不一致

D、以上全不对 

B、肯定是如出一辙的

2-11

C、有或然会分裂

将 {28, 15,
42, 18, 22, 5, 40}
各种按梯次插入到起来为空的最小堆(小根堆)中。则该树的前序遍历结果为:(5分)

D、以上全不对

A、5, 18,
15, 28, 22, 42, 40
B、5, 15,
18, 22, 28, 42, 40
C、5, 18,
28, 22, 15, 42, 40
D、5, 15,
28, 18, 22, 42, 40 

2-11

2-12

将 {28, 15,
42, 18, 22, 5, 40}
每一种按顺序插入到早先为空的细小堆中。则该树的前序遍历结果为:
A、5, 18,
15, 28, 22, 42, 40
B、5, 15,
18, 22, 28, 42, 40
C、5, 18,
28, 22, 15, 42, 40
D、5, 15,
28, 18, 22, 42, 40

将1~6这么些键值插到一棵伊始为空的二叉搜索树中。如若插入完毕后,搜索树结构如图所示,问:也许的插入连串是怎么?
(2分)
图片 3

2-12

A、1 2 3 4
5 6
B、4 1 2 3
5 6
C、4 1 3 2
6 5
D、4 1 3 2
5 6 

将1~6那四个键值插到一棵初叶为空的二叉搜索树中。假如插入实现后,搜索树结构如图所示,问:可能的插入种类是什么样?

2-13

图片 4

给定一有向图的邻接表如下。从极限V1出发按广度优先搜索法实行遍历,则收获的一种顶点类别为:
(2分)
图片 5

A、1 2 3 4
5 6
B、4 1 2 3
5 6
C、4 1 3 2
6 5
D、4 1 3 2
5 6

A、V1,V2,V3,V4,V5

2-13

B、V1,V2,V3,V5,V4

给定一有向图的邻接表如下。从终端V1出发按广度优先搜索法举办遍历,则获得的一种顶点连串为:

C、V1,V3,V2,V4,V5

图片 6

D、V1,V4,V3,V5,V2

A、V1,V2,V3,V4,V5

2-14

B、V1,V2,V3,V5,V4

已知八个图的邻接矩阵如下,则从终端V1出发按深度优先搜索法进行遍历,大概赢得的一种顶点类别为:
(2分)
图片 7

C、V1,V3,V2,V4,V5

A、V1,V2,V3,V4,V5,V6

D、V1,V4,V3,V5,V2

B、V1,V2,V4,V5,V6,V3

2-14

C、V1,V3,V5,V2,V4,V6

已知一个图的邻接矩阵如下,则从终端V1出发按深度优先搜索法实行遍历,也许取得的一种顶点类别为:

D、V1,V3,V5,V6,V4,V2 

图片 8

2-15

A、V1,V2,V3,V4,V5,V6

付给关键字系列{ 4321, 56, 57, 46, 28, 7, 331, 33, 234, 63
},上面哪个选拔是按次位优先(LSD)链式基数排序举行了一趟分配和综合机械化采煤的结果?
(2分)

B、V1,V2,V4,V5,V6,V3

A、→331→4321→33→63→234→56→46→57→7→28

C、V1,V3,V5,V2,V4,V6

B、→4321→331→33→63→234→56→46→57→7→28

D、V1,V3,V5,V6,V4,V2

C、→56→28→4321→331→33→234→46→57→63→7

2-15

D、→57→46→28→7→33→234→63→56→4321→331 

付出关键字连串{ 4321, 56, 57, 46, 28, 7, 331, 33, 234, 63
},上边哪个选取是按次位优先链式基数排序进行了一趟分配和综合机械化采煤的结果?

2-16

A、→331→4321→33→63→234→56→46→57→7→28

将连串{ 2,
12, 16, 88, 5, 10, 34 }排序。若前2趟排序的结果如下:

B、→4321→331→33→63→234→56→46→57→7→28

第①趟排序后:2, 12, 16, 10, 5, 34, 88

C、→56→28→4321→331→33→234→46→57→63→7

第叁趟排序后:2, 5, 10, 12, 16, 34, 88

D、→57→46→28→7→33→234→63→56→4321→331

则大概的排序算法是:(2分)
A、冒泡排序

2-16

B、快速排序

将类别{ 2,
12, 16, 88, 5, 10, 34 }排序。若前2趟排序的结果如下:

C、归并排序

第3趟排序后:2, 12, 16, 10, 5, 34, 88

D、插入排序 

第叁趟排序后:2, 5, 10, 12, 16, 34, 88

2-17

则只怕的排序算法是:
A、冒泡排序

给定有权无向图的邻接矩阵如下,其最小生成树的总权重是:(2分)
图片 9

B、快捷排序

A、24

C、归并排序

B、23

D、插入排序

C、18

2-17

D、17 

给定有权无向图的邻接矩阵如下,其最小生成树的总权重是:
图片 10

2-18

A、24

在使用仓库将下列哪其中缀表达式转换为后缀表明式进程中,堆栈的操作连串为:
push(′∗′)、push(′(′)、push(′+′)、pop()、pop()、pop()、push(′∗′)、pop()、push(′+′)、pop()
(2分)
A、2*(3+4)*5+6
B、2*(3+4*5)+6
C、2*(3+4*5+6)
D、以上都以 

B、23

2-19

C、18

行使线性探测争辨化解政策,hi(k)=(H(k)+i)mod11
,将散列函数值分别相当于② 、贰 、叁 、3的多少个对象a一 、a② 、a三 、a4都插入三个分寸为11的空散列表(哈希表)中。在分化的插入顺序中,哪句有关插入后散列表平均成功查找长度的论断是错的?
(陆分)
A、按a壹 、a贰 、a叁 、a4相继和按a一 、a叁 、a四 、a2一一,平均成功查找长度一样;
B、按a① 、a③ 、a贰 、a4依次和按a叁 、a① 、a贰 、a4顺序,平均成功查找长度一样;
C、按a一 、a三 、a二 、a4挨家挨户和按a肆 、a① 、a② 、a3逐项,平均成功查找长度一样;
D、按别的插入顺序,其平均成功查找长度都一样. 

D、17

2-20

2-18

将10, 12,
1, 14, 6, 5, 8, 15, 3, 9,
7每一种按顺序插入到初步为空的微小堆中,然后接二连三实施四次删除最小元素操作(DeleteMin),再插入4,16,此后堆顶的要素是何许?
(2分)
A、4

在运用仓库将下列哪在那之中缀表达式转换为后缀表达式进程中,堆栈的操作类别为:
push(′∗′)、push(′(′)、push(′+′)、pop、pop、pop、push(′∗′)、pop、push(′+′)、pop
A、2**5+6
B、2*+6
C、2*
D、以上都是

B、5

2-19

C、7

应用线性探测争辨消除政策,hi(k)=(H(k)+i)mod11,将散列函数值分别也便是二 、二 、③ 、3的三个目的a壹 、a② 、a叁 、a4都插入2个高低为11的空散列表中。在差异的插入顺序中,哪句有关插入后散列表平均成功查找长度的判定是错的?
A、按a① 、a二 、a三 、a4挨家挨户和按a一 、a三 、a④ 、a2逐项,平均成功查找长度一样;
B、按a一 、a③ 、a二 、a4一一和按a叁 、a一 、a二 、a4每种,平均成功查找长度一样;
C、按a一 、a叁 、a② 、a4依次和按a肆 、a① 、a二 、a3顺序,平均成功查找长度一样;
D、按其余插入顺序,其平均成功查找长度都一样.

D、9 

2-20

 

将10, 12,
1, 14, 6, 5, 8, 15, 3, 9,
7每一种按顺序插入到开端为空的微乎其微堆中,然后三番五次实施五回删除最小成分操作(DeleteMin),再插入4,16,此后堆顶的因素是如何?

次第填空题:

A、4

3-1

B、5

下列代码的功效是将小顶堆H中内定地方P上的要素的平头键值下调D个单位,然后继续将H调整为小顶堆。

C、7

1 void DecreaseKey( int P, int D, PriorityQueue H )
2 {
3    int i, key;
4    key = H->Elements[P] - D;
5    for ( i = /**/(4分); H->Elements[i/2] > key; i/=2 )
6       //(4分);
7    H->Elements[i] = key;
8 }

D、9

3-2

先后填空题:

下列代码的效益是将一列成分{ r[1] … r[n]
}按非递减顺序排序。普通选用排序是历次仅将3个待排种类的小小元放到科学的职务上,而以此另类的选料排序是每回从待排系列中并且找到最小元和最大元,把它们放到最后的不易地点上。

3-1

 1 void  sort( list r[], int n )  
 2 {
 3    int i, j, mini, maxi;
 4 
 5    for (i=1; i<n-i+1; i++) {
 6       mini = maxi = i;
 7       for( j=i+1; /**/(4分); ++j ){
 8          if( /**/(4分) ) mini = j; 
 9          else if(r[j]->key > r[maxi]->key) maxi = j;
10       }
11       if( /**/(4分) ) swap(&r[mini], &r[i]);
12       if( maxi != n-i+1 ){
13          if( /**/(4分) ) swap(&r[mini], &r[n-i+1]);
14          else swap(&r[maxi], &r[n-i+1]);
15       }
16    }
17 }

下列代码的效应是将小顶堆H中钦赐地点P上的成分的整数键值下调D个单位,然后继续将H调整为小顶堆。

3-3

1 void DecreaseKey( int P, int D, PriorityQueue H )2 {3    int i, key;4    key = H->Elements[P] - D;5    for ( i = /**/; H->Elements[i/2] > key; i/=2 )6       //;7    H->Elements[i] = key;8 }

核心要求给出希尔排序对给定起头连串{9, 8, 7, 6, 5, 4, 3, 2,
1}利用增量连串{1, 3,
7}举行排序的分步结果。将每步结果填在下列空中。注意:相邻数字间必须有三个空格,开始结尾不得有盈余空格。

3-2

原始种类 9
8 7 6 5 4 3 2 1

下列代码的机能是将一列成分{ r[1] … r[n]
}按非递减顺序排序。普通选择排序是每一趟仅将贰个待排连串的纤维元放到科学的岗位上,而这么些另类的选项排序是每趟从待排种类中并且找到最小元和最大元,把它们放到最终的不易地方上。

增量7排序后   (2分)

 1 void  sort( list r[], int n )   2 { 3    int i, j, mini, maxi; 4  5    for (i=1; i<n-i+1; i++) { 6       mini = maxi = i; 7       for( j=i+1; /**/; ++j ){ 8          if( /**/ mini = j;  9          else if(r[j]->key > r[maxi]->key) maxi = j;10       }11       if( /**/ swap(&r[mini], &r[i]);12       if( maxi != n-i+1 ){13          if( /**/ swap(&r[mini], &r[n-i+1]);14          else swap(&r[maxi], &r[n-i+1]);15       }16    }17 }

增量3排序后   (2分)
增量1排序后
1 2 3 4 5 6 7 8 9

3-3

3-4

核心必要给出希尔排序对给定开始体系{9, 8, 7, 6, 5, 4, 3, 2,
1}利用增量体系{1, 3,
7}进行排序的分步结果。将每步结果填在下列空中。注意:相邻数字间必须有一个空格,开首结尾不得有结余空格。

主旨须求交付下图中从A到此外顶点的最短路径。注意:填空时不可能有别的空格。

原始连串 9
8 7 6 5 4 3 2 1
增量7排序后

图片 11

增量3排序后

终点 路径

增量1排序后
1 2 3 4 5 6 7 8 9

A->B AB

3-4

A->C AC

核心供给提交下图中从A到此外顶点的最短路径。注意:填空时无法有别的层空间格。

A->D
  (2分)

图片 12

A->E   (2分)
A->F   
 (2分)
A->G
ABG

终点 路径

 

A->B AB

编程题:

A->C AC

Description:

A->D
  
A->E  

大旨要求依据给定的一棵二叉树的后序遍历和中序遍历结果,输出该树的先序遍历结果。 

A->F  

Input:

A->G
ABG

先是行提交正整数N(<=30)是树中结点的个数。随后两行,每行给出N个整数,分别对应后序遍历和中序遍历结果,数字间以空格分隔。标题保障输入正确对应一棵二叉树。

编程题:

Output:

Description:

在一行中输出Preorder:以及该树的先序遍历结果。数字间有一个空格,行末不得有结余空格。

宗旨须求依照给定的一棵二叉树的后序遍历和中序遍历结果,输出该树的先序遍历结果。

Sample
Input:

Input:

7
2 3 1 5 7 6 4
1 2 3 4 5 6
7

首先行提交正整数N是树中结点的个数。随后两行,每行给出N个整数,分别对应后序遍历和中序遍历结果,数字间以空格分隔。标题保险输入正确对应一棵二叉树。

Sample
Output:

Output:

Preorder: 4 1 3 2 6 5
7

在一行中输出Preorder:以及该树的先序遍历结果。数字间有三个空格,行末不得有结余空格。

 

Sample
Input:

 

7
2 3 1 5 7 6 4
1 2 3 4 5 6 7

 

Sample
Output:

判断题:FFTFF

Preorder: 4
1 3 2 6 5 7

选择题:CCBDB  CBDAC  CDCBB  BBADA

判断题:FFTFF

次第填空题:

选择题:CCBDB  CBDAC  CDCBB  BBADA

P  H->Elements[i]
= H->Elements[i/2]

先后填空题:

j <
n-i+1  r[j]->key < r[mini]->key  mini != i  maxi ==
i

P  H->Elements[i]
= H->Elements[i/2]

2 1 7 6 5 4
3 9 8  2 1 4 3 5 7 6 9 8

j <
n-i+1  r[j]->key < r[mini]->key  mini != i  maxi ==
i

ABGED  ABGE  ABGEF

2 1 7 6 5 4
3 9 8  2 1 4 3 5 7 6 9 8

编程题:

ABGED  ABGE  ABGEF

 1 #include <cstdio>
 2 #include <cstring>
 3 
 4 void getpre(int *post, int *in, int n)
 5 {
 6     if(n <= 0) return;
 7     int i = 0, root = post[n-1];
 8     for(; i<n; ++i) {
 9         if(in[i] == root)   break;
10     }
11     printf(" %d", root);
12     getpre(post, in, i);
13     getpre(post+i, in+i+1, n-i-1);
14 }
15 
16 int main()
17 {
18     int n, post[40], in[40];
19     scanf("%d", &n);
20     for(int i=0; i<n; ++i) {
21         scanf("%d", &post[i]);
22     }
23     for(int i=0; i<n; ++i) {
24         scanf("%d", &in[i]);
25     }
26 
27     printf("Preorder:");
28     getpre(post, in, n);
29 
30     return 0;
31 }

// Fin

编程题:

 

 1 #include <cstdio> 2 #include <cstring> 3  4 void getpre(int *post, int *in, int n) 5 { 6     if(n <= 0) return; 7     int i = 0, root = post[n-1]; 8     for(; i<n; ++i) { 9         if(in[i] == root)   break;10     }11     printf(" %d", root);12     getpre(post, in, i);13     getpre(post+i, in+i+1, n-i-1);14 }15 16 int main()17 {18     int n, post[40], in[40];19     scanf("%d", &n);20     for(int i=0; i<n; ++i) {21         scanf("%d", &post[i]);22     }23     for(int i=0; i<n; ++i) {24         scanf("%d", &in[i]);25     }26 27     printf("Preorder:");28     getpre(post, in, n);29 30     return 0;31 }

// Fin

相关文章