数据结构试题
第一章绪论
一、选择题：
1、在数据结构中，从逻辑上可以把数据结构分成（）。
A、动态结构和静态结构
B、紧凑结构和非紧凑结构
C、线性结构和非线性结构
D、内部结构和外部结构
2、算法分析的两个主要方面是（）。
A、空间复杂性和时间复杂性
B、正确性和简明性
C、可读性和文档性
D、数据复杂性和程序复杂性
3、以下与数据的存储结构无关的术语是（）。
A、循环队列
B、链表
C、哈希表
D、栈
4、以下数据结构中，哪一个是线性结构（）。
A．广义表B、二叉树C、稀疏矩阵D、串
5、在下面的程序段中，对x的赋值语句的频度为（）。
FOR i:=1TO n DO
FOR j:=1TO n DO
x:=x+1;
n)
A、O(2n)
B、O(n)
C、O(n2)
D、O(log
2
6、以下哪个数据结构不是多型数据类型（）。
A、栈
B、广义表
C、有向图
D、字符串
7、以下数据结构中，（）是非线性数据结构。
A、树
B、字符串
C、队
D、栈
8、以下属于逻辑结构的是（）。
A、顺序表  B.哈希表C、有序表D、单链表
9、下列程序段的时间复杂度为（）。
s=0；
for(i=1；i<n；i++)
for(j=1；j<n；j++)
s+=ij；
A、O(1)
B、O(n)
C、O(2n)
D、O(n2)
10、数据结构是（）。
A、一种数据类型
B、相互之间存在一种或多种特定关系的数据元素的集合
C、一组性质相同的数据元素的集合
D、数据的存储结构
11、算法分析的目的是（）。字符串是什么数据结构
A、辨别数据结构的合理性
B、评价算法的效率
C、研究算法中输入与输出的关系
D、鉴别算法的可读性
12、下面程序段的时间复杂度为（）。
for(int i=0;i<m;i++)
for(int j=0;j<n;j++)
a[i][j]=ij;
A、O(m2)
B、O(n2)
C、O(mn)
D、O(m+n)
13、执行下面程序段时，执行S语句的次数为（）。
for(int i=1;i<=n;i++)
for(int j=1;j<=i;j++)
S;
A、n2
B、n2/2
C、n(n+1)
D、n(n+1)/2
14、算法的可读性是指（）。
A、算法所含语句数较少
B、算法较简单，计算机容易编译
C、算法较简单，人们很容易看出它的执行结果
D、算法结构清晰，容易被算法设计者及其同行看懂
15、算法分析的主要任务是分析（）。
A、算法是否具有较好的可读性
B、算法中是否存在语法错误
C、算法的功能是否符合设计要求
D、算法的执行时间和问题规模之间的关系
二、填空题：
1、在数据逻辑结构的二元组S=（D，R）表示中，D是（），R是（）。
2、没有前驱的结点称为（），没有后继的结点称为（）。
3、数据的逻辑结构可以分为（）和（）两大类。
4、在树形结构中，每个结点最多只有一个（）。
5、为了实现随机访问，线性结构应该采用（）存储。
6、逻辑上相邻的结点在存储器中也相邻，这是（）存储结构的特点。
7、数据的运算是在（）上定义的，运算的具体实现与（）结构有关。
8、用数量级形式表示的算法执行时间称为算法的（）。
9、算法的执行时间是（）的函数。
10、在高级语言程序中，表示一组连续的存储单元，通常用（）。
11、数据的物理结构包括（）的表示和（）的表示。
12、对于给定的n个元素，可以构造出的逻辑结构有（），（），（），（）四种。
13、一个算法具有5个特性:（）、（）、（）、有零个或多个输入、有一个或多个输出。
14、一个算法的时间复杂度为(3n2+2nlog2n+4n-7)/(5n)，其数量级表示为（）。
15、在线性结构、树形结构和图形结构中，前驱和后继结点之间分别存在着（）、（）和（）的联系。
三、判断题：
1、计算机程序处理的对象可分为数据和非数据两大类。（）
2、构成数据的最小单位是数据项。（）
3、数据元素和结点是同一个概念。（）
4、每个结点一般包含若干个字段。（）
5、同一个结点中的各个字段类型可以不相同。（）
6、数据是由一些类型相同的数据元素构成的。（）
7、数据的逻辑结构与各数据元素在计算机中如何存储有关。（）
8、如果数据元素值的大小改变了，则数据的逻辑结构也随之改变。（）
9、逻辑结构相同的数据，结点类型也一定相同。（）
10、逻辑结构相同的数据，可以有多种不同的存储方法。（）
11、逻辑结构不相同的数据，要采用不同的存储方法来存储。（）
12、线性结构的特征之一是：开始结点和终端结点都是唯一的。（）
13、在线性结构中，每个结点都有一个前驱、一个后继。（）
14、线性结构可以看成是树形结构的一个简单特例。（）
15、树型结构可以看成是图状结构的一个简单特例。（）
16、判断某个算法是否容易阅读是算法分析的任务之一。（）
17、算法容易阅读是好算法的主要标志之一。（）
18、算法必须用程序设计语言来书写。（）
19、为了实现随机访问，线性结构只能用顺序方法存储。（）
20、问题的规模越大，其算法也就越长。（）
21、数据元素是数据的最小单位。()
22、记录是数据处理的最小单位。()
23、数据的逻辑结构是指数据的各数据项之间的逻辑关系；()
24、算法的优劣与算法描述语言无关，但与所用计算机有关。()
25、健壮的算法不会因非法的输入数据而出现莫名其妙的状态。()
26、算法可以用不同的语言描述，如果用C语言或PASCAL语言等高级语言来描述，则算法实际上就是程序了。()
27、程序一定是算法。()
28、数据的物理结构是指数据在计算机内的实际存储形式。()
29、在顺序存储结构中，有时也存储数据结构中元素之间的关系。()
30、顺序存储方式的优点是存储密度大，且插入、删除运算效率高。()
四、应用题：
1、评价一个好的算法，您是从哪几方面来考虑的？
2、若有100个学生，每个学生有学号，姓名，平均成绩，采用什么样的数据结构最方便，写出这些结构？
3、在编制管理通讯录的程序时，什么样的数据结构合适?为什么?
4、有下列运行时间函数：
（1）T1(n)=1000;（2）T2(n)=n2+1000n;（3）T3(n)=3n3+100n2+n+1;
分别写出相应的大O表示的运算时间。
五、综合题：
1、设计一数据结构，用来表示某一银行储户的基本信息：账号、姓名、开户年月日、储蓄类型、存入累加数、利息、帐面总数。
2、调用下列C函数f(n)或PASACAL函数f(n)，回答下列问题：
（1）试指出f(n)值的大小，并写出f(n)值的推导过程；
（2）假定n=5，试指出f(5)值的大小和执行f(5)时的输出结果。
C函数：int f(int n)
{int i,j，k,sum=0;
for(i=l;i<n+1;i++)
{for(j=n;j>i-1;j--)
for(k=1;k<j+1;k++)
sum++;
printf("sum=%d\n",sum);
}
return(sum);
}
第二章线性表
一、选择题：
1、一个顺序表所占存储空间的大小与（）无关。
A、顺序表长度
B、结点类型
C、结点中各字段的类型
D、结点存放顺序
2、设内存地址的分配是从小（低地址）到大（高地址）进行的。若存储某结点需要5个内存单元，则该结点的地址，通常是指5个内存单元中（）。
A、第3个单元的地址
B、地址值最小的那个单元的地址
C、地址的一个升序序列
D、地址的一个降序序列。
3、顺序表的长度与（）有关。
A、线性表中有多少个结点
B、每个结点有多少个字段
C、每个结点中各字段的类型
D、存储顺序表的数组类型
4、与单向链表相比，双向链表的优点之一是（）。
A、插入、删除操作更简单
B、可以进行随机访问
C、可以省略表头指针或表尾指针
D、顺序访问相邻结点更灵活
5、动态链表所占用的内存单元地址一定是（）。
A、无序的
B、连续的
C、不连续的
D、部分连续的
6、与动态链表相比，静态链表的缺点之一是（）。
A、插入、删除操作有时不方便
B、存储空间有时得不到充分利用
C、要求各结点具有相同的类型
D、链表中各结点的值只能读取，不能更改
7、如果对线性表的运算只有2种：删除第一个元素；在最后一个元素的后面插入新元素，则最好使用（）。
A、只有表头指针没有表尾指针的循环单向链表
B、只有表尾指针没有表头指针的循环单向链表
C、非循环双向链表
D、循环双向链表
8、设H是带表头结点循环单向链表的表头指针。当这种链表成为空链表时，（）。
A、表头结点指针字段的值为空
B、H的值为空
C、表头结点指针字段的值与H的值相等
D、表头结点指针字段的值与H的地址相等
9．设H是带表头结点循环单向链表的表头指针，p是和H同类型的变量。当p指向链表的最后一个结点时，（）。
A、该结点指针字段的值为空
B、p为空
C、p的值与表头结点指针字段的值相等
D、该结点指针字段的值与H的值相等
10．在长度为n的（）上，删除第一个元素，其算法的时间复杂度是O（l）。
A、只有表头指针的不带表头结点的循环单向链表

版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。