专升本_数据结构.doc

第一章 绪论

一．选择题

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

①A．算法 B．

数据元素

C．数据操作 D．逻辑结构

②A．操作 B．映象 C．存储 D．关系

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

①A．找出数据结构的合理性 ② A．

空间复杂性和时间复杂性

B．正确性和简明性 B．研究算法中的输入和输出的关系

C．

线性结构和非线性结构

D．内部结构和外部结构

5．以下属于顺序存储结构优点的是（ ）。

A．

存储密度大

B．插入运算方便

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

6．数据结构研究的内容是（ ）。

A．数据的逻辑结构 B．数据的存储结构

C．建立在相应逻辑结构和存储结构上的算法 D．

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

A．

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

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

A．

数据的逻辑结构是数据间关系的描述

B．数据的逻辑结构反映了数据在计算机中的存储方式

C．数据的逻辑结构分为顺序结构和链式结构

D．数据的逻辑结构分为静态结构和动态结构

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

A．探讨算法的正确性和可读性 B．探讨数据组织方式的合理性

C．

为给定问题寻找一种性能良好的解决方案

第二章 线性表

一、选择题

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

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

A．

顺序表

B．双链表 C．带头结点的双循环链表 D．单循环链表

4．某线性表中最常用的操作是在最后一个元素之后插入一个元素和删除第一个元素，则采用（ ）存储方式最节省运算时间。

A．单链表 B．仅有头指针的单循环链表 C．双链表 D．

仅有尾指针的单循环链表

5．在一个长度为 n 的顺序表中删除第 i 个元素(0<=i<=n)时，需向前移动（ ）个元素

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

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

A．n/2 B．n C．

（

n+1

）

/2 D．（n-1）/2

7．设单链表中指针 p 指向结点 m，若要删除 m 之后的结点（若存在），则需修改指针的操作为（ ）

A．p->next=p->next->next; B．p=p->next; C．p=p->next->next; D．p->next=p;

1．在线性表的顺序存储中元素之间的逻辑关系是通过

（

）

定的。

2．在双向链表中，每个结点含有两个指针域，一个指向（ ）结点，另一个指向（ ）结点。

3．当对一个线性表经常进行存取操作，而

和删除操作时，则采用（ ）存储结构为宜。

第三章 栈和队列

一、选择题

1．已知栈的最大容量为 4。若进栈序列为 1，2，3，4，5，6，且进栈和出栈可以穿插进行,则可能出现的出栈序列为（ ）

A.5，4，3，2，1，6 B.2，3，5，6，1，4 C.3

，

5

，

4

，

1

，

6 D.1，4，6，5，2，3

设有一个栈，元素的进栈次序为 A, B, C, D, E,下列是不可能的出栈序列（ ）

4．在具有 n 个单元的顺序存储的循环队列中，假定 front 和 rear 分别为队头指针和队尾指针，则判断队满的条件为（ ）

A．rear％n= = front B．（front+l）％n= = rear C．rear％n -1= = front D．(rear+l)

％

n= = front

5．在具有 n 个单元的顺序存储的循环队列中，假定 front 和 rear 分别为队头指针和队尾指针，则判断队空的条件为（ ）

A．rear％n= = front B．front+l= rear C．rear= = front D．(rear+l)％n= front

6．在一个链队列中，假定 front 和 rear 分别为队首和队尾指针，则删除一个结点的操作为（ ）