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、忧池二叉树有5个叶节点,其权重分别为10、12、16、21、30。 其最小带宽路径长度(WPL )为)
A.89
B.200
C.208
D.289
答案: b
分析:
本题是调查哈夫曼树的结构和WPL的计算
选择wpl=(162130 )2) 1012 ) *3=200,b