408计算机试卷结构,2021年考研计算机408数据结构试题与解
析（回忆版）
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
1、 使⽤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
北京事业单位考试网
2、 在⼀棵⾼度为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
第⼀趟分配：
1
考研计算机真题2
3
4
5
6
7
8
9
151
301
安徽省公务员考试网上报名入口372
372
892
093
043
485
946
146
236
009
第⼀趟收集：
151，301，372，372，892，093，043，485，946，146，236，009(元素372之前，之后相邻的元素分别是301，892，选C)
第⼆趟分配：
1
2
3
4
5
6
7
8
9
301
009
236
143
发布评论