2013数据结构 概述 线性表 栈与队列 习题及答案

第一章概论

一、填空题

1、数据的存储结构可用四种基本的存储方法表示，分别是顺序、链式、索引和散列。

2、一个算法具有5个特性:有穷性、确定性、可行性，有零个或多个输入、有一个或多

个输出。

3、数据结构包括数据的逻辑结构、存储结构和运算（或基本操作）这三个方面的内容。

4、数据结构中评价算法的两个重要指标是时间效率和空间效率。

5、一个数据结构在计算机中的表示称为存储结构。6、从逻辑上可以把数据结构分为线性结构、非线性结构两大类

7、数据逻辑结构除了集合以外，还包括线性结构、树形结构和图形结构。

8、数据的存储结构形式包括顺序存储、链式存储、索引存储和散列存储。9、数据结构主要研究数据的逻辑结构、存储结构和算法（或运算）3个方面的内容。

10、算法效率的度量可以分为事先估算和事后统计法。

二、单项选择题

1、数据结构中，与所使用的计算机无关的是数据的是（C）；

A、存储结构B、物理结构C、逻辑结构D、物理和逻辑结构

2、算法分析的目的是（C）

A)找出数据结构的合理性B)研究算法中的输入和输出的关系

C)分析算法的效率以求改进D)分析算法的易懂性和文档性

3、计算机算法指的是（C）

A)计算方法B)排序方法C)解决问题的有限运算序列D)调度方法

4、计算机算法必须具备输入、输出和（B）等5个特性。

A)可行性、可移植性和可扩充性B)可行性、确定性和有穷性

C)确定性、有穷性和稳定性D)易读性、稳定性和安全性

5、从逻辑上可以把数据结构分为（C）两大类。

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

C）线性结构、非线性结构D）初等结构、构造型结构

6、下列数据中，（C）是非线性数据结构。

A．栈B.队列C.完全二叉树D.堆

7、算法分析的两个主要方面是（A）。

A)空间复杂性和时间复杂性B)正确性和简明性

C)可读性和文档性D)数据复杂性和程序复杂性

8、在下面程序段的时间复杂度（D）i=1;

while(i<=n)

i=i*3;

A．O(3n)B．O(n)C．O(n3)D．O(log3n)

9、在下面的程序段中，对x的赋值语句的频度为（C）

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

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

x=x+1;

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

10、下面关于算法说法错误的是（D）

A．算法最终必须由计算机程序实现

B.为解决某问题的算法同为该问题编写的程序含义是相同的

C.算法的可行性是指指令不能有二义性

D.以上几个都是错误的

11、数据结构通常是研究数据的（A）及它们之间的相互关系。

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

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

12、数据在计算机中存储器内表示时，物理地址和逻辑地址相同并且是连续的，称之为（C）。

A．存储结构B．逻辑结构C．顺序存储结构D．链式存储结构

13、非线性结构中的每个结点（D）。

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

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

14、链式存储结构所占存储空间（A）。

A．分两部分，一部分存储结点的值，另一部分存放表示结点间关系的指针

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

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

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

15、数据的基本单位是（B）。

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

16、每个结点只含有一个数据元素，所有存储结点相继存放在一个连续的存储空间里。这种

存储结构称为（A）结构。

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

17、每一个存储结点不仅含有一个数据元素，还包含一组指针，该存储方式是（B）存储方式。A．顺序B．链式C．索引D．散列

18、算法分析的两个主要方面是（A）。

A．空间复杂性和时间复杂性B．正确性和简明性

C．可读性和文档性D．数据复杂性和程序复杂性

19、算法能正确的实现预定功能的特性称为算法的（A）。

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

20、算法在发生非法操作时可以作出相应处理的特性称为算法的（C）。

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

21、计算机算法必须具备输入、输出和（C）。

A．计算方法B．排序方法

C．解决问题的有限运算步骤D．程序设计方法

三、判断题

1.数据的逻辑结构说明数据元素之间的顺序关系,它依赖于计算机的储存结构.(×)

2.数据的逻辑结构是指数据的各数据项之间的逻辑关系；(×)

3.数据的物理结构是指数据在计算机内的实际存储形式。(√)

4．算法的优劣与算法描述语言无关，但与所用计算机有关。(×)

5．健壮的算法不会因非法的输入数据而出现莫名其妙的状态。(√)

6．算法可以用不同的语言描述，如果用C语言或PASCAL语言等高级语言来描述，则算法实

际上就是程序了。(×)

四、简答题

1、当为解决某一问题而选择数据结构时，应从哪些方面考虑？

答：通常考虑算法所需要的存储空间量和算法所需要的时间量。后者又涉及到四方面：程序

运行时所需输入的数据总量，对源程序进行编译所需时间，计算机执行每条指令所需时间和

程序中指令重复执行的次数。

第2章线性表

一、填空

1．当线性表的元素总数基本稳定，且很少进行插入和删除操作，但要求以最快的速度存取线性表中的元素时，应采用顺序存储结构。

2．顺序存储的线性表存储特点是用物理位置的相邻表示元素之间的关系的，在顺序表

中插入或删除一个元素，移动的元素个数与表长和该元素在表中的位置有关。如果线性表

L=（a1,a2,…,an）用数组表示，假定删除表中任一元素的概率相同，则删除一个元素平均需要移动元素的个数是（n-1）/2_；第i个元素（1<=i<=n）之前插入一个元素时，需向后

移动n-i+1_个元素。如果要在第1个元素前插入一个元素，要后移n个元素；删除第i个

元素(1≤i≤n)时，需向前移动n-i个元素。

3．设单链表的结点结构为(data,next)，next为指针域，已知指针px指向单链表中data为

x的结点，指针py指向data为y的新结点,若将结点y插入结点x之后，则需要执行以下

语句:__py->next=px->next;_px->next=py

4．在顺序表中访问任意一结点的时间复杂度均为O(1)，因此，顺序表也称为随机存取的

数据结构。5、链接存储的特点是利用__指针来表示数据元素之间的逻辑关系。在单链表中，除了首

元结点外，任一结点的存储位置由其直接前驱结点的链域的值指示，查找结点都必须从头

结点开始，因此，链表也称为顺序存取的数据结构。在n个结点的单链表中要删除已知结点*p，需找到它的前驱结点的地址，其时间复杂度为O（n），在给定值为x的结点后插入

一个新结点的时间复杂度为O(n)_。

7．已知指针p指向单链表L中的某结点，则删除其后继结点的语句是：u=p->next;为空表

的条件是：_L->next==L&&L->prior==Lp->next=u->next;

8．带头结点的双循环链表L中只有一个元素结点的条件是：L->next->next==L；

二、判断正误（在正确的说法后面打勾，反之打叉）

（×）1.线性表的特点是每个元素都有一个前驱和一个后继。

（×）2.链表的物理存储结构具有同链表一样的顺序。

（×）3.链表的删除算法很简单，因为当删除链中某个结点后，计算机会自动地将后续

的各个单元向前移动。

（×）4.取线性表的第i个元素的时间同i的大小有关.

（×）5.顺序表结构适宜于进行顺序存取，而链表适宜于进行随机存取。

（×）6.顺序存储方式的优点是存储密度大，且插入、删除运算效率高。

(√)7．链表是采用链式存储结构的线性表,进行插入、删除操作时，在链表中比在顺

序存储结构中效率高。

（×）8.线性表在顺序存储时，逻辑上相邻的元素未必在存储的物理位置次序上相邻。

（×）9.顺序存储方式只能用于存储线性结构。

（×）10.线性表的逻辑顺序与存储顺序总是一致的。

(×)11.链表中的头结点仅起到标识的作用。

(√)12.顺序存储结构的主要缺点是不利于插入或删除操作。

(√)13．线性表采用链表存储时，结点和结点内部的存储空间可以是不连续的。

(×)14．顺序存储方式插入和删除时效率太低，因此它不如链式存储方式好。

(×)15.对任何数据结构链式存储结构一定优于顺序存储结构。三、单项选择题

1．数据在计算机存储器内表示时，物理地址与逻辑地址相同并且是连续的，称之为（C）

（A）存储结构（B）逻辑结构（C）顺序存储结构（D）链式存储结构

2．一个向量第一个元素的存储地址是100，每个元素的长度为2，则第5个元素的地址是（B）

（A）110（B）108（C）100（D）120

3.在n个结点的顺序表中，算法的时间复杂度是O（1）的操作是（A）

（A）访问第i个结点（1≤i≤n）和求第i个结点的直接前驱（2≤i≤n）

（B）在第i个结点后插入一个新结点（1≤i≤n）

（C）删除第i个结点（1≤i≤n）

（D）将n个结点从小到大排序

4.向一个有127个元素的顺序表中插入一个新元素并保持原来顺序不变，平均要移动（B）

个元素

（A）8（B）63.5（C）63（D）7

5.线性表（a1,a2,…,an）以链接方式存储时，访问第i位置元素的时间复杂性为（C）

A．O（i）B．O（1）C．O（n）D．O（i-1）

6.链表是一种采用（B）存储结构存储的线性表；

（A）顺序（B）链式（C）星式（D）网状

7.线性表若采用链式存储结构时，要求内存中可用存储单元的地址（D）

（A）必须是连续的（B）部分地址必须是连续的

（C）一定是不连续的（D）连续或不连续都可以

8．线性表Ｌ在（B）情况下适用于使用链式结构实现。

（Ａ）需经常修改Ｌ中的结点值（Ｂ）需不断对Ｌ进行删除插入

（Ｃ）Ｌ中含有大量的结点（Ｄ）Ｌ中结点结构复杂

9．单链表的存储密度（C）

（Ａ）大于1；（Ｂ）等于1；（Ｃ）小于1；（Ｄ）不能确定

10．对于一个头指针为head的带头结点的单链表，判定该表为空表的条件是（B）

A．head==NULLB．head→next==NULLC．head→ext==headD．head!=NULL

11．下面关于线性表的叙述中，错误的是哪一个？（B）

A．线性表采用顺序存储，必须占用一片连续的存储单元。

B．线性表采用顺序存储，便于进行插入和删除操作。

C．线性表采用链接存储，不必占用一片连续的存储单元。

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

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