精华内容
下载资源
问答
  • 浙大MOOC 数据结构习题 题解索引

    《浙大MOOC 数据结构习题集》题解索引

    0. 写在前面

    1. 2021.6.21:本习题集已经完成啦
    2. 不知不觉间,已经进行了十多道算法题的整理总结了,随着数量的增加,找起来已经比较困难了,因此决定做个索引,以便查找
    3. 为自己设定一个目标,争取早日AC该套习题集,加油
    4. 平时比较忙,不定期更新,如有意见或建议,欢迎留言 :)

    1. English Title

    NO. Topic
    1 Maximum Subsequence Sum
    2 Reversing Linked List
    3 Pop Sequence
    4 List Leaves
    5 Tree Traversals Again
    6 Root of AVL Tree
    7 Complete Binary Search Tree
    8 File Transfer
    9 Huffman Codes
    10 Saving James Bond - Easy Version
    11 Saving James Bond - Hard Version
    12 How Long Does It Take(Topological sort)
    13 Insert or Merge
    14 Insertion or Heap Sort
    15 PAT Judge
    16 Sort with Swap(0, i)
    17 Hashing
    18 Hashing - Hard Version

    2. 中文题

    序号 题目
    1 最大子列和问题
    2 一元多项式的乘法与加法运算
    3 树的同构
    4 是否同一棵二叉搜索树
    5 堆中的路径
    6 列出连通集(邻接矩阵) ,列出连通集(邻接表)
    7 六度空间
    8 哈利·波特的考试
    9 旅游规划(邻接矩阵) ,旅游规划(邻接表)
    10 公路村村通
    11 关键活动
    12 排序
    13 统计工龄
    14 电话聊天狂人(Hash表_分离链接法)
    15 QQ帐户的申请与登陆(Hash表_开放地址法)
    展开全文
  • 06-图1 列出连通 (25 分) 给定一个有N个顶点和E条边的无向图,请用DFS和BFS分别列出其所有的连通。假设顶点从0到N−1编号。进行搜索时,假设我们总是从编号最小的顶点出发,按编号递增的顺序访问邻接点。 ...

    06-图1 列出连通集 (25 分)

    给定一个有N个顶点和E条边的无向图,请用DFS和BFS分别列出其所有的连通集。假设顶点从0到N−1编号。进行搜索时,假设我们总是从编号最小的顶点出发,按编号递增的顺序访问邻接点。

    输入格式:

    输入第1行给出2个整数N(0<N≤10)和E,分别是图的顶点数和边数。随后E行,每行给出一条边的两个端点。每行中的数字之间用1空格分隔。

    输出格式:

    按照"{ v​1​​ v​2​​ ... v​k​​ }"的格式,每行输出一个连通集。先输出DFS的结果,再输出BFS的结果。

    输入样例:

    8 6
    0 7
    0 1
    2 0
    4 1
    2 4
    3 5
    

    输出样例:

    { 0 1 4 2 7 }
    { 3 5 }
    { 6 }
    { 0 1 2 7 4 }
    { 3 5 }
    { 6 }

    最后输出要求一直没看懂,后来才知道原来是要给临接表的每一个表头节点后面的临接点排序。

    感觉这题用临接矩阵会舒服一些,临接表纯粹是为了学习使用的 

    #include <iostream>
    #include <deque>
    #define Vertex int
    #define Edge ENode
    #define MAX_VERTEX 10
    
    typedef struct _ENode	//边
    {
    	Vertex V1;
    	Vertex V2;
    }ENode;
    
    typedef struct _AdjVNode//临接顶点
    {
    	Vertex AdjV;
    	_AdjVNode *next;
    }AdjVNode;
    
    typedef struct _VNode	//顶点表头
    {
    	AdjVNode *first_node;
    }VNode[MAX_VERTEX];
    
    typedef struct _Graph	//图
    {
    	int Vertex_num;
    	int Edge_num;
    	VNode G;
    }Graph;
    
    void creat_Graph(Graph *G, int Vnum, int Enum);
    void insert_Edge(Graph *, Edge);
    void BFS_components(Graph *);
    void BFS(Graph *, Vertex first_V, int visited[]);
    void DFS_components(Graph *);
    void DFS(Graph *, Vertex first_V, int visited[]);
    void print_squ();
    void sort_AdjV(Graph *);
    void sort_bubble(AdjVNode *);
    
    using namespace std;
    
    deque<Vertex> V_squ;//输出的序列
    bool is_first_print = 1;
    
    int main()
    {
    	int N, E;
    	cin >> N >> E;
    	Graph *graph = new Graph;
    	Edge edge;
    	creat_Graph(graph, N, E);
    	for (int i = 0; i < E; i++)
    	{
    		cin >> edge.V1 >> edge.V2;
    		insert_Edge(graph, edge);
    	}
    	sort_AdjV(graph);
    	DFS_components(graph);
    	BFS_components(graph);
    
    	return 0;
    }
    
    void creat_Graph(Graph *graph, int Vnum, int Enum)
    {
    	graph->Vertex_num = Vnum;
    	graph->Edge_num = Enum;
    	for (Vertex i = 0; i < graph->Vertex_num; i++)
    		graph->G[i].first_node = NULL;
    }
    
    void insert_Edge(Graph *graph, Edge edge)
    { 
    	AdjVNode *AdjV_1, *AdjV_2;
    	AdjV_1 = new AdjVNode;
    	AdjV_2 = new AdjVNode;
    	AdjV_1->AdjV = edge.V1;
    	AdjV_2->AdjV = edge.V2;
    	//头插法
    	AdjV_2->next = graph->G[edge.V1].first_node;
    	graph->G[edge.V1].first_node = AdjV_2;
    	AdjV_1->next = graph->G[edge.V2].first_node;
    	graph->G[edge.V2].first_node = AdjV_1;
    }
    
    //广度优先遍历(输出)所有连通分量
    void BFS_components(Graph *graph)
    {
    	int	visited[MAX_VERTEX];
    	for (int i = 0; i < graph->Vertex_num; i++)
    		visited[i] = 0;
    
    	for (Vertex i = 0; i < graph->Vertex_num; i++)
    		if (visited[i] == 0) {
    			BFS(graph, i, visited);
    			print_squ();
    			V_squ.clear();
    		}
    }
    
    void BFS(Graph *graph, Vertex first_V, int visited[])	//入队前访问,出队后检查临接点并入队
    {														//直接访问临接表中的节点,访问完入队,之后只要检查他的临界点就OK了,不要单独去访问表头节点
    	AdjVNode *last;										//不用另外再写一个访问表头的代码,所以更加简洁,唯一一次访问表头是在开头的时候
    	Vertex V = first_V;
    	deque<Vertex>visit_queue;
    	V_squ.push_back(V);//访问表头
    	visited[V] = 1;
    	visit_queue.push_back(V);
    	while (!visit_queue.empty())
    	{
    		V = visit_queue.front();
    		visit_queue.pop_front();
    		last = graph->G[V].first_node;
    		while (last != NULL) {//将表头的所有临接点访问完,并入队,之后就不用访问表头了,出队后只要访问临接即可
    			if (visited[last->AdjV] == 0) {
    				V_squ.push_back(last->AdjV);
    				visited[last->AdjV] = 1;
    				visit_queue.push_back(last->AdjV);
    			}
    			last = last->next;
    		}
    	}
    }
    
    //深度优先遍历(输出)所有连通分量
    void DFS_components(Graph *graph)
    {
    	int	visited[MAX_VERTEX];
    	for (int i = 0; i < graph->Vertex_num; i++)
    		visited[i] = 0;
    
    	for (Vertex i = 0; i < graph->Vertex_num; i++)
    		if (visited[i] == 0) {
    			DFS(graph, i, visited);
    			print_squ();
    			V_squ.clear();
    		}
    }
    
    void DFS(Graph *graph, Vertex first_V, int visited[])
    {
    	AdjVNode *last;
    	Vertex V = first_V;
    
    	if (visited[V] == 0)
    	{
    		V_squ.push_back(V);
    		visited[V] = 1;
    	}
    	else return;
    	last = graph->G[V].first_node;
    	while (last != NULL)
    	{
    		V = last->AdjV;
    		DFS(graph, V, visited);
    		last = last->next;
    	}
    }
    
    void print_squ()
    {
    	if (is_first_print)
    		is_first_print = 0;
    	else
    		cout << endl;
    	cout << "{ ";
    	while (!V_squ.empty())
    	{
    		cout << V_squ.front() << " ";
    		V_squ.pop_front();
    	}
    	cout << "}" ;
    }
    
    void sort_AdjV(Graph *graph)
    {
    	AdjVNode *p;
    	for (Vertex i = 0; i < graph->Vertex_num; i++)
    	{
    		p = graph->G[i].first_node;
    		if (p) sort_bubble(p);
    	}
    }
    
    void sort_bubble(AdjVNode *head)
    {
    	AdjVNode *p,*q;
    	AdjVNode *last;
    	last = NULL;
    	Vertex tmp;
    	while (head->next != last)
    	{
    		p = head;
    		q = p->next;
    		while (p->next != last)
    		{
    			if (p->AdjV > q->AdjV)
    			{
    				tmp = p->AdjV;
    				p->AdjV = q->AdjV;
    				q->AdjV = tmp;
    			}
    			p = p->next;
    			q = q->next;
    		}
    		last = p;
    	}
    }

     

    展开全文
  • 7-2 装箱问题 (20 分)假设有N项物品,大小分别为s​1​​、s​2​​、…、s​i​​、…、s​N​​,其中s​i​​为满足1≤s​i​​≤100的整数。要把这些物品装入到容量为100的一批箱子(序号1-N)中。...

    7-2 装箱问题 (20 分)假设有N项物品,大小分别为s​1​​、s​2​​、…、s​i​​、…、s​N​​,其中s​i​​为满足1≤s​i​​≤100的整数。要把这些物品装入到容量为100的一批箱子(序号1-N)中。装箱方法是:对每项物品, 顺序扫描箱子,把该物品放入足以能够容下它的第一个箱子中。请写一个程序模拟这种装箱过程,并输出每个物品所在的箱子序号,以及放置全部物品所需的箱子数目。
    输入格式:
    输入第一行给出物品个数N(≤1000);第二行给出N个正整数s​i​​(1≤s​i​​≤100,表示第i项物品的大小)。
    输出格式:
    按照输入顺序输出每个物品的大小及其所在的箱子序号,每个物品占1行,最后一行输出所需的箱子数目。
    输入样例:
    8
    60 70 80 90 30 40 10 20

    输出样例:
    60 1
    70 2
    80 3
    90 4
    30 1
    40 5
    10 1
    20 2
    5
    解答如下:

    #include<iostream>
    using namespace std;
    int main(){
      
      int a[1000]={0};
      int b[1000]={0};
      int count=0;
      int N,val,i,j;
      cin>>N;
      for(i=1;i<N+1;i++)
      {
        cin>>val;
        a[i]=val;
        
    }//首先将元素个数以及内容全部输入
    for(i=1;i<=N;i++)
    {
     	for(j=1;j<=i;j++)
     	{
      		if(b[j]+a[i]<=100)
      		//因为b[j]初始值为零,所以当j=i时,这个条件必然满足,从而能够输出每一项,没有必要分析另外一种情况
      		{
       			b[j]+=a[i];
       			//用b[ ]这个数组来表示箱子实际所装物品的情况
       			cout<<a[i]<<" "<<j<<endl;
       			//如果新的一项物品可以装到之前已装箱的某个箱子里,那么就在对应项上相加
       			if(j>count)
       			{
        				count=j;
        				 //j表示实际装箱的编号,其中最大的那个值就是所用箱子的总数
       			}
      
       			break;
      		}
      
     
     	}
      }
    		cout<<count;
    }
    
    展开全文
  • 7-3 两个有序序列的中位数 (25 分)已知有两个等长的非降序序列S1, S2, 设计函数求S1与S2并集的中位数。有序序列A​0​​,A​1​​,⋯,A​N−1​​的中位数指A​(N−1)/2​​的值,即第⌊(N+1)/2⌋个数(A​0​​为...

    7-3 两个有序序列的中位数 (25 分)已知有两个等长的非降序序列S1, S2, 设计函数求S1与S2并集的中位数。有序序列A​0​​,A​1​​,⋯,A​N−1​​的中位数指A​(N−1)/2​​的值,即第⌊(N+1)/2⌋个数(A​0​​为第1个数)。
    输入格式:
    输入分三行。第一行给出序列的公共长度N(0<N≤100000),随后每行输入一个序列的信息,即N个非降序排列的整数。数字用空格间隔。
    输出格式:
    在一行中输出两个输入序列的并集序列的中位数。
    输入样例1:
    5
    1 3 5 7 9
    2 3 4 5 6

    输出样例1:
    4

    输入样例2:
    6
    -100 -10 1 1 1 1
    -50 0 2 3 4 5
    输出样例2:
    1
    解题思路:
    (1)将两个序列合并成一个序列,然后进行排序,排序之后取出新序列的中位数。
    (2)中位数算法:首先将两个序列分别排序变成两个升序序列,分别求两个升序序列A、B的中位数,设为a和b。
    若a=b,则a或b即为所求的中位数;
    否则,舍弃a、b中较小者所在序列之较小一半,同时舍弃较大者所在序列之较大一半,要求两次舍弃的元素个数相同。当A长度位奇数时,左半边=右半边,直接舍弃即可。当A长度位为偶数时,左半边+1=右半边。若a<b,舍弃a的左半边(包括中点)舍弃b的右半边(保留中点)始终保持A B 等长。
    在保留的两个升序序列中,重复上述过程,直到两个序列中均只含一个元素时为止,则较小者即为所求的中位数。
    中位数算法的程序如下:

    #include <iostream>
    using namespace std;
    int al,ar,amid,bl,br,bmid;
    int a[100]={0};
    int b[100]={0};
    int FindMid(int al,int ar,int bl,int br)
    {
    	while(1)
    	{
    		amid=(ar+al)/2;
    		bmid=(br+al)/2;
    		if(al==ar&&bl==br)
    		{
    			if(a[al]<b[bl])
    			return a[al];
    			else
    			return b[bl];
    		}
    		else
    		{	
    			if((ar+al)%2==0)
    			{
    				if(a[amid]<b[bmid])
    				{
    					al=amid;
    					br=bmid;
    				}
    				else
    				{
    					bl=bmid;
    					ar=amid;
    					
    				}
    			else
    			{
    				if(a[amid]<b[bmid])
    				{
    					al=amid+1;
    					br=bmid;
    				}
    				else
    				{
    					bl=bmid+1;
    					ar=amid;
    					}
    			}
    		}
    	}
    
    int main()
    {
    	int num;
    	int result;
    	cin>>num;
    	for(int i=0;i<num;i++)
    	{
    		cin>>a[i];
    		}
    	for(int i=0;i<num;i++)
    	{
    		cin>>b[i];
    		}
    	result=FindMid(0,num-1,0,num-1);
    	cout<<result<<endl;
    	}
    
    
    展开全文
  • 6-2 顺序表操作(20 分) 本题要求实现顺序表的操作。 函数接口定义: List MakeEmpty(); Position Find( List L, ElementType X ); bool Insert( List L, ElementType X, Position P ); bool ...
  • 7-4 求链式线性表的倒数第K项 (20 分)给定一系列正整数,请设计一个尽可能高效的...输出倒数第K个位置上的数据。如果这个位置不存在,输出错误信息NULL。 输入样例: 4 1 2 3 4 5 6 7 8 9 0 -1 输出样例: 7 ...
  • MOOC数据结构 第五周

    千次阅读 2020-08-01 13:40:31
    含有相同的字符 C.都是非空串 D.两个串的长度相等且对应位置的字符相同 3.若串str=“Software”,其子串的个数是(D )。 A.8 B.9 C.36 D.37 4.一个链串的节点类型定义为 #define NodeSize 6 typedef struct node ...
  • 06-图1 列出连通 (25分) 给定一个有N个顶点和E条边的无向图,请用DFS和BFS分别列出其所有的连通。假设顶点从0到N−1编号。进行搜索时,假设我们总是从编号最小的顶点出发,按编号递增的顺序访问邻接点。 输入...
  • MOOC笔记——用Tensorflow制作数据集

    千次阅读 2018-04-23 15:17:29
    使用tfrecords进行数据读取,会提高内存利用率。 存储训练数据的方法: 使用tf.train.Example()存储,训练数据的特征用键值对的形式表示,例如: 'img_raw': (图片)值 'label': 标签值(值是Bytelist/Floatlist/I...
  • 本博客是为了记录学习数据结构时做的题集,若代码有疏漏欢迎指出! ps:因为已经学过c++了所以就都用c++写了。
  • 3. 队列 3.1 什么是队列 数据插入:入队列(AddQ) 数据删除:出队列... 数据对象:一个有0个或多个元素的有穷线性表 操作:长度为MaxSize的队列Q∈Queue,队列元素item∈ElementType ...
  • //P4 打死我也不说 //若藏有“DSWYBS”,则这串字母必是沿行、列或斜45度方向依次排列的。 #include #include using namespace std; int r,l,x[6],y[6],index=0; string zfca=“DSWYBS”;...int xbx[8]={0,0,-1,-1,1,1,...
  • 题目分析:本题旨在测试各种不同的排序算法在各种数据情况下的表现。因此没有标准答案。本帖旨在给出各种排序算法的C++实现形式,并将结果进行比较、总结。希望能给大家带来帮助。 各种排序算法的代码: 1. 冒泡...
  • 题目链接:http://www.patest.cn/contests/mooc-ds/04-3 题目分析:这是一道考察“哈夫曼编码”的问题,但是这里大家不要陷入一个误区:就是一定要把哈夫曼树构造出来。我们首先分析一下题目的需求:  输入:第一...
  • 题目链接:http://www.patest.cn/contests/mooc-ds/07-2 题目分析:这是一道考察插入排序和归并排序的一道题。题目可能有点难以理解,这里稍加解释一下:  首先,输入的第一行是一个整型数,代表数据的个数。第二...
  • 题目链接:http://www.patest.cn/contests/mooc-ds/09-1 题目分析:这是一道考察哈希散列表的一道题。题目总体来说是比较简单的,但是可能有的同学英文不好,看不懂题意,这里简单解释一下。  输入的第一行是...
  • 题目分析:这是一道考察“并查”的问题,通过的人像2-1一样那么少。  首先输入的是一个整型数,代表网络中有多少个结点。  然后输入若干行,每行由1个字符,两个整数组成,字符为I代表增加连接,字符为C代表...
  • 研究对象 ... 本研究基于Canvas Network平台开放数据集,对数据集字段进行统计分析,并且选取有学习者自我评价数据的样本,探寻不同类型学习者在学习目标、期望学习时间、学习行为和学习成绩...
  • Udacity,Udemy和Coursera等大型开放式在线课程(MOOC)的网站为学习者提供了一种低成本,高效的知识获取方式。 业务分析主要依赖于计算机编码,是MOOC网站中的热门话题。 在这个项目中,我们旨在发现设计出色的...
  • 题目链接:http://www.patest.cn/contests/mooc-ds/06-2 题目分析:陈姥姥说,这是Dijstra算法的一道题。题目是中文的,这里就不再啰嗦了。有一点提示一下,咱们平时用的Dijistra算法,是用来求最短路径的。这道题...
  • 题目链接:http://www.patest.cn/contests/mooc-ds/06-3 题目分析:典型最小生成树问题,且只需输出树各边的权值之和出来就可以了。博主这里用的是Prim算法。 特别说明:  1. 用邻接矩阵表示图比较容易。保存...
  • 题目链接:http://www.patest.cn/contests/mooc-ds/06-5 题目分析:这是一道考察图的拓扑排序——关键路径问题。在作业06-4的基础上不仅要求每个点的最早开始时间,还要求每个点的最晚结束时间,除此之外,还要知道...
  • 题目链接:http://www.patest.cn/contests/mooc-ds/05-3 题目分析:这是一道考察图的广度优先遍历的一道题,... 用邻接表建立图,注意这道题有一个case数据量很大,如果用邻接矩阵肯定会吃不消的。建图时,注意是无...
  • 题目链接:http://www.patest.cn/contests/mooc-ds/08-1 题目分析:这是一道考察排序算法的一道题。如果对题目不懂的话,这里恰巧有一个中文题目,不妨看一下:  ...
  • 题目链接:http://www.patest.cn/contests/mooc-ds/03-3 题目分析:借助“栈”进行树的后续遍历。栈工作记录中必须注明刚才是在左子树还是在右子树中。  每次PUSH,times = 1;  每次POP检查栈顶记录的times:...
  • 本题要求实现给定二叉搜索树的5种常用操作。 函数接口定义: BinTree Insert( BinTree BST, ElementType X ); BinTree Delete( BinTree BST, ElementType X ); Position Find( BinTree BST, ElementType X );...
  • 2.2.1 什么是堆栈 后缀表达式 中缀表达式 前缀表达式 ...操作 Stack CreatStack(int MaxSize); int IsFull(Stack S,int MaxSize); void Push(Stack S,ElementType item); int IsEmpty(Stack S); ElementType
  • 链表及其实现–Mooc听课笔记 1.顺序存储 ` //2.1 第一节 简要介绍了按顺序存储时链表的结构,如下: typedef struct PolyNode* Polynominal; struct PolyNode{ int coef; int expon; Polynominal link; }; //2.1 第...

空空如也

空空如也

1 2 3 4 5 ... 16
收藏数 310
精华内容 124
关键字:

mooc数据集