前言：

今年考了10道判断题，16道选择题，分值和前面那套题一样，今年也是理论课和实验考试放在一起考的，三道函数题，两道编程题，共两个半小时。
判断和选择回忆的不可能太详细，反正基本都是作业题的范围，从第一章时间复杂度的分析，到最后一章排序，涵盖的知识点还是挺多的，只是难度没有21-22那套题那么大，毕竟那套题里有好几个都是考研真题，看解析都感觉比较困难。今年的选择题没涉及KMP，也没有关键路径的考察，但是这毕竟是课上学的重要知识点，建议同学们复习的时候一定要弄明白，说不定什么时候考。
下面的函数和编程回忆的还可以详细一点，尤其是编程题考了个原题。

函数题：

部分题目找不到原题，不过我觉得很简单，都是一些和作业题相似的函数题，代码量最长也就40行左右，下面的回忆不可能太准确，但是考点肯定没错。

6-1 求链式表的第K个元素（11分）

本题要求实现一个函数，找到并返回链式表的第K个元素。
函数接口定义：

ElementType FindKth( List L, int K );

其中List结构定义如下：

typedef struct LNode *PtrToLNode;struct LNode {    ElementType Data;
    PtrToLNode Next;
};
typedef PtrToLNode List;

L是给定单链表，函数FindKth要返回链式表的第K个元素。如果该元素不存在，则返回ERROR。

裁判测试程序样例：

include <stdio.h>
include <stdlib.h>
define ERROR -1
typedef int ElementType;
typedef struct LNode *PtrToLNode;
struct LNode {    ElementType Data;
    PtrToLNode Next;
};
typedef PtrToLNode List;
List Read(); /* 细节在此不表 */
ElementType FindKth( List L, int K );
int main(){
    int N, K;
    ElementType X;
    List L = Read();
    scanf("%d", &N);
    while ( N-- ) {
        scanf("%d", &K);
        X = FindKth(L, K);
        if ( X!= ERROR )
            printf("%d ", X);
        else  printf("NA ");
    }
    return 0;
}
/* 你的代码将被嵌在这里 */

输入样例：

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

输出样例：

4 NA 1 2 5 3 

代码长度限制 16 KB
时间限制 400 ms
内存限制 64 MB

6-2 建立二叉排序树（11分）

【非考试原题，但是十分类似】
建立一个二叉排序树，根据给定值对其实施查找。
二叉排序树的二叉链表存储表示：

typedef int ElemType;
typedef  struct  BSTNode
{  
    ElemType  data;
    struct  BSTNode   *lchild,*rchild;
}BSTNode,*BSTree;

函数接口定义：

void BSTInsert( BSTree &T, BSTree s)
void BSTCreate(BSTree  &T)
BSTree BSTSearch(BSTree T, ElemType k)

该函数中的参数说明：

ElemType k 要搜索的值
顺序表中第一个数据元素存储在 T.R[1]

测试主程序样例：

int main ()
{    
    BSTree T,p; 
    int x;
    BSTCreate(T);
    scanf("%d",&x);
    p=BSTSearch(T,x);
    if(p!=NULL)
    {  
       printf("have found!");
       printf(" lchild:");
       if(p->lchild)  printf("%d",p->lchild->data);
       else printf("NULL");
       printf(" rchild:");
       if(p->rchild) printf("%d",p->rchild->data);
       else printf("NULL");
    }
    else
       printf("NOT FOUND!");
    return 0;
}

输入格式:

第一行输入二叉排序树中结点的值，以-1结束。用逐个插入的方式创建二叉排序树。
第二行输入一个要查找的值。

输出格式:

找到，输出have found!。接着空一格，输出该结点左孩子值，后再空一格，输出该结点右孩子的值。如果孩子为空，对应位置输出NULL。
如果没有找到，输出NOT FOUND!。

输入样例1:

10 18 3 8 20 2 7 -1
3

输出样例1:

have found! lchild:2 rchild:8

输入样例2:

10 18 3 8 20 2 7 -1
8

输出样例2:

have found! lchild:7 rchild:NULL

输入样例3:

10 18 3 8 20 2 7 -1
5

输出样例3:

NOT FOUND!

6-3 求采用邻接矩阵作为存储结构的有向图各顶点的出度（15分-实验原题）

本题要求实现一个函数，输出有向图每个顶点的数据元素的值，以及每个顶点的出度的值。

函数接口定义：

void outdegree(MGraph G);

G为采用邻接矩阵作为存储结构的有向图。

裁判测试程序样例：

#include <stdio.h>
#define MVNum 100                 //最大顶点数 
typedef struct{ 
  char vexs[MVNum];           //存放顶点的一维数组 
  int arcs[MVNum][MVNum];     //邻接矩阵 
  int vexnum,arcnum;          //图的当前顶点数和弧数 
}MGraph; 
void outdegree(MGraph G);
void CreatMGraph(MGraph *G);/* 创建图 */
int main()
{
    MGraph G;
    CreatMGraph(&G);
    outdegree(G);
    return 0;
}
void CreatMGraph(MGraph *G)
{
    int i,j,k;
    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;    
    }
}
 
/* 请在这里填写答案 */

输入样例：

例如有向图

第一行给出图的顶点数n和弧数e。第二行给出n个字符，表示n个顶点的数据元素的值。后面是e行，给出每一条弧的两个顶点编号。

4 5
ABCD
1 0
2 0
2 1
3 2
3 1

输出样例：

输出n个顶点的元素值，顶点的数据类型为字符型。以及各顶点的出度值：

A:0
B:1
C:2
D:2

编程题：

7-1 堆栈的合法性（15分-实验）

假设以S和X分别表示入栈和出栈操作。如果根据一个仅由S和X构成的序列，对一个空堆栈进行操作，相应操作均可行（如没有出现删除时栈空）且最后状态也是栈空，则称该序列是合法的堆栈操作序列。请编写程序，输入S和X序列，判断该序列是否合法。

输入格式:

输入第一行给出两个正整数N和M，其中N是待测序列的个数，M（≤50）是堆栈的最大容量。随后N行，每行中给出一个仅由S和X构成的序列。序列保证不为空，且长度不超过100。

输出格式:

对每个序列，在一行中输出YES如果该序列是合法的堆栈操作序列，或NO如果不是。

输入样例：

4 10
SSSXXSXXSX
SSSXXSXXS
SSSSSSSSSSXSSXXXXXXXXXXX
SSSXXSXXX

输出样例：

YES
NO
NO
NO

代码长度限制 16 KB
时间限制 400 ms
内存限制 64 MB

7-2 PAT排名汇总（10分）

计算机程序设计能力考试（Programming Ability Test，简称PAT）旨在通过统一组织的在线考试及自动评测方法客观地评判考生的算法设计与程序设计实现能力，科学的评价计算机程序设计人才，为企业选拔人才提供参考标准（网址http://www.patest.cn）。
每次考试会在若干个不同的考点同时举行，每个考点用局域网，产生本考点的成绩。考试结束后，各个考点的成绩将即刻汇总成一张总的排名表。
现在就请你写一个程序自动归并各个考点的成绩并生成总排名表。

输入格式:

输入的第一行给出一个正整数N（≤100），代表考点总数。随后给出N个考点的成绩，格式为：首先一行给出正整数K（≤300），代表该考点的考生总数；随后K行，每行给出1个考生的信息，包括考号（由13位整数字组成）和得分（为[0,100]区间内的整数），中间用空格分隔。
输出格式:
首先在第一行里输出考生总数。随后输出汇总的排名表，每个考生的信息占一行，顺序为：考号、最终排名、考点编号、在该考点的排名。其中考点按输入给出的顺序从1到N编号。考生的输出须按最终排名的非递减顺序输出，获得相同分数的考生应有相同名次，并按考号的递增顺序输出。

输入样例:

2
5
1234567890001 95
1234567890005 100
1234567890003 95
1234567890002 77
1234567890004 85
4
1234567890013 65
1234567890011 25
1234567890014 100
1234567890012 85

输出样例:

9
1234567890005 1 1 1
1234567890014 1 2 1
1234567890001 3 1 2
1234567890003 3 1 2
1234567890004 5 1 4
1234567890012 5 2 2
1234567890002 7 1 5
1234567890013 8 2 3
1234567890011 9 2 4

代码长度限制 16 KB
时间限制 400 ms
内存限制 64 MB