数据结构习题及答案

第1章 算法

一、选择题

1. 算法的时间复杂度是指（ ）。 A）执行算法程序所需要的时间 B）算法程序中的指令条数

C）算法执行过程中所需要的基本运算次数 D）算法程序的长度

2. 算法的空间复杂度是指（ ）。 A）算法程序的长度

B）算法程序所占的存储空间

C）算法执行过程中所需要的存储空间 D）算法程序中的指令条数

3.下面（ ）的时间复杂度最好（即执行时间最短）。

A）O(n ) B）O(log2n) C）O(nlog2n ) D）O(n)

2

4.下面累加求和程序段的时间复杂度为（ ）。 int sum(int a[],int n) {

int i, s=0;

for (i=0;i

5.下面是将两个n阶矩阵a[][]与b[][]相加的结果存放到n阶矩阵c[][]中的算法，该算法的时间复杂度为（ ）。

void matrixadd(int a[][],int b[][],c[][],int n) {

int i,j;

for (i=0;i

for(j=0;j

c[i][j]=a[i][j]+b[i][j]; }

A）O(1 ) B）O(log2n) C）O( n ) D）O(n) 6.下面程序段的时间复杂度为（ ）。

1

2

2

int i=0,s1=0,s2=0; while(i

if(i%2) s1+=i;

else

s2+=i; i++; }

A）O(1 ) B）O(log2n ) C）O(n ) D）O(n) 7.下面程序段的时间复杂度为（ ）。

int prime(int n) {

int i=1;

int x=(int)sqrt(n); while(i<=x) {

i++;

if(n%i==0) break; }

if(i>x) return 1; else

return 0;

}

A）O(1 ) B）O(log2n) C）O(n ) D）O(n) 8.下面程序段的时间复杂度为（ ）

int fun(int n) {

int i=1,s=1; while(s

i++; s+=i; }

return i; }

A）O(n/2) B）O(log2n)

2

2

C）O(n ) D）O(n) 9.下面程序段的时间复杂度为（ ）

int i,j,m,n,a[][]; for(i=0;i

A）O(m) B）O(n) C）O(m*n ) D）O(m+n) 10. 下面程序段的时间复杂度为（ ）

int sum1(int n) {

int i,p=1,s=0; for(i=1;i<=n;i++) {

p*=i;

s=s+p;

}

return s; }

A）O(1 ) B）O(log2n) C）O(n ) D）O(n)

二、填空题

1.算法复杂度主要包括时间复杂度和 复杂度。

2.一个算法的时间复杂度的计算式为 ( 3n+2n+5 ) / n ，其数量级表示为 。 3.从一维数组a[n]中顺序查找出一个最大值元素的平均时间复杂度为 ，读取一个二维数组b[m][n]中任一元素的时间复杂度为 。

4.在下面程序段中，s = s+p语句的执行次数为 ，p*=j 语句的执行次数为 ，该程序段的时间复杂度为 。

int i=0, s=o; while(++i <=n) {

int p=1;

for(int j=1; j<=i ; j++ )

p*=j ; s=s+p ; }

5. 通常用平均性态分析和 两种方式来确定一个算法的工作量。

三、 简答题

3. 什么是算法？

4. 算法的基本特征是什么？

2

2

2

2

3

5. 算法的两种基本要素是什么？

6. 递归是算法的基本方法之一，其基本思想是什么？ 7. 算法的描述方法有多种，试说出任意三种方法。

四、编写出求下列问题的算法

1.比较两个整型数据a1与a2的大小，对于a1 > a2、a1 == a2、a1< a2这三种不同情况应分别返回“>”、“=”、“<”字符。

2.求一维double型数组a[n]中的所有元素之乘积。

3.假定一维整型数组a[n]中的每个元素值x均在[0，200]区间内，分别统计出落在0≤x < 20、20≤x<50、50≤x<80、80≤x<130、13 ≤x≤200各区间内的元素个数。

参考答案

一、单选题

1.C 2.C 3.B 4.C 5.D 6.C 7.D 8.D 9.C 10.C 二、填空题

1. 空间 2. O(n)

3.O(n)，O(1) 4. n，n(n+1)/2，O(n) 5. 最坏情况复杂性 三、简答题

1. 答案：所谓算法是指解题方案的准确而完整的描述。

2. 答案：算法的基本特征为：1)可行性；2)确定性；3)有穷性；4)拥有足够的情报。 3. 答案：算法通常由两种基本要素组成；一是对数据对象的运算和操作；二是算法的控制结构。

4. 答案：人们在解决一些复杂问题时，为了降低问题的复杂程度，一般总是将问题逐层分解，最后归结为一些最简单的问题。这种将问题逐层分解的过程，实际上并没有对问题进行求解。而只是当解决了最后那些最简单的问题后，再沿着原来分解的逆过程逐步进行综合，这就是递归的基本思想。

5.答案：一个算法可以用多种方式来描述，如自然语言、程序语言、流程图等。 四、算法设计

1.比较两个整型数据a1与a2的大小。

char compare(int a1,int a2) { if(a1>a2) return \elase if(a1==a2) return \

4

2

elase return \}

2.求一维double型数组a[n]中的所有元素之乘积。

double product(dluble a[],int n)

{

double p=1; for(int i=0;i< n;i++) p=p*a[i]; return p; }

3.统计数组a[n]中的每个元素值x分别落在0≤x<20、20≤x<50、50≤x< 80、80≤x<130、130≤x≤200各区间内的元素个数。

int count(int a[],int n,int c[5]) //用c[5]保存统计结果

{

int d[5]={20,50,80,130,201}; //用d[5]保存各统计区间上限 int i,j;

for(i=0;i

if(a[i]<0; || a[i]>200)

return 0; //数组中数据有错，统计失败 for(j=0;j< 5;j++)

if(a[i]

c[j]++; //使统计相应区间的元素数增1 }

return 1; //表示统计成功 }

5

{

if(r!=NULL) {

if(r->lchild!=NULL && r->rchild!=NULL) if(r->lchild->data >r->rchild->data) {

BiTree t=r->lchild; r->lchild=r->rchild; r->rchild=t; }

change(r->lchild); change(r->rchild); } }

2. 统计出二叉树中大于给定值x的结点个数，该统计值由函数返回。

int count(BiTree r,ElemType x)

{

if(r!=NULL) {

if(r->data >x)

return count(r->lchild,x)+count(r->rchild,x)+1; else

return count(r->lchild,x)+count(r->rchild,x); } return 0;

}

3. 对具有n个结点的二叉树进行中序遍历，并将得到的结点值序列保存到数组中。

void preserve(BiTree r,ElemType a[],int n)

{

static int i=0; if(r!=NULL) {

26

preserve(r->lchild,a,n); a[i++]=r->data; preserve(r->rchild,a,n); } }

第6章 图

一、单项选择题

1. 在一个具有n个顶点的有向图中，若所有顶点的出度数之和为s，则所有顶点的入度数之和为（ ）。

A）s B）s - 1 C）s+1 D）n 2. 在一个具有n个顶点的有向图中，若所有顶点的出度数之和为s，则所有顶点的度数之和为（ ）。

A）s B）s+1 C）s - 1 D）2s

3.在一个具有n个结点的无向图中，若具有e条边，则所有顶点的度数之和为（ ）。

A）n B）e C）2e D）n+e

4. 在一个具有n个顶点和e条边的无向图的邻接矩阵中，非零元素的个数为（ ）。

A）n B）ne C）e D）2e

5. 在一个具有n个顶点和e条边的无向图的邻接表中，边结点的个数为（ ）。

A）n B）ne C）e D）2e

二、填空题

1. 在一个无向图中，所有顶点的度数之和等于所有边数的 倍。

2. 若一个有向图的顶点集为{ a, b, c, d, e, f }，其顶点偶对的集合为{ ,,,,, }，则出度为0的顶点个数为 ，入度为1的顶点个数为 。

3. 在一个具有n个顶点的无向图中，要连通所有顶点，则至少需要 条边。 4. 表示图的两种存储结构为 和 。 5. 对于一个具有n个顶点的图，若采用邻接矩阵表示，则矩阵大小至少为 × 。 6. 对于一个具有n个顶点和e条边的无向图，在其对应的邻接表中，所含边结点的个数为 。

7. 图的深度优先搜索遍历，类似于树的 遍历；图的广度优先搜索遍历，类似与树的 遍历。

8. 一个图的顶点偶对集合为{ (a,c), (a,e), (b,e), (c,d), (d,e) }，从顶点a出发进行深度优先搜索遍历得到的顶点序列为 ；从顶点a出发进行广度优先搜索遍历得到的顶点序列为 。

27

参考答案

一、单项选择题

1.A 2.D 3.C 4.D 5.D

二、填空题

1. 2 2. 2, 4

3. n-1 4. 邻接矩阵，邻接表 5. n, n 6. e

7. 先序，层次 8. acdeb, acedb（答案不唯一）

第7章 查找与排序

一、单项选择题

1. 若查找每个元素的概率相等，则在长度为n的顺序表上，查找任一元素的平均查找长度为（ ）。

A）n B）n+1 C）(n+1)/2 D）(n-1)/2

2. 对长度为n的单链有序表，若查找每个元素的概率相等，则查找任一元素的平均查找长度为（ ）。

A）n/4 B）(n+1)/2 C）n/2 D）(n-1)/2

3. 对长度为9的顺序存储的有序表，采用折半法查找，在等概率情况下的平均查找长度为（ ）的值除以9。

A）18 B）20 C）25 D）22

4. 对长度为18的顺序存储的有序表，采用折半法查找，则查找第15个元素的查找长度为（ ）。

A）3 B）4 C）5 D）6

5. 对顺序存储的有序表（5，12，20，26，37，42，46，50，64），采用折半查找，则查找元素26的查找长度为（ ）。

A)2 B)3 C)4 D)5 6. 顺序查找法适合于存储结构为（ ）的线性表。

A）压缩存储 B）顺序存储或链式存储 C）索引存储 D）散列存储 7. 对线性表进行折半查找的前提条件是（ ）。

A）线性表以顺序方式存储，并且按关键字的查找频率排好序 B）线性表以顺序方式存储，并且按关键字的大小排好序 C）线性表以链式方式存储，并且按关键字的大小排好序 D）线性表以链式方式存储，并且按关键字的查找频率排好序

8. 在分块查找中，若用于查找表的长度为n，它被等分为k个子表，每个子表的长度均为n/k，则分块查找的平均查找长度为（ ）。

A）n+k B）k+k/n C）(k+k/n)/2+1 D）(k+k/n)/2

28

9. 在分块查找中，若用于查找表的长度为n，它被等分为若干个子表，每个子表的长度均为s，则分块查找的平均查找长度为（ ）。

A）(n+s)/2 B）(n+s)/2+1 C）(s+n/s)/2+1 D）(s+n/s)/2

10. 在分块查找中，若用于查找表的长度为144，它被等分为12个子表，每个子表的长度均为12，则分块查找的平均查找长度为（ ）。

A）12 B）24 C）13 D）79

11. 在分块查找中，若用于查找表的长度为117，它被等分为9个子表，则分块查找的平均查找长度为（ ）。

A）11 B）12 C）13 D）9

12.在一棵深度为h的具有n个元素的二叉排序树中，查找所有元素的最长查找长度为（ ）。

A）n B）log2n C）(h+1)/2 D）h

13.从具有n个结点的二叉排序树中查找一个元素时，在平均情况下的时间复杂度的为（ ）。

A）O(n) B）O(1) C）O(log2n) D）O(n)

14.从具有n个结点的二叉排序树中查找一个元素，在最坏情况下的平均查找长度是（ ）。

A）n B）log2n C）(n+1)/2 D）(n-1)/2

15. 若对n个元素进行插入排序，在进行第i遍排序过程前，有序表中的元素个数为（ ）。

A）i B）i+1 C）i-1 D）1

16. 若对n个元素进行插入排序，在进行第i遍排序时，为寻找插入位置，最多需要进行（ ）次元素的比较（假设第0号元素放有待查元素关键字）。

A）i B）i-1 C）1 D）i+1 17. 若对n个元素进行插入排序，在进行第i遍排序时，假设元素a[i+1]的插入位置为，a[j]，则需要移动元素的次数为（ ）。

A）j-i B）i-j-1 C）i-j D）i-j+1 18. 对n个元素进行插入排序的过程中，共需要进行（ ）遍。

A）n+1 B）n C）2n D）n-1 19. 对n个元素进行插入排序的时间复杂度为（ ）。

A）O(1) B）O(n) C）O(n) D）O(log2n)

20. 在对n个元素进行冒泡排序的过程中，第一遍排序，最多需要进行（ ）对相邻元素之间的交换。

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

21. 在对n个元素进行冒泡排序的过程中，最好情况下的时间复杂度的为（ ）。

A）O(1) B）O(n) C）O(n) D）O(log2n) 22. 在对n个元素进行冒泡排序的过程中，最坏情况下的时间复杂度为（ ）。

A）O(1) B）O(n) C）O(n) D）O(log2n) 23. 在对n个元素进行冒泡排序的过程中，最少需要（ ）遍完成。

222

2

29

A）1 B）n C）n-1 D）n/2

24. 在对n个元素进行快速排序的过程中，第一次划分最多需要移动（ ）次元素，包括开始把基准元素移动到临时变量中的一次。

A）n/2 B）n-1 C）n D）n+1 25. 在对n个元素进行快速排序的过程中，最好情况下需要进行（ ）遍。

A）n B）n/2 C）log2n D）2n 26. 在对n个元素进行快速排序的过程中，最坏情况下需要进行（ ）遍。

A）n B）n/2 C）log2n D）n-1 27. 在对n个元素进行快速排序的过程中，最好情况下的时间复杂度为（ ）。

A）O(1) B）O(n) C）O(nlog2n) D）O(log2n) 28. 在对n个元素进行快速排序的过程中，最坏情况下的时间复杂度为（ ）。

A）O(1) B）O(n) C）O(nlog2n) D）O(log2n)

29. 对元素序列（3，7，5，9，1）进行快速排序，在进行第一遍划分时，需要移动元素的次数为（ ），假设不包括开始把基准元素移动到临时变量的一次。

A）1 B）2 C）3 D）4

30. 在对下列四个序列进行快速排序时，各以第一个元素为基准进行第一遍划分，则在该次划分过程中，需要移动元素次数最多的序列为（ ）。

A）1，3，5，7，9 B）9，7，5，3，1 C）5，3，1，7，9 D）5，7，9，1，3

31.对元素序列（7，3，5，9，1，12，8，15）进行快速排序，在进行第一遍划分后，得到的左区间中元素的个数为（ ）。

A）2 B）3 C）4 D）5

32. 在对n个元素进行选择排序的过程中，在第i遍，需要从（ ）个元素中选择出最小值元素。

A）n-i+1 B）n-i C）i D）i+1

33. 对n个元素进行选择排序，在进行任一遍排序的过程中，为寻找最小值元素所需要的时间复杂度量级为（ ）。

A）O(1) B）O(n2)

C）O(log2n) D）O(n)

34. 若对n个元素进行归并排序，则进行归并的遍数为（ ）。

A）n B）n/2

C）?log2n? D）n-1

35. 对n个元素进行归并排序，在进行每一遍的时间复杂度量级为（ ）。

A）O(1) B）O(n2)

C）O(log2n) D）O(n)

36. 若一个元素序列基本有序，则选用（ ）方法较快。

A）插入排序 B）选择排序

30

22

inl y,m,d；

cout<<\请输入职工的出生日期(年月日)：\ cin>>y>>m>>d； BirthDay.setDate(y,m,d);

cout<<\请输入职工的受聘日期(年月日)：\； cin>>y>>m>>d； HireDay.setDate(y,m,d);

TotalMounthPay=0.0; //月薪总额初值为0 }

//构造函数

Employee::Employee(char *empKind, int empNo, char *name, char *sex, float totalMounthPay, int yl, int ml, int dl, int y2, int m2, int d2) {

strcpy(EmpKind, empKind); strcpy(Name,name); strcpy(Sex, sex); EmpNo= empNo;

TotalMounthPay=totalMounthPay; Daysetting(y1,m1,d1,y2,m2,d2); {

int Employee::getEmpNo( ) //取职工号 { retum EmpNo;}

float Employee::getTotalMounthPay( ) //取月薪总额 { retum TotalMounthPay;}

void Employee::print( ) //打印职工的信息 { cout<

void Employee::savetofile( ) //保存职工的信息

46

{ ofstream wages;

wages.open(\ if(! wages)

{ cout<<\月薪文件不能打开, 请检查．\\n\ return; }

wages<

<

void Employee::readwages(Employee **pEmp) //读出职工的信息 { char empKind[20], name[20], sex[10]; int empNo,y1,ml,d1,y2,m2,d2; float totalMounthPay； ifstream wages； wages.open(\ if (! wages)

{ cout<<\月薪文件不能打开，请检查．\\n \ return; } int i=0；

while(!wages.eof( ))

{ wages>>empKind>>empNo>>name>>sex>>totalMounthPay >>y1>>m1>>d1>>y2>>m2>>d2;

pEmp[i++]=new Employee(empKind, empNo, name, sex, totalMounthPay, y1, m1, dl, y2, m2, d2); }

wages.close( )； }

void Employee::Daysetting(int yl, int m1, int d1, int y2, int m2, int d2)

47

{ BirthDay.setDate(y1, m1, d1); HireDay.setDate(y2, m2, d2); }

float Employee::earnings( ) //计算月薪总额函数 {return 0；}

//BOSSl.CPP

//定义经理类Boss的成员函数 #include #include #include \ //类Boss的构造函数

Boss::Boss( ) //调用基类的缺省构造函数 { strcpy(EmpKind; \经理\ //职工种别

cout<<\请输入经理\的月薪：\ TotalMounthPay=earnings( ); }

float Boss::getMouthSalay( ) {return MouthSalary; }

float Boss::earnings( ) //计算月薪总额函数 {return MouthSalary; }

//COMMISl.CPP

//定义推销员类CommissionWorker的成员函数 #include #include #include \

//类CommisssionWorker的构造函数

CommissionWorker::CommissionWorker( ) //调用基类的缺省构造函数 { strcpy(EmpKind,\推销员\ //职工种别 cout<<\请输入\的本月销售量：\ cout<<\请输入\的本月提成比例：\

48

TotalMounthPay=earnings( ); }

float CommissionWorker::earnings( ) //计算月薪总额函数 {return commission*quantity; }

//HOURLYl.CPP

//定义小时工类HourlyWorker的成员函数 #include #include #include \

//类HourlyWorker的构造函数

HourlyWorker::HourlyWorker( ) //调用基类的缺省构造函数 { strcpy(EmpKind, \小时工\ //职工种别

cout<<\请输入小时工\的本月工作小时数: \ cout<<\请输入小时工\的本月每小时酬金：\ TotalMounthPay:earnings( ); }

float HourlyWorker::earnings( ) //计算月薪总额函数 {return wage *hours; }

//PIECEl.CPP

//定义计件工类PieceWorker的成员函数 #include #include #include \

//类PieceWorker的构造函数

PieceWorker::PieceWorker() //调用基类的缺省构造函数 { strcpy(EmpKind, \计件工\ //职工种别

cout<<\请输入计件工\的本月产品件数：\ cout<<\请输入计件工\的本月每件产品的报酬: \ cin>>wagePerPiece; TotalMounthPay=earnings();

49

}

float PieceWorker::earnings() //计算月薪总额函数 {return quantity *wagePerPiece; }

//SALEBOSS.CPP

//定义销售经理类SaleBoss的成员函数 #include #include #include \ #include \ #include \

SaleBoss::SaleBoss( ) //构造函数

{ strcpy(EmpKind, \销售经理\ //职工种别 TotalMounthPay=earnings(); }

float SaleBoss::earnings( ) //计算月薪总额函数 {return Boss::getMouthSalary( )+commission*quantity; }

//EMPMAIN.CPP

//类Employee层次结构的测试程序 #include #include #include #include #include #include \ #include \ #include \ #include \ #include \ #include \

void inputinfo( ); //输入职工信息

50

本文来源：https://www.bwwdw.com/article/jp4r.html