目录。第一部分选择题 2
第二部分填空题 19
第三部分应用题 24
1. 数据的四种基本逻辑结构是指（）
a．数组、链表、树、图形结构b．线性表、链表、栈、广义表。
c．线性结构、链表、树、图形结构 d．集合、线性结构、树、图形结构。
2. 在以单链表为存储结构的线性表中，数据元素之间的逻辑关系用___表示。
a．数据元素的相邻地址b．数据元素在表中的序号。
c．指向后继元素的指针d．数据元素的值。
3. 顺序存储的线性表（a1,a2,a3……an），在任一结点前插入一个新结点时所需移动结点的平均次数为 （）
a．nb．n/2c．n+1d．(n+1)/2
4．栈和队列都是（）
a．限制存取位置的线性结构b．顺序存储的线性结构。
c．链式存储的线性结构d．限制存取位置的非线性结构。
5. 若有三个字符a、b、c依次入栈，入栈过程中可以出栈，而其不可能的出栈序列为（）
a．a、b、cb．c、a、bc．c、b、a d．b、a、c
6．稀疏矩阵一般采用___方法压缩存储。
a．三维数组b．单链表
c．三元组表d．散列表。
7．深度为5的二叉树至少有___个叶子（）
a．16b．15c．8d．7
8. 二叉树若采用二叉链表结构表示，则对于n个结点的二叉树一定有（）
a．2n个指针域，其中n个指针为null
b．2n个指针域，其中n+1个指针为null
c．2n-1个指针域，其中n个指针为null
d．2n-1个指针域，其中n+1个指针为null
9. 具有3个结点的二叉树可有___种形态。
a．3b．5c．6d．9
10. 在一个带权连通图g中，权值最小的边一定包含在g的 （）
a．最小生成树中b．深度优先生成树中。
c．广度优先生成树中d．深度优先生成树中。
11. 能进行二分查找的线性表，必须以（）
a．顺序方式存储，且元素按关键字有序。
b．链式方式存储，且元素按关键字有序。
c．顺序方式存储，且元素按关键字分块有序。
d．链式方式存储，且元素按关键字分块有序。
12. 散列文件不能（）
a．随机存取b．索引存取。
c．按关键字存取d．直接存取。
13. 在题13图所示的各棵二叉树中，二叉排序树是（）
14. 一组记录的关键码为（46，79，56，38，40，84），则利用快速排序方法，以第一个记录为基准得到的一次划分结果为（）
a．38，40，46，56，79，84b．40，38，46，79，56，84
c．40，38，46，56，79，84d．40，38，46，84，56，79
15. 堆排序属于一种选择排序，其时间复杂性为（）
a．o（1b．o（n）
c．o（n2d．o（log2n）
16．下列数据组织形式中，（ 的结点按逻辑关系依次排列形成一个“锁链”。
a.集合b.树形结构。
c.线性结构d.图状结构。
17．数据结构可以形式化地定义为（s，△）其中s指某种逻辑结构，△是指（ ）
上的算法的存储结构。
c.在s上的一个基本运算集d.在s上的所有数据元素。
18．下列说法正确的是（ ）
a.线性表的逻辑顺序与存储顺序总是一致的。
b.线性表的链式存储结构中，要求内存中可用的存储单元可以是连续的，也可以不连续。
c.线性表的线性存储结构优于链式存储结构。
d.每种数据结构都具有插入、删除和查找三种基本运算。
19．设非空单链表的数据域为data，指针域为next，指针p指向单链表中第i个结点，s指向已生成的新结点，现将s结点插入到单链表中，使其成为第i个结点，下列算法段能正确完成上述要求的是（ ）
next=p->next;p->next=s；
next=s;s->next=p->next；
next=p->next;p->next=s;交换p->data和s->data；
next=p；
20．稀疏矩阵一般采用（ ）方法压缩存储。
a.三维数组b.单链表。
c.三元组表d.散列表。
21．树若用双亲链表表示，则（ ）
a.可容易地实现求双亲及子孙的运算。
b.求双亲及子孙的运算均较困难。
c.可容易地实现求双亲运算，但求子孙运算较困难。
d.可容易地实现求子孙运算，但求双亲运算较困难。
22．将一棵有50个结点的完全二叉树按层编号，则对编号为25的结点x，该结点（ ）
a.无左、右孩子
b.有左孩子，无右孩子。
c.有右孩子，无左孩子。
d.有左、右孩子。
23．用邻接表作为有向图g的存储结构。设有n个结点、e条弧，则拓扑排序的时间复杂度为（ ）
24．如果从无向图的任一顶点出发进行一次深度优先搜索即可访问所有顶点，则该图一定是（ ）
a.完全图b.连通图
c.有回路d.一棵树。
25．采用线性探测法解决冲突问题，所产生的一系列后继散列地址（ ）
a.必须大于等于原散列地址。
b.必须小于等于原散列地址。
c.可以大于或小于但不能等于原散列地址。
d.地址大小没有具体限制。
26．在对查找表的查找过程中，若被查找的数据元素不存在，则把该数据元素插入到集合中。这种方式主要适合于（ ）
a.静态查找表b.动态查找表。
c.静态查找表与动态查找表d.两种表都不适合。
27．由索引集、顺序集和数据集三部分组成的文件称为（ ）
文件b.散列文件。
c.顺序文件d.索引文件。
28．下列有关散列文件的说法中不正确的是（ ）
a.散列文件具有随机存放的优点。
b.散列文件只能按关键字存取。
c.散列文件需要索引区。
d.散列文件的记录不需要进行排序。
29．一组记录的键值为（12，38，35，25，74，50，63，90），按2路归并排序方法对该序列进行一趟归并后的结果为（ ）
a.12,38,25,35,50,74,63,90b.12,38,35,25,74,50,63,90
c.12,25,35,38,50,74,63,90d.12,35,38,25,63,50,74,90
30．用快速排序方法对包含有n个关键字的序列进行排序，最坏情况下执行的时间复杂度为（ ）
31.下列数据结构中，( 不都是线性结构。
a.栈和队列b.队列和数组。
c.数组和串d.文件和队列。
32.为了最快地对线性结构的数据进行某数据元素的读取操作，则其数据存储结构宜采用( )方式。
a.顺序存储b.链式存储。
c.索引存储d.散列存储。
33.设双链表中结点的前趋指针和后继指针的域名分别为t1和r1，则删除双链表中指针s所指结点的操作为( )
t1->r1=s->t1;s->r1->t1=s->r1;
t1->r1=s->r1;s->r1->t1=s->t1;
r1=s->t1->r1;s->t1=s->r->t1;
t1=s->t1->r1;s->r1=s->r->t1;
34.假设left和right为双向链表中指向直接前趋结点和直接后继结点的指针域，现要把一个指针s所指的新结点作为非空双链表中q所指地点(中间结点)的直接后继结点插入到该双向链表中，则下列算法段能正确完成上述要求的是( )
right=s; s->left=q; q->right->left=s; s->right=q->right;
left=q; q->right=s; q->right->left=s; s->right=q->right;
left=q; s->right=q->right; q->right->left=s; q->right=s;
d.以上都不对。
35.由下列三棵树组成的森林转换成一棵二叉树为( )
36.具有100个结点的完全二叉树的深度为( )
a.6b.7c.8d.9
37.已知一个稀疏矩阵的三元组表如下：(1，2，3)，(1，6，1)，(3，1，5)，(3，2，-1)，(4，5，4)，(5，1，-3)，则其转置矩阵的三元组表中第3个三元组为( )
a.(2，1，3b.(3，1，5c.(3，2，-1) d.(2，3，-1)
38.无向图的邻接矩阵是一个( )
a.对称矩阵b.零矩阵c.上三角矩阵 d.对角矩阵。
39.下列说法中正确的是( )
a.一个具有n个顶点的无向完全图的边数为n(n-1)
b.连通图的生成树是该图的一个极大连通子图。
c.图的广度优先搜索是一个递归过程。
d.对于非连通图的遍历过程中每调用一次深度优先搜索算法都得到该图的一个连通分量。
40.顺序查找法与二分查找法对存储结构的要求是( )
a.顺序查找与二分查找均只适用于顺序表。
b.顺序查找与二分查找既适用于顺序表，也适用于链表。
c.顺序查找只适用于顺序表。
d.二分查找只适用于顺序表。
a.其键值相同b.其元素值相同。
c.其散列地址相同d.其含义相同。
42.散列文件中的记录通常成组存放，若干个记录组成一个存储单位，这个存储单位称为( )
a.磁道b.块c.柱面d.桶。
经典数据结构上机题 答案
实验一线性表的顺序存储结构 实验学时 2学时 背景知识 顺序表的插入 删除及应用。目的要求 1 掌握顺序存储结构的特点。2 掌握顺序存储结构的常见算法。实验内容 1 输入一组整型元素序列，建立顺序表。数据结构上机实验题目。实验一线性表的顺序存储结构 实验学时 2学时 背景知识 顺序表的插入 删除及应...
数据结构经典题目
个人收集整理 zq 一 课程设计要求。课程设计报告要求按照如下几个内容认真完成 其中包括 需求分析 在该部分中叙述，每个模块地功能要求。概要设计 在此说明每个部分地算法设计说明 可以是描述算法地流程图 每个程序中使用地存储结构设计说明 如果指定存储结构请写出该存储结构地定义 个人收集整理勿做商业用途...
数据结构真题
总分 100.00，做题时间 90分钟 一 单项选择题 总题数 15，分数 30.00 1.一个算法的时间耗费的数量级称为该算法的 分数 2.00 a.效率。b.难度。c.可实现性。d.时间复杂度 解析 考点 算法的时间复杂度的概念 解析 一个算法的时间耗费的数量级称为该算法的时间复杂度。2.顺序表...