搜索
第一章信息与计算机1.1什么是信息？信息与数据的区别和联系在何处？信息定义之一：信息是现实世界中存在的客观实体、现象、关系进行描述的数据。信息定义之二：信息是经过加工后并对实体的行为产生影响的数据。与数据的区别和联系：数据定义：数据是现实世界客观存在的实体或事物的属性值，即指人们听到的事实和看到的景象。我们把这些数据收集起来，经过处理后，即得到人们需要的信息。信息和数据的关系可以归结为：1.信息是有一定含义的数据。2.信息是经过加工（处理）后的数据。3.信息是对决策有价值的数据。1.2信息有哪些基本属性？信息的基本属性有：1.事实性。2.等级性。3.可压缩性。4.可扩散性。5.可传输性。6.共享性。7.增值性和再生性。8.转换性。1.3计算机的主要特点是什么？计算机最主要的特点是：1.高速自动的操作功能。2.具有记忆的能力。3.可以进行各种逻辑判断。4.精确高速的计算能力。1.5完整的计算机系统应该包括哪几部分？目前最完整的计算机系统学说认为由五部分组成：1.人员2.数据3.设备4.程序5.规程1.6什么是计算机硬件？什么是计算机软件？硬件：泛指实际存在的物理设备，包括计算机本身及其外围设备。微型计算机的硬件系统：主机、外存储器、输入设备、输出设备、微机的系统总线。软件：是指计算机程序、方法、规则的文档以及在计算机上运行它时所必须的数据。计算机软件一般分为系统软件和应用软件。1.8软件技术发展的几个阶段各有什么特点？它与硬件的关系如何？第一阶段：高级语言阶段特点：这一时期，编译技术代表了整个软件技术，软件工作者追求的主要目的是设计和实现在控制结构和数据结构方面表现能力强的高级语言。但在这一时期内，编译系统主要是靠手工编制，自动化程度很低。硬件关系：此时期计算机的硬件要求仅能用机器指令来编制可运行的程序。第二阶段：结构程序设计阶段特点：在程序的正确性方面，提出了结构化程序设计思想使程序的可靠性提高了。程序设计方法论方面，提出由顶向下法和自底向上法。使程序模块化，使问题的复杂性和人的思维统一起来了。出现了软件生产管理。硬件关系：磁盘问世，操作系统发展，非数值计算应用发展，通信设备完善，网络发展，集成电路发展等使软件复杂性增加产生软件危机，在此背景下发展了软件技术。第三阶段：自动程序设计阶段特点：向集成化、一体化发展。出现了软件开发环境。程序设计基本方法进一步改进。硬件关系：集成电路迅速发展以及高分辨率终端的出现，为个人计算机发展提供了条件，再加上人工智能、专家系统研究的发展，使程序设计进入成熟期。1.9什么是多媒体计算机？多媒体计算机包含那几项？什么是多媒体计算机？1.“媒体”的概念分为两部分，其一是信息存储的实体，其二是表现信息形式的载体；2.多媒体计算机是以计算机为核心，可以综合处理数值计算、文本文件、图形图像、声音视频等多种信息的计算机系统。3.多媒体是20世纪90年代计算机发展的新领域，它是计算机技术与图形图像、动画、声音和视频等领域顶尖技术结合的产物，它将人机交互的信息从单纯的视觉（文字、图形）扩大到两个以上的媒体信息B：多媒体的基本要素：文本，图形，图像，动画，音频，视频，可以看出，它是电脑，电视机，游戏机，录放机，传真机和电话机的综合体第二章常用数据结构及其运算2.1什么是数据结构？它对算法有什么影响？数据结构是指同一数据对象中各数据元素间存在的关系。数据结构对算法的影响：算法的实现必须借助程序设计语言中提供的数据类型及其运算。一个算法的效率往往与数据的表达形式有关，因此数据结构的选择对数据处理的效率起着至关重要的作用。它是算法和程序设计的基本部分，它对程序的质量影响很大。2.2何谓算法？它与程序有何区别？广义地说，为解决一个问题而采取的方法和步骤，就称为“算法”。计算机算法是通过计算机能执行的算法语言来表达的。和程序的区别：一个程序包括两个方面的内容：（1）对数据的描述，即数据结构。（2）对操作的描述，即算法。所以算法是程序的一个要素。2.3何谓频度，时间复杂度，空间复杂度？说明其含义。频度：在某个算法中某个语句被重复执行的次数就是此语句的频度。时间复杂度：是用来估算一个算法的执行时间的量，以算法中频度最大的语句来度量。空间复杂度：指在算法中所需的辅助空间的单元，而不包括问题的原始数据占用的空间。2.4试编写一个求多项式Pn=anxn+an-1xn-1+……+a1x+a0的值Pn(x0)的算法，要求用乘法次数最少，并说明算法中主要语句的执行次数及整个算法的时间复杂度。A=(a0,a1……an)mul＝1//sum=a0fori=1tonmul＝mul*x//xsum=A[i]*mul+sum//求和end(i)进行了n次时间复杂度为：2n2.5计算下列各片段程序中X←X+1执行次数(1)fori=1tonforj=1toifork=1tojx←x+1end(k)end(j)end(i)执行次数：n*n*n(2)i←1whileindox←x+1i←i+1end(while)执行次数：n-1(3)fori=1tonj←1fork=j+1tonx←x+1end(k)end(i)执行次数：n*（n-1）2.6数据的存储结构主要有哪两种?它们之间的本质区别是什么？数据的存储结构：向量和链表。本质区别：向量是连续存放的，其存储空间是静态分配的，以存放顺序来表达元素的前后件的关系。链式存储结果不需要一组连续的存储单元，其数据元素可以分散存放在存储空间中，其元素关系由指针来指向。2.8已知线性表L(a1,a2,…,an)元素按递增有序排列。用向量作为存储结构，试编写算法：删除表中值在c与d之间(c=d)的元素找到第1个大于等于c的元素，序号为s找到第一个大于d的元素，序号为tL[s]←L[t]L[s+1]←L[t+1]…L[s+m]←L[t+m]//s+m=t-1m=t–s-1L[s+i]←L[t+i]//i=0tot-s-1i=1;//i从1循环到ns=-1;//第1个大于等于c的元素序号t=-1;//第1个大于d的元素序号fori=1tonstep-1ifs==-1andL[i]=c//找到第1个大于等于c的元素s=iift==-1andL[i]d//找到第1个大于d的元素t=i;end(i)ifs!=-1andt!=-1i=swhileitandi+t–s=nL[i]=L[i+t–s]i++end(while)elsereturn(错误没有找到元素在c和d之间)end(if)forj=cton-d+cL[j]--L[j+d-c]//把j+d-c项给jEnd(j)N--n-d+c//所有项数减少Returna1a2a3a4a5a6a7a8a9a10a11a12a130a14a15大于等于c序号4大于d序号112.9线性表A，B中的元素为字符串类型，用向量结构存储，试编写算法，判断B是否为A的子序列（例如A=ENGLISH，B=LIS，则B为A的子序列）A[m]B[n]A：B：i=1检查A中第1个元素开始的字符串是否与B匹配i=2检查A中第2个元素开始的字符串是否与B匹配……i=m–n+1检查A中第(m-n+1)个元素开始的字符串是否与B匹配A[m]B[n]if(mn)thenreturnerrorfor(i=1;i=m-n+1;i++)for(j=1;j=n;j++)if(A[i+j-1]!=B[j])break;end(j)ifjnthenreturn(A字符串中第i个字符开始的子串与B匹配)end(i)renturn(找不到匹配的子串)设A，B两个线性表的元素个数为m，nIf(m=n)then{return}Fori=0ton-1a=A[i]forj=0tom-1if(a=B[j])then{b++}end(j)end(i)if(b=m)then{B为A的子集}returna1a2a3a4a5a6a7a8a9a10a11a12a130a14a15b1b2b3b4b5b62.11写一个将向量L（a1，a2，an）倒置的算法。对L(a1，a2,......,an)如果是奇数个元素，则1,15交换1,n交换2，14交换2,n-1交换3，13交换3，n-2交换4，12交换4，n-3交换5，11交换5，n-4交换6，10交换6，n-5交换7，9交换7，n-6交换8，8交换8，n-7交换9，7交换9，n-8交换？停止！！！如果是偶数个元素，则1，14交换1,n交换2，13交换2,n-1交换3，12交换3，n-2交换4，11交换4，n-3交换5，10交换5，n-4交换6，9交换6，n-5交换7，8交换7，n-6交换8，7交换？8，n-7交换？停止！！！！小结：n个元素倒置的算法是，i=1while(in-i+1)a[i]与a[n-i+1]交换i++end(while)a1a2a3a4a5a6a7a8a9a10a11a12a130a14a15a1a2a3a4a5a6a7a8a9a10a11a12a130a14a152.12试编写算法求已知单链表长度，并考虑表空的情况。p=headi=0While(p!=nil)//表不为空P--next(p)//移动到下一个元素i++End(while)Returni//返回数据的个数2.13试编写算法删除单链表中第k个结点。GETNODE(q)GETNODE(p)q-headFori=1tok-1q-next(q)End(i)P-next(q);next(q)-next(p)Ret(p)Return^head2.14已知一循环链表中数值已按递增有序排列现要插入一个新结点，并使插入一个新节点，并使插入后链表仍为有序序列GETNODE(p)Data(p)=aWhile(data(p)data(n))n-next(n)End(while)q-nnext(p)--next(q)-preturn2.18设在长度大于1的循环链表中，即无头结点，也无头指正，p为指向链表中每个节点的指针，试编写算法删除该节点的前趋结点。q-Next(p)//找到该节点的前趋结点p-next(q);next(q)-next(p)RET(p)Return2.20试用单链表表示两个多项式；A=4x12+5x8+6x3+4，B=3x12+6x7+2x4+5(1)设计此两个多项式的数据结构。(2)写出两个多项式相加的算法。(3)分析算法的时间、空间复杂度。ADD-POLY(ha,hb)1.p←next(ha);q←next(hb)2.pre←ha;hc←ha//pre指向p的前趋，为c(x)头指针//3.while(pnil)AND(qnil)do4.case5.EXP(p)EXP(q):6.{pre←p;p←next(p)}7.EXP(p)=EXP(q):8.{x←COEF(p)+COEF(q);9.if(x0)then{COEF(p)←x;pre←p}10.else{next(pre)←next(p);RET(p)}11.p←next(pre);u←q;q←next(q);RET(u)}12.EXP(p)EXP(q):13.{u←next(q);next(q)←p;next(pre)←q;pre←q;q←u}14.end(case)15.end(while)16.if(qnil)thennext(pre)←q17.RET(hb)//释放多项式B(x)的头结点//18.return2.22CQ[0:10]为一循环队列，初态front=rear=1，画出下列操作后队的头，尾指示器状态：(1)d,e,b,g,h入队；rear=6front=1(2)d，e出队rear=6front=3(3)I,j,k,l,m入队rear=0front=3(4)b出队rear=0front=4(5)n,o,p,q,r入队rear=5front=42.22CQ[0：10]为一循环队列，初态front=rear=1，画出下列操作后队的头、尾指示器状态：(1)d,e,b,g,h入