数据结构_模拟测验题1-4(带答案)

单元测验1

一．判断题 （ㄨ）（1）数据的逻辑结构和数据的存储结构是相同的。 （ㄨ）（2）程序和算法原则上没有区别，所以在讨论数据结构时可以通用。 （√）（3）从逻辑关系上讲，数据结构主要分为线性结构和非线性结构两类。 （√）（4）数据的存储结构是数据的逻辑结构的存储映像。 （ㄨ）（5）数据的逻辑结构是依赖于计算机的。 （√）（6）算法是对解题方法和步骤的描述。 二．填空题

1．数据有逻辑结构和存储结构两种结构。

2. 数据结构按逻辑结构可分为两大类，它们是线性结构和非线性结构。 3．树形结构和图形结构合称为非线性结构。 4．数据的存储结构又叫物理结构。

5．数据的存储结构形式包括：顺序存储和链式存储 6．线性结构中的元素之间存在一对一的关系。 7．树形结构中的元素之间存在一对多的关系， 8．图形结构的元素之间存在多对多的关系。

9．数据结构主要研究数据的逻辑结构、存储结构和 二者之间的相互运算 三个方面的内容。 10．一个算法的时间复杂度是 问题规模 的函数。

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）

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

for(j=0;j

s= s+B[i][j];

（2）for (i=0;i

for (j=0;i

c[i][j]=i+j;

单元测验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)

{ ; ; }

return n;

}

2、在单链表中查找内容为x的结点的算法：

Node * Lsearch ( linknode *head, char x)

{

P=head;

while (P->next!=NULL && P->data!= x )

; if ( )

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 )

; if (p= =NULL)

printf ( \不存在结点a，无法插入! \\n\ else {

s= ; s->data= ; _ ___; _ _ _ __; } }

单元测验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 ）

Head

C /\\ A B D

A．A B．B C．C D．D

单元测验4

一．判断题

（√）（1）队列是限制在两端进行操作的线性表。 （√）（2）判断顺序队列为空的标准是头指针和尾指针均指向同一个结点。 （×）（3）在循环链队列中无溢出现象。 （×）（4）栈和队列都是顺序存储的线性结构。 （×）（5）在队列中允许删除的一端称为队尾。 （×）（6）顺序队列和顺序循环队列的队满和队空的判断条件是一样的。

二．填空题

1．在队列中存取数据应遵从的原则是 先进先出 。 2．在队列中，允许插入的一端称为 队尾 。 3．对于队列，只能在 队首 删除元素。

4．解决顺序队列“假溢出”的方法是采用 循环队列 。

5．顺序队列的队头指针为front，队尾指针为rear，则队空的条件为 front == rear 。 6．在一个链队列中，若队头指针与队尾指针的值相同，则表示该队列为 空 。

7．区分循环队列的满与空，有三种方法，它们是_设计数器_____、_设标志位_____和__少用一个存储空间____。

8. 循环队列存储在数组A[m]中，则入队时的操作为rear=(rear+1) % m 9．设顺序循环队列的队头指示器front指向队头元素，队尾指示器rear指向队尾元素后的一个空闲元素，队列的最大空间为M，则用牺牲一个存储单元区分队列满与空时，队满标志为 front==(rear+1)% M 。

10. 已知链队列的头尾指针分别是Q->front和Q->rear，则将值x入队的操作序列是p = (LQNode *)malloc(sizeof(LQNode))； p->data=x; p->next=NULL； Q->rear->next=p；Q->rear = p；

三．选择题

1．同一队列内各元素的类型( A )。

A．必须一致 B．不能一致 C．不限制 D．可以不一致 2．队列是一个( D )线性表结构。

A．不加限制的 B．推广了的 C．非 D．加了限制的

3．四个元素按：A，B，C，D顺序连续进队Q，执行一次出队操作后，队头元素是（ C ）。

A． D B． C C． B D． A

4．若用一个大小为6的数组来实现循环队列，且当前front和rear的值分别为3和0，当从队列中删除一个元素，再加入两个元素后，front和rear的值分别为 ( B )。

A．5和1 B．4和2 C．2和4 D．1和5 5．以下属于队列的操作有( D )。

A．在队首插入元素 B．删除值最小的元素

C．按元素的大小排序 D．判断是否还有元素

6. 设栈S和队列Q的初始状态为空，元素e1，e2，e3，e4,e5和e6依次通过栈S，一个元素出栈后即进队列Q，若6个元素出队的序列是e2，e4，e3,e6,e5,e1则栈S的容量至少应该是( C )。

A． 6 B. 4 C. 3 D. 2

单元测验5

一、选择题

1. 若对n阶对称矩阵A (行下标和列下标范围均为1…n)，将其下三角形的元素(包括主对角线上所有元素)依次存放于一维数组B［0..(n(n+1))/2-1］中，则在B中确定aij（i

2. 假设以行序为主序存储二维数组A=array[1..100，1..100]，设每个数据元素占2个存储单元，基地址为10，则LOC[5，5]=（ B ）。

A. 808 B. 818 C. 1010 D. 1020

本文来源：https://www.bwwdw.com/article/m046.html