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指针，如下所示
在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
分析：
选项，获得1左输入右输入、2右输入、3左输入、4左输入、5左输入、5、4、3、1、2
b选项，1左输入右输入均获得2右输入、3左输入、4右输入、5左输入、5、3、1、2、4
选项，1左输入右输入都得到2左输入、3右输入、4左输入、5右输入、4、2、1、3、5
d选项，1左入右出，2右入，错误，3不是1和2之间的
3、已知二维阵列a以行优先存储，其中每个元素占用一个存储单元，起始地址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的情况下，f中的树为()、d、a、e、g、c、f
A.1
B.2
C.3
D.4
答案： c
分析：
在本问题中，研究基于树的扫描序列构建唯一的二叉树，并将二叉树转换为相应的森林。
首先做二叉树：
根据孩子的兄弟表示法转换为对应的森林：
有三棵树，可以选择c
5、zzdxhd二叉树有5个叶节点，其权重分别为10、12、16、21、30。 其最小带宽路径长度(WPL )为)
A.89
B.200
C.208
D.289
答案： b
分析：
本题是调查哈夫曼树的结构和WPL的计算
选择wpl=(162130 )2) 1012 ) *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-ne
xt=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、 zzdxhd二叉树有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