一、选择题

选择题是随机的！我这只记录我错的三道

1、一个有n个结点的图，最多有（ A ）个连通分量。

A.n

B.1

C.0

D.n-1

最多n个点 一个点就是一个连通图 

最少1个连通图

 

二、程序填空题

1、要求建立一个无向图，采用邻接矩阵做为存储结构。
例如

输入信息为：

第一行给出图的顶点数n和边数e。

第二行给出n个字符，表示n个顶点的数据元素的值。

后面是e行，给出每一条边的两个顶点编号。

输出每个顶点的值以及各顶点的邻接点的值。
输入样例：

7 9
 
0123456
 
0 2
 
0 3
 
0 4
 
1 3
 
1 5
 
2 3
 
2 5
 
4 5
 
5 6

输出样例

0: 2 3 4
 
1: 3 5
 
2: 0 3 5
 
3: 0 1 2
 
4: 0 5
 
5: 1 2 4 6
 
6: 5

#include <stdio.h>
#define MVNum 100                 //最大顶点数 
typedef struct{ 
  char vexs[MVNum];           //存放顶点的一维数组 
  int arcs[MVNum][MVNum];     //邻接矩阵 
  int vexnum,arcnum;          //图的当前顶点数和边数 
}MGraph; 
void CreatMGraph(MGraph *G);/* 创建图 */
void printGraph(MGraph G);/*输出图 */
int main()
{
    MGraph G;
    CreatMGraph(&G);
    printGraph(G);
    return 0;
}
void CreatMGraph(MGraph *G)
{
    int i,j,k;
    char a;
    scanf("%d%d",&G->vexnum,&G->arcnum);
    getchar();
    for(i=0;i<G->vexnum;i++)
         scanf("%c",&G->vexs[i]); //第一空
    for(i=0;i<G->vexnum;i++)
         for(j=0;j<G->vexnum;j++)
            G->arcs[i][j]=0; //第二空
    for(k=0;k<G->arcnum;k++) 
    {  
        scanf("%d%d",&i,&j);     
        G->arcs[i][j]=1; //第三空    
        G->arcs[j][i]=1; //第四空
    }
}
void printGraph(MGraph G)
{
    int i,j;
    for(i=0;i<G.vexnum;i++)
    {
       printf("%c:",G.vexs[i]);
       for(j=0;j<G.vexnum;j++)
          if (G.arcs[i][j])  printf(" %c",G.vexs[j]);
       printf("\n");
    }
}

2、请把一个十进制数N转换为d进制数,并输出。

#include<iostream>
#include<stack>
using namespace std; 
int main()
{
    stack <int>s;
    int e;
    int N,d;
    cin>>N>>d;
    if(d==2 ||d==8|| d==16)
    {
        while(N)
        {
            s.push(N%d); //第一空  将N与d求余得到的d进制数压入栈 
            N=N/d;            
        }        
    }
    while(!s.empty())
    {
        e=s.top();  //第二空  获取栈顶元素e 
    
        s.pop();    //第三空  弹出栈顶元素 
        if(e>=10)
            cout<<char('a'+e-10);
        else
            cout<<e;
    }
    cout<<endl;
    return 0;    
}

3、计算二叉树深度。

#include<iostream>
using namespace std;
 
typedef struct BiNode
{                
    char data;                    
    struct BiNode *lchild,*rchild;    
}BiTNode,*BiTree;
 
 
void CreateBiTree(BiTree &T)
{    
    char ch;
    cin >> ch;
    if(ch=='#')  T=NULL;            
    else{                            
        T=new BiTNode;
        T->data=ch;                    
        CreateBiTree(T->lchild);    
        CreateBiTree(T->rchild);    
    }                                
}                                
 
int Depth(BiTree T)
{ 
    int m,n;
    if(!T) return 0;   //第一空     
    else 
    {                            
        m=Depth(T->lchild);   //第二空         
        n=Depth(T->rchild);   //第三空         
        if(m>n) return(m+1);        
        else return (n+1);
    }
}
 
int main()
{
    BiTree tree;
    CreateBiTree(tree);
    cout<<Depth(tree);
    return 0;
 
}

4、本题目要求以头插法建立单链表。

#include <stdio.h>
#include <stdlib.h>
 
typedef int ElemType;
typedef struct LNode
{
    ElemType data;
    struct LNode *next;
}LNode,*LinkList;
 
LinkList Create();
void print( LinkList L);
 
int main()
{
      LinkList L = Create();
      print(L);
      return 0;
}
LinkList Create()
{
    LinkList L,s;
    ElemType e;
    L = (LinkList)malloc(sizeof(LNode));
    
    L->next=NULL;  //第一空
    scanf("%d",&e);
    while(e!=-1)
    {
        s = (LinkList)malloc(sizeof(LNode));
        s->data=e;
        
        s->next=L->next;  //第二空
        L->next=s;  //第三空
 
        scanf("%d",&e);
    }
    return L; //第四空
}
void print(LinkList L)
{ 
    LinkList p;
    p=L->next;
    while (p)
    {
         printf("%d ", p->data);
         p =p->next;
    }
}

三、函数题

R6-1 计算二叉树的叶子数

本题是计算二叉树中叶子结点的个数。

函数接口定义：

int num (Bptr p);

裁判测试程序样例：

#include <stdio.h>
#include <malloc.h>
typedef struct node
{
    int data;
    struct node *Lson,*Rson;
}Bnode,*Bptr;
 
int num (Bptr p);
 
Bptr creat()
{
    Bptr p;
    int x;
    scanf("%d",&x);
    if(x==0)
        return NULL;
    p=(Bptr)malloc(sizeof(Bnode));
    p->data=x;
    p->Lson=creat();
    p->Rson=creat();
    return p;
}
 
int main()
{
  Bptr root;    
    int k;    
    root=creat();
  k=num(root);
  printf("%d\n", k);
  return 0;
 
}
 
/* 请在这里填写答案 */

 

输入样例：

3 4 1 0 0 0 2 0 0

输出样例：

2

int num (Bptr p)
{
    if(p)
    {
        if(!p->Lson&&!p->Rson)
            return 1+num(p->Lson)+num(p->Rson);
        else return num(p->Lson)+num(p->Rson);
    }
    return 0;
}

R6-2 实现基于邻接矩阵表示的深度优先遍历 

实现基于邻接矩阵表示的深度优先遍历。

函数接口定义：

void DFS(Graph G, int v);

其中 G 是基于邻接矩阵存储表示的无向图，v表示遍历起点。

裁判测试程序样例：

#include <stdio.h>
#include <stdlib.h>
#define MVNum 10
                        
int visited[MVNum];
typedef struct{ 
    char vexs[MVNum];                    
    int arcs[MVNum][MVNum]; 
    int vexnum,arcnum;             
}Graph;
 
void CreateUDN(Graph &G);//实现细节隐藏
void DFS(Graph G, int v);
void DFSTraverse(Graph G){ 
    int v;
    for(v = 0; v < G.vexnum; ++v)  visited[v] = 0;    
    for(v = 0; v < G.vexnum; ++v)
        if(!visited[v])  DFS(G, v); 
}
int main(){
    Graph G;
    CreateUDN(G);
    DFSTraverse(G);
    return 0;
}
 
/* 请在这里填写答案 */

输入样例：

输入第1行为结点数vexnum和边数arcnum。第2行为结点的值，依次输入arcnum行，每行输入两个结点的值表示该两个结点互为邻接点。

8 8
ABCDEFGH
A B
A C
B D
B E
C F
C G
D H
E H

输出样例：

遍历序列。

A B D H E C F G 

void DFS(Graph G, int v)
{
    visited[v]=1;
    printf("%c ",G.vexs[v]);
    
    for(int i=0;i<G.vexnum;i++)
    {
        if(G.arcs[v][i]==1&&visited[i]==0)
            DFS(G,i);
    }
}

四、编程题

R7-1 冒泡排序

输入格式:

输入在第1行中给出N（1<N≤100），在第2行中给出N个待排序的整数，数字间以空格分隔，并保证数字没有重复的出现。

输出格式:

给出冒泡排序每一遍后的中间结果数列，数字间以空格分隔，但末尾不得有多余空格。注意：当排序完成时应立即停止。

输入样例1:

7
4 5 7 6 3 2 1

输出样例1:

4 5 6 3 2 1 7
4 5 3 2 1 6 7
4 3 2 1 5 6 7
3 2 1 4 5 6 7
2 1 3 4 5 6 7
1 2 3 4 5 6 7

输入样例2:

6
1 2 3 6 5 4

输出样例2:

1 2 3 5 4 6
1 2 3 4 5 6

#include <iostream>
using namespace std;
 
int main()
{
    int n,a[101];
    cin>>n;
    for(int i=0;i<n;i++) cin>>a[i];
    
    for(int i=0;i<n-1;i++)
    {   
        int flag=0;
    
        for(int j=0;j<n-1-i;j++)
            if(a[j]>a[j+1]) 
                swap(a[j],a[j+1]),flag=1;
        
        if(!flag) break;
 
        cout<<a[0];
        for(int k=1;k<n;k++) cout<<' '<<a[k];
        if(i!=n-2) cout<<endl;
    }
        
}

R7-2 查找最接近的元素

在非降序排列的序列中，查找最接近x的元素。

输入格式:

第一行是n值；（1<=n<=105)

第二行是n个元素; （元素值<=109）

第三行是m值，表示有m次查询；
第四行有m个数，分别是要查询的x.

输出格式:

对于每次查询，输出最接近x的元素值。若有多个，输出最小那个。

输入样例:

5
0 1 7 8 9
2
3 8

输出样例:

1
8

不是二分的解法 最后一个点喜闻乐见的运行超时 这题用二分就不会 我第一次在考场上写的就是这

#include <iostream>
#include <cmath>
using namespace std;
const int N=1e5+10;
int main()
{
    int n,a[N],m,x,t,res;
    cin>>n;
    for(int i=0;i<n;i++) cin>>a[i];
    cin>>m;
    while(m--)
    {
        cin>>x;
        int minx=0x3f3f3f3f;
        for(int i=0;i<n;i++)
        {
            t=abs(a[i]-x);
            if(t<=minx)
            {
                minx=t;
                res=a[i];
            }
        }
        cout<<res<<endl;
    }
        
}

二分——教材：

#include <iostream>
#include <cmath>
using namespace std;
 
const int N=1e5+10;
int n,a[N],m,x;
 
int dic(int a[],int x)
{
    int l=0,r=n-1;
    while(l<r)
    {
        int mid=l+r>>1;
        if(a[mid]==x) return x;
        else if(a[mid]>x) r=mid-1;
        else l=mid+1;
    }
    if(abs(a[l]-x) < abs(a[r]-x)) return a[l];
    else if(abs(a[l]-x) >= abs(a[r]-x)) return a[r];
}
 
int main()
{
    cin>>n;
    for(int i=0;i<n;i++) cin>>a[i];
    cin>>m;
    
    while(m--)
    {
        cin>>x;
        cout<<dic(a,x)<<endl;
    }
        
}

二分——acw模板 

#include <bits/stdc++.h>
using namespace std;
 
const int N=1e5+10;
int a[N];
int n,q,x;
 
void solve()
{
	
		cin>>x;
		int l=1,r=n;
		while(l<r)  //res1为大于x的最小值
		{
			int mid=l+r>>1;
			if(a[mid]>=x)r=mid;
			else l=mid+1;
		}
		int res1=a[r];
 
		l=1,r=n;
		while(l<r)  //res2为小于x的最大值
		{
			int mid=l+r+1>>1;
			if(a[mid]<=x)l=mid;
			else r=mid-1;
		}
		int res2=a[r];
 
		if(abs(x-res1) < abs(x-res2)) cout<<res1<<endl;
		else cout<<res2<<endl; 
}
 
signed main()
{
    cin>>n;
	for(int i=1;i<=n;i++)cin>>a[i];
	cin>>q;
	while(q--)
	{
        solve();
    }
    return 0;
}