南邮_数据结构课后习题答案讲解

格式：ppt
大小：318.00 KB
文档页数：49

下载文档原格式

南邮_数据结构课后习题答案讲解

?
?
?1 4 7 ?
?
?
?4 4 9 ?
?4 4 9 ?
4.7 求对题图4-1的稀疏矩阵执行矩阵转置时数组
num[]和k[]的值。
col
0
1
2
3
4
num[col] 1
0
2
1
2
k[col]
0
1
1
3
4
2020/2/8
14
第六章习题讲解
6-2. 对于三个结点 A，B和C，可分别组成多少不同的无序树、有序树和二叉树？
int i,j,sum=0;
for (i=0;temp[i]<x&&i<n;i++); //找到首个大于等于 x的元素位置 i
if(i>n-1) return; //没有符合条件的元素
ffoorr ((jj==ii;;ljs<tn[j;]<) =y&&j<n;j++); if (lst[j]>y//)找到首个//大大于于yy的的元元素素前位移置 j
?0 0 ???3 0
6 0
0 0
0? 7??
行三元组：???10
2 0
6 ?列三元组：?1
? 3??
??0
0 2
?3?
6
? ?
? 0 0 0 0 0?
?1 4 7 ?
?3 2 ?8?
? ?
0
0 ? 8 10 0??
??3 2 ?8??
??3
3
10
? ?
?? 0 0 0 0 9??
?3 3 10 ?
（2）void Search_Delete(List *lst, T x,T y)

南邮陈慧南版数据结构课后习题答案

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; }

南邮数据结构课后习题课27页PPT

南邮数据结构Βιβλιοθήκη 后习题课26、机遇对于有准备的头脑有特别的亲和力。 27、自信是人格的核心。
28、目标的坚定是性格中最必要的力量泉源之一，也是成功的利器之一。没有它，天才也会在矛盾无定的迷径中，徒劳无功。- -查士德斐尔爵士。 29、困难就是机遇。--温斯顿．丘吉尔。 30、我奋斗，所以我快乐。--格林斯潘。
66、节制使快乐增加并使享受加强。 ——德谟克利特 67、今天应做的事没有做，明天再早也是耽误了。——裴斯泰洛齐 68、决定一个人的一生，以及整个命运的，只是一瞬之间。 ——歌德 69、懒人无法享受休息之乐。——拉布克 70、浪费时间是一桩大罪过。——卢梭

南邮数据结构A 习题9参考答案

9.1（2）（3）⎥⎥⎥⎥⎥⎥⎥⎥⎦⎤⎢⎢⎢⎢⎢⎢⎢⎢⎣⎡0000011000110101000100100010010000009.29.4template <class T>void LGraph<T>::Degree(int *in) { for (int i=0;i<n;i++) { in[i]=0;}ENode<T> *p; for (i=0; i<n; i++) { p=a[i];while (p){in[p->adjvex]++;p=p->nextarc;}}for (i=0;i<n;i++){cout<<i<<": " << in[i] << "; " << endl;}}9.69.139.16设AOE网如图题9-4所示。

求各事件的可能的最早发生时间和允许的最迟发生时间，各活动可能的最早开始时间河运许的最晚开始时间，以及关键活动和关键路径及其长度。

关键路径：a 2,a 7,a 9. 长度：239.17使用普里姆算法以1为源点，画出图题9-5的无向图的最小代价生成树。

9.18使用克鲁斯卡尔算法以，画出图题9-5的无向图的最小代价生成树9.21用迪杰斯特拉算法求图题9-6的有向图中以顶点A 为源点的单源最短路径。

写出一维数组d 和 path 在执行该算法的过程中各步的状态。

9.22用弗洛伊德算法求图题9-6的有向图的所有顶点之间的最短路径。

写出二维数组d 和path 在执行该算法的过程中各步的状态。

（1）初始状态dA pathAdCpathCdDpathDdE dG。

南邮数据结构答案

第1 章绪论一、基础题1. A2. C3. C4. A5. C二、扩展题1.数据是计算机加工处理的对象；数据元素是数据的基本单位，在计算机程序中通常作为一个整体进行考虑和处理；数据项是组成数据元素的、不可分割的最小单位。

2.数据结构是按某种逻辑关系组织起来的数据元素的集合，使用计算机语言描述并按一定的存储方式存储在计算机中，并在其上定义了一组运算。

3.集合结构、线性结构、树形结构和图形结构。

集合结构中，元素之间没有关系；线性结构中，元素之间存在一对一的关系；树形结构中，元素之间存在一对多的关系，其中最多只有一个元素没有前驱元素，这个元素就是根；图形结构中，元素之间存在多对多的关系。

4.顺序存储、链式存储、索引存储和散列存储。

5.一个算法是对特定问题的求解步骤的一种描述，是指令的有限序列。

其特征包括：➢输入：算法有零个或多个输入➢输出：算法至少产生一个输出➢确定性：算法的每一条指令都有确切的定义，没有二义性。

➢能行性/可行性：可以通过已经实现的基本运算执行有限次来实现➢有穷性：算法必须总能在执行有限步之后终止6.联系：程序是计算机指令的有序集合，是算法用某种程序设计语言的表述，是算法在计算机上的具体实现。

区别：在语言描述上不同，程序必须是用规定的程序设计语言来写，而算法的描述形式包括自然语言、伪代码、流程图和程序语言等；算法所描述的步骤一定是有限的，而程序可以无限地执行下去，比如一个死循环可以称为程序，但不能称为算法。

7.正确性：算法的执行结果应当满足功能需求，无语法错误，无逻辑错误简明性：思路清晰、层次分明、易读易懂，有利于调试维护健壮性：当输入不合法数据时，应能做适当处理，不至于引起严重后果效率：有效使用存储空间和有高的时间效率最优性：解决同一个问题可能有多种算法，应进行比较，选择最佳算法可使用性：用户友好性8(1)执行次数为n-1（n>=2），n=1时执行1次；时间复杂度为O(n)。

(2）执行次数为⌈log3n⌉；时间复杂度为O(logn)(3) 执行次数为n2；时间复杂度为O(n2)(4）执行次数为⌊√n⌋ + 1；时间复杂度为O(√n)第2 章线性表1．A2．D3．B4．C5．B6．D7．D8．C9．A10．D1.编写程序实现对顺序表逆置。

南邮数据结构A习题9参考答案.docx

9.1(3)「00000o-100100 010010 001010 110001 100000生成的邻接表9.4template <class T>void LGraph<T>::Degree(int *in) ( -for (int i=0;i<n;i++){in[i]=0;}ENode<T> *p;for (i=0; i<n; i++)P=a[i];while (p)(in[p->adjvex]++;p=p->nextarc;}}for (i=0;i<n;i++)(cout«i«n: " « in[i] «" « endl;}以2为起始顶点的深度优先搜索得到的生成树9.139. 16设A0E网如图题9-4所示。

求各事件的可能的最早发生时间和允许的最迟发生时间，各活动可能的最早开始时间河运许的最晚开始时间，以及关键活动和关键路径及其长度。

9.6O54333333352252222512511④所有可能的拓扑序列(b)按邻接表的拓扑序9.17以2为起始顶点的广度优先题图9.4关键路径：a.2, a?, ag. 长度：239. 17使用普里姆算法以1为源点，画出图题9-5的无向图的最小代价生成树。

9. 18使用克鲁斯卡尔算法以，画出图题9-5的无向图的最小代价生成树9. 21用迪杰斯特拉算法求图题9-6的有向图中以顶点A 为源点的单源最短路径。

写出一维数组d 和path 在执行该算法的过程中各步的状态。

源点终点最短路径路径长度 AB (A, B) 3C (A, B, C) 4D (A, D) 4E (A, B, E) 4G _ 8Sd[A]path[A] d[B] path[B] d[C] path[C] d[D] path[D] d[E] path[E] d[G] path[G] A 0,-1 3, A °°, -1 4, A 5, A °°, -1 B 0,-1 3, A 4,B 4, A 4,B °°, -1 C 0,-1 3, A4,B4, A4,B°°, -1D 0,-1 3, A 4,B 4, A 4,B 8, -1E 0,-1 3, A 4,B 4, A 4,B °°, "I9. 22用弗洛伊德算法求图题9-6的有向图的所有顶点之间的最短路径。

(完整版) 《数据结构》教材课后习题+答案

第1章绪论习题1．简述下列概念：数据、数据元素、数据项、数据对象、数据结构、逻辑结构、存储结构、抽象数据类型。

2．试举一个数据结构的例子，叙述其逻辑结构和存储结构两方面的含义和相互关系。

3．简述逻辑结构的四种基本关系并画出它们的关系图。

4．存储结构由哪两种基本的存储方法实现？5．选择题（1）在数据结构中，从逻辑上可以把数据结构分成（）。

A．动态结构和静态结构B．紧凑结构和非紧凑结构C．线性结构和非线性结构D．内部结构和外部结构（2）与数据元素本身的形式、内容、相对位置、个数无关的是数据的（）。

A．存储结构B．存储实现C．逻辑结构D．运算实现（3）通常要求同一逻辑结构中的所有数据元素具有相同的特性，这意味着（）。

A．数据具有同一特点B．不仅数据元素所包含的数据项的个数要相同，而且对应数据项的类型要一致C．每个数据元素都一样D．数据元素所包含的数据项的个数要相等（4）以下说法正确的是（）。

A．数据元素是数据的最小单位B．数据项是数据的基本单位C．数据结构是带有结构的各数据项的集合D．一些表面上很不相同的数据可以有相同的逻辑结构（5）以下与数据的存储结构无关的术语是（）。

A．顺序队列 B. 链表 C. 有序表 D. 链栈（6）以下数据结构中，（）是非线性数据结构A．树B．字符串C．队D．栈6．试分析下面各程序段的时间复杂度。

（1）x=90; y=100;while(y>0)if(x>100){x=x-10;y--;}else x++;（2）for (i=0; i<n; i++)for (j=0; j<m; j++)a[i][j]=0;（3）s=0;for i=0; i<n; i++)for(j=0; j<n; j++)s+=B[i][j];sum=s;（4）i=1;while(i<=n)i=i*3;（5）x=0;for(i=1; i<n; i++)for (j=1; j<=n-i; j++)x++;（6）x=n; //n>1y=0;while(x≥(y+1)* (y+1))y++;（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．选择题（1）一个向量第一个元素的存储地址是100，每个元素的长度为2，则第5个元素的地址是（）。

《数据结构》课后参考答案

《数据结构》课后参考答案第一题：1. 什么是数据结构？数据结构是一种组织和存储数据的方式，它涉及到数据的逻辑关系、数据元素之间的操作和存储方式等。

数据结构可以帮助我们更有效地组织和管理数据，提高程序的运行效率。

第二题：2. 请简述线性表和链表的区别。

线性表是一种线性结构，其中的数据元素按照线性的顺序排列。

线性表可以使用数组实现，也可以使用链表实现。

链表是一种动态数据结构，它通过节点之间的指针连接来存储数据元素。

主要区别：- 存储方式：线性表使用静态的连续内存空间存储，而链表使用动态的节点存储，并通过指针连接节点。

- 插入和删除操作：线性表需要移动数组中的元素，而链表只需要修改指针指向即可。

- 访问效率：线性表可以通过下标直接访问元素，访问效率高；链表需要从头节点开始逐个遍历，访问效率较低。

第三题：3. 请描述栈和队列的特点及其应用场景。

栈和队列都是常用的线性数据结构，它们在不同的场景中有着不同的特点和应用。

栈的特点：- 先进后出（LIFO）的数据结构。

- 只能在栈顶进行插入和删除操作。

- 用途广泛，如函数调用、表达式求值、计算机内存的管理等。

队列的特点：- 先进先出（FIFO）的数据结构。

- 可以在队尾插入元素，在队头删除元素。

- 用途广泛，如任务调度、消息传递、广度优先搜索等。

第四题：4. 请简述树和图的区别以及它们的应用场景。

树和图都是常用的非线性数据结构，它们之间有着一些区别和各自的应用场景。

树的特点：- 由节点和边组成的层次结构。

- 每个节点最多有一个父节点和多个子节点。

- 常用的树结构有二叉树、平衡二叉树、B树等。

- 应用场景包括文件系统、数据库索引等。

图的特点：- 由节点和边组成的非线性结构。

- 节点之间的关系可以是任意的。

- 常用的图结构有有向图、无向图、加权图等。

- 应用场景包括社交网络、路由算法、拓扑排序等。

综上所述，数据结构是计算机科学的重要基础，它为我们解决实际问题提供了有力的工具和方法。

南邮数据结构课后习题课共27页文档

南邮数据结构课后习题课
•
6、黄金时代是在我们的前面，而不在我们的后面。
•
7、心急吃不了热汤圆。•8、你可以很有来自性，但某些时候请收敛。•
9、只为成功找方法，不为失败找借口 (蹩脚的工人总是说工具不好)。
•
10、只要下定决心克服恐惧，便几乎能克服任何恐惧。因为，请记住，除了在脑海中，恐惧无处藏身。-- 戴尔．卡耐基。
46、我们若已接受最坏的，就再没有什么损失。——卡耐基 47、书到用时方恨少、事非经过不知难。——陆游 48、书籍把我们引入最美好的社会，使我们认识各个时代的伟大智者。——史美尔斯 49、熟读唐诗三百首，不会作诗也会吟。——孙洙 50、谁和我一样用功，谁就会和我一样成功。——莫扎特

南邮陈慧南版数据结构课后习题答案

}
65
if (p==root) root=root->lchild;
else q->rchild=p->lchild;
37
e=p->element;
25
delete p;
return true;
14
32
}
7.8 以下列序列为输入，从空树开始构造AVL搜索树。（1)A，Z，B，Y，C，X （2)A,V,L,T,R,E,I,S,O,K
解：1 调用9.4中的函数InDg计算各个顶点的入度； 2 利用拓扑排序算法依次删去入度为0的顶点发出的边，若最后还
有入度不为0顶点，则该有向图存在有向回路，返回真值。
template <class T>
void LinkedGraph<T>::InDg(ENode<T> *a[],int n,int ind[])
int i,j,top=-1; //top为栈顶元素的下标 ENode<T> *p; for(i=0; i<n; i++)
if(!InDegree[i]) {
时间复杂度。
template <class E,class K>
bool BSTree<E,K>::Delete(E&e)
{ BTNode<E> *p=root,*q=p;
if (!p) return flse;
25
37
91
while (p->rchild)
{ q=p;
14
56
p=p->rchild;
if(!visited[i]) DFS1(i,visited,parent); delete []visited, []parent; }

(完整版) 《数据结构》教材课后习题+答案

第1章绪论习题1．简述下列概念：数据、数据元素、数据项、数据对象、数据结构、逻辑结构、存储结构、抽象数据类型。

2．试举一个数据结构的例子，叙述其逻辑结构和存储结构两方面的含义和相互关系。

3．简述逻辑结构的四种基本关系并画出它们的关系图。

4．存储结构由哪两种基本的存储方法实现？5．选择题（1）在数据结构中，从逻辑上可以把数据结构分成（）。

A．存储结构B．存储实现C．逻辑结构D．运算实现（3）通常要求同一逻辑结构中的所有数据元素具有相同的特性，这意味着（）。

A．顺序队列 B. 链表 C. 有序表 D. 链栈（6）以下数据结构中，（）是非线性数据结构A．树B．字符串C．队D．栈6．试分析下面各程序段的时间复杂度。

数据结构_南京邮电大学中国大学mooc课后章节答案期末考试题库2023年

数据结构_南京邮电大学中国大学mooc课后章节答案期末考试题库2023年1.向最大堆84,49,82,26,29,46依次插入元素94,99,89,80,94，最终得到的最大堆是____________（提示：堆的元素插入操作需调用AdjustUp方法，请将答案表示成元素序列，并用半角逗号相隔，答案中不要有空格）。

参考答案:99,94,84,89,94,46,82,26,49,29,802.设有5×8的数组A，其每个元素占2个字节，已知A[0][4]在内存中的地址是120，按列优先顺序存储，A[2][6]的地址是_________ 。

参考答案:1443.以下选项_____是下图的深度优先遍历序列。

【图片】参考答案:K,D,A,B,E,C,F,G,J,H,I4.对最大堆序列95,61,66,9,19,27执行1次删除操作（提示：对优先级队列执行删除操作默认删除堆顶元素）后得到最大堆序列_____________（提示：堆元素删除操作需调用AdjustDown方法，请将答案表示成元素序列，并用半角逗号相隔，答案中不要有空格）。

参考答案:66,61,27,9,195.求该方法的渐近时间复杂度为__________.(注意填写答案时不要有空格，用x^y的方式表达x的y次方)void aFunc(int n) { for (int i = 0; i < n; i++) { for (int j = i; j < n; j++) { printf("Hello World\n"); } }}O(n^2)6.已知图的边集合:【图片】若采用邻接表存储，则顶点4对应的边结点链表中共有_________个边结点。

参考答案:27.用克鲁斯卡尔算法构造下图的最小代价生成树，第一条被加入生成树上的边一定是(E,C)。

【图片】参考答案:正确8.假设一棵含有18个结点的完全二叉树中，按层次从上到下、每层结点从左到右的顺序，从0开始编号，则编号为14的结点的左孩子编号为_______（如果孩子不存在，则填写NULL）。

1、下载文档前请自行甄别文档内容的完整性，平台不提供额外的编辑、内容补充、找答案等附加服务。
2、"仅部分预览"的文档,不可在线预览部分如存在完整性等问题,可反馈申请退款(可完整预览的文档不适用该条件!)。
3、如文档侵犯您的权益，请联系客服反馈,我们会尽快为您处理(人工客服工作时间：9:00-18:30)。

2014-5-13 4
2-12.设计一个算法，将单链表中结点以逆序排列。逆序的单链表中的结点均为原表中的结点。 Node* pInvert(Node* first) { Node *p=first, *q; first=NULL; while (p) { q=p->Link; p->Link=first; first=p; p=q; } return first; }
先序：DEHFJGCKAB
E
D
A
中序：HEJFGKCDAB 后序：HJKCGFEBAD
H
F
J G
B
C K
2014-5-13
19
6-8.设二叉树以二叉链表存储，试编写求解下列问题的递归算法：（3）求一棵二叉树中的叶结点个数；
int SizeL(BTree Bt) { return SizeofLeaf(Bt.Root); } int SizeofLeaf(BTNode *p) { if(!p) return 0; if( (!(p->RChild))&&(!(p->LChild)) ) return 1; return SizeofLeaf(p->LChild)+SizeofLeaf(p->RChild); }
2014-5-13 24
补充：已知（1，2，3，4，5，6，7，8，9，10， 11）找到9比较几次？
解：
第一次比较：M=(1+11)/2=6，6<9，找[7，11]；
第2次比较：M=(7+11)/2=9， 9=9，成功。所以一共比较2次成功
2014-5-13
25
8-1 建立37，45，91，25，14，76，56，65为输入时的二叉搜索树，再从该树上依次删除76，45，则树形分别如何？
2014-5-13
16
6-5. 找出所有二叉树，其节点在下列两种次序下恰好都以同样的次序出现：（1）先序和中序；（2）先序和后序；（3）中序和后序（1）或者为空二叉树，或者所有结点的左子树都是空的单支树（2）或者为空二叉树，或者只有根结点的二叉树（3）或者为空二叉树，或者所有结点的右子树都是空的单支树
加权路径长度：WPL=(2+3)×4+5×3+(7+9+12)×2=91
2014-5-13 23
7-4为什么说对半搜索算法只适用于顺序有序表的情况？为什么说顺序搜索可用于顺序表和链表，也不受表的有序性限制？解： 1、对半搜索算法必须针对顺序存储的有序表，要求满足两个条件： 1）顺序存储，只有顺序存储才可以根据元素下标（地址）随机存取元素； 2）有序存储，只有有序存储才可以其实现对半查找。 2、顺序搜索从头到尾逐个查找，所以可用于顺序表和链表，也不受表的有序性限制。
2014-5-13
17
6-6. 设对一棵二叉树进行中序遍历和后序遍历的结果分别为：（1）中序遍历（B D C E） A （F H G ）（2）后序遍历（D E C B）（H G F） A 画出该二叉树。
A B C D E H F G
2014-5-13
18
6-7 写出下图中二叉树的先序、中序和后序遍历结果
2014-5-13 13
4.6 给出下列稀疏矩阵的行优先和列优先顺序存储的行三元组和列三元组表示。
0 3 0 0 0 0 0 0 0 0 0 行三元组： 0 2 6 列三元组： 1 1 0 3 0 0 0 7 1 4 7 3 0 0 0 3 2 8 8 10 0 3 3 3 10 1 0 0 9 4 4 9 4 6 0
2014-5-13 5
第三章习题讲解
3-1. 设A，B，C，D，E五个元素依次进栈（进栈后可立即出栈），问能否得到下列序列。若能得到，则给出相应的push和pop序列；若不能，则说明理由。（1）A，B，C，D，E （1）能得到该序列。相应的push和pop序列为：push(A); pop(); push(B); pop(); push(C); pop(); push(D); pop(); push(E); pop();
2014-5-13
6
第三章习题讲解
3-1. 设A，B，C，D，E五个元素依次进栈（进栈后可立即出栈），问能否得到下列序列。若能得到，则给出相应的push和pop序列；若不能，则说明理由。（2）A，C，E，B，D （2）不能得到该序列，在E出栈时，B和D在栈中，B比D先进栈，所以D应比B先出栈。
2014-5-13 11
4-1. 设线性表采用顺序表示方式，并假定顺序表是有序的（设表中元素已按非递减次序排列）。编写函数，实现线性表的如下运算：（2）void Search_Delete(List *lst, T x,T y) 前置条件：x<y 后置条件：删除有序表中元素值在x和y之间（含x和y）的所有元素。
2014-5-13
7
3-1. 设A，B，C，D，E五个元素依次进栈（进栈后可立即出栈），问能否得到下列序列。若能得到，则给出相应的push和pop序列；若不能，则说明理由。（3）C，A，B，D，E （3）不能得到该序列，在C出栈时，A和B在栈中，A比B先进栈，所以B应比A先出栈。
2014-5-13
（1）无序树：9棵（2）有序树：12棵（3）二叉树：30棵
各 6棵 3棵 6棵
6棵
6棵
2014-5-13
15
6-3. 设在度为m的树中，度为1，2，…，m的节点个数分别为n1,n2,…,nm，求叶子节点的数目。
设度为0的节点个数为n0则：树的总度数=节点总个数-1 即：1*n1+2*n2+…+m*nm =n0+ n1+n2+n3+….+ nm-1 因此叶子节点数目为：n0=n2+2*n3+….+ (m-1)nm+1
37 25 45 91 76 56
14
建成的二叉树
2014-5-13
65
26
8-1 建立37，45，91，25，14，76，56，65为输入时的二叉搜索树，再从该树上依次删除76，45，则树形分别如何？
2014-5-13
20
（4）设计算法，交换一棵二叉树中每个结点的左、右子树。
void ExchBt(BTree Bt) { Exch(Bt.Root); } void Exch(BTNode *p) { if (p) { BTNode *q=p->LChild; p->LChild=p->RChild; p->RChild=q; Exch(p->LChild); Exch(p->RChild); } }
2014-5-13
2
第二章习题讲解
2-4．Loc(A[i][j][k])=134+(i*n*p+j*p+k)*2
2014-5-13
3
2-9. 设有长度为n 的一维整型数组A，设计一个算法，将原数组中的元素以逆序排列 void Invert(T elements[], int length) //length数组长度 //elements[]为需要逆序的数组 { T e; for (int i=1;i<length/2;i++) { e=elements[i-1]; elements[i-1]=elements[length-i]; elements[length-i]=e; } }
0 3 2 6 2 8 3 10 4 7 4 9
4.7 求对题图4-1的稀疏矩阵执行矩阵转置时数组 num[]和k[]的值。
col num[col] k[col]
2014-5-13
0 1 0
1 0 1
2 2 1

3 1 3
4 2 4
14
第六章习题讲解
6-2. 对于三个结点A，B和C，可分别组成多少不同的无序树、有序树和二叉树？
2014-5-13 21
6-13. 将上图中的树转换成二叉树，并将下图中的二叉树转换成森林。
2014-5-13
22
6-18. 设S={A,B,C,D,E,F}，W={2,3,5,7,9,12}，对字符集合进行哈夫曼编码，W为各字符的频率（1）画出哈夫曼树（2）计算带权路径长度（3）求各字符的编码 A: B: C: D: E: F: 1010 1011 100 00 01 11
2014-5-13
9
第四章习题讲解
4-1. 设线性表采用顺序表示方式，并假定顺序表是有序的（设表中元素已按非递减次序排列）。编写函数，实现线性表的如下运算：（1）int Search_Insert(List *lst,T x) 后置条件：在有序的顺序表中搜索元素x。 •若x在表中，则返回x在表中的位置。 •否则，若表未满，则在表中插入新元素x，并且插入后，线性表仍然是有序的，返回新元素x的位置； •若表已满，无法插入新元素，则返回-1。
2014-5-13
12
void Search_Delete(List *lst, T x, T y) { if (lst->Size==0) { printf(“The list is empty”); return -1; } int i,j,sum=0; for (i=0;temp[i]<x&&i<n;i++); //找到首个大于等于x的元素位置i if(i>n-1) return; //没有符合条件的元素 for for (j=i;lst[j]<=y&&j<n;j++); (j=i;j<n; ) //找到首个大于 y 的元素位置j if (lst[j]>y) //大于y 的元素前移 sum=j-i; lst[i++]=lst[j++]; while(j<n) //删除 sum个元素 else lst[i++]=lst[j++]; //小于等于 y的元素删除 n=n-sum; { j++; n--; } }

南邮_数据结构课后习题答案讲解

合集下载