北京工业大学 计算机软件基础考试习题

1、习 题 课1名词解释：数据，数据元素，数据结构。数据：数据就是计算机可以保存和处理的信息。数据元素：是组成数据的基本单位。 数据元素可以是一个数或字符串，也可以由若干数据项组成。数据项是数据的最小单位。数据结构：简单地说，数据结构就是研究数据及数据元素之间关系的一门学科。它包括三个方面的内容： 数据的逻辑结构、数据的存储结构和数据的运算。 数据结构是指数据之间的相互关系，即数据的组织形式。可以从集合的观点对数据结构加以形式化描述，即是一个二元组：Data-Structure = (D, R)其中：D是数据元素的集合，R是D上关系的集合。逻辑结构：数据的逻辑结构是指反映数据元素之间逻辑关系的数据

2、结构，它与数据的存储无关，是独立于计算机的。存储结构：数据的存储结构是逻辑结构用计算机语言的实现(亦称映像)，它是依赖于计算机语言的。算法：是由若干条指令组成的有限序列。2简述算法的五要素。有穷性：每条指令的执行次数必须是有限的。确定性：每条指令的含义必须明确，无二义性。可行性：每条指令都应在有限的时间内完成。输入性：具有零个或多个输入量，即算法开始前对算法给出的初始量。输出性：至少产生一个输出。3评价一个“正确的”算法主要有哪两个指标？(1) 时间复杂度：依据算法编制成程序后，在计算机上运行时所消耗的时间。(2) 空间复杂度：依据算法编制成程序后，在计算机执行过程中所需要的最大存储空间。4描

3、述以下三个概念的区别：头指针、头结点、首元结点(第一个元素结点)。头指针就是指向链表中第一个结点的指针。单链表是由头指针唯一确定的。因此可以用头指针的名字来命名单链表。头结点是在单链表第一个元素所在结点之前附设的一个结点。头结点的指针域存储第一个元素所在结点的存储位置；数据域可以不存储任何信息，也可以存储如线性表的长度等附加信息。设置头结点后，可使空表和非空表的逻辑状态及运算统一起来。首元结点就是第一个数据元素所在的结点。5有一线性表存储在一个带头结点的循环单链表L中，写出计算线性表元素个数的算法。int length(NODE *L) NODE *p; int counter=0; p=L-

4、next; while(p!=L) p=p-next; counter+; return counter; 6假设有一个循环单链表的长度大于1，且表中既无头结点也无头指针。已知S为指向链表中某结点的指针，试编写算法，在链表中删除结点S的前趋结点。提示：(1) 定义一个指针变量p指向结点*s的直接后继；(2) 定义一个指针变量q指向结点*s；(3) 当p-next不等于s时，令q=p，p=p-next; 重复上述处理直至p-next=s；(4) 令q-next=s; free(p)。void delprior(NODE *s) NODE *p, *q; p=s-next; q=s; while(

5、p-next!=s) q=p; p=p-next; q-next=s; free(p);7已知指针ha和hb分别指向两个单链表的头结点，且头结点的数据域中存放链表的长度，试写一算法将这两个链表连接在一起(即令其中一个表的首元结点连在另一个表的最后一个结点之后)，hc指向连接后的链表的头结点，并要求算法以尽可能短的时间完成连接运算。请分析你的算法的时间复杂度。8设计一个将线性链表进行逆置的算法。对于单链表，借助中间变量实现数据元素指针域中地址值的变化。参见Shiyan12.c的 reverse( )函数。9设有多项式 A(x) = 7 + 3x + 9x8 + 3x15 B(x) = 5x +

6、6x7-9x8 (1) 用单链表给出A(x)的存储表示； (2) 用单链表给出B(x)的存储表示；数据存储结构： typedef struct polyterm int coef; int exp; struct polyterm *next; TERM;10设有编号为1，2，3，4的四辆列车，顺序进入一个栈式结构的车站，具体写出这四辆列车开出车站的所有可能的顺序。1，2，3，4 1，2，4，3 1，3，2，41，3，4，2 1，4，3，2 2，1，3，42，1，4，3 2，3，1，4 2，3，4，12，4，3，1 3，2，1，4 3，2，4，13，4，2，1 4，3，2，111假设以带头结点

7、的循环单链表表示队列，并且只设一个指针指向队尾元素结点(不设头指针)，试编写相应的入列和出列算法。12假设以数组sequm存放循环队列的元素，同时设变量rear和quelen分别指示队尾元素的位置和内含元素的个数。试给出此循环队列的队满条件，并写出相应的入列和出列算法。队满条件：quelen=mstep1. 判定循环队列是否已满，若满，则给出队列溢出出错信息；step2. 队尾指针后移，将入队元素放入队尾指针所指的存储位置。step3. 队列元素个数增1。#define MAXSIZE m /* m为队列中数据元素个数的最大可能值*/ int sequMAXSIZE； /* 假设数据元素的类型

8、为整型*/ int quelen=0, rear=MAXSIZE-1；void addqueue(int x) if (quelen = MAXSIZE) printf(循环队列已满，上溢! n);exit(1);else rear = (rear+1)% MAXSIZE;sequ rear = x;quelen+;step1. 判定循环队列是否为空，若空，则给出队列溢出(下溢)信息；step2. 计算队头指针值，并读取队头元素；step3. 队列元素个数减1。#define MAXSIZE mint sequMAXSIZE；int quelen=0, rear=MAXSIZE-1；int d

9、elqueue( ) int front, x;if (quelen = 0) printf(循环队列已空，下溢！ n); x =-1;else front=(rear-quelen+MAXSIZE+1)% MAXSIZE; x = sequfront; quelen-;return x;13试将下列稀疏矩阵A用三元组形式来表示。 0 3 0 0 -7 0 0 0 0 0 8 0 0 0 0 20 0 0 0 0 0 0 -13 0 0 A=05551123215-7331844120553-1316二维数组A的元素是6个字符组成的串，行下标i的范围从0到8，列下标j的范围从1到10。从供选择

10、的答案中选出应填入下列关于数组存储叙述中( )内的正确答案。 (1) 存放A至少需要( )个字节。 (2) A的第8列和第5行共占( )个字节。 (3) 若A按行存放，元素A8，5 的起始地址与当A按列存放时的元素( )的起始地址一致。 供选择答案(1) a. 90； b. 180； c. 240； d. 270； e. 540；(2) a. 108；b. 114；c. 54； d. 60； e. 150；(3) a. A8,5；b. A3,10；c. A5,8；d. A0,9。 (1) 9*10*6=540 (2) (9+9)*6=108 (3) 8*10+5=85；85/9=9 余 4 答

11、案：A3，10；试验一：线性表的设计与实现 1. 线性表基本操作的实现：数据的存储结构#define MaxSize 1024 typedef int DataType; typedef struct node DataType dataMaxSize; int last; SequenList;人机交互部分内容：通过屏幕提示功能选择菜单；通过键盘输入实现功能的选择；要求：提示内容清晰易读，键盘操作简单准确；实现：循环扫描键盘，等待用户输入；根据输入内容确定要执行的分支程序。int main( ) SequenList MyList,*L; char cmd; int i, t, x; L=&

12、MyList; L-last=-1; do do clrscr( ); printf(nt c, C.Create Listn); printf(nt i, I .Insert); printf(nt d, D.Delete); printf(nt q, Q.QuitntYour choice:); cmd=getchar( ); while (?);while (cmd!=d)&(cmd!=D)& (cmd!=q)&(cmd!=Q)& (cmd!=i)&(cmd!=I)& (cmd!=c)&(cmd!=C);While (toupper(cmd)!=D)& (toupper(cmd)!=Q)

13、& (toupper(cmd)!=I)&(toupper(cmd)!=C); switch (cmd) case c: case C: CreateList(L); break; case i: case I: ? ? ? Insert(L,x,i); PrintOut(L); getch(); break; case d: case D: ? ? ? Delete(L,i); PrintOut(L); getch(); break; default: break; while(cmd!=q) & (cmd!=Q);printf (nInput the data to be inserted:

14、);scanf (%d,&x);printf (nInput the poistion to be inserted:);printf (n(1-%d)n,(L-last+2);scanf (%d,&i);printf(nInput the index_No of data to be deletedn);printf(n(1-%d):n,(L-last+1);scanf(%d,&i); while (toupper (cmd)!=Q);运算处理内容：建表、插入、删除、输出；实现：利用指针变量作为函数参数，传递 线性表地址；void CreateList (SequenList *L) int

15、 n, i, mydata; printf(nPlease input total number of data itemn); scanf(%d,&n); for(i=0;idatai=mydata; L-last=n-1; printf(nPress any key to continuen); getch( );int Insert (SequenList *L, DataType x, int i) int j; if (L-last=(MaxSize-1) printf (nOverflow!); return Null; else if (i(L-last+2) printf (r

16、ange error); return Null; else for (j=L-last;j=i-1;j-) L-dataj+1=L-dataj; L-datai-1=x; L-last=L-last+1; return (1);int Delete (SequenList *L,int i) int j; if (iL-last+1) printf (range error); return Null; else for (j=i;jlast;j+) L-dataj-1=L-dataj; L-last-; return (1);void PrintOut(SequenList *L) int

17、 i; for (i=0;ilast;i+) printf (data%d=, i+1); printf (%dt, L-datai); if (i!=0)&(i%4)=0) printf (n); 完善程序： #include #include #define Null 0线性表初值设置： L-last=-1;2. 一元多项式的相加、相乘的程序设计数据存储结构： typedef struct polyterm int coef; int exp; struct polyterm *next; TERM;人机交互部分内容：通过屏幕提示需要输入的数据和程序执行的结果；要求：提示内容清晰易读，键盘

18、操作简单准确。void main() TERM *ha,*hb,*hc,*p,*q,*h; printf(nInput the 1st polynomial); ha=creatpoly(); printf(nInput the 2nd polynomial); hb=creatpoly(); printf(nthe 1st polynomial is:); polyout(ha); printf(nthe 2nd polynomial is:); polyout(hb); hc=polyadd(ha,hb); printf(nthe addition of the two polynomia

19、l is:); polyout(hc); h=polymulti(ha,hb); printf(nthe multiplication of the two polynomial is:); polyout(h); return ; 运算处理内容：建表、相加、相乘、输出；实现：使用指针变量作为函数返回的参数， 传递线性表地址；条件：链表无头结点； 多项式系数和指数均为int型数据； 每个多项式数据输入的方式为： 系数，指数 数据按指数递减的顺序依次输入； 结束多项式数据输入的条件是： 0，0TERM *creatpoly( ) TERM *head,*r,*s; int m,n; head=(

20、TERM *)malloc (sizeof(TERM); printf(input coef and exp(1,2):n); scanf(%d,%d,&n,&m); r=head; while(n) s=(TERM *)malloc (sizeof(TERM); s-coef=n; s-exp=m; r-next=s; r=s; printf(nInput coef and exp:n); scanf(%d,%d, &n, &m); r-next=Null; r=head; head=head-next; free(r);/* 无头结点 */ return (head);TERM *poly

21、add(TERM *ha,TERM *hb) TERM *hc,*p,*q,*s,*r; int x; p=ha; q=hb; /* 无头结点 */ hc=(TERM *)malloc(sizeof(TERM); s=hc; while(p!=Null)&(q!=Null) if(p-exp=q-exp) x=p-coef+q-coef; if(x!=0) r=(TERM *)malloc(sizeof(TERM); r-exp=p-exp; r-coef=x; s-next=r; s=r; p=p-next; q=q-next; else if (p-expexp) r=(TERM *)ma

22、lloc (sizeof(TERM); r-coef=q-coef; r-exp=q-exp; s-next=r; s=r; q=q-next; else r=(TERM *)malloc(sizeof(TERM); r-exp=p-exp; r-coef=p-coef; s-next=r; s=r; p=p-next; while(p!=Null) r=(TERM *)malloc(sizeof (TERM); r-exp=p-exp; r-coef=p-coef; s-next=r; s=r; p=p-next; while(q!=Null) r=(TERM *)malloc (sizeo

23、f(TERM); r-exp=q-exp; r-coef=q-coef; s-next=r; s=r; q=q-next; s-next=Null; r=hc; hc=hc-next; free(r); return (hc);TERM *polymulti(TERM *f,TERM *g) TERM *fp,*gp,*hp,*q,*h; int maxp,p,r,x; maxp=f-exp+g-exp; h=(TERM *)malloc(sizeof(TERM); hp=h; g=reverse(g); for(r=maxp;r=0;r-) x=0; fp=f;gp=g; while(fp!

24、=Null)&(gp!=Null) p=fp-exp+gp-exp; if(pr)fp=fp-next; else if(pnext; else x+=fp-coef*gp-coef; fp=fp-next; gp=gp-next; /*end of while */ if(x!=0) q=(TERM *)malloc(sizeof(TERM); q-exp=r;q-coef=x; q-next=Null; hp-next=q;hp=q; /* end of for */ hp=h;h=h-next; free(hp); return (h);TERM* reverse(TERM *q) TE

25、RM *p1,*p2; if(q!=Null) p1=q-next; q-next=Null; while(p1!=Null) p2=p1-next;p1-next=q; q=p1;p1=p2; /* end of while */ return (q);void polyout(TERM *head) TERM *p,*q; p=head; while(p!=Null) printf(%d,%d ,p-coef,p-exp); p=p-next; printf(n);3. 约瑟夫环的程序设计数据存储结构描述： typedef struct tagnode int num; struct ta

26、gnode *next; LinkList; LinkList *head=Null,*last;人机交互部分内容：通过屏幕提示需要输入的数据和程序执行的结果；要求：提示内容清晰易读，键盘操作简单准确。int main( ) int n,m; printf (nInput the total number of people:n); scanf (%d,&n); printf (ninput the number of person you are to call:n); scanf (%d,&m); head=creat (n); last=select (head,m);n=last-nu

27、m; printf (the last one:%dn,n);free(last); printf (nPress any key to continue.n); getch ( );return (1);LinkList *creat (int n) LinkList *head,*s, *p; int i; s=(LinkList *)malloc (sizeof (LinkList); head=s; s-num=1;p=s; for (i=2;inum=i; p-next=s;p=s; p-next=head; return (head);LinkList *select (LinkL

28、ist *head, int m) LinkList *p,*q; int i, t, flag=0; p=head; t=1; q=p; /* q-前趋指针, p-当前指针 */ do p=q-next; t=t+1; if(t%m=0) printf(%4dt,p-num); if(q-next=q) flag=1;break; q-next=p-next; free(p); p=q; else q=p; while(q=p)|(flag=0); head=p; return (head); int main( ) int n, m, s; printf (Johephas problem

29、n); printf (input number of people, number to call,and start number:n); scanf (%d,%d,%d, &n, &m, &s); Josephus (n, m, s); getch ( ); void Josephus (int n, int m, int s) int *R, i, j; R=(int *)malloc (n+1)*sizeof (int); for (i=1;i=2;i-) s=(s+m-1)%i; if (s=0)s=i; printf (%d, Rs); for (j=s+1; jtop=-1;

30、return;void IniLinkedQue(LinkedQueTp *s) QUEUE *p1; s-front=(QUEUE *)malloc(sizeof(QUEUE); s-rear=s-front; p1=s-front; p1-num=0; p1-next=Null;2022/8/1267void Arrive(STACK *s1,LinkedQueTp *p,ElemType x) int f, no1, no2; f=Push(s1, x); /* 入栈：车进停车场 */ if (f=False) /* 停车场已满，车停在便道 */ EnLinkedQue(p, x.num

31、); no1=p-front-num; printf(第%d号车停在便道的第%d号车位上n, x.num, no1); else /* 显示车在停车场的位置 */ no1=s1-top+1;no2=x.num; printf(第%d号车停在停车场的第%d号车位上n, no2, no1);2022/8/1268void Arrive(STACK *s1,LinkedQueTp *p,ElemType x) int f; f=Push(s1, x); /* 入栈：车进停车场 */ if (f=False) /* 停车场已满，车停在便道 */ EnLinkedQue(p, x.num); print

32、f(第%d号车停在便道的第%d号车位上n, x.num, p-front-num); else /* 显示车在停车场的位置 */ printf(第%d号车停在停车场的第%d号车位上n, x.num, s1-top+1);2022/8/1269离开处理：已知：车牌号，离开时间处理：从停车场栈中寻找车牌号； 循环条件： 栈不为空； 没有找到(标志为假)； 注意：利用一个临时栈保存每次出栈的结点元素；出车处理： 显示停车费用，将临时栈结点数据返回到停车栈中， 将便道上的一辆车出队，并将该车加入到停车栈中；从便道队列中寻找车牌号； 循环条件：没有到队尾；没有找到(标志为假)；出车处理： 显示车辆离开信

33、息；错误处理： 在停车场栈和便道队列中都没有找到给定车牌号。2022/8/1270void Delive(STACK *s1, STACK *s2, LinkedQueTp *p, ElemType x) int n, f=False; ElemType y; QUEUE *q; while(s1-top-1) & (f!=True) y=Pop(s1); if(y.num!=x.num)n=Push(s2, y); elsef=True;函数调用应注意的问题：1. 函数的功能；2. 函数需要的参数；3. 函数返回结果。2022/8/1271 if (y.num=x.num) printf(第

34、%d号车应收费%d元, y.num, (x.arrtime-y.arrtime)*M); while (s2-top-1) y=Pop(s2);f=Push(s1,y); n=DeLinkedQue(p); if (n!=Null) y.num=n;y.arrtime=x.arrtime; f=Push(s1,y); printf(“第%d号车停在停车场第%d号车位上 n, y.num, s1-top+1); 2022/8/1272 else while(s2-top-1) y=Pop(s2);f=Push(s1,y); q=p-front;f=False; while(f=False & q

35、-next !=Null) if(q-next-num!=x.num)q=q-next; else q-next=q-next-next; p-front-num-; if(q-next=Null)p-rear=q; /* p-front; */ printf(第%d号车离开便道n, x.num); f=True; if(f=False)printf(输入数据错误,停车场和便道上均无第%d号车n,x.num);2022/8/1273int Push(STACK *s, ElemType x) int mytop; if(s-top=N-1) printf(nStack Overflow!n);

36、 return (False); else mytop=s-top;mytop+; s-stackmytop=x;s-top=mytop; return (True);2022/8/1274ElemType Pop(STACK *s) ElemType x; int i; if(s-toptop-; i=s-top+1;x=s-stacki; return x;2022/8/1275void EnLinkedQue(LinkedQueTp *s,int num1) QUEUE *p,*p1; p=(QUEUE *)malloc(sizeof(QUEUE); p-num=num1;p-next=

37、Null; p1=s-rear;p1-next=p; s-rear=p; p1=s-front; p1-num+;2022/8/1276int DeLinkedQue(LinkedQueTp *s) QUEUE *p; int n; if(s-front=s-rear)return(Null); else p=s-front-next; s-front-next=p-next; if(p-next=Null)s-rear=s-front; n=p-num; free(p); s-front-num-; return (n);2022/8/12772. 迷宫问题 问题说明 模拟心理学实验中老鼠对

38、仅有一入口和一个出口的迷宫找出路的过程。 基本要求 设计一程序对任意设定的迷宫，求出一条从入口到出口的路线，或得出没有可行通路的结论。2022/8/12782. 迷宫问题 数据结构描述： typedef struct elem int x, y, dir; ElemType; typedef struct stktag ElemType stackMAXLEN; int top; STACK; typedef struct moved int dx, dy; MOVE;2022/8/1279人机交互部分内容：通过屏幕提示需要输入的数据和程序执行的结果；要求：提示内容清晰易读，键盘操作简单准确。

39、2022/8/1280void main( ) STACK *s; int mazeM2N2; MOVE move8; IniMaze(maze);/* 初始化迷宫数组 */ getch( ); s=(STACK *)malloc(sizeof(STACK); IniStack(s); IniMove(move); path(maze, move, s); draw(maze, s);2022/8/1281void IniMaze(int mazeN2) /*初始化迷宫*/ int i, j, num; for(i=0, j=0; i=M+1; i+)mazeij=1; for(i=0, j=

40、N+1; i=M+1; i+)mazeij=1; for(i=0, j=0; j=N+1; j+)mazeij=1; for(i=M+1, j=0; j=N+1; j+)mazeij=1; for(i=1; i=M; i+) for(j=1; j=N; j+) num=(800*(i+j)+1500) % 327; if (num150)&(i!=M|j!=N) mazeij=1; else mazeij=0; printf(n);2022/8/1282 for(i=0; i=M+1; i+) printf(n); for(j=0; jtop=-1;int Push(STACK *s,Elem

41、Type x) if(s-top=MAXLEN-1)return (False); else s-stack+s-top=x; return (True);2022/8/1285ElemType Pop(STACK *s) ElemType elem; if (s-toptop-; return (s-stacks-top+1);2022/8/1286void path(int maze N2, MOVE move , STACK *s) int i, j, dir, x, y, f; ElemType elem; i=1; j=1; dir=0; maze11=-1; /* 设11为入口处

42、*/ do x=i+movedir.dx; /* 求下一步可行的到达点的坐标 */ y=j+movedir.dy;2022/8/1287 if(mazexy=0) elem.x=i;elem.y=j; elem.dir=dir; f=Push(s, elem); if(f=False)printf(栈长度太短n); i=x;j=y; dir=0;mazexy=-1; else if(dirtop=-1) & (dir=7) | (x=M) & (y=N) & (mazexy=-1); if(s-top=-1)printf(此迷宫无路n); else elem.x=x;elem.y=y; ele

43、m.dir=dir; f=Push(s, elem); printf(n迷宫的通路是:n); i=0; while(itop) printf(%d,%d), s-stacki.x, s-stacki.y); if(i!=s-top)printf(-); if(i+1)%4=0)printf(n); i+; printf(n);2022/8/1289void draw(int maze N2, STACK *s) int i, j; ElemType elem; for(i=1;i=M;i+) for(j=1;jtop-1) elem=Pop(s);i=elem.x; j=elem.y;maze

44、ij=8;2022/8/1290 for(i=0;i=M+1;i+) for(j=0;j=N+1;j+) if(i=0)&(j=0)|(i=M+1)&(j=N+1) printf(%3d,0); else if(mazeij=8)printf( %c,*); elseprintf(%3d,mazeij); printf(n); printf(n);2022/8/1291其它： #define M2 12 #define N2 11 #define MAXLEN M2 #define True 1 #define False 0 #define Null 0 #include #include

45、#include #include int M=M2-2, N=N2-2;2022/8/1292迷宫2-最短路线typedef struct elem int x, y; int dir; ElemType;typedef struct stktag ElemType stackMAXLEN; int top; STACK;typedef struct moved int dx, dy; MOVE;2022/8/1293typedef struct QueEle int x, y; int pre; QueElem;typedef struct QueTag QueElem queueMAXL

46、EN; int front, rear; QUEUE;2022/8/1294void main( ) STACK *s; QUEUE *p; int mazeM2N2, f; MOVE move8; IniMaze(maze); /* 初始化迷宫数组 */ getch(); s=(STACK *)malloc(sizeof(STACK); IniStack(s);/* 初始化栈 */2022/8/1295 p=(QUEUE *)malloc(sizeof(QUEUE); IniQueue(p);/* 初始化队列 */ IniMove(move);/* 初始化位移方向数组*/ f=shortpa

47、th(maze,move,p); /* 寻最短路径 */ if(f=True) printpath(p, s); draw(maze, s); else printf(n此迷宫无通路n); getch( );2022/8/1296void IniMaze(int maze N2) int i, j, num; printf(n); for(i=0,j=0;i=M+1;i+)mazeij=1; for(i=0,j=N+1;i=M+1;i+)mazeij=1; for(i=0,j=0;j=N+1;j+)mazeij=1; for(i=M+1,j=0;j=N+1;j+)mazeij=1; for(i=1;i=M;i+) f