nlg算法视频教程全集

‘壹’ 生活中出现过哪些人工智能

日常生活中大家都经常在用打车软件吧，预定成功之后大家有没有发现，叫了车之后很短的时间内车就能到达，因为叫车软件系统有智能检测，它会自动的评估和测距。然后将你的位置发送给车主，接着车主会在最短的时间赶到你的位置。
2，地图导航

有没有发现现在的导航越来越好用了，那么它好用在哪里呢，原来的导航只限于城市中使用，而且很多地方导航导着导着就没路了。而现在，无论你在哪个地方，甚至精确到镇上，导航都能顺利的将你的位置给你显示出来，在城市中行车，系统的智能会为你分析路况，让你能够顺利的避开堵车，让你顺利到达你想要去的地方。
3，人脸识别

人脸识别已经开始在很多个领域中运用，生活中所用的支付系统或是金融系统的人脸识别，能给人带来安全保障。高铁进站的人脸识别，酒店以及安防系统，还有生活中的门锁等。人工智能的技术慢慢的成熟。
4，智能的个人助理

现如今几乎每个智能手机中都会用到手机助手，比如苹果手机中的Siri，三星手机中的Bixby，还有小米中的小爱同学，谷歌助手等等这些手机助手，都是运用的语音识别技术，然后执行你所发出的任务，现在这项技术都在慢慢的成熟。
5，无人驾驶

无人驾驶其实离我们并不遥远，在我们的日常生活中，高铁，地铁，飞机等均已采用了无人驾驶技术，只不过这些都是有条件的在驾驶，都是有限定的铁路或是航道等，而在现在，无人驾驶汽车技术发展很迅速，而且已经有汽车已经研究出来，只是智能技术还缺少一点，还不能普及到所有的地方去使用。
6，越来越快的物流

现在购物之后快递越来越快了大家不知道有没有发现，其实这背后有着很智能的仓储物流系统，商家的货物不是自己发，而是将商品放在仓储中心，用户下单之后，人工智能会自动分发货物，将相应的货物分往客户所处的区域栏。然后物流车每天按时发车。将货物运往预定好的地区。
7，各种机器人和智能家居

最近经常看到的机器人都采用了人工智能技术，例如，智能扫地机器人，它会运用自带的传感器扫描垃圾，然后自动打扫卫生，相当的智能。还有一种叫做陪伴机器人，能够为孩子唱歌，讲笑话，教孩子读书等。家居系统中有智能电视，智能门锁，智能空调等。都采用的人工智能的技术，而且都在朝成熟化发展。越来越人性化。

‘贰’ PHP的算法可以实现大数据分析吗

1.Bloom filter

适用范围：可以用来实现数据字典，进行数据的判重，或者集合求交集

基本原理及要点：
对于原理来说很简单，位数组+k个独立hash函数。将hash函数对应的值的位数组置1，查找时如果发现所有hash函数对应位都是1说明存在，很明显这个过程并不保证查找的结果是100%正确的。同时也不支持删除一个已经插入的关键字，因为该关键字对应的位会牵动到其他的关键字。所以一个简单的改进就是 counting Bloom filter，用一个counter数组代替位数组，就可以支持删除了。

还有一个比较重要的问题，如何根据输入元素个数n，确定位数组m的大小及hash函数个数。当hash函数个数k=(ln2)*(m/n)时错误率最小。在错误率不大于E的情况下，m至少要等于n*lg(1/E)才能表示任意n个元素的集合。但m还应该更大些，因为还要保证bit数组里至少一半为 0，则m 应该>=nlg(1/E)*lge 大概就是nlg(1/E)1.44倍(lg表示以2为底的对数)。

举个例子我们假设错误率为0.01，则此时m应大概是n的13倍。这样k大概是8个。

注意这里m与n的单位不同，m是bit为单位，而n则是以元素个数为单位(准确的说是不同元素的个数)。通常单个元素的长度都是有很多bit的。所以使用bloom filter内存上通常都是节省的。

扩展：
Bloom filter将集合中的元素映射到位数组中，用k（k为哈希函数个数）个映射位是否全1表示元素在不在这个集合中。Counting bloom filter（CBF）将位数组中的每一位扩展为一个counter，从而支持了元素的删除操作。Spectral Bloom Filter（SBF）将其与集合元素的出现次数关联。SBF采用counter中的最小值来近似表示元素的出现频率。

问题实例：给你A,B两个文件，各存放50亿条URL，每条URL占用64字节，内存限制是4G，让你找出A,B文件共同的URL。如果是三个乃至n个文件呢？

根据这个问题我们来计算下内存的占用，4G=2^32大概是40亿*8大概是340亿，n=50亿，如果按出错率0.01算需要的大概是650亿个 bit。现在可用的是340亿，相差并不多，这样可能会使出错率上升些。另外如果这些urlip是一一对应的，就可以转换成ip，则大大简单了。

2.Hashing

适用范围：快速查找，删除的基本数据结构，通常需要总数据量可以放入内存

基本原理及要点：
hash函数选择，针对字符串，整数，排列，具体相应的hash方法。
碰撞处理，一种是open hashing，也称为拉链法；另一种就是closed hashing，也称开地址法，opened addressing。 (http://www.my400800.cn)

扩展：
d-left hashing中的d是多个的意思，我们先简化这个问题，看一看2-left hashing。2-left hashing指的是将一个哈希表分成长度相等的两半，分别叫做T1和T2，给T1和T2分别配备一个哈希函数，h1和h2。在存储一个新的key时，同时用两个哈希函数进行计算，得出两个地址h1[key]和h2[key]。这时需要检查T1中的h1[key]位置和T2中的h2[key]位置，哪一个位置已经存储的（有碰撞的）key比较多，然后将新key存储在负载少的位置。如果两边一样多，比如两个位置都为空或者都存储了一个key，就把新key 存储在左边的T1子表中，2-left也由此而来。在查找一个key时，必须进行两次hash，同时查找两个位置。

问题实例：
1).海量日志数据，提取出某日访问网络次数最多的那个IP。

IP的数目还是有限的，最多2^32个，所以可以考虑使用hash将ip直接存入内存，然后进行统计。

3.bit-map

适用范围：可进行数据的快速查找，判重，删除，一般来说数据范围是int的10倍以下

基本原理及要点：使用bit数组来表示某些元素是否存在，比如8位电话号码

扩展：bloom filter可以看做是对bit-map的扩展

问题实例：

1)已知某个文件内包含一些电话号码，每个号码为8位数字，统计不同号码的个数。

8位最多99 999 999，大概需要99m个bit，大概10几m字节的内存即可。

2)2.5亿个整数中找出不重复的整数的个数，内存空间不足以容纳这2.5亿个整数。

将bit-map扩展一下，用2bit表示一个数即可，0表示未出现，1表示出现一次，2表示出现2次及以上。或者我们不用2bit来进行表示，我们用两个bit-map即可模拟实现这个2bit-map。

4.堆

适用范围：海量数据前n大，并且n比较小，堆可以放入内存

基本原理及要点：最大堆求前n小，最小堆求前n大。方法，比如求前n小，我们比较当前元素与最大堆里的最大元素，如果它小于最大元素，则应该替换那个最大元素。这样最后得到的n个元素就是最小的n个。适合大数据量，求前n小，n的大小比较小的情况，这样可以扫描一遍即可得到所有的前n元素，效率很高。

扩展：双堆，一个最大堆与一个最小堆结合，可以用来维护中位数。

问题实例：
1)100w个数中找最大的前100个数。

用一个100个元素大小的最小堆即可。

5.双层桶划分 ----其实本质上就是【分而治之】的思想，重在“分”的技巧上！

适用范围：第k大，中位数，不重复或重复的数字

基本原理及要点：因为元素范围很大，不能利用直接寻址表，所以通过多次划分，逐步确定范围，然后最后在一个可以接受的范围内进行。可以通过多次缩小，双层只是一个例子。

扩展：

问题实例：
1).2.5亿个整数中找出不重复的整数的个数，内存空间不足以容纳这2.5亿个整数。

有点像鸽巢原理，整数个数为2^32,也就是，我们可以将这2^32个数，划分为2^8个区域(比如用单个文件代表一个区域)，然后将数据分离到不同的区域，然后不同的区域在利用bitmap就可以直接解决了。也就是说只要有足够的磁盘空间，就可以很方便的解决。

2).5亿个int找它们的中位数。

这个例子比上面那个更明显。首先我们将int划分为2^16个区域，然后读取数据统计落到各个区域里的数的个数，之后我们根据统计结果就可以判断中位数落到那个区域，同时知道这个区域中的第几大数刚好是中位数。然后第二次扫描我们只统计落在这个区域中的那些数就可以了。

实际上，如果不是int是int64，我们可以经过3次这样的划分即可降低到可以接受的程度。即可以先将int64分成2^24个区域，然后确定区域的第几大数，在将该区域分成2^20个子区域，然后确定是子区域的第几大数，然后子区域里的数的个数只有2^20，就可以直接利用direct addr table进行统计了。

6.数据库索引

适用范围：大数据量的增删改查

基本原理及要点：利用数据的设计实现方法，对海量数据的增删改查进行处理。
扩展：
问题实例：

7.倒排索引(Inverted index)

适用范围：搜索引擎，关键字查询

基本原理及要点：为何叫倒排索引？一种索引方法，被用来存储在全文搜索下某个单词在一个文档或者一组文档中的存储位置的映射。

以英文为例，下面是要被索引的文本：
T0 = "it is what it is"
T1 = "what is it"
T2 = "it is a banana"
我们就能得到下面的反向文件索引：
"a": {2}
"banana": {2}
"is": {0, 1, 2}
"it": {0, 1, 2}
"what": {0, 1}
检索的条件"what", "is" 和 "it" 将对应集合的交集。

正向索引开发出来用来存储每个文档的单词的列表。正向索引的查询往往满足每个文档有序频繁的全文查询和每个单词在校验文档中的验证这样的查询。在正向索引中，文档占据了中心的位置，每个文档指向了一个它所包含的索引项的序列。也就是说文档指向了它包含的那些单词，而反向索引则是单词指向了包含它的文档，很容易看到这个反向的关系。

扩展：

问题实例：文档检索系统，查询那些文件包含了某单词，比如常见的学术论文的关键字搜索。

8.外排序

适用范围：大数据的排序，去重

基本原理及要点：外排序的归并方法，置换选择 败者树原理，最优归并树

扩展：

问题实例：
1).有一个1G大小的一个文件，里面每一行是一个词，词的大小不超过16个字节，内存限制大小是1M。返回频数最高的100个词。

这个数据具有很明显的特点，词的大小为16个字节，但是内存只有1m做hash有些不够，所以可以用来排序。内存可以当输入缓冲区使用。

9.trie树

适用范围：数据量大，重复多，但是数据种类小可以放入内存

基本原理及要点：实现方式，节点孩子的表示方式

扩展：压缩实现。

问题实例：
1).有10个文件，每个文件1G， 每个文件的每一行都存放的是用户的query，每个文件的query都可能重复。要你按照query的频度排序 。

2).1000万字符串，其中有些是相同的(重复),需要把重复的全部去掉，保留没有重复的字符串。请问怎么设计和实现？

3).寻找热门查询：查询串的重复度比较高，虽然总数是1千万，但如果除去重复后，不超过3百万个，每个不超过255字节。

10.分布式处理 maprece

适用范围：数据量大，但是数据种类小可以放入内存

基本原理及要点：将数据交给不同的机器去处理，数据划分，结果归约。

扩展：

问题实例：

1).The canonical example application of MapRece is a process to count the appearances of

each different word in a set of documents:
void map(String name, String document):
// name: document name
// document: document contents
for each word w in document:
EmitIntermediate(w, 1);

void rece(String word, Iterator partialCounts):
// key: a word
// values: a list of aggregated partial counts
int result = 0;
for each v in partialCounts:
result += ParseInt(v);
Emit(result);
Here, each document is split in words, and each word is counted initially with a "1" value by

the Map function, using the word as the result key. The framework puts together all the pairs

with the same key and feeds them to the same call to Rece, thus this function just needs to

sum all of its input values to find the total appearances of that word.

2).海量数据分布在100台电脑中，想个办法高效统计出这批数据的TOP10。

3).一共有N个机器，每个机器上有N个数。每个机器最多存O(N)个数并对它们操作。如何找到N^2个数的中数(median)？

经典问题分析

上千万or亿数据（有重复），统计其中出现次数最多的前N个数据,分两种情况：可一次读入内存，不可一次读入。

可用思路：trie树+堆，数据库索引，划分子集分别统计，hash，分布式计算，近似统计，外排序

所谓的是否能一次读入内存，实际上应该指去除重复后的数据量。如果去重后数据可以放入内存，我们可以为数据建立字典，比如通过 map，hashmap，trie，然后直接进行统计即可。当然在更新每条数据的出现次数的时候，我们可以利用一个堆来维护出现次数最多的前N个数据，当然这样导致维护次数增加，不如完全统计后在求前N大效率高。

如果数据无法放入内存。一方面我们可以考虑上面的字典方法能否被改进以适应这种情形，可以做的改变就是将字典存放到硬盘上，而不是内存，这可以参考数据库的存储方法。

当然还有更好的方法，就是可以采用分布式计算，基本上就是map-rece过程，首先可以根据数据值或者把数据hash(md5)后的值，将数据按照范围划分到不同的机子，最好可以让数据划分后可以一次读入内存，这样不同的机子负责处理各种的数值范围，实际上就是map。得到结果后，各个机子只需拿出各自的出现次数最多的前N个数据，然后汇总，选出所有的数据中出现次数最多的前N个数据，这实际上就是rece过程。

实际上可能想直接将数据均分到不同的机子上进行处理，这样是无法得到正确的解的。因为一个数据可能被均分到不同的机子上，而另一个则可能完全聚集到一个机子上，同时还可能存在具有相同数目的数据。比如我们要找出现次数最多的前100个，我们将1000万的数据分布到10台机器上，找到每台出现次数最多的前 100个，归并之后这样不能保证找到真正的第100个，因为比如出现次数最多的第100个可能有1万个，但是它被分到了10台机子，这样在每台上只有1千个，假设这些机子排名在1000个之前的那些都是单独分布在一台机子上的，比如有1001个，这样本来具有1万个的这个就会被淘汰，即使我们让每台机子选出出现次数最多的1000个再归并，仍然会出错，因为可能存在大量个数为1001个的发生聚集。因此不能将数据随便均分到不同机子上，而是要根据hash 后的值将它们映射到不同的机子上处理，让不同的机器处理一个数值范围。

而外排序的方法会消耗大量的IO，效率不会很高。而上面的分布式方法，也可以用于单机版本，也就是将总的数据根据值的范围，划分成多个不同的子文件，然后逐个处理。处理完毕之后再对这些单词的及其出现频率进行一个归并。实际上就可以利用一个外排序的归并过程。

另外还可以考虑近似计算，也就是我们可以通过结合自然语言属性，只将那些真正实际中出现最多的那些词作为一个字典，使得这个规模可以放入内存。

‘叁’ 创建一单向链表,并使用复杂度为O(nlg(n))的排序算法对该单向链表进行由小到大排序。

占个地TvT... 我想说这个10分总归有点太便宜了TvT....

我先琢磨去|||

写注释去...

--
#include <stdio.h>
#include <stdlib.h>

struct s_node
{
int i;

s_node *next;
};

s_node * create_list(int in_n)
{
s_node *head = 0, *p;

head = new s_node;

head->i = rand();

p = head;

for (int i = 1; i < in_n; i++)
{
s_node *n = new s_node;

n->i = rand();

p->next = n;
p = n;
}

return head;
}

s_node _end_node = {0x7FFFFFFF}; // 用来标记排序时子链表的结尾

s_node * sort_list(s_node **in_list, int in_n) // 对给定链表的前n个节点排序，返回第n+1个节点
{
if (in_n == 2) // 链表有两个元素的时候，判断是否交换顺序，并截断
{
s_node *a = *in_list;
s_node *b = a->next;
s_node *r = b->next;

if (a->i > b->i)
{
*in_list = b;
b->next = a;
a->next = &_end_node;
}
else
{
b->next = &_end_node;
}

return r;
}
else if (in_n == 1) // 只有一个元素直接截断
{
s_node *r = (*in_list)->next;

(*in_list)->next = &_end_node;

return r;
}
else // 分别对前半部分和后半部分排序，然后再整合两部分
{
s_node *t = sort_list(in_list, in_n / 2);
s_node *r = sort_list(&t, in_n - in_n / 2);

s_node *p0 = *in_list, *p1 = t, *p;

// 根据大小按顺序加入整合后的链表

if (p0->i < p1->i)
{
*in_list = p0;

p0 = p0->next;
}
else
{
*in_list = p1;

p1 = p1->next;
}

p = *in_list;

for (int i = 1; i < in_n; i++)
{
if (p0->i < p1->i) // 因为rand的范围不会达到0x7FFFFFFF，这里直接这么判断就可以了，因为_end_node的i是0x7FFFFFFF。否则需要判断是否到了子链表尾部。
{
p->next = p0;

p0 = p0->next;
}
else
{
p->next = p1;

p1 = p1->next;
}

p = p->next;
}

return r;
}
}

void main()
{
s_node *list = create_list(30);

sort_list(&list, 30);

for (s_node *p = list;;)
{
printf("%d\n", p->i);

if (p->next == &_end_node)
{
break;
}
else
{
p = p->next;
}
}
}

‘肆’ 用Strassen算法做矩阵乘法， 若n*n矩阵中的n不是2的幂（例如3*3矩阵），如何用strassen算法表示

找到大于等于矩阵row的最近的满足2的k次方的整数，用这个整数作为strassen矩阵的strassenRow，填进去要计算的矩阵之后其余地方填0，在输出的时候只输出row×row的矩阵即可

‘伍’ 求高手，fortran编程语言，与有限元算法有关，现缺少open中的dat文件，该文件应如何编写

nn是有限元网格的节点个数，ne为有限元网格的单元个数，(xj(i),yj(i),i=1,nn)表示每个节点的x,y坐标；((node(i,j),j=1,4),i=1,ne)表示每个单元由哪四个节点组成，由此看来对求解域的离散应该采用的是4节点四边形线性单元。根据这个情况，假设你的求解域为矩形区域，你将它离散为4个单元，每个单元有4个节点组成，共有9个节点，

输入文件内容（两虚线间的内容）应该这样写：

——————————————————————

9,4

1，x坐标值，y坐标值

2，x坐标值，y坐标值

。。。

。。。

9，x坐标值，y坐标值

1，1，4，5，2（即1号单元由1,4,5,2这4个节点组成）

2，2，5，6，3

3，4，7，8，5

4，5，8，9，6

——————————————————

当然，我只是简单举例说明，具体多少个单元和节点要看你对求解区域怎么进行有限元网格划分而定，但是格式可以按照上面写

‘陆’ 时间为O（nlg n）的排序算法 如快速排序 堆排序 nlg是什么意思。好象是lgn。 什么意思

准确来说,是log(2,n),即以2为底取n的对数.
该时间复杂度的产生是由于算法中使用了二分法.二分法的其中一个显着的标志就是使得渐进复杂度变为2底对数级别.
直观来说,对于1000个数的排序,效率为O(n)的排序(假设有)将花费1000"单位"的时间,那么O(n²)的排序将花费10^6"单位"的时间.而O(nlogn)的排序将花费 1000*log(1000) ≈ 10000 "单位"的时间.
这里可以看出其效率的显着优势,
而通过函数有关特征可以得知,对数函数是增长的越来越慢的,这就使得O(nlogn)的排序可以在越大的工作量中和平方级排序拉大差距.

‘柒’ 归并算法中时间复杂度的nlg n,中的lgn是怎么算出来的啊

n + n/2+ n/4 + n/8 + ... + n/2^logn

高度就变成 1 + 1 + 1 + ...+ 1 安装对数的定义不就是logn么。

‘捌’ ai智能客服机器人哪个好

必须是Live800智能客服机器人和Live800智能营销机器人
Live800智能客服机器人有这些优势：
1、机器人可以7*24小时工作,没有负面情绪不疲劳,有问必回，准确率高；
2、无需培训上线快，只要在知识库添加业务知识就能回答；
3、知识面广更新快不易出错，只要知识库内容充足就能不断学习成长；
4、可以同时为多名客户解决问题，降低服务人力成本；
5、在机器人聊天信息中能挖掘有价值的客户,对企业来说更容易分析数据
Live800智能营销机器人有这些优势：
1、准确率高：采用知识图谱与深度学习，对话回答准确率>97%
2、套电率高：基于深度学习模型构建的NLU、NLG算法，机器人主动驱动多轮对话，拟人化发问精准获取客户信息。客户实测比人工客服套电率提升5%~35%
4、节约成本：白、夜班独立值守，完成咨询、营销套电、建档流程。节约超过60%的人力成本。。好的，如果有需要，随时欢迎你的询问。

‘玖’ 小语智能电话机器人怎么样

伴随着市场竞争的加剧和移动互联网技术的急速发展，越来越多的企业采用了新兴的客户沟通渠道。但是不管是何种新兴的沟通方式，依然无法取代最直接最有效的电话沟通。然而随着人力成本、培训成本以及客户数量的持续上升，给企业带来了巨大的外呼成本。



电销企业面临诸多难题

人工智能AI的出现给传统的企业电销带来了巨大的变革，人工智能+外呼，机器人使用标准话术，不会受情绪影响，能够准确理解用户的回答及意图，像人与人交流一样对话，针对分配而来的不同场景进行批量合规化语音外呼操作，成功解决了外呼电销的质量保证及效率提升的问题。

小语电销机器人采用最前沿的深度学习技术，神经性算法模块，将先进的语音识别(ASR) 、口语理解(SLU)、对话管理(DM)、自然语言生成(NLG)、文本生成语音(TTS)等技术模块进行协同运作，从而快速识别出客户对话中表达的意思，精准判断客户意向并给出准确回应，完成智能高效的人机互动，达到电销外呼业务目标。



小语智能电话机器人

作为行业的领导者，小语电话机器人可主动外呼电话，与用户进行多轮语音交流，在金融催缴、保险核保、房地产推广、教育办学等领域，代替绝大多数人工。小语智能电话机器人通过人工智能颠覆了现有的传统客服电销市场，能够让使用者仅用原有人工成本的1/6， 实现5倍效率提升，4倍边际收益提升，做到低成本，高效率，高精准，零情绪，零休息。彻底解决各行业客户电销中遇到的诸多根本性问题，帮助使用者更轻松的倍增业绩，为企业更快创造更多价值。



小语电话机器人，提升5倍工作效率

‘拾’ 哪位大侠有新版农大《数据结构》和《C#》在线作业答案可否贡献一下

一 单项选择题
1.
设有数据逻辑结构为：Data=(D,R);
D={d1,d2,d3,d4,d5,d6,d7 }
R={<d1,d2>,<d2,d1>,<d1,d4>,<d4,d1>,<d2,d3>,<d3,d2>,<d2,d6>,<d6,d2>,<d2,d7>,<d7,d2>,<d3,d7><d7,d3><d4,d6><d6,d4>,<d5,d7>,<d7,d5>}
试分析该数据结构属于哪种逻辑结构？（ c）
(5.0 分)
a 图结构
b 线性逻辑结构
c 网络结构
d 树结构
2.
判断下列程序段的时间复杂度数量级（b ）。
for(i=1;i<n;i++)
for(j=1;j<=i;j++)
for(k=1;k<=j;k++)
x=x+1;
(5.0 分)
a O(1)
b O(n3)
c O(n2)
d O(n)
3.
在一个长度为n的顺序存储线性表中，向第i个元素（1<=i<=n+1）位置插入一个新元素时，需要从后向前依次后移（a ）个元素。
(5.0 分)
a n-i+1
b i
c n-i
d n-i-1
4.
在一个单链表中，若要在p所指向的结点之后插入一个新结点，则需要相继修改（d ）个指针域的内容。
(5.0 分)
a 3
b 4
c 1
d 2
5.
当利用大小为N的数组顺序存储一个栈时，假定用top==N表示栈空，则向这个栈插入一个元素时，首先应执行（b ）语句修改top指针。
(5.0 分)
a top=0
b top--
c top=N-1
d top++
6.
在规定顺序环形队列一般状态队头指针指向第一个数据元素之前的空位，队尾指针指向末尾元素的前提下，假定一个顺序循环队列的队首和队尾指针分别用front和rear表示，则判断队空的条件为（b ）。
(5.0 分)
a rear+1 == front
b front+1 == rear
c front == 0
d front == rear
7.
下述编码中不是前缀编码的是（a ）。
(5.0 分)
a {0,01,00,11}
b {1,01,000,001}
c {0,10,110,111}
d {00,01,10,11}
8.
在一棵二叉树上第5层的结点数最多为（c ）。
(5.0 分)
a 32
b 8
c 16
d 15
9.
Huffman树是带权路径长度最小的数，树中权重（b ）的结点，距离根结点（ ）。
(5.0 分)
a 较高，较远
b 较高，较近
c 较低，较近
10.
在一个具有n个顶点的有向图中，若所有顶点的出度之和为S，则所有顶点的入度之和为（b ）。
(5.0 分)
a S-1
b S
c n
d S+1
11.
采用邻接表存储的图的深度优先遍历算法，类似与二叉树的（b ）。
(5.0 分)
a 按层遍历
b 先序遍历
c 中序遍历
d 后续遍历
12.
已知有向图如下，则该图的一种拓扑序列为（b ）。

(5.0 分)
a 1-2-3-4-5-6
b 1-4-6-2-5-3
c 1-4-2-3-6-5
d 1-2-4-6-3-5
13.
对下图从顶点a出发进行深度优先遍历，正确的广度优先遍历结点序列为（c ）。

(5.0 分)
a adcbef
b adefbc
c adbcef
d abcefb
14.
对长度为3的顺序表进行查找，查找第一个元素的概率是1/2，查找第二个元素的概率是1/3，查找第三元素的概率是1/6，则查找任意元素的平均查找长度为（b ）。
(5.0 分)
a 4/3
b 5/3
c 7/3
d 2
15.
多种排序方法中：（ ）法从未排序的序列中依次取出元素，与已排序序列（初始为空）中的元素作比较，将其放入已排序序列的正确位置；（d ）法从未排序的序列中挑选元素，并将其依次放入已排序序列的正确位置。
(5.0 分)
a 插入排序，选择排序
b 归并排序，堆排序
c 基数排序，快速排序
d 冒泡排序，shell排序
16.
用希尔排序对数据序列{15,9,7,8,20，-1,4}进行排序，进行第一趟排序后，数据序列变为{15，-1,4,8，20,9,7}，你认为采用的排序asp（数据段长度）为（ ）。
(5.0 分)
a 3
b 4
c 1
d 2
17.
一组记录关键字为{46,79,56,38,40,84}，应用快速排序法，以第一个关键字作为排序对象（枢轴），得到结果为（b ）。
(5.0 分)
a 40,38,46,84,56,79
b 38,40,46,56,79,84
c 40,38,46,56,79,84
d 40,38,46,79,56,84
18.
一个无序数据序列12,36,41,20,80,55 采用顺序表存储数据，采用堆排序算法建立的初始大根堆为（d ）。
(5.0 分)
a 80,36,20,12,55,41
b 80,12,20,55,36,41
c 80,12,55,20,36,41
d 80,36,15,20,12,41
19.
给定三个算法频度函数：
f(n)=100n3+n2+1000
g(n)=25n3+4000n2
h(n)=n1.01+1000nlg(n)
指出算法时间复杂度数量级描述中错误的是（c ）。
(5.0 分)
a g(n)=O(n3)
b f(n)=O(n3)
c h(n)=O(n1.01)
d h(n)=O(nlg(n))
20.
在数据结构中，从逻辑上可以把数据结构分成（b ）。
(5.0 分)
a 内部结构和外部结构
b 线性结构和非线性结构
c 动态结构和静态结构
d 紧凑结构和非紧凑结构
一 单项选择题
1.
设有数据逻辑结构为：Data=(D,R);
D={d1,d2,d3,d4,d5,d6,d7,d8,d9,d10}
R={<d1,d2>,<d1,d3>,<d1,d4>,<d2,d5>,<d2,d6>,<d3,d7>,<d3,d8>,<d3,d9>,<d4,d10>}
试分析该数据结构属于哪种逻辑结构？（c ）
(5.0 分)
a 线型逻辑结构
b 非线性逻辑结构
c 树结构
d 网络结构
2.
计算机算法必须具备输入、输出、（b ）等5个特征。
(5.0 分)
a 确定性、有穷性和稳定性
b 可行性、确定性和有穷性
c 易读性、安全性、稳定性
d 可行性、可移植性和可扩展性
3.
在一个长度为n的顺序存储线性表中，删除值为x的元素，问进行比较和数据移动的总操作次数为（b ）。
(5.0 分)
a (n+1)/2
b n
c n+1
d n/2
4.
带头结点的链表L为空的判定条件为（b ）。
(5.0 分)
a L！=NULL
b L->next==NULL
c L==NULL
d L->next==L
5.
消除递归不一定需要使用栈的说法是（a ）的。
(5.0 分)
a 正确
b 错误
6.
在解决计算机主机与打印机之间速度不匹配问题时通常设置一个打印数据缓冲区，主机将要输出的数据一次写入该缓冲区，而打印机则从该缓冲区中取出数据打印。该缓冲区应该是一个（a ）结构。
(5.0 分)
a 队列
b 堆栈
c 数组
d 线性表
7.
树中所有结点的度的总和等于结点总数加（c ）。
(5.0 分)
a 1
b 0
c -1
d 2
8.
某二叉树先序遍历结点访问顺序是 abdgcefh,中序遍历的节点访问顺序是 dgbaechf, 则其后序遍历的结点访问顺序是（ a）。
(5.0 分)
a gdbehfa
b bdgcefha
c gdbecfha
d bdgaechf
9.
利用3,6,8,12这四个值，作为叶子结点的权重，生成一棵Huffman树，该树的带权路径长度为（b ）。
(5.0 分)
a 55
b 58
c 38
d 29
10.
最小生成树指的是连通图中（d ）。
(5.0 分)
a 定点相对较少的生成树
b 边数最少的生成树
c 连通子图
d 所有生成树中权值之和最低的生成树
11.
无向图G=（V，E），V={a,b,c,d,e}，E={<a,b>, <a,c>, <d,c>, <d,e>, <b.e>, <c,e>}, 对该图进行拓扑排序，下列序列中（d ）不是拓扑序列。
(5.0 分)
a d,a,b,c,e
b a,b,d,c,e
c a,d,c,b,e
d a,b,c,d,e
12.
已知有向图的邻接表如下：

根据有向图深度优先遍历原则，从定点V1出发，所得到的定点序列是（ d）。
(5.0 分)
a 1-2-3-5-4
b 1-2-3-4-5
c 1-4-3-5-2
d 1-3-4-5-2
13.
对下图从顶点a出发进行深度优先遍历，不可能的深度优先遍历结点序列为（ c）。

(5.0 分)
a adefbc
b adcbfe
c adbefc
d adcefb
14.
下述序列中，（d ）是执行第一趟快速排序后所得到的序列。
(5.0 分)
a 【68,11,18,69】【23,93,73】
b 【93,73】【68,11,69,23,18】
c 【68,11,69,23】【18,93,73】
d 【68,11,69,23,18】【93,73】
15.
如果待排序序列中两个数据元素具有相同的值在排序前后他们的相互位置发生颠倒，则称该排序算法是不稳定的。（ ）和（b ）就是不稳定的排序算法。
(5.0 分)
a 冒泡排序，归并排序
b shell排序，简单选择排序
c 直接插入排序，简单选择排序
d shell排序，直接插入排序
16.
对线性表进行折半查找时，要求线性表必须（c ）。
(5.0 分)
a 以链接式存储结构存储
b 以链接式存储结构存储，且数据元素有序
c 以顺序存储结构存储，且数据元素有序
d 以顺序存储结构存储
17.
下面的序列中（ a）序列是堆。
(5.0 分)
a {1,2,8,4,3,9,10,5}
b {1,5,10,6,7,8,9,2}
c {9,8,7,6,4,8,2,1}
d {9,8,7,6,5,4,3,7}
18.
给出下列典型时间复杂度数量级从低到高的顺序。（c ）
O(1), O(n), O(n2), O(n3), O(nlg(n)), O(lg(n)), O(2n)
(5.0 分)
a O(1)< O(lg(n))< O(nlg(n)) < O(n)< O(n2)< O(n3)< O(2n)
b O(1)< O(lg(n))< O(n)< O(2n)< O(n2)< O(n3)< O(nlg(n))
c O(1)< O(lg(n))< O(n)<O(nlg(n))< O(n2)< O(n3)< O(2n)
d O(1)< O(2n) < O(n)<O(lg(n))< O(n2)< O(n3)< O(nlg(n))
19.
数据结构是一门研究非数值计算程序设计问题中（ c）以及它们之间的关系和运算等的课程。
(5.0 分)
a 数据对象
b 数据映像
c 逻辑存储
d 计算方法
20.
线性表是（d ）。
(5.0 分)
a 一个无限序列，不能为空
b 一个有限序列，可以为空
c 一个无限序列，可以为空
d 一个有限序列，不能为空