下载文档原格式
数据结构第2章习题参考答案1. 简答题1.1 什么是数据结构？数据结构是指相互之间存在一种或多种特定关系的数据元素的集合，它包括数据的逻辑结构和物理结构。
1.2 数据结构的分类有哪些？数据结构可以分为线性结构和非线性结构。
线性结构包括线性表、栈、队列和串；非线性结构包括树和图。
1.3 数据结构的逻辑结构有哪些？数据结构的逻辑结构包括线性结构、树形结构和图形结构。
1.4 数据结构的物理结构有哪些？数据结构的物理结构包括顺序存储结构和链式存储结构。
1.5 什么是算法？算法是指求解问题的具体步骤和方法。
1.6 算法的特性有哪些？算法应具有有穷性、确定性、可行性和输入输出性。
2. 选择题2.1 在栈的顺序存储结构中，栈的存储位置是：A. 自顶向下递增B. 自底向上递增C. 自底向上递减D. 自顶向下递减答案：D2.2 下列哪个数据结构不适合表示有父子关系的数据？A. 二叉树B. 图C. 链表D. 堆答案：D2.3 对于一棵完全二叉树，叶子节点的个数为n，则树中节点的总数为：A. 2nB. 2n + 1C. nD. n + 1答案：A2.4 假设有一个长度为10的栈，初始时栈为空，若对该栈连续执行5次入栈操作，然后执行4次出栈操作，最后执行1次入栈操作，则栈中剩余的元素个数为：A. 0B. 1C. 4D. 6答案：D3. 编程题3.1 实现一个栈数据结构的基本操作，包括入栈、出栈、获取栈顶元素和判断栈是否为空。
```Pythonclass Stack:def __init__(self):self.items = []def is_empty(self):return len(self.items) == 0def push(self, item):self.items.append(item)def pop(self):if self.is_empty():return Nonereturn self.items.pop()def peek(self):if self.is_empty():return Nonereturn self.items[-1]```3.2 实现一个队列数据结构的基本操作，包括入队、出队、获取队首元素和判断队列是否为空。
数据结构c语言版第三版习题解答数据结构 C 语言版第三版习题解答在学习计算机科学与技术的过程中，数据结构是一门非常重要的基础课程。
而《数据结构C 语言版第三版》更是众多教材中的经典之作。
其中的习题对于我们理解和掌握数据结构的概念、原理以及算法实现起着至关重要的作用。
接下来，我将为大家详细解答这本书中的一些典型习题。
首先，让我们来看一道关于线性表的习题。
题目是这样的：设计一个算法，从一个有序的线性表中删除所有其值重复的元素，使表中所有元素的值均不同。
对于这道题，我们可以采用双指针的方法来解决。
定义两个指针 p和 q，p 指向线性表的开头，q 从 p 的下一个位置开始。
当 q 所指向的元素与 p 所指向的元素相同时，我们就将 q 所指向的元素删除，并将 q 向后移动一位。
当 q 所指向的元素与 p 所指向的元素不同时，我们将 p 向后移动一位，并将 q 所指向的元素赋值给 p 所指向的位置，然后再将 q 向后移动一位。
当 q 超出线性表的范围时，算法结束。
下面是用 C 语言实现的代码：｀｀｀cvoid removeDuplicates(int arr, int n) ｛int p ＝ 0, q ＝ 1;while （q ＜ n) ｛if （arrp ＝＝ arrq) ｛for （int i ＝ q; i ＜ n 1; i+＋）｛arri ＝ arri ＋ 1;｝（n)；｝ else ｛p+＋；arrp ＝ arrq;｝q+＋；｝｝｀｀｀再来看一道关于栈的习题。
题目是：利用栈实现将一个十进制数转换为八进制数。
我们知道，将十进制数转换为八进制数可以通过不断除以 8 取余数的方法来实现。
而栈的特点是后进先出，正好适合存储这些余数。
以下是 C 语言实现的代码：｀｀｀cinclude ＜stdioh>include ＜stdlibh>define MAX_SIZE 100typedef struct ｛int top;int dataMAX_SIZE;｝ Stack;／／初始化栈void initStack(Stack s) ｛s>top ＝－1;｝／／判断栈是否为空int isEmpty(Stack s) ｛return s>top ＝＝－1;｝／／判断栈是否已满int isFull(Stack s) ｛return s>top ＝＝ MAX_SIZE 1;｝／／入栈操作void push(Stack s, int element) ｛if （isFull(s)）｛printf(＂Stack Overflow!＼n"）；return;｝s>data+＋s>top ＝ element;｝／／出栈操作int pop(Stack s) ｛if （isEmpty(s)）｛printf(＂Stack Underflow!＼n"）；return －1;｝return s>datas>top;｝／／将十进制转换为八进制void decimalToOctal(int decimal) ｛Stack s;initStack(＆s)；while （decimal!＝ 0) ｛push(＆s, decimal ％ 8)；decimal ／＝ 8;｝while （！isEmpty(＆s)）｛printf(＂％d"， pop(＆s)）；｝printf(＂＼n"）；｝int main(）｛int decimal;printf(＂请输入一个十进制数: ＂）；scanf(＂％d"，＆decimal)；printf(＂转换后的八进制数为: ＂）；decimalToOctal(decimal)；return 0;｝｀｀｀接下来是一道关于队列的习题。
数据结构习题集（自编）第一章绪论一、选择题1．数据结构是一门研究非数值计算的程序设计问题中的操作对象以及它们之间的（）和运算的学科。
A．结构B．关系 C．运算 D．算法2．在数据结构中，从逻辑上可以把数据结构分成（）。
A．动态结构和静态结构 B．紧凑结构和非紧凑结构C．线性结构和非线性结构 D．逻辑结构和存储结构3．线性表的逻辑顺序和存储顺序总是一致的，这种说法（）。
A．正确B．不正确 C．无法确定 D．以上答案都不对4．算法分析的目的是（）。
A．找出算法的合理性 B．研究算法的输人与输出关系C．分析算法的有效性以求改进 D．分析算法的易懂性5. 算法的时间复杂度取决于（）A．问题的规模B待处理数据的初态 C. A和B6．一个算法应该是（）。
A．程序B．问题求解步骤的描述C．要满足五个基本特性 D．A和C.7. 下面关于算法说法错误的是（）A．算法最终必须由计算机程序实现B.为解决某问题的算法与为该问题编写的程序含义是相同的C. 算法的可行性是指指令不能有二义性D. 以上几个都是错误的8．以下与数据的存储结构无关的术语是（）。
A．循环队列 B. 链表 C. 哈希表 D. 栈9．在下面的程序段中，对x的赋值语句的频度为（）for（i=0;i<n;i++）for(j=0;j<n;j++)x=x+1;nA． 2n B．n C．n2 D．log210．以下数据结构中，（）是非线性数据结构A．树 B．字符串 C．队列 D．栈11. 下列数据中，（）是线性数据结构。
A．哈夫曼树 B.有向无环图 C. 二叉排序树 D. 栈12．以下属于逻辑结构的是（）。
A．顺序表 B. 哈希表 C.有序表 D. 单链表二、填空题1、_______是信息的载体，是对客观事物的符号表示，它能够被计算机识别、存储、加工和处理，________是对能够有效的输人到计算机中并且能够被计算机处理的符号的总称。
（数据、数据）2、数据元素是数据的______，有些情况下也称为元素、结点、顶点、记录等。
单元练习1一．判断题（下列各题，正确的请在前面的括号内打√；错误的打╳）（√）（1）数据的逻辑结构与数据元素本身的内容和形式无关。
（√）（2）一个数据结构是由一个逻辑结构和这个逻辑结构上的一个基本运算集构成的整体。
（ㄨ）（3）数据元素是数据的最小单位。
（ㄨ）（4）数据的逻辑结构和数据的存储结构是相同的。
（ㄨ）（5）程序和算法原则上没有区别，所以在讨论数据结构时可以通用。
（√）（6）从逻辑关系上讲，数据结构主要分为线性结构和非线性结构两类。
（√）（7）数据的存储结构是数据的逻辑结构的存储映像。
（√）（8）数据的物理结构是指数据在计算机内实际的存储形式。
（ㄨ）（9）数据的逻辑结构是依赖于计算机的。
（√）（10）算法是对解题方法和步骤的描述。
二．填空题（1）数据有逻辑结构和存储结构两种结构。
（2）数据逻辑结构除了集合以外，还包括：线性结构、树形结构和图形结构。
（3）数据结构按逻辑结构可分为两大类，它们是线性结构和非线性结构。
（4）树形结构和图形结构合称为非线性结构。
（5）在树形结构中，除了树根结点以外，其余每个结点只有 1 个前趋结点。
（6）在图形结构中，每个结点的前趋结点数和后续结点数可以任意多个。
（7）数据的存储结构又叫物理结构。
（8）数据的存储结构形式包括：顺序存储、链式存储、索引存储和散列存储。
（9）线性结构中的元素之间存在一对一的关系。
（10）树形结构结构中的元素之间存在一对多的关系，（11）图形结构的元素之间存在多对多的关系。
（12）数据结构主要研究数据的逻辑结构、存储结构和算法（或运算）三个方面的内容。
（13）数据结构被定义为(D，R)，其中D是数据的有限集合，R是D上的关系的有限集合。
（14）算法是一个有穷指令的集合。
（15）算法效率的度量可以分为事先估算法和事后统计法。
（16）一个算法的时间复杂性是算法输入规模的函数。
（17）算法的空间复杂度是指该算法所耗费的存储空间，它是该算法求解问题规模n的函数。
数据结构(C语言版)习题参考答案数据结构(C语言版)习题参考答案1. 数据结构简介数据结构是计算机科学中重要的概念之一，它关注如何组织和存储数据，以便有效地进行访问和操作。
C语言是一种广泛应用于数据结构实现的编程语言。
本文将提供一些常见数据结构习题的参考答案，帮助读者理解和掌握数据结构的基本概念与实现。
2. 数组数组是一种线性结构，存储具有相同数据类型的元素。
以下是一些数组习题的参考答案：2.1 统计数组中某个元素出现的次数```int countOccurrences(int arr[], int n, int x) {int count = 0;for (int i = 0; i < n; i++) {if (arr[i] == x) {count++;}}return count;}```2.2 查找数组中的最大值和最小值```void findMinMax(int arr[], int n, int* min, int* max) { *min = arr[0];*max = arr[0];for (int i = 1; i < n; i++) {if (arr[i] < *min) {*min = arr[i];}if (arr[i] > *max) {*max = arr[i];}}}```3. 链表链表是一种动态数据结构，每个节点包含数据和指向下一个节点的指针。
以下是一些链表习题的参考答案：3.1 反转链表```Node* reverseLinkedList(Node* head) {Node* prev = NULL;Node* curr = head;while (curr != NULL) {Node* next = curr->next;curr->next = prev;prev = curr;curr = next;}return prev;}```3.2 合并两个有序链表```Node* mergeLists(Node* list1, Node* list2) {if (list1 == NULL) {return list2;}if (list2 == NULL) {return list1;}if (list1->data < list2->data) {list1->next = mergeLists(list1->next, list2);return list1;} else {list2->next = mergeLists(list1, list2->next);return list2;}}```4. 栈和队列栈和队列是两种重要的线性数据结构，栈支持后进先出（LIFO），队列支持先进先出（FIFO）。
大连理工大学张绍武老师数据结构第一次上机作业答案作业1. 线性表编程作业：1．将顺序表逆置，要求用最少的附加空间。
参考答案#include <stdio.h>#include <malloc.h>#include <process.h>#define LIST_INIT_SIZE 100#define LISTINCREMENT 10#define OK 1#define ERROR 0#define OVERFLOW -2typedef int Status;typedef int ElemType;typedef struct{ ElemType *elem;int length;int listsize;}SqList;//创建空顺序表Status InitList_Sq( SqList &L ){L.elem = (ElemType*) malloc (LIST_INIT_SIZE*sizeof(ElemType));if (!L.elem)exit(OVERFLOW);L.length = 0;L.listsize = LIST_INIT_SIZE;return OK;}//顺序表在第i个元素之前插入eStatus ListInsert_Sq( SqList &L, int i, ElemType e){ ElemType *newbase,*q,*p;if(i<1 || i>L.length+1) //插入位置非法return ERROR;if(L.length>=L.listsize)//溢出，动态追加空间{ newbase= (ElemType *)realloc(L.elem, (L.listsize+ LISTINCREMENT) *sizeof(ElemType));if(!newbase) exit(OVERFLOW);L.elem=newbase;L.listsize+=LISTINCREMENT;}q=&(L.elem[i-1]);for(p=&(L.elem[L.length-1]);p>=q;p--) //元素后移*(p+1)=*p;*q=e; //完成元素插入++L.length;return(OK);}//顺序表遍历显示Status ListTraverse_Sq(SqList L){ int i=0;if(!L.elem)return ERROR;while(i<L.length)printf("%d ",L.elem[i++]);printf("\n");return OK;}//顺序表逆置void Reverse_Sq(SqList &L){int i,j;ElemType temp;for(i=0,j=L.length-1; i<j; i++,j--){temp=L.elem[i];L.elem[i]=L.elem[j];L.elem[j]=temp;}}void main(){SqList L;char flag;int i;ElemType e;if(InitList_Sq(L)==OK){printf("建立空顺序表成功！\n");do{printf("当前线性表长度为：%d\n",L.length);printf("请输入要插入元素的位置：");scanf("%d",&i);printf("请输入要插入的元素值：");scanf("%d",&e);if(ListInsert_Sq(L,i,e)==OK){printf("插入成功，插入后顺序表长度为：%d\n",L.length);printf("插入后的顺序表为：");ListTraverse_Sq(L);}elseprintf("插入失败");printf("\n继续插入元素？(y/n) ");fflush(stdin);scanf("%c",&flag);}while(flag=='y');Reverse_Sq(L);printf("顺序表逆置后为：\n");ListTraverse_Sq(L);}elseprintf("顺序表初始化失败！\n");}2．从键盘读入n个整数（升序），请编写算法实现：（1）CreateList()：建立带表头结点的单链表；（2）PrintList()：显示单链表，（形如：H->10->20->30->40）;（3）InsertList()：在有序单链表中插入元素x；（4）ReverseList()：单链表就地逆置；（5）DelList()：在有序单链表中删除所有值大于mink且小于maxk的元素。
第1 章绪论课后习题讲解1. 填空(1) 从逻辑关系上讲，数据结构主要分为（）、（）、（）和（）。
(2) 数据的存储结构主要有（）和（）两种基本方法，不论哪种存储结构，都要存储两方面的内容：（）和（）。
(3)算法在发生非法操作时可以作出处理的特性称为（）。
2. 选择题⑴顺序存储结构中数据元素之间的逻辑关系是由（）表示的，链接存储结构中的数据元素之间的逻辑关系是由（）表示的。
A 线性结构B 非线性结构C 存储位置D 指针⑵假设有如下遗产继承规则：丈夫和妻子可以相互继承遗产；子女可以继承父亲或母亲的遗产；子女间不能相互继承。
则表示该遗产继承关系的最合适的数据结构应该是（）。
A 树B 图C 线性表D 集合3. 判断题(1) 每种数据结构都具备三个基本操作：插入、删除和查找。
第2 章线性表课后习题讲解1. 填空⑵顺序表中第一个元素的存储地址是100，每个元素的长度为2，则第5个元素的存储地址是（）。
第5个元素的存储地址=第1个元素的存储地址＋(5－1)×2=108⑶设单链表中指针p 指向结点A，若要删除A的后继结点（假设A存在后继结点），则需修改指针的操作为（）。
【解答】p->next=(p->next)->next⑸非空的单循环链表由头指针head指示，则其尾结点（由指针p所指）满足（）。
p->next=head⑹在由尾指针rear指示的单循环链表中，在表尾插入一个结点s的操作序列是（）；删除开始结点的操作序列为（）。
【解答】s->next =rear->next; rear->next =s; rear =s; q=rear->next->next; rear->next->next=q->next; delete q;2. 选择题⑴线性表的顺序存储结构是一种（）的存储结构，线性表的链接存储结构是一种（）的存储结构。
A 随机存取B 顺序存取C 索引存取D 散列存取【解答】A，B 【分析】参见2.2.1。
数据结构课程课后习题答案(总40页)--本页仅作为文档封面，使用时请直接删除即可----内页可以根据需求调整合适字体及大小--《数据结构简明教程》练习题及参考答案练习题11. 单项选择题（1）线性结构中数据元素之间是（）关系。
A.一对多B.多对多C.多对一D.一对一答：D（2）数据结构中与所使用的计算机无关的是数据的（）结构。
A.存储B.物理C.逻辑D.物理和存储答：C（3）算法分析的目的是（）。
A.找出数据结构的合理性B.研究算法中的输入和输出的关系C.分析算法的效率以求改进D.分析算法的易懂性和文档性答：C（4）算法分析的两个主要方面是（）。
A.空间复杂性和时间复杂性B.正确性和简明性C.可读性和文档性D.数据复杂性和程序复杂性答：A（5）计算机算法指的是（）。
A.计算方法B. 排序方法C.求解问题的有限运算序列D.调度方法答：C（6）计算机算法必须具备输入、输出和（）等5个特性。
A.可行性、可移植性和可扩充性B.可行性、确定性和有穷性C.确定性、有穷性和稳定性D.易读性、稳定性和安全性答：B2. 填空题（1）数据结构包括数据的①、数据的②和数据的③这三个方面的内容。
答：①逻辑结构②存储结构③运算（2）数据结构按逻辑结构可分为两大类，它们分别是①和②。
答：①线性结构②非线性结构3（3）数据结构被形式地定义为（D,R ），其中D 是 ① 的有限集合，R 是D 上的 ② 有限集合。
答：①数据元素 ②关系（4）在线性结构中，第一个结点 ① 前驱结点，其余每个结点有且只有1个前驱结点；最后一个结点 ② 后继结点，其余每个结点有且只有1个后继结点。
答：①没有 ②没有（5）在树形结构中，树根结点没有 ① 结点，其余每个结点有且只有 ② 个前驱结点；叶子结点没有 ③ 结点，其余每个结点的后继结点数可以是 ④ 。
答：①前驱 ②1 ③后继 ④任意多个（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。
1.设计一个非递归算法，从一棵二叉树中查找出所有结点的最大值并返回。
答：int InorderTraverse(BiTree T, void (*visit)(TelemType e)){ int max=0;InitStack(S); p = T;while(p||!StackEmpty(S)){if(p){Push(S,p); p =p->lchild;} //向左下走到头else{ Pop(S,p);visit(t->data);if((t->data)>max) max=t->data;p = p->rchild; //向右走一步}//else} // whilereturn max;}2.设树采用定长结点的多重链表表示，设计算法实现树的按层次遍历。
答：typedef struct CSTNode{ char data;struct CSTNode *childone,*childtwo,*childthree;}CSTNode，*CSTree;void LevelOrderTraverse(CSTree T){ CSTree p=T;SqQueue Q;if(!T) return;InitQueue(Q); EnQueue(Q,p);while(!QueueEmpty(Q)){ DeQueue(Q,p);printf("%c",p->data);if(p->childone) EnQueue(Q,p->childone);if(p->childtwo) EnQueue(Q,p->childtwo);if(p->childthree) EnQueue(Q,p->childthree);}}3.阅读下列算法，若有错，改正之。
BiTree InSucc(BiTree q){ // 已知q是指向中序线索二叉树上某个结点的指针，// 本函数返回指向*q的后继的指针。
r = q->rchild;if (!r -> rtag )while (!r -> rtag ) r = r->rchild;return r;}答：共3处错误BiTree InSucc(BiTree q){ // 已知q是指向中序线索二叉树上某个结点的指针，// 本函数返回指向*q的后继的指针。
r = q->rchild;if (!r -> rtag )while (!r -> ltag ) r = r->lchild;return r->lchild;}4.写出二叉树的先序遍历和后序遍历的非递归算法。
答:先序遍历非递归算法void PreOrderTraverse(BiTree T){SqStack S;InitStack(S);BiTree *p=T;while (p!=NULL || !StackEmpty(S)){while (p!=NULL) //遍历左子树{visit(T->data);Push(s,p);p=p->lchild;}if (!StackEmpty(s)) //通过下一次循环中的内嵌while实现右子树遍历 {Pop(S,p);p=p->rchild;}//endif}//endwhile}后序遍历非递归算法typedef enum {L,R} tagtype;typedef struct{BiTree ptr;tagtype tag;}stacknode;typedef struct{stacknode Elem[maxsize];int top;}SqStack;void PostOrderTraverse(BiTree T){SqStack S;stacknode x;InitStack(S);p=T;do{while (p!=null) //遍历左子树{x.ptr = p;x.tag = L; //标记为左子树push(S,x);p=p->lchild;}while (!StackEmpty(S) && S.Elem[S.top].tag==R){x = Pop(S);p = x.ptr;visit(p->data); //tag为R，表示右子树访问完毕，故访问根结点 }if (!StackEmpty(S)){S.Elem[S.top].tag =R; //遍历右子树p=S.Elem[s.top].ptr->rchild;}}while (!StackEmpty(S));}5.设计一个非递归算法，计算树的叶子结点数。
（要求说明树的存储方式）答：设树的存储方式为孩子兄弟链表typedef struct CSTNode{ char data;struct CSTNode *firstchild,*nextsibling;}CSTNode，*CSTree;void Getnum(CSTNode *t,int *n,int *m)//n是叶子节点数，m是非叶子结点数//其中n,m的初值为零{ CSTNode *queue=CSTNode[50];//初始化一个队列CSTNode *T=t;int rear=0,front=0;if(!T) return;//若树为空，则返回queue[rear++]=T;while(rear!=front){ T=queue[front++];if(T->firstchild||T->nextsibling)//结点有左子树或右子树{ (*m)++;if(T->firstchild) queue[rear++]=T->firstchild; if(T->nextsibling) queue[rear++]=T->nextsibling; }else (*n)++;}}6.已知带权无向图如图所示：(1). 根据普里姆（Prim）算法，设计算法,求它的从顶点a出发的最小生成树；(2). 根据克鲁斯卡尔（Kruskal）算法，求该图的最小生成树,给出添加边次序。
答： （1） struct {VertexType adjvex; // U 集中的顶点 VRType lowcost; // 边的权值 } closedge[MAX_VERTEX_NUM];void MiniSpanTree_P(MGraph G, VertexType a) { //用普里姆算法从顶点a 出发构造网G 的最小生成树 k = LocateVex ( G, a );for ( j=0; j<G.vexnum; ++j ) // 辅助数组初始化 if (j!=k)closedge[j] = { a, G.arcs[k][j].adj }; closedge[k].lowcost = 0; // 初始，U ＝{a} for (i=0; i<G.vexnum; ++i) { k = minimum(closedge);// 求出加入生成树的下一个顶点(k) printf(closedge[k].adjvex, G.vexs[k]); // 输出生成树上一条边closedge[k].lowcost = 0; // 第k 顶点并入U 集 for (j=0; j<G.vexnum; ++j) //修改其它顶点的最小边if (G.arcs[k][j].adj < closedge[j].lowcost)closedge[j] = { G.vexs[k], G.arcs[k][j].adj };} } （2）7．已知带权有向图如图所示：(1). 画出该图的邻接矩阵存储结构；(2). 求从顶点a 到其余各顶点之间的最短路经及最短路经长度，并给出计算过程。
答：a21 2 a fb d gc h e 6 97 832 5 1 30 24214 1 37 56 2 5 ab c eddc b e4 3（1）（2） 终点 1 2 3 4 5 6 7 b 2(a,b)c ∞32(a,b,c) 32(a,b,c) 13(a,b,d,e,c)13(a,b,d ,e,c)13(a,b,d,e,c)d 6(a,d) 3(a,b,d)e ∞ ∞ 5(a,b,d,e)f 9(a,f) 9(a,f) 9(a,f) 9(a,f)g ∞ ∞ ∞ 12(a,b,d,e,g) 12(a,b,d ,e,g)h ∞ ∞ ∞ ∞ ∞ 33(a,b,d,e,g,h) 18(a,b,d,e,c,h)Vj b d e f g c h S {a,b} {a,b,d} {a,b,d,e}{a,f} {a,b,d,e ,g} {a,b,d,e,c}{a,b,d,e,c,h}长度235912138．列出图中全部可能的拓扑有序序列，并指出应用7.5.1节中算法Topological Sort 算法求得的是哪一个序列？123456答：全部可能的拓扑有序序列：1-5-2-3-6-4 1-5-2-6-3-4 1-5-6-2-3-4 5-1-2-3-6-4 5-1-2-6-3-4 5-1-6-2-3-4 5-6-1-2-3-4应用7.5.1节中算法Topological Sort 算法求得的是 1-5-2-3-6-49．对下图所示AOE 网络，计算各活动弧的e(ai)和l （ai ）函数值，各事件（顶点）的ve(vi)和vl(vi)函数值，列出各条关键路径。
abcdef gha ∞ 2 ∞ 6 ∞9∞ ∞b ∞ ∞ 30 1 ∞ ∞ ∞ ∞c ∞ ∞ ∞ ∞ ∞ ∞ ∞ 5d ∞ ∞ ∞ ∞ 2 ∞ ∞ ∞e ∞ ∞ 8 ∞ ∞ ∞7 ∞f ∞ ∞ ∞ ∞ 3 ∞ 24 ∞g ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞ h ∞ ∞ ∞ ∞ ∞ ∞ ∞ 21关键路径：（α,G,H,K,J,E,ω）顶点 ve vl α 0 0A 1 20B 6 24C 17 26D 3 19E 34 34F 4 8G 3 3H 13 13I 1 7J 31 31K 22 22ω 44 44边ee el el-ee (α,A) 0 19 19 (α,B) 0 18 18 (α,D) 0 16 16 (α,F) 0 4 4 (α,G) 0 0 0 (α,I) 0 6 6 (A,C) 1 20 19 (B,C) 6 24 18 (D,C) 3 19 16 (D,E) 3 26 23 (D,J) 3 25 22 (F,E) 4 23 19 (F,H) 4 8 4 (G,ω) 3 23 20 (G,H) 3 3 0 (I,H) 1 7 6 (C,E) 17 26 9 (H,C) 13 22 9 (H,J) 13 27 14 (H,K) 13 13 0 (K,J) 22 22 0 (J,E) 31 31 0 (J,ω) 31 32 1 (E,ω)3434。
