南京信息工程大学期末试卷2019 -2020 学年第1 学期《数据结构》课程试卷A
本试卷共 5 页;考试时间120分钟;出卷:数据结构课程组;出卷时间2019 年12 月
学院专业年级班学号姓名得分
一、单项选择题(每小题 2 分,共20 分)
1. 下面程序段的时间复杂度是()。
i=s=0;
while(s<n){
i=1; s+=i;
}
log n) D. O(2n)
A. O(n)
B. O(n2)
C. O(
2
2. 数组A[0..5,0..6]的每个元素占5个字节,将其按列优先次序存储在起始地址为1000的内存
单元中,则元素A[5][5]的地址是()。
A. 1205
B. 1200
C. 1180
D. 1175
3. 针对任何一棵非空二叉树进行遍历,若限定先左后右的次序,则先序、中序和后序遍历
序列中,叶子结点之间的相对次序()。
A. 发生改变
B.保持不变
C. 不能确定
D. 以上都不对
4. 将长度为n的单链表链接在长度为m的单链表之后的算法的时间复杂度为()。
A. O(1)
B. O(n)
C. O(m)
D. O(m+n)
5. 若数据元素序列11, 12, 13, 7, 8, 9, 23, 4, 5是采用下列排序方法之一得到的第2趟排序后的
结果,则该排序算法只能是()。
A. 冒泡排序
哈夫曼编码树的带权路径长度B. 插入排序
C. 选择排序
D. 二路归并排序
6. 假设栈初始为空,将表达式a/b+(c*d-e*f)/g转换为后缀式的过程中,当扫描到f 时,栈
中的元素从栈底到栈顶依次是()。
A. # / + ( * - *
B. # / + - *
C. # + ( - *
D. # + ( * -
7. 用顺序存储的方法,将完全二叉树中n个结点,按层逐个从上到下、从左到右的顺序存放
在一维数组-1]中。若结点R[i]有左孩子,则存放左孩子的数组元素是()。
A. R[2i-1]
B. R[2i+1]
C. R[2i]
D. R[2/i]
8. 由关键字序列 (15,6,17,5,9,16,4,7,12,18,8) 来构造平衡二叉树,在构造平
衡二叉树时有可能失去平衡,则需要做( )调整,使得二叉排序树由不平衡转化为平衡。
A. 先左旋后右旋
B. 先右旋后左旋
C. 单向左旋
D. 单向右旋
9. 针对下面的有向图进行拓扑排序,则拓扑排序的结果序列是( )。
A. 125634
B. 516234
C. 123456
D. 521643
10. 若需要在O(2nlog n )的时间内完成对数组的排序,且要求排序是稳定的,则可选择的排
序方法是( )。
A. 快速排序
B. 堆排序
C. 归并排序
D. 直接插入排序
二、填空题 (每空 2 分,共 20 分)
1. 已知一棵完全二叉树的第6层(设根为第1层)有8个叶子结点,则该完全二叉树的结
点个数最多有 (1) 个。
2. 已知关键字序列为:5, 8, 12, 19, 28, 20, 15, 22是小顶堆,现在插入关键字3,则调整后
得到的小顶堆为 (2) 。
4. 用希尔排序方法对一个数据序列进行排序时,若第1趟排序结果为:9,1,4,13,7,8,20,23,15,
则该趟排序采用的增量d (15d ≤≤)的值可能为: (4) 。
5. 针对下图所示的有向网,若采用迪杰斯特拉(Dijkstra )算法,求源点a 到其他各个顶点
的最短路径。已知得到的第一条最短路径的目标顶点为b ,第二条最短路径的目标顶点为c ,
则按最短路径从小到大,后续得到的其余各个最短路径的目标顶点依次为 (5) 。
6. 设F 是一个森林,B 是由F 转换得到的二叉树,F 中有n 个非终端结点,则B 中右指针
域为空的结点有 (6) 个。
7. 在对n 个数据对象进行的二路归并排序中,整个归并过程的时间复杂度为是
(7) 。
8. 设栈S 和队列Q 的初始状态均为空,元素abcdefg 依次进入栈S 。若每个元素出栈后立即
进入队列Q ,且7个元素出队列的顺序是bdcfeag ,则栈S 的容量至少能存放 (8) 个元素 。
9. 已知可以利用栈将原表达式转换为后缀式,在将表达式a+b-a*((c+d)/e-f)+g 转换为后
缀式ab+acd+e/f-*-g+的过程中,同时保存在栈中的操作符(包括左括号和#号)的最大个
数是 (9)___。
10. 已知一个6 5的稀疏矩阵的三元组表示(按行序从小到大排列)如下图所示(i 表示行,
j 表示列,e 表示非零元的值),则该矩阵的转置矩阵的三元组表示(按行序从小到大排列)
是 (10)___。
三、判断题 (每题 2 分,共 10 分,错误打“×”,正确打“√” )
1. 已知一棵二叉树的先序和后序序列,则一定能够唯一确定该二叉树的形状。 ( )
2. 向一棵二叉排序树中插入一个新结点,则该结点一定为叶子结点。 ( )
3. 设某堆中有n 个结点,则在该堆中插入一个新结点的时间复杂度为2()O log n 。 ( )
4. 如果某个有向图的逆邻接表中第i 条单链表为空,则第i 个顶点的出度为零。 ( )
5. 用边表示活动的网络(AOE 网)的关键路径是指从源点到终点的路径长度最长的路径。
( )
四、应用题(本大题有8小题,共 40 分,每小题5分)
1. (5分)下图是一个工程项目的活动图,其中顶点表示活动开始或结束,弧表示包含的
活动,弧上的权值表示完成该活动所需的时间,请重画该图,并在每条弧的下方或上方标
注出该活动的最早发生时间和最迟发生时间(具体格式为:A|B ,A 代表最早发生时间,B
代表最迟发生时间);画出该图的所有关键路径,并计算该工程的工期。
2.(5分)已知一个图的顶点集V和边集E分别为:V={1,2,3,4,5,6,7};
E={<2,1>,<3,2>,<3,6>,<4,3>,<4,5>,<5,1>,<5,7>,<6,1>,<6,2>,<6,5>};
若采用邻接表存储它,并且每个顶点邻接表中的边结点,都是按照顶点序号从小到大的次序链接的。请:
(1)试画出该图;
(2)试给出该图所有可能的拓朴排序的序列。
3. (5分)已知下图为某个连通图的深度优先遍历生成树(从顶点A出发),其中虚线为回边。请:判断该连通图是否为重连通图?如果不是,哪些顶点是关节点?
4. (5分)假设某符号集X中包含5个符号:(s1,s2,s3,s4,s5),它们在报文中各自出现的频率分别为:(3,5,7,9,11)。试:
(1)画出该哈夫曼树(结点按照权值左小右大排列);
(2)写出各个符号的哈夫曼编码(按照左分支标“0”,右分支标“1”的方式编码);(3)计算该树的带权路径长度WPL。
5. (5分)已知关键字集合{ 30,29,04,14,05,21 },设哈希函数为:H(key) = key MOD 7 ( 表长=7 ),请画出分别采用下列两种处理“哈希冲突”的方法创建的哈希表:(1)二次探测再散列(又称平方探测再散列); (2)链地址法;并请分别计算这两个哈希表的ASL。
6. (5分)下图为一棵由森林转换过来的二叉树,请问:
(1)该二叉树由几棵树转换过来?
(2)请画出由下列二叉树转换成的森林。
7. (5分)已知下图表示一个通讯网络,边表示城市间的通讯线路,边上的权表示架设线路花费的代价,选择能连通每个城市且总代价最省的n-1条线路,请使用克鲁斯卡尔方法,画出该网的最小生成树的产生过程,并计算出总最小代价MinCost。
8. (5分)已知一组记录的关键码为(49,38,65,97,76,13,27,49),现采用快速
排序的方法,每趟都以待排序区间内的第一个记录为枢轴,请写出第1趟和第2趟快速排序后的结果。
五、算法填空题(共10 分,2分/空)
下面为希尔排序算法的伪代码描述,请填空完成该算法。其中,dk为每趟希尔排序所采用的增量。
void ShellInsert( SqList &L , int dk ) { // 对顺序表L作1趟希尔插入排序
for ( i=dk+1; i<=L.length; ++i ) // L.length为顺序表中元素的个数
if( L.elem[i] < L. elem [i-dk] ){ // L.elem指向顺序表的基地址
L. elem [0] = (1) ; // 暂存第i个元素
for ( j=i-dk; j>0 && (2) ; j -=dk )
(3) =L.elem[j]; //记录后移,查待插入位置
L.elem[j+dk] = (4) ; //插入
}
} // ShellInsert
void ShellSort ( SqList &L ) { //对顺序表L作希尔插入排序
int dlta[3], t=3 ; // t表示希尔排序的总趟数,dlta存放每趟希尔排序的增量
for( i=0; i<t ; i++){
scanf( “%d”, &dlta[i] );
ShellInsert( L, (5) );
}
} // ShellSort
版权声明:本站内容均来自互联网,仅供演示用,请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198,我们将在24小时内删除。
发表评论