数据结构 - 机器学习

题目：请实现一个函数，把字符串中的每个空格替换成"%20"。例如输入“Wearehappy.”，则输出“We%20are%20happy.”。时间复杂度为O（n2）的解法，不足以拿到Offer现在我们考虑怎么做替换操作。最直观的做法是从头到尾扫描字符串，每一次碰到空格字符的时候做替换。由于是把1个字符替换成3个字符，我们必须要把空格后面所有的字符都后移两个字节，否则就有两个字符被覆盖了。举个例子，我们从头到尾把"Wearehappy."中的每一个空格替换成"%20"。为了形象起见，我们可以用一个表格来表示字符串，表格中的每个格子表示一个字符假设字符串的长度是n。对每个空格字符，需要移动后面O（n）个字符，因此对含有O（n）个

1. 算法分析的目的是()。A.找出数据结构的合理性 B.研究算法的输入/输出关系 C.分析算法的效率以求改进 D.分析算法的易读性答案：C2. 什么是数据?它与信息是什么关系?什么是信息？广义地讲，信息就是消息。宇宙三要素（物质、能量、信息）之一。它是现实世界各种事物在人们头脑中的反映。此外，人们通过科学仪器能够认识到的也是信息。信息的特征为：可识别、可存储、可变换、可处理、可传递、可再生、可压缩、可利用、可共享。什么是数据？因为信息的表现形式十分广泛，许多信息在计算机中不方便存储和处理，例如，一个大 楼中4部电梯在软件控制下调度和运行的状态、一个商店中商品的在库明细表等，必须将它们转换成数据才能很方便地在计算机中存储、处理

1、选择题(1)直接插入排序算法的时间复杂度为（    ）A．O（N） B.O（1）   C.O(N2)   D.O(LOGN)(2)下列排序方法中，从平均时间而言最佳的是（   ）A．快速   B.希尔   C.基数   D.归并(3)下列是稳定的排序方法的（  ）A．快速   B.希尔   C.堆   D.基数(4)所需辅助空间为

实现二叉链表表示的二叉树，包括下列运算：1.建立一棵二叉树；2.按先序、中序和后序遍历二叉树；3.按层次遍历；4.求一棵二叉树的高度；5.交换一棵二叉树的左右子树；6.复制一棵二叉树；#include <stdio.h>#include <malloc.h>#include<stdlib.h>typedef char DataType;/*定义DataType类型*/typedef enum {Link,Thread}PointerTag;typedef struct node{DataType data;struct node&

根据广义表的不同形式，可以用线性表、树和图等数据结构或其修改形式来存储和实现广义表。对于定长的广义表可以用数组来存储，但是只能顺序地访问。最简单的方法是把括号也作为符号存储在数组中。可以使用链表结构存储，广义表结点的定义如下：    template <class T>        class GenListNode {    public:       int type;  //&

1. 判断题（l）栈是运算受限制的线性表。 （2）在栈空的情况下，不能作出栈操作，否则产生溢出。 （3）栈一定是顺序存储的线性结构。参考答案：(1）√    (2）√   (3）×  2. 选择题(l）设入栈序列是1、2、…、n，入栈过程中不允许中途出栈，则第i个输出的元素是(  ）。A．不确定            B.i     &nb

1. 下述算法的功能是什么？    LinkNodeDemo(LinkListL)//L是无头结点的单链表        {ListNode*P,*Q;    If (L&&L->next)     {Q=L;L=L->next;P=L;    while ( P->next)P=P->next;    P->next=Q

一、 反向用户排序函数sort()、asort()和ksort()都分别对应一个带字母“r”的反向排序函数，即rsort()、rasort()和rksort()，用户定义的排序函数没有单项变体对数组进行重新排序：函数shuffle()将数组个元素随机排序。函数array_reverse()给出一个原来数组的反向排序boolshuffle(array&$array)将数组打乱本函数打乱（随机排列单元的顺序）一个数组。arrayarray_reverse(array$array[,bool$preserve_keys])返回一个单元顺序相反的数组array_reverse()接受数组array作为输入并返回一个单元为相反顺序的新数组，如果pr

1、判断(1)大多数排序算法都有比较关键字大小和改变指向记录的指针或移动记录本身两种基本操作。(2)快速排序在任何情况下都比其他排序方法速度快。 (3)快速排序算法在每一趟排序中都能找到一个元素放在其最终位置上。 (4)如果某种排序算法不稳定，则该排序方法就没有实际应用价值。 (5)对 n个记录的进行快速排序，所需要的平均时间是 O(nlog2n)。 (6)冒泡排序是不稳定的排序。 (7)堆排序所需的时间与待排序的记录个数无关。 (8)当待排序的元素个数很多时，为了交换元素的位置要占用较多的时间，这是影响时间复杂度的主要因素。 (9)对快速排序来说，初始序列为正序或反序都是最坏的情况。参考答案：(

1、判断：图可以没有边，但不能没有顶点。答：对2、判断：在有向图中， <vl,v2>与<v2,vl>是两条不同的边。答：对3、判断：邻接表只能用于有向图的存储。答：错4、判断：用邻接矩阵法存储一个图时，在不考虑压缩存储的情况下，所占用的存储空间大小只与图中顶点个数有关，而与图的边数无关。答：对5、在一个图中，所有顶点的度数之和等于图的边数的（  ）倍。A.1/2               B.1