hsd数据结构期末考

2023-12-17 21:50
文章标签 数据结构 期末考 hsd

本文主要是介绍hsd数据结构期末考,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

考题1:有序表归并算法实现

问题描述:对任意输入的两个按值非递减有序的整数序列,写一程序将它们归并成一个按值非递减有序序列

输入描述:文本文件"input.txt"中保存了n个测试用例,文件以-1结束。每个用例的第一行m1表示第一个待归并有序序列的元素个数,第二行为该序列的m1个元素,第三行m2表示第二个待归并有序序列的元素个数,第四行为该序列的m2个元素

输出描述:输出结果保存在文本文件"output.txt"中。对于每个测试用例均有二行输出,第一行输出"Case #:##",#表示用例的编号(1…n),##表示归并后有序序列的元素个数;第二行输出##个按值非递减有序元素

输入示例:

​ 5

​ 1 4 8 10 30

​ 7

​ 2 4 20 35 50 60 86

​ 3

​ 38 45 100

​ 4

​ 38 45 100 120

​ -1

输出示例:

​ Case 1:12

​ 1 2 4 4 8 10 20 30 35 50 60 86

​ Case 2:7

​ 38 38 45 50 100 100 120

本题使用 有序表 相关知识

SqList.h

#ifndef SQLIST_H
#define SQLIST_H
#include"Public.h"
#define LIST_INIT_SIZE 2000
#define LISTINCREMENT 100typedef int Elemtype;
typedef struct{ElemType* elem;int length;int listsize;
}SqList;void MergeList1(SqList La,SqList Lb,SqList& Lc);
Status InitList_Sq(SqList& L);
void GetElem(SqList L,int i,ElemType& e);
Status ListInsert_Sq(SqList& L,int i,Element e);
void FPrint(SqList L,int CaseID,FILE* fout);
int FRead(SqList& L,FILE* fin);
void DestroyList_Sq(SqList& L);
#endif

SqList.cpp

#include<stdio.h>
#include<stdlib.h>
#include "Public.h"
#include "SqList.h"Status InitList_Sq(SqList& L)
{MALLOC(L.elem,LIST_INIT_SIZE * sizeof(ElemType),ElemType*);L.length = 0;L.listsize = LIST_INIT_SIZE;return OK;
}int FRead(SqList& L,FILE* fin)
{int n;fscanf(fin,"%d",&n);if(-1 == n) return n;L.length = n;for(int i = 0;i < n;i++){fscanf(fin,"%d",&L.elem[i]);  }return OK;
}void MergeList1(SqList La,SqList Lb,SqList& Lc)
{int i,j,k,La_len,Lb_len;ElemType ai,bj;La_len = La.length;Lb_len = Lb.length;i = j = 1;k = 0;while(i <= La_len && j < Lb_len){GetElem(La,i,ai);GetElem(Lb,j,bj);if(ai <= bj){ListInsert_Sq(Lc,++k,ai);++i;}else{ListInsert_Sq(Lc,++k,bj);++j}}while(i <= La_len){GetElem(La,i++,ai);ListInsert_Sq(Lc,++k,ai);}while(j <= Lb_len){GetElem(Lb,j++,bj);ListInsert_Sq(Lc,++k,bj);}
}void GetElem(SqList L,int i,ElemType& e)
{e = L.elem[i-1];
}Status ListInsert_Sq(SqList& L,int i,ElemType e)
{//在顺序线性表L中第i个位置之前插入新的元素eElemType* p,* q,* newBase;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]);			//q指示插入位置for(p = &(L.elem[L.length - 1]);p >= q; --p)*(p+1) = *p;					//插入位置及之后的元素右移*q = e;++L.length;							//表长增加1return OK;
}void FPrint(SqList L,int CaseID,FILE* fout)
{fprintf(fout,"Case &d:%d\n",CaseID,L.length);for(int i = 0;i < L.length;i++){fprintf(fout,"%d",L.elem[i]);}fprintf(fout,"\n");
}void DestroyList_Sq(SqList& L)
{FREE(L.elem);L.length = 0;
}

main.cpp

#include<stdio.h>
#include<stdlib.h>
#include"Public.h"
#inlcude"SqList.h"
void main()
{int ID = 1;SqList La,Lb,Lc;InitList_Sq(La);InitList_Sq(Lb);InitList_Sq(Lc);FILE* fin,* fout;fin = fopen("input.txt","r");fout = fopen("output.txt","w");while(FRead(La,fin) == OK){FRead(Lb,fin);MergeList1(La,Lb,Lc);FPrint(Lc,++ID,fout);DestroyList_Sq(La);DestroyList_Sq(Lb);DestroyList_Sq(Lc);}fclose(fout);fclose(fin);system("pause"); 
}

考题3:二叉树的中序非递归遍历算法实现

问题描述:对任意输入的表示某二叉树的字符序列,实现二叉树的中序非递归遍历算法,并输出其遍历结果

输入描述:从键盘上输入一串字符串,该字符串为二叉树的带#号的先序遍历结果,其中如果遍历到空树时用字符#代替

输出描述:从键盘输出二叉树的中序遍历结果

输入与输出示例:

​ 输入:

​ +A##/*B##C##D##

​ 输出:

​ A+B*C/D

​ 输入:

​ ABD##GJ###CFH##I###

​ 输出:

​ DBJGAHFIC

本题用到堆栈 和 树 相关知识

BiTree.h 文件

#ifndef BITREE_H
#define BITREE_H
struct node;
typedef struct node *treePointer;
typedef struct node{char data;treePointer leftChild,rightChild;
};
treePointer Create();
void iterInorder(treePointer node);
#endif

SqStack.h文件

#ifndef SQSTACK_H
#define SQSTACK_H
#include "Public.h"
#include "BiTree.h"
typedef treePointer element;
int Push_Sq(element item,element* stack,int& top);
int Pop(element* stack,int& top,element& item);
#endif

BiTree.cpp文件

#include<stdio.h>
#include<stdlib.h>
#include"Public.h"
#include"BiTree.h"
#include"SqStack.h"treePointer Create()
{treePointer bt;char ch;scanf("%c",&ch);if(ch == '#') bt = NULL;else{MALLOC(bt,sizeof(struct node),treePointer);bt->data = ch;bt->leftChild = Create();bt->rightChild = Create();}return bt;
}void iterInorder(treePointer node)
{int top = -1;element stack[MAX_STACK_SIZE];for(;;){for(;node = node->leftChild)Push_Sq(node,stack,top);int Flag = Pop(stack,top,node);if(!Flag) break;printf("%c",node->data);node = node->rightChild;}
}

SqStack.cpp文件

#include<stdio.h>
#include<stdlib.h>
#include"Public.h"
#include"SqStack.h"
#include"BiTree.h"int Push_Sq(element item,element* stack,int& top)
{if(top >= MAX_STACK_SIZE - 1){return FALSE;}stack[++top]  = item;return TRUE;
}int Pop(element* stack,int& top,element& item)
{if(top == -1) return FALSE;item = stack[top--];return TRUE;
}

main.cpp文件

#include<stdio.h>
#include<stdlib.h>
#include"Public.h"
#include"BiTree.h"
#include"SqStack.h"void main()
{treePointer bt;bt = Create();iterInorder(bt);printf("\n");system("pause");
}

考题4:二叉树层次遍历算法实现

问题描述:对任意输入的表示某二叉树的字符序列,实现二叉树的层次遍历算法,并输出其遍历结果

输入描述:从键盘上输入一串字符串,该字符串为二叉树的带#号的先序遍历结果,其中如果遍历到空树时用字符#代替

输出描述:从键盘输出二叉树的按层次遍历结果

输入与输出示例

​ 输入:

​ +A##/*B##C##D##

​ 输出:

​ +A/*DBC

​ 输入:

​ ABD##GJ###CFH##I###

​ 输出:

​ ABCDGFJHI

本题用 堆栈 和 二叉树 相关知识

BiTree.h

#ifndef BITREE_H
#define BITREE_H
struct node;
typedef struct node *treePointer;
typedef struct node{char data;treePointer leftChild,rightChild;
};
treePointer Create();
void levelOrder(treePointer ptr);
#endif

SqStack.h

#ifndef SQSTACK_H
#define SQSTACK_H
#include "Public.h"
#include "BiTree.h"
typedef treePointer,element;
int AddQ(element item,element *queue,int front,int &rear);
int DeleteQ(element *queue,int &front,int rear, element &item);
#endif

BiTree.cpp

#include<stdio.h>
#include<stdlib.h>
#include "Public.h"
#include "BiTree.h"
#include "SqStack.h"treePointer Create()
{treePointer bt;char ch;scanf("%c",&ch);if(ch == '#') bt = NULL;else{MALLOC(bt,sizeof(struct node),treePointer);bt->data = ch;bt->leftChild = Create();bt->rightChild = Create();}return bt;
}void levelOrder(treePointer ptr)
{int front = 0,rear = 0;element queue[MAX_QUEUE_SIZE];if(!ptr) return ;										/* empty tree */AddQ(ptr,queue,front,rear);					/* push the root onto queue */for(;;){int Flag = DeleteQ(queue,front,rear,ptr);				/* pop one node from queue */if(Flag){printf("%c",ptr->data);/* if leftChild is not NULL,push it onto queue*/if(ptr->leftChild) AddQ(ptr->leftChild,queue,front,rear); /* if rightChild is not NULL,push it onto queue*/if(ptr->rightChild) AddQ(ptr->rightChild,queue,front,rear);}else break;}
}

SqStack.cpp

#include<stdlib.h>
#include<stdio.h>
#include "Public.h"
#include "BiTree.h"
#include "SqStack.h"int AddQ(element item,element *queue,int front,int &rear)
{rear = (rear+1) % MAX_QUEUE_SIZE;if(front == rear) return FALSE;queue[rear] = item;return TRUE;
}int DeleteQ(element *queue,int &front,int rear,element &item)
{if(front == rear) return FALSE;front = (front + 1) % MAX_QUEUE_SIZE;item = queue[front];return TRUE;
}

main.cpp

#include<stdio.h>
#include<stdlib.h>
#include"Public.h"
#include"BiTree.h"
#include"SqStack.h"void main()
{treePointer bt;bt = Create();levelOrder(bt);printf("\n");system("pause");
}

考题5:堆排序算法实现

问题描述:对于任一无序正整数序列,写一程序用堆排序算法将其排序成按值非递减有序序列。

输入描述:文本文件“input.txt”中保存了n个测试用例,文件以-1结束。每个用例的第一行m表示待排序正整数序列的元素个数,第二行为该序列的m个正整数

输出描述:输出结果保存在文本文件“output.txt”中。对于每个测试用例均有二行输出,第一行输出“Case #:##”,#表示用例的编号(1…n),##表示排序后有序序列的元素个数,第二输出##个按值非递减有序元素

输入示例:

5

10 1 8 4 30

7

35 60 50 2 20 4 86

3

38 100 45

-1

输出示例:

​ Case 1:5

​ 1 4 8 10 30

​ Case 2:7

​ 2 4 20 35 50 60 86

​ Case 3:3

​ 38 45 100

本题考查堆排序算法

main.cpp

#include <stdio.h>
#include <stdlib.h>#define  MAX_SIZE 5000
#define SWAP(x,y,t) ( (t)=(x),(x)=(y),(y)=(t))
#define LeftChild(i) (2*(i)+1)
typedef int ElemType;
int FRead(FILE *fin,ElemType A[], int &N);
void FPrint(ElemType A[],int N,FILE*fout,int CaseID);	
void Heapsort (ElemType A[],int N);
void PercDown(ElemType A[],int i,int N);int main()
{ElemType A[MAX_SIZE];FILE *fin,*fout;int n;fin = fopen("input.txt","r");fout = fopen("output.txt","w");int CaseID = 0;while(1){if(FRead(fin,A,n) == -1) break;Heapsort(A,n);FPrint(A,n,fout,++CaseID);}fclose(fout);fclose(fin);system("pause");
}int FRead(FILE *fin,ElemType A[],int &N)
{fscanf(fin,"%d",&N);if(-1 == N) return N;for(int i = 0;i < N;i++)fscanf(fin,"%d",&A[i]);return 0;
}void FPrint(ElemType A[],int N,FILE *fout,int CaseID)
{fprintf(fout,"Case %d:%d\n",CaseID,N);fprintf(fout,"%d",A[0]);for(int i = 1;i < N;i++) fprintf(fout,"%5d",A[i]);fprintf(fout,"\n");
}void Heapsort(ElemType A[],int N)
{int i;ElemType temp;for(i = N / 2 - 1;i >= 0;i--)			//BuildHeapPercDown(A,i,N);for(i = N - 1;i > 0;i--){SWAP(A[0],A[i],temp);						//DeleteMaxPercDown(A,0,i);}
}void PercDown(ElemType A[],int i,int N)
{int Child;ElemType Temp;for(Temp = A[i];LeftChild(i) < N;i = Child){Child = LeftChild(i);if(Child != N - 1 && A[Child + 1] > A[Child])Child++;if(Temp < A[Child])A[i] = A[Child];elsebreak;}A[i] = Temp;
}

考题6:快速排序算法实现

问题描述:对于任意的无序正整数序列,写一程序用快速排序算法将其排序成按值非递减有序序列

输入描述:文本文件“input.txt”中保存了n个测试用例,文件以-1结束。每个用例的第一行m表示第一个待排序整数序列的元素个数,第二行为该序列的m个元素

输出描述:输出结果保存在文本文件“output.txt”中。对于每个测试用例均有二行输出,第一行输出“Case #:##”,#表示用例的编号(1…n),##表示排序后有序序列的元素个数,第二输出##个按值非递减有序元素

输入示例:

5

10 1 8 4 30

7

35 60 50 2 20 4 86

3

38 100 45

-1

输出示例:

​ Case 1:5

​ 1 4 8 10 30

​ Case 2:7

​ 2 4 20 35 50 60 86

​ Case 3:3

​ 38 45 100

本题考查快速排序算法

main.cpp

#include<stdio.h>
#include<stdlib.h>#define MAX_SIZE 5000
#define SWAP(x,y,t) ((t) = (x),(x) = (y),(y) = (t))
typedef int ElemType;
int FRead(FILE *fin,ElemType A[],int &N);
void FPrint(ElemType A[],int N,FILE *fout,int CaseID);
void quickSort(ElemType A[],int left,int right);
int Partition(ElemType A[],int left,int right);int main()
{ElemType A[MAX_SIZE];FILE *fin,*fout;int n;fin = fopen("input.txt","r");fout = fopen("output.txt","w");int CaseID = 0;while(1){if(FRead(fin,A,n) == -1) break;quickSort(A,0,n-1);FPrint(A,n,fout,++CaseID);}fclose(fout);fclose(fin);system("pause");
}int FRead(FILE *fin,ElemType A[],int &N)
{fscanf(fin,"%d",&N);if(-1 == N) return N;for(int i = 0;i < N;i++)fscanf(fin,"%d",&A[i]);return 0;
}void FPrint(ElemType A[],int N,FILE *fout,int CaseID)
{fprintf(fout,"Case %d:%d\n",CaseID,N);fprintf(fout,"%d",A[0]);for(int i = 1;i < N;i++) fprintf(fout,"%5d",A[i]);fprintf(fout,"\n");
}void quickSort(ElemType A[],int left,int right)
{if(left < right){int nextWhere = Partition(A,left,right);quickSort(A,left,nextWhere - 1);quickSort(A,nextWhere + 1,right);}
}int Partition(ElemType A[],int left,int right)
{ElemType pivot = A[left];ElemType temp;while(left < right){while(pivot < A[right]) --right;while(pivot > A[left]) ++left;SWAP(A[right],A[left],temp);}A[left] = pivot;return left;
}

考题7:深度优先搜索

问题描述:写一程序实现图的深度优先搜索算法(DFS),并对输入的有向网或无向网输出遍历结果

输入描述:文本文件“input.txt”中保存了一个有向网的输入,文件以-1结束。第一行表示该网的顶点数n(输入示例中为6)和弧数m(输入示例中为11);接下去m行是用(i,j,e)表示的弧,它表示从顶点i出发到顶点j的权值为e的弧。最后几行分别表示从这些顶点出发进行DFS,输出它们的结果

输出描述:输出结果保存在文本文件“output.txt”中。对每个开始搜索的顶点,都有一行,该行表示从该顶点出发进行DFS的结果

输入示例:

​ 6 11

​ 0 1 50

​ 0 2 10

​ 0 4 45

​ 1 2 15

​ 1 4 10

​ 2 0 20

​ 2 3 15

​ 3 1 20

​ 3 4 35

​ 4 3 30

​ 5 3 3

​ 1

​ 3

​ -1

输出示例:

​ DFS From V1: V1 V4 V3 V2 V0

​ DFS From V3: V3 V4 V1 V2 V0

image-20211227113308156

本题考查图 和 队列 相关知识

Graph.h

#ifndef GRAPH_H
#define GRAPH_H
#include"Public.h"struct node;
typedef struct node *nodePointer;
typedef struct node{int vertex;nodePointer next;int weight;
};void CreateGraph(FILE *fin,nodePointer graph[],int &n);
void PrintGraph(nodePointer graph[],int n);
void dfs(int v,nodePointer graph[],int n,short int visited[],FILE *fout);
#endif

Graph.cpp

#include<stdio.h>
#include<stdlib.h>
#include"Public.h"
#include"Graph.h"
#include"SqQueue.h"int b,c,d;
int front = 0,rear = 0;
void CreateGraph(FILE *fin,nodePointer graph[],int &n)
{int a;fscanf(fin,"%d %d",&n,&a);int q = -1;for(int i = 0;i < a;i++){nodePointer m;MALLOC(m,sizeof(node),nodePointer);fscanf(fin,"%d %d %d",&b,&c,&d);m->vertex = c;m->weight = d;if(q == b){m->next = graph[b];graph[b] = m;}else{m->next = NULL;graph[b] = m;}q = b;}
}void PrintGraph(nodePointer graph[],int n)
{nodePointer p;for(int i = 0;i < n;i++){printf("%d:",i);p = graph[i];while(p){printf("%d ",p->vertex);p = p->next;}printf("\n");}
}void dfs(int v,nodePointer graph[],int n,short int visited[],FILE *fout)
{nodePointer w;visited[v] = TRUE;fprintf(fout,"V%d ",v);for(w = graph[v];w;w = w->next)if(!visited[w->vertex])dfs(w->vertex,graph,n,visited,fout);
}

main.cpp

#define  _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <stdlib.h>
#include <memory.h>
#include "Public.h"
#include "Graph.h"void main (){nodePointer graph[MAX_VERTICES];int n=0;short int visited[MAX_VERTICES];memset(visited,FALSE,sizeof(short int) * MAX_VERTICES);FILE *fin,*fout;int v0=0;fin=fopen("input.txt","r");fout=fopen("output.txt","w");CreateGraph(fin,graph,n);while(true){fscanf(fin,"%d",&v0);if(v0==-1)break;fprintf (fout, "DBS From V%d:",v0) ;memset(visited,FALSE,sizeof(short int) * MAX_VERTICES);dfs(v0,graph,n,visited,fout);fprintf (fout, "\n" ) ;}PrintGraph(graph,6);fclose(fin);fclose(fout);system("pause");}

这篇关于hsd数据结构期末考的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/505983

相关文章

【数据结构】——原来排序算法搞懂这些就行,轻松拿捏

前言:快速排序的实现最重要的是找基准值,下面让我们来了解如何实现找基准值 基准值的注释:在快排的过程中,每一次我们要取一个元素作为枢纽值,以这个数字来将序列划分为两部分。 在此我们采用三数取中法,也就是取左端、中间、右端三个数,然后进行排序,将中间数作为枢纽值。 快速排序实现主框架: //快速排序 void QuickSort(int* arr, int left, int rig

6.1.数据结构-c/c++堆详解下篇(堆排序,TopK问题)

上篇:6.1.数据结构-c/c++模拟实现堆上篇(向下,上调整算法,建堆,增删数据)-CSDN博客 本章重点 1.使用堆来完成堆排序 2.使用堆解决TopK问题 目录 一.堆排序 1.1 思路 1.2 代码 1.3 简单测试 二.TopK问题 2.1 思路(求最小): 2.2 C语言代码(手写堆) 2.3 C++代码(使用优先级队列 priority_queue)

《数据结构(C语言版)第二版》第八章-排序(8.3-交换排序、8.4-选择排序)

8.3 交换排序 8.3.1 冒泡排序 【算法特点】 (1) 稳定排序。 (2) 可用于链式存储结构。 (3) 移动记录次数较多,算法平均时间性能比直接插入排序差。当初始记录无序,n较大时, 此算法不宜采用。 #include <stdio.h>#include <stdlib.h>#define MAXSIZE 26typedef int KeyType;typedef char In

【408数据结构】散列 (哈希)知识点集合复习考点题目

苏泽  “弃工从研”的路上很孤独,于是我记下了些许笔记相伴,希望能够帮助到大家    知识点 1. 散列查找 散列查找是一种高效的查找方法,它通过散列函数将关键字映射到数组的一个位置,从而实现快速查找。这种方法的时间复杂度平均为(

浙大数据结构:树的定义与操作

四种遍历 #include<iostream>#include<queue>using namespace std;typedef struct treenode *BinTree;typedef BinTree position;typedef int ElementType;struct treenode{ElementType data;BinTree left;BinTre

Python 内置的一些数据结构

文章目录 1. 列表 (List)2. 元组 (Tuple)3. 字典 (Dictionary)4. 集合 (Set)5. 字符串 (String) Python 提供了几种内置的数据结构来存储和操作数据,每种都有其独特的特点和用途。下面是一些常用的数据结构及其简要说明: 1. 列表 (List) 列表是一种可变的有序集合,可以存放任意类型的数据。列表中的元素可以通过索

浙大数据结构:04-树7 二叉搜索树的操作集

这道题答案都在PPT上,所以先学会再写的话并不难。 1、BinTree Insert( BinTree BST, ElementType X ) 递归实现,小就进左子树,大就进右子树。 为空就新建结点插入。 BinTree Insert( BinTree BST, ElementType X ){if(!BST){BST=(BinTree)malloc(sizeof(struct TNo

【数据结构入门】排序算法之交换排序与归并排序

前言         在前一篇博客,我们学习了排序算法中的插入排序和选择排序,接下来我们将继续探索交换排序与归并排序,这两个排序都是重头戏,让我们接着往下看。  一、交换排序 1.1 冒泡排序 冒泡排序是一种简单的排序算法。 1.1.1 基本思想 它的基本思想是通过相邻元素的比较和交换,让较大的元素逐渐向右移动,从而将最大的元素移动到最右边。 动画演示: 1.1.2 具体步

数据结构:线性表的顺序存储

文章目录 🍊自我介绍🍊线性表的顺序存储介绍概述例子 🍊顺序表的存储类型设计设计思路类型设计 你的点赞评论就是对博主最大的鼓励 当然喜欢的小伙伴可以:点赞+关注+评论+收藏(一键四连)哦~ 🍊自我介绍   Hello,大家好,我是小珑也要变强(也是小珑),我是易编程·终身成长社群的一名“创始团队·嘉宾” 和“内容共创官” ,现在我来为大家介绍一下有关物联网-嵌入

[数据结构]队列之顺序队列的类模板实现

队列是一种限定存取位置的线性表,允许插入的一端叫做队尾(rear),允许删除的一端叫做队首(front)。 队列具有FIFO的性质 队列的存储表示也有两种方式:基于数组的,基于列表的。基于数组的叫做顺序队列,基于列表的叫做链式队列。 一下是基于动态数组的顺序队列的模板类的实现。 顺序队列的抽象基类如下所示:只提供了接口和显式的默认构造函数和析构函数,在派生类中调用。 #i