数据结构期中复习参考题2008-4.docVIP

数据结构期中复习参考题 一， 简单题 1．从逻辑上可以把数据结构分成 A．动态结构和静态结构 B．顺序结构和链接结构 C．线性结构和非线性结构 D．初等结构和组合结构 【答】C。 2．下面哪一个术语与数据的存储结构无关？ A．顺序表 B．链表 C．散列表 D．队列 【答】D。 3．算法原则上都是能够由机器或人完成的。整个算法好像是一个解决问题的“工作序列”，其中的每一步都是我们力所能及的一个动作。这是算法的 A．正确性 B．有穷性 C．确定性 D．可行性 【答】D。 4．线性表的顺序存储是通过 ① 来反映数据元素之间的逻辑关系，而链式存储结构是通过 ② 反映数据元素之间的逻辑关系。 【答】① 前后顺序；② 指针或者引用关系。 5． ① 的线性表叫顺序表， ② 的线性表叫链表。 【答】① 元素顺序存储在一片相邻的存储区域中；② 元素位置没有顺序，通过指针链接。 6．在一个单链表中，若p所指结点不是最后结点，在p之后插入s所指结点，则执行 。 A. s-link=p; p-link=s; B. s-link=p-link; p-link=s; C. s-link=p-link; p=s; D. p-link=s; s-link=p; 【答】B。 7. 向栈顺序地输入一个整数序列1, 2, 3, 4, 5, 6，问是否可能得到如下的输出序列： （1）3, 2, 5, 6, 4, 1 【答】能。 （2）1, 5, 4, 6, 2, 3 【答】不能。 8．树和二叉树都是分支结构。 【答】正确。 9 ．二叉树是度为2的树。 【答】错误。 10 ．如果给定一个二叉树的先根序列和后根序列，则此二叉树即可惟一确定。 【答】错误。 11．二叉树与树林之间可以建立一一对应关系。 【答】正确。 12 ．二叉树中，具有两个子女的结点的中根后继结点最多只能有一个子女。 【答】正确。 13 ．满二叉树的结点个数必为奇数。 【答】正确。 14．树林的后根次序周游序列，等同于该树林对应二叉树的什么周游序列？ A. 先根周游序列 B. 后根周游序列 C. 对称序（中根）周游序列 D. 上述三种都不是 【答】C。 15．二叉树结点的后根序列： A．等同于该二叉树对应的树林结点的先根次序序列 B．等同于该二叉树对应的树林结点的后根次序序列 C．等同于该二叉树对应的树林结点的层次次序序列 D．不等同于上述任何一种序列 【答】D。 16 ．已知某二叉树的后根周游序列是DABEC，中根周游序列是DEBAC，它的先根周游序列是（ ）。 A. ACBED B. DECAB C. DEABC D. CEDBA 【答】D。 17 ．如果把由树转化得到的二叉树叫做这棵树对应的二叉树。下面结论中（ ）是正确的。 A. 树的先根周游序列与其对应的二叉树的先根周游序列相同 B. 树的后根周游序列与其对应的二叉树的后根周游序列相同 C. 树的先根周游序列与其对应的二叉树的中根周游序列相同 D. 以上都不对 【答】A。 18．设只包含根结点的二叉树的高度为0，则高度为k的二叉树的最大结点数为 A. 2 k B. 2 k+1?1 C. 2 k+1 D. 2 k?1+1 【答】B。 19 ．给定一个整数集合{3, 5, 6, 9, 12}，下列二叉树哪个是该整数集合对应的哈夫曼树？ 【答】C。 20 . 具有n个结点的满二叉树，其叶结点的个数为________。 【答】（符号表示不小于x的最小整数）。 21 . 采用链式方法存储N个结点的二叉树，该二叉树中共有 ① 个指针域，其中非空指针 ② 个。 【答】① 2N；②N?1。 22. 对某二叉树进行先根周游的结果为ABDEFC，中根（对称序）周游的结果为DBFEAC，则后根周游的结果为 ① ，对该二叉树对应的树林进行层次周游的结果为 ② 。 【答】① DFEBCA；② ABCDEF。 23 . 已知某二叉树的后根序列为ZXYW，对称序序列为ZXWY，它的先根序列是 ① 【答】① WXZY。  二， 问答题 1 ．算法与程序有什么区别。 【答】算法与程序的关系十分密切，但并不一样。一般来说，一个程序并不需要满足算法的有穷性等条件，例如操作系统的程序，只要整个系统不遭破坏，操作系统程序就永不结束。另外，程序是用机器可执行的语言书写的，而算法通常并没有这种限制。 2 ．用大“O”表示法描述下列复杂度： A．5n5/2 + n2/5 B．6*log2(n) + 9n C．3n4+ n* log2(n)