【2020-MOOC-浙江大学-陈越、何钦铭-数据结构】春期中考试(附每一个题目的详细解析)

文章目录

〇、前言一、判断题二、选择题三、程序填空题总结

〇、前言

这周开始了【MOOC-浙江大学-陈越、何钦铭-数据结构】的期中考试,感觉有点难,可能是我才学了一个月不到的原因???
在这里插入图片描述

一、判断题

1-1、用 邻接表 法存储图,占用的存储空间数只与图中结点个数有关,而与边数无关。
在这里插入图片描述
作者: DS课程组
单位: 浙江大学

邻接矩阵的空间复杂度为On2n^2),与边的个数无关。
邻接表的空间复杂度为On+en+e),与图中的结点个数和边的个数都有关。


1-2、在一棵由包含4、5、6等等一系列整数结点构成的 二叉搜索树 中,如果结点4和6在树的同一层,那么可以断定结点5一定是结点4和6的父亲结点。
在这里插入图片描述
作者: DS课程组
单位: 浙江大学

5是6的左子树节点就是一个反例。


1-3、如果无向图 G 必须进行两次 广度优先搜索 才能访问其所有顶点,则 G 一定有2个连通分量。
在这里插入图片描述
作者: DS课程组
单位: 浙江大学

连通分量:无向图的极大连通子图。
在这里插入图片描述
相似但是错误的说法:如果无向图G必须进行两次广度优先搜索才能访问其所有顶点,则G中一定有回路。


1-4、若一棵 平衡二叉树 的所有非叶结点的 平衡因子 都是0,则其必为完美二叉树。
在这里插入图片描述
作者: 徐镜春
单位: 浙江大学

平衡因子是0,代表着左右子树的高度一样。
在这里插入图片描述
在这里插入图片描述


1-5、若一个结点是某二叉树的 中序遍历序列 的最后一个结点,则它必是该树的 前序遍历序列 中的最后一个结点。
在这里插入图片描述
作者: DS课程组
单位: 浙江大学

假设:
A
/
B
中序是左一根一右顺序,前序是根一左一右顺序:

前序遍历序列为A-B;
中序遍历序列为B-A;

那么结点A是中序遍历序列的最后一个结点,但是它并不是前序遍历序列中的最后一个结点。
如果【若一个结点】改成【若一个叶子结点】,那么命题为真。


1-6、一棵有124个结点的 完全二叉树,其叶结点个数是确定的。
在这里插入图片描述
作者: DS课程组
单位: 浙江大学

在这里插入图片描述
124上限是128(272^7),下限是64(262^6),中间这些都可以是叶子结点数。
补充:
假设 n0 是度为0的节点总数(即叶子结点数),n1 是度为1的节点总数,n2 是度为2的节点总数。因为 n= n0+n1+n2(其中n为完全二叉树的节点总数),又因为一个度为2的节点会有2个子结点,一个度为1的结点会有1个子结点,除根结点外其他节点都有父结点,得到 n= 1+n1+2*n2;两式把 n2 消去得:n= 2*n0+n1-1,由于完全二叉树中度为1的结点数只有两种可能0或1,由此得到 n0=n/2n0=n+1)/2


1-7、算法 可以没有输入,但是必须有输出。
在这里插入图片描述
作者: 李廷元
单位: 中国民用航空飞行学院

在这里插入图片描述


1-8、通过对 堆栈 S操作:PushS,1), PushS,2), PopS), PushS,3), PopS), PopS)。输出的序列为:123。
在这里插入图片描述
作者: DS课程组
单位: 浙江大学

堆栈内的元素 输出的元素 执行的操作
1 PushS,1)
2,1 PushS,2)
2 ,1 2 PopS)
3,1 2 PushS,3)
3 ,1 2,3 PopS)
1 2,3,1 PopS)

1-9、在用数组表示的 循环队列 中,front 值一定小于等于 rear 值。
在这里插入图片描述
作者: DS课程组
单位: 浙江大学

循环队列!!!


1-10、在具有N个结点的单链表中,访问结点和增加结点的时间复杂度分别对应为 O1)ON)
在这里插入图片描述
作者: DS课程组
单位: 浙江大学

都是ON)。


二、选择题

2-1、下列哪个函数是ON)的?
在这里插入图片描述
答案:A
作者: DS课程组
单位: 浙江大学

在这里插入图片描述


2-2、先序遍历图示 二叉树 的结果为
在这里插入图片描述
在这里插入图片描述
答案:B
作者: DS课程组
单位: 浙江大学

先序遍历是根–左–右。


2-3、若某图的 深度优先搜索 序列是{V1, V4, V0, V3, V2},则下列哪个图不可能对应该序列?
在这里插入图片描述
答案:C
作者: 陈越
单位: 浙江大学

C应该是1,4,3,0,2。


2-4、已知一棵 完全二叉树 的第6层(设根为第1层)有8个叶结点,则该完全二叉树的结点个数最多是:
在这里插入图片描述
答案:C
作者: DS课程组
单位: 浙江大学

完全二叉树比起满二叉树,只是在最下面一层的右边缺少了部分叶结点,而最后一层之上是个满二叉树,并且只有最后两层上有叶结点。
第6层有叶结点,则完全二叉树的高度可能为6或7,显然树高为7时结点更多。若第6层上有8个叶结点,则前六层为满二叉树,而第7层缺失了8×2=16个叶结点,故完全二叉树的结点个数最多为 27−1−16=1112^7-1-16=111 个结点。


2-5、已知表头元素为c的 单链表 在内存中的存储状态如下表所示:
在这里插入图片描述
现将 f 存放于 1014H 处,并插入到单链表中,若 f 在逻辑上位于 ae 之间,则 aef 的“链接地址”依次是:
在这里插入图片描述
答案:D
作者: DS课程组
单位: 浙江大学

f 在逻辑上位于 ae 之间,则 a 的链接地址为1014,即 f 的地址,f 的链接地址为1010,即 e 的地址,其他的链接地址则不变。


2-6、对 最小堆(小顶堆) {1,3,2,12,6,4,8,15,14,9,7,5,11,13,10} 进行三次删除最小元的操作后,结果序列为:
在这里插入图片描述
答案:C
作者: DS课程组
单位: 浙江大学

硬算。


2-7、在一个不带头结点的非空 链式队列 中,假设 fr 分别为队头和队尾指针,则插入 s 所指的结点运算是 )。
在这里插入图片描述
答案:B
单位: 浙江大学城市学院

队列尾部插入元素。


2-8、表达式 a*b+c)-d后缀表达式 是:
在这里插入图片描述
答案:A
作者: DS课程组
单位: 浙江大学

后缀表达式。


2-9、一棵 二叉树 中,双分支结点数为15,单分支结点数为30,则叶子结点数为()个。
在这里插入图片描述
答案:B
作者: 严冰
单位: 浙江大学城市学院

在这里插入图片描述


2-10、在并查集问题中,已知集合元素0~8所以对应的父结点编号值分别是{ 1, -4, 1, 1, -3, 4, 4, 8, -2 }(注:−n表示树根且对应集合大小为n),那么将元素6和8所在的集合合并(要求必须将小集合并到大集合)后,该集合对应的树根和父结点编号值分别是多少?
在这里插入图片描述
答案:B
作者: DS课程组
单位: 浙江大学

在这里插入图片描述


2-11、设一段文本中包含字符{a, b, c, d, e},其出现频率相应为{3, 2, 5, 1, 1}。则经过哈夫曼编码后,文本所占字节数为:
在这里插入图片描述
答案:C
作者: DS课程组
单位: 浙江大学

在这里插入图片描述


2-12、下列函数

int func  int n )
{   int i = 0, sum = 0;
    while  sum < n )  sum += ++i;
    return i;
}

的时间复杂度是:
在这里插入图片描述
答案:B
作者: 考研试卷
单位: 浙江大学

进行t次循环后,sum = k+1)*k/2 < n,左侧约等于 k*k,则 t 等于 sqrtn),时间复杂度为On1/2)n^{1/2)})。


三、程序填空题

1、下列代码的功能是返回带头结点的单链表 L 的逆转链表。

List Reverse List L )
{
    Position Old_head, New_head, Temp;
    New_head = NULL;
    Old_head = L->Next;
    while  Old_head )  {
        Temp = Old_head->Next;
		Old_head->Next=New_head;	//需要填写的语句
        New_head = Old_head;  
        Old_head = Temp; 
    }
	L->Next=New_head;				//需要填写的语句
    return L;
}

以前我们用漫画讲过,可以自行查看,【手绘漫画】面试必考之图解逆转单链表/单链表逆序


2、下列代码的功能是将大顶堆 H 中指定位置 P 上的元素的整数键值上调 D 个单位,然后继续将 H 调整为大顶堆。

void IncreaseKey int P, int D, PriorityQueue H )
{
   int i, key;
   key = H->Elements[P] + D;
   for  i = P;								//需要填写的语句
   		H->Elements[i/2] < key;
   		i/=2 )  
		H->Elements[i] = H->Elements[i/2];	//需要填写的语句
	H->Elements[i] = key;
}

与插入类似。
在这里插入图片描述

总结

简单总结下,光看课和课件是不够的的,还是建议看看课程的书。
在这里插入图片描述
我放在公众号里了,欢迎自行去取!

回复【浙江大学】即可获得,这可是我花了积分在CSDN上下的啊!!!

在这里插入图片描述

如果有幸帮到你,请帮我点个【赞】,给个【关注】!如果能顺带【评论】给个鼓励,我将不胜感激。

如果想要更多的资源,欢迎关注 @我是管小亮,文字强迫症MAX~

回复【数据结构】即可获取我为你准备的大礼。

想看更多文(段)章(子),欢迎关注微信公众号「程序员管小亮」~

在这里插入图片描述

Published by

风君子

独自遨游何稽首 揭天掀地慰生平

发表回复

您的电子邮箱地址不会被公开。 必填项已用 * 标注