数据结构算法设计题100题

前五章习题算法

2.2

算法设计题

1.设计一个算法从一给定的有序顺序表L中删除元素值在X到Y(X<=Y)之间的所有元素,要求以较高的效率实现,要求算法的空间复杂度为O(1) void delete(SqList &L,ElemType x,ElemType y) {

int i=0,k=0;

while(i=x &&L.elem[i]

L.length=L.length-k; }

2设一个有序表L,含有2n个整数,其中n个位负数,n个为正数,设计一个算法将L中所有元素按正负相间排列. 要求算法的空间复杂度为O(1),时间复杂度为O(n) void move(SqList &L) {

int i=0,j=L.length-1; int temp;

while(i0)i++; while(i

while(i

} }

3.假设一两个元素依之=值递增有序排列的线性表A和B分别表示两个集合(同一 元素值各不相同),要求分别设计求A和B交并差集的算法,要求结果线形表中的元素依值递增有序排列,试对顺序表实现上述操作. 交集:

void intersection(SqList A,SqList B ,SqList &C) {

int i=0,j=0,k=0;

while(iB.elem[j]) j++; else { C.elem[k]=A.elem[i]; k++;i++;j++;} //共同

A 装箱问题模拟（20）

源码：

#include #include using namespace std;

char box[1010];

int main() {

memset(box,100,sizeof(box)); int N; int t;

int num=0; cin>>N;

int temp = N; while(temp--) {

cin>>t;

for (int i=0;i

int a = box[i]; if (a>=t) {

if (a==100) num++;

box[i] -=t;

cout<

cout<

//system(\ return 0; }

B 表达式转换（25）

源码：

#include #include #include using namespace std;

stack sta;

int main() {

string s;

string anwser; cin>>s;

int i;

bool n

第一章绪论

1.16

void print_descending(int x,int y,int z)//

按从大到小顺序输出三个数

{

scanf("%d,%d,%d",&x,&y,&z);

if(xy; //<->为表示交换的双目运算符,以下同

if(yz;

if(xy; //冒泡排序

printf("%d %d %d",x,y,z);

}//print_descending

1.17

Status fib(int k,int m,int &f)//求k 阶斐波那契序列的第m 项的值f

{

int tempd;

if(k<2||m<0) return ERROR;

if(m

else if (m==k-1) f=1;

else

{

for(i=0;i<=k-2;i++) temp[i]=0;

temp[k-1]=1; //初始化

for(i=k;i<=m;i++) //求出序列第k 至第m 个元素的值

{

sum=0;

for(j=i-k;j

temp[i]=sum;

}

f=temp[m];

}

return OK;

}//fib

分析:通过保存已经计算出来的结果,此方法的时间复杂度仅为O(m^2).如果采用递归编程(大多数人都会首先想到递归方法),则时间复杂度将高达O(k^m).

1.18

typedef struct{

char *sport;

enum{male,female}

gender;

char schoolname; //校名为'A

数据结构（本科）期末综合练习（算法设计题）

1. 设有一个线性表 (e0, e1, ?, en-2, en-1) 存放在一个一维数组A[arraySize]中的前n个数组元素位置。请编写一个函数将这个线性表原地逆置，即将数组的前n个元素内容置换为 (en-1, en-2, ?, e1, e0)。 函数的原型为：

template

void inverse ( Type A[ ], int n );

2. 试编写一个函数，在一个顺序表A中找出具有最大值和最小值的整数。

函数的原型如下所示，原型的参数表中给出顺序表对象为A，通过算法执行，从参数表中的引用参数Max中得到表中的最大整数，Min中得到表中的最小整数。

注意，函数中可使用顺序表的两个公有函数： Length( ) 求表的长度；

getData(int k) 提取第k个元素的值。

#include “SeqList.h”

template void FindMaxMin ( SeqList& A, int& Max, int& Min );

3. 设有两个整数类型的顺序表A（有 m个元素）和B（有n个元素），其元素均以升序排列。试编写一个函数，将这两个顺序表合并成一个顺

一.选择题（共15题，每题3分）

（1）下面关于算法说法错误的是_______。 a. 算法最终必须由计算机程序实现

b. 为解决某问题的算法同为该问题编写的程序含义是相同的 c. 算法的可行性是指指令不能有二义性 d. 以上几个都是错误的 （2）下面说法错误的是______.

a. 算法原地工作的含义是指不需要任何额外的辅助空间

b. 在相同的规模n下，复杂度O(n)的算法在时间上总是优于复杂度O(2n)的算法 c. 所谓时间复杂度是指最坏情况下，估算算法执行时间的一个上界 d. 同一个算法，实现语言的级别越高，执行效率就越低 （3）在下面的程序段中，对x的赋值语句的频度为_____。 for (int i; i

a. 0(2n) b. 0(n) c. 0(n2) d. O(log2n) （4）下面说法正确的是______。 a. 数据元素是数据的最小单位； b. 数据元素是数据的最小单位；

c. 数据的物理结构是指数据在计算机内的实际存储形式 d. 数据结构的抽象操作的定义与具体实现有关 （5）下面说法正确的是_______。

a. 在顺序存储结构中，有时也存储数据结构中元素之间的关系 b. 顺序

西安科技大学

2013年硕士研究生入学考试试题答案A

─────────────────────────────────

科目编号：824 科目名称：数据结构与算法设计

答案A： 一、 二、

单选题（2×15=30分） BDDAC BBCDC ABABC 填空题（2×10=20分）

（1） 运算/操作 （2） 4 （3） 90 （4） h （5） 2m-1 （6）top=p （7）队尾 （8）5 （9）n-1 （10）直接插入排序

三、

简答题（任选5道题，每小题8分，共40分）（只要答出要点即可） 顺序表：空间利用率高，插入、删除运算效率低；

链表：插入、删除运算效率高，不必事先估计“容量”， 空间利用率低。 （2）“假溢出”现象是

处理方式有 判断队满和队空

（3）二叉树的顺序存储方式是一维数组存储二叉树，且能反映各节点之间的逻辑关系； 优点是可方便实现二叉树的基本操作，缺点是，除非是完全二叉树，否则空间浪费很大。

（4）邻接矩阵：

邻接表、逆邻接表：不方便判断某两个顶点是否有边； 两种方式各有利弊。 （5）顺序查找，（n+1）/2;

第1章绪论

一、选择题

1. 算法的计算量的大小称为计算的（）。【北京邮电大学2000 二、3 （20/8分）】

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

2. 算法的时间复杂度取决于（）【中科院计算所 1998 二、1 （2分）】

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

3.计算机算法指的是（1），它必须具备（2）这三个特性。

(1) A．计算方法 B. 排序方法 C. 解决问题的步骤序列 D. 调度方法

(2) A可执行性、可移植性、可扩充性 B.可执行性、确定性、有穷性

C. 确定性、有穷性、稳定性

D.易读性、稳定性、安全性

【南京理工大学 1999 一、1（2分）【武汉交通科技大学 1996 一、1（ 4分）】

4．一个算法应该是（）。【中山大学 1998 二、1（2分）】

A．程序 B．问题求解步骤的描述 C．要满足五个基本特性 D．A和C.

5. 下面关于算法说法错误的是（）【南京理工大学 2000 一、1（1.5分）】

A．算法最终必须由计算机程序实现 B.为解决某问题的算法同为该问题编写的程序含义是相同的

C. 算法的可行性是指指令

第1章 绪论

1.1 简述下列术语：数据，数据元素、数据对象、数据结构、存储结构、数据类型和抽象数据类型。

解：数据是对客观事物的符号表示。在计算机科学中是指所有能输入到计算机中并被计算机程序处理的符号的总称。

数据元素是数据的基本单位，在计算机程序中通常作为一个整体进行考虑和处理。 数据对象是性质相同的数据元素的集合，是数据的一个子集。 数据结构是相互之间存在一种或多种特定关系的数据元素的集合。 存储结构是数据结构在计算机中的表示。

数据类型是一个值的集合和定义在这个值集上的一组操作的总称。 抽象数据类型是指一个数学模型以及定义在该模型上的一组操作。是对一般数据类型的扩展。

1.2 试描述数据结构和抽象数据类型的概念与程序设计语言中数据类型概念的区别。

解：抽象数据类型包含一般数据类型的概念，但含义比一般数据类型更广、更抽象。一般数据类型由具体语言系统内部定义，直接提供给编程者定义用户数据，因此称它们为预定义数据类型。抽象数据类型通常由编程者定义，包括定义它所使用的数据和在这些数据上所进行的操作。在定义抽象数据类型中的数据部分和操作部分时，要求只定义到数据的逻辑结构和操作说明，不考虑数据的存

西安科技大学

2013年硕士研究生入学考试试题答案A

─────────────────────────────────

科目编号：824 科目名称：数据结构与算法设计

答案A： 一、 二、

单选题（2×15=30分） BDDAC BBCDC ABABC 填空题（2×10=20分）

（1） 运算/操作 （2） 4 （3） 90 （4） h （5） 2m-1 （6）top=p （7）队尾 （8）5 （9）n-1 （10）直接插入排序

三、

简答题（任选5道题，每小题8分，共40分）（只要答出要点即可） 顺序表：空间利用率高，插入、删除运算效率低；

链表：插入、删除运算效率高，不必事先估计“容量”， 空间利用率低。 （2）“假溢出”现象是

处理方式有 判断队满和队空

（3）二叉树的顺序存储方式是一维数组存储二叉树，且能反映各节点之间的逻辑关系； 优点是可方便实现二叉树的基本操作，缺点是，除非是完全二叉树，否则空间浪费很大。

（4）邻接矩阵：

邻接表、逆邻接表：不方便判断某两个顶点是否有边； 两种方式各有利弊。 （5）顺序查找，（n+1）/2;

一、判断题 (每题1分,共131分)

1. 线性表的逻辑顺序总是与其物理顺序一致。（ ） 【答案】错

2. 线性表的顺序存储优于链式存储。（ ） 【答案】错

3. 在长度为n的顺序表中，求第i个元素的直接前驱算法的时间复杂度为0（1）。（ ） 【答案】对

4. 若一棵二叉树中的结点均无右孩子，则该二叉树的中根遍历和后根遍历序列正好相反。（ ） 【答案】错

5. 顺序表和一维数组一样，都可以按下标随机（或直接）访问。（ ） 【答案】对

6. 内部排序是指排序过程在内存中进行的排序。（ ）

【答案】对

7. 当待排序序列初始有序时，简单选择排序的时间复杂性为O(n)。（ ） 【答案】错

8. 用邻接矩阵存储一个图时，在不考虑压缩存储的情

况下，所占用的存储空间大小只与图中的顶点个数有关，而与图的边数无关。 ( )

14. 当向一个最小堆插入一个具有最小值的元素时，该

元素需要逐层向上调整，直到被调整到堆顶位置为止。( )

【答案】对

15. 哈希查找法中解决冲突问题的常用方法是除留余数法。（ ） 【答案】错

16. 对具有n个结点的堆进行插入一个元素运算的时间复杂度为O(n)。( ) 【答案】错

17. 堆排序是一种稳定的排序