数据结构第4章作业

第4章串作业

1 一个字符串中（任意连续字符组成的子序列）称为该串的子串。

2 空串与空格串的区别在于（空串的长度为0，空格串长度不为0 ）。

3 设有两个串p和q，求p在q中首次出现的位置的运算称作（模式匹配）。

4 串时一种特殊的线性表，其特殊性体现在（操作的对象通常为串的整体）。

5 已知3个字符串分别为S=’ab…abcaabcbca…a’,S1=’caab’,S2=’bcb’,利用所学字符串基本运算的函数得到结果串为：

S3=’caabcbca…aca…a’

要求写出得到上述结果串S3所用的函数及执行算法。

i1=index(S,S1,1)

i2=index(S,S2,1)+3;

sub1=substr(S,i1,length(S)-i1+1);

sub2=substr(S,i2,length(S)-i2+1;

S3=concat(sub1, sub2);

6 如果某串的长度小于一个常数，则采用何种存储方式最节省空间？

定长顺序存储

数据结构第1章作业

第1章绪论 一、选择题 1. 算法的计算量的大小称为计算的（）。 A．效率 B. 复杂性 C. 现实性 D. 难度 2. 算法的时间复杂度取决于（） A．问题的规模 B. 待处理数据的初态 C. A和B 3.计算机算法指的是（1），它必须具备（2）这三个特性。 (1) A．计算方法 B. 排序方法 C. 解决问题的步骤序列 D. 调度方法 (2) A．可执行性、可移植性、可扩充性 B. 可执行性、确定性、有穷性 C. 确定性、有穷性、稳定性 D. 易读性、稳定性、安全性 4．一个算法应该是（）。 A．程序 B．问题求解步骤的描述 C．要满足五个基本特性 D．A和C. 5. 下面关于算法说法错误的是（） A．算法最终必须由计算机程序实现 B.为解决某问题的算法同为该问题编写的程序含义是相同的 C. 算法的可行性是指指令不能有二义性 D. 以上几个都是错误的 6. 下面说法错误的是（） (1）算法原地工作的含义是指不需要任何额外的辅助空间 （2）在相同的规模n下，复杂度O(n)的算法在时间上总是优于复杂度O(2n)的算法（3）所谓时间复杂度是指最坏情况下，估算算法执行时间的一个上界 （4）同一个算法，实现语言的级别越高，执行效率就越低 A．(1) B.(1),(2) C.(1),(4) D.(3) 7．从逻辑上可以把数据结构分为（）两大类。 A．动态结构、静态结构 B．顺序结构、链式结构 C．线性结构、非线性结构 D．初等结构、构造型结构 8．以下与数据的存储结构无关的术语是（）。 A．循环队列 B. 链表 C. 哈希表 D. 栈 9．以下数据结构中，哪一个是线性结构（）？ A．广义表 B. 二叉树 C. 稀疏矩阵 D. 串 10．以下那一个术语与数据的存储结构无关？（） A．栈 B. 哈希表 C. 线索树 D. 双向链表 11．在下面的程序段中，对x的赋值语句的频度为（） FOR i:=1 TO n DO FOR j:=1 TO n DO x:=x+1; A． O(2n) B．O(n) C．O(n2) D．O(log2n) 12．程序段 FOR i:=n-1 DOWNTO 1 DO FOR j:=1 TO i DO IF A[j]>A[j+1] THEN A[j]与A[j+1]对换；

数据结构第10章 习题答案

1．下列排序算法中，其中（ D ）是稳定的。 A. 堆排序，冒泡排序 B. 快速排序，堆排序 C. 直接选择排序，归并排序 D. 归并排序，冒泡排序 2．有一组数据（15，9，7，8，20，-1，7，4）用快速排序的划分方法进行一趟划分后数据的排序为 ( A )（按递增序）。 A．下面的B，C，D都不对。 B．9，7，8，4，-1，7，15，20 C．20，15，8，9，7，-1，4，7 D. 9，4，7，8，7，-1，15，20 3.下列排序算法中，在每一趟都能选出一个元素放到其最终位置上，并且其时间性能受数据初始特性影响的是：（ B ）。 A. 直接插入排序 B. 快速排序 C. 直接选择排序 D. 堆排序 4．如果只想得到1000个元素组成的序列中第5个最小元素之前的部分排序的序列，用（ D ）方法最快。 A．起泡排序 B．快速排列 C．Shell排序 D．堆排序 E．简单选择排序 5．从未排序序列中依次取出一个元素与已排序序列中的元素依次进行比较，然后将其放在已排序序列的合适位置，该排序方法称为( A )排序法。 A. 插入 B. 选择 C. 希尔 D. 二路归并 6. 在排序算法中，每次从未排序的记录中挑出最小（或最大）关键码字的记录，加入到已排序记录的末尾，该排序方法是（ A ）。 A. 选择 B. 冒泡 C. 插入 D. 堆 7. 若用冒泡排序方法对序列{10,14,26,29,41,52}从大到小排序，需进行（ C ）次比较。 A. 3 B. 10 C. 15 D. 25 8. 对序列{15，9，7，8，20，-1，4，} 用希尔排序方法排序，经一趟后序列变为{15，-l，4，8，20，9，7}则该次采用的增量是 ( B ) A. l B. 4 C. 3 D. 2 9. 堆排序是（ E ）类排序 A. 插入 B. 交换 C. 归并 D. 基数 E. 选择 10．排序方法有许多种，（1）法从未排序的序列中依次取出元素，与已排序序列（初始时为空）中的元素作比较，将其放入已排序序列的正确位置上；（2）法从未排序的序列中挑选元素，并将其依次放入已排序序列（初始时为空）的一端；交换排序方法是对序列中的元素进行一系列比较，当被比较的两元素逆序时，进行交换；（3）和（4）是基于这类方法的两种排序方法，而（4）是比（3）效率更高的方法；（5）法是基于选择排序的一种排序方法，是完全二叉树结构的一个重要应用。 （1）--（5）: A．选择排序 B．快速排序 C．插入排序 D．起泡排序 E．归并排序 F．shell排序 G．堆排序 H．基数排序 10.1C 5 2A 3D 4B 5G 1．若不考虑基数排序，则在排序过程中，主要进行的两种基本操作是关键字的__ ____和记录的_____。比较,移动 2．分别采用堆排序，快速排序，冒泡排序和归并排序，对初态为有序的表，则最省时间的是_____算法，最费时间的是______算法。冒泡,快速 3. 设用希尔排序对数组{98，36，-9，0，47，23，1，8，10，7}进行排序，给出的步长（也称增量序列）依次是4，2，1则排序需__________趟，写出第一趟结束后，数组中数据的排列次序__________。3,(10,7,-9,0,47,23,1,8,98,36) 4．对给定文件（28，07，39，10，65，14，61，17，50，21）选择第一个元素28进行划分，写出其快速排序第一遍的排序过程。

数据结构第五章 查找 答案

数据结构与算法上机作业第五章查找

一、选择题 1、若构造一棵具有n个结点的二叉排序树，在最坏情况下，其高度不超过 B 。 A. n/2 B. n C. (n+1)/2 D. n+1 2、分别以下列序列构造二叉排序数（二叉查找树），与用其他3个序列所构造的结果不同的是 C ： A. (100, 80, 90, 60, 120, 110, 130) B. (100, 120, 110, 130, 80, 60, 90) C. (100, 60, 80, 90, 120, 110, 130) D. (100, 80, 60, 90, 120, 130, 110) 3、不可能生成下图所示的二叉排序树的关键字的序列是 A 。 A. 4 5 3 1 2 B. 4 2 5 3 1 C. 4 5 2 1 3 D. 4 2 3 1 5 4、在二叉平衡树中插入一个结点造成了不平衡，设最低的不平衡点为A，并已知A的左孩子的平衡因子为0，右孩子的平衡因子为1，则应作 C 型调整使其平衡。 A. LL B. LR C. RL D. RR 5、一棵高度为k的二叉平衡树，其每个非叶结点的平衡因子均为0，则该树共有 C 个结点。 A. 2k-1-1 B. 2k-1+1 C. 2k-1 D. 2k+1 6、具有5层结点的平衡二叉树至少有 A 个结点。 A. 12 B. 11 C. 10 D. 9 7、下面关于B-和B+树的叙述中，不正确的是 C 。 A. B-树和B+树都是平衡的多叉树 B. B-树和B+树都可用于文件的索引结构 C. B-树和B+树都能有效地支持顺序检索

D. B-树和B+树都能有效地支持随机检索 8、下列关于m阶B-树的说法错误的是 D 。 A. 根结点至多有m棵子树 B. 所有叶子结点都在同一层次 C. 非叶结点至少有m/2（m为偶数）或m/2+1(m为奇数)棵子树 D. 根结点中的数据是有序的 9、下面关于哈希查找的说法正确的是 C 。 A. 哈希函数构造得越复杂越好，因为这样随机性好，冲突小 B. 除留余数法是所有哈希函数中最好的 C. 不存在特别好与坏的哈希函数，要视情况而定 D. 若需在哈希表中删去一个元素，不管用何种方法解决冲突都只要简单地将该元素删去即可 10、与其他查找方法相比，散列查找法的特点是 C 。 A. 通过关键字的比较进行查找 B. 通过关键字计算元素的存储地址进行查找 C. 通过关键字计算元素的存储地址并进行一定的比较进行查找 D. 以上都不是 11、有一组关键字{8, 24, 16, 3, 12, 32, 51}，采用除留余数法构造散列函数：H(key)=key mod 12，则将发生次冲突。 A. 3 B. 4 C. 5 D. 6 12、有一个结点的关键字为83，采用移位叠加法生成4位散列地址，则生成的地址为 B 。 A. 3482 B. 3583 C. 9018 D. 9019 二、填空题 1、在查找过程中有插入或删除元素操作的，称为动态查找。

数据结构第十章习题课

1．下列排序算法中，其中（）是稳定的。 A. 堆排序，冒泡排序 B. 快速排序，堆排序 C. 直接选择排序，归并排序 D. 归并排序，冒泡排序 2．若需在O(nlog2n)的时间内完成对数组的排序，且要求排序是稳定的，则可选择的排序方法是（）。 A. 快速排序 B. 堆排序 C. 归并排序 D. 直接插入排序3．排序趟数与序列的原始状态有关的排序方法是( )排序法。 A．插入 B. 选择 C. 冒泡 D. 快速4．对一组数据（84，47，25，15，21）排序，数据的排列次序在排序的过程中 的变化为（1）84 47 25 15 21 （2）15 47 25 84 21 （3）15 21 25 84 47 （4） 15 21 25 47 84 则采用的排序是( )。 A. 选择 B. 冒泡 C. 快速 D. 插入5．对序列{15，9，7，8，20，-1，4}进行排序，进行一趟后数据的排列变为{4，9，-1，8，20，7，15}；则采用的是（）排序。 A. 选择 B. 快速 C. 希尔 D. 冒泡6．若上题的数据经一趟排序后的排列为{9，15，7，8，20，-1，4}，则采用的 是（）排序。 A．选择 B. 堆 C. 直接插入 D. 冒泡 7．在文件“局部有序”或文件长度较小的情况下，最佳内部排序的方法是（）A．直接插入排序B．冒泡排序C．简单选择排序 8．下列排序算法中，（）算法可能会出现下面情况：在最后一趟开始之前，所有元素都不在其最终的位置上。 A. 堆排序 B. 冒泡排序 C. 快速排序 D. 插入排序 9. 下列排序算法中，占用辅助空间最多的是：( ) A. 归并排序 B. 快速排序 C. 希尔排序 D. 堆排序10．用直接插入排序方法对下面四个序列进行排序（由小到大），元素比较次数 最少的是（）。 A．94,32,40,90,80,46,21,69 B．32,40,21,46,69,94,90,80 C．21,32,46,40,80,69,90,94 D．90,69,80,46,21,32,94,40 11. 若用冒泡排序方法对序列{10,14,26,29,41,52}从大到小排序，需进行（）次比较。 A. 3 B. 10 C. 15 D. 25 12．对n个记录的线性表进行快速排序为减少算法的递归深度，以下叙述正确

数据结构课程作业

数据结构课程作业_A 交卷时间：2017-08-09 10:08:51 一、单选题 1. (7分)设有一个二维数组A[m][n]，假设A[0][0]存放位置在644(10)，A[2][2]存放位置在676(10)，每个元素占一个空间，问A[3][3](10)存放在什么位置脚注(10)表示用10进制表示。 A. 688 B. 678 C. 692 D. 696 纠错 得分： 7 知识点：第五章 展开解析 答案 C 解析第五章第二节综合题目 2. (7分)若有18个元素的有序表存放在一维数组A[19]中，第一个元素放A[1]中，现进行二分查找，则查找A［3］的比较序列的下标依次为( ) A. 1，2，3 B. 9，5，2，3 C. 9，5，3 D. 9，4，2，3 纠错 得分： 0 知识点：第九章 展开解析 答案 D 解析第九章第一节有序表的查找

(7分)设某完全无向图中有n个顶点，则该完全无向图中有（）条边。 A. n(n-1)/2 B. n(n-1) C. n2 D. n2-1 纠错 得分： 7 知识点：第七章 展开解析 答案 A 解析第七章第一节综合题目 4. (7分)若在任意一棵二叉树中，有n0个叶子结点，有n2个度为2的结点，则：n0=_____ A. n2+1 B. n2-1 C. n2+2 D. n2-2 纠错 得分： 7 知识点：第六章 展开解析 答案 A 解析第六章第二节二叉树的性质 5. (7分)栈的插入和删除操作在（）进行。 A. 栈顶 B. 栈底 C. 任意位置 D. 指定位置

得分： 7 知识点：第三章 展开解析 答案 A 解析第三章第一节栈的表示和实现 6. (7分)设有序表中有1000个元素，则用二分查找查找元素X最多需要比较（）次。 A. 25 B. 10 C. 7 D. 1 纠错 得分： 7 知识点：第九章 展开解析 答案 B 解析第九章第一节有序表的查找 7. (7分)设某棵二叉树的高度为10，则该二叉树上叶子结点最多有（）。 A. 20 B. 256 C. 512 D. 1024 纠错 得分： 7 知识点：第六章 展开解析 答案 C 解析第六章第六节二叉树的性质

数据结构第五章习题课课案

1、特殊矩阵和稀疏矩阵哪一种压缩存储后会失去随机存取的功能?为什么? 答：后者在采用压缩存储后将会失去随机存储的功能。因为在这种矩阵中，非 零元素的分布是没有规律的，为了压缩存储，就将每一个非零元素的值和它所 在的行、列号作为一个结点存放在一起，这样的结点组成的线性表中叫三元组 表，它已不是简单的向量，所以无法用下标直接存取矩阵中的元素。 2、二维数组M的元素是4个字符（每个字符占一个存储单元）组成的串，行下 标i的范围从0到4，列下标j的范围从0到5，M按行存储时元素M[3][5]的 起始地址与M按列存储时元素（）的起始地址相同。 A、M[2][4] B、M[3][4] C、M[3][5] D、M[4][4] 为第 3、设有一个10阶的对称矩阵A，采用压缩存储方式，以行序为主存储，a 11 的地址为（）。 一元素，其存储地址为1，每个元素占一个地址空间，则a 85 A. 13 B. 33 C. 18 D. 40 4、若对n阶对称矩阵A以行序为主序方式将其下三角形的元素(包括主对角线 （i

数据结构各章作业题目

第一章作业 一、选择题 1.被计算机加工的数据元素不是孤立的，它们彼此之间一般存在某种关系，通常把数据元素之间的 这种关系称为( )。 A. 规则 B. 结构 C. 集合 D. 运算 2.在Data_Structure=(D,S)中，D是( )的有限集合。 A. 数据元素 B. 算法 C. 数据操作 D.数据对象 3.计算机所处理的数据一般具有某种关系，这是指( )之间存在的某种关系。 A. 数据与数据 B. 数据元素与数据元素 C. 元素内数据项与数据项 D. 数据文件内记录与记录 4.顺序存储表示中数据元素之间的逻辑关系是由( )表示的。 A. 指针 B. 逻辑顺序 C. 存储位置 D. 问题上下文 5.链接存储表示中数据元素之间的逻辑关系是由( )表示的。 A. 指针 B. 逻辑顺序 C. 存储位置 D. 问题上下文 6.从逻辑上可将数据结构分为( )。 A. 动态结构和静态结构 B. 紧凑结构和非紧凑结构 C. 内部结构和外部结构 D. 线性结构和非线性结构 7.以下选项属于线性结构的是( )。 A. 广义表 B. 二叉树 C. 串 D. 稀疏数组 8.以下选项属于非线性结构的是( )。 A. 广义表 B. 队列 C. 优先队列 D. 栈 9.以下属于逻辑结构的是( ) A. 顺序表 B. 散列表 C. 有序表 D. 单链表 10.一个完整的算法应该具有( )等特性。 A. 可执行性、可修改性和可维护性 B. 可行性、确定性和有穷性

C. 确定性、有穷性和可靠性 D. 正确性、可读性和有效性 11.若一个问题既可以用迭代方法也可以用递归方法求解，则( )的方法具有更高的时空效率。 A. 迭代 B. 递归 C. 先递归后迭代 D. 先迭代后递归 12.一个递归算法必须包括( ) A. 递归部分 B. 终止条件和递归部分 C. 迭代部分 D. 终止条件和迭代部 分 13.算法的时间复杂度与( )有关。 A. 问题规模 B. 源程序长度 C. 计算机硬件运行速度 D. 编译后执行程序的 质量 二、指出下列各算法的功能并求出其时间复杂度。 (1) int Prime(int n){ int i=2,x=(int)sqrt(n); //sqrt(n)为求n的平方根 while(i<=x){ if(n%i==0)break; i++; } if(i>x) return 1; else return 0; } (2) int sum1(int n){ int p=1,s=0; for(int i=1;i<=n;i++){ p*=i;s+=p;

数据结构作业第1章

第1章绪论 1. 填空 （1）（）是数据的基本单位，在计算机程序中通常作为一个整体进行考虑和处理。 （2）（）是数据的最小单位，（）是讨论数据结构时涉及的最小数据单位。 （3）从逻辑关系上讲，数据结构主要分为（）、（）、（）和（）。 （4）数据的存储结构主要有（）和（）两种基本方法，不论哪种存储结构，都要存储两方面的内容：（）和（）。 （5）算法具有五个特性，分别是（）、（）、（）、（）、（）。 （6）在一般情况下，一个算法的时间复杂度是（）的函数。 （7）设待处理问题的规模为n，若一个算法的时间复杂度为一个常数，则表示成数量级的形式为（），若为n*log25n，则表示成数量级的形式为（）。 2. 选择题 ⑴顺序存储结构中数据元素之间的逻辑关系是由（）表示的，链式存储结构中的数据元素之间的逻辑关系是由（）表示的。 A 线性结构 B 非线性结构 C 存储位置 D 指针 ⑵假设有如下遗产继承规则：丈夫和妻子可以相互继承遗产；子女可以继承父亲或母亲的遗产；子女间不能相互继承。则表示该遗产继承关系的最合适的数据结构应该是（）。 A 树 B 图 C 线性表 D 集合 ⑶算法指的是（）。 A 对特定问题求解步骤的一种描述，是指令的有限序列。 B 计算机程序 C 解决问题的计算方法 D 数据处理 ⑷下面（）不是算法所必须具备的特性。 A 有穷性 B 确切性 C 高效性 D 可行性 ⑸算法分析的目的是（），算法分析的两个主要方面是（）。 A 找出数据结构的合理性 B 研究算法中输入和输出的关系 C 分析算法的效率以求改进 D 分析算法的易读性和文档性 E 空间性能和时间性能 F 正确性和简明性 G 可读性和文档性H 数据复杂性和程序复杂性 3. 判断题 （1）算法的时间复杂度都要通过算法中的基本语句的执行次数来确定。 （2）每种数据结构都具备三个基本操作：插入、删除和查找。 （3）逻辑结构与数据元素本身的内容和形式无关。 （4）基于某种逻辑结构之上的基本操作，其实现是唯一的。 4. 分析以下各程序段，并用大O记号表示其执行时间。

数据结构作业系统_第五章答案

数据结构作业系统_第五章答案 5.21④假设稀疏矩阵A和B均以三元组表作为存储结构。 试写出矩阵相加的算法，另设三元组表C存放结果矩阵。 要求实现以下函数： Status AddTSM(TSMatrix A,TSMatrix B,TSMatrix &C); /* 三元组表示的稀疏矩阵加法: C=A+B */ 稀疏矩阵的三元组顺序表类型TSMatrix的定义： #define MAXSIZE 20 // 非零元个数的最大值 typedef struct { int i,j; // 行下标,列下标 ElemType e; // 非零元素值 }Triple; typedef struct { Triple data[MAXSIZE+1]; // 非零元三元组表,data[0]未用 int mu,nu,tu; // 矩阵的行数、列数和非零元个数 }TSMatrix; Status AddTSM(TSMatrix A,TSMatrix B,TSMatrix &C) /* 三元组表示的稀疏矩阵加法: C=A+B */ { int k=1,n=1,p=1; ElemType ce; if(A.mu!=B.mu||A.nu!=B.nu)return ERROR; while(k<=A.tu&&n<=B.tu) {

if(A.data[k].i==B.data[n].i&&A.data[k].j==B.data[n].j) { ce=A.data[k].e+B.data[n].e; if(ce) { C.data[p].i=A.data[k].i; C.data[p].j=A.data[k].j; C.data[p].e=ce; p++; //printf("%d,,%d ",ce,C.data[p-1].e); } k++;n++; } else if(A.data[k].iA.tu) while(n<=B.tu)

数据结构--重修作业题

第一章绪论 一、选择题 3.在数据结构中，从逻辑上可以把数据结构分成（） （A）动态结构和静态结构（B）紧凑结构和非紧凑结构 （C）线性结构和非线性结构（D）内部结构和外部结构 5.算法分析的目的是（）。 （A）找出数据结构的合理性（B）研究算法中的输入和输出的关系 （C）分析算法的效率以求改进（D）分析算法的易懂性和文档性 二、判断题 1.数据的机内表示称为数据的存储结构。（） 2.算法就是程序。（） 5.算法的时间复杂度取决于问题的规模和待处理数据的初态。（） 三、填空题 1.数据逻辑结构包括________、________、_________ 和_________四种类型,其中树形结构和图形结构合称为_____。 2.在线性结构中,第一个结点____前驱结点,其余每个结点有且只有______个前驱结点；最后一个结点______后续结点,其余每个结点有且只有_______个后续结点。 3.在树形结构中,树根结点没有_______结点,其余每个结点有且只有_______个前驱结点；叶子结点没有________结点,其余每个结点的后续结点可以 _________。 4.在图形结构中,每个结点的前驱结点数和后续结点数可以_________。 5.线性结构中元素之间存在________关系,树形结构中元素之间存在______关系,图形结构中元素之间存在_______关系。 8.链式存储结构与顺序存储结构相比较,主要优点是 ________________________________。 9.设有一批数据元素,为了最快的存储某元素,数据结构宜用_________结构,为了方便插入一个元素,数据结构宜用____________结构。

第二章数据结构习题作业

2.6．数据的存储结构主要有哪两种？它们之间的本质区别是什么？ 答：主要有：顺序存储结构和链式存储结构两种。 区别: 顺序存储结构是借助元素在存储器的相对位置来表示数据间的逻辑关系，而链式存储结构是借助指针来表示数据间的逻辑关系。 2.7 设数据结构的集合为D={d1,d2,d3,d4,d5},试指出下列各关系R所对应的数据结构B=(D,R)中哪些是线性结构，哪些是非线性结构。 （1）R={(d1,d2),(d2,d4),(d4,d2),(d2,d5),(d4,d1)}; ( 2 ) R={(d5,d4),(d4,d3),(d3,d1),(d1,d2)}; ( 3 ) R={(di,di+1)|i=4,3,2,1}; ( 4 ) R={(di,dj)|i

2.〉链表：扩展性强，易于删除，添加；内存中地址非连续；长度可以实时变化；适用于需要进行大量增添或删除元素操作而对访问元素无要求的程序。 （2）缺点 顺序表：插入，删除操作不方便；扩展性弱；不易删除，添加。 链表：不易于查询，索引慢。 （3）顺序表和链表的优缺点是互相补充的关系。 2.17 试比较单向链表与双向链表的优缺点。 答：（1）优点 单向链表：耗存储空间小； 双向链表：可以从任何一点开始进行访问; （2）缺点： 单向链表：访问时必须从头开始，耗时。 双向链表：耗存储空间大。 （3）两者为互补关系 2.22 CQ[0:10]为一循环队列，初态front=rear=1,画出下列操作后队的头，尾指示器状态： （1）d,e,h,g,入队； （2）d,e出队； （3）I,j,k,l,m入队； （4）b出队；

数据结构第一章课后习题与答案

第 1 章 绪 论 (2005-07-14) - 第 1 章 绪 论 课后习题讲解 1. 填空 ⑴（ ）是数据的基本单位，在计算机程序中通常作为一个整体进行考虑和处理。 【解答】数据元素 ⑵（ ）是数据的最小单位，（ ）是讨论数据结构时涉及的最小数据单位。 【解答】数据项，数据元素 【分析】数据结构指的是数据元素以及数据元素之间的关系。 ⑶ 从逻辑关系上讲，数据结构主要分为（ ）、（ ）、（ ）和（ ）。 【解答】集合，线性结构，树结构，图结构 ⑷ 数据的存储结构主要有（ ）和（ ）两种基本方法，不论哪种存储结构，都要存储两方面的内容：（ ）和（）。 【解答】顺序存储结构，链接存储结构，数据元素，数据元素之间的关系 ⑸ 算法具有五个特性，分别是（ ）、（ ）、（ ）、（ ）、（ ）。 【解答】有零个或多个输入，有一个或多个输出，有穷性，确定性，可行性 ⑹ 算法的描述方法通常有（ ）、（ ）、（ ）和（ ）四种，其中，（ ）被称为算法语言。 【解答】自然语言，程序设计语言，流程图，伪代码，伪代码 ⑺ 在一般情况下，一个算法的时间复杂度是（ ）的函数。 【解答】问题规模 ⑻ 设待处理问题的规模为n，若一个算法的时间复杂度为一个常数，则表示成数量级的形式为（ ），若为 n*log25n，则表示成数量级的形式为（ ）。 【解答】Ο(1)，Ο(nlog2n) 【分析】用大O记号表示算法的时间复杂度，需要将低次幂去掉，将最高次幂的系数去掉。

2. 选择题 ⑴ 顺序存储结构中数据元素之间的逻辑关系是由（ ）表示的，链接存储结构中的数据元素之间的逻辑关系是由（ ）表示的。 A 线性结构 B 非线性结构 C 存储位置 D 指针 【解答】C，D 【分析】顺序存储结构就是用一维数组存储数据结构中的数据元素，其逻辑关系由存储位置（即元素在数组中的下标）表示；链接存储结构中一个数据元素对应链表中的一个结点，元素之间的逻辑关系由结点中的指针表示。 ⑵ 假设有如下遗产继承规则：丈夫和妻子可以相互继承遗产；子女可以继承父亲或母亲的遗产；子女间不能相互继承。则表示该遗产继承关系的最合适的数据结构应该是（ ）。 A 树 B 图 C 线性表 D 集合 【解答】B 【分析】将丈夫、妻子和子女分别作为数据元素，根据题意画出逻辑结构图。 ⑶ 算法指的是（ ）。 A 对特定问题求解步骤的一种描述，是指令的有限序列。 B 计算机程序 C 解决问题的计算方法 D 数据处理 【解答】A 【分析】计算机程序是对算法的具体实现；简单地说，算法是解决问题的方法；数据处理是通过算法完成的。所以，只有A是算法的准确定义。 ⑷ 下面（ ）不是算法所必须具备的特性。 A 有穷性 B 确切性 C 高效性 D 可行性 【解答】C 【分析】高效性是好算法应具备的特性。 ⑸ 算法分析的目的是（ ），算法分析的两个主要方面是（ ）。 A 找出数据结构的合理性 B 研究算法中输入和输出的关系 C 分析算法的效率以求改进 D 分析算法的易读性和文档性 E 空间性能和时间性能 F 正确性和简明性 G 可读性和文档性 H 数据复杂性和程序复杂性

数据结构第五章图习题教学文案

05 图 【单选题】 1. 设无向图G 中有五个顶点，各顶点的度分别为2、4、3、1、2，则G 中边数为（C ）。 Ａ、4条 Ｂ、5条 Ｃ、6条 Ｄ、无法确定 2. 含n 个顶点的无向完全图有（D ）条边；含n 个顶点的有向图最多有（C ）条弧；含n 个顶点的有向强连通图最多有（C ）条弧；含n 个顶点的有向强连通图最少有（Ｆ）条弧；设无向图中有n 个顶点，则要接通全部顶点至少需（G ）条边。 A 、n 2 B 、n(n+1) C 、n(n-1) D 、n(n-1)/2 E 、n+1 F 、n G 、n-1 3. 对下图从顶点a 出发进行深度优先遍历，则（A ）是可能得到的遍历序列。 A 、acfgdeb B 、abcdefg C 、acdgbef D 、abefgcd 对下图从顶点a 出发进行广度优先遍历，则（D ）是不可能得到的遍历序列。 A 、abcdefg B 、acdbfge C 、abdcegf D 、 adcbgef 4. 设图G 的邻接矩阵A=???? ??????010101010，则G 中共有（C ）个顶点；若G 为有向图，则G 中共有（D ）条弧；若G 为无向图，则G 中共有（B ）条边。 A 、1 B 、2 C 、3 D 、4 E 、5 F 、9 G 、以上答案都不对 5. 含n 个顶点的图，最少有（B ）个连通分量，最多有（D ）个连通分量。 A 、0 B 、1 C 、n-1 D 、n 6. 用邻接表存储图所用的空间大小（A ）。 A 、与图的顶点数和边数都有关 B 、只与图的边数有关 C 、只与图的顶点数有关 D 、与边数的平方有关 7. n 个顶点的无向图的邻接表最多有（B ）个表结点。 A 、n 2 B 、n(n-1) C 、n(n+1) D 、n(n-1)/2 8. 无向图G=(V ,E)，其中：V={a,b,c,d,e,f}，E={(a,b),(a,e),(a,c),(b,e),(c,f),(f,d),(e,d)}，对该图进行深度优先遍历，得到的顶点序列正确的是（D ）。 A 、a,b,e,c,d,f B 、a,c,f,e,b,d C 、a,e,b,c,f,d D 、a,e,d,f,c,b 9. 图的BFS 生成树的树高比DFS 生成树的树高（A ）。 A 、小或相等 B 、小 C 、大或相等 D 、大

数据结构第十章习题课

1 .下列排序算法中，其中（ ）是稳定的。 A.堆排序，冒泡排序 B.快速排序，堆排序 C.直接选择排序，归并排序 D.归并排序，冒泡排序 2.若需在O （nlog 2n ）的时间内完成对数组的排序，且要求排序是稳定的，贝U 可选 择的排序方法是（ ）。 A.快速排序 B.堆排序 C.归并排序 D.直接插入排序 3.排序趟数与序列的原始状态有关的排序方法是（）排序法。 A .插入 B.选择 C.冒泡 D.快速 15， 21）排序，数据的排列次序在排序的过程中 （2） 15 47 25 84 21 （3） 15 21 25 84 47 （4） 15 21 25 47 84则采用的排序是 （ ） A.选择 B.冒泡 5. 对序列｛15，9，7，8，20，-1, 4｝进行排序，进行一趟后数据的排列变为｛4, 9, -1，8，20，7，15｝;则采用的是（ A.选择 B.快速 6. 若上题的数据经一趟排序后的排列为 ｛9，15，7，8, 是（ ）排序。 A .选择 B.堆 C.直接插入 D.冒泡 7. 在文件“局部有序”或文件长度较小的情况下，最佳内部排序的方法是（ ） A .直接插入排序 B .冒泡排序 C .简单选择排序 8. 下列排序算法中，（ ）算法可能会出现下面情况：在最后一趟开始之前, 所有元素都不在其最终的位置上。 A.堆排序 B.冒泡排序 C.快速排序 D.插入排序 9. 下列排序算法中，占用辅助空间最多的是: A.归并排序 B.快速排序 10. 用直接插入排序方法对下面四个 序列进行排序（由小到大），元素比较次数 最少的是（ ）O A . 94,32,40,90,80,46,21,69 B . 32,40,21,46,69,94,90,80 C . 21,32,46,40,80,69,90,94 D . 90,69,80,46,21,32,94,40 11. 若用冒泡排序方法对序列｛10,14,26,29,41,52｝从大到小排序，需进行 （ ） 4.对一组数据（84，47，25, 的变化为（1） 84 47 25 15 21 C.快速 D.插入 ）排序。 C.希尔 D.冒泡 20, -1 , 4｝，则采用的 C.希尔排序 D.堆排序

数据结构作业及答案

第一章绪论 一、选择题 1.数据结构是一门研究非数值计算的程序设计问题中计算机的1以及它们之间的2和运算等的学科。1 A.数据元素 B.计算方法 C.逻辑存储 D.数据映像 2 A.结构 B.关系 C.运算 D.算法 2.数据结构被形式地定义为(K, R)，其中K是1的有限集，R是K上的2有限集。 1 A.算法 B.数据元素 C.数据操作 D.逻辑结构 2 A.操作 B.映像 C.存储 D.关系 3.在数据结构中，从逻辑上可以把数据结构分成。 A.动态结构和静态结构 B.紧凑结构和非紧凑结构 C.线性结构和非线性结构 D.内部结构和外部结构 4.线性结构的顺序存储结构是一种1的存储结构，线性表的链式存储结构是一种2的存储结构。A.随机存取 B.顺序存取 C.索引存取 D.散列存取 5.算法分析的目的是1，算法分析的两个主要方面其一是指2，其二是指正确性和简单性。1 A.找出数据结构的合理性 B.研究算法中的输入和输出的关系 C.分析算法的效率以求改进 D.分析算法的易懂性和文档性 2 A.空间复杂度和时间复杂度 B.研究算法中的输入和输出的关系 C.可读性和文档性 D.数据复杂性和程序复杂性k 6.计算机算法指的是1，它必须具备输入、输出和2等5个特性。 1 A.计算方法 B.排序方法 C.解决问题的有限运算序列 D.调度方法 2 A.可执行性、可移植性和可扩充性 B.可行性、确定性和有穷性 C.确定性、有穷性和稳定性 D.易读性、稳定性和安全性 7.线性表的逻辑顺序与存储顺序总是一致的，这种说法。A.正确 B.不正确 8线性表若采用链式存储结构时，要求内存中可用存储单元的地址。 A.必须连续的 B.部分地址必须连续的 C.一定是不续的D连续不连续都可以 9.以下的叙述中，正确的是。A.线性表的存储结构优于链式存储结构 B.二维数组是其数据元素为线性表的线性表C.栈的操作方式是先进先出D.队列的操作方式是先进后出10.每种数据结构都具备三个基本运算：插入、删除和查找，这种说法。A.正确B.不正确 二、填空题1.数据逻辑结构包括三种类型、和，树形结构和图形结构合称为。2.在线性结构中，第一个结点前驱结点，其余每个结点有且只有个前驱结点；最后一个结点后续结点，其余每个结点有且只有个后续结点。3.算法的五个重要特性是、、、、。 4.下面程序段的时间复杂度是。 for( i = 0; i < n; i++) for( j = 0; j < m; j++) A[i][j] = 0; 5.下面程序段的时间复杂度是。 i = s = 0; while ( s < n) { i ++; /* i = i +1*/ s += i; /* s = s + i*/ } 6.下面程序段的时间复杂度是。 s = 0; for( i = 0; i < n; i++) for( j = 0; j < n; j++) s += B[i][j]; sum = s; 7.下面程序段的时间复杂度是。 i = 1; while ( i <= n ) i = i * 3;

数据结构作业

数据结构习题 第一章绪论 1.6 在程序设计中，常用下列三种不同的出错处理方式： 1) 用exit语句终止执行并报告错误； 2) 以函数的返回值区别正确返回或错误返回； 3) 设置一个整形变量的函数参数以区别正确返回或某种错误返回。 试讨论这三种方法各自的优缺点。 1.7 在程序设计中，可采用下列三种方法实现输出和输入： 1) 通过scanf和printf语句； 2) 通过函数的参数显示传递； 3) 通过全局变量隐式传递。 试讨论这三种方法的优缺点。 1.8 设n为正整数。试确定下列各程序段中前置以记号@的语句的频度： 5) for (i = 1; i <= n; i++ ) { for (j = 1; j <= i; j++) { for (k = 1; k <= j; k++) { @ x += delta; } } } 答案：n*(n+1)*(n+2) =1+（1+2）+（1+2+3）+...+(1+2+3+...+n) =∑ =+ n i i i 1 2 / )1 ( * =1/2*∑ =+ n i i i i 1 * =n*(n+1)*(2n+1)/12 +n*(n+1)/4 =n*(n+1)*(n+2)/6 7) x = n; //n是不小于1的常数 y = 0; while (x >= (y + 1) * (y + 1)) { @ y++; } 答案：n向下取整 8) x = 91; y = 100; while (y > 0) { @ if (x > 100) { x -= 10; y--;}

else { x++; } } 答案：if 执行次数为1100， if 判断内部执行为100次 1.19 试编写算法，计算i!·2i （i = 0, 1, …, n-1）的值并分别存入数组a[arrsize]的各个分量中。假设计算机中允许的整数最大值为MAXINT ，则当n > arrsize 或对某个k （0 ≤ k ≤ n-1）使k!·2k > MAXINT 时，应按出错处理。注意选择你认为较好的出错处理方法。 1.20 试编写算法求一元多项式∑==n i i i x a x 0n )(P 的值P n (x 0)，并确定算法中每一语句的执行 次数和整个算法的时间复杂度。注意选择你认为较好的输入和输出方法。本题的输入为a i （i=0, 1, …, n ）、x 0和n ，输出为P n (x 0)。

数据结构第九、十章 作业答案

第九章 查找 一、填空题 1. 在数据的存放无规律而言的线性表中进行检索的最佳方法是 顺序查找（线性查找） 。 2. 线性有序表（a 1，a 2，a 3，…，a 256)是从小到大排列的，对一个给定的值k ，用二分法检索 表中与k 相等的元素，在查找不成功的情况下，最多需要检索 8 次。设有100个结点，用二分法查找时，最大比较次数是 7 。 3. 假设在有序线性表a[1..20]上进行折半查找，则比较一次查找成功的结点数为1；比较两次查找成功的结点数为 2 ；比较四次查找成功的结点数为 8 ,其下标从小到大依次是1,3,6,8,11,13,16,19______，平均查找长度为 3.7 。 解：显然，平均查找长度＝O （log 2n ）<5次（25）。但具体是多少次，则不应当按照公式 )1(log 12++=n n n ASL 来计算（即（21×log 221）/20＝4.6次并不正确！）。因为这是在假设n ＝2m -1 的情况下推导出来的公式。应当用穷举法罗列： 全部元素的查找次数为＝（1＋2×2＋4×3＋8×4＋5×5）＝74； ASL ＝74/20=3.7 ！！！ 4．折半查找有序表（4，6，12，20，28，38，50，70，88，100），若查找表中元素20，它 将依次与表中元素 28，6，12，20 比较大小。 5. 在各种查找方法中，平均查找长度与结点个数n 无关的查找方法是 散列查找 。 6. 散列法存储的基本思想是由 关键字的值 决定数据的存储地址。 7. 有一个表长为m 的散列表，初始状态为空，现将n （n