软件技术基础概论习题解析与上机指导

出版时间：2012-8  出版社：科学出版社  作者：吕林涛 编  页数：150  字数：2220000  

内容概要

本书是与《软件技术基础概论》(吕林涛主编，科学出版社出版)配套使用的教学辅导书。全书分两篇，共17章：习题解析篇主要包括数据结构、软件工程技术、数据库技术、统一建模语言UML和Web网页设计各章末的习题解析；算法上机实现篇主要包括线性表算法、栈和队列算法、树与二叉树算法、图算法、查找算法和排序算法上机实现。书中的全部算法都在VisualC++6．0环境下测试通过。通过本书的学习，读者可以进一步深入理解软件技术基本手段和常用方法，提高分析问题和解决问题的能力。
本书可作为高等学校工学专业和其他相关专业本科生、研究生教材，也可作为工程应用领域中应用软件进行开发的科研和工程技术人员的参考书。

书籍目录

第1篇　习题解析
　第1章 绪论
　第2章 线性表
　第3章 栈和队列
　第4章 树与二叉树
　第5章 图
　第6章 查找
　第7章 排序
　第8章 软件工程技术
　第9章 数据库技术
　第10章 统一建模语言UML
　第11章 Web网页设计
第2篇　算法上机实现
　第12章 线性表算法
　 12．1 顺序表基本运算
　 12．2 在表头插入生成单链表
　 12．3 在表尾插入生成单链表
　 12．4 单链表基本运算
　 12．5 例12．1算法实现
　 12．6 例12．2算法实现
　 12．7 例12．3算法实现
　 12．8 例12．4算法实现
　 12．9 例12．5算法实现
　第13章 栈和队列算法
　 13．1 顺序栈基本运算
　 13．2链栈基本运算
　 13．3 循环队列基本运算
　 13．4 链队列基本运算
　 13．5 例13．1算法实现
　 13．6 例13．2算法实现
　……

章节摘录

版权页：   插图：   （2）链接表法为解决冲突的方法，其余均为哈希函数构造方法，故选A、B、C、E。 3.填空题。 （1）顺序查找含有n个元素的顺序表；若查找成功，则比较关键字的次数最多为___次；当使用监视哨时，若查找失败，则比较关键字的次数为___。 （2）在n个记录的有序表中进行折半查找，则最大的比较次数是___。 （3）设顺序表（a1，a2，…，a500）元素的值由小到大排列，对一个给定的k值用二分法查找顺序表，在查找不成功时至多需要比较___次。 （4）用二分法查找一个线性表时，该线性表必须具有的特点是___；而分块查找法要求将待查的表均匀地分成若干块且块中的元素可无序存放，但块与块之间___。 （5）分块查找中，若索引表对各块内均采用顺序查找，则有900个元素的线性表分成___块最好；若分成25块，其平均查找长度为___。 （6）二叉排序树的查找长度不仅与___有关，也与二叉排序树的___有关。 （7）在二叉排序树上插入新结点时不必移动其他结点，仅需使树叶结点的指针由指向新结点即可。 （8）假定有k个关键字互为同义词，若用线性探测再散列的方法把这k个关键字存入散列表中，则至少需要进行___次探测。 【解析】 （1）顺序查找n个元素，则查找成功时比较次数最多的是查找第n个元素，即需查找n次；若使用监视哨，则查找失败的情况发生在查完n个元素却仍未找到要找的元素并在遇到监视哨时终止查找，也即共查找了n+1次，所以应填：n；n+1。 （2）相当于走了一个完全二叉树由树根到树叶的长度，即|log：n|+1，故应填：|log2n|+1。 （3）由log2n+1可知log2 500+1=9，故应填：9。 （4）应填：顺序存储且有序；有序。 （5）设每块中有S个记录，则对长度为n的表来说，当s取√n时平均查找长度为最小值：√n+1。对本题则s=√900=30，即块数=900÷30=30为最好。设块数为b，则平均查找长度，对本题则有故应填：30；31.5。 （6）应填：结点数n；生成过程（或形态）。 （7）二叉排序树插入新结点时总是将该结点作为树叶结点插入。因此，总是使原来某个树叶结点的指针由空改为指向这个新插入的树叶结点，故应填：空。 （8）设表长为m，关键字的个数为n，若发生冲突的地址为d，则依次探查d+1，d+2，…，m—1，0，1，…，d—1，直到找到一个空单元地址为止。假定冲突的单元地址d之后和之前都为空单元，则k个同义词关键字依次探测存入散列表而需进行1+2+…+k次探测。如果在地址d之后或之前存在非空单元，则探测的次数必然大于，故应填。 4.判断题。 （1）用数组或单链表存储的有序表均可用折半查找方法来提高查找速度。 （2）有n个数存放在一维数组中，在进行顺序查找时，这n个数的排列有序或无序决定了平均查找长度的不同。 （3）在任意一棵非空二叉排序树中，删除某结点后又将其插入，则所得到的二叉排序树与删除之前的原二叉排序树相同。

编辑推荐

《普通高等教育电气信息类应用型规划教材:软件技术基础概论习题解析与上机指导》可作为高等学校工学专业和其他相关专业本科生、研究生教材，也可作为工程应用领域中应用软件进行开发的科研和工程技术人员的参考书。