计算机专业数据结构试题答案,2021考研计算机408数据结构试
题及答案解析
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
91人才网招聘工作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
解析：
本题考查根据树的遍历序列构造⼀个唯⼀的⼆叉树，再将⼆叉树转换成对应的森林。
⾸先先构造⼆叉树：
根据孩⼦兄弟表⽰法转换成对应的森林：
天津市2023年公务员考试公告
则可以得到有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
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]的存储地址是()
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
2023年国考招考职位表C．3
D．4
答案：C
解析：考研计算机真题
本题考查根据树的遍历序列构造⼀个唯⼀的⼆叉树，再将⼆叉树转换成对应的森林。
⾸先先构造⼆叉树：
根据孩⼦兄弟表⽰法转换成对应的森林：
则可以得到有3棵树，选C
5、 若某⼆叉树有5个叶⼦结点，其权值分别为10，12，16，21，30。则其最⼩的带权路径长度(WPL)是()
A．89
B．200
解析：
本题考查哈夫曼树的构造，以及WPL的计算
WPL=(16+21+30)*2+(10+12)*3=200，选B