2021年全国硕士研究生招生考试已经结束,大家可以适当的休息两天,接下来就是准备复试的时候了。上海 考研网小编给大家整理了“2021年408数据结构试题与解析”的内容,一起来看一下吧~1、 已知指针指向一个带头结点的非空单循环链表,结点结构data、next,其中next是指向直接后继结点的指针,p是尾指针,q是临时指针。现要删除该链表的第一个元素,正确的语句序列是()
a. h->next=h->next->next;q=h->next;free(q);
b. q=h->next;h->next=h->next->next;free(q);
c. q=h->next;h->next=q->next;if(p!=q)p=h;free(q);
d. q=h->next;h->next=q->next;if(p=q)p=h;free(q);
答案:d
解析:
a选项中,h->next=h->next->next修改了头结点的后继,q指
针指向的不是待删除的第一个结点,a错;
b选项中,假设这个链表中只剩下最后一个结点(即尾指针p指向的结点),q=h->next q指针指向带删除的第一个结点(最后一个结点),则删除后,还需要修改p指针,b错;
c、d选项中,q=h->next;h->next=q->next,q指针指向待删除的第一个结点,头结点指向第二个结点,此时若尾指针p和q指针指向同一个位置的话,则我们需要修改尾指针p,将其指向头结点(空单循环链表),则选d
2、 已知初始为空的队列q的一端能进行入队操作又能进行出队操作,另一端能进行入队操作,若a的入队序列是1,2,3,4,5,则不可能得到的出队序列是()
a.5,4,3,1,2
b.5,3,1,2,4
c.4,2,1,3,5
d.4,1,3,2,5
答案:d
解析:
a选项,1左入右入都可,2右入,3左入,4左入,5左入,得到5,4,3,1,2
b选项,1左入右入都可,2右入,3左入,4右入,5左入,得到5,3,1,2,4
c选项,1左入右入都可,2左入,3右入,4左入,5右入,得到4,2,1,3,5
d选项,1左入右入都可,2右入,错误,3不可能在1和2的中间
3、 已知二维数组a按行优先方法存储,每个元素占用1个存储单元,起始地址a[0][0]为100,若元素a[3][3]的存储地址是220,则元素a[5][5]的存储地址是()
a.295
b.300
c.301
d.306
答案:b
解析:
首先分析题干信息,按行优先方法存储,二维数组的行、列下标都是从0开始,并且已知起始存储地址为100,假设二维数组有n行m列。
loc(a[3][3])= loc(a[0][0])+(3*m+4-1)*1=220,可以求出m=39
则loc(a[5][5])= loc(a[0][0])+(5*39+6-1)*1=300,选b
4、 某森林f对应的二叉树为t,若t的先序遍历序列是a,b,d,c,e,g,f,中序遍历序列是b,d,a,e,g,c,f,则f中树的棵树是()
a.1
b.2
c.3
d.4
答案:c
解析:
本题考查根据树的遍历序列构造一个唯一的二叉树,再将二叉树转换成对应的森林。
首先先构造二叉树:
根据孩子兄弟表示法转换成对应的森林:
则可以得到有3棵树,选c
5、 若某二叉树有5个叶子结点,其权值分别为10,12,16,21,30。则其最小的带权路径长度(wpl)是()
a.89
b.200
c.208
d.289
答案:b
解析:
本题考查哈夫曼树的构造,以及wpl的计算
wpl=(16+21+30)*2+(10+12)*3=200,选b
6、 给定平衡二叉树如下图所示,放入关键字23后根中的关键字是()
a.16
b.20
c.23
d.25
答案:d
解析:
插入23后,树的形态如下:
则根节点20不平衡,平衡因子为1-3=-2,则需要旋转调整后,得到平衡二叉树如下:
根为25,选d
7、 给定如下有向图,该图的拓扑有序序列的个数是()
a.1
b.2
c.3
d.4
答案:a
解析:
拓扑排序解决步骤如下:
(1)在有向图中选一个没有前驱(入度为0)的顶点且输出之。
(2)从图中删除该顶点和所有以它为尾的弧。
重复上述两步,直至全部顶点均已输出,或者当前图中不存在无前驱的顶点为止。后一种情况则说明有向图中存在环。
根据此有向图,可得到拓扑排序序列只有一个:abcdef
8、 使用dijkstra算法求下图中从顶点1到其余个顶点的最短路径,将当前找到的从顶点1到顶点2,3,4,5的最短路径长度保存在数组dist中,求出第二条最短路径后,dist中的内容更新为()没有图暂时无法给出答案与解析,后续补上
a.26,3,14,6
b.25,3,14,6
c.21,3,14,6
d.15,3,14,6
9、 在一棵高度为3 的3阶b树中,根为第一层,若第二层有4个关键字,则该树的结点个数最多是()
a.11
b.10
c.9
d.8
答案:a
解析:
根据b树的定义,3阶b树满足:除根之外的所有非终端节点至少有2棵子树;所有非终端结点的关键字个数n的取值范围为:1<=n<=2
已知根为第一层,若第二层有4个关键字,则该树第一层1个结点,3个分支,第二层3个结点,由于有4个关键字,所以3个结点的分支树分别为2,2,3,第三层7个结点。
总结点个数最多为1+3+7=11个,选a
11、设数组s={ 93,946,372,9,146,151,301,485,236,372,43,892},采用最低位优先(lsd)基数排序将s排列成升序序列,第一趟分配收集后,元素372之前,之后相邻的元素是()
a.43,892
b.236,301
c.301,892
d.485,301
答案:c
解析:
93,946,372,9,146,151,301,485,236,372,43,892
r=10
第一趟分配:
0
1
2
3
4
5
6
7
8
9
151
301
372
372
892
093
043
485
946
146
236
009
第一趟收集: