东华理工大学2018年《811数据结构》考研专业课真题试卷

811数据结构考研题库数据结构是计算机科学领域的核心课程之一，对于考研学生来说，掌握数据结构的基本概念、原理和算法是至关重要的。

以下是一份针对数据结构的考研题库，旨在帮助学生复习和准备考试。

一、选择题1. 在数据结构中，线性结构的特点是什么？A. 元素之间存在一对一的关系B. 元素之间存在一对多的关系C. 元素之间存在多对多的关系D. 元素之间存在一对一或多对多的关系2. 栈（Stack）是一种特殊的线性表，其特点是：A. 只能在一端进行插入和删除操作B. 可以在两端进行插入和删除操作C. 只能在一端进行插入操作，另一端进行删除操作D. 可以在任意位置进行插入和删除操作3. 哈希表（Hash Table）解决冲突的方法不包括：A. 开放定址法B. 链地址法C. 线性探测法D. 二分查找法二、简答题1. 请简述链表与数组在存储结构上的主要区别。

2. 什么是二叉树的遍历？请列举出前序遍历、中序遍历和后序遍历的过程。

三、计算题1. 给定一个无向图，包含5个顶点和6条边，请计算其最小生成树的总权重，并给出生成树的边。

2. 假设有一个长度为n的有序数组，请计算使用二分查找法找到特定元素的时间复杂度。

四、编程题1. 编写一个函数，实现单链表的反转，并说明时间复杂度。

2. 给定一个二叉树的前序遍历序列和中序遍历序列，请恢复出这棵二叉树。

五、论述题1. 论述堆排序算法的原理及其时间复杂度，并讨论其在实际应用中的优缺点。

2. 描述图的深度优先搜索（DFS）和广度优先搜索（BFS）算法，并比较它们的不同点。

结束语数据结构的学习不仅仅是为了应对考试，更是为了在实际工作中能够高效地解决问题。

通过不断的练习和思考，可以加深对数据结构的理解和应用能力。

希望这份题库能够帮助你更好地复习和准备考研，祝你取得理想的成绩。

注意：答案请做在答题纸上，做在试卷上无效
第 1 页，共 2 页 东华理工大学2016年硕士生入学考试初试试题
科目代码： 811 ; 科目名称：《数据结构（含C 程序设计）》；（A 卷） 适用专业（领域）名称：077500、081200计算机科学与技术
一、编写程序题：（共5小题，每小题12分，共60分）
1. 某百货公司进行促销活动，对于购物价格x≥5000元的8折，5000>x≥3000元的
8.5折，3000>x≥1000的9折，否则没有折扣。

编写函数，计算对购物x 元的折后价。

2. 计算1+(1×2)+(1×2×3)+…+(1×2×3×…×n)。

3. 已知一个班1门课的成绩，计算高于平均分的学生人数所占的百分数。

4. 输入一行字符，统计出26个大小写英文字母的个数。

5. 从键盘输入一串字符，除了空格，逐个把这些字符写入磁盘文件中，直到用户输入一个‘@’为止。

二、综合过程题：（共9小题，每小题10分，共90分）
1.设结点的类型如下：
typedef struct node
{ char data;
struct node *next;
}linklist;
编写建立带头结点的单链表的函数,结点值从键盘输入，当输入为‘#’时结束。

2.已知顺序栈的结构定义如下，编写出栈的函数。

typedef struct
{ int d[100];
int top;
}sqstack;
3.已知二叉树如下图，写出其前、中、后续的遍历结果。

东华理工大学2018年硕士生入学考试初试试题科目代码： 812 ; 科目名称：《分析化学（含仪器分析》；（ A 卷）适用专业（领域）名称： 070300化学一、选择题：（共13小题，每小题2分，共30分）1. 以EDTA滴定法测定石灰石中CaO[M r(CaO)=56.08]含量, 采用 0.02 mol/LEDTA 滴定, 设试样中含CaO约50 % , 试样溶解后定容至250 mL, 移取25 mL进行滴定, 则试样称取量宜为-------------------------------------------------------------------------------( )(A) 0.1 g 左右(B) 0.2 g ~ 0.4 g (C) 0.4 g ~ 0.8 g (D) 1.2 g ~ 2.4 g2. 微溶化合物A2B3在溶液中的解离平衡是: A2B3==2A + 3B。

今已测得B的浓度为3.0×10-3mol/L,则该微溶化合物的溶度积K sp是------------------------------------------( )(A) 1.1×10-13 (B) 2.4×10-13 (C) 1.0×10-14 (D) 2.6×10-113. 以下银量法测定需采用返滴定方式的是--------------------------------------------------( )(A)莫尔法测Cl-(B)吸附指示剂法测Cl-(C)佛尔哈德法测Cl-(D)AgNO3滴定CN-(生成Ag[Ag(CN)2]指示终点4. 气液色谱中，保留值实际上反映的是下列哪两者间的相互作用---------------------( )(A)组分和载气(B)载气和载体(C)组分和固定液(D)组分和载体5. 测定铁矿中 Fe 的质量分数, 求得置信度为 95％时平均值的置信区间为35.21%±0.10%。

2022年东华理工大学计算机科学与技术专业《数据结构与算法》科目期末试卷A（有答案）一、选择题1、n个结点的完全有向图含有边的数目（）。

A.n*nB.n(n+1)C.n/2D.n*(n-1)2、下列说法不正确的是（）。

A.图的遍历是从给定的源点出发每个顶点仅被访问一次B.遍历的基本方法有两种：深度遍历和广度遍历C.图的深度遍历不适用于有向图D.图的深度遍历是一个递归过程3、若线性表最常用的操作是存取第i个元素及其前驱和后继元素的值，为节省时间应采用的存储方式（）。

A.单链表B.双向链表C.单循环链表D.顺序表4、动态存储管理系统中，通常可有（）种不同的分配策略。

A.1B.2C.3D.45、有六个元素6，5，4，3，2，1顺序入栈，下列不是合法的出栈序列的是（）。

A.543612B.453126C.346521D.2341566、下列关于无向连通图特性的叙述中，正确的是（）。

Ⅰ．所有的顶点的度之和为偶数Ⅱ．边数大于顶点个数减1 Ⅲ．至少有一个顶点的度为1 A．只有Ⅰ B．只有Ⅱ C．Ⅰ和Ⅱ D．Ⅰ和Ⅲ7、循环队列放在一维数组A中，end1指向队头元素，end2指向队尾元素的后一个位置。

假设队列两端均可进行入队和出队操作，队列中最多能容纳M－1个元素。

初始时为空，下列判断队空和队满的条件中，正确的是（）。

A．队空：end1＝＝end2；队满：end1＝＝（end2＋1）mod MB．队空：end1＝＝end2；队满：end2＝＝（end1＋1）mod （M－1）C．队空：end2＝＝（end1＋1）mod M；队满：end1＝＝（end2＋1） mod MD．队空：end1＝＝（end2＋1）mod M；队满：end2＝＝（end1＋1） mod （M－1）8、在下述结论中，正确的有（）。

①只有一个结点的二叉树的度为0。

②二叉树的度为2。

③二叉树的左右子树可任意交换。

④深度为K的完全二叉树的结点个数小于或等于深度相同的满二叉树。

注意：答案请做在答题纸上，做在试卷上无效
第 1 页，共 2 页 东华理工大学2016年硕士生入学考试初试试题
科目代码： 811 ; 科目名称：《数据结构（含C 程序设计）》；（A 卷） 适用专业（领域）名称：077500、081200计算机科学与技术
一、编写程序题：（共5小题，每小题12分，共60分）
1. 某百货公司进行促销活动，对于购物价格x≥5000元的8折，5000>x≥3000元的
8.5折，3000>x≥1000的9折，否则没有折扣。

编写函数，计算对购物x 元的折后价。

2. 计算1+(1×2)+(1×2×3)+…+(1×2×3×…×n)。

3. 已知一个班1门课的成绩，计算高于平均分的学生人数所占的百分数。

4. 输入一行字符，统计出26个大小写英文字母的个数。

5. 从键盘输入一串字符，除了空格，逐个把这些字符写入磁盘文件中，直到用户输入一个‘@’为止。

二、综合过程题：（共9小题，每小题10分，共90分）
1.设结点的类型如下：
typedef struct node
{ char data;
struct node *next;
}linklist;
编写建立带头结点的单链表的函数,结点值从键盘输入，当输入为‘#’时结束。

2.已知顺序栈的结构定义如下，编写出栈的函数。

typedef struct
{ int d[100];
int top;
}sqstack;
3.已知二叉树如下图，写出其前、中、后续的遍历结果。

东华理工大学2018年硕士生入学考试初试试题科目代码： 840 ; 科目名称：《综合英语》；（ A 卷）适用专业（领域）名称：学科教学（英语）Part I Reading Comprehension (50%，2.5*20)In this section there are four passages followed by questions or unfinished statements, each with four suggested answers marked A, B, C and D. Choose the one that you think is the best answer.Text AThe bag is one of the most simple and useful things in the world. It is a container made of paper or cloth. It has given the world many strange expressions that are not very simple. Some of them are used in the United States today.One is “bagman”. It describes a go-between. The go-between sees to it that money is passed — often illegally — from one person to another. Another widely-used expression is to “let the cat out of the bag”. It is used when someone tells something that was supposed to be secret. No one can explain how the cat got into the bag. But there is an old story about it.Long ago tradesmen sold things in large cloth bags. One day a woman asked for a pig. The tradesman held up a cloth bag with something moving inside it. He said it was a live pig. The woman asked to see it. When the dishonest tradesman opened the bag, out jumped a cat — not a pig. The tradesman’s secret was out. He was trying to trick her. And now everybody knew it.The phrase “to be left holding the bag” is as widely used as the expression “to let the cat out of the bag”. This expression makes the person left holding the bag responsible for an action, often a crime or misdeed. That person is the one who is punished. The others involved in the act escape. Where the expression came from is not clear. Some say that General George Washington used it during the American Revolutionary War. One of Washington’s officers, Royall Taylor, used the expression in a play about Daniel Shay’s rebellion. The play was in 1787, after Taylor helped to put down Shay’s rebellion.Shay led a thousand war veterans in an attack on a federal building in Springfield, Massachusetts. Guns were in the building. Some of the protesters were farmers who had no money to buy seed. Some had been put in prison for not paying their debts. They were menwho fought one war against the king of England, and were now prepared to fight against their own government. Most of the rebels were captured. Shay and some of the officers escaped.In his play, Taylor describes Shay as disappearing, giving others “the bag to hold”.A bag is useful in many ways. Just be careful not “to let the cat out of the bag”, or someone may leave you “holding the bag”.1. According to the passage, a bagman refers to _________________.A) a person who travels around carrying his things in a bag B) a vagrant workerC) a person who delivers or collects money for criminals D) a homeless person2. Which of the following is TRUE concerning the story about “let the cat out of the bag”?A) The tradesman wanted to play a joke with the woman.B) The woman wanted to buy a cat.C) The tradesman kept a cat in a plastic bag.D) The tradesman lied to the woman that he had a live pig in the bag.3. What can we infer from the story “to be left holding the bag”?A) The person left holding the bag was completely innocent.B) The person left holding the bag took no responsibility for committing crimes.C) Many farmers protested against the government because they couldn’t pay their debts.D) Many protesters became the scapegoats for Shay and his officers.4. What does the last sentence of this passage mean?A) A bag has many different functions.B) People should often keep secret or they will be left to take the responsibility for everything.C) People should watch out and learn to take the responsibility for their actions.D) You will have to hold the bag if you let the cat out of it.5. The best title for this passage is ________________.A) Don’t Let the Cat Out of the Bag B) To Be Left Holding a BagC) Words and Their Stories: Bag Expressions D) Bag: A Useful ContainerText BTraditional plant breeding involves crossing varieties of the same species in ways they could cross naturally．For example，disease-resistant varieties of wheat have been crossed with high-yield wheat to combine these properties．This type of natural gene exchange is safe and fairly predictable．Genetic engineering（GE）involves exchanging genes between unrelated species that cannot naturally exchange genes with each other．GE can involve the exchange of genes between vastly different species—e.g. putting scorpion toxin genes into maize or fish antifreeze genes into tomatoes．It is possible that a scorpion toxin gene，even when it is in maize DNA，will still get the organism to produce scorpion toxin, but what other effects may it have in this alien environment？We are already seeing this problem—adding human growth hormone genes to pigs certainly makes them grow—but it also gives them arthritis and makes them cross-eyed，which was entirely unpredictable．It will be obvious，for example，that the gene for human intelligence will not have the same effect if inserted into cabbage DNA as it had in human DNA, but what side-effect would it have？In other words，is GM food safe to eat？The answer is that nobody knows because long-term tests have not been carried out．Companies wanting a GM product approved in the UK or U.S. are required to provide regulatory bodies with results of their own safety tests．Monsanto’s soya beans were apparently fed to fish for ten weeks before being approved．There was no requirement for independent testing，for long-term testing，for testing on humans or testing for specific dangers to children or allergic people．The current position of the UK Government is that “There is no evidence of long-term dangers from GM foods.” In the U.S.，the American Food and Drug Administration (AFDA) is currently being prosecuted for covering up research that suggested possible risks from GM foods．6. Genetic engineering .A) involves crossing varieties of the same speciesB) is safe and fairly predictableC) is dangerous and entirely unpredictableD) covers the exchange of genes between different species7. According to the passage, which of the following statements is NOT true?A) The side-effect of adding human growth hormone to pigs is that pigs may acquire somediseases of human.B) Human intelligence gene functions differently in human DNA and in cabbage DNA.C) In the UK or U.S., a GM product cannot be approved before the results of its safetytests are provided.D) Tests show that GM foods have specific dangers to children or allergic people.8. What can we infer from the last paragraph?A) There is no evidence of long-term dangers from GM foods.B) The UK government and the U.S. government have different attitudes towards GMfoods.C) The AFDA in the U.S. was charged with concealing some research findings.D) The governments of the UK and the U.S. are protecting the GM foods.9. The possible title for the passage might be .A) Safe to Eat? B) GM Food NeedsC) Genetic Engineering D) A New Way of Breeding10. What’s the writer’s attitude towards GM food?A) Neutral. B) Positive. C) Negative. D) Indifferent. Text CFaces, like fingerprints, are unique. Did you ever wonder how it is possible for us to recognize people? Even a skilled writer probably could not describe all the features that make one face different from another. Yet a very young child－or even an animal, such as a pigeon－can learn to recognize faces. We all take this ability for granted.We also tell people apart by how they behave. When we talk about someone’s personality, we mean the ways in which he or she acts, speaks, thinks and feels that make that individual different from others.Like the human face, human personality is very complex. But describing someone’s personality in words is somewhat easier than describing his face. If you were asked to describe what a “nice face” looked like, you probably would have a difficult time doing so.But if you were asked to describe a “nice person,” you might begin to think about someone who was kind, considerate, friendly, warm, and so forth.There are many words to describe how a person thinks, feels and acts. Gordon Allport, an American psychologist, found nearly 18,000 English words characterizing differences in people’s behavior. And many of us use this information as a basis for describing, or typing, his personality. Bookworms, conservatives, military types---- people are described with such terms.People have always tried to “type” each other. Actors in early Greek drama wore masks to show the audience whether they played the villain’s or the hero’s role. In fact, the words “person” and “personality” come from the Latin persona, meaning “mask”. Today, most television and movie actors do not wear masks. But we can easily tell the “good guys” from the “bad guys” because the two types differ in appearance as well as in actions.11. The main idea of this passage is ____________.A) how to distinguish people’s facesB）how to describe people’s personalityC) how to distinguish people both inward and outwardD) how to differ good persons from bad persons12. The author is most probably a _________.A) behaviorist B) psychologist C) sociologist D) scientist13. Which of the following is NOT true?A) Different people may have different personalities.B) People differ from each other in appearance.C) People can learn to recognize faces.D) People can describe all the features of others.14. The reason why it is easier to describe a person’s personality in words than his face is that________.A) a person’s face is more complex than his personalityB) a person’s personality is easily distinguishedC) a person’s personality is very complexD) many words are available when people try to describe one’s personality15. W e learn from the passage that people classify a person into a certain type according to________.A) his way of acting and thinking B) his way of speaking and behavingC) his learning and behavior D)his physical appearance and hispersonalityText DIt is often helpful when thinking about biological processes to consider some apparently similar yet better understood non-biological process. In the case of visual perception an obvious choice would be colour photography. Since in many respects eyes resemble cameras, and percepts photographs, is it not reasonable to assume that perception is a sort of photographic process whereby samples of the external world become spontaneously and accurately reproduced somewhere inside our heads? Unfortunately, the answer must be no. The best that can be said of the photographic analogy is that it points up what perception is not. Beyond this it is superficial and misleading. Four simple experiments should make the matter plain.In the first a person is asked to match a pair of black and white discs, which are rotating at such a speed as to make them appear uniformly grey. One disc is standing in shadow, the other in bright illumination. By adjusting the ratio of black to white in one of the discs the subject tries to make it look the same as the other. The results show him to be remarkably accurate, for it seems he has made the proportion of black to white in the brightly illuminated disc almost identical with that in the disc which stood in shadow. But there is nothing photographic about his perception, for when the matched discs, still spinning, are photographed, the resulting print shows them to be quite dissimilar in appearance. The disc in shadow is obviously very much darker than the other one. What has happened? Both the camera and the person were accurate, but their criteria differed. One might say that the camera recorded things as they look, and the person things as they are. But the situation is manifestly more complex than this, for the person also recorded things as they look. He did better than the camera because he made them look as they really are. He was not misled by the differences in illumination. He showed perceptual constancy. By reason of an extremely rapid, wholly unconscious piece of computation he received a more accurate record of theexternal world than could the camera.In the second experiment a person is asked to match with a colour card the colours of two pictures in dim illumination. One is of a leaf, the other of a donkey. Both are coloured an equal shade of green. In making his match he chooses a much stronger green for the leaf than for the donkey. The leaf evidently looks greener than the donkey. The percipient makes a perceptual world compatible with his own experience. It hardly needs saying that cameras lack this versatility.In the third experiment hungry, thirsty and satiated people are asked to equalize the brightness of pictures depicting food, water and other objects unrelated to hunger or thirst. When the intensities at which they set the pictures are measured it is found that hungry people see pictures relating to food as brighter than the rest (i.e. to equalize the pictures they make the food ones less intense), and thirsty people do likewise with “drink” pictures. For the satiated group no differences are obtained between the different objects. In other words, perception serves to satisfy needs, not to enrich subjective experience. Unlike a photograph the percept is determined by more than just the stimulus.The fourth experiment is of a rather different kind. With ears plugged, their eyes beneath translucent goggles and their bodies either encased in cotton wool, or floating naked in water at body temperature, people are deprived for considerable periods of external stimulation. Contrary to what one might expect, however, such circumstances result not in a lack of perceptual experience but rather a surprising change in what is perceived. The subjects in such an experiment begin to see, feel and hear things which bear no more relationship to the immediate external world than does a dream in someone who is asleep. These people are not asleep yet their hallucinations, or so-called ‘autistic’ perceptions, may be as vivid, if not more so, than any normal percept.16. In the first paragraph, the author suggests that _______.A. colour photography is a biological processB. vision is rather like colour photographyC. vision is a sort of photographic processD. vision and colour photography are very different17. In the first experiment, it is proved that a person _______.A. makes mistakes of perception and is less accurate than a cameraB. can see more clearly than a cameraC. is more sensitive to changes in light than a cameraD. sees colours as they are in spite of changes in the light18. The second experiment shows that ________.A. people see colours according to their ideas of how things should lookB. colours look different in a dim lightC. cameras work less efficiently in a dim lightD. colours are less intense in larger objects19. What does “to equalize the brightness” (Line 1, Para. 4) mean?A. To arrange the pictures so that the equally bright ones are together.B. To change the lighting so that the pictures look equally bright.C. To describe the brightness.D. To move the pictures nearer or further away.20. The group of experiments, taken together, proves that human perception is _______.A. unreliableB. mysterious and unpredictableC. less accurate than a cameraD. related to our knowledge, experience and needsPart II Translation ( 50 Points)Section A :For this part, you are allowed 30 minutes to translate a passage from Chinese into English.（30%）1812年春，拿破仑在俄国边境屯兵60万。