单元测验1
一．判断题
（ㄨ）（1）数据的逻辑结构和数据的存储结构是相同的。
（ㄨ）（2）程序和算法原则上没有区别，所以在讨论数据结构时可以通用。
（√）（3）从逻辑关系上讲，数据结构主要分为线性结构和非线性结构两类。
（√）（4）数据的存储结构是数据的逻辑结构的存储映像。
（ㄨ）（5）数据的逻辑结构是依赖于计算机的。
（√）（6）算法是对解题方法和步骤的描述。
二．填空题
1．数据有逻辑结构和存储结构两种结构。
2.数据结构按逻辑结构可分为两大类，它们是线性结构和非线性结构。
3．树形结构和图形结构合称为非线性结构。
4．数据的存储结构又叫物理结构。
5．数据的存储结构形式包括：顺序存储和链式存储
6．线性结构中的元素之间存在一对一的关系。
7．树形结构中的元素之间存在一对多的关系。
8．图形结构的元素之间存在多对多的关系。
9．数据结构主要研究数据的逻辑结构、存储结构和二者之间的相互运算三个方面的内容。
10．一个算法的时间复杂度是问题规模的函数。
时间复杂度：Ο(1)＜Ο(log2n)＜Ο(n)＜Ο(nlog2n)＜Ο(n2)＜Ο(n3)＜…＜Ο(2n)＜Ο(n!)
11．若一个算法中的语句频度之和为T（n）=6n+3nlog2n，则算法的时间复杂度为O（nlog2n）。
12．若一个算法中的语句频度之和为T（n）=3n+nlog2n+n2，则算法的时间复杂度为O（n2）。
三．选择题
1．数据结构通常是研究数据的（ D ）及它们之间的相互联系。
A.联系与逻辑B.存储和抽象C.联系和抽象 D.存储结构和逻辑结构
2．数据在计算机内存储时，数据元素在存储器内相对位置可以表示元素之间的逻辑关系，称为（D）。
A.存储结构B.逻辑结构C.链式存储结构D.顺序存储结构
3．链接存储的存储结构所占存储空间（A）。
A．分两部分，一部分存放结点的值，另一部分存放表示结点间关系的指针
B．只有一部分，存放结点值
C．只有一部分，存储表示结点间关系的指针
D．分两部分，一部分存放结点值，另一部分存放结点所占单元数
4．在数据结构中，与所使用的计算机无关的是（B）
A.物理结构B.逻辑结构(不用进行计算)C.存储结构D.逻辑和存储结构
5．算法能正确的实现预定功能的特性称为（A）
5．算法能正确的实现预定功能的特性称为（A）
A.正确性B.易读性C.健壮性D.高效性
6．算法在发生非法操作时可以作出处理的特性称为（B）
A.正确性B.健壮性C.易读性D.高效性
7．下列时间复杂度中最坏的是（A）
A.O（n2）B.O（log2n）C.O（n）D.O（1）
8.算法分析的两个主要方面是（C）。
A.可读性和文档性B.正确性和简明性C.空间复杂性和时间复杂性D.数据复杂性和程序复杂性
四．分析下面各程序段的时间复杂度
（1）s=0;
for(i=0;i<n;i++)O（n）
for(j=0;j<n;j++)O（n2）
s= s+B[i][j];
（2）for (i=0;i<n;i++) O（n）
for (j=0;i<n;j++)
c[i][j]=i+j; O（n2）
单元测验2
一．判断题
（√）（1）在线性表的链式存取结构中，逻辑上相邻的两个元素在物理位置上并不一定紧邻。
（×）（3）顺序存储方式的优点是存储密度大，插入、删除效率高→链式存储。
（×）（4）链表的删除算法简单，因为当删除链中某个结点后，计算机会自动地将后续的各个单元向前移动。
（√）（5）线性表采用顺序存储，必须占用一片连续的存储单元。
（×）（6）顺序表结构适宜于进行顺序存取，而链表适宜于进行随机存取。
二．填空题
1．顺序表相对于链表的优点是： 节省存储 和随机存取。
2．链表相对于顺序表的优点有插入、删除方便；缺点是存储密度 小 。
3．在一个长度为n的顺序表中删除第i个元素，要移动 n-i 个元素。
4．当线性表的元素总数基本稳定，且很少进行插入和删除操作，但要求以最快速度存取线性表中的元素时，应采用 顺序 存储结构
5．在线性表的链接存储中，元素之间的逻辑关系是通过 指针 决定的。
6．对一个需要经常进行插入和删除操作的线性表，采用 链接 存储结构为宜。
三．选择题
1．单链表的存储密度（ C ）。
存储密度 = （结点数据本身所占的存储量）/（结点结构所占的存储总量）
A．大于1 B．等于1 C．小于1 D．不能确定
2．已知一个顺序存储的线性表，设每个结点需占m个存储单元，若第一个结点的地址为B，则第i个结点的地址为（ A ）。
A． B+(i-1)*m B．B+i*m C． B-i*m D． B+(i+1)*m
3．在有n个结点的顺序表上做插入、删除结点运算的时间复杂度为（ B ）。
A．O（1） B．O（n） C．O（n2） D．O（log2n）
4．下面关于线性表的叙述中，错误的是（ B ）关系。
A．顺序表必须占一片地址连续的存储单元 B．链表可以随机存取任一元素
C．链表不必占用一片地址连续的存储单元 D．顺序表可以随机存取任一元素
5．链表不具备的特点是（ C）。
A ．插入删除时不需移动元素 B．不必事先估计存储空间
C．随机访问 D．所需空间与线性表成正比
6．用链式存储结构存储的线性表，其优点是（ B ）。
A．便于随机存取 B．便于插入和删除
C． 花费的存储空间比顺序表少 D．数据元素的物理顺序与逻辑顺序相同
四．程序填空
1、求带头结点的单链表长的算法：
int f ( linknode *head, int n)
{
P=head; n=0;
While (P->next!=NULL)
{
P = P->next;
++n;
}
return n;
}
2、在单链表中查内容为x的结点的算法：
Node * Lsearch ( linknode *head, char x)
{
P=head;
while (P->next!=NULL && P->data!= x )
P = P->next;
if (P->next ==NULL )
printf ( " 没有到! \n");
else
return P; /*到，返回结点指针*/
}
3、在带头结点head的单链表的结点a之后插入新元素x：
struct Node
{
Char data;
Node *next;
};
void ListInsert (Node *head, Char x)
{
node *p,*s;
p=head->next;
while (p!=NULL) && ( p->data!=a )
P = P->next;
if (p==NULL)
printf ( " 不存在结点a，无法插入! \n");
else
{
s = (node*)malloc(sizeof(node));; //让指针s指向x的地址
s->data=x;
s->next = p->next;
p->next = s;
}
}
单元测验3
一．判断题
（√）（1）栈是运算受限制的线性表。
（√）（2）在栈空的情况下，不能作出栈操作，否则产生下溢出。
（ㄨ）（3）栈一定是顺序存储的线性结构。
（√）（4）栈的特点是“后进先出”。
（√）（5）链栈与顺序栈相比，其特点之一是通常不会出现栈满的情况。
（ㄨ）（6）一个栈的输入序列为：A，B，C，D，可以得到输出序列：C，A，B，D。
二．填空题
1．在栈结构中，允许插入、删除的一端称为 栈顶 。
2．在一个链栈中，若栈顶指针等于NULL，则表示 栈空 。
3．已知顺序栈S，在对S进行出栈操作之前首先要判断 栈是否空 。
4．从一个栈删除元素时，首先取出栈顶元素，然后再移动 栈顶指针 。
5. 顺序栈用data[n]存储数据，栈顶指针是top, 则值为x的元素入栈的操作是_ data[top]=x；top++；
三．选择题
1．设有编号为1，2，3，4的四辆列车，顺序进入一个栈式结构的站台，下列不可能的出站顺序为 ( B )
A．1234 B．1423 C．1324 D．1243
2．顺序栈存储空间的实现使用（ B ）存储栈元素。
A．链表 B．数组 C．循环链表 D．变量
3．如果以链表作为栈的存储结构，则出栈操作时（ B ）
A．必须判别栈是否满 B．必须判别栈是否空
C．必须判别栈元素类型 D．队栈可不做任何判别
4．一个栈的入栈次序ABCDE，则栈的不可能的输出序列是 ( D )。
A．EDCBA B．DECBA C．ABCDE D．DCEAB
5、栈与一般线性表的区别在于 ( C )。
A．数据元素的类型不同 B．数据元素的个数不同
C．操作是否受限制 D．逻辑结构不同
6．带头结点的链栈LS的示意图如下，栈顶元素是（ A ）
A．A B．B C．C D．D
单元测验4
一．判断题
（√）（1）队列是限制在两端进行操作的线性表。
（√）（2）判断顺序队列为空的标准是头指针和尾指针均指向同一个结点。
（×）（3）在循环链队列中无溢出现象。
（×）（4）栈和队列都是顺序存储的线性结构。
完全二叉树算法（×）（5）在队列中允许删除的一端称为队尾。
（×）（6）顺序队列和顺序循环队列的队满和队空的判断条件是一样的。
发表评论