数据结构各章习题练习
- 格式：doc
- 大小：56.00 KB
- 文档页数：5
一、选择题
1．数据结构是一门研究计算机中____对象及其关系的学科。
（1）数值运算 （2）非数值运算
（3）集合 （4）非集合
2．数据结构的定义为(K，R)，其中K是____的集合。
（1）算法 （2）数据元素
（3）数据操作 （4）逻辑结构
3．算法分析的目的是____。
（1） 找出数据结构的合理性
（2） 研究算法中输入和输出的关系
（3） 分析算法的效率以求改进
（4） 分析算法的易懂性和文档性
4．在一个单链表中，若p所指结点不是最后结点，在p之后插入s所指结点，则执行___。
（1）s->link=p;p->next=s;
（2）s->link=p->link;p->link=s;
（3）s->link=p->link;p=s;
（4）p->link=s;s->link=p;
9 与数据元素本身的形式、内容、相对位置、个数无关的是数据的 ( )。
A. 存储结构 B. 逻辑结构
C. 算法 D. 操作
10 用链表表示线性表的优点是 ( )。
A. 便于随机存取 B. 花费的存储空间比顺序表少
C. 便于插入与删除 D. 数据元素的物理顺序与逻辑顺序相同
11、数据结构是研究数据的（ ）及它们之间的相互联系。
A、理想结构，物理结构 b、理想结构，逻辑结构
C、物理结构，逻辑结构 d、抽象结构，逻辑结构
12、线性表是（ ）。
a、一个有限系列，可以为空 b、一个有限系列，不能为空
c、一个无限系列，可以为空 d、一个无限系列，不能为空
13、组成数据的基本单位是 （ ） 。
a、数据项 b、数据类型 c、数据元素 d、数据变量
14、线性表的链接实现有利于（ ）运算。
A、插入 b、读表元 c、查找 d、定位
15 线性表采用链式存储时，其地址（ ）
A 必须是连续的 B 部分地址是连续的
C 一定是不连续的 D 连续与否均可以
16、设单链表中指针p指着结点a，若要删除a之后的结点（若存在），则需要修改指针的操作为（ ）。
A、p->next=p->next->next b、p=p->next
C、 p= p->next->next d、p->next=p
第三章
1．输入序列为（A,B,C,D）不可能的输出有（ ）。
A (A,B,C,D) B (D,C,B,A) C (A,C,D,B) D (C,A,B,D) 2 链式栈与顺序栈相比，一个比较明显的优点是 ( )。
A. 插入操作更加方便 B. 通常不会出现栈满的情况
C. 不会出现栈空的情况 D. 删除操作更加方便
3 在一个顺序存储的循环队列中，队头指针指向队头元素的 ( )。
A. 前一个位置 B. 后一个位置
C. 队头元素位置 D. 队尾元素的前一位置
5．栈的数组表示中，top为栈顶指针，栈空的条件是____。
（1） top=0 （2）top=maxSize
（2） top=maxSize（4）top=-1
6．在数组表示的循环队列中，front、rear分别为队列的头、尾指针，maxSize为数组的最大长度，队满的条件是____。
（1） front=maxSize （2）(rear+1)%maxSize=front
（2） rear=maxSize （4）rear=front
7．栈和队列的共同特点是____。
（1） 都是先进后出 （2）都是先进先出
（2） 只允许在端点处插入和删除 （4）没有共同点
第四章
6．设有串t=’I am a good student ’，那么Substr(t,6,6)=（ ）。
A student B a good s C good D a good
第六章
1、若已知一棵二叉树先序序列为ABCDEFG，中序序列为CBDAEGF，则其后序序列为(a)
A CDBGFEA B CDBFGEA C CDBAGFE D BCDAGFE
4、具有2000个结点的二叉树，其高度至少为（ C ）。
A、９ b、１０ c、１１ d、１２
5、中序遍历一棵二叉排序树所得到的结点序列是键值的（ ）序列。
A、递增或递减 b、递减 c、递增 d、无序
6．在一棵具有5层的满二叉树中结点总数为 ( )。
A. 31 B. 32 C. 33 D. 16
7含5个结点（元素值均不相同）的二叉搜索树有（ ）种。
A、54 B、42 C、36 D、65
8一个二叉树按顺序方式存储在一个维数组中，如图
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14
A B C D E F G H I J
则结点E在二叉树的第（ ）层。
A、1 B、2 C、3 D、4
第七章
2．具有 n 个顶点的有向完全图有（ ）条弧。
A n B n*(n-1) C n*(n+1) D n*n
3 n 个顶点的连通图至少有（ ）条边。
A、n-1 B 、n C、n+1 D、0
第九章 1排序趟数与序列的原始状态(原始排列)有关的排序方法是（ ）排序方法。
A 插入 B 选择 C 冒泡 D 快速
2．设有100个数据元素，采用折半搜索时，最大比较次数为 ( )。
A. 6 B. 7 C. 8 D. 10
3 对待排序的元素序列进行划分，将其分为左、右两个子序列，再对两个子序列施加同样的排序操作，直到子序列为空或只剩一个元素为止。这样的排序方法是 ( )。
A. 直接选择排序 B. 直接插入排序
C. 快速排序 D. 起泡排序
4 对5个不同的数据元素进行直接插入排序，最多需要进行 ( ) 次比较。
A. 8 B. 10 C. 15 D. 25
9、采用折半查找方法进行查找，数据文件应为（ ），且限于（ ）。
A 有序表 顺序存储结构 B 有序表 链式存储结构
C 随机表 顺序存储结构 D 随机表 链式存储结构
10、从未排序序列中依次取出一个元素与已排序序列中的元素依次进行比较，然后将其存放在已排序序列的合适位置，该排序方法称为（ ）排序法。
A 插入 B 选择 C 希尔 D 二路并归
12．将递归算法转换成对应的非递归算法时，通常需要使用____。
（1）栈 （2）队列 （3）链表 （4）数组
二、填空题
第一二章
1、算法是指令的有限序列，其中每一条指令表示一个或多个操作，此外，一个算法还具有五个重要特性，它们分别是 有穷性 、 确定性 、 可行性 、有零或多个输入和有一或多个输出。
2、循环链表的主要优点是 从任何一个结点出发可以遍历所有结点 。
3．为度量一个搜索算法的性能，需要在_______ 时间______和空间复杂度方面进行权衡。
4． 算法优劣的五个标准是正确性、可使用性、_可读性 健壮性 效率___、____、____。
5． 下面程序段的时间复杂度是_____。
For(i=0;i
For(j=0;j
A[i][j]=0;
6． 用顺序存储方式实现的线形表，称为____线性表____。
7． 单链表是__线性表____的链接存储表示。
8． 在一个单链表中删除p所指结点的下一个结点时，应执行以下操作：
q=p->link;
p->link=____ q ->link__
Delete q
9． 将适当的语句添入单链表搜索函数find中。
templateListNode*List::find(Type value){
current=frist->link
while(current!=NULL)
if(current->data=value)break
else current=current->link;
return _______
} 10．算法是指令的有限序列，其中每一条指令表示一个或多个操作，此外，一个算法还具有五个重要特性，它们分别是 、 、可行性、有零或多个输入和有一或多个输出。
11．为度量一个搜索算法的性能，需要在时间复杂度和空间复杂度方面进行权衡。
12数据结构是一门研究非数值计算的程序设计问题中计算机的 非数值计算 以及它们之间____关系和操作______的等等的学科。
第三四章
1设有串t=’I am a student ’，s=’good’，那么Concat(t,s)= ’I am a student good’，Substr(t,8,7)= ‘student’ 。
2在解决计算机主机与打印机之间速度不匹配问题时通常设置一个打印数据缓冲区，主机将要输出的数据依次写入该缓冲区，而打印机则从该缓冲区中取出数据打印。该缓冲区应该是一个 队列 结构，其主要特点是 先进先出 。
3对于一个以顺序实现的循环队列Q[0…m-1]，队头、队尾指针分别为f、r，其判空的条件是 r=f ，判满的条件是 (r+1)%m=f 。
4． 设有两个串p和q，求p在q中首次出现的位置的运算称为_________。
