数据结构习题集含
目录 1
选择题 2
第一章绪论 2
第二章 线性
4
第三章 栈和队列 5
第四章 串 6
第五章 数组和广义表 7
第六章 树和二叉树 7
第七章 图 9
第八章 查找 11
第九章 排序 12
简答题 15
第一章绪论 15
第二章 线性表 20
第三章 栈和队列 22
第四章 串 24
第五章 数组和广义表 24
第六章 树和二叉树 26
第七章 图 31
第八章 查找 33
第九章 排序 34
编程题 36
第一章绪论 36
第二章线性表 36
第三章 栈和队列 46
第四章 串 46
第五章 数组和广义表 46
第六章 树和二叉树 46
第七章 图 46
第八章 查找 46
第九章 排序 51
选择题
第一章绪论
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、无共同点