数据结构习题与答案

A、所有的操作算法实现简单B、便于随机存储
C、便于插入和删除D、便于利用零散的存储器空间
3.若长度为n的线性表采用顺序存储结构，在其第i个位置插入一个新元素算法的时间复杂度为C。
A、O(log2n) B、O(1)
C、O(n) D、O(n2)
4.（1）静态链表既有顺序存储的特点，又有动态链表的优点。所以，它存取表中第i个元素的时间与i无关；
4、线性结构的特征：逻辑上满足有且仅有一个开始结点和一个终端结点，且其余结点有且仅有唯一的一个直接前趋和一个直接后继。
5.数据的存储结构被分为顺序、链接、索引和散列4种。
6.存储结构是逻辑结构的存储实现，其基本目标是建立数据的机内表示。
7.数据表示任务是逐步完成的，即数据表示形式的变化过程是：机外表示→
A、带尾指针的非循环链表B、带尾指针的循环链表
C、带头指针的非循环链表D、带头指针的循环链表
2、若用一个大小为6的数组来实现循环队列，且当rear和front的值分别为0和3。当从队列中删除一个元素，再加入两个元素后，rear和front的值分别是B。
A、1和5 B、2和4
C、4和2 D、5和1
3、设栈的输入序列为1、2、3、4，则C不可能是其出栈序列。
push (s,x); }
push (s,x); printf(x)
push(s,y); }
push(s,x);
push(s,'E');
push(s,x);
此题的输出结果是HELOLLL。
5、以下为单链表删除运算，分析算法，请在处填上正确的语句。
void delete_lkist(lklist head,int i)
D、q－＞next=p－＞next;q－＞prior=p;p－＞next=q;p－＞next=q;
8.将两个各有n个元素的有序表归并成一个有序表，其最少的比较次数是A。
A、n b.2n－1 c.2n d.n－1
9.在一个长度为n的顺序表中，在第i个元素（1≤i≤n+1）之前插入一个新元素时须向后移动B个元素。
B、序存储的线性表可以随机存取
C、由于顺序存储要求连续的存储区域，所以在存储管理上不够灵活
D、线性表的链式存储结构优于顺序存储结构
二、判断题
1.线性表采用链表存储时，结点和结点内部的存储空间可以是不连续的。（错）
2.在具有头结点的链式存储结构中，头指针指向链表中的第一个数据结点。（错）
3.顺序存储的线性表可以随机存取。（对）
A、O(1) B、O(n) C、O(n2) D、O(nlog2n)
13.以下说法正确的是D。
A、顺序存储方式的优点是存储密度大且插入、删除运算率高
B、链表的每个结点中都恰好包含一个指针
C、线性表的顺序存储结构优于链式存储结构
D、顺序存储结构属于静态结构而链式结构属于动态结构
14.以下说法错误的是A。
B、对递归定义的数据结构不要使用递归过程
C、过程应是自封闭的，尽量少使用全程变量
D、多采用一些技巧以提高程序的运行效率
二、填空题
1.一个算法有5个特性：有穷性、确定性、可行性、有零个或多个输入、有一个或多个输出。
2.算法的时间复杂度是指该算法所求解问题规模（或频度）的函数。
3.算法的可行性是指每一条指令都应在有限的时间内完成。
A、1243 B、2134 C、1432 D、4312 E、3214
4、已知一算术表达式的中缀形式为A+B*C-D/E，后缀形式为ABC*+DE/-，其前缀形式为C。
A、-A+B*C/DE B、-A+B*CD/E
C、-+*ABC/DE D、-+A*BC/DE
5、设栈的输入序列是1、2、…、n，若输出序列的第一个元素是n，则第i个输出元素是B。
B、(*p).next=s;(*s).next=(*p).next;
C、s－＞next=p－＞next;p－＞next=s－＞next;
D、s－＞next=p－＞next;p－＞next=s;
p
s
图2-6插入结点示意
6.在双向链表存储结构中，删除p所指的结点时须修改指针A。
A、p－＞next－＞prior=p－＞prior;p－＞prior－＞next=p－＞next;
4、写出下列程序段的输出结果。（假设此栈中元素的类型是char）
void main ( ) pop (s,x)
{stack s; push(s,'H');
char x,y; while(!stackEmpty(a))
InitStack(a) {pop(s,y);
x='L', y='O ' printf(y);
{
p=1;
for(j=1;j<=i;j++)
p=p*j;
sum=sum+p;
}
return (sum);
}
T（n）=O（n2）
2、j=1;
while(j<=n)
{j=j*2;
}
O(log2n)
习题二
一、选择题
1.线性表是具有n个C的有限序列。
A、表元素B、字符C、数据元素
D、数据项E、信息项
2.线性表的静态链表存储结构与顺序存储结构相比优点是C。
一、选择题
1.下面说法错误的是C。
（1）算法原地工作的含义是指不需要任何额外的辅助空间。
（2）在相同的规模n下，复杂度O（n）的撒在时间上总是优于复杂度O(2n)的算法。
（3）所谓时间复杂度是指最坏情况下，估算算法执行时间的一个上界。
（4）同一个算法，实现语言的级别越高，执行效率越低。
A、（1）B、（1）（2）C、（1）（4）D、（3）
7.以下说法正确的是D。
A、数据元素是数据的最小单位
B、数据项是数据的基本单位
C、数据结构是带有结构的各数据项的集合
D、一些表面上很不相同的数据可以有相同的逻辑结构
8.以下说法错误的是A。
A、程序设计的实质是数据处理
B、数据的逻辑结构是数据的组织形式，基本运算规定了数据的基本操作方式
C、运算实现是完成运算功能的算法或这些算法的设计
B、p－＞next=p－＞next－＞next;p－＞next－＞prior=p;
C、p－＞prior－＞next=p;p－＞prior=p－＞prior－＞prior;
D、p－＞prior=p－＞next－＞next;p－＞next=p－＞prior－＞prior;
7.在双向循环链表中，在P指针所指的结点后插入q所指向的新结点，其修改指针的操作是C。
4.在单链表中，要访问某个结点，只要知道该结点的指针即可；因此，单链表是一种随机存储结构。（错）
5.在线性表的顺序存储结构中，插入和删除元素时，移动元素的个数与该元素的位置有关。（对）
6.顺序存储结构属于静态结构，链式结构属于动态结构。（对）
3、简述以下算法的功能：
status A (linkedist L)
A、(rear-1)%n==front B、(rear+1)%n==front
{//L是无表头结点的单链表
if (L && L—>next)
{Q=L;L=L－>next;P=L;
while (P－>next) P=P－>next;
P－>next=Q;Q－>next=NULL;
}
return ok;
}//A
本程序实现的功能就是：如果L的长度不小于2，则将首元结点删去并插入到末尾。
逻辑结构→存储结构。
8.数据处理任务也是逐步完成的，即转化过程是：处理要求→基本运算→ →算法。
9.从逻辑关系上讲数据结构主要分为两大类，它们是线性结构和非线性结构。
10.数据结构的基本任务是数据结构的设计和实现。
三、给出下列算法的时间复杂度。
1、Sum(int n)
{
int sum=0,i,j;
for (i=1;i<=n;i++)
11.对单链表表示法，以下说法错误的是C。
A、数据域用于存储线性表的一个数据元素
B、指针域（或链域）用于存放一个指向本结点所含数据元素的直接后继所在结点的指针
C、所有数据通过指针的链接而组织成单链表
D、NULL称为空指针，它不指向任何结点只起标志作用
12.若指定有n个元素的向量，则建立一个有序单向链表的时间复杂性的量级是C。
5.与数据元素本身的形式、内容、相对位置、个数无关的是数据的C。
A、存储结构B、存储实现
C、逻辑结构D、运算实现
6.通常要求同一逻辑结构中的所有数据元素具有相同的特性，这意味着B。
A、数据具有同一特点
B、不仅数据元素所包含的数据项的个数要相同，而且对应数据项的类型要一致
C、每个数据元素都一样
D、数据元素所包含的数据项的个数要相等
A、不确定B、n-i+1 C、i D、n-i
6、假定一个顺序循环队列的队首和队尾指针分别用front和rear表示，则判队空的条件是D。
A、front+1==rear B、front==rear+1
C、front==0 D、front==rear
7、假定一个顺序循环队列存储于数组A[n]中，其队首和队尾指针分别用front和rear表示，则判断队满的条件是B。
A、n－i B、n－i+1 C、n－i－1 D、i
10.线性表L=(a1，a2,……an)，下列说法正确的是D。
A、每个元素有有一个直接前驱和一个直接后继
B、线性表中至少有一个元素
C、表中诸元素的排列必须是由小到大或由大到小。