数据结构多少章

第四章 串

一、选择题

1．下面关于串的的叙述中，哪一个是不正确的？（ ）【北方交通大学 2001 一、5（2分）】

A．串是字符的有限序列 B．空串是由空格构成的串

C．模式匹配是串的一种重要运算 D．串既可以采用顺序存储，也可以采用链式存储 2 若串S1=‘ABCDEFG’, S2=‘9898’ ,S3=‘###’,S4=‘012345’,执行

concat(replace(S1,substr(S1,length(S2),length(S3)),S3),substr(S4,index(S2,‘8’),length(S2))) 其结果为（ ）【北方交通大学 1999 一、5 （25/7分）】

A．ABC###G0123 B．ABCD###2345 C．ABC###G2345 D．ABC###2345 E．ABC###G1234 F．ABCD###1234 G．ABC###01234

3．设有两个串p和q，其中q是p的子串，求q在p中首次出现的位置的算法称为（ ）

A．求子串 B．联接 C．匹配 D．求串长 【北京邮电大学

第1章 绪论

一、选择题

1. 算法的计算量的大小称为计算的（ ）。

A．效率 B. 复杂性 C. 现实性 D. 难度 2. 一个算法应该是（ ）。

A．程序 B．问题求解步骤的描述 C．要满足五个基本特性 D．A和C. 3．从逻辑上可以把数据结构分为（ ）两大类。

A．动态结构、静态结构 B．顺序结构、链式结构 C．线性结构、非线性结构 D．初等结构、构造型结构 二、判断题

1. 数据元素是数据的最小单位。( )

2. 数据的逻辑结构是指数据的各数据项之间的逻辑关系；( ) 3．算法的优劣与算法描述语言无关，但与所用计算机有关。( ) 4．健壮的算法不会因非法的输入数据而出现莫名其妙的状态。( )

5. 算法可以用不同的语言描述，如果用C 语言来描述，则算法实际上就是程序了。( ) 6．顺序存储方式的优点是存储密度大，且插入、删除运算效率高。( ) 三、填空

1．数据的物理结构包括 的表示和 的表示。

2. 对于给定的n个元素,可以构造

第五章 练习

1. 假设一个15阶的上三角矩阵A按行优先顺序压缩存储在一维数组B中，则非零元素

A[9,9]在B中的存储位置k=_______。（注：矩阵元素下标从1开始）。

2. 三维数组a[4][5][6](下标从0开始计，a有4*5*6个元素），每个元素的长度是2，则a[2][3][4]

的地址是_______。(设a[0][0][0]的地址是1000,数据以行为主序方式存储)。

3. 假设按低下标优先存储整数数组A[9][3][5][8]时，第一个元素的字节地址是100，每个整数占四个字节。问下列元素的存储地址是什么？ （1）a0000 (2)a1111 (3)a3125 (4) a8247

4. 按高下标优先存储方式（最右的下标为主序），顺序列出数组A[2][2][3][3]中所有元素

aijkl,列出aijkl的序列。 5. 广义表运算式HEAD(TAIL(((a,b,c),(x,y,z))))的结果是_______。 6. 求下列广义表操作的结果 GetHead 【(p,h,w)】 GetTail 【(b,k,p,h)】 GetHead 【((a,b),(c,d))】 GetTa

第五章 练习

1. 假设一个15阶的上三角矩阵A按行优先顺序压缩存储在一维数组B中，则非零元素

A[9,9]在B中的存储位置k=_______。（注：矩阵元素下标从1开始）。

2. 三维数组a[4][5][6](下标从0开始计，a有4*5*6个元素），每个元素的长度是2，则a[2][3][4]

的地址是_______。(设a[0][0][0]的地址是1000,数据以行为主序方式存储)。

3. 假设按低下标优先存储整数数组A[9][3][5][8]时，第一个元素的字节地址是100，每个整数占四个字节。问下列元素的存储地址是什么？ （1）a0000 (2)a1111 (3)a3125 (4) a8247

4. 按高下标优先存储方式（最右的下标为主序），顺序列出数组A[2][2][3][3]中所有元素

aijkl,列出aijkl的序列。 5. 广义表运算式HEAD(TAIL(((a,b,c),(x,y,z))))的结果是_______。 6. 求下列广义表操作的结果 GetHead 【(p,h,w)】 GetTail 【(b,k,p,h)】 GetHead 【((a,b),(c,d))】 GetTa

第10

章 排序

一、选择题

1．某内排序方法的稳定性是指( )。 【南京理工大学 1997 一、10（2分）】

A．该排序算法不允许有相同的关键字记录 B．该排序算法允许有相同的关键字

记录

C．平均时间为0（n log n）的排序方法 D．以上都不对 2．下面给出的四种排序法中( )排序法是不稳定性排序法。【北京航空航天大学 1999 一、10 （2分）】

A. 插入 B. 冒泡 C. 二路归并 D. 堆积 3．下列排序算法中，其中（ ）是稳定的。 【福州大学 1998 一、3 (2分)】 A. 堆排序，冒泡排序 B. 快速排序，堆排序 C. 直接选择排序，归并排序 D. 归并排序，冒泡排序 4．稳定的排序方法是（ ） 【北方交通大学 2000 二、3（2分）】

A．直接插入排序和快速排序 B．折半插入排序和起泡排序

C．简单选择排序和四路归并排序 D．树形选择排序和shell排序

5．下列排序

第3章 数据结构

3．1数据结构的基本概念

一、 课后部分习题答案 3-1 什么是算法？

解答：算法是在有限步骤内求解某一问题所使用的一组定义明确的规则。通俗点说，就是计算机解题的过程。在这个过程中，无论是形成解题思路还是编写程序，都是在实施某种算法。

二、 部分例题及解题思路 ? 选择题

1. 数据结构是指（ ）。

A.数据元素的组织形式 B.数据类型 C.数据存储结构 D.数据定义

2. 数据在计算机存储器内表示时，物理地址与逻辑地址不相同的，称之为（ ）。

A.存储结构 B.逻辑结构 C.链式存储结构 D.顺序存储结构 3. 树形结构是数据元素之间存在一种（ ）。

A.一对一关系 B.多对多关系 C.多对一关系 D.一对多关系

4. 设语句x++的时间是单位时间，则以下语句的时间复杂度为（ ）。

for(i=1; i<=n; i++) for(j=i; j<=n; j++) x++;

A.O(1)

B.O(n)

2 C.O(n)

D.O(n)

35. 算法分析的目的是（1），算法分析的两个主要方面是（2）。

（1） A.找出数据结构的合理性 B.研究算法中的输入和输出关系

C.分析算法的效率以求改进

数据结构答案

第 6 章 图

2005-07-14

第 6 章 图

课后习题讲解

1. 填空题

⑴ 设无向图G中顶点数为n，则图G至少有（ ）条边，至多有（ ）条边；若G为有向图，则至少有（ ）条边，至多有（ ）条边。 【解答】0，n(n-1)/2，0，n(n-1)

【分析】图的顶点集合是有穷非空的，而边集可以是空集；边数达到最多的图称为完全图，在完全图中，任意两个顶点之间都存在边。

⑵ 任何连通图的连通分量只有一个，即是（ ）。 【解答】其自身

⑶ 图的存储结构主要有两种，分别是（ ）和（ ）。 【解答】邻接矩阵，邻接表

【分析】这是最常用的两种存储结构，此外，还有十字链表、邻接多重表、边集数组等。 ⑷ 已知无向图G的顶点数为n，边数为e，其邻接表表示的空间复杂度为（ ）。 【解答】Ｏ(n+e)

【分析】在无向图的邻接表中，顶点表有n个结点，边表有2e个结点，共有n+2e个结点，其空间复杂度为Ｏ(n+2e)=Ｏ(n+e)。

⑸ 已知一个有向图的邻接矩阵表示，计算第j个顶点的入度的方法是（ ）。 【解答】求第j列的所有元素之和

⑹ 有向图G用邻接矩阵A[n][n]存储，其第i行的所有元素之和等于顶点i的（ ）。 【解答】出度

⑺ 图的深度优先遍历类似于树的（ ）遍历，它

《数据结构(C语言描述)》

21世纪高等院校规划教材 数据结构(C语言描述)

ISDN 7-5084-3301-7 斯庆巴拉 主编 中国水利水电出版社

《数据结构(C语言描述)》

第一章 学习数据结构课程的意义学习重点 掌握学习本课程的意义 掌握本课程的主体框架和讨论范围 掌握如何对算法进行描述和分析

《数据结构(C语言描述)》

引入：一般情况下，用计算机解决一 个实际问题时，都是先对具体问题抽 象，建立问题的求解模型，然后设计 相应的算法，编写程序并上机调试， 最后解决问题。

《数据结构(C语言描述)》

1.1 实例：高校选修课程管理 1.2 数据结构的主要内容 1.3 算法和算法分析

本章总结

《数据结构(C语言描述)》

1.1 实例：高校选修课程管理1.1.1 问题描述 1.1.2 问题的分析 1.1.3 学习本课程的意义

《数据结构(C语言描述)》

1.1.1 问题描述表1-1是一所学校学生选修课程的选 修情况登记表。要求用计算机来完成对 学生选修课程的全程管理。 通常必备的功能有登记，修改、查 询和打印等。在本例中重点完成查询功 能。

《数据结构(C语言描述)》

表1-1 某学校学生选修课程情况登记表选修课程名 学号 姓名 系别 课程名 0

第1章 绪论

一、选择题

1. 算法的计算量的大小称为计算的（ ）。

A．效率 B. 复杂性 C. 现实性 D. 难度 2. 一个算法应该是（ ）。

A．程序 B．问题求解步骤的描述 C．要满足五个基本特性 D．A和C. 3．从逻辑上可以把数据结构分为（ ）两大类。

A．动态结构、静态结构 B．顺序结构、链式结构 C．线性结构、非线性结构 D．初等结构、构造型结构 二、判断题

1. 数据元素是数据的最小单位。( )

2. 数据的逻辑结构是指数据的各数据项之间的逻辑关系；( ) 3．算法的优劣与算法描述语言无关，但与所用计算机有关。( ) 4．健壮的算法不会因非法的输入数据而出现莫名其妙的状态。( )

5. 算法可以用不同的语言描述，如果用C 语言来描述，则算法实际上就是程序了。( ) 6．顺序存储方式的优点是存储密度大，且插入、删除运算效率高。( ) 三、填空

1．数据的物理结构包括 的表示和 的表示。

2. 对于给定的n个元素,可以构造

第10

章 排序

一、选择题

1．某内排序方法的稳定性是指( )。 【南京理工大学 1997 一、10（2分）】

A．该排序算法不允许有相同的关键字记录 B．该排序算法允许有相同的关键字

记录

C．平均时间为0（n log n）的排序方法 D．以上都不对 2．下面给出的四种排序法中( )排序法是不稳定性排序法。【北京航空航天大学 1999 一、10 （2分）】

A. 插入 B. 冒泡 C. 二路归并 D. 堆积 3．下列排序算法中，其中（ ）是稳定的。 【福州大学 1998 一、3 (2分)】 A. 堆排序，冒泡排序 B. 快速排序，堆排序 C. 直接选择排序，归并排序 D. 归并排序，冒泡排序 4．稳定的排序方法是（ ） 【北方交通大学 2000 二、3（2分）】

A．直接插入排序和快速排序 B．折半插入排序和起泡排序

C．简单选择排序和四路归并排序 D．树形选择排序和shell排序

5．下列排序