北京工业大学-计算机软件基础考试习题课件.ppt
- 【下载声明】
1. 本站全部试题类文档,若标题没写含答案,则无答案;标题注明含答案的文档,主观题也可能无答案。请谨慎下单,一旦售出,不予退换。
2. 本站全部PPT文档均不含视频和音频,PPT中出现的音频或视频标识(或文字)仅表示流程,实际无音频或视频文件。请谨慎下单,一旦售出,不予退换。
3. 本页资料《北京工业大学-计算机软件基础考试习题课件.ppt》由用户(晟晟文业)主动上传,其收益全归该用户。163文库仅提供信息存储空间,仅对该用户上传内容的表现方式做保护处理,对上传内容本身不做任何修改或编辑。 若此文所含内容侵犯了您的版权或隐私,请立即通知163文库(点击联系客服),我们立即给予删除!
4. 请根据预览情况,自愿下载本文。本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。
5. 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007及以上版本和PDF阅读器,压缩文件请下载最新的WinRAR软件解压。
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 北京工业大学 计算机软件 基础 考试 习题 课件
- 资源描述:
-
1、l1名词解释:数据,数据元素,数据结构。名词解释:数据,数据元素,数据结构。数据:数据:数据就是计算机可以保存和处理的信息。数据就是计算机可以保存和处理的信息。数据元素:数据元素:是组成数据的基本单位。是组成数据的基本单位。数据元素可以是一个数或字符串,也可以由数据元素可以是一个数或字符串,也可以由若干数据项组成。若干数据项组成。数据项是数据的最小单位数据项是数据的最小单位。l数据结构数据结构:简单地说,数据结构就是研究数据及数:简单地说,数据结构就是研究数据及数据元素之间关系的一门学科。据元素之间关系的一门学科。它包括三个方面的内它包括三个方面的内容:容:数据的逻辑结构、数据的存储结构和数据
2、的运数据的逻辑结构、数据的存储结构和数据的运算。算。数据结构数据结构是指数据之间的相互关系,即数据的组是指数据之间的相互关系,即数据的组织形式。可以从集合的观点对数据结构加以形式化描织形式。可以从集合的观点对数据结构加以形式化描述,即是一个二元组:述,即是一个二元组:Data-Structure=(D,R)l其中:其中:D是数据元素的集合,是数据元素的集合,R是是D上关系的集合。上关系的集合。l逻辑结构逻辑结构:数据的逻辑结构是指反映数据元素之间逻:数据的逻辑结构是指反映数据元素之间逻辑关系的数据结构,它与数据的存储无关,是独立于辑关系的数据结构,它与数据的存储无关,是独立于计算机的。计算机的
3、。l存储结构存储结构:数据的存储结构是逻辑结构用计算机语言数据的存储结构是逻辑结构用计算机语言的实现的实现(亦称映像亦称映像),它是依赖于计算机语言的。,它是依赖于计算机语言的。l算法算法:是由若干条指令组成的有限序列。:是由若干条指令组成的有限序列。l2简述算法的五要素。简述算法的五要素。有穷性:每条指令的执行次数必须是有限的。有穷性:每条指令的执行次数必须是有限的。确定性:每条指令的含义必须明确,无二义性。确定性:每条指令的含义必须明确,无二义性。可行性:每条指令都应在有限的时间内完成。可行性:每条指令都应在有限的时间内完成。输入性:具有零个或多个输入量,即算法开始前对输入性:具有零个或多
4、个输入量,即算法开始前对算法给出的初始量。算法给出的初始量。输出性:至少产生一个输出。输出性:至少产生一个输出。l3评价一个评价一个“正确的正确的”算法主要有哪两个指算法主要有哪两个指标?标?l(1)时间复杂度时间复杂度:依据算法编制成程序后,在计算机:依据算法编制成程序后,在计算机上运行时所消耗的时间。上运行时所消耗的时间。l(2)空间复杂度空间复杂度:依据算法编制成程序后,在计算机:依据算法编制成程序后,在计算机执行过程中所需要的最大存储空间。执行过程中所需要的最大存储空间。l4描述以下三个概念的描述以下三个概念的区别区别:头指针、头结:头指针、头结点、首元结点点、首元结点(第一个元素结点
5、第一个元素结点)。l头指针头指针就是指向链表中第一个结点的指针。单链表是就是指向链表中第一个结点的指针。单链表是由头指针唯一确定的。因此可以用头指针的名字来命由头指针唯一确定的。因此可以用头指针的名字来命名单链表。名单链表。l头结点头结点是在单链表第一个元素所在结点之前附设的一是在单链表第一个元素所在结点之前附设的一个结点。头结点的指针域存储第一个元素所在结点的个结点。头结点的指针域存储第一个元素所在结点的存储位置;数据域可以不存储任何信息,也可以存储存储位置;数据域可以不存储任何信息,也可以存储如线性表的长度等附加信息。设置头结点后,可使空如线性表的长度等附加信息。设置头结点后,可使空表和非
6、空表的逻辑状态及运算统一起来。表和非空表的逻辑状态及运算统一起来。l首元结点首元结点就是第一个数据元素所在的结点。就是第一个数据元素所在的结点。l5有一线性表存储在一个带头结点的循环单有一线性表存储在一个带头结点的循环单链表链表L中,写出计算线性表元素个数的算法。中,写出计算线性表元素个数的算法。lint length(NODE*L)l NODE *p;l int counter=0;l p=L-next;l while(p!=L)l p=p-next;l counter+;l return counter;l 6假设有一个假设有一个循环单链表循环单链表的长度大于的长度大于1,且表,且表中既无
7、头结点也无头指针。已知中既无头结点也无头指针。已知S为指向链表为指向链表中某结点的指针,试编写算法,在链表中删除中某结点的指针,试编写算法,在链表中删除结点结点S的前趋结点。的前趋结点。l提示:提示:l(1)定义一个指针变量定义一个指针变量p指向结点指向结点*s的直接后继;的直接后继;l(2)定义一个指针变量定义一个指针变量q指向结点指向结点*s;l(3)当当p-next不等于不等于s时,令时,令q=p,p=p-next;重复上述处理直至重复上述处理直至p-next=s;l(4)令令q-next=s;free(p)。lvoid delprior(NODE*s)l NODE*p,*q;l p=s
8、-next;q=s;l while(p-next!=s)l q=p;p=p-next;l q-next=s;l free(p);ll7已知指针已知指针ha和和hb分别指向两个单链表的头分别指向两个单链表的头结点,且头结点的数据域中存放链表的长度,结点,且头结点的数据域中存放链表的长度,试写一算法将这两个链表连接在一起试写一算法将这两个链表连接在一起(即令其中即令其中一个表的首元结点连在另一个表的最后一个结一个表的首元结点连在另一个表的最后一个结点之后点之后),hc指向连接后的链表的头结点,并要指向连接后的链表的头结点,并要求算法以尽可能短的时间完成连接运算。请分求算法以尽可能短的时间完成连接运
9、算。请分析你的算法的时间复杂度。析你的算法的时间复杂度。l8设计一个将线性链表进行逆置的算法。设计一个将线性链表进行逆置的算法。l对于单链表,借助中间变量实现数据元素指针域中地对于单链表,借助中间变量实现数据元素指针域中地址值的变化。参见址值的变化。参见Shiyan12.c的的 reverse()函数。函数。l9设有多项式设有多项式l A(x)=7+3x+9x8+3x15l B(x)=5x+6x7-9x8l(1)用单链表给出用单链表给出A(x)的存储表示;的存储表示;l(2)用单链表给出用单链表给出B(x)的存储表示;的存储表示;l数据存储结构:数据存储结构:l typedef struct
10、polyterm l int coef;l int exp;l struct polyterm*next;l TERM;l10设有编号为1,2,3,4的四辆列车,顺序进入一个栈式结构的车站,具体写出这四辆列车开出车站的所有可能的顺序。l1,2,3,4 1,2,4,3 1,3,2,4l1,3,4,2 1,4,3,2 2,1,3,4l2,1,4,3 2,3,1,4 2,3,4,1l2,4,3,1 3,2,1,4 3,2,4,1l3,4,2,1 4,3,2,1l11假设以带头结点的循环单链表表示队列,假设以带头结点的循环单链表表示队列,并且只设一个指针指向队尾元素结点并且只设一个指针指向队尾元素结点
11、(不设头指不设头指针针),试编写相应的入列和出列算法。,试编写相应的入列和出列算法。l12假设以数组假设以数组sequm存放循环队列的元素存放循环队列的元素,同时设变量,同时设变量rear和和quelen分别指示队尾元素分别指示队尾元素的位置和内含元素的个数。试给出此循环队列的位置和内含元素的个数。试给出此循环队列的队满条件,并写出相应的入列和出列算法。的队满条件,并写出相应的入列和出列算法。l队满条件:队满条件:quelen=mlstep1.判定循环队列是否已满,若满,则给出队列溢判定循环队列是否已满,若满,则给出队列溢出出错信息;出出错信息;lstep2.队尾指针后移,将入队元素放入队尾指
12、针所指队尾指针后移,将入队元素放入队尾指针所指的存储位置。的存储位置。lstep3.队列元素个数增队列元素个数增1。l#define MAXSIZE ml /*m为队列中数据元素个数的最大可能值为队列中数据元素个数的最大可能值*/l int sequMAXSIZE;l /*假设数据元素的类型为整型假设数据元素的类型为整型*/l int quelen=0,rear=MAXSIZE-1;lvoid addqueue(int x)lif(quelen=MAXSIZE)lprintf(循环队列已满,上溢循环队列已满,上溢!n);lexit(1);llelse lrear=(rear+1)%MAXSIZ
13、E;lsequ rear=x;lquelen+;lllstep1.判定循环队列是否为空,若空,则给出队列溢判定循环队列是否为空,若空,则给出队列溢出出(下溢下溢)信息;信息;lstep2.计算队头指针值,并读取队头元素;计算队头指针值,并读取队头元素;lstep3.队列元素个数减队列元素个数减1。l#define MAXSIZE mlint sequMAXSIZE;lint quelen=0,rear=MAXSIZE-1;lint delqueue()lint front,x;lif(quelen=0)l printf(循环队列已空,下溢!循环队列已空,下溢!n);l x=-1;lelse l
14、 front=(rear-quelen+MAXSIZE+1)%MAXSIZE;l x=sequfront;l quelen-;llreturn x;ll13试将下列稀疏矩阵试将下列稀疏矩阵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-13l16二维数组二维数组A的元素是的元素是6个字符组成的串,行个字符组成的串,行下标下标i的范围从的范围从0到到8,列下标,列下标j的范围从的范围从1到到10。从供选择的答案中选出应填入下列关于数组存从供
15、选择的答案中选出应填入下列关于数组存储叙述中储叙述中()内的正确答案。内的正确答案。l (1)存放存放A至少需要至少需要()个字节。个字节。l (2)A的第的第8列和第列和第5行共占行共占()个字节。个字节。l (3)若若A按行存放,元素按行存放,元素A8,5 的起始地址与当的起始地址与当A按按列存放时的元素列存放时的元素()的起始地址一致。的起始地址一致。l 供选择答案供选择答案l(1)a.90;b.180;c.240;d.270;e.540;l(2)a.108;b.114;c.54;d.60;e.150;l(3)a.A8,5;b.A3,10;c.A5,8;d.A0,9。l(1)9*10*6
16、=540l(2)(9+9)*6=108l(3)8*10+5=85;85/9=9 余余 4l 答案:答案:A3,10;试验一:线性表的设计与实现试验一:线性表的设计与实现 l1.线性表基本操作的实现线性表基本操作的实现:数据的存储结构数据的存储结构l#define MaxSize 1024 typedef int DataType;typedef struct node DataType dataMaxSize;int last;SequenList;人人机交互部分机交互部分l内容:通过屏幕提示功能选择菜单;内容:通过屏幕提示功能选择菜单;通过键盘输入实现功能的选择;通过键盘输入实现功能的选择;
17、l要求:提示内容清晰易读,要求:提示内容清晰易读,键盘操作简单准确;键盘操作简单准确;l实现:循环扫描键盘,等待用户输入;实现:循环扫描键盘,等待用户输入;根据输入内容确定要执行的分支程序。根据输入内容确定要执行的分支程序。lint main()l SequenList MyList,*L;l char cmd;l int i,t,x;l L=&MyList;L-last=-1;l do l do l clrscr();l printf(nt c,C.Create Listn);l printf(nt i,I.Insert);l printf(nt d,D.Delete);l printf(n
18、t q,Q.QuitntYour choice:);l cmd=getchar();l 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)&(toupper(cmd)!=I)&(toupper(cmd)!=C);l switch(cmd)l case c:l case C:CreateList(L);break;l case i:l case I:?Insert(L,x,i);PrintOut(
19、L);l getch();break;l case d:l case D:?l Delete(L,i);PrintOut(L);l getch();break;l default:break;l l while(cmd!=q)&(cmd!=Q);lprintf(nInput the data to be inserted:);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 b
20、e deletedn);printf(n(1-%d):n,(L-last+1);scanf(%d,&i);while(toupper(cmd)!=Q);运算处理运算处理l内容:建表、插入、删除、输出;内容:建表、插入、删除、输出;l实现:利用指针变量作为函数参数,传递实现:利用指针变量作为函数参数,传递 线性表地址;线性表地址;void CreateList(SequenList*L)int n,i,mydata;printf(nPlease input total number of data itemn);scanf(%d,&n);for(i=0;idatai=mydata;L-last=
21、n-1;printf(nPress any key to continuen);getch();lint Insert(SequenList*L,DataType x,int i)l int j;l if(L-last=(MaxSize-1)l printf(nOverflow!);l return Null;l else if(i(L-last+2)l printf(range error);l return Null;l else l for(j=L-last;j=i-1;j-)l L-dataj+1=L-dataj;l L-datai-1=x;l L-last=L-last+1;l re
22、turn(1);lint 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 i;for(i=0;ilast;i+)printf(data%d=,i+1);printf(%dt,L-datai);if(i!=0)&(i%4)=0)printf(n);l完善程序:完善程序:l#include l#include l#de
23、fine Null 0l线性表初值设置:线性表初值设置:l L-last=-1;l2.一元多项式的相加、相乘的程序设计一元多项式的相加、相乘的程序设计l数据存储结构:数据存储结构:l typedef struct polyterm l int coef;l int exp;l struct polyterm*next;l TERM;人人机交互部分机交互部分l内容:通过屏幕提示需要输入的数据和程内容:通过屏幕提示需要输入的数据和程序执行的结果;序执行的结果;l要求:提示内容清晰易读,要求:提示内容清晰易读,键盘操作简单准确。键盘操作简单准确。void main()TERM*ha,*hb,*hc,
24、*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 polynomial is:);polyout(hc);h=polymulti(ha,hb);printf(n
25、the multiplication of the two polynomial is:);polyout(h);return;运算处理运算处理l内容:建表、相加、相乘、输出;内容:建表、相加、相乘、输出;l实现:使用指针变量作为函数返回的参数,实现:使用指针变量作为函数返回的参数,传递线性表地址;传递线性表地址;l条件:链表无头结点;条件:链表无头结点;多项式系数和指数均为多项式系数和指数均为int型数据;型数据;每个多项式数据输入的方式为:每个多项式数据输入的方式为:系数,指数系数,指数 数据按指数递减的顺序依次输入;数据按指数递减的顺序依次输入;结束多项式数据输入的条件是:结束多项式数据
展开阅读全文