Ⅰ 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分)
;