房子收录于考研408

2026-05-12 2026-06-23 约 2600 字预计阅读 6 分钟 - 次阅读 - 条评论

数据结构真题部分大题

第五章树与二叉树

2014年求二叉树带权路径长度(WPL)

问题描述

给定一个二叉树T,采用二叉链表存储,结构为(left-weight-right),求出T的WPL(带权路径长度)

思路分析

求WPL就是求各叶节点的权值与其路径长度乘积然后求和

所以对于当前节点进行判断,若为叶节点则返回其权值与路径(也就是当前深度)的乘积,否则可以向下递归求其左右子树最后层层返回

代码

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17


//第二问给出二叉树的数据类型定义
typedef struct node
{
  int weight;
  struct node *left,*right;
}Tree;
//

int WPL(Tree *p,int h)//传入当前节点和当前深度,初始为传入(根节点,0)
{
  if(p->left==NULL&&p->right==NULL)
  {
    return p->weight*h;//为叶节点则返回其权值与路径(也就是当前深度)的乘积
  }else{
    return WPL(p->left,h+1) + WPL(p->right,h+1);//不为叶节点可以向下递归求其左右子树WPL之和;
  }
}

注意

当节点只有一个孩子时,会传入空指针,导致空指针异常,王道书上写到作为408算法题,不要求考虑边界条件.只要思想正确,代码逻辑正确,即可满分,无非就是加上if (p == NULL)return 0;

2017年求表达式树转中缀表达式

问题描述

给定一个表达式树T,输出等价的中缀表达式,如下

输出(a+b) * (c*(-d))

思路分析

对中序遍历进行改造即可,注意到除根节点符合所表达的算式外,任意子树都需要左右括号,所以进行左子树遍历前需要加左括号 (,进行右子树遍历后需要加右括号 )

代码

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22


//题目给出了节点定义
typedef struct node
{
  char data[10];
  struct node *left,*right;
}BTree;
//

void InThread(BTree *p,int h)//初始化传入(根节点,1) 因为需要判断是否为子树,要加左右括号,所以传入高度
{
  if(p==NULL)return;//空节点结束函数;
  if(p->left==NULL&&p->right==NULL)//如果是叶节点直接输出操作数,添加括号逻辑交给分支节点
  {
    printf("%s",p->data);
  }else{
    if(h>1)printf("(");//当前节点如果为分支节点且不为根结,则先加上左括号
    InThread(p->left,h+1)//递归遍历左子树
    printf("%s",p->data);//输出此分支节点的操作符
    InThread(p->right,h+1)//递归遍历右子树
    if(h>1)printf(")");//加回右括号
  }
}

注意

本题主要在于考虑清楚加括号逻辑(除根节点外,任意分支节点所表达的运算都需要加括号)

本题本质是改造中序遍历。根结点不加括号，非根的分支结点所代表的子表达式需要加括号。若遇到叶子结点，直接输出操作数；若遇到运算符结点，则按照“左子树、根、右子树”的顺序输出。对于单目运算符，例如 -d，其左子树可能为空，也可以用同样的递归逻辑处理。

第六章图

2021邻接矩阵无向图度的问题

问题描述

给定一个无向连通图,采用邻接矩阵存储,求出是否有EL路径存在

EL描述如下:

度位奇数的顶点个数为不大于2的偶数,则存在EL路径

思路分析

本题送分题

统计图中符合要求顶点个数,看是否符合个数为2或0(不超过2的偶数为0和2)

代码

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27


//本题给出了图的定义
typedef struct
{
  int numVertices,numEDges;//顶点数,边数
  int Edge[MAXV][MAXV];//邻接矩阵
}MGraph;
//

int IsExitEL(MGraph G)//补全方法
{
 int i,j,degree,count = 0;
 for(i = 0;i < G.numVertices;i++)
 {
    degree = 0;
    for(j = 0;j < G.numVertices;j++)
    {
      if(G.Edge[i][j]!=0)degree++;
    }
    if(degree%2!=0)count++;
 }
 if(count==0||count==2)
 {
  return 1;
 }else{
  return 0;
 }
}

注意

邻接矩阵中,某一行(列)中不为0元素的个数就是对应顶点的度,所以第一个for循环遍历所有顶点,每次循环里依次遍历对应顶点的度, 最后判断count数,所以本题空间复杂度为O(1)不需要额外空间,时间复杂度为O( $n^2$ )

2023邻接矩阵有向图度的问题

问题描述

给定一个有向图,采用邻接矩阵存储,求出图中出度大于入度的顶点总数且输出所有这些点

思路分析

遍历各顶点,各顶点再遍历行(出度),列(入度),分别统计,再比较

代码

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29


//本题给出了图的定义
typedef struct
{
  int numVertices,numEDges;//顶点数,边数
  char VerticeList[MAXV];//顶点表
  int Edge[MAXV][MAXV];//邻接矩阵
}MGraph;
//

int printVertices(MGraph G)//补全方法
{
  int i,j,count = 0,inDegree,outDegree;
  for(i = 0;i < G.numVertices;i++)
  {
    inDegree = 0;
    outDegree = 0;
    for(j = 0;j < G.numVertices;j++)
    {
      if(G.Edge[i][j]!=0)outDegree++;
      if(G.Edge[j][i]!=0)inDegree++;
    }
    if(outDegree > inDegree)
    {
      printf("%c",G.VerticeList[i]);
      count++;
    }
  }
  return count;
}

注意

邻接矩阵中,某一行(列)中不为0元素的个数就是对应顶点的度,所以第一个for循环遍历所有顶点,每次循环分两次判断对应顶点的出度和入度, 本题空间复杂度为O(1)不需要额外空间,时间复杂度为O( $n^2$ )

2024邻接矩阵有向图的拓扑序列问题

问题描述

给定一个有向图,采用邻接矩阵存储,求该图是否有唯一的拓扑结构

思路分析

通过一个入度数组,每次找出入度唯一为0的顶点删除,并让其所有临接顶点的入度-1,重复此过程,若进行了此图的顶点个数次,则意味着存在唯一的拓扑结构

代码

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65


//本题给出了图的定义
typedef struct
{
  int numVertices,numEDges;//顶点数,边数
  char VerticeList[MAXV];//顶点表
  int Edge[MAXV][MAXV];//邻接矩阵
}MGraph;
//

int uniquely(MGraph G)//补全方法
{
  int indegree[MAXV];//定义入度统计数组;长度为顶点数个数
  int visited[MAXV];//标记某顶点是否被删掉
  int i,j,k;
  int count = 0;//已经处理的个数
  //初始化
  for(i = 0;i<G.numVertices;i++)
  {
    indegree[i] = 0;
    visited[i] = 0;//0为未处理
  }

  for(i = 0;i<G.numVertices;i++)
  {
    for(j = 0;j<G.numVertices;j++)
    {
      if(G.Edge[i][j]!=0)
      {
        indegree[j]++;  //遍历每一列,求出对应顶点的入度
      }
    }
  }


  while(n<G.numVertices)
  {
    int zeroCount = 0;//当前入度为0的个数
    int pos = -1;//当前入度为0的位置(唯一的)
    for( i = 0;i<G.numVertices;i++)
    {
      if(visited[i]==0&&indegree[i]==0)
      {
        zeroCount++;
        pos = i;
      }
    }
    if(zeroCount!=1)return0;
    //来到这里,说明只有一个入度为0点;如果没有入度为零的点说明为环,如果大于1说明下一次删除有不同选择,拓扑序列不唯一
    visited[pos] = 1;
    count++;

    //关键逻辑,查找当前行的每一列,若当前入度为0顶点的有邻接顶点,则其邻接顶点对应列标(j)的入度-1
    for(j = 0;j<G.numVertices;j++)
    {
      if(G.Edge[pos][j]!=0)
      {
        indegree[j]--;
      }
    }
  }
  return 1;//所有顶点处理完毕



}

注意

本题关键理顺求入度逻辑,以及删除一个顶点后,其余顶点入度的变化

数据结构大题

数据结构真题部分大题

第五章树与二叉树

2014年求二叉树带权路径长度(WPL)

2017年求表达式树转中缀表达式

第六章图

2021邻接矩阵无向图度的问题

2023邻接矩阵有向图度的问题

2024邻接矩阵有向图的拓扑序列问题

相关内容

目录