文章目录
〇、前言
这周开始了【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,则其必为完美二叉树。
作者: 徐镜春
单位: 浙江大学
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/2
或n0=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 | PopS) | |
3,1 | 2 | PushS,3) |
2,3 | PopS) | |
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
在逻辑上位于 a
和 e
之间,则 a
、e
、f
的“链接地址”依次是:
答案:D
作者: DS课程组
单位: 浙江大学
f
在逻辑上位于a
和e
之间,则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、在一个不带头结点的非空 链式队列 中,假设 f
和 r
分别为队头和队尾指针,则插入 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~
回复【数据结构】即可获取我为你准备的大礼。
想看更多文(段)章(子),欢迎关注微信公众号「程序员管小亮」~