数据结构习题集含答案
目录
目录 (1)
选择题 (2)
第一章绪论 (2)
第二章线性表 (4)
第三章栈和队列 (6)
第四章串 (7)
第五章数组和广义表 (8)
第六章树和二叉树 (8)
第七章图 (11)
第八章查找 (13)
第九章排序 (14)
简答题 (19)
第一章绪论 (19)
第二章线性表 (24)
第三章栈和队列 (26)
第四章串 (28)
第五章数组和广义表 (29)
第六章树和二叉树 (31)
第七章图 (36)
第八章查找 (38)
第九章排序 (39)
编程题 (41)
第一章绪论 (41)
第二章线性表 (41)
第三章栈和队列 (52)
第四章串 (52)
第五章数组和广义表 (52)
第六章树和二叉树 (52)
第七章图 (52)
第八章查找 (52)
第九章排序 (57)
选择题
第一章绪论
1.数据结构这门学科是针对什么问题而产生的？（A ）
A、针对非数值计算的程序设计问题
B、针对数值计算的程序设计问题
C、数值计算与非数值计算的问题都针对
D、两者都不针对
2.数据结构这门学科的研究内容下面选项最准确的是（D ）
A、研究数据对象和数据之间的关系
B、研究数据对象
C、研究数据对象和数据的操作
D、研究数据对象、数据之间的关系和操作
3.某班级的学生成绩表中查得张三同学的各科成绩记录，其中数据结构考了90
分，那么下面关于数据对象、数据元素、数据项描述正确的是（C ）
A、某班级的学生成绩表是数据元素，90分是数据项
B、某班级的学生成绩表是数据对象，90分是数据元素
C、某班级的学生成绩表是数据对象，90分是数据项
D、某班级的学生成绩表是数据元素，90分是数据元素
4.*数据结构是指（A ）。
A、数据元素的组织形式
B、数据类型
C、数据存储结构
D、数据定义
5.数据在计算机存储器内表示时，物理地址与逻辑地址不相同，称之为（C ）。
A、存储结构
B、逻辑结构
C、链式存储结构
D、顺序存储结构
6.算法分析的目的是（C ）
A、找出数据的合理性
B、研究算法中的输入和输出关系
C、分析算法效率以求改进
D、分析算法的易懂性和文档型性
7.算法分析的主要方法（A ）。
A、空间复杂度和时间复杂度
B、正确性和简明性
C、可读性和文档性
D、数据复杂性和程序复杂性
8.计算机内部处理的基本单元是（B ）
A、数据
B、数据元素
C、数据项
D、数据库
9.数据在计算机内有链式和顺序两种存储方式，在存储空间使用的灵活性上，
链式存储比顺序存储要（B ）。
A、低
B、高
C、相同
D、不好说
10.算法的时间复杂度取决于（ C ）
A 、问题的规模B、待处理数据的初始状态
C、问题的规模和待处理数据的初始状态
D、不好说
11.数据结构既研究数据的逻辑结构，又研究物理结构，这种观点（B ）。
A、正确
B、错误
C、前半句对，后半句错
D、前半句错，后半句对
12.在数据结构中，从逻辑上可以把数据结构分成（ C ）
A、动态结构和静态结构
B、紧凑结构和非紧凑结构
C、线性结构和非线性结构
D、内部结构和外部结构
13.线性表的顺序存储结构是一种( )的存储结构，线性表的链式存储结构是一
种（ A ）存储结构。
A、随机存取
B、顺序存取
C、索引存取
D、散列存取
14.*下列程序的时间复杂度是（A ）
for (i=1; i<=n; ++i){
for (j=1; j<=n; ++j){
c [i][j]=0;
}
}
A、O(n2)
B、O(n)
C、O(2n)
D、O(2n2)
15.*下列程序的空间复杂度是（A ）
for (i=1; i<=n; ++i){
for (j=1; j<=m; ++j){
c [i][j]=0;
}
}
A、O(m*n)
B、O(m+n)
C、O(m-n)
D、O(m/n)
16.*求下列程序段的时间复杂度( B )
for( i=1; i<=n ; i + + )
for ( j=1; j<=n ; j + + )
x=x+1;
A、O(n2)
B、O(n)
C、O(1)
D、O(0)
第二章线性表
1.关于线性表的说法不正确的是？（D ）
A、存在唯一的一个被称为“第一个”的数据元素（开始结点）
B、存在唯一的一个被称为“最后一个”的数据元素（终端结点）
C、除第一个之外，集合中的每个数据元素均只有一个前驱
D、除第一个之外，集合中的每个数据元素均只有一个后继
2.关于顺序表的说法不正确的是？（D ）
A、逻辑关系上相邻的两个元素在物理存储位置上也相邻
B、可以随机存取表中任一元素，方便快捷
C、在线性表中插入某一元素时，往往需要移动大量元素
D、在线性表中删除某一元素时，无需移动大量元素
3.当线性表的元素总数基本稳定，且很少进行插入和删除操作，但要求以最快
的速度存取线性表中的元素时，应采用什么存储结构？（A ）
A、顺序表
B、单链表
C、循环链表
D、双链表
4.在一个长度为n的顺序表中第i个元素（1<=i<=n）之前插入一个元素时，
需向后移动多少个元素。（C ）
A、n-1
B、n-i
C、n-i+1
D、n-i-1
5.在单链表中设置头结点的作用是( )。
A、单链表定义而已
B、指定表的起始位置
C、为双向链表做准备
D、为循环链表做准备
6.根据线性表链式存储结构中每一个结点包含的指针数，将线性链表分成（C ）
A、单链表与循环链表
B、单链表与十字链表
C、单链表与双链表
D、循环链表与多链表
7.链接存储的特点是利用什么来表示数据元素之间的逻辑关系（A ）
A、引用
B、串联
C、挂接
D、指派
8.已知指针p指向单链表L中的某结点，则删除其后继结点的语句是（D ）
A、p = p.next
B、p =null
C、p.next=null
D、p.next = p.next.next
9.*在单链表L中，指针p所指结点有后继结点的条件是（B ）
A、p = p.next
B、p.next!=null
C、p.next=null
D、p.next = p.next.next
10.*在单链表p结点之后插入s结点的操作是（C ）
A、p.next=s; s.next=p.next;
B、s.next = p.next; p.next=p.next.next;
C、s.next = p.next; p.next = s;
D、s.next=p; p.next=s;
第三章栈和队列
1.栈、队列通常采用两种存储结构，它们是(B )
A、散列方式和索引方式
B、顺序存储结构和链式存储结构
C、链表存储结构和数组
D、线性和非线性存储结构
2.一个栈入栈序列是a,b,c,d, 则栈输出序列不可能是(C )
A、d,c,b,a
B、c,d,b,a
C、d,c,a,b
D、a,b,c,d
3.判断顺序栈（最多结点数为m）为栈满的条件是（D ）
A、top==0
B、 top!=m
C、 top!=0
D、top==m
4.栈存取数据原则（或栈特点）是（B ）
A、后进后出
B、后进先出
C、先进先出
D、随意进出
5.*经过以下栈运算后，x的值是（A ）
InitStack(s);
Push(s,d);
Push(s,e);
Pop(s,x);
Pop(s,x);
GetTop(s,x);
A、 d
B、 e C 、 x D、 s
6.一个队列的进队序列为：a，b，c，d，则出队序列是： ( A )
A、a，b，c，d
B、 d，c，b，a
C、a，d，c，b
D、 c，b，d，a
7.循环队列为空队列的条件是：（D）
A、Q.front=0
B、 Q.（rear+1)%MaxSize==Q.front
C、 Q.rear=0
D、 Q.rear==Q.front
8.在存储结构上，如果用带头节点单链表实现队列（假定front和rear分别
为队首和队尾指针），则删除一个结点的操作为（A ）。
A、front.next=front.next.next
B、rear=rear.next
C、rear=front.next
D、front= front.next
9.栈和队列共同点是（C ）
A、先进后出
B、先进先出
C、允许在端点处进行操作线性表
D、无共同点
10.插入和删除只能在一端进行的线性表是（B ）
A、循环队列
B、栈
C、队列
D、循环栈
11.插入和删除分别在两端端进行的线性表是（C ）
A、循环队列
B、栈
C、队列
D、循环栈
12.循环队列为满队列的条件是：（B ）
A、Q.front=0
B、 Q.（rear+1)%MaxSize==Q.front
C、 Q.rear=0
D、 Q.rear==Q.front
第四章串
1.关于串的叙述，错误的是：（B ）
A．串是字符有限序列B．空串是由空格构成的串
C．模式匹配是串的重要运算 D．串有用顺序、链式两种存储方式
2.串长度是指（B ）
A．串所含不同字母数目 B．串所含字符数目
C．串所含不同字符数目 D．串所含非空格字符数目
3.*若串S=”database”,其子串数目是（B ）。
A．16 B．37 C．8 D．36
4.设串S1是串S子串，则求S1在S中定位运算称为（B ）
A．求子串 B．串匹配 C．联接 D．求串长
5.设有串s1=”welcome to zdsoft colleage!”和s2=”so”,那么s2在s1
中的索引位置是（C ）
A．12 B．14 C．13 D．10
6.*若串S=“software“,其子串的数目是（B ）。
A．8 B．37 C．36 D．9
第五章数组和广义表
第六章树和二叉树
1.假设在一棵二叉树中，双分支结点数为15，单分支结点数为30个，则叶子
结点数为（ B ）个。
A. 15
B. 16
C. 17
D. 47
2.假定一棵三叉树的结点数为50，则它的最小高度为（C ）。
A. 3
B. 4
C. 5
D. 6
3.在一棵二叉树上第4层的结点数最多为（D ）。
A. 2
B. 4
C. 6
D. 8
4.用顺序存储的方法将完全二叉树中的所有结点逐层存放在数组中R[1..n]，
结点R[i]若有左孩子，其左孩子的编号为结点（B ）。
A. R[2i+1]
B. R[2i]
C. R[i/2]
D. R[2i-1]
5.设n , m 为一棵二叉树上的两个结点，在中序遍历序列中n在m前的条件是
（B ）。
A. n在m右方
B. n在m 左方
C. n是m的祖先
D. n是m的子孙
6.下面叙述正确的是（D ）。
A. 二叉树是特殊的树
B. 二叉树等价于度为2的树
C. 完全二叉树必为满二叉树
D. 二叉树的左右子树有次序之分
7.现有一深度为5的二叉树，请问其最多有（ D ）个结点。
A. 32
B. 5
C.30
D. 31
8.现有一深度为4的二叉树，请问其最多有（ A ）个结点。
A. 15
B. 16
C.17
D.6
9.在一棵二叉排序树上按（ B ）遍历得到的结点序列是一个有序序列。
A. 先序
B. 中序
C.后序
D.头序
10.在一棵二叉树中，度为0的结点数为n0，度为2的结点数为n2，则n0=（ C ）
A. n+1
B. n+2
C.n2+1
D.2n+1
11.由三个结点构成的二叉树，共有（B ）种不同的形态。
A. 4
B. 5
C.6
D.7
12.一棵含有n个结点的树，（ A ）形态达到最大深度。
A. 单支树
B. 二叉树
C.三叉树
D.n叉树
13.不含任何结点的空树（ C ）。
Ａ.是一棵树; Ｂ.是一棵二叉树;
Ｃ.是一棵树也是一棵二叉树; Ｄ.既不是树也不是二叉树
14.二叉树是非线性数据结构，所以( C ) 。
Ａ.它不能用顺序存储结构存储; Ｂ.它不能用链式存储结构存储;
Ｃ.顺序存储结构和链式存储结构都能存储;
Ｄ.顺序存储结构和链式存储结构都不能使用
15.具有n(n>0)个结点的完全二叉树的深度为(C )。
Ａ.log2(n)Ｂ. log2(n)Ｃ.[ log2(n) ] +1 Ｄ.log2(n)+1
16.在一棵三元树中度为3的结点数为2个，度为2的结点数为1个，度为1的
结点数为2个，则度为0的结点数为（D ）个。
A. 4
B. 5
C.6
D.7
17.有关二叉树下列说法正确的是（B ）
A．二叉树的度为2 B．一棵二叉树的度可以小于
2
C．二叉树中至少有一个结点的度为2 D．二叉树中任何一个结点的度都为2
18.在完全二叉树中，若一个结点是叶结点，则它没（C ）。
A．左子结点B．右子结点
C．左子结点和右子结点D．左子结点，右子结点和兄弟结点
19.在下列情况中，可称为二叉树的是（B ）
A．每个结点至多有两棵子树的树 B. 哈夫曼树
C．每个结点至多有两棵子树的有序树 D. 每个结点只有一棵右子树
第七章图
1.图的深度优先遍历类似于二叉树的（ A ）。
A．先序遍历 B．中序遍历 C．后序遍历 D．层次遍历
2.已知一个图如图所示，若从顶点a出发按深度优先遍历，则可能得到的一种
顶点序列为（C ）
A．abecdf B．acfebd C．aebcfd D．aedfcb
3.若从无向图的任意一个顶点出发进行一次深度优先搜索可以访问图中所有
的顶点，则该图一定是（ B ）图。
A．非连通 B．连通 C．强连通 D．有向
4.在一个图中，所有顶点的度数之和等于所有边数的（ C ）倍。
A 1/2
B 1
C 2
D 3
5.在一个有向图中，所有顶点的入度之和等于所有顶点出度之和的（ B ）
倍。
A 1/2
B 1
C 2
D 3
6.一个有N个顶点的有向图最多有（ B ）条边。
A N
B N(N-1)
C N(n-1)/2
D 2N
7. 具有4个顶点的无向完全图有（ A ）条边。
A 6
B 12
C 18
D 20
8. 具有6个顶点的无向图至少有（ A ）条边才能确保是一个连通图。
A 5
B 6
C 7
D 8
9. 对于一个具有N 个顶点的无向图，若采用邻接矩阵表示，则该矩阵大小是
（D ）
A N
B (N-1)2
C N-1
D N*N
10. 一个具有N 个顶点的无向图中，要连通全部顶点至少要（ C ）条边
A N
B N+1
C N-1
D N/2
11. *已知图的邻接矩阵如图所示，则从顶点0出发按深度优先遍历的结果是
（ C ）。??????????
????????????01000111011000
01011010110011
00100011001001
1011110 A ．0 2 4 3 1 5 6 B ．0 1 3 6 5 4 2 C ．0 1 3 4 2 5 6 D ．0 3 6 1 5 4 2
12. 已知图的邻接表下图所示，则从顶点0出发按广度优先遍历的结果是（ ），
按深度优先遍历的结果是（ D ）。
A ．0 1 3 2
B ．0 2 3 1
C ．0 3 2 1
D ．0 1 2 3
13.已知图的邻接表下图所示，则从顶点0出发按广度优先遍历的结果是（），
按深度优先遍历的结果是（）。
A．0 1 3 2 B．0 2 3 1 C．0 3 2 1 D．0 1 2 3
14.当在一个有序的顺序表上查找一个数据时，既可用折半查找，也可用顺序查
找，但前者比后者的查找速度（ C ）。
A．必定快 B．不一定
C．在大部分情况下要快 D．取决于表递增还是递减
15.折半查找有序表（4，6，10，12，20，30，50，70，88，100）。若查找表中
元素58，则它将依次与表中（ A ）比较大小，查找结果是失败。
A．20，70，30，50 B．30，88，70，50
C．20，50 D．30，88，50
第八章查找
1.顺序查找法适合于存储结构为（B ）的线性表。
A．散列存储 B．顺序存储或链式存储
C．压缩存储 D．索引存储
2.在查找过程中，若同时还要增、删工作，这种查找称为（ B ）。
A、静态查找
B、动态查找
C、内查找
D、外查找
3.索引顺序表的特点是顺序表中的数据（ A ）。
A、有序
B、无序
C、块间有序
D、散列
4.采用顺序查找方法查找长度为n的线性表时，每个元素的平均查找长度为（C）
A、 n
B、n/2
C、(n+1)/2
D、(n-1)/2
5.*将10个元素散列到1000000个单元的哈希表，则（ C ）产生冲突。
A、一定会
B、一定不会
C、仍可能会
D、以上都不对
6.*散列表的地址区间为0~16，散列函数H(k)=k%17，采用线性探测法解决地
址冲突，将关键字26、25、72、38、1、18、59依次存储到散列表中。元素59存放在散列表中的地址为（ A ）
A、 8
B、 9
C、 10
D、 11
7.设有序表的关键字序列为{1,3,9,12,32,41,45,62,75,77,82,95,100}，当采
用二分查找法查找值为82的节点时，经（ C ）次比较后查找成功。
A、 1
B、 2
C、 3
D、 4
8.设有100个元素，用折半查找法进行查找时，最大、最小比较次数分别时
（ A ）
A、 7,1
B、6,1
C、5,1
D、8,1
第九章排序
1.对n个不同的记录按排序码值从小到大次序重新排列，用冒泡(起泡)排序方
法，初始序列在（A ）情况下，与排序码值总比较次数最少。
A．按排序码值从小到大排列 B．按排序码值从大到小排列
C．随机排列(完全无序) D．基本按排序码值升序排列
2.对n个不同的记录按排序码值从小到大次序重新排列，用冒泡(起泡)排序方
法，在（B）情况下，与排序码值总比较次数最多。
A．按排序码值从小到大排列 B．按排序码值从大到小排列
C．随机排列(完全无序) D．基本按排序码值升序排列
3.对n个不同的记录按排序码值从小到大次序重新排列，用直接插入排序方法，
初始序列在（A）情况下，与排序码值总比较次数最少。
A．按排序码值从小到大排列 B．按排序码值从大到小排列
C．随机排列(完全无序) D．基本按排序码值升序排列
4.对n个不同的记录按排序码值从小到大次序重新排列，用直接插入排序方法，
初始序列在（B）情况下，与排序码值总比较次数最多。
A．按排序码值从小到大排列 B．按排序码值从大到小排列
C．随机排列(完全无序) D．基本按排序码值升序排列
5.对n个不同的记录按排序码值从小到大次序重新排列，用快速排序方法在
（C）情况下，与排序码值总比较次数最少。
A．按排序码值从小到大排列 B．按排序码值从大到小排列
C．随机排列(完全无序) D．基本按排序码值升序排列
6.对n个不同的记录按排序码值从小到大次序重新排列，用快速排序方法，在
（A）情况下与排序码值总比较次数最多。
A．按排序码值从小到大排列 B．按排序码值从大到小排列
C．随机排列(完全无序) D．基本按排序码值升序排列
7.用冒泡排序方法对n个记录按排序码值从小到大排序时，当初始序列是按排
序码值从大到小排列时，与码值总比较次数是（D）。
A．n-1 B．n C．n+1 D．n(n-1)／2
8.下列排序方法中，与排序码值总比较次数与待排序记录的初始序列排列状态
无关的是 (D) 。
A．直接插入排序 B．冒泡排序 C．快速排序 D．直接选择排序
9.将6个不同的整数进行排序，至少需要比较 (A) 次。
A．5 B．6 C．15 D．21
10.将6个不同的整数进行排序，至多需要比较 (C) 次。
A．5 B．6 C．15 D．21
11.*若需要时间复杂度在O(nlog2n)内，对整数数组进行排序，且要求排序方法
是稳定的，则可选择的排序方法是 (B) 。
A．快速排序 B．归并排序 C．堆排序 D．直接插入排序
12.当待排序的整数是有序序列时，采用 (B) 方法比较好，其时间复杂度为
O(n)。
A．快速排序 B．冒泡排序 C．归并排序 D．直接选择排序
13.当待排序的整数是有序序列时，采用（A）方法比较差，达到最坏情况下
时间复杂度为O(n2)。
A．快速排序 B．冒泡排序 C．归并排序 D．直接选择排序
14.当待排序的整数是有序序列时，无论待排序序列排列是否有序，采用（D）
方法的时间复杂度都是O(n2)。
A．快速排序 B．冒泡排序 C．归并排序 D．直接选择排序
15.*堆是一种 (B) 排序。
A．插入 B．选择 C．交换 D．归并
16.*若一组记录的排序码值序列为{40，80，50，30，60，70}，利用堆排序方
法进行排序，初建的大顶堆是 (D ) 。
A．80，40，50，30，60，70 B．80，70，60，50，40，30
C．80，70，50，40，30，60 D．80，60，70，30，40，50
17.若一组记录的排序码值序列为{50，80，30，40，70，60}利用快速排序方法，
以第一个记录为基准，得到一趟快速排序的结果为（B ）。
A．30，40，50，60，70，80 B．40，30，50，80，70，60
C．50，30，40，70，60，80 D．40，50，30，70，60，80
18.*下列几种排序方法中要求辅助空间最大的是（C ）。
A．堆排序 B．直接选择排序 C．归并排序 D．快速排序
19.已知A[m]中每个数组元素距其最终位置不远，采用下列 (A) 排序方法最
节省时间。
A．直接插入 B．堆 C．快速 D．直接选择
20.*设有10000个互不相等的无序整数，若仅要求找出其中前10个最大整数，
最好采用（B）排序方法。
A．归并 B．堆 C．快速 D．直接选择
21.*在下列排序方法中不需要对排序码值进行比较就能进行排序的是（A）。
A：基数排序 B．快速排序 C．直接插入排序 D．堆排序
22.*给定排序码值序列为{F，B，J，C，E，A，I，D，C，H}，对其按字母的字
典序列的次序进行排列，希尔(Shell)排序的第一趟(d1=5)结果应为（D ）。
A．{B，F，C，J，A，E，D，I，C，H}
B．{C，B，D，A，E，F，I，C，J，H}
C．{B，F，C，E，A，I，D，C，H，J}
D．{A，B，D，C，E，F，I，J，C，H}
23.给定排序码值序列为{F，B，J，C，E，A，I，D，C，H}，对其按字母的字典
序列的次序进行排列，冒泡排序(大数下沉)的第一趟排序结果应为（C ）。
A．{B，F，C，J，A，E，D，I，C，H}
B．{C，B，D，A，E，F，I，C，J，H}
C．{B，F，C，E，A，I，D，C，H，J}
D．{A，B，D，C，E，F，I，J，C，H}
24.给定排序码值序列为{F，B，J，C，E，A，I，D，C，H}，对其按字母的字典
序列的次序进行排列，快速排序的第一趟排序结果为（B ）。
A．{B，F，C，J，A，E，D，I，C，H}
B．{C，B，D，A，E，F，I，C，J，H}
C．{B，F，C，E，A，I，D，C，H，J}
D．{A，B，D，C，E，F，I，J，C，H}
25.*给定排序码值序列为{F，B，J，C，E，A，I，D，C，H}，对其按字母的字
典序列的次序进行排列，二路归并排序的第一趟排序结果是（A ）。
A．{B，F，C，J，A，E，D，I，C，H}
B．{C，B，D，A，E，F，I，C，J，H}
C．{B，F，C，E，A，I，D，C，H，J}
D．{A，B，D，C，E，F，I，J，C，H}
简答题
第一章绪论
1.请分别给出数据、数据对象、数据元素、数据项的含义，并说明四者的关系。
数据(Data):是对信息的一种符号表示。在计算机科学中是指所有能输入到计算机中并能被计算机程序处理的符号的总称。（一个得分点）
数据元素(Data Element):是数据的基本单位，在计算机程序中通常作为一个整体进行考虑和处理，相当于表中的一条记录。（一个得分点）
数据项：相当于记录的“域”, 是数据的不可分割的最小单位,如学号（一个得分点）
数据对象：性质相同的数据元素的集合，是数据的一个子集.例如: 同一个班的所有学生记录集合。（一个得分点）
关系：包含关系：数据泛指所有。数据对象是数据的一个子集，由数据元素组成，数据元素是由数据项组成。（一个得分点）
评分标准，总共5个得分点，每段话一个得分。
2.请给出数据的逻辑结构的含义，并举例说明数据的逻辑结构通常有哪些。
数据的逻辑结构：指数据元素之间的逻辑关系。即用自然语言描述数据，它与数据的存储无关，是独立于计算机的，逻辑结构有四种。（一个得分点）
集合结构：仅同属一个集合（结构名字0.5个得分点、举例0.5得分点）
线性结构: 一对一（1:1) （结构名字0.5个得分点、举例0.5得分点）
树结构: 一对多（1:n) （结构名字0.5个得分点、举例0.5得分点）
图结构: 多对多 (m:n) （结构名字0.5个得分点、举例0.5得分点）
评分标准：每段话一个得分点，总共5个得分点。
什么是数据的物理结构？有哪些物理结构？数据的物理结构与逻辑结构有什么区别与联系？
2017年数据结构期末考试题及答案 一、选择题（共计50分，每题2分，共25题） 1 ?在数据结构中，从逻辑上可以把数据结构分为 C 。 A. 动态结构和静态结构B?紧凑结构和非紧凑结构 C.线性结构和非线性结构 D .内部结构和外部结构 2?数据结构在计算机内存中的表示是指 A ° A. 数据的存储结构 B.数据结构 C.数据的逻辑结构 D .数据元 素之间的关系 3.在数据结构中，与所使用的计算机无关的是数据的 A 结构。 A. 逻辑B?存储 C.逻辑和存储 D.物理 4 .在存储数据时，通常不仅要存储各数据元素的值，而且还要存储 C ° A.数据的处理方法B?数据元素的类型 C.数据元素之间的关系 D.数据的存储方法 5. 在决定选取何种存储结构时，一般不考虑 A ° A.各结点的值如何B?结点个数的多少 C?对数据有哪些运算 D.所用的编程语言实现这种结构是否方便。 6. 以下说法正确的是D ° A. 数据项是数据的基本单位 B. 数据元素是数据的最小单位 C. 数据结构是带结构的数据项的集合 D. —些表面上很不相同的数据可以有相同的逻辑结构 7. 在以下的叙述中，正确的是B ° A. 线性表的顺序存储结构优于链表存储结构 B. 二维数组是其数据元素为线性表的线性表 C?栈的操作方式是先进先出 D.队列的操作方式是先进后出
8. 通常要求同一逻辑结构中的所有数据元素具有相同的特性，这意味着 A. 数据元素具有同一特点 B. 不仅数据元素所包含的数据项的个数要相同，而且对应的数据项的类型要一致 C. 每个数据元素都一样 D. 数据元素所包含的数据项的个数要相等 9 ?链表不具备的特点是 A 。 A.可随机访问任一结点 B.插入删除不需要移动元素 C?不必事先估计存储空间 D.所需空间与其长度成正比 10. 若某表最常用的操作是在最后一个结点之后插入一个结点或删除最后一 个结点，则采用 D 存储方式最节省运算时间。 A.单链表B ?给出表头指针的单循环链表 C.双链表D ?带头结点 的双循环链表 11. 需要分配较大空间，插入和删除不需要移动元素的线性表，其存储结构是 B 。 A.单链表B .静态链表 C.线性链表 D .顺序存储结构 12 .非空的循环单链表head的尾结点（由p所指向）满足C 。 A. p—>next 一NULL B. p — NULL C. p—>next == head D. p = = head 13 .在循环双链表的p所指的结点之前插入s所指结点的操作是 D 。 A .p—> prior-> prior=s B .p—> prior-> n ext=s C.s —> prior—> n ext = s D.s —> prior—> prior = s 14 .栈和队列的共同点是C 。 A.都是先进后出 B .都是先进先出 C.只允许在端点处插入和删除元素 D .没有共同点
数据结构试题及答案 一、单项选择题 (1)一个算法应该就是（)。 A)程序???B）问题求解步骤得描述 C）要满足五个基本属性??D) A与C (2)算法指得就是（)。 A）计算机程序???B）解决问题得计算方法 C)排序算法???D）解决问题得有限运算序列。 (3)与数据元素本身得形式、内容、相对位置、个数无关得就是数据得(）。 A) 存储结构B) 逻辑结构C）算法D)操作 (4)从逻辑上可以把数据结构分为( ）两大类。 A）动态结构、静态结构??B) 顺序结构、链式结构 C）线性结构、非线性结构???D）初等结构、构造型结构 (5)下列叙述中正确得就是(）。 A)一个逻辑数据结构只能有一种存储结构 B）数据得逻辑结构属于线性结构,存储结构属于非线性结构 C）一个逻辑数据结构可以有多种存储结构,且各种存储结构不影响数据处理得效率 D）一个逻辑数据结构可以有多种存储结构,且各种存储结构影响数据处理得效率 (6)数据得基本单位就是（） ?A) 数据项??B) 数据类型C)数据元素??D)数据变量 (7)下列程序得时间复杂度为（) i=０；s＝０; wｈｉlｅ(s 数据结构考试题库 绪论 一、填空题 1.数据的逻辑结构被分为集合、(线性结构)、(树形结构)和(图状结构)四种。 2.物理结构是数据结构在计算机中的表示，又称为(存储结构)。 3.数据元素的逻辑结构包括( 线性)、(树)和图状结构3种类型，树形结构和图状结构合称为(非线性结构)。 4.(数据元素)是数据的基本单位，(数据项)是数据不可分割的最小单位。 5.线性结构中元素之间存在(一个对一个)关系，树形结构中元素之间存在(一个对多个)关系，图状结构中元素之间存在(多个对多个)关系。 ？6.数据结构是一门研究非数值计算的程序设计问题中：计算机的(数据元素)以及它们之间的(关系)和(运筹)等的学科。 7.算法的五个重要特性为有穷性、确定性、(输入)、(输出)和(可行性)。 二、选择题 1.数据的不可分割的基本单位是(D)。 A.元素 B.结点 C.数据类型 D.数据项 *2.线性表的逻辑顺序与存储顺序总是一致的，这种说法(B)。 A.正确 B.不正确 C.不确定 D.无法选择 3.线性结构是指数据元素之间存在一种(D)。 精心整理，用心做精品2 A.一对多关系 B.多对多关系 C.多对一关系 D.一对一关系 4.在数据结构中，从逻辑上可以把数据结构分成(A)。 A.动态结构和静态结构 B.紧凑结构和非紧凑结构 C.线性结构和非线性结构 D.内部结构和外部结构 5.线性表若采用链式存储结构时，要求内存中可用存储单元的 地址( D)。 A.必须是连续的 B.部分地址必须是连续的 C.一定是不连续的 D.连续不连续都可以 三、简答题 1.算法的特性是什么。 答：有穷性确定性可行性有0或多个输入有1或多个输出线性结构 一、填空题 1.在一个长度为n的线性表中删除第i个元素（1≤i≤n）时，需向前移动(n-i)个元素。 2.从循环队列中删除一个元素时，其操作是(先移动队首指针，后取出元素)。 3.在线性表的单链接存储中，若一个元素所在结点的地址为p，则其后继结点的地址为(p->next)。 4.在一个单链表中指针p所指向结点的后面插入一个指针q所指向的结点时，首先把(p->next)的值赋给q->next，然后(q->date)的值赋给p->next。 5.从一个栈删除元素时，首先取出(栈顶元素)，然后再使(栈顶指针)减1。 6.子串的定位操作通常称做串的(模式匹配)。 精心整理，用心做精品3 一．是非题 （正确的打“√”，错误的打“×”。） 1. 数据结构可用三元式表示（D，S，P）。其中：D是数据对象，S是D上的关系， P是对D的基本操作集。× 2. 线性表的链式存储结构具有可直接存取表中任一元素的优点。× 3. 字符串是数据对象特定的线性表。 4. 二叉树是一棵结点的度最大为二的树。× 5．邻接多重表可以用以表示无向图，也可用以表示有向图。× 6．可从任意有向图中得到关于所有顶点的拓扑次序。× 7．一棵无向连通图的生成树是其极大的连通子图。× 8．二叉排序树的查找长度至多为log2ｎ。× 9．对于一棵m阶的B-树.树中每个结点至多有m 个关键字。除根之外的所有非终端结点至少有┌m/2┐个关键字。× 10．对于目前所知的排序方法，快速排序具有最好的平均性能。 11. 顺序存储方式的优点是存储密度大，且插入、删除运算效率高。× 12. 二维数组是其数据元素为线性表的线性表。 13. 连通图G的生成树是一个包含G的所有n个顶点和n-1条边的子图。× 14. 折半查找不适用于有序链表的查找。 15. 完全二叉树必定是平衡二叉树。 16. 中序线索二叉树的优点是便于在中序下查找直接前驱结点和直接后继结点。 17. 队列是与线性表完全不同的一种数据结构。× 18. 平均查找长度与记录的查找概率有关。 19. 二叉树中每个结点有两个子结点，而对一般的树，则无此限制，所以，二叉树是树的特殊情形。× 20. 算法的时间复杂性越好，可读性就越差；反之，算法的可读性越好，则时间复杂性就越差。× 二．选择题 1. 若对编号为1，2，3的列车车厢依次通过扳道栈进行调度，不能得到 ( e ) 的序列。 a:1,2,3 b:1,3,2 c:2,1,3 d:2,3,1 e:3,1,2 f:3,2,1 2. 递归程序可借助于( b )转化为非递归程序。 a:线性表 b: 栈 c:队列 d:数组 3. 在下列数据结构中( c )具有先进先出（FIFO）特性， ( b )具有先进后出(FILO）特性。 a:线性表 b:栈 c:队列 d:广义表 4. 对字符串s=’data-structure’ 执行操作replace(s,substring(s,6,8),’bas’) 数据结构期末考试试题及答案 、选择题 评价一个算法时间性能的主要标准是()。1. A、算法易于调试 B、算法易于理解 C、算法的稳定性和正确性 D、算法的时间复杂度 )等五个特性。计算机算法具备有输入、输出、 2. A、可行性、可移植性和可扩充性 B、可行性、确定性和有穷性 C、确定性、有穷性和稳定性 D、XX、稳定性和XX 。带头结点的单链表head为空的判定条件是()3. A、h ead==NULL B、h ead->next==NULL C、head->next==head D、head！=NULL 以下关于线性表的说法不正确的是()。4. A、线性表中的数据元素可以是数字、字符、记录等不同类型。 B、线性表中包含的数据元素个数不是任意的。 C、线性表中的每个结点都有且只有一个直接前趋和直接后继。 D、存在这 样的线性表：表中各结点都没有直接前趋和直接后继。 在顺序表中，只要知道()，就可在相同时间内求出任一结点的存储地址。 5.A、基地址 B、结点大小 C、向量大小 D、基地址和结点大小 ()运算中，使用顺序表比链表好。6. A、插入 B、删除 C、根据序号查找 D、根据元素值查找一个长度为n的顺序表中，向第i个元素之前插入一个新元素时，需要向后移动()个元素7.A、n-i B、n-i+1 C、n-i-1 D、i ()适合作为经常在首尾两端操作线性表的存储结构。8. A、顺序表 B、单链表 C、循环链表 D、双向链表 栈和队列的共同点是() 9. A、都是先进后出 B、都是先进先出 C、只允许在端点处插入和删除元素 D、没有共同点 一个队列的入列序列是1234，则队列的输出序列是()。10. A 、4321 B 、12 3 4 C 、1432 D 、 3241队列与一般的线性表的区别在于()。11. A、数据元素的类型不同 B、运算是否受限制 C、数据元素的个数不同 D、逻辑结构不同 假上溢”现象会出现在()中。12. A、循环队列 B、队列 C、链队列 、顺序队列D.二、填空 数据结构习题集含答案 目录 选择题 第一章绪论 1.数据结构这门学科是针对什么问题而产生的（A ） A、针对非数值计算的程序设计问题 B、针对数值计算的程序设计问题 C、数值计算与非数值计算的问题都针对 D、两者都不针对 2.数据结构这门学科的研究内容下面选项最准确的是（D ） A、研究数据对象和数据之间的关系 B、研究数据对象 C、研究数据对象和数据的操作 D、研究数据对象、数据之间的关系和操作 3.某班级的学生成绩表中查得张三同学的各科成绩记录，其中数据结构考了90分，那 么下面关于数据对象、数据元素、数据项描述正确的是（C ） A、某班级的学生成绩表是数据元素，90分是数据项 B、某班级的学生成绩表是数据对象，90分是数据元素 C、某班级的学生成绩表是数据对象，90分是数据项 D、某班级的学生成绩表是数据元素，90分是数据元素 4.*数据结构是指（A ）。 A、数据元素的组织形式 B、数据类型 C、数据存储结构 D、数据定义 5.数据在计算机存储器内表示时，物理地址与逻辑地址不相同，称之为（C ）。 A、存储结构 B、逻辑结构 C、链式存储结构 D、顺序存储结构 6.算法分析的目的是（C ） A、找出数据的合理性 B、研究算法中的输入和输出关系 C、分析算法效率以求改进 D、分析算法的易懂性和文档型性 7.算法分析的主要方法（A ）。 A、空间复杂度和时间复杂度 B、正确性和简明性 C、可读性和文档性 D、数据复杂性和程序复杂性 8.计算机内部处理的基本单元是（B ） A、数据 B、数据元素 C、数据项 D、数据库 9.数据在计算机内有链式和顺序两种存储方式，在存储空间使用的灵活性上，链式存储 比顺序存储要（B ）。 A、低 B、高 C、相同 D、不好说 10.算法的时间复杂度取决于（ C ） A 、问题的规模B、待处理数据的初始状态 C、问题的规模和待处理数据的初始状态 D、不好说 11.数据结构既研究数据的逻辑结构，又研究物理结构，这种观点（B ）。 A、正确 B、错误 C、前半句对，后半句错 D、前半句错，后半句对 12.在数据结构中，从逻辑上可以把数据结构分成（ C ） A、动态结构和静态结构 B、紧凑结构和非紧凑结构 C、线性结构和非线性结构 D、内部结构和外部结构 13.线性表的顺序存储结构是一种( )的存储结构，线性表的链式存储结构是一种（ A ） 存储结构。 A、随机存取 B、顺序存取 C、索引存取 D、散列存取 14.*下列程序的时间复杂度是（A ） for (i=1; i<=n; ++i){ for (j=1; j<=n; ++j){ c [i][j]=0; 2013-2014学年二学期数据结构期末考试模拟试卷(1~6卷) 一、应用题(3小题，共24分) 1已知某字符串S中共有8种字符，各种字符分别出现2次、1次、4次、5次、7次、3 次、4次和9次，对该字符串用［0,1］进行前缀编码，问该字符串的编码至少有多少位。 【解答】以各字符出现的次数作为叶子结点的权值构造的哈夫曼编码树如图所示。其带权路 径长度=2X 5+1X 5+3X 4+5X 3+9X 2+4X 3+4X 3+7X 2=98，所以，该字符串的编码长度至少为98位。 2.已知关键码序列为(Ja n, Feb, Mar, Apr, May, Jun, Jul, Aug, Sep, Oct, Nov, Dec), 散列表的地址空间为0~16,设散列函数为H(x)= ［i/2」(取下整数)，其中i为关键码 中第一个字母在字母表中的序号，采用链地址法处理冲突构造散列表，并求等概率情况下查找成功的平均查找长度。 【解答】H(Ja n)=10/2=5, H(Feb)=6/2=3, H(Mar)=13/2=6, H(Apr)=1/2=0 H(May)=13/2=6, H(Ju n)=10/25, H(Jul)=10/25, H(Aug)=1/2=0 H(Sep)=19/2=8, H(Oct) =15/2=7, H(Nov) =14/2=7, H(Dec) =4/2=2 采用链地址法处理冲突，得到的开散列表如下： 平均查找长度=(1 X 7+2X 4+3X 1)/12=18/12 3.分析下面各程序段的时间复杂度 (1)s1(int n) { int p=1,s=0; for (i=1;iv=n;i++) { p*=i;s+=p; } return(s); } ——0(n) (2)s2(int n) x=0;y=0; For (k=1;kv=n;k++) x++; For (i=1;iv=n;i++) For (j=1;jv=n;j++) y++; ——0(n) 1?下述算法的功能是什么？ ListNode *Demo l(LinkList L P ListNode *p) ("L是有头结蛊的单链表 ListNodc *q=L->rLCxt P (1) V ‘V … 」(1 )返回结点*p的直接前趋结点地址。 q=q->nest; if (q) return q, else ?ro< #*p not in L"); I ⑵ i/oid Demo2(LisINode *p ,ListNode +q) 〔//p t*q*8S 表中的 两个结点 (2)交换结点*p和结点*q (p和q的值不变)。 DataTypetemp; temp=p->data, p->data=q->data; q-x^ata^emp, 1.对给定的一组权值W=( 5, 2, 9, 11, 8, 3, 7),试构造相应的哈夫曼树，并计算它的带权路径长度。【解答】构造的哈夫曼树如图所示。 第二章算法分析 1.算法分析是计算机科学的基础 2.增长函数表示问题（n）大小与我们希望最优化的值之间的关系。该函数表示了该算法的时间复杂度或空间复杂度。增长函数表示与该问题大小相对应的时间或空间的使用 3.渐进复杂度：随着n的增加时增长函数的一般性质，这一特性基于该表达式的主项，即n 增加时表达式中增长最快的那一项。 4.渐进复杂度称为算法的阶次，算法的阶次是忽略该算法的增长函数中的常量和其他次要项，只保留主项而得出来的。算法的阶次为增长函数提供了一个上界。 5.渐进复杂度：增长函数的界限，由增长函数的主项确定的。渐进复杂度类似的函数，归为相同类型的函数。 6.只有可运行的语句才会增加时间复杂度。 7. O() 或者大O记法：与问题大小无关、执行时间恒定的增长函数称为具有O（1）的复杂度。 增长函数阶次 t(n)=17 O(1) t(n)=3log n O(log n) t(n)=20n-4 O(n) t(n)=12n log n + 100n O(n log n) t(n)=3n2+ 5n - 2 O(n2) t(n)=8n3+ 3n2O(n3) t(n)=2n+ 18n2+3n O(2n) 8.所有具有相同阶次的算法，从运行效率的角度来说都是等价的。 9.如果算法的运行效率低，从长远来说，使用更快的处理器也无济于事。 10.要分析循环运行，首先要确定该循环体的阶次n，然后用该循环要运行的次数乘以它。（n 表示的是问题的大小） 11.分析嵌套循环的复杂度时，必须将内层和外层循环都考虑进来。 12.方法调用的复杂度分析： 如：public void printsum(int count){ int sum = 0 ; for (int I = 1 ; I < count ; I++) sum += I ; System.out.println(sun); } printsum方法的复杂度为O（n）,计算调用该方法的初始循环的时间复杂度，只需把printsum方法的复杂度乘以该循环运行的次数即可。所以调用上面实现的printsum方法的复 杂度为O（n2）。 13指数函数增长> 幂函数增长> 对数函数增长 2011-2012学年第一学期期末考查 《数据结构》试卷 （答案一律写在答题纸上，在本试卷上做答无效） 一、选择（每题1分，共10分） 1.长度为n的线性表采用顺序存储结构，一个在其第i个位置插入新元素的算法时间复杂度为（D） A.O(0) B.O(1) C.O(n) D.O(n2) 2.六个元素按照6，5，4，3，2，1的顺序入栈，下列哪一个是合法的出栈序列？（D） A.543612 B.453126 C.346512 D.234156 3.设树的度为4，其中度为1、2、3、4的结点个数分别是4、2、1、2，则树中叶子个数为（B ） A.8 B.9 C.10 D.11 4.设森林F对应的二叉树B有m个结点，B的右子树结点个数为n，森林F中第一棵树的结点个数是（ B ） A. m-n B.m-n-1 C.n+1 D.m+n 5.若一棵二叉树具有10个度为2的结点，5个度为1的结点，则度为0的结点个数是（B） A.9 B.11 C.15 D.不确定 6.下列哪一个方法可以判断出一个有向图是否有环。（A） A.深度优先遍历 B.拓扑排序 C.求最短路径 D.求关键路径 7.第7层有10个叶子结点的完全二叉树不可能有（B ）个结点。 A.73 B.234 C.235 D.236 8.分别用以下序列构造二叉排序树，与用其他三个序列构造的结果不同的是（B） A.（100,80,90,60,120,110,130） B.（100, 120, 110,130,80, 60,90） C.（100,60,80,90,120,110,130） D.（100,80, 60,90, 120, 130,110） 9.对一组数据（84，47，25，15，21）排序，数据的排列次序在排序过程中变化如下：（1）84 47 25 15 21 （2）15 47 25 84 21 （3）15 21 25 84 47（4）15 21 25 47 84则采用的排序方法是（B ） A.选择排序 B.起泡排序 C.快速排序 D.插入排序 10.对线性表进行折半查找时，要求线性表必须（D） A.以顺序方式存储 B.以顺序方式存储，且数据元素有序 第一章概论 一、选择题 1、研究数据结构就是研究（Ｄ）。 Ａ. 数据的逻辑结构?B。数据的存储结构 C。数据的逻辑结构和存储结构?D．数据的逻辑结构、存储结构及其基本操作(研究非数值计算的程序设计问题中，计算机操作对象以及他们之间的关系和操作) 2、算法分析的两个主要方面是（Ａ）。 A．空间复杂度和时间复杂度???B。正确性和简单性 C。可读性和文档性D．数据复杂性和程序复杂性 3、具有线性结构的数据结构是（ D ）。(线性结构就是：在非空有限集合中，存在为一个被称为第一个的数据元素和最后一个元素,有除了第一个元素，集合中每一个元素均只有一个前驱，除了最后一个元素有唯一后继)（链表、栈、队列、数组、串） A. 图Ｂ. 树??C．广义表(线性表的推广) D．栈 4、计算机中的算法指的是解决某一个问题的有限运算序列,它必须具备输入、输出、（ B ）等5个特性。 Ａ．可执行性、可移植性和可扩充性? B. 可执行性、有穷性和确定性 C。确定性、有穷性和稳定性??? D. 易读性、稳定性和确定性 5、下面程序段的时间复杂度是( C ）。 for(i=0；i 第三章栈和队列 一、判断题： 1、栈和队列都是限制存取点的线性结构(易) 2、栈和队列是两种重要的线性结构。(易) 3、带头结点的单链表形式的队列，头指针F指向队列的头结点，尾指针R指向队列的最后一个结点(易) 4、在对不带头结点的链队列作出队操作时，不会改变头指针的值。(易) 答案：1-4 √√×× 二、选择题： 1、一个栈的入栈序列a，b，c，d，e，则栈的不可能的输出序列是C____。 A、 edcba B、 decba C、 dceab D、 abcde 2、若已知一个栈的入栈序列是1，2，3，…，n，其输出序列为p1，p2，p3，…，pn，若p1=n，则pi 为_C___。 A、 i B、 n=i C、 n-i+1 D、不确定 3、栈结构通常采用的两种存储结构是_A___。 A、顺序存储结构和链式存储结构 B、散列方式和索引方式 C、链表存储结构和数组 D、线性存储结构和非线性存储结构 4、判定一个顺序栈ST（最多元素为m0）为空的条件是_B___。A、top !=0 B、top= =0 C、top !=m0 D、top= =m0-1 5、判定一个顺序栈ST（最多元素为m0）为栈满的条件是D。A、top！=0 B、top= =0 C、top！=m0 D、top= =m0-1 6、队列操作的原则是( A ) A、先进先出 B、后进先出 C、只能进行插入 D、只能进行删 除 7、向一个栈顶指针为HS的链栈中插入一个s所指结点时，则执行__ _C_。(不带空的头结点) (易) A、HS—＞next=s;9 B、s—＞next= HS—＞next; HS—＞next=s; C、s—＞next= HS; HS=s; D、s—＞next= HS; HS= HS—＞next 数据结构考试及答案（） 作者: 日期: 2 数据结构试题 一、单选题 1、在数据结构的讨论中把数据结构从逻辑上分为（C） A 内部结构与外部结构 B 静态结构与动态结构 C 线性结构与非线性结构 D 紧凑结构与非紧凑结构。 2、采用线性链表表示一个向量时，要求占用的存储空间地址（D） A 必须是连续的B部分地址必须是连续的 C 一定是不连续的D可连续可不连续 3、采用顺序搜索方法查找长度为n的顺序表时，搜索成功的平均搜索长度为 （D ）。 An B n/2 C （n-1）/2 D （n+1）/2 4、在一个单链表中，若q结点是p结点的前驱结点，若在q与p之间插入结点s，则执行（D ）o A s—link = p—link ；p—link = s； B p—link = s; s—link = q; C p—link = s—link ；s—link = p； D q—link = s; s—link = p; 5、如果想在4092个数据中只需要选择其中最小的5个，采用（C ）方法最好。 A 起泡排序 B 堆排序C锦标赛排序 D 快速 排序 6、设有两个串t和p，求p在t中首次出现的位置的运算叫做（B ）o A 求子串B模式匹配C 串替换 D 串连接 7、在数组A中，每一个数组元素A[i][j] 占用3个存储字，行下标i从1到8, 列下标j从1到10。所有数组元素相继存放于一个连续的存储空间中，则存放 该数组至少需要的存储字数是（ C ）。 A 80 B 100 C 240 D 270 8、将一个递归算法改为对应的非递归算法时，通常需要使用（ A ）。 A 栈B队列C循环队列D优先队列 9、一个队列的进队列顺序是1,2, 3, 4 ，则出队列顺序为（C ）。 10、在循环队列中用数组A[0.. m-1]存放队列元素，其队头和队尾指针分别为front和rear，则当前队列中的元素个数是（ D ）。 A （ front - rear + 1） % m B （rear - front + 1） %m C （ front - rear + m） % m D （ rear - front + n） % m 11、一个数组元素a[i]与（A ）的表示等价。 A * （a+i） B a+i C *a+i D &a+i 12、若需要利用形参直接访问实参，则应把形参变量说明为（ B ）参数 A指针 B 引用C值 D 变量 13、下面程序段的时间复杂度为（C) for (i nt i=0;i 《数据结构》题库及答案 一、选择题 1．线性表的顺序存储结构是一种 的存储结构，线性表的链式存储结构是一种 的存储结构。 a. 随机存储； b.顺序存储； c. 索引存取； d. HASH 存取 2．一个栈的入栈序列是a,b,c,d,e ，则栈的不可能的输出序列是 。 a. edcba; b. decba; c. dceab; d.abcde 3．一个队列的入队序列是1，2，3，4，则队列的输出序列是 。 a. 4,3,2,1; b. 1,2,3,4; c. 1,4,3,2; d.3,2,4,1 4．在一个单链表中，已知p 结点是q 结点的直接前驱结点，若在p 和q 之间插入结点s ，则执行的操作是 。 a. s->nxet=p->next; p->next=s; b. p->next=s->next; s->next=p; c. q->next=s; s->next=p; d. p->next=s; s->next=q; 5．设有两个串p,q ，求q 在p 中首次出现的位置的运算称作 。 a.联接 b.模式匹配 c.求子串 d.求串长 6．二维数组M 的成员是6个字符（每个字符占一个存储单元）组成的串，行下标i 的范围从0到8，列下标j 的范围从1到10，则存放M 至少需要 个字节。 a. 90 b.180 c.240 d.540 7．在线索二叉树中，结点p 没有左子树的充要条件是 。 a. p->lch==NULL b. p->ltag==1 c. p->ltag==1且p->lch=NULL d. 以上都不对 8．在栈操作中，输入序列为（A ，B ，C ，D ），不可能得到的输出序列为：______ A 、（A ， B ， C ， D ） B 、（D ，C ，B ，A ） C 、（A ，C ，D ，B ） D 、（C ，A ，B ，D ） 9．已知某二叉树的后序序列是dabec ，中序序列是debac ，则它的先序序列是 。 A 、acbed B 、decab C 、deabc D 、cedba 10．设矩阵A 是一个对称矩阵，为了节省存储空间，将其下三角部分（见下图）按行序存放在一维数组B[1..n(n-1)/2]中，对任一上三角部分元素)(j i a ij ，在一维数组B 的存放位置是 。 广东创新科技职业学院期末考试试题（标明A 卷、B 或C 卷） 2018 —2019 学年第二学期考试科目：《数据结构》 (闭（开）卷 90分钟) 院系____________ 班级____________ 学号___________ 姓名 __________ 一、选择题（每小题 2 分，共 40 分） 1.计算机识别、存储和加工处理的对象被统称为（）。 A ．数据 B ．数据元素 C ．数据结构 D ．数据类型 2.数据结构指的是数据之间的相互关系，即数据的组织形式。数据结构一般包括（）三方面内容。 A ．数据的逻辑结构、数据的存储结构、数据的描述 B ．数据的逻辑结构、数据的存储结构、数据的运算 C ．数据的存储结构、数据的运算、数据的描述 D ．数据的逻辑结构、数据的运算、数据的描述3．数据的逻辑结构包括（）。 A ．线性结构和非线性结构 B ．线性结构和树型结构 C ．非线性结构和集合结构 D ．线性结构和图状结构 4.（）的特征是：有且仅有一个开始结点和一个终端结点，且所有结点都最多只有一个直接前驱和一个直接后继。 A ．线性结构 B ．非线性结构 C ．树型结构 D ．图状结构 5. 评价一个算法时间性能的主要标准是（）。 A ．算法易于调试 B ．算法易于理解 C ．算法的稳定性和正确性 D ．算法的时间复杂度 6. 下述程序段①中各语句执行频度的和是（）。 s=0; ① for(i=1;i<=i;j++) s+=j; A ．n-1 B ．n C ．2n-1 D ．2n 7. 下面程序段的时间复杂度为（）。 for(i=0;i 2012年数据结构期末考试题及答案 一、选择题 1．在数据结构中，从逻辑上可以把数据结构分为C。 A．动态结构和静态结构B．紧凑结构和非紧凑结构 C．线性结构和非线性结构D．内部结构和外部结构 2．数据结构在计算机内存中的表示是指A。 A．数据的存储结构B．数据结构C．数据的逻辑结构D．数据元素之间的关系 3．在数据结构中，与所使用的计算机无关的是数据的A结构。 A．逻辑B．存储C．逻辑和存储D．物理 4．在存储数据时，通常不仅要存储各数据元素的值，而且还要存储C。 A．数据的处理方法B．数据元素的类型 C．数据元素之间的关系D．数据的存储方法 5．在决定选取何种存储结构时，一般不考虑A。 A．各结点的值如何B．结点个数的多少 C．对数据有哪些运算D．所用的编程语言实现这种结构是否方便。 6．以下说法正确的是D。 A．数据项是数据的基本单位 B．数据元素是数据的最小单位 C．数据结构是带结构的数据项的集合 D．一些表面上很不相同的数据可以有相同的逻辑结构 7．算法分析的目的是C，算法分析的两个主要方面是A。 （1）A．找出数据结构的合理性B．研究算法中的输入和输出的关系 C．分析算法的效率以求改进C．分析算法的易读性和文档性 （2）A．空间复杂度和时间复杂度B．正确性和简明性 C．可读性和文档性D．数据复杂性和程序复杂性 8．下面程序段的时间复杂度是O（n2）。 s ＝0； for（I ＝0；i＜n；i＋＋） for（j＝0；j＜n；j＋＋） s ＋＝B[i][j]； sum ＝s ； 9．下面程序段的时间复杂度是O（n*m）。 for（i ＝0；i＜n；i＋＋） for（j＝0；j＜m；j＋＋） A[i][j] ＝0； 10．下面程序段的时间复杂度是O（log3n）。 i ＝0； while（i＜＝n） i ＝i * 3； 11．在以下的叙述中，正确的是B。 A．线性表的顺序存储结构优于链表存储结构 B．二维数组是其数据元素为线性表的线性表 C．栈的操作方式是先进先出 D．队列的操作方式是先进后出 12．通常要求同一逻辑结构中的所有数据元素具有相同的特性，这意味着B 。 A．数据元素具有同一特点 B．不仅数据元素所包含的数据项的个数要相同，而且对应的数据项的类型要一致 C．每个数据元素都一样 D．数据元素所包含的数据项的个数要相等 13．链表不具备的特点是A。 A．可随机访问任一结点B．插入删除不需要移动元素 C．不必事先估计存储空间D．所需空间与其长度成正比 14．不带头结点的单链表head为空的判定条件是A。 数据结构试题库及答案 第一章 概论 一、选择题 1 、研究数据结构就是研究（ D ）。 A. 数据的逻辑结构 B. 数据的存储结构 C. 数据的逻辑结构和存储结构 D. 数据的逻辑结构、存储结构及其基本操作 2 、算法分析的两个主要方面是（ A ）。 A. 空间复杂度和时间复杂度 B. 正确性和简单性 C. 可读性和文档性 D. 数据复杂性和程序复杂性 3 、具有线性结构的数据结构是（ D ）。 A. 图 B. 树 C. 广义表 D. 栈 4 、计算机中的算法指的是解决某一个问题的有限运算序列，它必须具备输入、输出、 （ B ）等 5 个 特性。 A. 可执行性、可移植性和可扩充性 B. 可执行性、有穷性和确定性 C. 确定性、有穷性和稳定性 D.易读性、稳定性和确定性 5 、下面程序段的时间复杂度是（ C ）。 for(i=0;i 数据结构习题 习题一 一、选择题 1、算法分析的两个主要方面是：（） A．正确性和简明性B．时间复杂度和空间复杂度 C．数据复杂性和程序复杂性D．可读性和文档性 2、在数据结构中，从逻辑上可以把数据结构分成（）。 A．动态结构和静态结构 B．紧凑结构和非紧凑结构 C．线性结构和非线性结构 D．逻辑结构和存储结构 3、计算机算法具备输入、输出和（）等5个特性： A．有穷性、确定性和稳定性B．可行性、可移植性和可扩充性 C．有穷性、确定性和可行性D．易读性、稳定性和安全性 4、算法分析的目的是（）。 A．找出算法的合理性 B．研究算法的输人与输出关系 C．分析算法的有效性以求改进 D．分析算法的易懂性 二、填空题 1、数据结构是一门研究非数值计算的程序设计问题中计算机的以及它们之间的和运算等的学科。 2、线性结构中元素之间存在的关系，树形结构中元素之间存在的关系， 图形结构中元素之间存在的关系。 3、________是数据不可分割的最小单元，是具有独立含义的最小标识单位。例如构成一个数据元素的字段、域、属性等都可称之为________。 4、数据的________指数据元素及其关系在计算机存储器内的表示。_________是逻辑结构在计算机里的实现，也称之为映像。 5、所谓算法（Algorithm）是对特定问题求解方法和步骤的一种描述，它是指令的一组__________，其中每个指令表示一个或多个操作。 三、问答题 1、用大O形式写出下面算法的时间复杂度： i＝0； s=0； while(s＜n） ｛ i++; s+=i; ｝ 2、写出以下算法的时间复杂度： for（i＝0; i＜m; i＋＋） for（j＝0 ; j＜t; j＋＋） c[i][j]=0； for（i=0；i＜m；i＋＋） for（j=o; j 贵州大学理学院数学系信息与计算科学专业 《数据结构》期末考试试题及答案 (2003-2004学年第2学期) 一、单项选择题 1．对于一个算法，当输入非法数据时，也要能作出相应的处理，这种要求称为（）。 (A)、正确性(B). 可行性(C). 健壮性(D). 输入性 2．设S为C语言的语句,计算机执行下面算法时，算法的时间复杂度为（）。 for(i=n-1；i>=0；i--) for(j=0；j 绪论 一、填空题 1.数据的逻辑结构被分为集合、（线性结构）、（树形结构）和（图状结构）四种。 2. 物理结构是数据结构在计算机中的表示，又称为（存储结构）。 3. 数据元素的逻辑结构包括（线性）、（树）和图状结构3 种类型，树形结构和图状结构合称为（非线性结构）。 4. （数据元素）是数据的基本单位，（数据项）是数据不可分割的最小单位。 5. 线性结构中元素之间存在（一个对一个）关系，树形结构中元素之间存在（一个对多个）关系，图状结构中元素之间存在（多个对多个）关系。 ？ 6.数据结构是一门研究非数值计算的程序设计问题中：计算机的（数据元素）以及它们之间的（关 系）和（运筹）等的学科。 7. 算法的五个重要特性为有穷性、确定性、（输入）、（输出）和（可行性）。 二、选择题 1. 数据的不可分割的基本单位是（D）。 A.元素 B.结点C数据类型D.数据项 *2. 线性表的逻辑顺序与存储顺序总是一致的，这种说法（B）。 A.正确 B.不正确C不确定 D.无法选择 3. 线性结构是指数据元素之间存在一种（D）。 A.一对多关系 B.多对多关系C多对一关系D.—对一关系 4. 在数据结构中，从逻辑上可以把数据结构分成（A）。 A.动态结构和静态结构 B.紧凑结构和非紧凑结构 C线性结构和非线性结构D.内部结构和外部结构 5. 线性表若采用链式存储结构时，要求内存中可用存储单元的地址（D）。 A.必须是连续的 B.部分地址必须是连续的 C. 一定是不连续的 D.连续不连续都可以 三、简答题 1. 算法的特性是什么。 答：有穷性确定性可行性有0 或多个输入有 1 或多个输出 线性结构 一、填空题 1?在一个长度为n的线性表中删除第i个元素（1< i产时，需向前移动（n-i）个元素。 2. 从循环队列中删除一个元素时，其操作是（先移动队首指针，后取出元素）。 3?在线性表的单链接存储中，若一个元素所在结点的地址为p,则其后继结点的地址为（p-> next）。 4. 在一个单链表中指针p所指向结点的后面插入一个指针q所指向的结点时，首先把（p->next）的值赋给q->next，然后（q->date）的值赋给p->next。 5. 从一个栈删除元素时，首先取出（栈顶元素），然后再使（栈顶指针）减1。 6. 子串的定位操作通常称做串的（模式匹配）。 7. 设目标T= ‘ abccdcdccba,模式P= ‘ cdc则第（六）次匹配成功。。 8. 顺序栈S 中，出栈操作时要执行的语句序列中有S->top（--）；进栈操作时要执行的语句序列中有S->top（++）。数据结构考试题库
数据结构试题(含答案)
数据结构期末考试试题及答案
数据结构考试题库含答案
数据结构题库教材
数据结构复习资料,java数据结构期末考试
《数据结构》期末考试题及答案
数据结构试题及答案
数据结构相关题库及答案
数据结构考试及答案()
《数据结构》题库及答案
《数据结构》期末考试试卷
2015年数据结构期末考试题及答案
数据结构试题库与答案
数据结构题库汇总
数据结构期末考试试题及答案
数据结构考试题库
相关主题
文本预览