计算机软件技术基础课后答案

计算机软件技术基础课后答案计算机软件技术基础课后答案【篇一：《计算机软件技术基础》复习题(含答案)】txt>1.线性表的链式存储结构与顺序存储结构相比优点是a.所有的操作算法实现简单c.便于插入和删除b.便于随机存取d.便于利用零散的存储器空间2.线性表是具有n个的有限序列。a.表元素d.数据项b.字符c.数据元素e.信息项3.若长度为n的线性表采用顺序存储结构，在其第i个位置插入一个新元素的算法的时间复杂度为c。（1≤i≤n+1）a.o(0)b.o(1)2c.o(n)d.o(n)4.设a是一个线性表(a1,a2,?,an)，采用顺序存储结构，则在等概率的前提下，平均每插入一个元素需要移动的元素个数为b，平均每删除一个元素需要移动的元素个数为a；若元素插在ai与ai+1之间(0≤i≤n-1)的概率为元素所要移动的元素个数为c；2(n?i)，则平均每插入一个n(n?1)n?122n?1c.3a.n23n?1d.4b.5.下列函数中，按它们在n??时的无穷大阶数，最大的是d。a.lognb.nlognn/2c.2d.n!6.a.s-next=p+1;p-next=s;b.(*p).next=s;(*s).next=(*p).next;c.s-next=p-next;p-next=s-next;d.s-next=p-next;p-next=s;7.将两个各有n个元素的有序表归并为一个有序表时，其最少的比较次数是a。a.nc.n-1b.2n-1d.2n13.用单链表表示的链式队列的队头在链表的a位置。a.链头b.链尾c.链中14.若用单链表表示队列，则应该选用。a.带尾指针的非循环链表b.带尾指针的循环链表c.带头指针的非循环链表d.带头指针的循环链表15.在解决计算机主机与打印机之间速度不匹配问题时，通常设置一个打印数据缓冲区，主机将要输出的数据依次写入该缓冲区，而打印机则从该缓冲区中取出数据打印，先放入打印缓冲区的数据先被打印。该缓冲区应该是一个b结构。a.堆栈b.队列c.数组d.线性表待排序的序列中的相邻元素两两比较，凡是逆序则进行交换，这是(3)排序。如果整个排序过程都在内存中进行，称为(4)排序。排序算法的复杂性与排序算法的(5)有关。供选答案：(1):(2):(3):(4):(5):a.选择b.插入c.比较d.归并a.选择b.插入c.比较d.归并a.冒泡b.交换c.比较d.散列a.外部b.内部c.外存d.内存a.运算量大小与占用存储多少b.运算量大小与处理的数据量大小c.并行处理能力和占用存储多少d.占用存储多少和处理的数据量大小答案：baaba47.操作系统是对计算机资源进行的(1)系统软件，是(2)的接口。在处理机管理中，进程是一个重要的概念，它由程序块、(3)和数据块三部分组成，它有3种基本状态，不可能发生的状态转换是(4)。虚拟存储器的作用是允许程序直接访问比内存更大的地址空间，它通常使用(5)作为它的一个主要组成部分。供选答案：(1):a.输入和输出b.键盘操作c.管理和控制d.汇编和执行(2):a.软件和硬件b.主机和外设c.高级语言和机器语言d.用户和计算机(3):a.进程控制块b.作业控制块c.文件控制块d.设备控制块(4):a.运行态转换为就绪态b.就绪态转换为运行态c.运行态转换为等待态d.等待态转换为运行态(5):a.软盘b.硬盘c.cdromd.寄存器答案：cdadb48.a是信息的载体，它能够被计算机识别、存储和加工处理。a.数据b.数据元素c.结点d.数据项49.下列程序段的时间复杂度为c。for(i=1;in;i++){y=y+1;for(j=0;j=(2*n);j++)x++;}供选答案：2a.o(n-1)b.o(2n)c.o(n)d.o(2n+1)50.下面程序段的时间复杂度为d。i=1;while(i=n)i=i*2;供选答案：a.o(1)b.o(n)c.o(n2)d.o(log2n)51.下面程序段的时间复杂度为b。a=0;b=1;for(i=2;i=n;i++){s=a+b;b=a;a=s;}供选答案：2a.o(1)b.o(n)c.o(log2n)d.o(n)52.数据结构是一门研究非数值计算的程序设计问题中，计算机的a以及它们之间的关系和运算等的学科。a.操作对象b.计算方法c.逻辑存储d.数据映象53.在数据结构中，从逻辑上可以把数据结构分成c。a.动态结构和静态结构b.紧凑结构和非紧凑结构c.线性结构和非线性结构d.内部结构和外部结构54.算法分析的目的是c。a.找出数据结构的合理性b.研究算法中输入和输出的关系c.分析算法的效率以求改进d.分析算法的易懂性和文档性55.算法分析的两个主要方面是d。a.间复杂性和时间复杂性b.正确性和简明性c.可读性和文档性d.数据复杂性和程序复杂性56.一个线性顺序表第一个元素的存储地址是100，每个元素的长度为2，则第5个元素的地址为b。a.110b.108c.100d.12057.若已知一个栈的入栈序列是1,2,3,?,n，其输出序列为p1,p2,p3,?,pn，若p1=n，则pi为c。a.ib.n-ic.n-i+1d.不确定58.对于一个栈，给出输入项a,b,c。如果输入项序列由a,b,c所组成，则不可能产生的输出序列是a。a.cabb.cbac.abcd.acb59.设有如下的单链表的按序号查找的算法，其时间复杂度为b。linknode*getnode(linklisthead,inti){intj;listnode*p;p=head;j=0;while(p-nextji){p=p-next;j++;}if(i==j)return(p);else【篇二：《计算机软件技术基础(第三版)》的课后答案】是信息？信息与数据的区别和联系在何处？信息定义之一：信息是现实世界中存在的客观实体、现象、关系进行描述的数据。信息定义之二：信息是经过加工后并对实体的行为产生影响的数据。与数据的区别和联系：数据定义：数据是现实世界客观存在的实体或事物的属性值，即指人们听到的事实和看到的景象。我们把这些数据收集起来，经过处理后，即得到人们需要的信息。信息和数据的关系可以归结为：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软件技术发展的几个阶段各有什么特点？它与硬件的关系如何？第一阶段：高级语言阶段特点：这一时期，编译技术代表了整个软件技术，软件工作者追求的主要目的是设计和实现在控制结构和数据结构方面表现能力强的高级语言。但在这一时期内，编译系统主要是靠手工编制，自动化程度很低。硬件关系：此时期计算机的硬件要求仅能用机器指令来编制可运行的程序。第二阶段：结构程序设计阶段特点：在程序的正确性方面，提出了结构化程序设计思想使程序的可靠性提高了。程序设计方法论方面，提出由顶向下法和自底向上法。使程序模块化，使问题的复杂性和人的思维统一起来了。出现了软件生产管理。硬件关系：磁盘问世，操作系统发展，非数值计算应用发展，通信设备完善，网络发展，集成电路发展等使软件复杂性增加产生软件危机，在此背景下发展了软件技术。第三阶段：自动程序设计阶段特点：向集成化、一体化发展。出现了软件开发环境。程序设计基本方法进一步改进。硬件关系：集成电路迅速发展以及高分辨率终端的出现，为个人计算机发展提供了条件，再加上人工智能、专家系统研究的发展，使程序设计进入成熟期。第二章2.1什么是数据结构？它对算法有什么影响？数据结构是指同一数据对象中各数据元素间存在的关系。对算法是影响：算法的实现必须借助程序设计语言中提供的数据类型及其运算。一个算法的效率往往与数据的表达形式有关，因此数据结构的选择对数据处理的效率起着至关重要的作用。它是算法和程序设计的基本部分，它对程序的质量影响很大。2.2何谓算法？它与程序有何区别？广义地说，为解决一个问题而采取的方法和步骤，就称为“算法”。计算机算法是通过计算机能执行的算法语言来表达的。和程序的区别：一个程序包括两个方面的内容：（1）、对数据的描述，即数据结构。（2）、对操作的描述，即算法。所以算法是程序的一个要素。2.3何谓频度，时间复杂度，空间复杂度？说明其含义。频度：在某个算法中某个语句被重复执行的次数就是此语句的频度。时间复杂度：是用来估算一个算法的执行时间的量，以算法中频度最大的语句来度量。空间复杂度：指在算法中所需的辅助空间的单元，而不包括问题的原始数据占用的空间。2.6数据的存储结构主要有哪两种?它们之间的本质区别是什么？数据的存储结构：向量和链表。本质区别：向量是连续存放的，其存储空间是静态分配的，以存放顺序来表达元素的前后件的关系。链式存储结果不需要一组连续的存储单元，其数据元素可以分散存放在存储空间中，其元素关系由指针来指向。2.16试比较顺序表和链表的优缺点。1.线性表的长度是否固定方面：由于向量的存储空间是静态分配的，链表的存储空间是动态分配的，因此若表长不固定时采用线性链表较好。2.线性表的主要操作是什么：由于向量是连续存放的，所以适用于查找操作，不适用插入、删除操作。由于线性链表只能顺序存取，所以适用于插入、删除操作，不适用于查找操作。3.采用的算法语言：线性链表要求所使用的语言工具提供指针类型变量。2.17试比较单向链表与双向链表的优缺点。1.单向链表只能单方向地寻找表中的结点，双向链表具有对称性，从表中某一给定的结点可随意向前或向后查找。2.在作插入、删除运算时，双向链表需同时修改两个方向上的指针，单向链表则简便些。2.23试画出表达式a*(b-d)/d+c**(e*f)执行过程中ns,os栈的变化情况。b-d=t1d/t1=t2t2*a=t3e*f=t4t4**c=t52.26用三元组和带行辅助向量形式表示下列稀疏矩阵：800?1300026?1500220?15?0????0113000??1500600050??（1）：???0?30403000???000?600??（2）：200040??000000??000????000000??9100000??00?12?020000000????0028000?????000400000??700000000????12002060030??（1）：三元组带行辅助向量2.27试说明树与二叉树有何不同？为何要将一般树转换为二叉树？树与二叉树区别：树是由n个（n=0）结点组成的有限集合t，其中有且仅有一个结点称为根结点，在此类元素结点之间存在明显的分支和层次关系。二叉树是一种特殊的树结构，每一个结点最多只有两个孩子，即最多只有两个分支。为何要转换：一般树，树中结点次序没有要求，分支庞杂。而二叉树，元素之间存在严谨的前后代关系，在对数据元素进行删除、查找、插入等运算时更加有效率。2.28将下列（题图2.3）的一般树化为二叉树。题图2.3转换后：2.30设一棵二叉树其中序和后序遍历为中序：bdceafhg后序：decbhgfa画出这棵二叉树的逻辑结构，并写出先序遍历结果。先序遍历：abcdefgh其逻辑结构如下：【篇三：计算机软件技术基础习题一解答】正整数,分析下列各程序段中加下划线的语句的执行次数。(1)for(inti=1;i=n;i++)for(intj=1;j=n;j++){c[i][j]=0.0;for(intk=1;k=n;k++)c[i][j]=c[i][j]+a[i][k]*b[k][j];}(2)x=0;y=0;for(inti=1;i=n;i++)for(intj=1;j=i;j++)for(intk=1;k=j;k++)x=x+y;(3)inti=1,j=1;while(i=nj=n){i=i+1;j=j+i;}(4)*inti=1;do{for(intj=1;j=n;j++)i=i+j;}while(i100+n);【解答】nnn3(1)???1?ni?1j?1k?1?(2)nijnin???1???i?1j?1k?1i?1j?1j??i?1?i(i?1)?1???2??2?2n?ii?12?1ni??2i?11n(n?1)(2n?1)261n(n?1)2?n(n?1)(n?2)6(3)i=1时，i=2，j=j+i=1+2=2+1，i=2时，i=3，j=j+i=(2+1)+3=3+1+2，i=3时，i=4，j=j+i=(3+1+2)+4=4+1+2+3，i=4时，i=5，j=j+i=(4+1+2+3)+5=5+1+2+3+4，??i=k时，i=k+1，j=j+i=(k+1)+(1+2+3+4+?+k)，?j??k?1????k?1??k?i?ni?1k?k?1?2?k?3k?322?n解出满足上述不等式的k值，即为语句i=i+1的程序步数。(4)for语句每执行一次，语句i=i+j将执行n次，而i的值会增加因此，当for语句执行k次后，i的值将变为1?kn(n?1)2n(n?1)2故最终for语句的执行次数k为满足1?kn(n?1)2?100?n的最小整数k，语句i=i+j的程序步数为n*k。4.试编写一个函数计算n!*2的值，结果存放于数组a[arraysize]的第n个数组元素中，0?n?arraysize。若设计算机中允许的整数的最大值为maxint，则当narraysize或者对于某一个k(0?k?n)，使得k!*2maxint时，应按出错处理。可有如下三种不同的出错处理方式：(1)用printf显示错误信息及exit(1)语句来终止执行并报告错误；kn(3)在函数的参数表设置一个引用型的整型变量来区别是正常返回还是某种错误返回。试讨论这三种方法各自的优缺点，并以你认为是最好的方式实现它。【解答】#includestdio.hconstintarraysize=100;constintmaxint=0x7fffffff;intcalc(intt[],intn){inti,value=1;t[0]=1;if(n!=0){}voidmain(){inta[arraysize];inti;for(i=0;iarraysize;i++)if(!calc(a,i)){printf(failedat%d.\n,i);break;intedge=maxint/n/2;for(i=1;in;i++){value*=i*2;t[i]=value;if(valueedge)return0;}value*=n*2;}t[n]=value;printf(a[%d]=%d\n”,n,t[n]);return1;}}/*---------顺序表结构的定义.为简化起见，表元素我们使用整型数据----------------------数据元素从data[0]处开始存储---------------------------------*/typedefstruct/*注意typedef的使用*/{intdata[maxsize];/*数据域*/intlength;/*表长*/}listtype;5.设有一个线性表(a0,a1,?,an-2,an-1)存放在一个一维数组a[arraysize]中的前n个数组元素位置。请编写一个函数将这个线性表原地逆置，即将数组的前n个原址内容置换为(an-1,an-2,?,a1,a0)。最后分析此算法的时间复杂度及空间复杂度。【解答】voidinverse(listtype*a){inttmp;intn=a-length;for(inti=0;i=(n-1)/2;i++){tmp=a-data[i];a-data[i]=a-data[n-i-1];a-data[n-i-1]=tmp;}}时间复杂度：需进行n/2次循环，因此时间复杂度为o(n)；空间复杂度：使用一个整形辅助存储单元tmp，因此空间复杂度为o(1)。6.顺序表的插入和删除要求仍然保持各个元素原来的次序。设在等概率情形下,对有127个元素的顺序表进行插入,平均需要移动多少个元素?删除一个元素,又平均需要移动多少个元素?【解答】若设顺序表中已有n个元素。又设插入或删除表中各个元素的概率相等，则在插入时因有n+1个插入位置(可以在表中最后一个表项后面追加)，每个元素位置插入的概率为1/(n+1)，但在删除时只能在已有n个表项范围内删除，所以每个元素位置删除的概率为1/n。插入时平均移动元素个数amn(averagymovingnumber)为amn???n?i??n?1i?01n1n?1(n?(n?1)???1?0)?1n?1n(n?1)2?n2?63.51n?1删除时平均移动元素个数amn为amn??ni?0(n?i?1)?1n((n?1)?(n?2)???1?0)?1(n?1)nn2?n?12?637.利用顺序表的操作，实现以下的函数。并分析你所编制的函数的时间复杂度，并分析(2)与(3)的时间复杂度出现差异的原因。(1)从顺序表中删除具有给定值x的所有元素。(2)从顺序表中删除其值在给定值s与t之间（要求s小于t）的所有元素。(3)从有序顺序表中删除其值在给定值s与t之间（要求s小于t）的所有元素。(4)将两个有序顺序表la,lb合并成一个新的有序顺序表lc。(5)从顺序表中删除所有其值重复的元素，使表中所有元素的值均不相同。【解答】(1)从顺序表中删除具有给定值x的所有元素。voiddelvalue(listtype*l,intx){inti=0,j;while(il-length)if(l-data[i]==x){l-length--;}}elsei++;(2)实现删除其值在给定值s与t之间（要求s小于t）的所有元素的函数如下：/*循环,寻找具有值x的元素并删除它*//*删除具有值x的元素,后续元素前移*//*表长减1*/for(j=i;jl-length-1;j++)l-data[j]=l-data[j+1];voiddelvalue_s_to_t(listtype*l,ints,intt){inti,j;if(l-length==0||s=t){printf(“listisemptyorparametersareillegal!\n”);exit(1);}i=0;while(il-length)/*循环,寻找具有值x的元素并删除它*/if(l-data[i]=sl-data[i]=t){/*删除满足条件的元素,后续元素前移*/for(j=i;jl-length-1;j++)l-data[j]=l-data[j+1];l-length--;}}elsei++;/*表长减1*/(3)实现从有序顺序表中删除其值在给定值s与t之间的所有元素的函数如下：voiddelvalue_s_to_t_1(listtype*l,intsintt){inti,j,k;if(l-length==0||s=t){printf(“listisemptyorparametersareillegal!\n”);exit(1);}for(i=0;il-length;i++)if(l-data[i]=s)break;if(il-length){for(j=1;i+jl-length;j++)/*循环,寻找值t的第一个元素*/if(l-data[i+j]t)break;/*退出循环时,i+j指向该元素*/}}for(k=i+j;kl-length;k++)/*删除满足条件的元素,后续元素前移*/l-data[k-j]=l-data[k];l-length-=j;/*表长减j*//*循环,寻找值≥s的第一个