数据结构与算法习题库考前必备.docx

第一章 绪论

一．选择题

数据结构被形式地定义为（K，R），其中K是①_B_的有限集合，R是K上的②_D_的有限集合。

①A．算法

B．数据元素

C．数据操作

D．逻辑结构

②A．操作

B．映象

C．存储

D．关系

算法分析的目的是①C，算法分析的两个主要方面是②A。

①A．找出数据结构的合理性B．研究算法中的输入和输出的关系C．分析算法的效率以求改进D．分析算法的易懂性和文档性

②A．空间复杂性和时间复杂性B．正确性和简明性C．可读性和文档性D．数据复杂性和程序复杂性

在计算机存储器内表示时，物理地址和逻辑地址相同并且是连续的，称之为

(B)

逻辑结构 B．顺序存储结构C．链表存储结构 D．以上都不对

数据结构中，在逻辑上可以把数据结构分成：( C）。

动态结构和静态结构 B．紧凑结构和非紧凑结构

C．线性结构和非线性结构 D．内部结构和外部结构5．以下属于顺序存储结构优点的是（A）。

A．存储密度大 B．插入运算方便

C．删除运算方便 D．可方便地用于各种逻辑结构的存储表示6．数据结构研究的内容是（D）。

A．数据的逻辑结构 B．数据的存储结构C．建立在相应逻辑结构和存储结构上的算法 D．包括以上三个方面

链式存储的存储结构所占存储空间（A ）。A．分两部分，一部分存放结点值，另一部分存放表示结点间关系的指针B．只有一部分，存放结点值C．只有一部分，存储表示结点间关系的指针D．分两部分，一部分存放结点值，另一部分存放结点所占单元数

一个正确的算法应该具有5个特性，除输入、输出特性外，另外3个特性是（A）。

A．确定性、可行性、有穷性 B．易读性、确定性、有效性

C．有穷性、稳定性、确定性 D．可行性、易读性、有穷性9．以下关于数据的逻辑结构的叙述中正确的是（ A）。A．数据的逻辑结构是数据间关系的描述B．数据的逻辑结构反映了数据在计算机中的存储方式C．数据的逻辑结构分为顺序结构和链式结构D．数据的逻辑结构分为静态结构和动态结构

10．算法分析的主要任务是（C）。

A．探讨算法的正确性和可读性 B．探讨数据组织方式的合理性C．为给定问题寻找一种性能良好的解决方案 D．研究数据之间的逻辑关系

二．解答

设有一数据的逻辑结构为：B=(D,S)，其中：

D={d1,d2,…,d9}

S={d1,d3,d1,d8,d2,d3,d2,d4,d2,d5,d3,d9,d4,d7,d4,d6,

d5,d6,d8,d9,d9,d7}画出这个逻辑结构示意图。

d8

d8

d1

d9

d3

d2

d4

d7

d6

d5

第二章线性表

一、选择题

下述哪一条是顺序存储结构的优点？（A）

存储密度大B．插入运算方便C．删除运算方便D．可方便地用于各种逻辑结构的存储表示

下面关于线性表的叙述中，错误的是哪一个？（B）A．线性表采用顺序存储，必须占用一片连续的存储单元。B．线性表采用顺序存储，便于进行插入和删除操作。C．线性表采用链接存储，不必占用一片连续的存储单元。D．线性表采用链接存储，便于插入和删除操作。3．若某线性表最常用的操作是存取任一指定序号的元素和在最后进行插入和删除运算，则利用（A）存储方式最节省时间。

顺序表B．双链表C．带头结点的双循环链表D．单循环链表4．某线性表中最常用的操作是在最后一个元素之后插入一个元素和删除第一个元素，则采用（D）存储方式最节省运算时间。

A．单链表B．仅有头指针的单循环链表C．双链表D．仅有尾指针的单循环链表5．在一个长度为n的顺序表中删除第i个元素(0=i=n)时，需向前移动（A）个元素A．n-i B．n-i+l C．n-i-1 D．i

从一个具有n个结点的单链表中查找其值等于x的结点时，在查找成功的情况下，需平均比较（C）个元素结点

A．n/2 B．n C．（n+1）/2 D．（n-1）/2

设