没有合适的资源？快使用搜索试试~ 我知道了~

文库首页安全技术网络安全PTA习题：Data Structures and Algorithms (English)1

PTA习题：Data Structures and Algorithms (English)1

doc文档

需积分: 0 0 下载量 94 浏览量 2022-08-08 21:15:03 上传评论收藏 388KB DOCX 举报

温馨提示

试读

23页

PTA习题：Data Structures and Algorithms (English)1

资源详情

资源评论

资源推荐

6-11 Shortest Path [1] (25 分)

Write a program to find the unweighted shortest distances from any vertex to a given

source vertex in a digraph.

Format of functions:

void ShortestDist( LGraph Graph, int dist[], Vertex S );

where LGraph is defined as the following:

typedef struct AdjVNode *PtrToAdjVNode;

struct AdjVNode{

Vertex AdjV;

PtrToAdjVNode Next;

};

typedef struct Vnode{

PtrToAdjVNode FirstEdge;

} AdjList[MaxVertexNum];

typedef struct GNode *PtrToGNode;

struct GNode{

int Nv;

int Ne;

AdjList G;

};

typedef PtrToGNode LGraph;

The shortest distance from V to the source S is supposed to be stored in dist[V]. If V

cannot be reached from S, store -1 instead.

Sample program of judge:

#include <stdio.h>

#include <stdlib.h>

typedef enum {false, true} bool;

#define MaxVertexNum 10 /* maximum number of vertices */

typedef int Vertex; /* vertices are numbered from 0 to MaxVertexNum-1 */

typedef struct AdjVNode *PtrToAdjVNode;

struct AdjVNode{

Vertex AdjV;

PtrToAdjVNode Next;

};

typedef struct Vnode{

PtrToAdjVNode FirstEdge;

} AdjList[MaxVertexNum];

typedef struct GNode *PtrToGNode;

struct GNode{

int Nv;

int Ne;

AdjList G;

};

typedef PtrToGNode LGraph;

LGraph ReadG(); /* details omitted */

void ShortestDist( LGraph Graph, int dist[], Vertex S );

int main()

{

int dist[MaxVertexNum];

Vertex S, V;

LGraph G = ReadG();

scanf("%d", &S);

ShortestDist( G, dist, S );

for ( V=0; V<G->Nv; V++ )

printf("%d ", dist[V]);

return 0;

}

/* Your function will be put here */

Sample Input (for the graph shown in the figure):

7 9

0 1

0 5

0 6

5 3

2 1

2 6

6 4

4 5

6 5

Sample Output:

-1 1 0 3 2 2 1

6-12 Shortest Path [2] (25 分)

Write a program to find the weighted shortest distances from any vertex to a given source

vertex in a digraph. It is guaranteed that all the weights are positive.

Format of functions:

void ShortestDist( MGraph Graph, int dist[], Vertex S );

where MGraph is defined as the following:

typedef struct GNode *PtrToGNode;

struct GNode{

int Nv;

int Ne;

WeightType G[MaxVertexNum][MaxVertexNum];

};

typedef PtrToGNode MGraph;

The shortest distance from V to the source S is supposed to be stored in dist[V]. If V

cannot be reached from S, store -1 instead.

Sample program of judge:

#include <stdio.h>

#include <stdlib.h>

typedef enum {false, true} bool;

#define INFINITY 1000000

#define MaxVertexNum 10 /* maximum number of vertices */

typedef int Vertex; /* vertices are numbered from 0 to MaxVertexNum-1 */

typedef int WeightType;

typedef struct GNode *PtrToGNode;

struct GNode{

int Nv;

int Ne;

WeightType G[MaxVertexNum][MaxVertexNum];

};

typedef PtrToGNode MGraph;

MGraph ReadG(); /* details omitted */

void ShortestDist( MGraph Graph, int dist[], Vertex S );

int main()

{

int dist[MaxVertexNum];

Vertex S, V;

MGraph G = ReadG();

scanf("%d", &S);

ShortestDist( G, dist, S );

for ( V=0; V<G->Nv; V++ )

printf("%d ", dist[V]);

return 0;

}

/* Your function will be put here */

Sample Input (for the graph shown in the figure):

7 9

0 1 1

0 5 1

0 6 1

5 3 1

2 1 2

2 6 3

6 4 4

4 5 5

6 5 12

Sample Output:

-1 2 0 13 7 12 3

7-1 Maximum Subsequence Sum（25 分）

Given a sequence of K integers { N1, N2, ..., NK }. A continuous subsequence is defined

to be { Ni, Ni+1, ..., Nj } where 1≤i≤j≤K. The Maximum Subsequence is the continuous

subsequence which has the largest sum of its elements. For example, given sequence

{ -2, 11, -4, 13, -5, -2 }, its maximum subsequence is { 11, -4, 13 } with the largest sum

being 20.

Now you are supposed to find the largest sum, together with the first and the last

numbers of the maximum subsequence.

剩余22页未读，继续阅读

内容反馈

CyberNinja

粉丝: 21
资源: 297

上传资源快速赚钱

我的内容管理展开

我的资源快来上传第一个资源

我的收益

登录查看自己的收益

我的积分登录查看自己的积分

我的C币登录后查看C币余额

我的收藏

我的下载

下载帮助

前往需求广场，查看用户热搜

PTA习题：Data Structures and Algorithms (English)1

评论0

最新资源

PTA习题：Data Structures and Algorithms (English)1

评论0

Data-Structures-and-Algorithms

Data Structures and Algorithms Using Python.pdf

Python Data Structures and Algorithms [2017]

JavaScript Data Structures and Algorithms

R Data Structures and Algorithms 无水印pdf

Data Structures and Algorithms in Java(6th) 无水印pdf

Data.Structures.and.Algorithms.Made.Easy.epub

Data Structures and Algorithms in Java (2nd Edition)

Hands-On Data Structures and Algorithms with JavaScript_Code 源码

Data Structures and Algorithms in C++, 4th edition.pdf

<<Data Structures, Algorithms, and Applications in Java>> 源码及习题答案

Hands-On Data Structures and Algorithms with Rust.epub

Data Structures and Algorithms Made Easy

Data Structures and Algorithms in Java, 5th Edition (Part 3/3)

Data Structures And Algorithms With Object-oriented Design Patterns In Java

Data Structures and Algorithms Using Python

Data Structures and Algorithms in Java, 5th Edition (Part 2/3)

Data Structures, Algorithms and Applications in C++ Second Edition

最新资源