全部知识点

请设计一个算法，将给定的表达式树(二叉树)转换为等价的中缀表达式(通过括号反映操作符的计算次序)并输出。例如，当下列两棵表达式树作为算法的输入时，输出的等价中缀表达式分别为(a+b) * (c * (-d)和(a * b)+(-(c-d))。

二叉树结点定义如下：

typedef struct node{
    char data[10];                 //存储操作数或操作符
    struct node *left, *right;
}BTree;

请回答下列问题。

（1）给出算法的基本设计思想。

（2）根据设计思想，采用C或C++语言描述算法，关键之处给出注释。

答：

（1）算法的基本设计思想

表达式树的中序序列加上必要的括号即为等价的中缀表达式。可以基于二叉树的中序遍历策略得到所需的表达式。(3分)

表达式树中分支结点所对应的子表达式的计算次序，由该分支结点所处的位置决定。为得到正确的中缀表达式，需要在生成遍历序列的同时，在适当位置增加必要的括号。显然，表达式的最外层(对应根结点)及操作数(对应叶结点)不需要添加括号。

（2）算法实现(10分)

void BtreeToE(BTree *root) {
    BtreeToExp(root,1); //根的高度为1
}
void BtreeToExp(BTree *root, int deep) {
    if(root == NULL) return;
    else if(root->left == NULL && root->right == NULL)//若为叶结点
        printf("%s",root->data);//输出操作数
    else {
        if(deep>1) printf("(");//若有子表达式则加1层括号
        BtreeToExp(root->left，deep+1);
        printf("%s",root->data); //输出操作符
        BtreeToExp(root->right,deep+1);
        if(deep>1) printf(")");//若有子表达式则加1层括号
    }
}

使用Prim(普里姆)算法求带权连通图的最小(代价)生成树(MST)。请回答下列问题。

（1）对下列图G，从顶点A开始求G的MST，依次给出按算法选出的边。

（2）图G的MST是唯一的吗？

（3）对任意的带权连通图，满足什么条件时，其MST是唯一的？

答：

（1）Prim算法属于贪心策略。算法从一个任意的顶点开始，一直长大到覆盖图中所有顶点为止。算法每一步在连接树集合S中顶点和其他顶点的边中，选择一条使得树的总权重增加最小的边加入集合S。当算法终止时，S就是最小生成树。

①S中顶点为A，候选边为(A,D)、(A,B)、(A,E)，选择(A,D)加入S。

②S中顶点为A、D，候选边为(A,B)、(A,E)、(D,E)、(C,D)，选择(D,E)，加入S。

③S中顶点为A、D、E，候选边为(A,B)、(C,D)、(C,E)，选择(C,E)加入S。

④S中顶点为A、D、E、C，候选边为(A,B)、(B,C)，选择(B,C)加入S。

⑤S就是最小生成树。

依次选出的边为：

(A，D),(D，E),(C，E),(B，C) （4分）

（2）图G的MST是唯一的。（2分）第一小题的最小生成树包括了图中权值最小的四条边，其他边都比这四条边大，所以此图的MST唯一。

（3）当带权连通图的任意一个环中所包含的边的权值均不相同时，其MST是唯一的。

已知，计算f(n)的C语言函数f1如下：

int f1(unsigned n){
    int sum=1, power=1;
    for(unsigned i=0;i<=n-1;i++){
        power *= 2;
        sum += power;
    }
    return sum;
}

将f1中的int都改为float，可得到计算f(n)的另一个函数f2。假设unsigned和int型数据都占32位，float采用IEEE754单精度标准。请回答下列问题。

（1）当n=0时，f1会出现死循环，为什么？若将f1中的变量和n都定义为int型，则f1是否还会出现死循环？为什么？

（2）f1(23)和f2(23)的返回值是否相等？机器数各是什么(用十六进制表示)？

（3）f1(24)和f2(24)的返回值分别为33 554 431和33 554 432.0，为什么不相等？

（4）f(31)=232-1，而f1(31)的返回值却为-1，为什么？若使f1(n)的返回值与f(n)相等，则最大的n是多少？

（5）f2(127)的机器数为7F80 0000H，对应的值是什么？若使f2(n)的结果不溢出，则最大的n是多少？若使f2(n)的结果精确(无舍入)。则最大的n是多少？

答：

（1）由于i和n是unsigned型，故“i<=n-1”是无符号数比较，n=0时，n-1的机器数为全1，值是232-1，为unsigned型可表示的最大数，条件“i<=n-1”永真，因此出现死循环。(2分)

若i和n改为int类型，则不会出现死循环。(1分)

因为“i<=n-1”是带符号整数比较，n=0时，n-1的值是-1，当i=0时条件“i<=n-1”不成立，此时退出for循环。(1分)

（2）f1(23)与f2(23)的返回值相等。（1分）f(23) = 223+1-1 = 224-1，它的二进制形式是24个1。int占32位，没有溢出。float有1个符号位，8个指数位，23个底数位，23个底数位可以表示24位的底数。所以两者返回值相等。

f1(23)的机器数是 00FF FFFFH。（1分）

f2(23)的机器数是 4B7F FFFFH。（1分）

显而易见前者是24个1，即 0000 0000 1111 1111 1111 1111 1111 1111（2），后者符号位是 0，指数位为 23+127(10) = 1001 0110（2），底数位是 111 1111 1111 1111 1111 1111（2）。

（3）当n=24时，f(24) = 1 1111 1111 1111 1111 1111 1111 B，而float型数只有24位有效位，舍入后数值增大，所以f2(24)比f1(24)大1。(1分)

（4）显然f(31)已超出了int型数据的表示范围，用f1(31)实现时得到的机器数为32个1，作为int型数解释时其值为-1，即f1(31)的返回值为-1。(1分)

因为int型最大可表示数是0后面加31个1，故使f1(n)的返回值与f(n)相等的最大n值是30。(1分)

（5）IEEE 754标准用“阶码全1、尾数全0”表示无穷大。f2返回值为float型，机器数7F80 0000H对应的值是+∞。(1分)当n=126时，f(126) = 2127-1 = 1.1…1×2126，对应阶码为127+126=253，尾数部分舍入后阶码加1，最终阶码为254，是IEEE 754单精度格式表示的最大阶码。故使f2结果不溢出的最大n值为126。(1分)当n=23时，f(23)为24位1，float型数有24位有效位，所以不需舍入，结果精确。故使f2获得精确结果的最大n值为23。(1分)

在按字节编址的计算机M上，题43中f1的部分源程序(阴影部分)与对应的机器级代码(包括指令的虚拟地址)如下：

     int fl(unsigned n)

1    00401020   55          push ebp

     ......        ...          ......

         for(unsigned i=0; i<=n-1; i++)

     ......        ...          ......

20   0040105E   39 4D F4    cmp dword ptr[ebq-0Ch],ecx

     ......        ...          ......

     {    power *= 2;

 ......        ...          ......

23   00401066 D1 E2      shl edx,1

 ......  ...         ......

  return sum;

 ......        ...           ......

35   0040107F C3           ret

  }

其中，机器级代码行包括行号、虚拟地址、机器指令和汇编指令。请回答下列问题。

（1）计算机M是RISC还是CISC？为什么？

（2）f1的机器指令代码共占多少字节？要求给出计算过程。

（3）第20条指令cmp通过i减n-1实现对i和n-1的比较。执行f1(0)过程中，当i=0时，cmp指令执行后，进/借位标志CF的内容是什么？要求给出计算过程。

（4）第23条指令shl通过左移操作实现了power*2运算，在f2中能否也用sh1指令实现power*2？为什么？

答：

（1）M为CISC。(1分)M的指令长短不一，不符合RISC指令系统特点。(1分)

（2）f1的机器代码占96 B。(1分)

因为f1的第一条指令“push ebp”所在的虚拟地址为0040 1020H，最后一条指令“ret”所在的虚拟地址为0040 107FH，所以，f1的机器指令代码长度为0040 107FH-0040 1020H+1 = 60H = 96个字节。(1分)

（3）CF=1。(1分)cmp指令实现i与n-1的比较功能，进行的是减法运算。在执行f1(0)过程中，n=0，当i=0时， i=0000 0000H，并且n-1=FFFF FFFFH。因此，当执行第20条指令时，在补码加/减运算器中执行“0减FFFF FFFFH”的操作，即0000 0000H+0000 0000H+1=0000 0001H，此时，进位输出C=0，减法运算时的借位标志CF=C⊕1=1。(2分)

（4）f2中不能用shl指令实现power*2。(1分)

因为 shl 指令用来将一个整数的所有有效数位作为一个整体左移；而f2中的变量power是float型，其机器数中不包含最高有效数位，但包含了阶码部分，将其作为一个整体左移时并不能实现“乘2”的功能，因而f2中不能用shl指令实现power*2。(2分)浮点数运算比整型运算要复杂，耗时也较长。

假定题44给出的计算机M采用二级分页虚拟存储管理方式，虚拟地址格式如下：

请针对题43的函数f1和题44中的机器指令代码，回答下列问题。

（1）函数f1的机器指令代码占多少页？

（2）取第1条指令(push ebp)时，若在进行地址变换的过程中需要访问内存中的页目录和页表，则会分别访问它们各自的第几个表项(编号从0开始)？

（3）M的I/O采用中断控制方式。若进程P在调用f1之前通过scanf( )获取n的值，则在执行scanf( )的过程中，进程P的状态会如何变化?CPU是否会进入内核态？

答：

（1）函数f1的代码段中所有指令的虚拟地址的高20位相同，因此f1的机器指令代码在同一页中，仅占用1页。（1分）页目录号用于寻找页目录的表项，该表项包含页表的位置。页表索引用于寻找页表的表项，该表项包含页的位置。

（2）push ebp指令的虚拟地址的最高10位（页目录号）为 00 0000 0001，中间10位（页表索引）为00 0000 0001，所以，取该指令时访问了页目录的第1个表项，（1分）在对应的页表中访问了第1个表项。（1分）

（3）在执行scanf( )的过程中，进程P因等待输入而从执行态变为阻塞态。(1分)输入结束时，P被中断处理程序唤醒，变为就绪态。(1分)P被调度程序调度，变为运行态。(1分)CPU状态会从用户态变为内核态。(1分)

某进程中有3个并发执行的线程thread1、thread2和thread3，其伪代码如下所示。

//复数的结构类型定义
typedef struct
{
    float a;
    float b;
} cnum;
cnum x, y, z; //全局变量
 
//计算两个复数之和
cnum add(cnum p, cnum q)
{
    cnum s;
    s.a = p.a+q.a;
    s.b = p.b+q.b;
    return s;
}

thread1
{
    cnum w;
    w = add(x, y);
    …
}
 
thread2
{
    cnum w;
    w = add(y, z),
    …
}

thread3
{
    cnum w;
    w.a = 1;
    w.b = 1;
    z = add(z, w);
    y = add(y, w);
    …
}

请添加必要的信号量和P、V(或wait( )、signal( ))操作，要求确保线程互斥访问临界资源，并且最大程度地并发执行。

答：

先找出线程对在各个变量上的互斥、并发关系。如果是一读一写或两个都是写，那么这就是互斥关系。每一个互斥关系都需要一个信号量进行调节。

semaphore mutex_y1=1；//mutex_y1用于thread1与thread3对变量y的互斥访问。(1分)

semaphore mutex_y2=1；//mutex_y2用于thread2与thread3对变量y的互斥访问。(1分)

semaphore mutex_z=1； //mutex_z用于变量z的互斥访问。(1分)

互斥代码如下：(5分)

甲乙双方均采用后退N帧协议(GBN)进行持续的双向数据传输，且双方始终采用捎带确认，帧长均为1000B。Sx, y和Rx, y分别表示甲方和乙方发送的数据帧，其中x是发送序号，y是确认序号(表示希望接收对方的下一帧序号)；数据帧的发送序号和确认序号字段均为3比特。信道传输速率为100Mbps，RTT=0.96ms。下图给出丁甲方发送数据帧和接收数据帧的两种场景，其中t0为初始时刻，此时甲方的发送和确认字号均为0，t1时刻甲方有足够多的数据待发送。

请回答下列问题。

（1）对于图(a)，t0时刻到t1时刻期间，甲方可以断定乙方已正确接收的数据帧数是多少?正确接收的是哪几个帧(请用Sx, y形式给出)?

（2）对于图(a)，从t1时刻起，甲方在不出现超时且未收到乙方新的数据帧之前，最多还可以发送多少个数据帧?其中第一个帧和最后一个帧分别是哪个(请用Sx, y形式给出)?

（3）对于图(b)，从t1时刻起，甲方在不出现新的超时且未收到乙方新的数据帧之前，需要重发多少个数据帧?重发的第一个帧是哪个(请用Sx, y形式给出)?

（4）甲方可以达到的最大信道利用率是多少?

答：

（1）t0时刻到t1时刻期间，甲方可以断定乙方已正确接收了3个数据帧，(1分)分别是S0,0、S1,0、S2,0。(1分)R3,3说明乙发送的数据帧确认号是3，即希望甲发送序号3的数据帧，说明乙已经接收了序号为 0~2的数据帧。

（2）从t1时刻起，甲方最多还可以发送5个数据帧，(1分)其中第一个帧是S5,2，(1分)最后一个数据帧是S1,2。(1分)发送序号3位，有8个序号。在GBN协议中，序号个数>=发送窗口+1，所以这里发送窗口最大为7。此时已发送了S3,0 和 S4,1，所以最多还可以发送5个帧。

（3）甲方需要重发3个数据帧（1分），重发的第一个帧是S2,3。(1分）在GBN协议中，接收方发送了N帧后，检测出错，则需要发送出错帧及其之后的帧。S2,0超时，所以重发的第一帧是S2。已收到乙的R2帧，所以确认号应为3。

（4）甲方可以达到的最大信道利用率是：

U=发送数据的时间/从开始发送第一帧到收到第一个确认帧的时间 = N * Td /(Td + RTT + Ta)。

U是信道利用率，N是发送窗口的最大值，Td是发送一数据帧的时间，RTT是往返时间，Ta是发送一确认帧的时间。这里采用捎带确认，Td=Ta。

给定程序中，函数fun的功能是：将N╳N矩阵主对角线元素中的值与反向对角线对应位置上元素中的值进行交换。例如，若N=3，有下列矩阵：

1 2 3

4 5 6

7 8 9

交换后为：

3 2 1

4 5 6

9 8 7

请在程序的下划线处填入正确的内容并把下划线删除，使程序得出正确的结果。

注意：源程序存放在考生文件夹下的BLANK.C中。

不得增行或删行，也不得更改程序的结构！

给定源程序：

#include <stdio.h>
#define N 4
/**********found**********/
void fun(int  ___1___ , int n)
{int i,s;
/**********found**********/
   for(___2___; i++)
   {s=t[i][i];
      t[i][i]=t[i][n-i-1];
/**********found**********/
      t[i][n-1-i]=___3___;
   }
}
main()
{int t[][N]={21,12,13,24,25,16,47,38,29,11,32,54,42, 21,33,10}, i, j;
   printf("\nThe original array:\n");
   for(i=0; i<N; i++)
   {for(j=0; j<N; j++) printf("%d ",t[i][j]);
      printf("\n");
   }
   fun(t,N);
   printf("\nThe result is:\n");
   for(i=0; i<N; i++)
   {for(j=0; j<N; j++) printf("%d ",t[i][j]);
      printf("\n");
   }
}

由N个有序整数组成的数列已放在一堆数组中，给定程序MODI1.C中函数fun的功能是：利用折半查找算法查找整数m在数组中的位置。若找到，返回其下标值；反之，返回-1.

折半查找的基本算法是：每次查找前先确定数组中待查的范围：low和high（lowhigh，查找结束。

请改正程序中的错误，使它能得出正确结果。

注意：不要改动main函数，不得增行或删行，也不得更改程序的结构。

给定源程序：

#include <stdio.h>
#define N 10
/************found************/
___________1___________
{int low=0,high=N-1,mid;
   while(low<=high)
   {mid=(low+high)/2;
      if(m<a[mid])
        high=mid-1;
/************found************/
      ________2_______
        low=mid+1;
      else return(mid);
   }
   return(-1);
}
main()
{int i,a[N]={-3,4,7,9,13,45,67,89,100,180 },k,m;
   
   printf("a数组中的数据如下:");
   for(i=0;i<N;i++) printf("%d ", a[i]);
   printf("Enter m: "); scanf("%d",&m);
   k=fun(a,m);
   if(k>=0) printf("m=%d,index=%d\n",m,k);
   else printf("Not be found!\n");
}

假定输入的字符串中只包含字母和*号。请编写函数fun，它的功能是：除了尾部的*号之外，将字符串中其它*号全部删除。形参p已指向字符串中最后的一个字母。在编写函数时，不得使用C语言提供的字符串函数。

例如，字符串中的内容为：****A*BC*DEF*G*******，删除后，字符串中的内容应当是：ABCDEFG*******。

注意：部分源程序在文件PROG1.C中。

请勿改动主函数main和其它函数中的任何内容，仅在函数fun的花括号中填入你编写的若干语句。

给定源程序：

#include <stdio.h>
void fun(char *a, char *p)
{
    ____1____
    ____2____
    while(____3____){
      if(*q !='*')____4____;
      ____5____
    }
    while(*p)____6____;
    a[j]='\0';
}
main()
{char s[81],*t;
   void NONO ();
   printf("Enter a string:\n");gets(s);
   t=s;
   while(*t)t++;
   t--;
   while(*t=='*')t--;
   fun(s , t);
   printf("The string after deleted:\n");puts(s);
   NONO();
}
void NONO()
{/* 本函数用于打开文件，输入数据，调用函数，输出数据，关闭文件。 */
  FILE *in, *out ;
  int i ; char s[81],*t ;
  in = fopen("in.dat","r");
  out = fopen("out.dat","w");
  for(i = 0 ; i < 10 ; i++) {
    fscanf(in, "%s", s);
    t=s;
    while(*t)t++;
    t--;
    while(*t=='*')t--;
    fun(s,t);
    fprintf(out, "%s\n", s) ;
  }
  fclose(in);
  fclose(out);
}

给定程序中，函数fun的功能是将不带头结点的单向链表逆置。即若原链表中从头至尾结点数据域依次为：2、4、6、8、10，逆置后，从头至尾结点数据域依次为：10、8、6、4、2.

请在程序的下划线处填入正确的内容并把下划线删除，使程序得出正确的结果。

注意：源程序存放在考生文件夹下的BLANK.C中。

不得增行或删行，也不得更改程序的结构！

给定源程序：

#include  <stdio.h>
#include  <stdlib.h>
#define N 5
typedef struct node {
  int data;
  struct node *next;
} NODE;
/**********found**********/
__1__ fun(NODE *h)
{NODE *p, *q, *r;
  p = h;
  if (p == NULL)
    return NULL;
  q = p->next;
  p->next = NULL;
  while (q)
  {
/**********found**********/
    r = q->__2__;
    q->next = p;
    p = q;
/**********found**********/
    q = __3__ ;
  }
  return p;
}
NODE *creatlist(int a[])
{NODE *h,*p,*q; int i;
   h=NULL;
   for(i=0; i<N; i++)
   {q=(NODE *)malloc(sizeof(NODE));
      q->data=a[i];
      q->next = NULL;
      if (h == NULL) h = p = q;
      else {p->next = q; p = q;}
   }
   return h;
}
void outlist(NODE *h)
{NODE *p;
   p=h;
   if (p==NULL) printf("The list is NULL!\n");
   else
   {printf("\nHead ");
      do
      {printf("->%d", p->data); p=p->next;}
      while(p!=NULL);
      printf("->End\n");
  }
}
main()
{NODE *head;
   int a[N]={2,4,6,8,10};
   head=creatlist(a);
   printf("\nThe original list:\n");
   outlist(head);
   head=fun(head);
   printf("\nThe list after inverting :\n");
   outlist(head);
}

给定程序MODI1.C中函数fun的功能是：将s所指字符串中位于奇数位置的字符或ASCII码为偶数的字符放入t所指数组中（规定第一个字符放在第0位中）。

例如，字符串中的数据为：AABBCCDDEEFF，则输出应当是ABBCDDEFF。

请改正程序中的错误，使它能得出正确结果。

注意：不要改动main函数，不得增行或删行，也不得更改程序的结构。

给定源程序：

#include <stdio.h>
#include <string.h>
#define N 80
void fun(char *s, char t[])
{int i, j=0;
   for(i=0; i<(int)strlen(s); i++)
/***********found**********/
   if(__1__)
        t[j++]=s[i];
/***********found**********/
   __2__;
}
main()
{char s[N], t[N];
   printf("\nPlease enter string s : "); gets(s);
   fun(s, t);
   printf("\nThe result is : %s\n",t);
}

请编写函数fun，函数的功能是：将M行N列的二维数组中的数据，按列的顺序依次放到一维数组中。

例如，二维数组中的数据为：

33 33 33 33

44 44 44 44

55 55 55 55

则一维数组中的内容应该是：

33 44 55 33 44 55 33 44 55 33 44 55。

注意：部分源程序在文件PROG1.C中。

请勿改动主函数main和其它函数中的任何内容，仅在函数fun的花括号中填入你编写的若干语句。

给定源程序：

#include <stdio.h>
void fun(int s[][10], int b[], int *n, int mm, int nn)
{
    __1__;
    for(j=0;j<nn;j++)
    for(__2__)
    {
      b[*n]=__3__;
      __4__;
    }
}
main()
{int w[10][10]={{33,33,33,33},{44,44,44,44},{55,55, 55,55}},i,j;
   int a[100]={0}, n=0;void NONO ();
   printf("The matrix:\n");
   for(i=0; i<3; i++)
   {for(j=0;j<4; j++)printf("%3d",w[i][j]);
      printf("\n");
   }
   fun(w,a,&n,3,4);
   printf("The A array:\n");
   for(i=0;i<n;i++)printf("%3d",a[i]);printf("\n\n");
   NONO();
}
void NONO ()
{/* 请在此函数内打开文件，输入测试数据，调用 fun 函数，输出数据，关闭文件。 */
  FILE *rf, *wf ; int i, j, k ;
  int w[10][10], a[100], n = 0, mm, nn ;
  rf = fopen("in.dat","r");
  wf = fopen("out.dat","w");
  for(k = 0 ; k < 5 ; k++) {
    fscanf(rf, "%d %d", &mm, &nn);
    for(i = 0 ; i < mm ; i++)
      for(j = 0 ; j < nn ; j++) fscanf(rf, "%d", &w[i][j]);
    fun(w, a, &n, mm, nn);
    for(i = 0 ; i < n ; i++) fprintf(wf, "%3d", a[i]); fprintf(wf, "\n");
  }
  fclose(rf); fclose(wf);
}

一个栈的初始状态为空。一方面将元素5,4,3,2,1依次入栈，然后退栈一次，再将元素 A,B,C,D依次入栈，之后将所有元素所有退栈，则所有元素退栈（涉及中间退栈的元素）的顺序为____

在长度为n的线性表中，寻找最大项至少需要比较____次。

一棵二叉树有10个度为1的结点，7个度为2的结点，则该二叉树共有____个结点。

仅由顺序、选择（分支）和反复（循环）结构构成的程序是____程序。

数据库设计的四个阶段是：需求分析，概念设计，逻辑设计，____

以下程序运营后的输出结果是____。

#include<stdio．h>
main(){
int a=200，b=010;　　
printf("％d%d\n",a,b);
}

有以下程序

　　＃include＜stdio．h>
　　main（）
　　｛int  x,Y;
　　scanf（”％2d%ld”，＆x，＆y）；printf（”％d＼n”，x+y）；
　　｝

　　程序运营时输入：1234567程序的运营结果是____