数据结构算法设计题题库

前五章习题算法

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++;} //共同

一、单项选择题

2

1某算法的时间复杂度是O(n)，表明该算法（ ）。

22

A 问题规模是n B 问题规模与n成正比

2 2

C 执行时间等于n D 执行时间与n成正比 2、关于数据结构的描述，不正确的是（ ）。 A 数据结构相同，对应的存储结构也相同。

B 数据结构涉及数据的逻辑结构、存储结构和施加其上的操作等三个方面。 C 数据结构操作的实现与存储结构有关。 D 定义逻辑结构时可不考虑存储结构。

3、按排序策略分来，起泡排序属于（ ）。

A 插入排序 B 选择排序 C 交换排序 D 归并排序 4、利用双向链表作线性表的存储结构的优点是（ ）。

A 便于进行插入和删除的操作 B 提高按关系查找数据元素的速度 C 节省空间 D 便于销毁结构释放空间

5、一个队列的进队顺序为1,2,3,4，则该队列可能的输出序列是（ ）。 A 1,2,3,4 B 1,3,2,4 C 1,4,2,3 D 4,3,2,1 6、Dijkstra算法是按（ ）方法求出图中从某顶点到其余顶点最短路径的。 A 按长度递减的顺序求出图的某顶点到其余顶点的最短路径

B 按长度递增

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

一.选择题（共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. 顺序

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

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个元素），其元素均以升序排列。试编写一个函数，将这两个顺序表合并成一个顺

西安科技大学

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;

西安科技大学

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.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.从逻辑上可以把数据结构分为（C）。

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

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

2.若某线性表的常用操作是取第i个元素及其前趋元素，则采用( A )存储方式最节省时间 A.顺序表 B.单链表 C.双链表 D.单向循环

3. 衡量查找算法效率的主要标准是（B）。

A.元素个数 B.平均查找长度 C.所需的存储量 D.算法难易难度

4.程序段s=i=0；do {i=i+1； s=s+i；}while(i<=n)；的时间复杂度为（ A ）。 A O(n) B O(nlog2n) C O(n2) D O(n3/2) 5.下述哪一条是顺序存储方式的优点？（A ）

A．存储密度大 B.插入和删除运算方便 C. 获取符合某种条件的元素方便 D.查找运算速度快

6.下列关于数据结构的叙述中，正确的是( D ). A.数组是不同类型值的集合

B.递归算法的程序结构比迭代算法的程序结构更为精炼 C.树是一种线性结构

D.用一维数组存储一棵完全二叉树是有效的存储方法

7.对一个算法的评价，不包括如下（B ）方面的内容。

A．健壮性和可读性 B．并行性 C．正确性 D．时空复杂度 8.

第一章绪论（含算法的定义和度量）

1.从逻辑上可以把数据结构分为（C）。

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

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

2.若某线性表的常用操作是取第i个元素及其前趋元素，则采用( A )存储方式最节省时间 A.顺序表 B.单链表 C.双链表 D.单向循环

3. 衡量查找算法效率的主要标准是（B）。

A.元素个数 B.平均查找长度 C.所需的存储量 D.算法难易难度

4.程序段s=i=0；do {i=i+1； s=s+i；}while(i<=n)；的时间复杂度为（ A ）。 A O(n) B O(nlog2n) C O(n2) D O(n3/2) 5.下述哪一条是顺序存储方式的优点？（A ）

A．存储密度大 B.插入和删除运算方便 C. 获取符合某种条件的元素方便 D.查找运算速度快

6.下列关于数据结构的叙述中，正确的是( D ). A.数组是不同类型值的集合

B.递归算法的程序结构比迭代算法的程序结构更为精炼 C.树是一种线性结构

D.用一维数组存储一棵完全二叉树是有效的存储方法

7.对一个算法的评价，不包括如下（B ）方面的内容。

A．健壮性和可读性 B．并行性 C．正确性 D．时空复杂度 8.