数据结构10套卷

2018最新十套数据结构试题及答案汇编

2018数据结构试题（一） ........................................................................................... 1 2018数据结构试题（二） ........................................................................................... 5 2018数据结构试题（三） ........................................................................................... 8 2018数据结构试题（四） ......................................................................................... 11 2018数据结构试题（五） ................................................................

2018最新十套数据结构试题及答案汇编

2018数据结构试题（一） ........................................................................................... 1 2018数据结构试题（二） ........................................................................................... 5 2018数据结构试题（三） ........................................................................................... 8 2018数据结构试题（四） ......................................................................................... 11 2018数据结构试题（五） ................................................................

2018最新十套数据结构试题及答案汇编

2018数据结构试题（一） ........................................................................................... 1 2018数据结构试题（二） ........................................................................................... 5 2018数据结构试题（三） ........................................................................................... 8 2018数据结构试题（四） ......................................................................................... 11 2018数据结构试题（五） ................................................................

一. 选择题

1. 向一个有127个元素的顺序表中插入一个新元素并保持原来顺序不变，平均要移动（ ）个元素。

A．8 B. 63.5 C. 63 D. 7

2. 设有一个二维数组A[m][n]，假设A[0][0]存放位置在644（10），A[2][2]存放位置在676（10），每个元素占一个空间，则A[3][3]在（ ）位置，（10）表明用10进数表示。！P113

A．692（10） B. 626（10） C. 709（10） D. 724（10）

·3. 一个有序顺序表有255个对象，采用顺序搜索查表，平均搜索长度为（ ）。？

A．128 B. 127 C. 126 D. 255 ·4. 含5个结点（元素值均不相同）的二叉树搜索树有（ ）种。 A．54 B. 42 C. 36 D. 65 5．N个顶点的连通图至少有（ ）条边。

A．N－1

第2章自测卷答案姓名班级

一、填空（每空1分，共13分）

1. 【严题集

2.2①】在顺序表中插入或删除一个元素，需要平均移动表中一半元素，具体移动的元素个数与表长和该元素在表中的位置有关。

2. 线性表中结点的集合是有限的，结点间的关系是一对一的。

3. 向一个长度为n的向量的第i个元素(1≤i≤n+1)之前插入一个元素时，需向后移动n-i+1 个元素。

4. 向一个长度为n的向量中删除第i个元素(1≤i≤n)时，需向前移动n-i 个元素。

5. 在顺序表中访问任意一结点的时间复杂度均为O(1)，因此，顺序表也称为随机存取的数据结构。

6. 【严题集2.2①】顺序表中逻辑上相邻的元素的物理位置必定相邻。单链表中逻辑上相邻的元素的物理位置不一定相邻。

7. 【严题集2.2①】在单链表中，除了首元结点外，任一结点的存储位置由其直接前驱结点的链域的值指示。

8．在n个结点的单链表中要删除已知结点*p，需找到它的前驱结点的地址，其时间复杂度为O（n）。二、判断正误（在正确的说法后面打勾，反之打叉）（每小题1分，共10分）

（×）1. 链表的每个结点中都恰好包含一个指针。

答：错误。链表中的结点可含多个指针域，分别存放多个指针。例如，双向链表中的结点可

以含有两个指针域，分别

第2章自测卷答案姓名班级

一、填空（每空1分，共13分）

1. 【严题集

2.2①】在顺序表中插入或删除一个元素，需要平均移动表中一半元素，具体移动的元素个数与表长和该元素在表中的位置有关。

2. 线性表中结点的集合是有限的，结点间的关系是一对一的。

3. 向一个长度为n的向量的第i个元素(1≤i≤n+1)之前插入一个元素时，需向后移动n-i+1 个元素。

4. 向一个长度为n的向量中删除第i个元素(1≤i≤n)时，需向前移动n-i 个元素。

5. 在顺序表中访问任意一结点的时间复杂度均为O(1)，因此，顺序表也称为随机存取的数据结构。

6. 【严题集2.2①】顺序表中逻辑上相邻的元素的物理位置必定相邻。单链表中逻辑上相邻的元素的物理位置不一定相邻。

7. 【严题集2.2①】在单链表中，除了首元结点外，任一结点的存储位置由其直接前驱结点的链域的值指示。

8．在n个结点的单链表中要删除已知结点*p，需找到它的前驱结点的地址，其时间复杂度为O（n）。二、判断正误（在正确的说法后面打勾，反之打叉）（每小题1分，共10分）

（×）1. 链表的每个结点中都恰好包含一个指针。

答：错误。链表中的结点可含多个指针域，分别存放多个指针。例如，双向链表中的结点可

以含有两个指针域，分别

数据结构试卷（四）

一、选择题(每题1分共 20分)

1．设一维数组中有n个数组元素，则读取第i个数组元素的平均时间复杂度为（ ）。

2

(A) O(n) (B) O(nlog2n) (C) O(1) (D) O(n) 2．设一棵二叉树的深度为k，则该二叉树中最多有（ ）个结点。

kk-1k

(A) 2k-1 (B) 2 (C) 2 (D) 2-1

3．设某无向图中有n个顶点e条边，则该无向图中所有顶点的入度之和为（ ）。 (A) n (B) e (C) 2n (D) 2e 4．在二叉排序树中插入一个结点的时间复杂度为（ ）。

2

(A) O(1) (B) O(n) (C) O(log2n) (D) O(n)

5．设某有向图的邻接表中有n个表头结点和m个表结点，则该图中有（ ）条有向边。 (A) n (B) n-1 (C) m (D) m-1

6．设一组初始记录关键字序列为(345，253，674，924，627)，则用基数排序需要进行（ ）趟的分配和回收才能使得初始关键字序列变成有序序列。 (A) 3 (B) 4 (C) 5 (D) 8 7．设用链表作为栈的存储结构则退栈操作（ ）。 (A) 必须判别栈是否为满 (B)

2000年试卷A

一 、简答问题：（每小题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

三、单项选择题：(每小题1分，共5分)

1．对于只在表的首、尾进行插入操作的线性表，宜采用的存储结构为: A) 顺序表 B) 用头指针表示的单循环链表 C) 用尾指针表示的单循环链表 D) 单链表 2．假设以第一个元素为分界元素，对字符序列（Q, H, C, Y, P, A, M, S, R, D, F, X）进行快速排序，则第一次划分的结果是：

A) (A, C, D, F, H, M, P, Q, R, S, X, Y) B) (A, F, H, C, D, P, M, Q, R, S, Y, X) C) (F, H, C, D, P, A, M, Q, R, S, Y, X) D) (P, A, M, F, H, C, D, Q, S, Y, R, X) 3．下面是三个关于有向图运算的叙述：

（1）求有向图结点的拓扑序列，其结果必定是唯一的

（2）求两个指向结点间的最短路径，其结果必定是唯一的 （3）求AOE网的关键路径，其结果必定是唯一的 其中哪个（些）是正确的？

A) 只有（1） B) （1）和（2） C) 都正确 D) 都不正确 4

数据结构作业

班级： 学号： 姓名： 教师：

第一章：概述

一．单项选择。

1、数据结构是一门研究数值计算得程序设计问题中计算机的 以及它们之间的 和运算等的学科。

(1)A.数据元素 B.计算方法 C.逻辑存储 D.数据映像 （2）A．结构 B关系 C运算 D算法 2、数据结构被形式地定义为（K，R），其中K是 的有限集，R是K上的 有限集。 （1）A.算法 B.数据元素 C.数据操作 D.逻辑结构 （2）A.操作 B.映像 C.存储 D.关系

3、 线性结构的顺序存储结构是一种 的存储结构，线性表的链式存储结构式一种 的存储结构。

A．随机存取 B.顺序存取 C.索引存取 D.散列存取

4、计算机算法指的是 ，它必须必备输入，输出和 等5个特性。 （1）A.计算方法 B.排序方法 C.解决问题的有限运算序列 D.调度方法 （2）A.可执行性、可移值性和可扩充性 B.