1、设有一组初始记录关键字为(45，80，48，40，22，78)，要求构造一棵二叉排序树并给出构造过程。
、 void linklist_reverse(linklist &l)
/链表的就地逆置；为简化算法，假设表长大于2
p=l->next;q=p->next;s=q->next;p->next=null
while(s->next)
q->next=p;p=q;
q=s;s=s->next; /把l的元素逐个插入新表表头。
q->next=p;s->next=q;l->next=s;
//linklist_reverse
3、给定n个村庄之间的交通图，若村庄i和j之间有道路，则将顶点i和j用边连接，边上的wij表示这条道路的长度，现在要从这n个村庄中选择一个村庄建一所医院，问这所医院应建在哪个村庄，才能使离医院最远的村庄到医院的路程最短？试设计一个解答上述问题的算法，并应用该算法解答如图所示的实例。（20分）
4、二部图（bipartite graph） g=（v，e）是一个能将其结点集v分为两不相交子集v 1和v2=v-v1的无向图，使得：v1中的任何两个结点在图g中均不相邻，v2中的任何结点在图g中也均不相邻。
1）．请各举一个结点个数为5的二部图和非二部图的例子。
2）．请用c或pascal编写一个函数bipartite判断一个连通无向图g是否是二部图，并分析程序的时间复杂度。设g用二维数组a来表示，大小为n*n（n为结点个数）。请在程序中加必要的注释。
若有必要可直接利用堆栈或队列操作。【
5、本题应使用深度优先遍历，从主调函数进入dfs(v)时 ，开始记数，若退出dfs()前，已访问完有向图的全部顶点（设为n个），则有向图有根，v为根结点。将n个顶点从1到n编号，各调用一次dfs()过程，就可以求出全部的根结点。题中有向图的邻接表存储结构、记顶点个数的变量、以及访问标记数组等均设计为全局变量。
建立有向图g的邻接表存储结构参见上面第2题，这里只给出判断有向图是否有根的算法。
int num=0， visited=0 //num记访问顶点个数，访问数组visited初始化。
const n=用户定义的顶点数；
adjlist g用邻接表作存储结构的有向图g。
void dfs(v)
visited [v]=1; num++;访问的顶点数＋1
if (num==n) /if
p=g[v].firstarc;
while (p)
if (visied[p->adjvex]==0) dfs (p->adjvex);
p=p->next;} while
visited[v]=0; num--;恢复顶点v
//dfsvoid judgeroot()
/判断有向图是否有根，有根则输出之。
static int i ;
for (i=1;i<=n;i++ 从每个顶点出发，调用dfs()各一次。
num=0; visited[1..n]=0; dfs(i);
}//judgeroot
算法中打印根时，输出顶点在邻接表中的序号（下标），若要输出顶点信息，可使用g[i].vertex。
6、对二叉树的某层上的结点进行运算，采用队列结构按层次遍历最。
适宜。int leafklevel(bitree bt, int k) /求二叉树bt 的第k(k>1) 层上叶子结点个数。
if(bt==null ||k<1) return(0);
bitree p=bt,qq是队列，元素是二叉树结点指针，容量足够大。
int front=0,rear=1,leaf=0; /front 和rear是队头和队尾指针， leaf是叶子结点数。
int last=1,level=1; q[1]=p; /last是二叉树同层最右结点的指针，level 是二叉树的层数。
while(front<=rear)
p=q[++front];
if(level==k &&p->lchild &&p->rchild) leaf++;叶子结点。
if(p->lchild) q[++rear]=p->lchild左子女入队。
if(p->rchild) q[++rear]=p->rchild右子女入队。
if(front==last) last移到指向下层最右一元素。
if(level>k) return (leaf层数大于k 后退出运行。
//while }/结束leafklevel
7、后序遍历最后访问根结点，即在递归算法中，根是压在栈底的。采用后序非递归算法，栈中存放二叉树结点的指针，当访问到某结点时，栈中所有元素均为该结点的祖先。本题要找p和q 的最近共同祖先结点r ,不失一般性，设p在q的左边。
后序遍历必然先遍历到结点p，栈中元素均为p的祖先。将栈拷入另一辅助栈中。再继续遍历到结点q时，将栈中元素从栈顶开始逐个到辅助栈中去匹配，第一个匹配（即相等）的元素就是结点p 和q的最近公共祖先。
typedef struct
bitree t;int tag;//tag=0 表示结点的左子女已被访问，tag=1表示结点的右子女已被访问。
stack;
stack s,s1;栈，容量够大。
bitree ancestor(bitree root,p,q,r)//求二叉树上结点p和q的最近的共同祖先结点r。
top=0; bt=root;
while(bt!=null ||top>0)
while(bt!=null &&bt!=p &&bt!=q结点入栈。
s[++top].t=bt; s[top].tag=0; bt=bt->lchild;} 沿左分枝向下。
if(bt==p) /不失一般性，假定p在q的左侧，遇结点p时，栈中元素均为p的祖先结点。
for(i=1;i<=top;i++)s1[i]=s[i]; top1=top; }将栈s的元素转入辅助栈s1 保存。
if(bt==q) /找到q 结点。
for(i=top;i>0;i--)将栈中元素的树结点到s1去匹配。
pp=s[i].t;
for (j=top1;j>0;j--)
if(s1[j].t==pp)
while(top!=0 &&s[top].tag==1) top退栈。
if (top!=0)｛s[top].tag=1;bt=s[top].t->rchild;｝ 沿右分枝向下遍历。
//结束while(bt!=null ||top>0)
return(null);/p无公共祖先。
//结束ancestor
8、给定n个村庄之间的交通图，若村庄i和j之间有道路，则将顶点i和j用边连接，边上的wij表示这条道路的长度，现在要从这n个村庄中选择一个村庄建一所医院，问这所医院应建在哪个村庄，才能使离医院最远的村庄到医院的路程最短？试设计一个解答上述问题的算法，并应用该算法。
法解答如图所示的实例。（20分）
#define maxsize 栈空间容量void inouts(int s[maxsize])
/s是元素为整数的栈，本算法进行入栈和退栈操作。
int top=0top为栈顶指针，定义top=0时为栈空。
for(i=1; i<=n; i++)n个整数序列作处理scanf(“%d”,&x); 从键盘读入整数序列。
if(x!=-1读入的整数不等于-1时入栈。
if(top==maxsize-1)
else s[++top]=x; /x入栈else //读入的整数等于-1时退栈。
if(top==0)
else printf(“出栈元素是%d”,s[top算法结。
、 void linklist_reverse(linklist &l)
/链表的就地逆置；为简化算法，假设表长大于2p=l->next;q=p->next;s=q->next;p->next=nullwhile(s->next)
q->next=p;p=q;
q=s;s=s->next; /把l的元素逐个插入新表表头。
q->next=p;s->next=q;l->next=s;
//linklist_reverse
11、由二叉树的前序遍历和中序遍历序列能确定唯一的一棵二叉树，下面程序的作用是实现由已知某二叉树的前序遍历和中序遍历序列，生成一棵用二叉链表表示的二叉树并打印出后序遍历序列，请写出程序所缺的语句。
#define max 100
typedef struct node
char info; struct node *llink, *rlink; }tnode;
char pred[max],inod[max];
main(int argc,int **ar**)
tnode *root;
if(argc<3) exit 0;
strcpy(pred,ar**[1]);strcpy(inod,ar**[2]);
root=restore(pred,inod,strlen(pred));
postorder(root);
tnode *restore(char *ppos,char *ipos,int n)
tnode *ptr； char *rpos; int k;
if(n<=0) return null;
ptr->info=(1for((2rposllink=restore(ppos+1, (4)__k );
ptr->rlink=restore ((5)__k,rpos+1,n-1-k);
return ptr;
postorder(tnode*ptr)
if(ptr=null) return;
postorder(ptr->llink); postorder(ptr->rlink); printf(“%c”,ptr->info12、对二叉树的某层上的结点进行运算，采用队列结构按层次遍历最适宜。
int leafklevel(bitree bt, int k) /求二叉树bt 的第k(k>1) 层上叶子结点个数。
if(bt==null ||k<1) return(0);
bitree p=bt,qq是队列，元素是二叉树结点指针，容量足够大。
int front=0,rear=1,leaf=0; /front 和rear是队头和队尾指针， leaf是叶子结点数。
int last=1,level=1; q[1]=p; /last是二叉树同层最右结点的指针，level 是二叉树的层数。
while(front<=rear)
p=q[++front];
if(level==k &&p->lchild &&p->rchild) leaf++;叶子结点。
if(p->lchild) q[++rear]=p->lchild左子女入队。
if(p->rchild) q[++rear]=p->rchild右子女入队。
if(front==last) last移到指向下层最右一元素。
if(level>k) return (leaf层数大于k 后退出运行。
//while }/结束leafklevel
13、证明由二叉树的中序序列和后序序列，也可以唯一确定一棵二叉树。
29. ①试找出满足下列条件的二叉树。
1）先序序列与后序序列相同 2）中序序列与后序序列相同。
3）先序序列与中序序列相同 4）中序序列与层次遍历序列相同
14、有一个带头结点的单链表，每个结点包括两个域，一个是整型域info，另一个是指向下一个结点的指针域next。假设单链表已建立，设计算法删除单链表中所有重复出现的结点，使得info域相等的结点只保留一个。
#include <>
typedef char datatype;
typedef struct node
else s=q; /找与p结点值相同的结点*/
q=q->next;
p=p->next;
return head15、设有两个集合a和集合b，要求设计生成集合c=a∩b的算法，其中集合a、b和c用链式存储结构表示。
typedef struct node lklist;
void intersection(lklist *ha,lklist *hb,lklist *&hc)
lklist *p,*q,*t;
for(p=ha,hc=0;p!=0;p=p->next)
for(q=hb;q!=0;q=q->next) if (q->data==p->data) break;
if(q!=0)
else s[++top]=x; /x入栈else //读入的整数等于-1时退栈。
if(top==0)
else printf(“出栈。
元素是%d”,s[top算法结。
18、设一组有序的记录关键字序列为(13，18，24，35，47，50，62，83，90)，查找方法用二分查找，要求计算出查找关键字62时的比较次数并计算出查找成功时的平均查找长度。
2023年吉林省C语言加强
1 设一棵树t中边的集合为，要求用孩子兄弟表示法 二叉链表 表示出该树的存储结构并将该树转化成对应的二叉树。2 设一组有序的记录关键字序列为 13，18，24，35，47，50，62，83，90 查找方法用二分查找，要求计算出查找关键字62时的比较次数并计算出查找成功时的平均查找长度。3 我们可用 ...
2023年吉林省教育统计情况
2013年吉林省教育系统学校数量统计。一 汇总表。二 详细说明。2013年末，全省小学5103所，招生21.8万人，在校生136.2万人。初中1200所，招生21.8万人，在校生64.5万人。普通高中学校243所，招生15.1万人，在校生45.3万人。中等职业教育学校 机构 336所，招生6.1万人...
2019吉林省数据结构 C考
1 已知广义表l x,y,z a,u,t,w 从l 表中取出原子项t 的操作是 d a head head tail tail l b tail head head tail l c head tail head tail l d head tail head tail tail l 2 与无向图相...