1. 填空。
（ ）是数据的基本单位，在计算机程序中通常作为一个整体进行考虑和处理。
（ ）是数据的最小单位，（ 是讨论数据结构时涉及的最小数据单位。
从逻辑关系上讲，数据结构主要分为和（ ）
数据的存储结构主要有（ ）和（ ）两种基本方法，不论哪种存储结构，都要存储两方面的内容：（ 和（ ）
算法具有五个特性，分别是。
算法的描述方法通常有和（ ）四种，其中，（ 被称为算法语言。
在一般情况下，一个算法的时间复杂度是（ ）的函数。
设待处理问题的规模为n，若一个算法的时间复杂度为一个常数，则表示成数量级的形式为（ ）若为n*log25n，则表示成数量级的形式为（ ）
2. 选择题
顺序存储结构中数据元素之间的逻辑关系是由（ ）表示的，链接存储结构中的数据元素之间的逻辑关系是由（ ）表示的。
假设有如下遗产继承规则：丈夫和妻子可以相互继承遗产；子女可以继承父亲或母亲的遗产；子女间不能相互继承。则表示该遗产继承关系的最合适的数据结构应该是（ ）
a 树 b 图 c 线性表 d 集合。
算法指的是（ ）
a 对特定问题求解步骤的一种描述，是指令的有限序列。
b 计算机程序 c 解决问题的计算方法 d 数据处理。
下面（ ）不是算法所必须具备的特性。
a 有穷性 b 确切性 c 高效性 d 可行性
算法分析的目的是（ ）算法分析的两个主要方面是（ ）
3. 判断题。
算法的时间复杂度都要通过算法中的基本语句的执行次数来确定。
每种数据结构都具备三个基本操作：插入、删除和查找。
所谓数据的逻辑结构指的是数据之间的逻辑关系。
逻辑结构与数据元素本身的内容和形式无关。
基于某种逻辑结构之上的基本操作，其实现是唯一的。
4. 分析以下各程序段，并用大o记号表示其执行时间。
5．设有数据结构（d，r），其中d=，r=。试画出其逻辑结构图并指出属于何种结构。
6. 为整数定义一个抽象数据类型，包含整数的常见运算，每个运算对应一个基本操作，每个基本操作的接口需定义前置条件、输入、功能、输出和后置条件。
7. 求多项式a(x)的算法可根据下列两个公式之一来设计：
a(x)=anxn+an-1xn-1+…+a1x+a0
a(x)=(anx+an-1)x+…+a1)x)+a0
根据算法的时间复杂度分析比较这两种算法的优劣。
8. 算法设计（要求：算法用伪**和c++描述，并分析最坏情况下的时间复杂度）
对一个整型数组a[n]设计一个排序算法。
找出整型数组a[n]中元素的最大值和次最大值。
1．顺序存储结构的特点是（ ）链接存储结构的特点是（ ）
2. 算法在发生非法操作时可以作出处理的特性称为（ ）
3. 常见的算法时间复杂度用大ｏ记号表示为：常数阶( )对数阶( )线性阶 ( 平方阶( )和指数阶( )
4．将下列函数按它们在n 时的无穷大阶数，从小到大排列。
5．试描述数据结构和抽象数据类型的概念与程序设计语言中数据类型概念的区别。
6. 对下列用二元组表示的数据结构，试分别画出对应的逻辑结构图，并指出属于何种结构。
a=(d，r)， 其中d=，r=
b=(d，r)， 其中d=，r=
c=( d，r)，其中d=，r=
d=(d，r)， 其中d=，r=
7. 求下列算法的时间复杂度。
count=0; x=1;
while (x)
x*=2;
count++;
return count;
1. 填空。
在顺序表中，等概率情况下，插入和删除一个元素平均需移动（ ）个元素，具体移动元素的个数与（ ）和（ ）有关。
顺序表中第一个元素的存储地址是100，每个元素的长度为2，则第5个元素的存储地址是（ ）
设单链表中指针p 指向结点a，若要删除a的后继结点（假设a存在后继结点），则需修改指针的操作为（ ）
单链表中设置头结点的作用是（ ）
非空的单循环链表由头指针head指示，则其尾结点（由指针p所指）满足（ ）
在由尾指针rear指示的单循环链表中，在表尾插入一个结点s的操作序列是（ ）删除开始结点的操作序列为（ ）
一个具有n个结点的单链表，在指针p所指结点后插入一个新结点的时间复杂度为（ ）在给定值为x的结点后插入一个新结点的时间复杂度为（ ）
可由一个尾指针唯一确定的链表有。
2. 选择题。
线性表的顺序存储结构是一种（ ）的存储结构，线性表的链接存储结构是一种（ ）的存储结构。
a 随机存取 b 顺序存取 c 索引存取 d 散列存取。
线性表采用链接存储时，其地址（ ）
a 必须是连续的 b 部分地址必须是连续的。
c 一定是不连续的 d 连续与否均可以。
单循环链表的主要优点是（ ）
a 不再需要头指针了
b 从表中任一结点出发都能扫描到整个链表；
c 已知某个结点的位置后，能够容易找到它的直接前趋；
d 在进行插入、删除操作时，能更好地保证链表不断开。
链表不具有的特点是（ ）
a 可随机访问任一元素 b 插入、删除不需要移动元素。
c 不必事先估计存储空间 d 所需空间与线性表长度成正比
若某线性表中最常用的操作是取第i 个元素和找第i个元素的前趋，则采用（ ）存储方法最节省时间。
a 顺序表 b 单链表 c 双链表 d 单循环链表。
若链表中最常用的操作是在最后一个结点之后插入一个结点和删除第一个结点，则采用（ ）存储方法最节省时间。
a 单链表 b 带头指针的单循环链表 c 双链表 d 带尾指针的单循环链表。
若链表中最常用的操作是在最后一个结点之后插入一个结点和删除最后一个结点，则采用（ ）存储方法最节省运算时间。
a 单链表 b 循环双链表 c单循环链表 d 带尾指针的单循环链表。
在具有n个结点的有序单链表中插入一个新结点并仍然有序的时间复杂度是（ ）
a o(1) b o(n) c o(n2) d o(nlog2n)
对于n个元素组成的线性表，建立一个有序单链表的时间复杂度是（ ）
a o(1) b o(n) c o(n2) d o(nlog2n)
使用双链表存储线性表，其优点是可以（ ）
a 提高查找速度 b 更方便数据的插入和删除。
c 节约存储空间 d 很快**存储空间。
在一个单链表中，已知q所指结点是p所指结点的直接前驱，若在q和p之间插入s所指结点，则执行（ ）操作。
a s->next=p->next; p->next=s; b q->next=s; s->next=p;
c p->next=s->next; s->next=p; d p->next=s; s->next=q;
在循环双链表的p所指结点后插入s所指结点的操作是（ ）
a p->next=s; s->prior=p; p->next->prior=s; s->next=p->next;
b p->next=s; p->next->prior=s; s->prior=p; s->next=p->next;
c s->prior=p; s->next=p->next; p->next=s; p->next->prior=s;
d s->prior=p; s->next=p->next; p->next->prior=s; p->next=s
3. 判断题。
线性表的逻辑顺序和存储顺序总是一致的。
线性表的顺序存储结构优于链接存储结构。
设p，q是指针，若p=q，则*p=*q。
线性结构的基本特征是：每个元素有且仅有一个直接前驱和一个直接后继。
在单链表中，要取得某个元素，只要知道该元素所在结点的地址即可，因此单链表是随机存取结构。
4．请说明顺序表和单链表各有何优缺点，并分析下列情况下，采用何种存储结构更好些。
若线性表的总长度基本稳定，且很少进行插入和删除操作，但要求以最快的速度存取线性表中的元素。
如果n个线性表同时并存，并且在处理过程中各表的长度会动态发生变化。
描述一个城市的设计和规划。
5．算法设计。
设计一个时间复杂度为ｏ(n)的算法，实现将数组a[n]中所有元素循环右移k个位置。
已知数组a[n]中的元素为整型，设计算法将其调整为左右两部分，左边所有元素为奇数，右边所有元素为偶数，并要求算法的时间复杂度为ｏ(n)。
试编写在无头结点的单链表上实现线性表的插入操作的算法，并和带头结点的单链表上的插入操作的实现进行比较。
试分别以顺序表和单链表作存储结构，各写一实现线性表就地逆置的算法。
假设在长度大于1的循环链表中，即无头结点也无头指针，s为指向链表中某个结点的指针，试编写算法删除结点s的前趋结点。
已知一单链表中的数据元素含有三类字符：字母、数字和其他字符。试编写算法，构造三个循环链表，使每个循环链表中只含同一类字符。
设单链表以非递减有序排列，设计算法实现在单链表中删去值相同的多余结点。
判断带头结点的双循环链表是否对称。
1. 已知一维数组a采用顺序存储结构，每个元素占用4个存储单元，第9个元素的地址为144，则第一个元素的地址是（ ）
a 108 b 180 c 176 d 112
2．在长度为n的线性表中查找值为x的数据元素的时间复杂度为： （
a o(0) b o(1) c o(n) d o(n2)
数据结构练习
一 选择题 1 若长度为n的线性表采用顺序存储结构，删除它的第i数据元素之前，需要先依次向前移动 个数据元素。a 2.在单链表中，已知q指的结点是p指的结点的直接前驱结点，若在q和p指的结点之间插入一个由s指的结点，则需执行b a.q next p s next p b.s next p q nex...
数据结构练习
第1章。1.从逻辑上可以把数据结构分为。a 动态结构 静态结构 b 顺序结构 链式结构。c.线性结构 非线性结构 d 初等结构 构造型结构。2.关于算法的描述，不正确的是。a.算法最终必须由计算机程序实现。b 所谓时间复杂度是指最坏情况下，估算算法执行时间的一个上界。c.健壮的算法不会因非法的输人数...
数据结构练习
一 选择题。1 广度优先遍历的含义是 从图中某个顶点v出发，在访问了v之后依次访问v的各个未被访问过的邻接点，然后分别从这些邻接点出发依次访问它们的邻接点，且 先被访问的顶点的邻接点 先于 后被访问的顶点的邻接点 被访问，直至图中所有已被访问的顶点的邻接点都被访问到是下图的广度优先遍历序列。a.1 ...