计算机软件基础习题及答案.docx

《计算机软件基础习题及答案.docx》由会员分享，可在线阅读，更多相关《计算机软件基础习题及答案.docx（35页珍藏版）》请在优知文库上搜索。

1、习题一L什么是数据结构，数据的逻辑结构，数据的存储结构？数据结构对算法有什么影响？请举例说明。2 .数据结构的存储方式主要有哪两种？它们之间的本质区别是什么？3 .设刀为正整数，分析以下各程序段中加下划线的语句的执行次数。(1) for(inti=1;i=n;i+)for(intj=1;j=n;j+)cij=0.0;for(intk=1;k=n;k+)cij=cij+aik*bkj;)(2) x=0;y=0;for(inti=1;i=n;i+)for(intj=1;j=i;j+)for(intk=1;k=j;k+)=+y;(3) inti=1,j=1;while(i=n&j=n)1 =i+1；

2、J=J+i；)(4)*inti=1;dofor(intj=1;j=n;j+)while(imaxlnt时，应按出错处理。可有如下三种不同的出错处理方式：(1)用Printf显示错误信息及exit(1)语句来终止执行并报告错误；(2)用返回整数函数值0,1来实现算法，以区别是正常返回还是错误返回；(3)在函数的参数表设置一个引用型的整型变量来区别是正常返回还是某种错误返回。试讨论这三种方法各自的优缺点，并以你认为是最好的方式实现它。5 .设有一个线性表(ao,a,an-2,an-)存放在一个一维数组AarraySize中的前n个数组元素位置。请编写一个函数将这个线性表原地逆置，即将数组的前n个原

3、址内容置换为(an-1,an-2,a1,a。)。最后分析此算法的时间复杂度及空间复杂度。6 .顺序表的插入和删除要求仍然保持各个元素原来的次序。设在等概率情形下，对有127个元素的顺序表进行插入，平均需要移动多少个元素？删除一个元素，又平均需要移动多少个元素？7 .利用顺序表的操作，实现以下的函数。并分析你所编制的函数的时间复杂度，并分析(2)与(3)的时间复杂度出现差异的原因。(1)从顺序表中删除具有给定值X的所有元素。(2)从顺序表中删除其值在给定值S与t之间要求S小于t)的所有元素。(3)从有序顺序表中删除其值在给定值S与t之间要求S小于t的所有元素。(4)将两个有序顺序表la,Ib合并

4、成一个新的有序顺序表Ico(5)从顺序表中删除所有其值重复的元素，使表中所有元素的值均不相同。8 .线性表可用顺序表或链表存储。试问：(1)两种存储表示各有哪些主要优缺点？(2)如果有n个表同时并存，并且在处理过程中各表的长度会动态发生变化，表的总数也可能自动改变、在此情况下，应选用哪种存储表示？为什么？(3)假设表的总数根本稳定，且很少进行插入和删除，但要求以最快的速度存取表中的元素，这时,应采用哪种存储表示？为什么？9 .试写出计算线性链表长度的算法。10设有一个表头指针为h的单链表。试设计一个算法，通过遍历一趟链表，将链表中所有结点的链接方向逆转，如以下图所示。要求逆转结果链表的表头指针

5、h指向原链表的最后一个结点。W=OPPrh11 .设有一线性链表，其结点值均为整数。试将该线性链表分解为两个线性链表，其中一链表中的结点值均为负整数，而另一链表中结点的值均为正整数，并删除结点值为零的结点。12 .设ha和hb分别是两个带表头结点的非递减有序单链表的表头指针，试设计一个算法，将这两个有序链表合并成一个非递减有序的单链表。要求结果链表仍使用原来两个链表的存储空间，不另外占用其它的存储空间。表中允许有重复的数据。13 .设ha和hb分别是两个带表头结点的非递减有序单链表的表头指针，试设计一个算法，将这两个有序链表合并成一个非递增有序的单链表。要求结果链表仍使用原来两个链表的存储空间

6、，不另外占用其它的存储空间。表中允许有重复的数据。14 .在一个循环链表中寻找值为X的结点，并将该结点移到第一个结点之前。15 .对于下面的每一步，画出栈元素和栈顶指针的示意图:1栈初始化；元素X入栈；元素y入栈；出栈栈初始化6)元素Z入栈右图所示。结构的站台,到435612,16 .铁路进行列车调度时，常把站台设计成栈式结构的站台，如试问：(1)设有编号为1,2,3,4,5,6的六辆列车，顺序开入栈式那么可能的出栈序列有多少种？(2)假设进站的六辆列车顺序如上所述，那么是否能够得325641,154623和135426的出站序列，如果不能，说明为什么不能；如果能，说明如何得到(即写出进栈或出

7、栈的序列)。17 .试证明：假设借助栈可由输入序列1,2,3,n得到一个输出序列pi,p2,p3,，小(它是输入序列的某一种排列)，那么在输出序列中不可能出现以下情况，即存在ijk,使得PjPkl)的各棵树中，高度最小的树的高度是多少？它有多少个叶结点？多少个分支结点？高度最大的树的高度是多少？它有多少个叶结点？多少个分支结点？4 .试分别画出具有3个结点的树和3个结点的二叉树的所有不同形态。5 .如果一棵树有m个度为1的结点，有112个度为2的结点，个度为m的结点，试问有多少个度为O的结点？试推导之。6 .假设用二叉链表作为二叉树的存储表示，试针对以下问题编写递归算法：(1)统计二叉树中叶结

8、点的个数。(2)以二叉树为参数，交换每个结点的左子女和右子女。(3)求二叉树的深度。7 .一棵高度为h的满k叉树有如下性质：第h层上的结点都是叶结点，其余各层上每个结点都有k棵非空子树，如果按层次自顶向下，同一层自左向右，顺序从1开始对全部结点进行编号，试问：(1)各层的结点个数是多少？(2)编号为i的结点的父结点(假设存在)的编号是多少？(3)编号为i的结点的第m个孩子结点(假设存在)的编号是多少？(4)编号为i的结点有右兄弟的条件是什么？其右兄弟结点的编号是多少？(5)假设结点个数为n,那么高度h是n的什么函数关系？8 .请画出以下图所示的树所对应的二叉树。9 .一棵二叉树的前序遍历的结果

9、是ABECDFGHIJ,中序遍历的结果是EBCDAFHIGJ,试画出这棵二叉树。10 .给定权值集合15,03,14,02,06,09,16,17),构造相应的霍夫曼树，并计算它的带权路径长度。习题三11 设有序顺序表中的元素依次为017,094,154,170,275,503,509,512,553,612,677,765,897,908o试画出对其进行折半查找时的二叉查找树，并计算查找成功的平均查找长度和查找不成功的平均查找长度。12 假设对有n个元素的有序顺序表和无序顺序表进行顺序查找，试就以下三种情况分别讨论两者在等查找概率时的平均查找长度是否相同？(1)查找失败；(2)查找成功，且表

10、中只有一个关键码等于给定值k的对象；(3)查找成功，且表中有假设干个关键码等于给定值k的对象，要求一次查找找出所有对象。13 设有100oO个记录对象，通过分块划分为假设干子表并建立索引，那么为了提高查找效率，每一个子表的大小应设计为多大？14 设散列表为HT13,散列函数为H(左”)=Aey%130用闭散列法解决冲突，对以下关键码序列12,23, 45,57,20,03,78,31,15,36造表。(1)采用线性探测法寻找下一个空位，画出相应的散列表，并计算等概率下查找成功的平均查找长度和查找不成功的平均查找长度。(2)采用随机探测法寻找下一个空位，随机数序列为：5,4,2,7,3,6,。画

11、出相应的散列表,并计算等概率下查找成功的平均查找长度。5 .设有150个记录要存储到散列表中，要求利用线性探查法解决冲突，同时要求找到所需记录的平均比拟次数不超过2次。试问散列表需要设计多大？设是散列表的装载因子，那么有ASLSUCC=(1+；-)21-a6 .设有15000个记录需放在散列文件中，文件中每个桶内各页块采用链接方式连结，每个页块可存放30个记录。假设采用按桶散列，且要求查找到一个已有记录的平均读盘时间不超过次，那么该文件应设置多少个桶？，链地址法的平均查找长度ASL=1+27 .设待排序的排序码序列为12,2,16,30,28,10,16*,20,6,18),试分别写出使用以下

12、排序方法每趟排序后的结果。并说明做了多少次排序码比拟。(1)直接插入排序(2)希尔排序(增量为5,2,1)(3)冒泡排序(4)快速排序(5)直接选择排序(6)堆排序(7)二路归并排序8 .在起泡排序过程中，什么情况下排序码会朝向与排序相反的方向移动，试举例说明。在快速排序过程中有这种现象吗？9 .试设计一个算法，使得在0(n)的时间内重排数组，将所有取负值的排序码排在所有取正值(非负值)的排序码之前。提示：比照快速排序的第一趟排序，此处，以0为控制关键字。10 .手工跟踪对以下各序列进行堆排序的过程。给出形成初始堆及每选出一个排序码后堆的变化。(1)按字母顺序排序：Tim,Dot,Eva,Rom,Kim,Guy,Ann,Jim,Kay,Ron,Jan(2)按数值递增顺序排序：26,33,35,29,19,12,22(3)同样7个