数据结构练习题

1.设n、m为正整数变量，下列程序段的时间复杂度为： i=1;j=0;

while(i+j<=n)

{if (i>j) j++; else i++;}

2.设n为正整数变量，下述程序段的时间复杂度为（ ） k=1;

while(k

k=k*3;

}

3.设n、m为正整数变量，下列程序段的时间复杂度为（ ） x=0;

for(i=1;i<=n;i++)

for(j=1;j<=m;j++) x++;

4.设n为正整数变量，下列程序段的时间复杂度为：

y=0；

while ( (y+1)*(y+1) >=n)

y++;

5.判断正误：数据元素是数据不可分割的最小单位。（错）

6.数据结构中评价算法的两个重要指标是算法的时间复杂度和空间复杂度。 7.四种基本的数据结构为集合线性结构树形结构、图状结构或网状结构 8.算法的五个特性是有穷性确定性、可行性、 输入和输出。

9.数据结构在计算机中的表示称为数据的物理结构，又称存储结构

10 .数据结构是一门研究非数值计算的程序设计问题中计算机的操作对象以及它们之间的关系和操作的学科

第二章

1 (1/1 分)

顺序存储时，要求内存可用存储单元的地址（ ）

一定连续 一定连续 - 正确 一定不连续 不一定连续 部分连续，部分不连续 2 (1/1 分)

下列说法中正确的是（ ）

顺序存储方式只能用于线性结构，不能用于非线性结构 基于某种逻辑结构之上的运算，其实现是唯一的

算法可以用不同的语言描述，则算法实际上就是程序了

数据结构的三大组成部分是逻辑结构、存储结构和运算 - 正确 3 (1/1 分)

线性表（a1,a2,?,an）以顺序方式存储时，访问第i（1≤i≤n）个位置元素的时间复杂度为

（ ）。

4 (1/1 分)

在一个以L为头的单循环链表中，p指针指向链尾的条件是（ ）。

p->next==L - 正确 B p->next==NULL C p->next->next==L D p->data==-1 5 (1/1 分)

链式存储时，要求存储单元的地址（ ）。

一定连续 一定不连续 不一定连续 - 正确 部分连续,部分不连续 6 (1/1 分)

在一个单链表中，已知q所指结点是p所指结点的前驱结点，若在q和p之间插入s结点，

则执行( )

7 (1/1 分)

若某线性表中最常用的操作是在最后一个元素之后插入一个元素和删除第一个元素，则采用

（ ）存储方式最节省时间。

8 (1/1 分)

设指针变量p指向单链表中结点A(结点A不是尾结点)，若删除单链表中结点A，则需要修改指针的操作序列为（ ）。

9 (1/1 分)

在一个以L为头的非循环单链表中，p指针指向链尾的条件是（ ）。

p->next==L p->next==NULL p->next==NULL - 正确 p->next->next==L p->data==-1 10 (1/1 分)

链表不具有的特点是（ ）。

插入、删除不需要移动元素 可随机访问任一元素 - 正确 不必事先估计存储空间

所需空间与线性长度成正比 11 (1/1 分)

若线性表最常用的操作是存取任一指定序号的元素和在最后进行插入和删除运算，则利用（ ）存储方式最节省时间。

顺序表 - 正确 双链表 带头结点的双循环链表 单循环链表 12 (1/1 分)

不带头结点的单链表为空的判定条件是 （ ）

head==NULL - 正确 head->next==NULL head->next==head head!=NULL 13 (1/1 分)

线性表（a1,a2,?,an）以链接方式存储时，访问第i（1≤i≤n）个位置元素的时间复杂度为

（ ）。

14 (1/1 分)

判断正误：线性表中的任一元素都有唯一的前驱和后继。（错）

第三章

1 (1/1 分)

输入序列为abc，若输出序列为bca，经过的栈操作为（ ）。

push,pop,push,pop,push,pop push,push,push,pop,pop,pop push,push,pop,push,pop,pop push,push,pop,push,pop,pop - 正确 push,pop,push,push,pop,pop

2 (1/1 分)

一个栈的入栈序列为a，b，c，d，e，则出栈的不可能序列为（ ）。

e d c b a d e c b a d c e a b d - 正确 a b c d e 3 (1/1 分)

设有一顺序栈S，元素s1、s2、s3、s4、s5、s6依次入栈，如果6个元素出栈的顺序是s2、s4、s3、s6、s5、s1，则栈的容量至少应该是（ ）

2 3 - 正确 5 6

4 (1/1 分)

一个栈的输入序列为123?n，若输出序列的第一个元素是n，输出第i（1<=i<=n）个元素是（ ）。

不确定 n-i+1 n-i+1 - 正确 i n-i

5 (1/1 分)

若一个栈的输入序列为1,2,3,?,n，输出序列的第一个元素是i，则第j个输出元素是（ ）。

i-j-1 i-j j-i+1 不确定的 不确定的 - 正确

6 (1/1 分)

若进队列的序列为1,2,3,4 则（ ）是一个出队列序列。

3,2,1,4 3,2,4,1 4,2,3,1 1,2,3,4 1,2,3,4 - 正确 7 (1/1 分)

栈和队列的共同特点是（ ）。

只允许在端点处插入和删除元素 只允许在端点处插入和删除元素 - 正确 都是先进后出 都是先进先出 没有共同点

8 (1/1 分)

循环队列Q的最大容量为M,循环队列队空的条件是（ ）

Q .front ==Q.rear Q .front ==Q.rear - 正确 Q.front！=Q.rear Q.front= =(Q.rear+1)%M Q.front! =(Q.rear+1)%M

9 (1/1 分)

循环队列Q的最大容量为M, 循环队列队满的条件是 （ ）

Q .front ==Q.rear Q.front！=Q.rear Q.front= =(Q.rear+1)%M Q.front= =(Q.rear+1)%M - 正确 Q.front! =(Q.rear+1)%M

10 (1/1 分)

栈式结构的铁路调度站,入栈顺序为1,2,3的三列车,并在任何时候允许出栈,则出栈顺序有（ ）种。

2 3 5 5 - 正确 6 11 (1/1 分)

若用一个大小为6的数组来实现循环队列，且当前rear和front的值分别为0和2。当从队列中删除3个元素，再插入上2个元素后，rear和front的值分别为（）。

5和2 2和5 2和5 - 正确 3和2 2和3

第四章

1 (1/1 分)

下面关于串的叙述中，哪一个是不正确的？（ ）