发布时间 : 星期一 文章第7章算法程序与计算系统之灵魂练习题答案解析更新完毕开始阅读8757ab91a300a6c30c229fc8
本题考查对树结构的理解。 “树”既需要存储数据元素本身即数据，还需要存储数据元素之间的关系。（A）的说法没有问题。用两个数组组织树形数据时，一个数组存放数据元素，另一个数组存储对应的父元素。用三个数组组织树形数据时，一个数组存放数据元素，剩下的两个数据，一个存放对应的左儿子，一个存放对应的右儿子。组织树形数据时，可以把每个元素当做一个节点，通过指针来指向其儿子。故（B）（C）（D）正确。（E）不正确。 详细内容请参考第七章视频“算法，程序与计算系统之灵魂”与第七章课件。
(2)参照上图(I)，下列说法不正确的是_____。
(A)当数据元素不发生变化，而只是数据元素之间的关系发生变化时，可以通过调整数据元素对应的左指针数组或右指针数组中的值来完成；
(B)当数据元素不发生变化，而只是数据元素之间的关系发生变化时，既需要调整数据元素本身，又需要调整其对应的左指针数组或右指针数组中的值来完成； (C)相同的数据元素，不同的左指针和右指针可以反映数据元素之间不同的关系； (D)图(a)说明，一个数据元素最多只能有两个子元素，一个是左子元素，一个是右子元素； (E)上述说法有不正确的。
答案：B 解释：
本题考查对树结构的理解。 “树”既需要存储数据元素本身即数据，还需要存储数据元素之间的关系。当数据元素不发生变化，而只是数据元素之间的关系发生变化时，数据本身是不需要调整的。(B)错误。其余说法均正确。 详细内容请参考第七章视频“算法，程序与计算系统之灵魂”与第七章课件。
(3)上图(I)表示的数据的逻辑关系，下列正确的是_____。
(A)图II.(a)； (B)图II.(b)； (C)图II.(c)； (D)图II.(d)；
图II.
答案：D 解释： 本题考查对树结构的理解。 第一个元素值为100。其左指针指向的存储单元的内容为地址：00000000 00000010。该地址存储的数据为50。故第一个元素100的左儿子为50。一次类推，可以画出（d）中的树。故（D）正确。 详细内容请参考第七章视频“算法，程序与计算系统之灵魂”与第七章课件。
(4)如想使图(I)，改变为存储下图III所示的逻辑关系，操作正确的是_____。
图III.
(A)将00000000 00001000号存储单元的值修改00000000 01101110(即十进制的110)； (B)将00000000 00011010号存储单元的值修改为00000000 00000111；
(C)将00000000 00010001号存储单元的值修改为00000000 00000000(即Null)； (D)将00000000 00010011号存储单元的值修改为00000000 00001000； (E)上述(A)(B)(C)(D)都需要正确完成；
答案：E 解释：
本题考查对树结构的理解。 想要得到题目要求，则需要改变的是100的右儿子的值。首先，增加110这个元素。这是（A）的操作。很容易知道，110这个元素对应的左指针指向00000000 00010001，将该单元的存储内容改为NULL，增加了110元素的左儿子为空。这是（C）的操作。然后将100元素的右指针指向110，这是（D）的操作。最后，将110的右指针指向150。这是（C）的操作。至此，整个过程完成。所以，（E）正确。 详细内容请参考第七章视频“算法，程序与计算系统之灵魂”与第七章课件。
(5)如想使图(I)，改变为存储下图IV所示的逻辑关系，下列四步操作都是需要的，但有些操作的内容却是不正确的。不正确的是_____。
图IV.
(A)将00000000 00001000号存储单元的值修改为00000000 01010101； (B)将00000000 00010010号存储单元的值修改为00000000 00000010；
(C)将00000000 00011010号存储单元的值修改为00000000 00000000(即Null)； (D)将00000000 00001010号存储单元的值修改为00000000 00001000；
答案：B 解释：
本题考查对树结构的理解。 (A)的操作是在存储表中增加85这个元素。（C）的操作是将85的右儿子设为NULL。（D）的操作是将100的左指针指向85元素的地址。（B）是对00000000 00010010地址进行操作。而改地址在整个过程中，通过其它选项来看，不会有涉及到（B）中的地址。故（B）不正确。 详细内容请参考第七章视频“算法，程序与计算系统之灵魂”与第七章课件。
8. 堆栈(stack)是一种特殊的串行形式的数据结构，其特殊支出在于只能允许在链结串行或阵列的一端（称为堆栈顶端指针，top）进行加入数据(push)或输出数据(pop)的运算。其示意图如下所示。
(1)有关堆栈数据结构的说法，不正确的是_____。
(A) 堆栈按照先进先出（FIFO, First In First Out）的原理运作； (B) 堆栈按照后进先出（LIFO, Last In First Out）的原理运作； (C) 堆栈可以使用顺序存储结构作为存储结构； (D) 堆栈可以使用链式存储结构作为存储结构。
答案：A 解释：
本题考查对堆栈结构的理解。 在堆栈中，先进栈的元素被保存在堆栈下部。在弹出元素时，栈顶的元素先被弹出。故堆栈运行的原理是后进先出。（A）不正确，（B）正确。堆栈可以使顺序存储结构和链式结构来实现。（C）（D）正确。 详细内容请参考第七章视频“算法，程序与计算系统之灵魂”与第七章课件。
(2) 有关堆栈数据结构的基本运算，说法不正确的是_____。
(A) 推入是将数据放入堆栈的顶端，堆栈顶端指针top加一； (B) 弹出是将堆栈顶端的数据取出，堆栈顶端指针top减一； (C) 如果堆栈顶端指针top为0，则堆栈为空；
(D) 如果是固定长度的堆栈，当堆栈顶端指针top与长度相等时，堆栈是满的。 (E) 上述说法有不正确的；
答案：E 解释：
本题考查对堆栈结构的理解。 堆栈只有一个出口，那便是栈顶。推入数据，是在堆栈的顶端推入，数据个数增加了一，栈顶指针加一，（A）正确。弹出数据，也是在堆栈的顶端弹出，数据个数减一，栈顶指针减一，（B）正确。栈顶指针的值代表了堆栈中数据的个数。栈顶指针为0，堆栈为空。栈顶指针为堆栈的固定长度，则堆栈是满的。（C）(D)均正确。故（E）的说法不正确。 详细内容请参考第七章视频“算法，程序与计算系统之灵魂”与第七章课件。
(3) 假定当前堆栈顶端指针top=10，欲将栈底的元素取出，其他的元素仍然保持在栈中，则需要进行___ ___次弹出操作，____ ____次推入操作。
(A) 1，1 (B) 2，1 (C) 10，9 (D) 10，0 (E) 11，8