计算英语教程 12

DataStructureUnit4TextA

Contents

NewWords

Abbreviations

Phrases课文讲解NewWordsNewWordsNewWordsNewWordsNewWordsPhrasesPhrasesPhrasesAbbreviationsStudyofKeyNewWordsStudyofKeyNewWordsStudyofKeyNewWordsStudyofKeyNewWordsStudyofKeyNewWordsStudyofKeyNewWordsStudyofKeyPhrases

StudyofKeyPhrases

StudyofKeyPhrases

StudyofKeyPhrases

StudyofKeyPhrases

StudyofKeyAbbreviationsStudyofKeyAbbreviationsListeningtoTextAnalysisofDifficultSentencesAnalysisofDifficultSentencesAnalysisofDifficultSentencesAnalysisofDifficultSentencesDataStructureSimplyput,adatastructureisacontainerthatstoresdatainaspecificlayout.This“layout”allowsadatastructuretobeefficientinsomeoperationsandinefficientinothers.Thefollowingarethetopeightdatastructuresthatyoushouldknow.英

文数据结构简而言之，数据结构是一个以特定布置存储数据的容器。这种“布置”使数据结构在某些操作中有效，而在另一些操作中效率低下。以下是你应该了解的八大数据结构。中

文课文讲解1.ArraysAnarrayisthesimplestandmostwidelyuseddatastructure.Otherdatastructureslikestacksandqueuesarederivedfromarrays.Here’sanimageofasimplearrayofsize4,containingelements(1,2,3and4):(seefigure4-1)Eachdataelementisassignedapositivenumericalvaluecalledtheindex,whichcorrespondstothepositionofthatiteminthearray.Themajorityoflanguagesdefinethestartingindexofthearrayas0.英

文1.数组数组是最简单、使用最广泛的数据结构。其它数据结构（如堆栈和队列）是从数组派生而来。这是大小为4的简单数组的图像，其中包含元素（1、2、3和4）:（图略）每个数据元素都被分配一个称为下标的正数值，该数值对应于该项在数组中的位置。大多数语言将数组的起始下标定义为0。中

文课文讲解Thefollowingarethetwotypesofarrays:●One-dimensionalarrays(asshownabove)●Multi-dimensionalarrays(arrayswithinarrays)英

文以下是两种类型的数组：●一维数组（如上所示）●多维数组（数组中的数组）中

文课文讲解Basicoperationsofarrays:●Insert—Insertsanelementatgivenindex.●Get—Returnstheelementatgivenindex.●Delete—Deletesanelementatgivenindex.●Size—Getthetotalnumberofelementsinarray.英

文数组的基本操作：●插入—在给定下标处插入元素。●获取—返回给定下标处的元素。●删除—删除给定下标处的元素。●大小—获取数组中元素的总数。中

文课文讲解Commonlyaskedarrayinterviewquestions:●Findthesecondminimumelementofanarray.●Findfirstnon-repeatingintegersinanarray.●Mergetwosortedarrays.●Rearrangepositiveandnegativevaluesinanarray.英

文常见的面试问题：●查找数组的第二小的元素。●查找数组中的第一个非重复整数。●合并两个排序的数组。●在数组中重新排列正值和负值。中

文课文讲解2.StacksWeareallfamiliarwiththefamousUndooption,whichispresentinalmosteveryapplication.Everwonderedhowitworks?Theidea:youstorethepreviousstatesofyourwork(whicharelimitedtoaspecificnumber)inthememoryinsuchanorderthatthelastoneappearsfirst.Thiscan’tbedonejustbyusingarrays.Thatiswherethestackcomesinhandy.英

文2.堆栈我们都熟悉著名撤消选项，目前几乎所有的应用软件都有这一选项。有没有想过它是如何工作的？这个想法是：按照最后一个放在最前面的顺序，将工作的先前状态（限于特定数量）存储在内存中。这不能仅通过使用数组来完成。那堆栈就派上用场了。中

文课文讲解Areal-lifeexampleofstackcouldbeapileofbooksplacedinaverticalorder.Inordertogetthebookthat’ssomewhereinthemiddle,youwillneedtoremoveallthebooksplacedontopofit.ThisishowtheLIFO(LastInFirstOut)methodworks.Here’sanimageofstackcontainingthreedataelements(1,2and3),where3isatthetopandwillberemovedfirst:(seefigure4-2)英

文现实生活中垂直顺序放置的一摞书可以是堆栈的示例。为了拿到中间的书籍，你需要拿开所有放在其上面的书籍。这就是LIFO（后进先出）方法的工作方式。这是包含三个数据元素（1、2和3）的堆栈图像，其中3在顶部，并且将首先移去：（图略）中

文课文讲解Basicoperationsofstack:●Push—Insertsanelementatthetop.●Pop—Returnsthetopelementafterremovingfromthestack.●isEmpty—Returnstrueifthestackisempty.●Top—Returnsthetopelementwithoutremovingfromthestack.英

文堆栈的基本操作：●Push—在顶部插入一个元素。●Pop—返回顶部元素并将其从堆栈中移除。●isEmpty—如果堆栈为空，则返回true。●Top—返回顶部元素，但不从堆栈中移除。中

文课文讲解Commonlyaskedstackinterviewquestions:●Evaluatepostfixexpressionusingastack.●Sortvaluesinastack.●Checkbalancedparenthesesinanexpression.英

文堆栈面试常见问题：●使用堆栈计算后缀表达式。●对堆栈中的值进行排序。●检查表达式中的括号是否配对。中

文课文讲解3.QueuesSimilartostack,queueisanotherlineardatastructurethatstorestheelementinasequentialmanner.TheonlysignificantdifferencebetweenstackandqueueisthatinsteadofusingtheLIFOmethod,queueimplementstheFIFOmethod,whichisshortforFirstinFirstOut.Aperfectreal-lifeexampleofqueue:alineofpeoplewaitingataticketbooth.Ifanewpersoncomes,theywilljointhelinefromtheend,notfromthestart—andthepersonstandingatthefrontwillbethefirsttogettheticketandhenceleavetheline.英

文3.队列类似于堆栈，队列是另一种线性数据结构，它以顺序方式存储元素。堆栈和队列之间的唯一显著区别是，队列使用FIFO方法代替了LIFO方法，该方法是先进先出的缩写。一个真实的队列示例：人们在售票亭排队等待。如果有新人来，将排在队尾而不是队首——站在最前面的人将是第一个获得票先离开。中

文课文讲解Here’sanimageofqueuecontainingfourdataelements(1,2,3and4),where1isatthetopandwillberemovedfirst:(seefigure4-3)英

文这是一张包含四个数据元素（1、2、3和4）的队列图像，其中1位于顶部，并且将首先移去：（图略）中

文课文讲解BasicoperationsofQueue:●Enqueue()—Insertselementtotheendofthequeue.●Dequeue()—Removesanelementfromthestartofthequeue.●isEmpty()—Returnstrueifqueueisempty.●Top()—Returnsthefirstelementofthequeue.英

文队列的基本操作：●Enqueue()—将元素插入队列的末尾。●Dequeue()—从队列的开头删除一个元素。●isEmpty()—如果队列为空，则返回true。●Top()—返回队列的第一个元素。中

文课文讲解Commonlyaskedqueueinterviewquestions:●Implementstackusingaqueue.●Reversefirstkelementsofaqueue.●Generatebinarynumbersfrom1tonusingaqueue.英

文队列面试常见问题：●使用队列实现堆栈。●反转队列的前k个元素。●使用队列生成从1到n的二进制数。中

文课文讲解4.LinkedListAlinkedlistisanotherimportantlineardatastructurewhichmightlooksimilartoarraysatfirstbutdiffersinmemoryallocation,internalstructureandhowbasicoperationsofinsertionanddeletionarecarriedout.Alinkedlistislikeachainofnodes,whereeachnodecontainsinformationlikedataandapointertothesucceedingnodeinthechain.There’saheadpointer,whichpointstothefirstelementofthelinkedlist,andifthelistisemptythenitsimplypointstonullornothing.英

文4.链表链表是另一种重要的线性数据结构，乍一看可能与数组相似，但在内存分配、内部结构以及插入和删除的基本操作方式上有所不同。链表就像一个节点链，其中每个节点都包含信息（例如数据）和指向链中后续节点的指针。有一个头指针，它指向链接列表的第一个元素，如果列表为空，则仅指向null或不指向任何内容。中

文课文讲解Linkedlistsareusedtoimplementfilesystems,hashtables,andadjacencylists.Here’savisualrepresentationoftheinternalstructureofalinkedlist:(seefigure4-4)Followingarethetypesoflinkedlists:●Singlylinkedlist(Unidirectional)●Doublylinkedlist(Bidirectional)英

文链表用于实现文件系统、哈希表和邻接表。这是链接列表内部结构的直观表示：（图略）以下是链接列表的类型：●单链表（单向）●双链表（双向）中

文课文讲解Basicoperationsoflinkedlist:●InsertAtEnd—Insertsgivenelementattheendofthelinkedlist.●InsertAtHead—Insertsgivenelementatthestart/headofthelinkedlist.●Delete—Deletesgivenelementfromthelinkedlist.●DeleteAtHead—Deletesfirstelementofthelinkedlist.●Search—Returnsthegivenelementfromalinkedlist.●isEmpty—Returnstrueifthelinkedlistisempty.英

文链表的基本操作：●InsertAtEnd—在链表的末尾插入给定的元素。●InsertAtHead—在链接列表的开头插入给定的元素。●Delete—从链表中删除给定的元素。●DeleteAtHead—删除链表的第一个元素。●Search—从链表中返回给定的元素。●isEmpty—如果链接列表为空，则返回true。中

文课文讲解Commonlyaskedlinkedlistinterviewquestions:●Reversealinkedlist.●Detectloopinalinkedlist.●ReturnNthnodefromtheendinalinkedlist.●Removeduplicatesfromalinkedlist.英

文常见的链表面试问题：●反向链表。●在链表中检测循环。●从链表的末尾返回第N个节点。●删除链表中的重复项。中

文课文讲解5.GraphsAgraphisasetofnodesthatareconnectedtoeachotherintheformofanetwork.Nodesarealsocalledvertices.Apair(x,y)iscalledanedge,whichindicatesthatvertexxisconnectedtovertexy.Anedgemaycontainweight/cost,showinghowmuchcostisrequiredtotraversefromvertexxtoy.(seefigure4-5)Typesofgraphs:●Undirectedgraph●Directedgraph英

文5.图图是一组以网络形式相互连接的节点。节点也称为顶点。一个pair(x,y)称为边，它表示顶点x连接到顶点y的边。一条边可能包含重量/成本，表明从顶点x到y遍历需要多少成本。（图略）图的类型：●无向图●有向图中

文课文讲解Inaprogramminglanguage,graphscanberepresentedusingtwoforms:●Adjacencymatrix●AdjacencylistCommongraphtraversingalgorithms:●Breadthfirstsearch●Depthfirstsearch英

文在编程语言中，图形可以使用两种形式表示：●邻接矩阵●邻接表常见的图遍历算法：●广度优先搜索●深度优先搜索中

文课文讲解Commonlyaskedgraphinterviewquestions:●Implementbreadthanddepthfirstsearch.●Checkifagraphisatreeornot.●Countnumberofedgesinagraph.●Findtheshortestpathbetweentwovertices.英

文图面试常见问题：●进行广度和深度优先搜索。●检查图形是否为树。●计算图中的边数。●查找两个顶点之间的最短路径。中

文课文讲解6.TreesAtreeisahierarchicaldatastructureconsistingofvertices(nodes)andedgesthatconnectthem.Treesaresimilartographs,butthekeypointthatdifferentiatesatreefromthegraphisthatacyclecannotexistinatree.Treesareextensivelyusedinartificialintelligenceandcomplexalgorithmstoprovideanefficientstoragemechanismforproblem-solving.Here’sanimageofasimpletree,andbasicterminologiesusedintreedatastructure:(seefigure4-6)英

文6.树树是由顶点（节点）和连接它们的边组成的分层数据结构。树类似于图，但是区别图与树的关键是树中不能存在循环。树被广泛用于人工智能和复杂算法中，以提供有效的存储机制来解决问题。这是一棵简单的树的图像，以及树数据结构中使用的基本术语：（图略）中

文课文讲解Thefollowingarethetypesoftrees:●N-arytree●Balancedtree●Binarytree●Binarysearchtree●AVLtree●Redblacktree●2–3treeOutoftheabove,binarytreeandbinarysearchtreearethemostcommonlyusedtrees.英

文以下是树的类型：●N叉树●平衡树●二叉树●二叉搜索树●AVL树●红黑树●2–3棵树其中，二叉树和二叉搜索树是最常用的树。中

文课文讲解Commonlyaskedtreeinterviewquestions:●Findtheheightofabinarytree.●Findkthmaximumvalueinabinarysearchtree.●Findnodesat“k”distancefromtheroot.●Findancestorsofagivennodeinabinarytree.英

文树面试常见问题：●查找二叉树的高度。●在二叉搜索树中找到第k个最大值。●查找距离根节点为“k”的节点。●在二叉树中查找给定节点的先辈中

文课文讲解7.TrieTrie,whichisalsoknownas“PrefixTrees”,isatree-likedatastructurewhichprovestobequiteefficientforsolvingproblemsrelatedtostrings.Itprovidesfastretrieval,andismostlyusedforsearchingwordsinadictionary,providingautosuggestionsinasearchengine,andevenforIProuting.Here’sanillustrationofhowthethreewords“top”,“thus”,and“their”arestoredinTrie:(seefigure4-7)Thewordsarestoredinthetoptothebottommannerwheregreencolorednodes“p”,“s”and“r”indicatestheendof“top”,“thus”,and“their”respectively.英

文7.字典树字典树也称为“前缀树”，是一种类似树的数据结构，被证明对于解决与字符串有关的问题非常有效。它提供了快速的检索功能，主要用于在字典中搜索单词，在搜索引擎中提供自动建议，甚至用于IP路由。下面说明了如何在字典树中存储“top”、“thus”和“their”这三个词：（图略）单词以从上到下的方式存储，其中绿色节点“p”、“s”和“r”分别表示“top”、“thus”和“their”的结尾。中

文课文讲解CommonlyaskedTrieinterviewquestions:●CounttotalnumberofwordsinTrie.●PrintallwordsstoredinTrie.●SortelementsofanarrayusingTrie.●FormwordsfromadictionaryusingTrie.●BuildaT9dictionary.英

文字典树面试常见问题：●计算字典树中的单词总数。●打印所有存储在字典树中的单词。●使用字典树对数组的元素进行排序。●使用字典树从字典中形成单词。●构建T9词典。中

文课文讲解8.HashTableHashingisaprocessusedtouniquelyidentifyobjectsandstoreeachobjectatsomepre-calculateduniqueindexcalledits