数据结构与算法习题

数据结构与算法习题

习题1

⼀、选择题1．数据结构通常是研究数据的（）及它们之间的相互联系。

A．存储结构和逻辑结构B．存储和抽象

C．联系和抽象D．联系与逻辑

2．从逻辑上可以把数据结构分为（）两⼤类。

A．动态结构、静态结构B．顺序结构、链式结构

C．线性结构、⾮线性结构D．初等结构、构造型结构

3．数据处理的基本单位是（）。

A．数据元素B．数据项

C．数据类型D．数据变量

4．数据结构中线性结构中元素对应关系为（）。

A．⼀对⼀B．⼀对多

C．多对多D．⽆关系

5．数据结构中树形结构中元素对应关系为（）。

A．⼀对⼀B．⼀对多

C．多对多D．⽆关系

6．数据结构中图形结构中元素对应关系为（）。

A．⼀对⼀B．⼀对多

C．多对多D．⽆关系

7．数据在计算机存储器内表⽰时，物理地址和逻辑地址相同并且是连续的，称为（）。

A．存储结构B．逻辑结构

C．顺序存储结构D．链式存储结构

8．⾮线性结构中的每个结点（）。

A．⽆直接前趋结点B．⽆直接后继结点

C．只有⼀个直接前趋结点和⼀个直接后继结点

D．可能有多个直接前趋结点和多个直接后继结点

9．链式存储的存储结构所占存储空间（）。

A．分两部分，⼀部分存放结点的值，另⼀部分存放表⽰结点间关系的指针

B．只有⼀部分，存放结点的值

C．只有⼀部分，存储表⽰结点间关系的指针

D．分两部分，⼀部分存放结点的值，另⼀部分存放结点所占单元素

10．算法分析的两个主要⽅⾯是（）。

A．正确性和简单性B．可读性和⽂档性C．数据复杂性和程序复杂性D．时间复杂度和空间复杂度

11．算法的计算量⼤⼩称为算法的（）。

A．现实性B．难度C．时间复杂性D．效率

12．数据的基本单位是（）。

A．数据结构B．数据元素C．数据项D．⽂件

13．每个结点只含有⼀个数据元素，所有存储结点相继存放在⼀个连续的存储区⾥，这种存储结构称为（）结构。

A．顺序存储B．链式存储

C．索引存储D．散列存储

14．每⼀个存储结点不仅含有⼀个数据元素，还包含⼀组指针，该存储⽅式是（）存储⽅式。

A．顺序B．链式C．索引D．散列

15．以下任何两个结点之间都没有逻辑关系的是（）。

A．图形结构B．线性结构C．树形结构D．集合

16．在数据结构中，与所使⽤的计算机⽆关的是（）。

A．物理结构B．存储结构

C．逻辑结构D．逻辑和存储结构

17．下列四种基本逻辑结构中，数据元素之间关系最弱的是（）。

A．集合B．线性结构C．树形结构D．图形结构

18．与数据元素本⾝的形式、内容、相对位置、个数⽆关的是数据的（）。

A．逻辑结构B．存储结构C．逻辑实现D．存储实现

19．每⼀个存储结点只含有⼀个数据元素，存储结点存放在连续的存储空间，另外有⼀组指明结点存储位置的表，该存储⽅式是（）存储⽅式。A．顺序B．链式C．索引D．散列

20．算法能正确的实现预定功能的特性称为算法的（）。

A．正确性B．易读性C．健壮性D．⾼效性

21．算法在发⽣⾮法操作时可以做出处理的特性称为算法的（）。

A．正确性B．易读性C．健壮性D．⾼效性

22．下列时间复杂度中最坏的是（）。

A．O(1) B．O(n) C．O(log2n) D．O(n2)

23．在下⾯的程序段中，对x的赋值语句的频度为（）。

for( i=1;i

for(j=1;j

x++;

A．O(2n) B．O(n) C．O(n2) D．O(log2n)

⼆、填空题1．常见的数据结构有集合、线性结构、结构、结构。

2．算法的5个重要特性是有穷性、、可⾏性、输⼊、。3．评价算法的优劣通常主要考虑算法的和这两⽅⾯。

4．线性结构中元素之间存在关系，树形结构中元素之间存在关系，图形结构中元素之间存在关系。

5．数据的存储结构⼜叫。

6．数据结构被定义为(D，R)，其中D是数据的有限集合，R是D上的的有限集合。

7．算法的空间复杂度是指该算法所耗费的，它是该算法求解问题规模n的函数。

8．算法是⼀个的集合，算法效率的度量可以分为和。

9．若⼀个算法中的语句频度之和为T(n)=7n+4n2，则算法的时间复杂度为。

10．设有⼀组数据元素需存储，为了⽅便查找某元素，数据宜采⽤存储结构；为了⽅便插⼊与删除某元素，数据宜采⽤存储结构。

三、判断题1．数据的逻辑结构与数据元素本⾝的内容和形式⽆关。（）

2．⼀个数据结构是由⼀个逻辑结构和这个逻辑结构上⼀个基本运算集构成的整体。（）

3．数据元素是数据的最⼩单位。（）

4．数据的逻辑结构和数据的存储结构是相同的。（）

5．程序和算法原则上没有区别，所以在讨论数据结构时可以通⽤。（）

6．从逻辑关系上讲，数据结构主要分为线性结构和⾮线性结构两类。（）

7．数据的存储结构是数据的逻辑结构的存储映像。（）

习题2

⼀、选择题1．下⾯关于线性表的叙述中，错误的是（）。

A．线性表采⽤顺序存储，必须占⽤⼀⽚连续的存储单元。

B．线性表采⽤顺序存储，便于进⾏插⼊和删除操作。

C．线性表采⽤链接存储，不必占⽤⼀⽚连续的存储单元。

D．线性表采⽤链接存储，便于插⼊和删除操作。

2．在有n个结点的顺序表上做插⼊、删除结点运算的时间复杂度为（）。

A．O(1)B．O(n)

C．O(n2)D．O(log2n)

3．两个指针P和Q，分别指向单链表的两个元素，P所指元素是Q所指元素前驱的条件是（）。

A．P->next == Q->next B．P->next == Q

C．Q->next == P D．P == Q

4．在单链表中，增加头结点的⽬的是（）。

A．使单链表⾄少有⼀个结点B．标志表中⾸结点的位置

C．⽅便运算的实现D．说明该单链表是线性表的链式存储结构

5．在顺序表中，只要知道（），就可以求出任意⼀个结点的存储地址。

A．基地址B．结点⼤⼩

C．向量⼤⼩D．基地址和结点⼤⼩6．链表不具备的特点是（）。

A．随机访问B．不必事先估计存储空间

C．插⼊删除时不需移动元素

D．所需空间与线性表成正⽐

7．在（）的运算中，使⽤顺序表⽐链表好。

A．插⼊B．根据序号查找

C．删除D．根据元素查找

8．在单链表指针为p的结点之后插⼊指针为s的结点，正确的操作是（）。

A．p->next=s;s->next=p->next;

B．s->next=p->next;p->next=s;

C．p->next=s;p->next=s->next;

D．p->next=s->next;p->next=s;

9．⽤链表表⽰线性表的优点是（）。

A．便于进⾏插⼊和删除操作B．便于随机存取

C．占⽤的存储空间较顺序表少D．元素的物理顺序与与逻辑顺序⼀致

10．在⼀个长度为n的顺序表中，若要删除第i（1≤i≤n）个元素，则需向前移动（）个元素。

A．n-i+1 B．n-i-1 C．n-i D．i

11．在⼀个长度为n的顺序表中，若要在第i（1≤i≤n）个元素前插⼊⼀个元素时，则需向后移动（）个元素。A．n-i+1 B．n-i-1 C．n-i D．i

12．设p为指向单循环链表上某结点的指针，则*p的直接前驱（）。

A．找不到B．查找时间复杂度为O(1)

C．查找时间复杂度为O(n)D．查找结点的次数约为n

13．等概率情况下，在有n个结点的顺序表上做插⼊结点运算，需平均移动结点的数⽬为（）。

A．n B．(n-1)/2 C．n/2 D．(n+1)/2

14．以下链表结构中，从当前结点出发能够访问到任意结点的是（）。

A．单向链表和双向链表

B．循环链表和单向链表

C．循环链表和双向链表

D．单向链表、双向链表和循环链表

15．对具有n个结点的线性表进⾏插⼊或删除操作，所需的算法时间复杂度为（）。

A．O(n2) B．O(nlog2n)

C．O(log2n) D．O(n)

⼆、填空题1．线性表L=(a1,a2,…,a n)采⽤顺序存储，假定删除表中任意元素的概率相同，则删除⼀个元素平均需要移动元素的个数是。

2．顺序表相对于链表的优点是：和随机存取；链表相对于顺序表的优点是：⽅便。

3．在单链表中要在已知结点*P之前插⼊⼀个新结点，需找到*P的直接前趋结点的地址，其查找的时间复杂度为。4．在长度为n的顺序表中，如果要在第i个元素前插⼊⼀个元素，要后移个元素。

5．链表相对于顺序表的优点是插⼊、删除⽅便；缺点是存储密度。

6．链式存储的特点是利⽤来表⽰数据元素之间的逻辑关系。

7．在双向链表中，每个结点有两个指针域，⼀个指向其结点，另⼀个指向其结点。

8．在⼀个双链表中，设指针p是指向该表中待删除的结点，则需要执⾏的操作为：。

9．若对⼀个线性表经常进⾏查找操作，⽽很少进⾏插⼊和删除操作时，则采⽤存储结构为宜，相反，若经常进⾏的是插⼊和删除操作时，则采⽤存储结构为宜。

三、判断题1．线性表的链式存储结构优于顺序存储结构。（）

2．链表的每个结点都恰好包含⼀个指针域。（）

3．在线性表的链式存储结构中，逻辑上相邻的两个元素在物理位置上并不⼀定紧邻。（）

4．顺序存储⽅式的优点是存储密度⼤，插⼊、删除效率⾼。（）

5．线性链表的删除算法简单，因为当删除链中某个结点后，计算机会⾃动地将后续的各个单元向前移动。

6．顺序表的每个结点只能是⼀个简单类型，⽽链表的每个结点可以是⼀个复杂类型。（）

7．线性表链式存储的特点是可以⽤⼀组任意的存储单元存储表中的数据元素。（）

8．线性表采⽤顺序存储，必须占⽤⼀⽚连续的存储单元。（）

9．顺序表结构适宜于进⾏顺序存取，⽽链表适宜于进⾏随机存取。（）

10．插⼊和删除操作是数据结构中最基本的两种操作，所以这两种操作在数组中也经常使⽤。（）

习题3

⼀、选择题1．对于栈操作数据的原则是（）。

A．先进先出B．后进先出

C．后进后出D．不分顺序

2．有6个元素按6,5,4,3,2,1 的顺序进栈，问下列（）不是合法的出栈序列？

A．5 4 3 6 1 2B．4 5 3 1 2 6

C．3 4 6 5 2 1D．2 3 4 1 5 6

3．插⼊和删除只能在⼀端进⾏的线性表，称为（）。

A．队列B．循环队列C．栈D．循环栈

4．输⼊序列为ABC，可以变为CBA时，经过的栈操作为（）。

A．push,pop,push,pop,push,pop B．push,push,push,pop,pop,pop

C．push,push,pop,pop,push,pop D．push,pop,push,push,pop,pop

5．设有编号为1,2,3,4的四辆列车，顺序进⼊⼀个栈结构的站台，下列不可能的出站顺序为（）。

A．1234 B．1243

C．1324 D．1423

6．如果以链表作为栈的存储结构，则出栈操作时（）。

A．必须判别栈是否满B．必须判别栈是否空