试卷详情
-
初级程序员下午试题-50
-
[简答题][函数2.1说明]
下面程序的功能是:将由键盘输入的某个十进制数转换成对应的R进制数并输出。这里R是 2到16的整数,由键盘输入。例如,输入n=128,base=13后的输出为9B。
[函数2.1]
#include <stdio.h>
main( )
{ char b[16]={’0’,’1’,’2’,’3’,’4’,’5’,’6’,’7’,’8’,’9’,’A’,’B’,’C’,’D’,’E’,’F’};
int c[64],n,i=0,base;
printf("Enter a number:");scaaf("%d",&n);
printf("Enter new base:");scanf("%d",&base);
do{c[i]= (1) ;
i++;
n=n/base;
}while( (2) );
printf("Transmit new base:");
for(- -i;i>=0;- -i)printf("%c", (3) );
}
[函数2.2说明]
所谓回文字符中是指正序和逆序拼写相同的字符串,例如astrtsa,adgdtdgda等。下面函数int fun(char *str)的功能是判断字符串str是否是回文,当字符串是回文时,函数返回1,否则返回0。
[函数2.2]
int fun(char *str)
{ int i,j,l;
for(i=0;str[i]! =’/0’;i++);
l=i/2;
for(j=0,i- -;j<=1; (4) )
if( (5) ) return 0;
return 1;
}
-
[简答题][说明]
Kruskal算法是一种构造图的最小生成树的方法。设G为一无向连通图,令T是由G的顶点构成的于图,Kmskal算法的基本思想是为T添加适当的边使之成为最小生成树:初始时,T中的点互相不连通;考察G的边集E中的每条边,若它的两个顶点在T中不连通,则将此边添加到T中,同时合并其两顶点所在的连通分量,如此下去,当添加了n-1条边时,T的连通分量个数为1,T便是G的一棵最小生成树。
下面的函数void Kruskal(EdgeType edges[],int n)利用Kruskal算法,构造了有n个顶点的图 edges的最小生成树。其中数组father[]用于记录T中顶点的连通性质:其初值为father[i]=-1 (i=0,1,…,n-1),表示各个顶点在不同的连通分量上;若有father[i]=j,j>-1,则顶点i,j连通;函数int Find(int father[],int v)用于返回顶点v所在树形连通分支的根结点。
[函数]
#define MAXEDGE 1000
typedef struct
{ int v1;
int v2;
}EdgeType;
void Kruskal(EdgeType edges[],int n)
{ int father[MAXEDGE];
int i,j,vf1,vt2;
for(i=0;i<n;i+ +) father[i]=-1;
i=0;
j=0;
while(i<MAXEDGE && j< (1) )
{ vf1=Find(father,edges[i].v1);
vf2=Find(father,edges[i].v2);
if( (2) )
{ (3) =vf1;
(4) ;
printf("%3d%3d/n",edges[i].v1,edges[i].v2);
}
(5) ;
}
}
int Find(int father[],int v)
{ int t;
t=v;
while(father[t]>=0) t=father[t];
return(t);
}
-
[简答题][说明]
邻接表是图的一种顺序存储与链式存储结合的存储方法。其思想是:对于图G中的每个顶点 vi,将所有邻接于vi的顶点vj连成一个单链表,这个单链表就称为顶点vi的邻接表,其中表头称作顶点表结点VertexNode,其余结点称作边表结点EdgeNode。将所有的顶点表结点放到数组中,就构成了图的邻接表AdjList。邻接表表示的形式描述如下: #define MaxVerNum 100 /*最大顶点数为100*/
typedef struct node{ /*边表结点*/
int adjvex; /*邻接点域*/
struct node *next; /*指向下一个边表结点的指针域*/ }EdgeNode;
typedef struct vnode{ /*顶点表结点*/
int vertex; /*顶点域*/
EdgeNode *firstedge; /*边表头指针*/
}VertexNode;
typedef VertexNode AdjList[MaxVerNum]; /*AdjList是邻接表类型*/
typedef struct{
AdjList adjlist; /*邻接表*/
int n; /*顶点数*/
}ALGraph; /*ALGraph是以邻接表方式存储的图类型*/
深度优先搜索遍历类似于树的先根遍历,是树的先根遍历的推广。
下面的函数利用递归算法,对以邻接表形式存储的图进行深度优先搜索:设初始状态是图中所有顶点未曾被访问,算法从某顶点v出发,访问此顶点,然后依次从v的邻接点出发进行搜索,直至所有与v相连的顶点都被访问;若图中尚有顶点未被访问,则选取这样的一个点作起始点,重复上述过程,直至对图的搜索完成。程序中的整型数组visited[]的作用是标记顶点i是否已被访问。
[函数]
void DFSTraverseAL(ALGraph *G)/*深度优先搜索以邻接表存储的图G*/
{ int i;
for(i=0;i< (1) ;i++) visited[i]=0;
for(i=0;i< (1) ;i++)if( (2) ) DF
-
[简答题][说明]
有若干教师,每个教师只有姓名,一个教师可以指导多名研究生;每名研究生有姓名和研究方向,程序最后输出每个教师指导的所有研究生的姓名和研究方向。
[Java程序]
public class Teacher {
String name;
int top=0;
Student[] student=new Student[20];
public Teacher( ) {}
public Teacher(String name) { this.name=name;}
boolean add(Student stu){
int len=this.student.length;
if (top<len-1) {
this.student[top]=siu;
(1) ;
return true;
}
else
return (2) ;
}
void disp( ){
System.out.println(“指导老师"”+this.name);
System.out.println(“研究生:”);
for(int i=0;i< (3) ;i++){
System.out.println(“姓名:”+this.student[i].name+“/t研究方向:”+this.student[i]. search);
}
}
public static void main(String[] args){
Teacher t[]={new Teacher(“李明”),new Teacher(“王华”)};
Student s1 = new Student(“孙强”,“数据库”);
Student s2 = new Student(“陈文”,“软件工程”);
Student s3 = new Student(“章锐”,“计算机网络”);
if(! t[0].add(s1)) {System.out.println(“每个老师最多只能指导20个学生!”);}
if(! t[0].add(a2)) {System.out.println(“每个老师最多只能指导20个学生!”);}
-
[简答题][说明]
下面的词典类Dic实现了简单的英译汉功能。程序运行后的输出为“我是一个学生”。
[C++程序]
#include <iostream.h>
#include <string.h>
#define Max 100
class Dic
{ int top;
char words[Max] [12];
char mean[Max] [20];
public:
Die( ){top=0;}
void add(char w[],char m[]){
strcpy(words[top],w);
strcpy(mean[top],m);
(1) ;
}
void trans(char str[]) {
int i=0,j=0,k=0,s;
char w[12],h[200];
while(l) {
if(str[i]! =’’&&str[i]! =’/0’)
w[j++]=str[i]; //读取单词的一个字符,记录在w中
else {
w[j]=’/0’;
for(s=0;s < top;s++)
if(strcmp(words[s],w) (2) 0) break;
if(s<top) //找到了,翻译成对应的mean[s]
{ strcpy(w,mean[s]); j= (3) ;}
else //未找到,翻译成(unknown)
{ strcpy(w,"(unknown)"}; j=9; }
for(s=0;s<j;s++)
h[k++]=w[s];
if(str[i]==’/0’) { (4) ; break;}
j=0;
}