《算法分析与设计》练习题一

《算法分析与设计》练习题一一、简答题程序书写格式应该遵循哪四个原则？答：（1）正确使用缩进：一定要有缩进，否则代码的层次不明显。在一行内只写一条语句。‘{’, ‘}’位置不可随意放置。变量和运算符之间最好加1个空格什么是算法？答：用计算机解决问题的过程可以分成三个阶段：分析问题、设计算法和实现算法。算法可以理解为有基本运算及规定的运算顺序所构成的完整的解题步骤，它是求解问题类的、机械的、统一的方法，它由有限多个步骤组成，对于问题类中每个给定的具体问题，机械地执行这些步骤就可以得到问题的解答。或者看成按照要求设计好的有限的确切的计算序列，并且这样的步骤和序列可以解决一类问题。什么是线性结构？什么是非线性结构？答：线性结构：数据逻辑结构中的一类。它的特征是若结构为非空集，则该结构有且只有一个开始结点和一个终端结点，并且所有结点都有且只有一个直接前趋和一个直接后继。线性表就是一个典型的线性结构。栈、队列、串等都是线性结构。非线性结构：数据逻辑结构中的另一大类，它的逻辑特征是一个结点可能有多个直接前趋和直接后继。数组、广义表、树和图等数据结构都是非线性结构。已知二叉树后序遍历序列是DABEC,中序遍历序列是DEBAC,则前序遍历序列是什么？答:前序遍历序列是CEDBA什么是数制？答：数制是人们利用符号进行计数的一种科学方法。数制也称计数制,是用一组固定的符号和统一的规则来表示数值的方法。如果将十进制数106转换为八进制数，结果是多少？答：152请问查找算法的效率用什么进行度量？答：平均查找长度ASL：在查找其关键字等于给定值的过程中，需要和给定值进行比较的关键字个数的期望值称为查找成功时的平均查找长度。ASL=^ipciii=1其中，n是结点的个数；是查找第i个结点的概率，是找到第i个结点所需要的比较次数。写出快速排序法的基本思想。答：快速排序的基本思想是：将原问题分解为若干个规模更小但结构与原问题相似的子问题。递归地解决这些子问题，然后将这些子问题的解组合为原问题的解。（1）先从数列中取出一个数作为基准数。（2）分区过程，将比这个基准数大的数全放到它的右边，小于或等于它的数全放到它的左边。（3）再对左右区间重复第（2）步，直到各区间只有一个数。递归算法解决问题的特点是什么？答：（1）递归就是在函数里调用自身。（2）在使用递归策略时，必须有一个明确的递归结束条件，称为递归出口。（3）递归算法解题通常显得很简洁，但递归算法的运行效率较低。（4）在递归调用的过程当中系统为每一层的返回点、局部量等开辟了栈来存储。递归次数过多容易造成栈溢出等。所以一般不提倡用递归算法设计程序。简述空串与空格串的区别。答：不含任何字符的串称为空串，其长度为0。仅含有空格字符的串称为空格串，其长度为串中空格字符的个数。空格符可用来分割一般的字符，便于人们识别和阅读，但计算串长时应包括这些空格符。空串在串处理中可作为任意串的子串。程序调试的作用是什么？经过调试后的程序是否需要再测试？答：程序调试的作用是将程序测试过程中发现的错误改正过来，程序调试后需要再次进行测试。算法通常有哪些特征？答：（1）输入：所谓输入是指从算法在执行时需要从外界取得必要的信息。一个算法有零个或多个输入，以刻画运算对象的初始情况。（2）确定性：算法的每一个步骤必须要确切地定义。即算法中所有有待执行的动作必须严格而不含混地进行规定，不能有歧义性，以保证算法的实际执行结果是精确地符合要求或期望，通常要求实际运行结果是确定的。（3）有穷性（有限性）：一个算法在执行有限步之后必须结束。也就是说，一个算法，它所包含的计算步骤应是有限的。（4）输出：算法有一个或多个的输出，即与输入有某个特定关系的量，简单地说就是算法的最终结果。（5）有效性（可行性）：算法中有待执行的运算和操作必须是相当基本的，换言之，它们都是能够精确地进行的，算法执行者甚至不需要掌握算法的含义即可根据该算法的每一步骤要求进行操作，并最终得出正确的结果。什么是数据结构？答：数据结构指的是数据之间的相互关系，即数据的组织形式。一般包括三个方面的内容:数据的逻辑结构、存储结构和数据的运算。一个栈的初始状态为空，首先将元素5，4，3，2，1依次入栈，然后退栈一次，再将元素A、B、C、D依次入栈，之后将所有元素全部退栈，则所元素退栈（包括中间退栈的元素）的顺序为什么？答：1DCBA2345列出几种常见的进制（至少三种）答：通常采用的进制有十进制、二进制、八进制和十六进制等。如果将十进制数238转换为二进制数，结果是多少？答：11101110什么是查找？答：根据给定的某个值，在查找表中确定一个其关键字等于给定值的记录或数据元素。写出插入排序基本思想及排序步骤。答：排序基本思想：每次将一个待排序的数据元素，插入到前面已经排好序的数列中的适当位置，使数列依然有序；直到待排序数据元素全部插入完为止。插入排序步骤：第i次插入的数是a[i],这时数组b中的b[0]~b[i-1]E经有序了，将a[i]插入到数组b中的合适位置。插入@[V的过程，分为3个步骤：（1）从b[0]开始，在b[0]~b[i-1]范围内找第一个大于a[i]的数，其位置记为k;（2）从b[i-1]开始，将b[i-1]~b[k]复制到后一个位置，相当于将这些数“后移”一个位置；（3）将a[i]放置在b[k]位置上，替换b[k]。递推算法与递归算法的区别是什么？答：递推：知道第一个，推出下一个，直到达到目的。递归：要知道第一个，需要先知道下一个，直到一个已知的，再反回来，得到上一个，直到第一个。简述主串与子串的关系。答：串中任意个连续的字符组成的子序列被称为该串的子串。包含子串的串又被称为该子串的主串。子串在主串中第一次出现的第一个字符的位置称子串在主串中的位置。如果将二进制数101001101011转换为十六进制数，结果是多少？答：A6B对于长度为n的有序表，折半查找的平均查找长度是多少？答：平均查找长度是logn次。2写出归并排序法的基本思想。答：归并排序是将两个或两个以上的有序子表合并成一个新的有序表。初始时，把含有n个结点的待排序序列看作由n个长度都为1的有序子表组成，将它们依次两两归并得到长度为2的若干有序子表，再对它们两两合并。直到得到长度为n的有序表，排序结束。请写出递归的基本概念，以及设计递归算法的两个关键问题。答：递归的概念：一个函数直接或间接调用自己本身，这种函数叫递归函数。设计递归算法的两个关键问题：（1）确定递推公式（2）确定边界（终了）条件（递归出口）25.写出如下字符处理函数的功能：（1）intisdigit（intc）（2）intisalpha（intc）（3）intisalnum（intc）（4）intislower（intc）（5）intisupper（intc）答：（1）intisdigit（intC）判断C是否是数字字符，是则返回1,否则返回0。（2）intisalpha（intC）判断C是否是