[计算机类试卷]数据结构与算法练习试卷3及答案与解析.doc

1、数据结构与算法练习试卷 3及答案与解析 1 以下关于顺序存储结构的叙述中，哪一条是不正确的 ?_。 （ A）存储密度大 （ B）逻辑上相邻的节点物理上不必邻接 （ C）可以通过计算直接确定第 i个节点的存储地址 （ D）插入、删除运算操作不方便 2 单键表的每个节点中包括一个指针 link，它指向该节点的后继节点。现要将指针q指向的新节点插入到指针 p指向的单链表节点之后，下面的操作序列中哪一个是正确的 ?_。 （ A） q： =p.link； p.link： =q.link； （ B） p.link： =q.link； q： =p.link； （ C） q.link： =p.link； p.

2、link： =q； （ D） p.link： =q； q.link： =p.link； 3 设有下三角矩阵 A0 10,0 10，按行优先顺序存放其非零元素，每个非零元素占两个字节，存放的基地址为 100，则元素 A5,5的存放地址为 _。 （ A） 110 （ B） 120 （ C） 130 （ D） 140 4 栈 S最多能容纳 4个元素。现有 6个元素按 A、 B、 C、 D、 E、 F的顺序进栈，下列哪一个序 列不是可能的出栈序列 ? _。 （ A） A、 D、 E、 C、 B、 F （ B） A、 F、 E、 D、 C、 B （ C） C、 B、 E、 D、 A、 F （ D） C、

3、 D、 B、 F、 E、 A 5 霍夫曼算法可以用于 _。 （ A）动态存储管理 （ B）表达式求值 （ C）数据通信的二进制编码 （ D）城市间的交通网设计 6 设待排序关键码序列为 (25， 18， 9， 33， 67， 82， 53， 95， 12， 70)，要按关键码值递增的顺序进行排序，采取以第一个关键码为分界元素的快速排序法，第一趟完成后关键码 33被放到了第几个 位置 ?_。 （ A） 3 （ B） 5 （ C） 7 （ D） 9 7 下列排序方法中，哪一种方法的总的关键码比较次数与记录的初始排列状态无关 ?_。 （ A）直接插入排序 （ B）起泡排序 （ C）快速排序 （ D）

4、直接选择排序 8 以下关于数据的存储结构的叙述中哪一条是正确的 ?_。 （ A）数据的存储结构是数据间关系的抽象描述 （ B）数据的存储结构是逻辑结构在计算机存储器中的实现 （ C）数据的存储结构分为线性结构和非线性结构 （ D）数据的存储结构对数据运算的具体实现没有 影响 9 以下关于队列的叙述中哪一条是不正确的 ?_。 （ A）队列的特点是先进先出 （ B）队列既能用顺序方式存储，也能用链接方式存储 （ C）队列适用于二叉树对称序遍历算法的实现 （ D）队列适用于树的层次次序遍历算法的实现 10 单链表的每个节点中包括一个指针 link，它指向该节点的后继节点。现要将指针 q指向的新节点插

5、入到指针 p指向的单链表节点之后，下面的操作序列中哪一个是正确的 ? _。 （ A） q： =p.link； p.link： =q.link； （ B） p.link： =q.link； q： =p.link； （ C） q.link： =p.link； plink： =q； （ D） p.link： =q； q.link： =p.link； 11 在顺序表 (3， 6， 8， 10， 12， 15， 16， 18， 21， 25， 30)中，用二分法查找关键码值 11，所需的关键码比较次数为 _。 （ A） 2 （ B） 3 （ C） 4 （ D） 5 12 设散列表的地址空间为 0 10，

6、散列函数为 h(k)=k mod 11，用线性探查法解决碰撞。现从空的散列表开始，依次插入关键码值 95， 14， 27， 68， 82，则最后一个关键码 82的地址为： _。 （ A） 4 （ B） 5 （ C） 6 （ D） 7 13 设待排序关键码序列为 (25， 18， 9， 33， 67， 82， 53， 95， 12， 70)，要按关键码值递增的顺序进行排序，采取以第一个关键码为分界元素的快速排序法，第一趟完成后关键码 96被放到了第几个位置 ?_。 （ A） 7 （ B） 8 （ C） 9 （ D） 10 14 设平衡的二叉排序树 (AVL树 )的节点个数为 n，则其平均检索长度

7、为 _。 （ A） O(1) （ B） O(log2n) （ C） O(n) （ D） O(nlog2n) 15 对于给出的一组权 w=10,12,16,21,30，通过霍夫曼算法求出的扩充二叉树的带权外部路径长度为 _。 （ A） 89 （ B） 189 （ C） 200 （ D） 300 16 如果一棵二叉树节点的前序序列是 A、 B、 C，后序序列是 C、 B、 A，则该二叉树节点的对称序序列 _。 （ A）必为 A、 B、 C （ B）必为 A、 C、 B （ C）必为 B、 C、 A （ D）不能确定 17 二维数组 A0 8， 0 9，其每个元 素占 2个字节，从首地址 400开始

8、，按行优先顺序存放，则元素 A8， 5的存储地址为 _。 （ A） 570 （ B） 506 （ C） 410 （ D） 482 18 以下哪一个不是栈的基本运算 _? （ A）删除栈顶元素 （ B）删除栈底元素 （ C）判断栈是否为空 （ D）将栈置为空栈 19 以下关于数据结构的基本概念的叙述中哪一条是错误的 ?_。 （ A）数据元素是数据的基本单位 （ B）数据项是有独立含义的数据最小单位 （ C）数据结构概念包含的主要内容是数据的逻辑结构和数据的存储结构 （ D）数据的逻辑结构分为线性结构和非线性结构 20 以下关于链式存储结构的叙述中哪一条是错误的 ?_。 （ A）节点除自身信息外还

9、包括指针域，因此存储密度小于顺序存储结构 （ B）逻辑上相邻的节点物理上不必邻接 （ C）可以通过计算直接确定第 i个节点的存储地址 （ D）插入、删除运算操作方便，不必移动节点 21 栈结构不适用于下列哪一种应用 ? _。 （ A）表达式求值 （ B）树的层次次序遍历算法的实现 （ C）二 叉树对称序遍历算法的实现 （ D）快速排序算法的实现 22 设根节点的层次为 0，则高度为 k的二叉树的最大节点数为 _。 （ A） 2k （ B） 2k-1 （ C） 2k+1 （ D） 2k+1-1 23 对线性表进行二分法查找，其前提条件是 _。 （ A）线性表以顺序方式存储，并已按关键码值排好序

10、（ B）线性表以顺序方式存储，并已按关键码值的查找频率排好序 （ C）线性表以链接方式存储，并已按关键码值排好序 （ D）线性表以链接方式存储，并已按关键码值的查找频率排好序 24 在包含 1000个元素的线性表中实现如下各运算，哪一个所需的执行时间最长 ?_。 （ A）线性表按顺序方式存储，在线性表的第 10个节点后面插入一个新节点 （ B）线性表按链接方式存储，在线性表的第 10个节点后面插入一个新节点 （ C）线性表按顺序方式存储，删除线性表的第 990个节点 （ D）线性表按链接方式存储，删除指针 p所指向的节点 25 下列问题基于如下描述：现有关键码值分别为 10、 20、 30、

11、40的 4个节点，按所有可能的插入顺序去构造二叉排序树。 25 能构造出多少棵不同的二叉排序树 ?_。 （ A） 24 （ B） 14 （ C） 10 （ D） 8 26 这些二叉排序树中有多少棵是最佳二叉排序树 ?_。 （ A） 6 （ B） 5 （ C） 4 （ D） 3 27 下列问题基于下面的叙述；某二叉树节点的前序序列为 E、 A、 C、 B、 D、 G、F，对称序序列为 A、 B、 C、 D、 E、 F、 G。 27 该二叉树节点的后序序列为 _。 （ A） B、 D、 C、 A、 F、 G、 E （ B） B、 D、 C、 F、 A、 G、 E （ C） E、 G、 F、 A、

12、C、 D、 B （ D） E、 G、 A、 C、 D、 F、 B 28 该二叉树对应的树林包括多少棵树 ?_。 （ A） 1 （ B） 2 （ C） 3 （ D） 4 数据结构与算法练习试卷 3答案与解析 1 【正确答案】 B 【知识模块】 数据结构与算法 2 【正确答案】 C 【知识模块】 数据结构与算法 3 【正确答案】 D 【知识模块】 数据结构与算法 4 【正确答案】 B 【知识模块】 数据结构与算法 5 【正确答案】 C 【知识模块】 数据结构与算法 6 【正确答案】 D 【知识模块】 数据结构与算法 7 【正确答案】 B 【知识模块】 数据结构与算法 8 【正确答案】 B 【知识模

13、块】 数据结构与算法 9 【正确答案】 C 【知识模块】 数据结构与算法 10 【正确答案】 C 【知识模块】 数据结构与算法 11 【正确答案】 C 【知识模块】 数据结构与算法 12 【正确答案】 C 【知识模块】 数据结构与算法 13 【正确答案】 B 【知识模块】 数据结构与算法 14 【正确答案】 B 【知识模块】 数据结构与算法 15 【 正确答案】 C 【知识模块】 数据结构与算法 16 【正确答案】 D 【知识模块】 数据结构与算法 17 【正确答案】 A 【知识模块】 数据结构与算法 18 【正确答案】 B 【知识模块】 数据结构与算法 19 【正确答案】 A 【知识模块】 数据结构与算法 20 【正确答案】 C 【知识模块】 数据结构与算法 21 【正确答案】 B 【知识模块】 数据结构与算法 22 【正确答案】 D 【知识模块】 数据结构与算法 23 【 正确答案】 A 【知识模块】 数据结构与算法 24 【正确答案】 A 【知识模块】 数据结构与算法 25 【正确答案】 B 【知识模块】 数据结构与算法 26 【正确答案】 B 【知识模块】 数据结构与算法 27 【正确答案】 A 【知识模块】 数据结构与算法 28 【正确答案】 B 【知识模块】 数据结构与算法