Ⅰ c语言数据结构（考题，测试你的能力）－－编写源代码
P88 稀疏矩阵十字链表相加算法如下：
/*假设ha为A稀疏矩阵十字链表的头指针，hb为B稀疏矩阵十字链表的头指针*/
#include<stdio.h>
#define maxsize 100
struct linknode
{ int i,j;
struct linknode *cptr,*rptr;
union vnext
{ int v;
struct linknode *next;} k;
};
struct linknode creatlindmat( ) /*建立十字链表*/
{ int x, m, n, t, s, i, j, k;
struct linknode *p , *q, *cp[maxsize],*hm;
printf("请输入稀疏矩阵的行、列数及非零元个数\n");
scanf("%d%d%d",&m,&n,&t);
if (m>n) s=m; else s=n;
hm=(struct linknode*)malloc(sizeof(struct linknode)) ;
hm->i=m; hm->j=n;
cp[0]=hm;
for (i=1; i<=s;i++)
{ p=(struct linknode*)malloc(sizeof(struct linknode)) ;
p->i=0; p->j=0;
p->rptr=p; p->cptr=p;
cp[i]=p;
cp[i-1]->k.next=p;
}
cp[s]->k.next=hm;
for( x=1;x<=t;x++)
{ printf("请输入一个三元组(i,j,v)\n");
scanf("%d%d%d",&i,&j,&k);
p=(struct linknode*)malloc(sizeof(struct linknode));
p->i=i; p->j=j; p->k.v=k;
/*以下是将p插入到第i行链表中 */
q=cp[i];
while ((q->rptr!=cp[i]) &&( q->rptr->j<j))
q=q->rptr;
p->rptr=q->rptr;
q->rptr=p;
/*以下是将P插入到第j列链表中*/
q=cp[j];
while((q->cptr!=cp[j]) &&( q->cptr->i<i))
q=q->cptr;
p->cptr=q->cptr;
q->cptr=p;
}
return hm;
}
/* ha和hb表示的两个稀疏矩阵相加，相加的结果放入ha中*/
struct linknode *matadd(struct linknode *ha, struct linknode *hb)
{ struct linknode *pa, *pb, *qa, *ca,*cb,*p,*q;
struct linknode *hl[maxsize];
int i , j, n;
if((ha->i!=hb->i)||(ha->j!=hb->j))
printf("矩阵不匹配,不能相加\n");
else
{ p=ha->k.next; n=ha->j;
for (i=1;i<=n; i++)
{ hl[i]=p;
p=p->k.next;
}
ca=ha->k.next; cb=hb->k.next;
while(ca->i==0)
{pa=ca->rptr; pb=cb->rptr;
qa=ca;
while(pb->j!=0)
{ if((pa->j<pb->j)&&(pa->j!=0))
{ qa=pa; pa=pa->rptr;}
else if ((pa->j>pb->j)||(pa->j==0)) /*插入一个结点*/
{ p=(struct linknode*)malloc(sizeof(struct linknode));
p->i=pb->i; p->j=pb->j;
p->k.v=pb->k.v;
qa->rptr=p; p->rptr=pa;
qa=p; pb=pb->rptr;
j=p->j; q=hl[j]->cptr;
while((q->i<p->i)&&(q->i!=0))
{ hl[j]=q; q=hl[j]->cptr;}
hl[j]->cptr=p; p->cptr=q;
hl[j]=p;
}
else
{pa->k.v=pa->k.v+pb->k.v;
if(pa->k.v==0) /*删除一个结点*/
{ qa->rptr=pa->rptr;
j=pa->j; q=hl[j]->cptr;
while (q->i<pa->i)
{hl[j]=q; q=hl[j]->cptr;}
hl[j]->cptr=q->cptr;
pa=pa->rptr; pb=pb->rptr;
free(q);
}
else
{ qa=pa; pa=pa->rptr;
pb=pb->rptr;
}
}
}
ca=ca->k.next; cb=cb->k.next;
}
}
return ha;
}
void print(struct linknode *ha) /*输出十字链表*/
{ struct linknode *p,*q;
p=ha->k.next;
while(p->k.next!=ha)
{ q=p->rptr;
while(q->rptr!=p)
{ printf("%3d%3d%3d\t",q->i,q->j,q->k.v);
q=q->rptr;
}
if(p!=q)
printf("%3d%3d%3d",q->i,q->j,q->k.v);
printf("\n");
p=p->k.next;
}
q=p->rptr;
while(q->rptr!=p)
{ printf("%3d%3d%3d\t",q->i,q->j,q->k.v);
q=q->rptr;
}
if(p!=q)
printf("%3d%3d%3d",q->i,q->j,q->k.v);
printf("\n");
}
void main()
{
struct linknode *ha=NULL,*hb=NULL,*hc=NULL;
ha=creatlindmat( ); /*生成一个十字链表ha*/
hb=creatlindmat( ); /*生成另一个十字链表hb*/
printf("A:\n"); /*输出十字链表ha*/
print(ha);printf("\n");
printf("B:\n"); /*输出十字链表hb*/
print(hb);printf("\n");
hc=matadd(ha,hb); /*十字链表相加*/
printf("A+B:\n"); /*输出相加后的结果*/
print(hc);printf("\n");
}
P94 数据类型描述如下：
#define elemtype char
struct node1
{ int atom;
struct node1 *link;
union
{
struct node1 *slink;
elemtype data;
} ds;
}
P95 数据类型描述如下：
struct node2
{ elemtype data;
struct node2 *link1,*link2;
}
P96 求广义表的深度depth(LS)
int depth(struct node1 *LS)
{
int max=0,dep;
while(LS!=NULL)
{ if(LS->atom==0) //有子表
{ dep=depth(LS->ds.slink);
if(dep>max) max=dep;
}
LS=LS->link;
}
return max+1;
}
P96 广义表的建立creat(LS)
void creat(struct node1 *LS)
{
char ch;
scanf("%c",&ch);
if(ch=='#')
LS=NULL;
else if(ch=='(')
{LS=(struct node*)malloc(sizeof(struct node));
LS->atom=0;
creat(LS->ds.slink);
}
else
{ LS=(struct node*)malloc(sizeof(struct node));
LS->atom=1;
LS->ds.data=ch;
}
scanf("%c",&ch);
if(LS==NULL);
else if(ch==',')
creat(LS->link);
else if((ch==')')||(ch==';'))
LS->link=NULL;
}
P97 输出广义表print(LS)
void print(struct node1 *LS)
{
if(LS->atom==0)
{
printf("(");
if(LS->ds.slink==NULL)
printf("#");
else
print(LS->ds.slink);
}
else
printf("%c ",LS->ds.data);
if(LS->atom==0)
printf(")");
if(LS->link!=NULL)
{
printf(";");
print(LS->link);
}
}
P98 该算法的时间复杂度为O(n)。整个完整程序如下：
#include<stdio.h>
#define elemtype char
struct node1
{ int atom;
struct node1 *link;
union
{
struct node1 *slink;
elemtype data;
} ds;
};
void creat(struct node1 LS) /*建立广义表的单链表*/
{
char ch;
scanf("%c",&ch);
if(ch=='#')
LS=NULL;
else if(ch=='(')
{LS=(struct node1*)malloc(sizeof(struct node1));
LS->atom=0;
creat(LS->ds.slink);
}
else
{ LS=(struct node1*)malloc(sizeof(struct node1));
LS->atom=1;
LS->ds.data=ch;
}
scanf("%c",&ch);
if(LS==NULL);
else if(ch==',')
creat(LS->link);
else if((ch==')')||(ch==';'))
LS->link=NULL;
}
void print(struct node1 LS) /*输出广义单链表*/
{
if(LS->atom==0)
{
printf("(");
if(LS->ds.slink==NULL)
printf("#");
else
print(LS->ds.slink);
}
else
printf("%c",LS->ds.data);
if(LS->atom==0)
printf(")");
if(LS->link!=NULL)
{
printf(";");
print(LS->link);
}
}
int depth(struct node1 LS) /*求广义表的深度*/
{
int max=0;
while(LS!=NULL)
{ if(LS->atom==0)
{ int dep=depth(LS->ds.slink);
if(dep>max) max=dep;
}
LS=LS->link;
}
return max+1;
}
main()
{ int dep;
struct node1 *p=NULL;
creat(p); /*建立广义表的单链表*/
print(p); /*输出广义单链表*/
dep=depth(p); /*求广义表的深度*/
printf("%d\n",dep);
}
第六章 树
P109 二叉链表的结点类型定义如下：
typedef struct btnode
{ anytype data;
struct btnode *Lch,*Rch;
}tnodetype;
P109 三叉链表的结点类型定义如下：
typedef struct btnode3
{ anytype data;
struct btnode *Lch,*Rch，*Parent ;
}tnodetype3;
P112 C语言的先序遍历算法：
void preorder (tnodetype *t)
/*先序遍历二叉树算法，t为指向根结点的指针*/
{ if (t!=NULL)
{printf("%d ",t->data);
preorder(t->lch);
preorder(t->rch);
}
}
P113 C语言的中序遍历算法：
void inorder(tnodetype *t)
/*中序遍历二叉树算法，t为指向根结点的指针*/
{
if(t!=NULL)
{inorder(t->lch);
printf("%d ",t->data);
inorder(t->rch);
}
}
P113 C语言的后序遍历算法：
void postorder(tnodetype *t)
/*后序遍历二叉树算法，t为指向根结点的指针*/
{
if(t!=NULL)
{ postorder(t->lch);
postorder(t->rch);
printf("%d ",t->data);
}
}
P114 如果引入队列作为辅助存储工具，按层次遍历二叉树的算法可描述如下：
void levelorder(tnodetype *t)
/*按层次遍历二叉树算法，t为指向根结点的指针*/
{tnodetype q[20]; /*辅助队列*/
front=0;
rear=0; /*置空队列*/
if (t!=NULL)
{ rear++;
q[rear]=t; /*根结点入队*/
}
while (front!=rear)
{ front++;
t=q [front];
printf ("%c\n",t->data);
if (t->lch!=NULL) /*t的左孩子不空，则入队*/
{ rear++;
q [rear]=t->lch;
}
if (t->rch!=NULL) /*t的右孩子不空，则入队*/
{ rear++;
q [rear]=t->rch;
}
}
}
P115 以中序遍历的方法统计二叉树中的结点数和叶子结点数，算法描述为：
void inordercount (tnodetype *t)
/*中序遍历二叉树，统计树中的结点数和叶子结点数*/
{ if (t!=NULL)
{ inordercount (t->lch); /*中序遍历左子树*/
printf ("%c\n",t->data); /*访问根结点*/
countnode++; /*结点计数*/
if ((t->lch==NULL)&&(t->rch==NULL))
countleaf++; /*叶子结点计数*/
inordercount (t->rch); /*中序遍历右子树*/
}
}
P115 可按如下方法计算一棵二叉树的深度：
void preorderdeep (tnodetype *t,int j)
/*先序遍历二叉树，并计算二叉树的深度*/
{ if (t!=NULL)
{ printf ("%c\n",t->data); /*访问根结点*/
j++;
if (k<j) k=j;
preorderdeep (t->lch,j); /*先序遍历左子树*/
preorderdeep (t->rch,j); /*先序遍历右子树*/
}
}
P117 线索二叉树的结点类型定义如下：
struct nodexs
{anytype data;
struct nodexs *lch, *rch;
int ltag,rtag; /*左、右标志域*/
}
P117 中序次序线索化算法
void inorderxs (struct nodexs *t)
/*中序遍历t所指向的二叉树，并为结点建立线索*/
{ if (t!=NULL)
{ inorderxs (t->lch);
printf ("%c\n",t->data);
if (t->lch!=NULL)
t->ltag=0;
else { t->ltag=1;
t->lch=pr;
} /*建立t所指向结点的左线索，令其指向前驱结点pr*/
if (pr!=NULL)
{ if (pr->rch!=NULL)
pr->rtag=0;
else { pr->rtag=1;
pr->rch=p;
}
} /*建立pr所指向结点的右线索，令其指向后继结点p*/
pr=p;
inorderxs (t->rch);
}
}
P118 在中根线索树上检索某结点的前驱结点的算法描述如下：
struct nodexs * inpre (struct nodexs *q)
/*在中根线索树上检索q所指向的结点的前驱结点*/
{ if (q->ltag==1)
p=q->lch;
else { r=q->lch;
while (r->rtag!=1)
r=r->rch;
p=r;
}
return (p);
}
P119 在中根线索树上检索某结点的后继结点的算法描述如下：
struct nodexs * insucc (struct nodexs *q)
/*在中根线索树上检索q所指向的结点的后继结点*/
{ if (q->rtag==1)
p=q->rch;
else { r=q->rch;
while (r->ltag!=1)
r=r->lch;
p=r;
}
return (p);
}
P120 算法程序用C语言描述如下：
void sortBT(BT *t,BT *s) /*将指针s所指的结点插入到以t为根指针的二叉树中*/
{ if (t==NULL) t=s; /*若t所指为空树，s所指结点为根*/
else if (s->data < t->data)
sortBT(t->lch,s); /*s结点插入到t的左子树上去*/
else
sortBT(t->rch,s); /*s结点插入到t的右子树上去*/
}
P121 二叉排序树结点删除算法的C语言描述如下：
void delnode(bt,f,p)
/*bt为一棵二叉排序树的根指针，p指向被删除结点，f指向其双亲*/
/*当p=bt时f为NULL*/
{ fag=0; /*fag=0时需修改f指针信息，fag=1时不需修改*/
if (p->lch==NULL)
s=p->rch; /*被删除结点为叶子或其左子树为空*/
else if (p->rch==NULL)
s=p->lch;
else { q=p; /*被删除结点的左、右子树均非空*/
s=p->lch;
while (s->rch!=NULL)
{ q=s;
s=s->rch;
} /*寻找s结点*/
if (q=p)
q->lch=s->lch;
else q->rch=s->lch;
p->data=s->data; /*s所指向的结点代替被删除结点*/
DISPOSE(s);
Fag=1;
}
if (fag=0) /*需要修改双亲指针*/
{ if (f=NULL)
bt=s; /*被删除结点为根结点*/
else if (f->lch=p)
f->lch=s;
else f->rch=s;
DISPOSE(p); /*释放被删除结点*/
}
}
第七章 图
P134 用邻接矩阵表示法表示图，除了存储用于表示顶点间相邻关系的邻接矩阵外，通常还需要用一个顺序表来存储顶点信息。其形式说明如下：
# define n 6 /*图的顶点数*/
# define e 8 /*图的边(弧)数*/
typedef char vextype; /*顶点的数据类型*/
typedef float adjtype; /*权值类型*/
typedef struct
{vextype vexs[n];
adjtype arcs[n][n];
}graph;
P135 建立一个无向网络的算法。
CREATGRAPH(ga) /*建立无向网络*/
Graph * ga;
{
int i,j,k;
float w;
for(i＝0;i<n;i++ )
ga ->vexs[i]＝getchar(); /*读入顶点信息，建立顶点表*/
for(i＝0;i<n;i++ )
for(j＝0;j<n;j++)
ga ->arcs[i][j]＝0; /*邻接矩阵初始化*/
for(k＝0;k<e;k++) /*读入e条边*/
(scanf("％d％d％f",&I,&j,&w); /*读入边(vi,vj)上的权w */
ga ->arcs[i][j]＝w;
ga - >arcs[j][i]＝w;
}
} /*CREATGRAPH*/
P136 邻接表的形式说明及其建立算法：
typedef struct node
{int adjvex; /*邻接点域*/
struct node * next; /*链域*/
}edgenode; /*边表结点*/
typedef struct
{vextype vertex; /*顶点信息*/
edgenode link; /*边表头指针*/
}vexnode; /*顶点表结点*/
vexnode ga[n];
CREATADJLIST(ga) /*建立无向图的邻接表*/
Vexnode ga[ ];
{int i,j,k;
edgenode * s;
for(i=o;i<n;i++＝ /*读入顶点信息*/
(ga[i].vertex＝getchar();
ga[i].1ink＝NULL; /*边表头指针初始化*/
}
for(k＝0;k<e;k++＝ /*建立边表*/
{scanf("％d％d",&i,&j); /*读入边(vi , vj)的顶点对序号*/
s＝malloc(sizeof(edgenode)); /*生成邻接点序号为j的表结点*s */
s-> adjvex＝j;
s- - >next：＝ga[i].Link;
ga[i].1ink＝s; /*将*s插入顶点vi的边表头部*/
s＝malloc(size0f(edgende)); /*生成邻接点序号为i的边表结点*s */
s ->adjvex＝i;
s ->next＝ga[j].1ink;
ga[j].1ink＝s; /*将*s插入顶点vj的边表头部*/
}
} /* CREATADJLIST */
P139 分别以邻接矩阵和邻接表作为图的存储结构给出具体算法，算法中g、g1和visited为全程量，visited的各分量初始值均为FALSE。
int visited[n] /*定义布尔向量visitd为全程量*/
Graph g; /*图g为全程量*/
DFS(i) /*从Vi+1出发深度优先搜索图g，g用邻接矩阵表示*/
int i;
{ int j;
printf("node：％c＼n" , g.vexs[i]); /*访问出发点vi+1 */
Visited[i]＝TRUE; /*标记vi+l已访问过*/
for (j＝0;j<n;j++) /*依次搜索vi+1的邻接点*/
if((g.arcs[i][j]＝＝1) ＆＆(! visited[j]))
DFS(j); /*若Vi+l的邻接点vj+l未曾访问过，则从vj+l出发进行深度优先搜索*/
} /*DFS*/
vexnode gl[n] /*邻接表全程量*/
DFSL(i) /*从vi+l出发深度优先搜索图g1，g1用邻接表表示*/
int i;
{ int j;
edgenode * p;
printf("node：％C\n" ,g1[i].vertex);
vistited[i]＝TRUE;
p＝g1[i].1ink; /*取vi+1的边表头指针*/
while(p !＝NULL) /*依次搜索vi+l的邻接点*/
{
if(! Vistited[p ->adjvex])
DFSL(p - >adjvex); /*从vi+1的未曾访问过的邻接点出发进行深度优先搜索*/
p＝p - >next; /*找vi+l的下一个邻接点*/
}
} /* DFSL */
P142 以邻接矩阵和邻接表作为图的存储结构，分别给出宽度优先搜索算法。
BFS(k) /＊从vk+l出发宽度优先搜索图g，g用邻接矩阵表示，visited为访问标志向量*/
int k;
{ int i,j;
SETNULL(Q); /*置空队Q */
printf("％c＼n"，g.vexs[k]); /*访问出发点vk+l*x/
visited[k]＝TRUE; /*标记vk+l已访问过*/
ENQUEUE(Q，K); /*已访问过的顶点(序号)入队列*/
While(!EMPTY(Q)) /*队非空时执行*/
{i＝DEQUEUE(Q); /*队头元素序号出队列*/
for(j＝0;j<n;j++)
if((g.arcs[i][j]＝＝1)＆＆(! visited[j]))
{printf("％c＼n" , g.vexs[j]); /*访问vi+l的未曾访问的邻接点vj+l */
visited[j]＝TRUE;
ENQUEUE(Q,j); /*访问过的顶点入队*/
}
}
} /* BFS */
BFSL(k) /*从vk+l出发宽度优先搜索图g1，g1用邻接表表示*/
int k
{ int i;
edgenode * p;
SETNULL(Q);
printf("％c＼n" , g1[k].vertex);
visited[k]＝TRUE;
ENQUEUE(Q,k);
while(! EMPTY(Q));
{ i＝DEQUEUE(Q);
p＝g1[i].1ink /*取vi+l的边表头指针*/
while(p !＝NULL) /*依次搜索vi+l的邻接点*/
{ if( ! visited[p - >adjvex]) /*访问vi+l的未访问的邻接点*/
{ printf{"％c＼n" , g1[p - >adjvex].vertex};
visited[p - >adjvex]＝TRUE;
ENQUEUE(Q,p - >adjvex); /*访问过的顶点入队*/
}
p＝p - >next; /*找vi+l的下一个邻接点*/
}
}
} /*BFSL*/
P148 在对算法Prim求精之前，先确定有关的存储结构如下：
typdef struct
{Int fromvex，endvex; /*边的起点和终点*/
float length; /*边的权值*/
} edge;
float dist[n][n]; /*连通网络的带权邻接矩阵*/
edgeT[n-1]; /*生成树*/
P149 抽象语句(1)可求精为：
for(j=1;j<n;j++) /*对n-1个蓝点构造候选紫边集*/
{T[j-1].fromvex＝1}; /*紫边的起点为红点*/
T[j-1].endvex＝j+1; /*紫边的终点为蓝点*/
T[j-1].1ength＝dist[0][j]; /*紫边长度*/
}
P149 抽象语句(3)所求的第k条最短紫边可求精为：
min＝max; /*znax大于任何边上的权值*/
for (j＝k;j<n-1;j++) /*扫描当前候选紫边集T[k]到T[n-2]，找最短紫边*/
if(T[j].1ength<min)
{min＝T[j].1ength;m＝j; /*记录当前最短紫边的位置*/
}
P149 抽象语句(4)的求精：
e＝T[m];T[m]＝T[k];T[k]＝e， /* T[k]和T[m]交换*/
v＝T[kl.Endvex]; /* v是刚被涂红色的顶点*/
P149 抽象语句(5)可求精为：
for(j＝k+1;j<n-1;j++) /*调整候选紫边集T[k+1]到T[n-2]*/
{d＝dist[v-1][T[j].endvex-1]; /*新紫边的长度*/
if(d<T[j].1ength) /*新紫边的长度小于原最短紫边*/
{T[j].1ength＝d;
T[j].fromvex＝v; /*新紫边取代原最短紫边*/
}
}
P150 完整的算法：
PRIM() /*从第一个顶点出发构造连通网络dist的最小生成树，结果放在T中*/
{int j , k , m , v , min , max＝l0000;
float d;
edge e;
for(j=1;j<n;j++) /*构造初始候选紫边集*/
{T[j-1].formvex＝1; /*顶点1是第一个加入树中的红点*/
T[j-1].endvex＝j+1;
T[j-1].length＝dist[o][j];
}
for(k＝0;k<n-1;k++) /*求第k条边*/
{min＝max;
for(j＝k;j<n-1;j++) /*在候选紫边集中找最短紫边*/
if(T[j].1ength<min)
{min＝T[j].1ength;
m＝j;
} /*T[m]是当前最短紫边*/
}
e＝T[m];T[m]＝T[k];T[k]＝e; /*T[k]和T[m]交换后，T[k]是第k条红色树边*/
v＝T[k].endvex ; /* v是新红点*/
for(j＝k+1;j<n-1;j++) /*调整候选紫边集*/
{d＝dist[v-1][T[j].endvex-1];
if(d<T[j].1ength);
{T[j].1ength＝d;
T[j].fromvex＝v;
}
}
} /* PRIM */
P151 Kruskl算法的粗略描述：
T＝(V,φ);
While(T中所含边数<n-1)
{从E中选取当前最短边(u,v);
从E中删去边(u,v);
if((u,v)并入T之后不产生回路，将边(u,v)并入T中;
}
P153 迪杰斯特拉算法实现。算法描述如下：
#define max 32767 /*max代表一个很大的数*/
void dijkstra (float cost[][n],int v)
/*求源点v到其余顶点的最短路径及其长度*/
{ v1=v-1;
for (i=0;i<n;i++)
{ dist[i]=cost[v1][i]; /*初始化dist*/
if (dist[i]<max)
pre[i]=v;
else pre[i]=0;
}
pre[v1]=0;
for (i=0;i<n;i++)
s[i]=0; /*s数组初始化为空*/
s[v1]=1; /*将源点v归入s集合*/
for (i=0;i<n;i++)
{ min=max;
for (j=0;j<n;j++)
if (!s[j] && (dist[j]<min))
{ min=dist[j];
k=j;
} /*选择dist值最小的顶点k+1*/
s[k]=1; /*将顶点k+1归入s集合中*/
for (j=0;j<n;j++)
if (!s[j]&&(dist[j]>dist[k]+cost[k][j]))
{ dist[j]=dist[k]+cost[k][j]; /*修改 V-S集合中各顶点的dist值*/
pre[j]=k+1; /*k+1顶点是j+1顶点的前驱*/
}
} /*所有顶点均已加入到S集合中*/
for (j=0;j<n;j++) /*打印结果*/
{ printf("%f\n%d",dist[j],j+1;);
p=pre[j];
while (p!=0)
{ printf("%d",p);
p=pre[p-1];
}
}
}
P155 弗洛伊德算法可以描述为：
A(0)[i][j]=cost[i][j]; //cost为图的邻接矩阵
A(k)[i][j]=min{A(k-1) [i][j],A(k-1) [i][k]+A(k-1) [k][j]}
其中 k=1,2,…,n
P155 弗洛伊德算法实现。算法描述如下：
int path[n][n]; /*路径矩阵*/
void floyd (float A[][n],cost[][n])
{ for (i=0;i<n;i++) /*设置A和path的初值*/
for (j=0;j<n;j++)
{ if (cost[i][j]<max)
path[i][j]=j;
else { path[i][j]=0;
A[i][j]=cost[i][j];
}
}
for (k=0;k<n;k++)
/*做n次迭代，每次均试图将顶点k扩充到当前求得的从i到j的最短路径上*/
for (i=0;i<n;i++)
for (j=0;j<n;j++)
if (A[i][j]>(A[i][k]+A[k]
Ⅱ C语言题急求！~！~！~！~！~！~！~！~！~！
1．
最初的C语言是为描述和实现
UNIX
操作系统而设计的。
2．
C语言规定，标识符必须以字母或
下划线
开头。
3．
C语言的double型数据在内存中占用
8
个字节的存储单元。
4．
×C语言的变量有
2
种存储类型，其中
static
型变量不进行初始化时，初值自动为0
5．写出下列表达式的求值结果：
(1)
2+3<=2
0
(2)
5/3+2
3
(3)
!
(3>2)||8!=7
1
(4)
3+7%3
4
6．已知int=12;
执行语句a*=2+4后，变量a的值为
24
。
7．已知int=2,b;
执行语句b=
a--;
后，变量a的值为
1
,
b的值为
2
。
8．若有int
a=2，b=1，c=0;
执行语句c=a++
-
b
-
-;
后，变量c的值为
1
,b的值为
0
一、
判断题（1×5分,正确的画√，错误的画×）
（×）1.
C语言俗称“低级语言的高级形式”，这说明C语言的功能不强。
（√）2.
C语言允许用实型表达式向整型变量赋值。
×（×）3.
C语言的全局变量只能是extern存储类型。
×（×）4.
已知int
a[4],*p;则语句p=&a;是正确的。
（×）5.
下面的程序段构成死循环。
a=5;
while
(1)
{a--;
if
(a<0)
break
;
}
三、单项选择题：（2×10分）
1.
在IBM-PC机中，unsigned
int类型表示的数据范围是（
D
）。
A）0-127
B）0-255
C）0-32767
D）0-65535
2.
下列符号中，合法的C常量是（
C
）。
A)
1e8.2
B)
0XFFH
C)
‘\n’
D)
089
3．语句x=3;
do{printf(“%d”,x);x--}while(x=
=0);
的执行结果是（
C
）。
A）3210
B）
321
C）3
D）无任何显示
4.
已知p、q
是两个同类型的指针变量，下列表达式有语法错误的是（
B
）。
（A）p!=NULL&&p=
=q
（B）
p*q
（C）p++,q--
（D）p-q+1
5．若k=
-1,
表达式k=
k>=0
?
(k-2)
:
(
k+2)
的值为（
D
）。
（A）-3
（B）
-2
（C）1
（D）2
×6．下面关于C函数的说法中正确的是（
B
）。
A）C函数的返回值类型必须是整型、实型或指针三者之一
B）C函数的返回值必须用return语句带回主函数
C）C函数允许递归调用，也允许在函数体中定义子函数
D）任何C函数必须使用return语句带回主程序
×7．若定义typedef
struct
user
{int
num;
char
name[21];
long
code;}
UserTp,;
则表达式
sizeof(UserTp)的值为（
D
）。
A)
0
B)
21
C)
31
D)
27
×8．已知static
int
a[
]={1,2,3,4};
int
*p;
若有p=a+2;
则*p++的值为（
C
）。
A）1
B）2
C）3
D）4
×9．定义C函数时，若缺省函数返回值类型，则返回值类型为（
A
）。
A）int
B）char
C）void
D）char
*
10.
×为只读操作打开正文（文本）文件，正确的打开方式是（
A
）。
A)
“r+”
B)
“a”
C)
“w”
D)
“rb”
四、多项选择题（2×5分,多选或错选不得分，少选得1分）
1．以下数据类型在内存中占用4个字节的是（
BC
）。
A)
int
B)
unsigned
long
C)
float
D)
unsigned
char
×2.
定义char
s[81];
后，能正确输入一个字符串到数组s的语句是（
ABC
）。
A）gets(s);
B）scanf
(”%c”,s);
C）scanf
(”%s”,&s[0]);
D）gets(&s[0]);
3.
以下关于C源程序文件的说法中正确的是（
BCD
）
A）是一种二进制文件
B）是一种文本（ASCII码）文件
C）可以用DOS的type命令显示其内容
D）文件扩展名一般为c
×4.
下面关于C语言的说法错误的是（
ACD
）。
A)
C函数必须有形式参数
B)
任何复合语句体的{
}中允许定义局部变量
C)
局部变量都存储在动态存贮区
D)
C程序的执行起点只能是main函数
5.
以下程序正确计算p=n!
(n>=0)的是（
AB
）。
A)
for(p=1.0,k=1;k<=n;)
p*=k++;
B)
p=1.0;k=0;while(k<n)
p*=++k;
C)
p=1.0;k=1;do{++k;p*=k;}
while(k<=n);
D)
p=1.0;for(k=n;k>=1;k--)
p*=k--;
五、读程序与程序填空（共22分）
1．阅读以下程序，写出程序运行结果：（共3Χ4分）
×
(1)
#include
”stdio.h”
void
main()
{char
a[61],*s;int
n;
gets(a);
for(s=a;*s;s++)
if(*s>=’a’&&*s<=’z’)
*s-32;
puts(a);
}
若程序的输入为abcb,则输出结果为
ABCD
。
(2)
#include
”stdio.h”
void
main()
{
int
s=0,k=0;
while(k<4)
{s+=k;k++;printf(“%d”,s);}
}
该程序的输出是
0136
。
(3)
#include
“stdio.h”
void
main(
)
{static
int
a[5]={2,-15,1,0,-7};
int
i；
for(i=0;i<5;i++)
if(a[i]<0)
a[i]
=
-a[i];
for(i=4;i>=0;i--)
printf(“%4d”,
a[i])；
}
该程序的输出是7
0
1
15
12
(4)
×#include
“stdio.h”
#define
N
5
int
swap(int
*p,
int
*q)
{int
t;
if(p<q)
{t=*p;*p=*q;*q=t;}
return
p<q;
}
void
f(int
a[
],int
m)
{int
*p,
*q;
p=a;q=a+m;
while(swap(p,q))
{p++;
q--}
}
void
main(
)
{int
m,a[N];
for(m=0;m<N;m++)
scanf(“%d”,a+m);
f(a,N-1);
for(m=0;m<N;m++)
printf(“%d”,a[m]);
}
若程序的输入为1
2
3
4
5,
则输出结果为
5
4
3
2
1
2．程序填空：（共10分）
（1）
×以下程序的功能是输入年、月、日，求该日期是这一年的第几天，填空使之完善。
#include
“stdio.h”
int
IsLeap(int
y)
/*
此函数的功能是判断年号y是否为闰年
*/
/*
已知闰年的条件是年号y能被4整除，但不能被100整除，或年号y能被400整除
*/
{int
r;
if(
y%4=
=0&&y%100!=0||y%400=
=0
)
r=1;
else
r=
0
;return
r;}
int
DaysofMonth(int
y,int
m)
/*
此函数的功能是求y年m月的天数
*/
{
int
days;
switch(m)
{case
4,6,9,11:days=30;break;
case
2:if(IsLeap(y))
days=28;else
days=29;break;
default:days=
31
;
}
return
days
;
}
void
main
(
)
{int
k,y,m,d,days;
printf(“Input
year,month,date:”);scanf(“%d%d%d”,&y,&m,&d);
days=0;
for(k=
1
;
k<m
;k++)days+=
DaysofMonth(y,k);
days+=d;
printf(“days=%d\n”,days);}
(2)
下面程序的功能是输出100至1000以内的素数,请填空使之完善。
#include
“stdio.h”
#include
“
math.h
”
void
main
(
)
{
int
m,k,j;
for(m=100;m<=1000;m++)
{k=sqrt(m);
for(j=2;
j<=k
;j++)
if(m%j
=
=
0)
break;
if(
j>k或
j>=k+1
)
printf(“%5d”,m);
}
}
六、根据题意编写程序：（3Χ6+10=28分）
1.
编程序，从键盘输入a0,a1,a2,…,an计算s=ao+a1x+a2x2+…+anxn
×2．编程序，将正文（文本）文件中的小写字母变成大写并统计输出文件有多少个字符，
要求文件名由键盘输入。
×3．编程序，输入n个英文单词（n用#define定义为8）,然后将这些单词按英文字典顺
序输出。
×4．编程序，从键盘输入n个学生的姓名、学号和住址，按照学号次序把它们串成一个单向链表。
1．
main(
)
{float
x,a[n+1],s=0.0;
int
i,n;printf(“请输入n和x的值”)；scanf(“%d,%f”,n,x);printf(“请输入所有系数的值”)；
for(i=0;i<=n;i++)scanf(“%f”,&a[i]);
for(i=0;i<=n;i++)
s=s+a[i]*pow(x,i);printf(“s=%f”,s”)；}
2.
#include
“stdio.h”
main
(
)
{int
i;char
ch,name[80];
FILE
*fp;
i=0;
printf(“please
input
the
filename:”);
scanf(“%s”,name);
if((fp=fopen(name,”r+”))==NULL)
{
printf(“cannot
open
the
file”);
exit(0);}
ch=fgetc(fp);
i++;
if((ch>=’a’)&&(ch<=’z’))
ch=ch-32;
fputc(ch,fp);
printf(“字符总数为%”,i);
fclose(fp);
}
3.
#include
"stdio.h"
#include
"string.h"
#define
n
8
void
main(
)
{char
*p,*s[n],t[21];
int
i,j;
for(i=0;i<n;i++)
{scanf("%s",t);
s[i]=(char
*)malloc(strlen(t)+1);
strcpy(s[i],t);
}
for(i=0;i<n-1;i++)
for(j=i+1;j<n;j++)
if(strcmp(s[i],s[j])>0)
{p=s[i];s[i]=s[j];s[j]=p;}
for(i=0;i<n;i++)
printf("%s\n",s[i]);
}
输入
basic
good
well
c
pascal
morning
hlr
cpp
输出：
basic
c
cpp
good
hlr
morning
pascal
well
Ⅲ C语言程序设计考题
解: x>i,i=2
当x输入为3时,执行结果为0,1
当x输入为4时,执行结果为1,0,1
当x输入为5时,执行结果为0,0,0,1
当x输入为6时,执行结果为1,1,0,0,1
当x输入为7时,执行结果为0,0,0,0,0,1
............
由执行结果可看出该程序的功能是:通过输入一个数x,得到执行结果,由结果中1的个数,判断在小于等于x范围内,x的约数的个数.
Ⅳ 计算机二级C语言操作题积累
2017年计算机二级C语言操作题积累
多媒体计算机是当前计算机领域中最引人注目的高新技术之一。多媒体计算机就是利用计算机技术、通信技术和大众传播技术，来综合处理多种媒体信息的计算机。下面是我整理的关于计算机二级C语言操作题积累，欢迎大家参考!
一、单选题(每小题1分，共40分)
1[单选题] 下列关于综合布线系统的描述中，错误的是()。
A.双绞线扭绞可以减少电磁干扰
B.管理子系统设置在楼层配线间内
C.多介质插座是用来连接铜缆和光纤的
D.对于建筑群子系统直埋布线是最理想的方式
2[单选题] IP地址块59.67.79.128/28、59.67.79.144/28和59.67.79.160/27经聚合后可用地址数为()。
A.62
B.64
C.126
D.128
3[单选题] IP地址块202.111.15.128/28、202.111.15.144/28和202.111.15.160/28经过聚合后可用的地址数为()。
A.40
B.42
C.44
D.46
4[单选题] 下列攻击手段中，基于网络的入侵防护系统无法阻断的是()。
A.SYNFlooding
B.SQL注入
C.DDOS
D.PingofDeath
5[单选题] 差异备份、增量备份、完全备份三种备份策略的备份速度由快到慢依次为()。
A.增量备份、差异备份、完全备份
B.差异备份、增量备份、完全备份
C.完全备份、差异备份、增量备份
D.完全备份、增量备份、差异备份
6[单选题] CiscoPIX525防火墙用来允许数据流从具有较低安全级接口流向较高安全级接口的配置命令是()。
A.fixup
B.conit
C.global
D.nameif
7[单选题] 在Windows2003系统下DHCP服务器中添加排除时，应输入的信息是()。
A.起始IP地址和结束IP地址
B.起始IP地址和网关地址
C.起始IP地址和MAC地址
D.起始IP地址和掩码
8[单选题] 下列关于服务器技术的描述中，错误的是()。
A.集群系统中一台主机出现故障时不会影响系统的性能
B.采用RISC结构处理器的服务器通常使用UNIX系统
C.热插拔功能允许用户在不切断电源的情况下更换硬盘、电源等
D.分布式内存访问(NUMA.技术将对称多处理器(SMP)和集群(Cluster)技术结合起来
9[单选题] 下列对交换机中交换表的描述中，错误的是()。
A.在一些高端交换机中，交换表通常被保存在CAM存储器中
B.交换表中没有接收帧的目的MAC地址时，交换机用Flood技术转发该帧
C.使用“showmac-addres-table”命令可显示小型交换机的交换表内容
D.交换表的内容包括目的IP地址及其所对应的交换机端口号
10[单选题] 下列关于无线网络HipeR1AN/2协议的描述中，错误的.是()。
A.采用5GHz工作频段
B.上行速率最多可达54Mbps
C.室外最大覆盖范围为30米
D.可支持面向连接的传输服务
二、综合题(每空2分，共40分)
(1)打开工作簿文件EXCEL.xlsx,将工作表sheetl的Al：El单元格合并为一个单元格,内容水平居中,计算“合计”列的内容,将工作表命名为“科研经费使用情况表”.
(2)选取“科研经费使用情况表”的“项目编号”列和“合计”列的单元格内容,建立“簇状棱锥图”,x轴上的项为项目编号,图表标题为“科研经费使用情况图”,插入到表的A7：El8单元格区域内.
三、演示文稿题
打开考生文件夹下的演示文稿yswg.pptx,按照下列要求完成对此文稿的修饰并保存.
(1)整个演示文稿设置成“时装设计”模板;将全部幻灯片切换效果设置成“分割”.
(2)将第二张幻灯片对象部分的动画效果设置为“向内溶解”;在演示文稿的开始处插入一张“标题幻灯片”,作为文稿的第一张幻灯片,主标题键人“讽刺与幽默”,并设置为60磅、加粗、红色(请用自定义标签中的红色250,绿色1,蓝色1).
二、电子表格题
(1)【解题步骤】
步骤1：通过“答题”菜单打开EXCEL.xlsx文件，选中A1：E1单元格，在【开始】功能区的【对齐方式】分组中，单击“合并后居中”按钮，合并单元格并使内容居中。
步骤2：计算“合计”列内容。在E3单元格中插入公式“=SUM(B3：D3)”，并按回车键，将鼠标移动到E3单元格的右下角，按住鼠标左键不放向下拖动即可计算出其他行的值。
注：当鼠标指针放在已插入公式的单元格的右下角时，它会变为小十字“+”，按住鼠标左键拖动其到相应的单元格即可进行数据的自动填充。
步骤3：双击现有名称，输入新名称“科研经费使用情况表”。
步骤4：保存文件。
(2)【解题步骤】
步骤1：按照要求建立“簇状棱锥图”。选中“项目编号”列和“合计”列，在【插入】功能区的【图表】分组中，单击“创建图表”按钮，弹出“插入图表”对话框，在“柱形图”中选择“簇状棱锥图”，单击“确定”按钮，即可插入图表。
步骤2：按照题目要求设置图表标题。在插入的图表中，选中图表标题，改为“科研经费使用情况图”。
步骤3：调整图的大小并移动到指定位置。选中图表，按住鼠标左键单击图表不放并拖动，将其拖动到A7：El8单元格区域内。
注：不要超过这个区域。如果图表过大，无法放下，可以将鼠标放在图表的右下角，当鼠标指针变为“、”时。按住左键拖动可以将图表缩小到指定区域内。
步骤4：保存文件。
三、演示文稿题
(1)【解题步骤】
步骤1：通过“答题”菜单打开ysw9.pptx文件，按照题目要求设置幻灯片模板。选中幻灯片，在【设计】功能区的【主题】分组中，单击“其他”下拉三角按钮，选择“时装设计”模板。
步骤2：按照题目要求设置幻灯片的切换效果。选中幻灯片，在【切换】功能区的【切换到此幻灯片】分组中，单击“其他”下拉三角按钮，在“细微型”选项组中选择“分割”效果。
(2)【解题步骤】
步骤1：按照题目要求设置剪贴画的动画效果。选中第二张幻灯片的图片，在【动画】功能区的【动画】分组中，单击“其他”下拉三角按钮，选择“更多进入效果”选项，弹出“更改进入效果”对话框。在“基本型”选项组中选择“向内溶解”效果，单击“确定”按钮。
步骤2：按照要求插入新幻灯片。用鼠标右键单击第一张幻灯片前面的位置，在【开始】功能区的【幻灯片】分组中，单击“新建幻灯片”下拉三角按钮，选择“标题幻灯片”选项。新插入的幻灯片作为第一张幻灯片。
步骤3：在第一张幻灯片的“单击此处添加标题”处输入“讽刺与幽默”。
步骤4：按题目要求设置字体。选中“讽刺与幽默”，在【开始】功能区的【字体】分组中，单击“字体”按钮，弹出“字体”对话框。在“字体”选项卡中，设置“大小”为“60磅”，设置“字体样式”为“加粗”。单击“字体颜色”下拉三角按钮，选择“其他颜色”选项，弹出“颜色”对话框。单击“自定义”选项卡，设置“红色”为“250”，设置“绿色”为…l’，设置“蓝色”为…l’，单击“确定”按钮，再单击“确定”按钮。
步骤5：保存文件。
三、应用题(共20分)
;