数据结构习题（1,2,3章）

第一章 绪论

一．选择题

1．下面关于算法说法正确的是（ ） A．算法最终必须由计算机程序实现

B．为解决某问题的算法同为该问题编写的程序含义是相同的 C．算法的可行性是指指令不能有二义性 D．以上几个都是错误的

2．以下哪一个术语与数据的存储结构无关？（ ）

A．栈 B．哈希表 C．线索树 D．循环队列

3．算法复杂度通常是表达算法在最坏情况下所需要的计算量，O(1)的含义是（ ） A．算法执行一步就完成 B．算法执行1秒钟就完成 C．算法执行常数步就完成 D．算法执行可变步数就完成 4．数据结构研究的内容是（ ）。

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

5．一个正确的算法应该具有 5 个特性，除输入、输出特性外，另外 3 个特性是（ ）。 A．确定性、可行性、有穷性 B．易读性、确定性、有效性 C．有穷性、稳定性、确定性 D．可行性、易读性、有穷性 6．以下关于数据的逻辑结构的叙述中正确的是（ ）。 A．数据的逻辑结构是数据间关系的描述

B．数据的逻辑结构反映了数据在计算机中的存储方式 C．数据的逻辑结构分为顺序结构和链式结构 D．数据的逻辑结构分为静态结构和动态结构 7．下列时间复杂度中最坏的是（ ）

A．O(1) B．O(n) C．O(log2n） D．O(n2) 8．算法的时间复杂度取决于（ ）

A．待处理数据的初态 B．问题的规模

C．程序本身所占的空间 D．问题的规模和待处理数据的初态

二．综合应用题

1.有下列运行时间函数：

（1）f1(n)=1000; （2）f2(n)=n2+1000n; （3）f3(n)=3n3+100n2+n+1; 分别写出相应的大O表示的运算时间。

2.下面函数mergesort执行的时间复杂度为多少?假设函数调用为mergesort(1,n)，merge 函数时间复杂度为 O(n)

void mergesort(int i,int j) {

int m; if(i!=j) {

mergesort(i,m); mergesort(m+1,j);

merge(i,j,m);//本函数时间复杂度为 O(n)

} }

第二章 线性表

一．选择题

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

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

C．删除运算方便 D．可方便地用于各种逻辑结构的存储表示 2．下面关于线性表的叙述中，错误的是哪一个？（ ）

A．线性表采用顺序存储，必须占用一片连续的存储单元。 B．线性表采用顺序存储，便于进行插入和删除操作。 C．线性表采用链接存储，不必占用一片连续的存储单元。 D．线性表采用链接存储，便于插入和删除操作。

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

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

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

A．单链表 B．仅有头指针的单循环链表 C．双链表 D．仅有尾指针的单循环链表 5．在一个长度为n的顺序表中删除第i个元素(1<=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;

8．在一个单链表中，已知q结点是p结点的前趋结点，若在q和p之间插入s结点，则须执行（ ）

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

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

9．线性表的顺序存储结构是一种（ ）的存储结构。

A．随机存取 B．顺序存取 C．索引存取

D．散列存取

二．算法设计

1．设有一个正整数序列组成的有序单链表（按递增次序有序，且允许有相等的整数存在），试编写能实现下列功能的算法（要求用最少的时间和最小的空间） ①确定在序列中比正整数x大的数有几个（相同的数只计算一次） ②将单链表中比正整数x小的偶数从单链表中删除

2．设有一个表头指针为h的单链表。试设计一个算法，通过遍历一趟链表，将链表中所有结点的链接方向逆转，如下图所示。要求逆转结果链表的表头指针h指向原链表的最后一个结点。

Λ

3．设计算法将一个带头结点的单链表A分解为两个具有相同结构的链表B、C，其中B表的结点为A表中值小于零的结点，而C表的结点为A表中值大于零的结点（链表A的元素类型为整型，要求B、C表利用A表的结点）。 4. 假设链表A、B分别表示一个集合，试设计算法以判断集合A是否是集合B的子集，若是，则返回1，否则返回0，并分析算法的时间复杂度。

5．设有一单循环链表la，其结点有三个域：prior、data与next，其中data为数据域,，next域指向直接后继，prior域应指向直接前驱，但目前空着。试写一算法将此单循环链表改造为双向循环链表。

6．设顺序表用数组 A[]表示，表中元素存储在数组下标 1~m+n 的范围内，前 m 个元素递增有序，后 n 个元素递增有序，设计一个算法，使得整个顺序表有序。 （1）给出算法的基本设计思想。

（2）根据设计思想，采用C或C++语言描述算法，关键之处给出注释。 （3）说明你所设计算法的时间复杂度和空间复杂度。

p h Λ

Λ h