数据结构习题课5
- 格式：ppt
- 大小：193.73 KB
- 文档页数：34
下载文档原格式
合集下载
严蔚敏版数据结构习题及参考答案
习题1一、单项选择题A1.数据结构是指（）。
A.数据元素的组织形式B.数据类型C.数据存储结构D.数据定义C2.数据在计算机存储器内表示时，物理地址与逻辑地址不相同的，称之为（）。
A.存储结构B.逻辑结构C.链式存储结构D.顺序存储结构D3.树形结构是数据元素之间存在一种（）。
A.一对一关系B.多对多关系C.多对一关系D.一对多关系B4.设语句x++的时间是单位时间，则以下语句的时间复杂度为（）。
for(i=1; i<=n; i++)for(j=i; j<=n; j++)x++;A.O(1)B.O(2n)C.O(n)D.O(3n)CA5.算法分析的目的是（1），算法分析的两个主要方面是（2）。
（1） A.找出数据结构的合理性 B.研究算法中的输入和输出关系C.分析算法的效率以求改进D.分析算法的易懂性和文档性（2） A.空间复杂度和时间复杂度 B.正确性和简明性C.可读性和文档性D.数据复杂性和程序复杂性6.计算机算法指的是（1），它具备输入，输出和（2）等五个特性。
（1） A.计算方法 B.排序方法C.解决问题的有限运算序列D.调度方法（2） A.可行性，可移植性和可扩充性 B.可行性，确定性和有穷性C.确定性，有穷性和稳定性D.易读性，稳定性和安全性7.数据在计算机内有链式和顺序两种存储方式，在存储空间使用的灵活性上，链式存储比顺序存储要（）。
A.低B.高C.相同D.不好说8.数据结构作为一门独立的课程出现是在（）年。
A.1946B.1953C.1964D.19689.数据结构只是研究数据的逻辑结构和物理结构，这种观点（）。
A.正确B.错误C.前半句对，后半句错D.前半句错，后半句对10.计算机内部数据处理的基本单位是（）。
A.数据B.数据元素C.数据项D.数据库二、填空题1.数据结构按逻辑结构可分为两大类，分别是______________和_________________。
南邮陈慧南版数据结构课后习题答案
template <class T> void LinkedStack<T>::SetNull() { Node<T> *q; while (top) { q=top->link; delete top; top=q; } }
i k(循环次数) 2*i 1 1 21<n 2 2 22<n 2k-1 n 2k<n 2k<n, k<log2n, k=log2n
划线语句的执行次数为 log2n。O(log2n) (3) for(int i=1;i<=n;i++) for(int j=1;j<=i;j++) for (int k=1;k<=j;k++) x++;
习题三（第50页）
3.1 设A、B、C、D、E五个元素依次进栈(进栈后可立即出栈)，问 能否得到下列序列。若能得到，则给出相应的push和pop序列；若不 能，则说明理由。 1) A,B,C,D,E 2) A,C,E,B,D 3) C,A,B,D,E 4) E,D,C,B,A 答：2）和3）不能。对2）中的E，B，D而言，E最先出栈则表明，此 时B和D均在栈中，由于，B先于D进栈，所以应有D先出栈。同理3） 也不能。 (1)能。 push,pop,push,pop,push,pop,push,pop,push,pop (4)能。 push,push,push,push,push,pop,pop,pop,pop,pop
template <class T> bool LinkedStack<T>::IsEmpty() const { return !top; }
template <class T> bool LinkedStack<T>::IsFull() const { return false; }
数据结构习题和答案及解析
第 1 章绪论课后习题讲解1. 填空⑴（）是数据的基本单位，在计算机程序中通常作为一个整体进行考虑和处理。
【解答】数据元素⑵（）是数据的最小单位，（）是讨论数据结构时涉及的最小数据单位。
【解答】数据项，数据元素【分析】数据结构指的是数据元素以及数据元素之间的关系。
⑶从逻辑关系上讲，数据结构主要分为（）、（）、（）和（）。
【解答】集合，线性结构，树结构，图结构⑷数据的存储结构主要有（）和（）两种基本方法，不论哪种存储结构，都要存储两方面的内容：（）和（）。
【解答】顺序存储结构，链接存储结构，数据元素，数据元素之间的关系⑸算法具有五个特性，分别是（）、（）、（）、（）、（）。
【解答】有零个或多个输入，有一个或多个输出，有穷性，确定性，可行性⑹算法的描述方法通常有（）、（）、（）和（）四种，其中，（）被称为算法语言。
【解答】自然语言，程序设计语言，流程图，伪代码，伪代码⑺在一般情况下，一个算法的时间复杂度是（）的函数。
【解答】问题规模⑻设待处理问题的规模为n，若一个算法的时间复杂度为一个常数，则表示成数量级的形式为（），若为n*log25n，则表示成数量级的形式为（）。
【解答】Ο(1)，Ο(nlog2n)【分析】用大O记号表示算法的时间复杂度，需要将低次幂去掉，将最高次幂的系数去掉。
2. 选择题⑴顺序存储结构中数据元素之间的逻辑关系是由（）表示的，链接存储结构中的数据元素之间的逻辑关系是由（）表示的。
A 线性结构B 非线性结构C 存储位置D 指针【解答】C，D【分析】顺序存储结构就是用一维数组存储数据结构中的数据元素，其逻辑关系由存储位置（即元素在数组中的下标）表示；链接存储结构中一个数据元素对应链表中的一个结点，元素之间的逻辑关系由结点中的指针表示。
⑵假设有如下遗产继承规则：丈夫和妻子可以相互继承遗产；子女可以继承父亲或母亲的遗产；子女间不能相互继承。
则表示该遗产继承关系的最合适的数据结构应该是（）。
数据结构 习题课
算 法
练习5 若已知非空线性链表第一个结点的指针为list， 请 写一个算法， 将该链表中数据域值最小的那个 移到链表的最前端。
list
35 67 18
…
52
10
14
71
…
82
65
q
p
^
list=q;
list
35 67 18
s->link=q->link;
…
52 10 14 71
…
82
65
s
q
^
（删除表中第i元素）
寻找满足条件的元素，即从表中第一个 元素开始到最后那个元素，反复比较相邻的 两个元素是否相同,若相同，删除其中一个， 否则，比较下一对相邻元素。
for(j=i+1; j<n; j++) A[j−1]=A[j]; n--;
（删除表中第i元素）
void DEL( ElemType A[ ], int &n ) { int j, i=0; 比较相邻元素 while(i<n-1) if(A[i]!=A[i+1]) i++; else { for(j=i+1; j<n; j++) A[j−1]=A[j]; n– – ; } } 删除一个元素
list
35 68 59 28
q->link=list;
… q p r r sp qp
r=p; p=p->link;
void REMOVE(LinkList &list ) { 算法 LinkList q=list,s,r; p=list → link; r=list; while (p!=NULL) { if (p→data<q→data) then 寻找值最小结点 { s=r; q=p; } r=p; O (链表长度) p=p→link; // 找到值最小的那个结点 ，地址由q记录 // } if (q!=list) then // 若值最小的结点不是链表最前面那个结点 // { s→link=q→link; q→link=list; list=q ; list s q } } … … 28 39 35 82
《数据结构》第五章习题参考答案
《数据结构》第五章习题参考答案一、判断题（在正确说法的题后括号中打“√”，错误说法的题后括号中打“×”）1、知道一颗树的先序序列和后序序列可唯一确定这颗树。
( ×)2、二叉树的左右子树可任意交换。
（×）3、任何一颗二叉树的叶子节点在先序、中序和后序遍历序列中的相对次序不发生改变。
（√）4、哈夫曼树是带权路径最短的树，路径上权值较大的结点离根较近。
（√）5、用一维数组存储二叉树时，总是以前序遍历顺序存储结点。
( ×)6、完全二叉树中，若一个结点没有左孩子，则它必是叶子结点。
( √)7、一棵树中的叶子数一定等于与其对应的二叉树的叶子数。
（×）8、度为2的树就是二叉树。
（×）二、单项选择题1．具有10个叶结点的二叉树中有（ B ）个度为2的结点。
A．8 B．9 C．10 D．112．树的后根遍历序列等同于该树对应的二叉树的( B )。
A. 先序序列B. 中序序列C. 后序序列3、二叉树的先序遍历和中序遍历如下：先序遍历：EFHIGJK；中序遍历：HFIEJKG 。
该二叉树根的右子树的根是：( C )A. EB. FC. GD. H04、在下述结论中，正确的是（ D ）。
①具有n个结点的完全二叉树的深度k必为┌log2(n+1)┐；②二叉树的度为2；③二叉树的左右子树可任意交换；④一棵深度为k(k≥1)且有2k-1个结点的二叉树称为满二叉树。
A．①②③B．②③④C．①②④D．①④5、某二叉树的后序遍历序列与先序遍历序列正好相反，则该二叉树一定是（ D ）。
A．空或只有一个结点B．完全二叉树C．二叉排序树D．高度等于其结点数三、填空题1、对于一棵具有n个结点的二叉树，对应二叉链接表中指针总数为__2n____个，其中___n-1_____个用于指向孩子结点，___n+1___个指针空闲着。
2、一棵深度为k(k≥1)的满二叉树有_____2k-1______个叶子结点。
数据结构c语言版课后习题答案
数据结构c语言版课后习题答案数据结构是计算机科学中的一个重要概念，它涉及到组织、管理和存储数据的方式，以便可以有效地访问和修改数据。
C语言是一种广泛使用的编程语言，它提供了丰富的数据结构实现方式。
对于学习数据结构的C语言版课程，课后习题是巩固理论知识和提高实践能力的重要手段。
数据结构C语言版课后习题答案1. 单链表的实现在C语言中，单链表是一种常见的线性数据结构。
它由一系列节点组成，每个节点包含数据部分和指向下一个节点的指针。
实现单链表的基本操作通常包括创建链表、插入节点、删除节点、遍历链表等。
答案：- 创建链表：定义一个链表结构体，然后使用动态内存分配为每个节点分配内存。
- 插入节点：根据插入位置，调整前后节点的指针，并将新节点插入到链表中。
- 删除节点：找到要删除的节点，调整其前后节点的指针，然后释放该节点的内存。
- 遍历链表：从头节点开始，使用指针遍历链表，直到达到链表尾部。
2. 二叉树的遍历二叉树是一种特殊的树形数据结构，其中每个节点最多有两个子节点。
二叉树的遍历是数据结构中的一个重要概念，常见的遍历方式有前序遍历、中序遍历、后序遍历和层序遍历。
答案：- 前序遍历：先访问根节点，然后递归遍历左子树，最后递归遍历右子树。
- 中序遍历：先递归遍历左子树，然后访问根节点，最后递归遍历右子树。
- 后序遍历：先递归遍历左子树，然后递归遍历右子树，最后访问根节点。
- 层序遍历：使用队列，按照从上到下，从左到右的顺序访问每个节点。
3. 哈希表的实现哈希表是一种通过哈希函数将键映射到表中一个位置来访问记录的数据结构。
它提供了快速的数据访问能力，但需要处理哈希冲突。
答案：- 哈希函数：设计一个哈希函数，将键映射到哈希表的索引。
- 哈希冲突：使用链地址法、开放地址法或双重哈希法等解决冲突。
- 插入操作：计算键的哈希值，将其插入到对应的哈希桶中。
- 删除操作：找到键对应的哈希桶，删除相应的键值对。
4. 图的表示和遍历图是一种复杂的非线性数据结构，由顶点（节点）和边组成。
数据结构课程习题集第1页共25页
《数据结构》课程习题集第 1 页（共 25 页）一、. 选择题. 1. 算法的计算量的大小称为计算的（）。
A．效率 B. 复杂性 C. 现实性 D. 难度.2. 算法的时间复杂度取决于（）.A．问题的规模 B. 待处理数据的初态 C. A和B 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. 设一个栈的输入序列是 1，2，3，4，5,则下列序列中，是栈的合法输出序列的是（）。
A. 5 1 2 3 4B. 4 5 1 3 2C. 4 3 1 2 5D. 3 2 1 5 4.12. 某堆栈的输入序列为a, b，c ，d,下面的四个序列中，不可能是它的输出序列的是（）。
数据结构(C语言版)(第2版)课后习题答案
数据结构(C语言版)(第2版)课后习题答案数据结构(C语言版)(第2版)课后习题答案1. 简介数据结构是计算机科学领域中非常重要的一门学科，它研究的是数据的组织、存储和管理方式。
本文将针对《数据结构(C语言版)(第2版)》的课后习题提供答案，帮助读者更好地理解和应用数据结构。
2. 第一章: 绪论在第一章中，主要介绍了数据结构的基本概念、分类和基本操作。
以下是部分习题的答案：2.1 习题1习题描述：什么是数据结构？答案：数据结构是指数据对象中元素之间的关系，以及对这些关系进行操作的方法和技术的集合。
2.2 习题2习题描述：数据结构的分类有哪些？答案：数据结构可以分为线性结构和非线性结构。
线性结构包括线性表、栈、队列等；非线性结构包括树、图等。
3. 第二章: 线性表第二章介绍了线性表的定义、分类和实现。
以下是部分习题的答案：3.1 习题1习题描述：什么是线性表？答案：线性表是由n个数据元素a1, a2, ..., an组成的有限序列，其中元素之间存在着一一对应的关系。
3.2 习题2习题描述：线性表的分类有哪些？答案：线性表可以分为顺序表和链表。
顺序表是用一段地址连续的存储单元一次存储线性表的所有元素，而链表是采用链式存储结构，通过每个元素存储其后继元素的地址来实现元素之间的逻辑关系。
4. 第三章: 栈与队列第三章讲解了栈和队列的定义、特性和实现。
以下是部分习题的答案：4.1 习题1习题描述：栈和队列有什么区别？答案：栈是一种后进先出的线性表，只能在表尾进行插入和删除操作；队列是一种先进先出的线性表，只能在表的一端进行插入和删除操作。
4.2 习题2习题描述：栈的应用有哪些？答案：栈在计算机科学中有广泛的应用，如函数的调用和返回、括号匹配、表达式求值等。
5. 第四章: 串第四章讲解了串的定义、模式匹配和实现。
以下是部分习题的答案：5.1 习题1习题描述：什么是串？答案：串是由零个或多个字符组成的有限序列，串中的字符个数称为串的长度。
李春葆《数据结构教程》(C++语言描述)课后习题(第5~8章)【圣才出品】
三、算法设计题 （1）设定二维整数数组 B[0..m-1，0..n-1]的数据在行、列方向上都按从小到大的顺序 排序，且整型变量 x 中的数据在 B 中存在。试设计一个算法，找出一对满足 B[i，j]=x 的 i、 j 值，要求比较次数不超过 m+n。 答： void FindX(int &a,int x) {
（4）一个稀疏矩阵经过压缩后，和直接采用二维数组存储相比会失去______特性。 A．顺序存储 B．随机存取 C．输入／输出 D．以上都不对 【答案】B 【解析】稀疏矩阵可以采用三元组顺序表或是十字链表压缩存储，无论采取哪种方式， 均会使稀疏矩阵不再具有随机存取功能，答案为 B 项。
（5）当 m 行 n 列的稀疏矩阵采用十字链表表示时，其中单链表的个数为______。
（3）简述广义表、数组和线性表之间的异同。 答：一维数组可以看做是一个线性表，类似的也可以采用链式存储和顺序存储结构，但 是在计算机中直接将其视为连续的存储单元集合，二维数组同理可以视为每一个元素都是相 同类型的线性表的线性表，以此类推，任何多维数组都可以看做是线性表，其中每一个数据 元素也是一个线性表，所以说多维数组是线性表的推广。 广义表也是线性表的推广，其一般表示业余线性表相同，只不过其每一个元素既可以是 一个线性表，也可以是一个单个数据元素（原子），而线性表中的每一个元素只能是单个的 数据，这也就使得广义表一般只能用链式结构来表示，二线性表可以用顺序结构和链式结构 表示。
答：下三角矩阵的示意图如下图所示：
4 / 73
圣才电子书
十万种考研考证电子书、题库视频学习平台
a00 a10a11 a20a31a32 aij a 1 ij
在 A[i,j]之前共有 i 行，每行元素个数递增，同时此行有 j 个元素在其之前，因此其前
数据结构习题五(答案)
数据结构习题(5)学号________ 姓名_______ 课堂号(___________)1.选择题1)对N个元素的表做顺序查找时，若查找每个元素的概率相同，则平均查找长度为( A )A．（N+1）/2 B. N/2 C. N D. [（1+N）*N ]/22)下面关于二分查找的叙述正确的是 ( D )A. 表必须有序，表可以顺序方式存储，也可以链表方式存储B. 表必须有序且表中数据必须是整型，实型或字符型C. 表必须有序，而且只能从小到大排列D. 表必须有序，且表只能以顺序方式存储3)折半查找的时间复杂性为（D）A. O（n2）B. O（n）C. O（nlog(n)）D. O（log(n)）4)概率不同的有序表，最适合的查找算法是（ C ）A．顺序查找B．折半查找C．静态树表查找 D．索引顺序表查找5)平均查找长度最短的查找方法是____C________。
A．折半查找 B.顺序查找 C.哈希查找 4.其他6)折半查找有序表（4，6，10，12，20，30，50，70，88，100）。
若查找表中元素58，则它将依次与表中A比较大小，查找结果是失败。
A．20，70，30，50 B．30，88，70，50 C．20，50 D．30，88，507)当采用分快查找时，数据的组织方式为 ( B )A．数据分成若干块，每块内数据有序B．数据分成若干块，每块内数据不必有序，但块间必须有序，每块内最大（或最小）的数据组成索引块C. 数据分成若干块，每块内数据有序，每块内最大（或最小）的数据组成索引块D. 数据分成若干块，每块（除最后一块外）中数据个数需相同8)分别以下列序列构造二叉排序树，与用其它三个序列所构造的结果不同的是( 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)9)设有一组记录的关键字为{19，14，23，1，68，20，84，27，55，11，10，79}，用链地址法构造散列表，散列函数为H（key）=key MOD 13,散列地址为1的链中有（ D ）个记录。
- 1、下载文档前请自行甄别文档内容的完整性，平台不提供额外的编辑、内容补充、找答案等附加服务。
- 2、"仅部分预览"的文档,不可在线预览部分如存在完整性等问题,可反馈申请退款(可完整预览的文档不适用该条件!)。
- 3、如文档侵犯您的权益，请联系客服反馈,我们会尽快为您处理(人工客服工作时间：9:00-18:30)。
方法二：拓扑排序
void Graph :: TopoOrder( ) {
int top = - 1 ; for ( int i=0 ; i<n ; i + + )
if ( count[i] = = 0 ) { count[i] = top ; top = i ; }
for ( int i=0 ; i<n ; i + + ) if ( top = = - 1 ) //检测图中是否有回路 { cout << " There is a cycle in network ! " << endl ; return ; } else { int j=top ; top=count[top] ; cout<<j<<endl ; //输出栈顶j Edge *p = head[j].Adjacent ; while( p != NULL ) //把j的所有邻接顶点的入度减1 { int k=p->VerAdj ; if ( --count[k]= = 0 ) { count[k]=top ; top=k ; } p=p->link ; } }
5-12
设计一个算法，检测采用邻接表方法存储、具 有n个顶点的有向图中是否存在从顶点v到顶 点u的路径，若存在路径，算法给出信息 TRUE，否则，给出信息FALSE .
参考答案
算法Path(v,u. flag) /*判断v到u是否有路.有,flag为TRUE,否则FALSE.vis全局，记
录结点访问状态*/ P1[递归出口] IF(v=u) THEN (flag TRUE.RETURN.) P2[依次判断v的邻接顶点是否有到u的路]
时间复杂度O(n)，空间复杂度O(n)
其它方法
调用DFS或BFS，检查vis数组，判断是否在一个连 通分支。
Warshall，判断v、u之间是否连通
5-13
设G＝（V,E）是有向图，请给出算法，判断G 中是否有回路，并要求算法的复杂性为O（ n+e）。
方法一：深度优先搜索
思想：深搜时，每个结点有两个状态，标记是 否被访问过（0未访问，1已访问过）。判环时 ，多引入一个状态，标记结点正在访问中（-1 正在访问中）。如果一个结点正在访问中，又 遍历到该接点，那个存在环路。这种状况是由 于出现了反向边，即后代指向祖先的边。
4
5
6
15
3
1234
dis 35 0 10 15
path 4 -1 2 2
s
1111
56
30 ∞ 4 -1 10
最短路径 最短路径长度
2→3
10
2→4
15
2→4→5
30
2→4→1
35
2→6
∞
5-15
试求出下图中所有顶点之间的最短路径
参考答案
A(-1)
A(Hale Waihona Puke )A(1)A(2)
A(3)
0 1 2 3 012 3 0 1 2 3 0 1 2 3 0 12 3
}
思考
无向图如何判环？
5-14
对于下图所示的非负有向网络，给出Dijkstra
算法产生的由源点2到图中其它顶点的最短路
径长度以及路径所经历的顶点，并写出生成过
程。
50
10
1
2
3
10 15 35
20
20
30
4
5
6
15
3
50
10
1
2
3
10 15 35
20
20
30
4
5
6
15
3
S2
1
2
初始化
∞
如果图中有多个连通分支，需要对每个连通分 支都判断。
算法Cycle(v.flag)
/*判断以v为起点的连通分支是否有环，若有，flag为TRUE, 否则FALSE. vis全局，记录每个点的访问状态*/
C1[标记v正在访问中] vis[v]=-1.
C2[深度优先遍历] p Head[v]. WHILE(p<>NULL) DO ( if(VerAdj(p)=-1) (flag=TRUE.RETURN) if(VerAdj(p)=0) ( Cycle(VerAdj(p), flag). IF(flag=TRUE) THEN RETURN.) p Link(p).
vis[v]=1. p Head[v]. WHILE(p<>NULL) DO (
IF(vis[VerAdj(p)]=0) ( Path(VerAdj(p),u, flag). IF(flag=TRUE) THEN RETURN. )
p Link(p). ). P3[不存在路]
flag=FALSE. ▌
0
2
∞
0
23
∞
0
234
35
0
2 3 4 5 35
0
2 3 4 5 1 35
0
2 3 4 5 1 6 35
0
参考答案
3
4 56
∞ ∞ ∞∞
10 15 ∞ ∞
10 15 40 ∞
10 15 30 ∞
10 15 30 ∞
10 15 30 ∞
10 15 30 ∞
50
10
1
2
3
10 15 35
20
20
30
参考答案
0 0 9 3 0 9 3 0 9 14 3 0 9 14 3 0 5 7 3 1 0 5 0 5 0 5 6 0 5 9 6 0 5 9 2 1 0 1 10 0 4 1 10 0 4 1 10 0 4 1 6 0 4 3 2 4 0 2 4 0 2 4 0 5 2 4 0 5 2 4 0
Path(-1)
Path(0)
Path(1)
Path(2)
Path(3)
01230123012301230 12 3
0 -1 0 -1 0 -1 0 -1 0 -1 0 1 0 -1 0 1 0 -1 3 3 0 1 -1 -1 1 -1 -1 -1 1 -1 0 -1 1 -1 2 -1 1 0 2 -1 1 0 2 2 -1 -1 -1 2 0 -1 0 2 0 -1 0 2 0 -1 0 2 3 -1 0 3 -1 3 3 -1 -1 3 3 -1 0 3 3 -1 2 3 3 -1 2 3 3 -1
数据结构习题 第 5 章
吉林大学计算机科学与技术学院 谷方明
第5章作业
5-1，5-7，5-12，5-13，5-14，5-15，5-16
5-1
给出下图所示的邻接矩阵和邻接表
A
B
C
D
E
参考答案
A B
1
2
C
3
4
D
E
5
12345 00110 00110 00001 00000 10010
参考答案：注意头指针数组
A
C
D
B
C
D
C
E
Λ
D
Λ
E
A
E
5-7
用邻接矩阵存储一个包含1000个顶点和1000条 边的图，则该图的邻接矩阵中有多少元素？有 多少非零元素？该矩阵是否为稀疏矩阵？
参考答案
１）矩阵中元素个数：1000000 ２）若图为有向图：非零元素的个数：1000
若图为无向图：非零元素的个数：2000 ３）该矩阵是稀疏矩阵