数据结构 - 机器学习

题目描述在一个二维数组中（每个一维数组的长度相同），每一行都按照从左到右递增的顺序排序，每一列都按照从上到下递增的顺序排序。请完成一个函数，输入这样的一个二维数组和一个整数，判断数组中是否含有该整数。解题思路：比如在上图的二维数组中查找元素7，我们每次查找都使用当前数组右上角那个元素与目标元素作比较。比如第一次选右上角的9与7对比，7小于9，显然，9所在那一列不可能有7了，因为那一列最小的元素是9,7比9还小。我们就剔除了这一列！接下来，数组右上角的元素就变为8了，7比8小，因此再剔除这一列。此时数组右上角元素为2了，7比2大，那就剔除2所在的行，这是因为2是在这行的最右边，是这行的最大的元素，7比2大，就比这行所有元素都大，所以剔除这一行。总结一下上面的思路：当target==当前数组

一、选择题1、非空循环链表head的尾结点p满足下列(    )条件。   A.head->next==p  B.head==p  C.p->next==head  D.p->next==NULL解析：本题考点是非空循环链表的特性。因为是非空循环链表，所以尾结点的下一个结点应该是头结点。因此，本题参考答案是C。 2、设栈s的类型为sqstack，判定栈空的条件是(    )。   A.s==NULL  B.s->t

一、选择题1.二叉树中第5层上的结点个数最多为______  A.8       B.15       C.16       D.32解析：本题考点是二叉树中各层结点个数的计算方法。二叉树中第i层上的结点个数最多为2i-1。因此，本题参考答案是C。 2.一个无向连通图的生成树是含有该连通图的全部顶点的_____。  A.极小连通子图    B.极小子图  

    一、选择题1、数组的数据元素类型DataType可根据实际需要而定义。以下说法完全正确的是（     ） A．数组的读运算可以读取一个数据元素整体,写运算只能修改一个数据元素的一部分 B．数组的读、写运算可以读取或修改一个数据元素的一部分或一个整体 C．数组的读、写运算只能读取或修改一个数据元素的一部分 D．数组的读、写运算只能读取或修改一个数据元素整体解析：本题考点是数组的数据元素类型的定义。数组的读、写运算可以读取或修改一个数据元素的一部分或一个整体，当数据元素本身不是原子项时，我们可以修改一个数据元素的一部分。因此，本题参考答案是B。 

一、选择题1、顺序表是线性表的（    ） A．链式存储结构 B．顺序存储结构 C．索引存储结构 D．散列存储结构解析：本题考点是顺序表的基本特点。 顺序表是在计算机内存中以数组的形式保存的线性表，是指用一组地址连续的存储单元依次存储数据元素的线性结构。线性表采用顺序存储的方式存储就称之为顺序表。顺序表是将表中的结点依次存放在计算机内存中一组地址连续的存储单元中。因此，本题参考答案是B。 2、以下说法错误的是（    ）A．求表长、定位这二种运算在采用顺序存储结构时实现的效率不比采用链式存储结构时实现的效率低 B．顺序存储的线性表可以随机存

问题描述：在某个字符串中（字符串可能很长，比如有几千万个字符），请找出某个出现频率大于50%的那个字符。例如：在字符串"aabcdaa"中，字符串长为7，字符'a'出现了4次，其出现频率大于50%，因此'a'就是最终要输出的字符。问题分析：思路1：解决这个问题最简单的方法就是遍历一遍字符串，针对每个字符都统计出其出现的次数，最后再遍历一遍这些次数，看哪个字符的次数超过了总次数的50%。该方法的优点是思路简单明了，缺点是额外的存储空间耗费大，算法时间复杂度高。思路2：首先对这个字符串中的字符按照某种次序排序（比如字符的字典序），得到一个有序的字符串，显而易见，该字符串中间的那个字符一定就是我们要找的那个出现频率超过50%的字符。该方法的优点是

问题描述:  要求在时间复杂度和空间复杂度分别为O(n)和O(1)的条件下把一个长度为N的字符串循环左移M位，例如将长度为9的字符串"123456789"循环左移4位后得到字符串"567891234"。程序的输入为N（字符串长度）和M（循环左移的位数），输出为循环移位后的字符串。解题思路:  乍一看此题，一般人都会这样想：先把字符串的前M个字符复制到临时数组变量中，然后将余下N-M个字符都分别向左移动M位，再把临时数组变量中的M个字符粘到N-M个字符的末尾。是否很简单呢？但是，这种做法的空间复杂度是O(n)，不符合要求。    这样一来，二般人出现了，他们会这样想：

1、给出两个单向链表的头指针pHead1和pHead2，判断这两个链表是否相交。假设两个链表均不带环。如果两个链表相交于某一节点，那么在这个相交节点之后的所有节点都是两个链表所共有的。也就是说，如果两个链表相交，那么最后一个节点肯定是共有的。先遍历第一个链表，记住最后一个节点，然后遍历第二个链表，到最后一个节点时和第一个链表的最后一个节点做比较，如果相同，则相交，否则不相交。时间复杂度为O(len1+len2)，因为只需要一个额外指针保存最后一个节点地址，空间复杂度为O(1)。2、给出一个单向链表的头指针pHead，判断链表中是否有环。链表中有环，其实也就是自相交。我们用两个指针pslow和pfast从头开始遍历链表，pslow每次前进一个节点，pfast每次前进两个结点，若存在环，则psl