《计算机软件基础习题及其参考-答案~》由会员分享，可在线阅读，更多相关《计算机软件基础习题及其参考-答案~（36页珍藏版）》请在金锄头文库上搜索。
1、-_习题一1.什么是数据结构，数据的逻辑结构，数据的存储结构？数据结构对算法有什么影响？请举例说明。2.数据结构的存储方式主要有哪两种？它们之间的本质区别是什么？3.设n为正整数, 分析下列各程序段中加下划线的语句的执行次数。(1)for (int i = 1; i = n; i+) for (int j = 1; j = n; j+) cij = 0.0; for (int k = 1; k = n; k+) cij = cij + aik * bkj; (2)x = 0; y = 0; for (int i = 1; i = n; i+) for (int j = 1; j = i; j+
2、) for (int k = 1; k = j; k+) x = x + y;(3)int i = 1, j = 1; while (i=n & j=n) i = i + 1; j = j + i; (4)*int i =1; do for (int j = 1; j = n; j+) i = i + j; while(iarraySize或者对于某一个k (0 k n)，使得k!*2k maxInt时，应按出错处理。可有如下三种不同的出错处理方式：(1) 用printf显示错误信息及exit(1)语句来终止执行并报告错误；(2) 用返回整数函数值0, 1来实现算法，以区别是正常返回还是错误返
3、回；(3) 在函数的参数表设置一个引用型的整型变量来区别是正常返回还是某种错误返回。试讨论这三种方法各自的优缺点，并以你认为是最好的方式实现它。5.设有一个线性表 (a0, a1, , an-2, an-1) 存放在一个一维数组AarraySize中的前n个数组元素位置。请编写一个函数将这个线性表原地逆置，即将数组的前n个原址内容置换为 (an-1, an-2, , a1, a0)。最后分析此算法的时间复杂度及空间复杂度。6.顺序表的插入和删除要求仍然保持各个元素原来的次序。设在等概率情形下, 对有127个元素的顺序表进行插入, 平均需要移动多少个元素? 删除一个元素, 又平均需要移动多少个元
4、素?7.利用顺序表的操作，实现以下的函数。并分析你所编制的函数的时间复杂度，并分析(2)与(3)的时间复杂度出现差异的原因。(1) 从顺序表中删除具有给定值x的所有元素。(2) 从顺序表中删除其值在给定值s与t之间（要求s小于t）的所有元素。(3) 从有序顺序表中删除其值在给定值s与t之间（要求s小于t）的所有元素。(4) 将两个有序顺序表la,lb合并成一个新的有序顺序表lc。(5) 从顺序表中删除所有其值重复的元素，使表中所有元素的值均不相同。8.线性表可用顺序表或链表存储。试问：(1) 两种存储表示各有哪些主要优缺点?(2) 如果有n个表同时并存，并且在处理过程中各表的长度会动态发生变化
5、，表的总数也可能自动改变、在此情况下，应选用哪种存储表示？为什么？(3) 若表的总数基本稳定，且很少进行插入和删除，但要求以最快的速度存取表中的元素，这时，应采用哪种存储表示？为什么？9.试写出计算线性链表长度的算法。10.设有一个表头指针为h的单链表。试设计一个算法，通过遍历一趟链表，将链表中所有结点的链接方向逆转，如下图所示。要求逆转结果链表的表头指针h指向原链表的最后一个结点。11.设有一线性链表，其结点值均为整数。试将该线性链表分解为两个线性链表，其中一链表中的结点值均为负整数，而另一链表中结点的值均为正整数，并删除结点值为零的结点。12设ha和hb分别是两个带表头结点的非递减有序单链
6、表的表头指针, 试设计一个算法, 将这两个有序链表合并成一个非递减有序的单链表。要求结果链表仍使用原来两个链表的存储空间, 不另外占用其它的存储空间。表中允许有重复的数据。13设ha和hb分别是两个带表头结点的非递减有序单链表的表头指针, 试设计一个算法, 将这两个有序链表合并成一个非递增有序的单链表。要求结果链表仍使用原来两个链表的存储空间, 不另外占用其它的存储空间。表中允许有重复的数据。14.在一个循环链表中寻找值为x的结点，并将该结点移到第一个结点之前。15.对于下面的每一步，画出栈元素和栈顶指针的示意图：（1）栈初始化；（2）元素x入栈；（3）元素y入栈；（4）出栈（5）栈初始化（6
7、）元素z入栈16.铁路进行列车调度时, 常把站台设计成栈式结构的站台，如右图所示。试问：(1) 设有编号为1,2,3,4,5,6的六辆列车, 顺序开入栈式结构的站台, 则可能的出栈序列有多少种?(2) 若进站的六辆列车顺序如上所述, 那么是否能够得到435612, 325641, 154623和135426的出站序列, 如果不能, 说明为什么不能; 如果能, 说明如何得到(即写出进栈或出栈的序列)。17.试证明：若借助栈可由输入序列1, 2, 3, , n得到一个输出序列p1, p2, p3, , pn (它是输入序列的某一种排列)，则在输出序列中不可能出现以下情况，即存在i j k，使得pj
8、 pk 1)的各棵树中，高度最小的树的高度是多少？它有多少个叶结点？多少个分支结点？高度最大的树的高度是多少？它有多少个叶结点？多少个分支结点？4试分别画出具有3个结点的树和3个结点的二叉树的所有不同形态。5如果一棵树有n1个度为1的结点, 有n2个度为2的结点, , nm个度为m的结点, 试问有多少个度为0的结点? 试推导之。6若用二叉链表作为二叉树的存储表示，试针对以下问题编写递归算法：(1) 统计二叉树中叶结点的个数。(2) 以二叉树为参数，交换每个结点的左子女和右子女。(3) 求二叉树的深度。7一棵高度为h的满k叉树有如下性质: 第h层上的结点都是叶结点, 其余各层上每个结点都有k棵非
9、空子树, 如果按层次自顶向下, 同一层自左向右, 顺序从1开始对全部结点进行编号, 试问:(1) 各层的结点个数是多少?(2) 编号为i的结点的父结点(若存在)的编号是多少?(3) 编号为i的结点的第m个孩子结点(若存在)的编号是多少?(4) 编号为i的结点有右兄弟的条件是什么? 其右兄弟结点的编号是多少?(5) 若结点个数为 n, 则高度h是n 的什么函数关系?8请画出下图所示的树所对应的二叉树。123456789已知一棵二叉树的前序遍历的结果是ABECDFGHIJ, 中序遍历的结果是EBCDAFHIGJ, 试画出这棵二叉树。10给定权值集合15, 03, 14, 02, 06, 09, 1
10、6, 17, 构造相应的霍夫曼树, 并计算它的带权路径长度。习题三1. 设有序顺序表中的元素依次为017, 094, 154, 170, 275, 503, 509, 512, 553, 612, 677, 765, 897, 908。试画出对其进行折半查找时的二叉查找树, 并计算查找成功的平均查找长度和查找不成功的平均查找长度。2. 若对有n个元素的有序顺序表和无序顺序表进行顺序查找, 试就下列三种情况分别讨论两者在等查找概率时的平均查找长度是否相同?(1) 查找失败;(2) 查找成功, 且表中只有一个关键码等于给定值k的对象;(3) 查找成功, 且表中有若干个关键码等于给定值k的对象, 要
11、求一次查找找出所有对象。3. 设有10000个记录对象, 通过分块划分为若干子表并建立索引, 那么为了提高查找效率, 每一个子表的大小应设计为多大? 4. 设散列表为HT13, 散列函数为 H (key) = key %13。用闭散列法解决冲突, 对下列关键码序列 12, 23, 45, 57, 20, 03, 78, 31, 15, 36 造表。(1) 采用线性探测法寻找下一个空位, 画出相应的散列表, 并计算等概率下查找成功的平均查找长度和查找不成功的平均查找长度。(2) 采用随机探测法寻找下一个空位, 随机数序列为：5，4，2，7，3，6，。画出相应的散列表, 并计算等概率下查找成功的平均查找长度。5. 设有150个记录要存储到散列表中, 要求利用线性探查法解决冲突, 同时要求找到所需记录的平均比较次数不超过2次。试问散列表需要设计多大？ 设a是散列表的装载因子，则有6. 设有15000个记录需放在散列文件中，文件中每个桶内各页块采用链接方式连结，每个页块可存放30个记录。若采用按桶散列，且要求查找到一个已有记录的平均读盘时间不超过1.5次，则该文件应设置多少个桶
