数据结构课后答案第7章
“数据结构课后答案第7章”相关的资料有哪些?“数据结构课后答案第7章”相关的范文有哪些?怎么写?下面是小编为您精心整理的“数据结构课后答案第7章”相关范文大全或资料大全,欢迎大家分享。
数据结构第7章 图习题
第7章 图
一、单项选择题
1.在一个无向图G中,所有顶点的度数之和等于所有边数之和的______倍。 A.l/2 C.2
B.1 D.4
2.在一个有向图中,所有顶点的入度之和等于所有顶点的出度之和的______倍。 A.l/2 C.2
B.1 D.4
3.一个具有n个顶点的无向图最多包含______条边。 A.n C.n-1
B.n+1 D.n(n-1)/2
4.一个具有n个顶点的无向完全图包含______条边。 A.n(n-l) C.n(n-l)/2
B.n(n+l) D.n(n-l)/2
5.一个具有n个顶点的有向完全图包含______条边。 A.n(n-1) C.n(n-l)/2
B.n(n+l) D.n(n+l)/2
6.对于具有n个顶点的图,若采用邻接矩阵表示,则该矩阵的大小为______。A.n C.n-1
7.无向图的邻接矩阵是一个______。 A.对称矩阵 C.上三角矩阵
数据结构答案第6章
数据结构答案
第 6 章 图
2005-07-14
第 6 章 图
课后习题讲解
1. 填空题
⑴ 设无向图G中顶点数为n,则图G至少有( )条边,至多有( )条边;若G为有向图,则至少有( )条边,至多有( )条边。 【解答】0,n(n-1)/2,0,n(n-1)
【分析】图的顶点集合是有穷非空的,而边集可以是空集;边数达到最多的图称为完全图,在完全图中,任意两个顶点之间都存在边。
⑵ 任何连通图的连通分量只有一个,即是( )。 【解答】其自身
⑶ 图的存储结构主要有两种,分别是( )和( )。 【解答】邻接矩阵,邻接表
【分析】这是最常用的两种存储结构,此外,还有十字链表、邻接多重表、边集数组等。 ⑷ 已知无向图G的顶点数为n,边数为e,其邻接表表示的空间复杂度为( )。 【解答】O(n+e)
【分析】在无向图的邻接表中,顶点表有n个结点,边表有2e个结点,共有n+2e个结点,其空间复杂度为O(n+2e)=O(n+e)。
⑸ 已知一个有向图的邻接矩阵表示,计算第j个顶点的入度的方法是( )。 【解答】求第j列的所有元素之和
⑹ 有向图G用邻接矩阵A[n][n]存储,其第i行的所有元素之和等于顶点i的( )。 【解答】出度
⑺ 图的深度优先遍历类似于树的( )遍历,它
数据结构课后答案
杜晓航 杜晓航 杜晓航 杜晓航 杜晓航 杜晓航 杜晓航 杜晓航 杜晓航
第一章 绪论 一、选择题
1. 算法的计算量的大小称为计算的( B )。
A.效率 B. 复杂性 C. 现实性 D. 难度 2. 算法的时间复杂度取决于(C )
A.问题的规模 B. 待处理数据的初态 C. A 和B 3.计算机算法指的是(1C) ,它必须具备(2B) 这三个特性。
(1) A.计算方法 B. 排序方法 C. 解决问题的步骤序列 D. 调度方法 (2) A.可执行性、可移植性、可扩充性 B. 可执行性、确定性、有穷性 C. 确定性、有穷性、稳定性 D. 易读性、稳定性、安全性 4.一个算法应该是( B ) 。
A.程序 B.问题求解步骤的描述 C.要满足五个基本特性 D.A 和C. 5
数据结构历年考研试题第7章图
第七章 图
一、选择题
1.图中有关路径的定义是( )。【北方交通大学 2001 一、24 (2分)】
A.由顶点和相邻顶点序偶构成的边所形成的序列 B.由不同顶点所形成的序列 C.由不同边所形成的序列 D.上述定义都不是 2.设无向图的顶点个数为n,则该图最多有( )条边。
2
A.n-1 B.n(n-1)/2 C. n(n+1)/2 D.0 E.n 【清华大学 1998 一、5 (2分)】【西安电子科技大 1998 一、6 (2分)】 【北京航空航天大学 1999 一、7 (2分)】
3.一个n个顶点的连通无向图,其边的个数至少为( )。【浙江大学 1999 四、4 (4分)】
A.n-1 B.n C.n+1 D.nlogn; 4.要连通具有n个顶点的有向图,至少需要( )条边。【北京航空航天大学 2000 一、6(2分)】
A.n-l B.n C.n+l D.2n 5.n个结点
数据结构课后习题答案1--7 - 图文
习题1
1.解释以下概念:逻辑结构,存储结构,操作,数据结构,数据结构的表示,数据结构的实现,抽象数据类型,算法,算法的时间代价,算法的空间代价,大O表示法。
2.理解以下关系:算法与数据结构的关系;数据结构与抽象数据类型的关系;算法和数据结构与问题求解的关系。
3. 写出下列程序段的平均情况下的时间代价O表示式。 (1) a=b+c; d=a+e (2) sum=0;
for (i=0;i<3;i++) for (j=0;j while (x>=(y+1)*(y+1)) y++; (4) s=0; if(even(n)) for (i=0;i if(x>lO0){ x=x-10; n=n-1; }else x=x+1; } 4.对于给定的n个元素,可以构造出有 , , , 四种。 逻辑结构 的 5.按增长率由小到大的顺序排列下列各函数: 33n2n4nn 2, ( ), ( ), ( ), n, n
数据结构课后习题(第4-5章)
楚雄师院计科系 网络工程2010级 《算法与数据结构》课后习题(第4~5章)
【课后习题】第4章 串 第5章 数组和广义表
网络工程2010级( )班 学号: 姓名:
题 号 得 分 一 二 三 四 总分 一、填空题(每空1分,共30分)
1. 串有三种机内表示方法: 、 和 ,其中前两种属于顺序存储结构,第三种属于 。
2. 若n为主串长度,m为子串长度,则串的BF(朴素)匹配算法最坏的情况下需要比较字符的总次数
为 ,T(n)= 。
3. 是任意串的子串;任意串S都是S本身的子串,除S本身外,S的其他子串称为S的 。 4. 设数组a[1?50, 1?60]的基地址为1000,每个元素占2个存储单元,若以行序为主序顺序存储,则
元素a[32,58]的存储地址为 。
5. 对于数组,比较适于采用 结构够进行存储。 6. 广义表的深度是指____
数据结构课后习题答案(1~5章)
第1章 绪论
5.选择题:CCBDCA
6.试分析下面各程序段的时间复杂度。 (1)O(1) (2)O(m*n) (3)O(n2) (4)O(log3n)
(5)因为x++共执行了n-1+n-2+??+1= n(n-1)/2,所以执行时间为O(n2) (6)O(n)
第2章 线性表
1.选择题
babadbcabdcddac 2.算法设计题
(6)设计一个算法,通过一趟遍历在单链表中确定值最大的结点。 ElemType Max (LinkList L ){
if(L->next==NULL) return NULL;
pmax=L->next; //假定第一个结点中数据具有最大值 p=L->next->next;
while(p != NULL ){//如果下一个结点存在 if(p->data > pmax->data) pmax=p; p=p->next; }
return pmax->data;
(7)设计一个算法,通过遍历一趟,将链表中所有结点的链接方向逆转,仍利用原表的存储空间。
void inverse(LinkList &L) { // 逆置带头结点的单链表 L p=L->next;
数据结构第4章
第四章 串
一、选择题
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. 填空
⑴( )是数据的基本单位,在计算机程序中通常作为一个整体进行考虑和处理。 【解答】数据元素
⑵( )是数据的最小单位,( )是讨论数据结构时涉及的最小数据单位。 【解答】数据项,数据元素
【分析】数据结构指的是数据元素以及数据元素之间的关系。
⑶ 从逻辑关系上讲,数据结构主要分为( )、( )、( )和( )。 【解答】集合,线性结构,树结构,图结构
⑷ 数据的存储结构主要有( )和( )两种基本方法,不论哪种存储结构,都要存储两方面的内容:( )和( )。
【解答】顺序存储结构,链接存储结构,数据元素,数据元素之间的关系 ⑸ 算法具有五个特性,分别是( )、( )、( )、( )、( )。 【解答】有零个或多个输入,有一个或多个输出,有穷性,确定性,可行性
⑹ 算法的描述方法通常有( )、( )、( )和( )四种,其中,( )被称为算法语言。 【解答】自然语言,程序设计语言,流程图,伪代码,伪代码 ⑺ 在一般情况下,一个算法的时间复杂度是( )的函数。 【解答】问题规模
⑻ 设待处理问题的规模为n,若一个算法的时间复杂度为一个常数,则表示成数量级的形式为( ),若为n*log2
数据结构课后习题答案
第1章 绪论
1.简述下列概念:数据、数据元素、数据项、数据对象、数据结构、逻辑结构、存储结构、抽象数据类型。
答案:
数据:是客观事物的符号表示,指所有能输入到计算机中并被计算机程序处理的符号的总称。如数学计算中用到的整数和实数,文本编辑所用到的字符串,多媒体程序处理的图形、图像、声音、动画等通过特殊编码定义后的数据。
数据元素:是数据的基本单位,在计算机中通常作为一个整体进行考虑和处理。在有些情况下,数据元素也称为元素、结点、记录等。数据元素用于完整地描述一个对象,如一个学生记录,树中棋盘的一个格局(状态)、图中的一个顶点等。
数据项:是组成数据元素的、有独立含义的、不可分割的最小单位。例如,学生基本信息表中的学号、姓名、性别等都是数据项。
数据对象:是性质相同的数据元素的集合,是数据的一个子集。例如:整数数据对象是集合N={0,±1,±2,?},字母字符数据对象是集合C={‘A’,‘B’,?,‘Z’, ‘a’,‘b’,?,‘z’},学生基本信息表也可是一个数据对象。
数据结构:是相互之间存在一种或多种特定关系的数据元素的集合。换句话说,数据结构是带“结构”的数据元素的集合,“结构”就是指数据元素之间存在的关系。
逻辑结构:从逻辑关系上