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

习题一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；J=J+i；)(4)*inti=1;dofor(intj=1;j<=n;j+)while(i<100+n);4 .试编写一个函数计算n!*2r的值，结果存放于数组AarraySize的第n个数组元素中，0narraySizeo假设设计算机中允许的整数的最大值为maxlnt,那么当QarraySize或者对于某一个k(0kn),使得k!*2k>maxlnt时，应按出错处理。可有如下三种不同的出错处理方式：(1)用Printf显示错误信息及exit(1)语句来终止执行并报告错误；(2)用返回整数函数值0,1来实现算法，以区别是正常返回还是错误返回；(3)在函数的参数表设置一个引用型的整型变量来区别是正常返回还是某种错误返回。试讨论这三种方法各自的优缺点，并以你认为是最好的方式实现它。5 .设有一个线性表(ao,a,an-2,an-)存放在一个一维数组AarraySize中的前n个数组元素位置。请编写一个函数将这个线性表原地逆置，即将数组的前n个原址内容置换为(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合并成一个新的有序顺序表Ico(5)从顺序表中删除所有其值重复的元素，使表中所有元素的值均不相同。8 .线性表可用顺序表或链表存储。试问：(1)两种存储表示各有哪些主要优缺点？(2)如果有n个表同时并存，并且在处理过程中各表的长度会动态发生变化，表的总数也可能自动改变、在此情况下，应选用哪种存储表示？为什么？(3)假设表的总数根本稳定，且很少进行插入和删除，但要求以最快的速度存取表中的元素，这时,应采用哪种存储表示？为什么？9 .试写出计算线性链表长度的算法。10设有一个表头指针为h的单链表。试设计一个算法，通过遍历一趟链表，将链表中所有结点的链接方向逆转，如以下图所示。要求逆转结果链表的表头指针h指向原链表的最后一个结点。W=OPPrh11 .设有一线性链表，其结点值均为整数。试将该线性链表分解为两个线性链表，其中一链表中的结点值均为负整数，而另一链表中结点的值均为正整数，并删除结点值为零的结点。12 .设ha和hb分别是两个带表头结点的非递减有序单链表的表头指针，试设计一个算法，将这两个有序链表合并成一个非递减有序的单链表。要求结果链表仍使用原来两个链表的存储空间，不另外占用其它的存储空间。表中允许有重复的数据。13 .设ha和hb分别是两个带表头结点的非递减有序单链表的表头指针，试设计一个算法，将这两个有序链表合并成一个非递增有序的单链表。要求结果链表仍使用原来两个链表的存储空间，不另外占用其它的存储空间。表中允许有重复的数据。14 .在一个循环链表中寻找值为X的结点，并将该结点移到第一个结点之前。15 .对于下面的每一步，画出栈元素和栈顶指针的示意图:1栈初始化；元素X入栈；元素y入栈；出栈栈初始化6)元素Z入栈右图所示。结构的站台,到435612,16 .铁路进行列车调度时，常把站台设计成栈式结构的站台，如试问：(1)设有编号为1,2,3,4,5,6的六辆列车，顺序开入栈式那么可能的出栈序列有多少种？(2)假设进站的六辆列车顺序如上所述，那么是否能够得325641,154623和135426的出站序列，如果不能，说明为什么不能；如果能，说明如何得到(即写出进栈或出栈的序列)。17 .试证明：假设借助栈可由输入序列1,2,3,n得到一个输出序列pi,p2,p3,，小(它是输入序列的某一种排列)，那么在输出序列中不可能出现以下情况，即存在i<j<k,使得Pj<Pk<Pi0(提示：用反证法)18 .将编号为O和1的两个栈存放于一个数组空间Vm中，栈底分别处于数组的两端。当第O号栈的栈顶指针top0等于T时该栈为空，当第1号栈的栈顶指针topl等于m时该栈为空。两个栈均从两端向中间增长。当向第0号栈插入一个新元素时，使top0增1得到新的栈顶位置，当向第1号栈插入一个新元素时，使topl减1得到新的栈顶位置。当top0+l=topl时或top0=toplT时，栈空间满，此时不能再向任一栈参加新的元素。试定义这种双栈(DoUbIeStaCk)结构的类定义，并实现判栈空、判栈满、插入、删除算法。19 .改写顺序栈的进栈成员函数PUSh(x),要求当栈满时执行一个StaCkFUI1()操作进行栈满处理。其功能是：动态创立一个比原来的栈数组大二倍的新数组，代替原来的栈数组，原来栈数组中的元素占据新数组的前MaxSize位置。20 .根据教案中给出的优先级，答复以下问题：(1)在表达式求值的过程中，如果表达式e含有n个运算符和分界符，问操作数栈(NS)中最多可存入多少个元素？(2)如果表达式e含有n个运算符,且括号嵌套的最大深度为6层，问栈中最多可存入多少个元素？21 .表达式的中缀表示为a*X-b/x2,试利用栈将它改为后缀表示ax*bx27-。写出转换过程中栈的变化。表示乘方运算)22 .设循环队列的容量为701序号从1到70，经过一系列入队和退队运算后，有：1)front=15,rear=46;front=45,rear=10问在上述两种情况下，循环队列中各有多少个元素？23.设用链表表示一个双端队列，要求可在表的两端插入，但限制只能在表的一端删除。试编写基于此结构的队列的插入(enqueue)和删除(dequeue)算法，并给出队列空和队列满的条件。习题21 .列出右图所示二叉树的叶结点、分支结点和每个结点的层次。2 .使用(1)顺序表示和(2)二叉链表表示法，分别画出上图所示二叉树的存储表示。3 .在结点个数为n(n>l)的各棵树中，高度最小的树的高度是多少？它有多少个叶结点？多少个分支结点？高度最大的树的高度是多少？它有多少个叶结点？多少个分支结点？4 .试分别画出具有3个结点的树和3个结点的二叉树的所有不同形态。5 .如果一棵树有m个度为1的结点，有112个度为2的结点，个度为m的结点，试问有多少个度为O的结点？试推导之。6 .假设用二叉链表作为二叉树的存储表示，试针对以下问题编写递归算法：(1)统计二叉树中叶结点的个数。(2)以二叉树为参数，交换每个结点的左子女和右子女。(3)求二叉树的深度。7 .一棵高度为h的满k叉树有如下性质：第h层上的结点都是叶结点，其余各层上每个结点都有k棵非空子树，如果按层次自顶向下，同一层自左向右，顺序从1开始对全部结点进行编号，试问：(1)各层的结点个数是多少？(2)编号为i的结点的父结点(假设存在)的编号是多少？(3)编号为i的结点的第m个孩子结点(假设存在)的编号是多少？(4)编号为i的结点有右兄弟的条件是什么？其右兄弟结点的编号是多少？(5)假设结点个数为n,那么高度h是n的什么函数关系？8 .请画出以下图所示的树所对应的二叉树。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)查找成功，且表中只有一个关键码等于给定值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,。画出相应的散列表,并计算等概率下查找成功的平均查找长度。5 .设有150个记录要存储到散列表中，要求利用线性探查法解决冲突，同时要求找到所需记录的平均比拟次数不超过2次。试问散列表需要设计多大？设是散列表的装载因子，那么有ASLSUCC=(1+；-)21-a6 .设有15000个记录需放在散列文件中，文件中每个桶内各页块采用链接方式连结，每个页块可存放30个记录。假设采用按桶散列，且要求查找到一个已有记录的平均读盘时间不超过次，那么该文件应设置多少个桶？，链地址法的平均查找长度ASL=1+27 .设待排序的排序码序列为12,2,16,30,28,10,16*,20,6,18),试分别写出使用以下排序方法每趟排序后的结果。并说明做了多少次排序码比拟。(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个