2011年暨南大学830数据结构考研试题

数据结构暨南大学期末试卷试题一、判断题(共10分)1. 当静态链表采用数组实现时，插入与删除操作仍需移动元素。

2. 栈也是一种线性表，也同样有顺序存储结构和链式存储结构。

3. 二叉树的三种遍历算法区别仅在于对树根、左右子树访问先后顺序的不同。

4. 邻接表是图的一种顺序存储结构。

5. 二叉树就是度数为2的树。

6. 在哈希表中勿需比较就可找到记录在表中的位置。

7. 线性表的链式存储结构既方便其存取操作，也方便其插入与删除操作。

8. 顺序存储结构既适合于完全二叉树，也同样适合于一般的二叉树。

9.一个算法是正确的、高效率的，还不能说它就是一个“好”的算法。

10. 快速排序与堆排序的平均时间复杂度相同。

二、概念填空(共20分，每题2分)1.对顺序存储结构的线性表，设表长为La;在各元素插入为等概率条件下，插入一个数据元素需平均移动表中元素_______ 个;在最坏情况下需移动表中元素_______ 个。

2.从逻辑角度看，四种基本的数据结构可分为__________、___________、____________和____________;两种存储结构为_____________和_________________。

3.一个深度为,的满k(k>2)叉树，其第i层(若存在)有________个结点;编号为p(p>1)的结点其父结点(父结点为非根结点)编号是___________________。

4.具有n个结点的完全二叉树的深度为____________;编号为p(<n)的结点其右孩子(若存在)结点编号是___________。

5.堆栈被称为一个_____________的线性表;队列被称为一个_____________的线性表。

6.静态查找表的查找方法主要有:有序表查找及________________________;在n个记录中进行折半查找，当查找不成功时，与关键字比较次数最多为_____________________。

计算机专业基础综合数据结构（排序）历年真题试卷汇编5(总分：66.00，做题时间：90分钟)一、单项选择题(总题数：15，分数：30.00)1.已知关键字序列5，8，12，19，28，20，15，22是小根堆(最小堆)，插入关键字3，调整后得到的小根堆是( )。

【2009年全国试题9(2分)】A.3，5，12，8，28，20，15，22，19 √B.3，5，12，19，20，1 5，22，8，28C.3，8，12，5，20，15，22，28，19D.3，12，5，8，28，20，1 5，22，19首先按所给关键字序列画出完全二叉树，关键字3插入结点22的后边。

沿结点3到根的路径调整堆，直到满足堆的定义为止。

2.若数据元素序列11，12，13，7，8，9，23，4，5是采用下列排序方法之一得到的第二趟排序后的结果，则该排序算法只能是( )。

【2009年全国试题10(2分)】A.起泡排序B.插入排序√C.选择排序D.二路归并排序起泡排序的特点是待排序元素相邻两两比较，逆序交换，每趟有一个最大元素到达底部(或一个最小元素到达顶部)；插入排序的特点是先假定第一个元素有序，从第二个元素起，每趟将未排序元素的第一个元素插入的前面有序子文件中；选择排序的特点是第一趟在待排序元素中选最小(或最大)元素和第一个元素交换，第二趟在未排序元素中选次小(或次大)和第二个元素交换；二路归并排序是两两归并，再四四归并，等等。

3.采用递归方式对顺序表进行快速排序。

下列关于递归次数的叙述中，正确的是( )。

【2010年全国试题10(2分)】A.递归次数与初始数据的排列次序无关B.每次划分后，先处理较长的分区可以减少递归次数C.每次划分后，先处理较短的分区可以减少递归次数D.递归次数与每次划分后得到的分区的处理顺序无关√快速排序和数据的初始排列次序相关。

每次划分后，先处理较短分区可以减少递归深度，递归次数和先处理哪个分区无关。

4.对一组数据(2，12，1 6，88，5，10)进行排序，若前三趟排序结果如下：第一趟排序结果：2，12，16，5，10，88 第二趟排序结果：2，12，5，10，16，88 第三趟排序结果：2，5，10，12，16，88则采用的排序方法可能是( )。

2011 年考研计算机学科专业基础综合一．选择题1．设n是描述问题规模的非负整数，下面程序片段的时间复杂度是x = 2;while ( x < n/2 )x = 2*x;A．O(log2n) B．O(n) C．O(n log2n) D．O(n2)2．元素a, b, c, d, e依次进入初始为空的栈中，若元素进栈后可停留、可出栈，直到所有元素都出栈，则在所有可能的出栈序列中，以元素d开头的序列个数是A．3 B．4 C．5 D．63．已知循环队列存储在一维数组A[0..n-1] 中，且队列非空时front和rear 分别指向队头元素和队尾元素。

若初始时队列为空，且要求第1个进入队列的元素存储在A[0]处，则初始时front和rear 的值分别是A．0, 0 B．0, n-1 C．n-1, 0 D．n-1, n-14．若一棵完全二叉树有768个结点，则该二叉树中叶结点的个数是A．257 B．258 C．384 D．3855．若一棵二叉树的前序遍历序列和后序遍历序列分别为1, 2, 3, 4和4, 3, 2, 1，则该二叉树的中序遍历序列不．会是A．1, 2, 3, 4 B．2, 3, 4, 1 C．3, 2, 4, 1 D．4, 3, 2, 16．已知一棵有2011 个结点的树，其叶结点个数为116，该树对应的二叉树中无右孩子的结点个数是A．115 B．116 C．1895 D．18967．对于下列关键字序列，不．可能构成某二叉排序树中一条查找路径的序列是A．95, 22, 91, 24, 94, 71 B．92, 20, 91, 34, 88, 35C．21, 89, 77, 29, 36, 38 D．12, 25, 71, 68, 33, 348．下列关于图的叙述中，正确的是I．回路是简单路径II．存储稀疏图，用邻接矩阵比邻接表更省空间III．若有向图中存在拓扑序列，则该图不存在回路A．仅II B．仅I、II C．仅III D．仅I、III9．为提高散列（Hash）表的查找效率，可以采取的正确措施是I．增大装填（载）因子II．设计冲突（碰撞）少的散列函数III．处理冲突（碰撞）时避免产生聚集（堆积）现象您所下载的资料来源于 考研资料下载中心获取更多考研资料，请访问A．仅I B．仅II C．仅I、II D．仅II、III10．为实现快速排序算法，待排序序列宜采用的存储方式是A．顺序存储B．散列存储C．链式存储D．索引存储11．已知序列25, 13, 10, 12, 9是大根堆，在序列尾部插入新元素18，将其再调整为大根堆，调整过程中元素之间进行的比较次数是A．1 B．2 C．4 D．512．下列选项中，描述浮点数操作速度指标的是A．MIPS B．CPI C．IPC D．MFLOPS13．float型数据通常用IEEE 754单精度浮点数格式表示。

2023年招收攻读硕士学位研究生入学考试试题A卷******************************************************************************************** 招生专业与代码：网络空间安全考试科目名称及代码：数据结构830考生注意：所有答案必须写在答题纸（卷）上，写在本试题上一律不给分。

一、单项选择题(每题2分，共20分)1. 以下数据结构中, ( )是非线性数据结构A．字符串B．树C．队列D．栈2. 请选择下面程序段的时间复杂度( )i = 1;while (i <= n)i = i * 3;A. O（n）B. O（log3 n）C. O（n2）D. O（i * n）3. 顺序表中第一个元素的存储地址为120，每个元素的长度为5，则第4个元素的地址为( )A. 135B. 140C. 130D. 1454. 在单链表中，要将L所指节点插入到M所指节点之后，其语句应为( )A. L->next = M+1; M->next = L;B. (*M).next = L; (*L).next = (*M).next;C. L->next = M->next; M->next = L->next;D. L->next = M->next; M->next = L;5. 若让元素1，2，3，4，7依次进栈，则出栈顺序不可能为( )A. 7, 4, 3, 2, 1B. 4, 3, 1, 2, 7C. 2, 1, 7, 4, 3D. 2, 3, 7, 4, 16. 假设栈S与队列Q的初始状态为空，元素e1、e2、e3、e4、e5和e6依次进入栈S，一个元素出栈后即进入Q，若6个元素出队的序列是e2、e4、e3、e6、e5和e1，则栈S 的容量至少为( )A．2 B. 4 C. 3. D.67. 假设以行序列为主序存储二维数组A = array[1..100,1..100]，设每个数据元素占2个存储单元，基地址为10，则LOC[5, 5] = ( )A．808 B．1010 C．818 D．10208. 由3个不同结点可计算出多少种不同的二叉树？( )A. 3B. 4C. 5D. 69. 广度优先遍历类似于二叉树的( )A. 先序遍历B. 中序遍历C. 层次遍历D. 后序遍历10. 设哈希表长为14，哈希函数是H(key)=key%11，表中已有数据的关键字为15，38，61，84共四个，现要将关键字为49的元素加到表中，用二次探测法解决冲突，则放入的位置是( )A．8 B．3 C．5 D．9考试科目：数据结构共 3 页，第 1 页二．填空题(每空2分，共20分)1.设一组初始记录关键字序列为(20，12，42，31，18，14，28)，则根据这些记录关键字构造的二叉排序树的平均查找长度是__________。

2011年广东暨南大学外国语言文学综合考研真题学科、专业名称：英语语言文学、外国语言学及应用语言学研究方向：各方向考试科目名称：外国语言文学综合考试考试科目代码：808考生注意：所有答案必须写在答题纸（卷）上，写在本试题上一律不给分。

Ⅰ.Multiple choices.There are20questions in this part.Choose the best answer to each question.Write your answers on the ANSWER SHEET.Both literature candidates and linguistics candidates must do this part.（20%）1.The first American President to be elected from the Republican Party was_______.A.Abraham LincolnB.James MonroeC.James MadisonD.Thomas Jefferson2.The most important and largest river in the United States of America is_________.A.the Ohio RiverB.the Colorado RiverC.the Missouri RiverD.the Mississippi River3.______________has been called the"cradle of American liberty".A.PhiladelphiaB.BostonC.PlymouthD.Chicago4.Junior college in America is_______________.A.two-year collegeB.four-year collegeC.three-year collegeD.five-year college5.President Nixon decided to resign because he__________________.A.refused to hand over the White House tapes to courtB.was tired of political struggle in Washington D.C.C.came to sec that most probably he would be impeachedD.was deserted by the Republican Party6.To its full sense,the British Parliament consists of_______________.A.the House of Lords and the House of CommonsB.the House and the SenateC.the Queen and the House of LordsD.the Sovereign,the House of Lords and the House of Commons7.Which of the following is true under Thatcher's administration in the UK?A.The proportion of owner-occupation decreased.B.Public housing became more important.C.Many Public houses were sold to people.D.The UK became more European-like in its housing arrangement.8.The oldest British daily newspaper is______________.A.Daily ExpressB.The TimesC.Financial TimesD.The Observer9.In appearance the Queen of Great Britain seems very powerful,but in reality,she is only______________.A.the Supreme Governor of EnglandB.the Duke of EdinburghC.a figure-headD.all of the above10.Britain joined the European Community in_________________.A.1972B.1973C.1974D.197511.In Industrial Revolution,George Stephenson invented________________.A.railway engineB.spinning machineC.steam engineD.cotton textile12.London's Metropolitan Police Force is directly under the control of__________.A.the Lord ChancellorB.the Home SecretaryC.the AttorneyD.the Prime Minister13.Ireland has a bipolar political system with two major parties.They are_________.A.Sinn Fein and Fianna FailB.Sinn Fein and Fine GaelC.Fianna Fail and Fine GaelD.IRA and Sinn Fein14.________________is the oldest of all the parties in Ireland.A.The Irish Labour PartyB.The Progressive DemocratsC.Finna FailD.Fine Gael15.In______________James Joyce introduced the stream of consciousness techniqueas a remarkable means of character portrayal.A.DublinersB.UlyssesC.A Portrait of the Artist as a Young ManD.Paradise and Hell16.By_____________,Upper Canada and Lower Canada were created.A.Canada Act of1791B.Quebec Act of1774C.British North America ActD.Act of Paris of176317.The_______are the indigenous people of New Zealand,and have a rich and variedculture.A.MaoriB.CherokeeC.People from IndiaD.People from Southeast Asia18._____________is Australia's largest and most diverse industry.A.MiningB.ManufacturingC.FishingD.Agriculture19.New Zealand became a separate colony of Britain in________________.A.1841B.1857C.1907D.193120.Who produced the first complete map of New Zealand in1769?A.Abel Tasman.B.A Dutchman.C.HobsonD.James Cook.II.Fill in the blanks with proper answers.Write your answers on the ANSWER SHEET. Both literature candidates and linguistics candidates must do this part.(20%) 1._________features are the phonemic features that occur above the level of thesegments.They include stress,tone,intonation,etc.2.English consonants can be classified in terms of_____________of articulationorin terms of place of articulation.3.The affix“-ish”in the word boyish conveys a_____________meaning.4.___________morphemes are those that cannot be used independently but have tobe combined with other morphemes to form a word.5.In the complex sentence，the incorporated or subordinate clause is normallycalled an_____________clause.6.A______________is a structurally independent unit that usually comprises anumber of words to form a complete statement，question or command.7.______________can be defined as the study of meaning.8.When two words are identical in sound，but different in spelling and meaning，they are called________________.9.The notion of______________is essential to the pragmatic study of language.10.There are four maxims under the________________principle：the maxim ofquantity，the maxim of quality，the maxim of relation and the maxim of manner.11.Lord_______________(1561-1626),the world-renowned British essayist,foundso much leisure for study as to make himself a great philosopher,a good historian and an elegant writer.His concise essay“Of Studies”thoroughly illustrates the functions and significance of study.12.“I Have Nothing to Offer but Blood,Tears,and Sweat”is a speech given bythe British Prime Minister________________,who is a Nobel Prize winner for literature and a prolific and well-respected painter as well.13.James Joyce(1882-1941),the Irish novelist,is noted for his experimental useof language in such works as____________(1922)and Finnegans Wake(1939).14.In the_______________point of view,the narrator appears to know everythingabout all the characters,including what they are thinking.It takes no actions, casts no judgments,expresses no opinions and has no physical form in or out of the story.15._______________writers introduced a new theme into literature:the struggleof the proletariat for its rights.They portrayed the world as it was seen by the poor,the down trodden.16.An_______________story is a story whose overall plot is concerned with puttingthe protagonist through a particular sort of experience.The idea is that the character is forced,by what he/she encounters in the course of the action,to become"a different person,"usually someone more complicated,more comprehensive,with wider views.17.The story of“The Celebrated Jumping Frog of Calaveras County”can be viewedas an epitome of the late______________century American society and culture.18.Edgar Allan Poe was considered part of the American____________________Movement.Best known for his tales of mystery and the macabre,Poe was one of the earliest American practitioners of the short story and is considered theinventor of the detective fiction genre.He is further credited with contributing to the emerging genre of science fiction.19.With the publication of The Sun Also Rises,three years later,Hemingway becamethe spokesman for what Gertrude Stein called______________.20.“I felt a funeral,in my Brain,/And Mourners to and fro/Kept treading–treading–till it seemed/That Sense was breaking through–“The poet who writes these lines is_______________.III.Write your answers on the ANSWER SHEET according to requirements.Both literature candidates and linguistics candidates must do this part.(10%) Section A:Decide whether each of the following statements is True or False.If it is true,write T on the ANSWER SHEET.If it is false,Write F on the ANSWER SHEET.1.D-structure is formed by the XP rule in accordance with the head’ssubcategorization properties.2.An illocutionary act is the act performed by or resulting from saying something;it is the consequence of the utterance.3.Phonology is the study of the speech sounds and their functions.4.Diglossia refers to the dialect having to do with separation brought about bydifferent social conditions.ponential analysis is a way proposed by the structural semantics to analyzelexical/word meaning.Section B:Identify the author and indicate the genre of each of the following works.6.Dream Children7.The Raven8.The Death of the Salesman9.Shall I compare thee to a Summers day?10.Vanity FairIV.Choose SIX terms from the following and explain them briefly.Write your answers on the ANSWER SHEET.(30%)1.stream of consciousness2.The Aesthetic Movement3.Iceberg Theory4.Naturalism5.Theatre of the Absurd6.Predication analysis7.Neurolinguisticsnguage Acquisition Device(LAD)9.Idiolect10.Draw a tree diagram for the surface structure of“The girl bought the book”.V.Answer the following questions.According to different majors,choose the ones you must do.Write your answers on the ANSWER SHEET.(40%)Section A：for linguistics candidates only1.What is Language acquisition in modern linguistics?2.How do you understand Sapir-Whorf hypothesis?3.Explain the term sense and reference by using examples.4.State clearly the term“complementary distribution”in phonemics.Section B:for literature candidates only1.In the short story“A Rose for Emily”,what does the“rose”in the title symbolize?2.What are the main features of Metaphysical poetry?3.Why is Mark Twain acclaimed as“the Father of American National Literature”?4.What is/are the theme(s)of Jonathan Swift’s Gulliver’s Travels?VI.Choose ONE of the following and write your response to it.Write your answer on the ANSWER SHEET.(30%)1.In what basic ways does modern linguistics differ from traditional grammar?2.Analyze the following poem as to its theme,poetic form,and rhetorical devices,and develop it into an essay of200words.LondonWilliam Blake(1757-1827)I wander thro’each charter’d street,Near where the charter’d Thames does flow,And mark in every face I meetMarks of weakness,marks of woe.In every cry of every Man,In every Infant’s cry of fear,In every voice,in every ban,The mind-forg’d manacles I hear.How the Chimney-sweeper’s cryEvery black’ring Church appalls;And hapless Soldier’s sighRuns in blood down Palace walls.But most thro’midnight streets I hearHow the youthful Harlot’s curseBlasts the new born Infant’s fear,And blights with plagues the Marriage hearse.。