数据结构期末考试试卷含答案一.pdfVIP

《数据结构》 期末考试 试卷和答案 期末考试 一 、简答问题：（每小题 4 分，共 16 分） 1． 四类数据结构 2． 线性结构与非线性结构有何差别？ 3 ． 简述算法的定义与特性。 4 ． 设有 1000 个无序元素，仅要求找出前 10 个最小元素，在 下列排序方法中（归并排序、基数排序、快速排序、堆排序、插 入排序）哪一种方法最好，为什么？ 二、判断正误：（每小题 1 分，共 5 分） 正确在（ ）内打√，否则打 。 1． （ ）二叉排序树或是一棵空树，或是具有下列性质 的二叉树： 若它的左子树非空，则根结点的值大于其 左孩子 的 值， 若它的右子树非空，则根结点的值大于其 右孩子 的 值。 2． （ ）索引顺序表的特点是块内可无序，块间要有序。 3 ． （ ）子串是主串中任意个连续字符组成的序列。 4 ． （ ）线性结构只能用顺序结构存放，非线性结构只 能用链表存放。 5． （ ）快速排序的枢轴元素可以任意选定。 三、单项选择题： (每小题 1 分，共 4 分) 1 S 4 6 A B C D E F ．栈 最多能容纳 个元素。现有 个元素按 、、、 、、 的顺 西北大学 《数据结构》 , ? 序进栈 问下列哪一个序列是可能的出栈序列 A)E D C B A F B)B C E F A D 、 、 、 、 、 、 、 、 、 、 C)C B E D A F D)A D F E B C 、 、 、 、 、 、 、 、 、 、 2 ．将一棵有 100 个结点的完全二叉树从根这一层开始，每一层 1 49 从左到右依次对结点进行编号，根结点编号为 ，则编号为 的结点的左孩子的编号为： A 98 B 99 C 50 D 48 、 、 、 、 3. 对下列关键字序列用快速排序法进行排序时，速度最快的情 形是： A {21 25 5 17 9 23 30} B {25 23 30 17 21 5 9} ） 、 、 、 、 、 、 ） 、 、 、 、 、 、 B {21 9 17 30 25 23 5} D {5 9 17 21 23 25 30} ） 、 、 、 、 、 、 ） 、 、 、 、 、 、 4. 设森林 F 中有三棵树，第一、第二和第三棵树的结点个数分别 M1 M2 M3 F 为 、 和 。与森林 对应的二叉树根结点的右子树上的结 点个数是： A ）M1 B）M1+M2 C）M3 D）M2+M3 四、填空题： (每小题 2 分,共 20 分) 1． 设一哈希表表长 M 为 100 ，用除留余数法构造哈希函数， H K =K MOD P P =M , P 即 （ ）