一、总体分析
计算机科学与技术学科全国硕士研究生统一入学考试已经进行了两次。数据结构部分的考试范围要求掌握：
1，基本数据结构的知识
2，算法设计和编程的能力
3，综合应用算法和数据结构的技能
从考试的命题来看，2010年比2009年的题目难度要大一些。在这里，我对2009年考题与2010年考题的考试范围进行了简单的比较：
A, 选择题部分，请参考表1
表1
2010年选择题还有一道题（11题）是对几种排序方法的考察。
由表1我们可以总结出，在选择题部分，各主要知识点分布如下，请参考表2：
表2
B ，综合应用题部分的试题范围如下：
总体上讲，2009年的试题较简单，2010年的试题比较复杂，且难度稍大，但平时教学中应当都教过，或练习都做过。
二、2010 年考试改卷的基本情况
2010年考试改卷的大概情况如下：
客观题是机改，数据结构部分总分22分，平均得分约为17分，失分较多的是
第2题（双端队列）
第5题（K叉树叶结点的计算）
第8题（拓扑排序的序列个数）
第10题（快速排序递归次数）；
主观题是人改，数据结构部分总分23分
第41题10分，平均得分5分，失分最多的是
计算散列表长度（2分），多数考生未得分。
将给定元素存储到散列表中（6分），平均得3分。如果第1问错了，不影响第2问得分；但可惜散列函数有不少同学选择不完全对。
计算平均查找长度（2分），平均得1分。
第42题是算法设计题13分，平均得6～8分，失分最多的是算法效率达不到要求。
许多考生成绩差的主要原因：
1，本科数据结构课程学习不够扎实；
2，考前复习不够充分；
3，考试时审题不仔细，急于给出答案，未严格推导。
三、2010年考试试卷分析
由于篇幅有限，在此只例举综合题两道大题进行分析。
二、综合应用题
41题：（10分）将关键字序列{ 7, 8, 30, 11, 18, 9, 14 } 散列存储到散列表中，散列表的存储空间是一个下标从 0 开始的一个一维数组散列，函数为：
H(key) = (key′3) MOD 7
处理冲突采用线性探测再散列法，要求装载因子为 0.7
问题：
(1) 请画出所构造的散列表。
(2) 分别计算等概率情况下，查找成功和查找不成功的平均查找长度。
解答：这是一道常规的数据结构题目。实际上要做三步工作：计算表的长度，从而将 7 个数据存储到散列表中，最后计算等查找概率情形下，查找成功和查找不成功的平均查找长度。
(1) 根据题意，表的装载因子为a = n/m = 0.7，n = 7，因此有m = n/a = 10，即表长度为m = 10。
分别计算各个数据元素的散列地址：
H(7) = (7*3) mod 7 = 0，一次比较到位
H(8) = (8*3) mod 7 = 3，一次比较到位
H(30) = (30*3) mod 7 = 6，一次比较到位
H(11) = (11*3) mod 7 = 5，一次比较到位
H(18) = (18*3) mod 7 = 5，冲突，= 6，冲突，
= 7，三次比较到位
H(9) = (9*3) mod 7 = 6，冲突，= 7，冲突，
= 8，三次比较到位
H(14) = (14*3) mod 7 = 0，冲突，= 1，二次比较到位
根据以上得到的各数据元素的散列地址，可以得到如下散列表：图1
图1
42题：（13分）设将n (n > 1) 个整数存放到一维数组 R中。设计一个在
时间和空间两方面尽可能高效的算法。将 R 中的序列循环左移 p（0 < p < n）个位置，即将 R 中的数据由 (a0, a1, ……an-1) 变换为(ap, ap-1, …an-1, a0, a1, …, ap-1)。要求：
(1) 给出算法的基本设计思想。
(2) 根据设计思想，采用C或C++或JaVa语言描述算法，关键之处给出注释。
(3) 说明你所设计算法的时间复杂度和空间复杂度。
解答：此算法即有名的海豚算法。
解法一（标准答案）
算法基本思路是首先把序列{ a0, a1, ..., ap, …, an-1 }逆转为{an-1, an-2, ..., ap, …,a0 }，再分别逆转{ an-1, an-2, ..., ap }和{ ap-1, ap-2, …,a0 }，最后得到{ ap, ap+1, …, an-1, a0, …, ap-1}。
(1) 逆转算法
void reverse ( int A[ ], int left, int right ) {
int n = right-left+1;
if ( n <= 1 ) return;
if ( n <= 1 ) return;
for ( int i = 0; i < n/2; i++ ) {
int temp = A[i];
A[i] = A[n-i-1];
A[n-i-1] = temp;
}
}
(2) 循环左移算法
void sift_Left ( int a[ ], int n, int p ) {
reverse ( a, 0, n-1 );
reverse ( a, 0, n-p-1 );
reverse ( a, n-p, n-1 );
}
第一个 reverse 函数执行了3n/2次数据移动，使用了一个辅助存储；第二个 reverse 函数执行了3(n-p)/2次数据移动，使用了一个辅助存储；第三个reverse 函数执行了3p/2次数据移动，使用了一个辅助存储；总共执行了3n次数据移动，使用了1个辅助存储。
解法二（利用最大公约数）清华阅卷组给出
如果n与p不互质，一次循环左移只涉及间隔为p
如果n与p不互质，一次循环左移只涉及间隔为p的部分数据元素，可先求n与p的最大公约数m,再做m次循环左移，每次比上次右错一位，从而实现所有数据元素的循环左移。例如，n = 10，p = 4，m = 2，做 2 次循环左移。第1次涉及位置0-4-8-2-6，第2次涉及位置1-5-9-3-7。
(1) 求n与p的最大公约数的算法
int GCD( int n, int p ) {
//函数用辗转相除法计算n与p的最大公约数, 若n
//与p互质, 则函数返回1.
if ( n < p ) { int temp = n; n = p; p = temp; }
int r = n % p;
while ( r != 0 ) { n = p; p = r; r = n % p; }
return p;
}
(2) 循环左移算法
void sift_k ( int a[ ], int n, int p ) {
if ( !p ) return;
int i, j, m, k, temp;
m = GCD(n, p);
for ( k = 0; k < m; k++ ) {
temp = a[k]; i = k; j = (i +p) % n;
while ( j != k ) {
a[i] = a[j]; i = j; j = ( j+p ) % n;
}
a[i] = temp;
}
}
解法三（解法二的改进型）清航考研给出
调用子程序需要花费较多的时间和空间代价，本算法省去了计算最大公约数，仅利用一个控制变量控制循环左移的次数，效果更好。void siftLeft_p ( int a[ ], int n, int p ) {
if ( !p ) return;
int i, j; int temp; int count = 0, k = 0;
while ( count < n ) {
i = k; temp = a[i]; j = (i+p) % n;
while ( j != k ) {
a[i] = a[j]; i = j; j = (i+p) % n;
count++;
}
a[i] = temp; count++;
k++;
}
}
设m为n与p的最大公约数，则最内层while循环执行m次，每次循环执行n/m+1次数据移动，包括与temp的相互传送2次，总的数据移动次数为m*(n/m+1) = n+m。
特别地，当p = n时，m = n，最内层while循环不执行，总的数据移动次数2n，做了n次与temp的传出和传入；当p = 0时，总的数据移动次数为0。算法用了一个附加存储temp。
解法四（被扣了分的算法）
很多考生使用了一个附加数组，先暂存子序列
{ a0, a1, ..., ap }，再把序列中后面的n-p个数据元素前移，得{ ap, …, an-1 }；最后把暂存到临时数组中的子序列拷贝到an-1后面，得到结果： { ap, …, an-1, a0, a1, ..., ap }
由于使用的附加空间较多，相应也扣了一些分。算法移动元素的次数为n+p；特别地，当n = p 时，算法移动元素的次数为2n。
英语中的独立主格结构 独立主格结构是由一个相当于主语的名词或代词加上非谓语动词、形容词、副词或介词短语构成的一种独立主格成分。With( without) 的复合结构可看作是独立主格结构的一种形式。 一、独立主格结构的特点 1）独立主格结构的逻辑主语与句子的主语不同，它独立存在。 2）名词或代词与后面的分词，形容词，副词，不定式，介词等是主谓关系。 3）独立主格结构一般有逗号与主句分开。 The test finished, we began our holiday. = When the test was finished, we began our holiday. 4）当表示人体部位的词做逻辑主语时，及物动词用现在分词，不及物动词用过去分词 二、独立主格结构的构成: 名词普通格或代词主格+ 现在分词/过去分词/不定式/名词/形容词/副词/介词短语。 1．名词（或代词）+ 现在分词 现在分词表示前面的名词或代词主动进行的动作或状态。 He seating himself at the desk, his mother began to tell him a story. Everyone being ready, the teacher began his class. The food being cooked, the boy was watching TV. 注意：现在分词being或having been在独立主格结构中可以省略。 The weather（being）fine, we decided to go on an outing. 独立主格结构中的being在下列两种情况下一般不能省略， 一是在“There being + 名词”结构中，There being no bus, we had to walk home. 二是在逻辑主语是代词的情况下。It being Sunday, all the offices are closed. 2．名词（或代词）+ 不定式（短语）不定式表示将来的动作。 He suggested going for a picnic, Mary to provide the food. Many flowers and grass to be planted, our newly-built school will look even more beautiful. 3．名词（或代词）+ 过去分词 过去分词表示前面的名词或代词被动完成的动作。 The girls lay on her back, her hands crossed under her head. The workers worked still harder, their living conditions greatly improved. He was listening attentively in class, his eyes fixed on the blackboard. 4．名词（或代词）+ 形容词（短语） 形容词（短语）在独立主格结构中说明前面名词或代词的性质、状态 The floor wet, we had to stay outside for a while. He turned to me, his eyes sleepy. 5．名词（或代词）+ 副词 副词在独立主格结构中也多是说明名词或代词的状态。 The meeting over, we all went home. School over, we all went home. 6．名词（或代词）+ 介词短语 A robber burst into the room, knife in hand. He left the office, tears in eyes. 注意：在“逻辑主语+介词短语”构成的独立主格结构里，当介词是in时，其前后的两个名词均不加任何修饰成分。但with 的复合结构不受此限制。例如：The teacher came in, with a book in his hand.
数据结构实验总结报告 一、调试过程中遇到哪些问题？ （1）在二叉树的调试中，从广义表生成二叉树的模块花了较多时间调试。 由于一开始设计的广义表的字符串表示没有思考清晰，处理只有一个孩子的节点时发生了混乱。调试之初不以为是设计的问题，从而在代码上花了不少时间调试。 目前的设计是： Tree = Identifier(Node,Node) Node = Identifier | () | Tree Identifier = ASCII Character 例子：a(b((),f),c(d,e)) 这样便消除了歧义，保证只有一个孩子的节点和叶节点的处理中不存在问题。 （2）Huffman树的调试花了较长时间。Huffman编码本身并不难处理，麻烦的是输入输出。①Huffman编码后的文件是按位存储的，因此需要位运算。 ②文件结尾要刷新缓冲区，这里容易引发边界错误。 在实际编程时，首先编写了屏幕输入输出（用0、1表示二进制位）的版本，然后再加入二进制文件的读写模块。主要调试时间在后者。 二、要让演示版压缩程序具有实用性，哪些地方有待改进？ （1）压缩文件的最后一字节问题。 压缩文件的最后一字节不一定对齐到字节边界，因此可能有几个多余的0，而这些多余的0可能恰好构成一个Huffman编码。解码程序无法获知这个编码是否属于源文件的一部分。因此有的文件解压后末尾可能出现一个多余的字节。 解决方案： ①在压缩文件头部写入源文件的总长度（字节数）。需要四个字节来存储这个信息（假定文件长度不超过4GB）。 ②增加第257个字符（在一个字节的0~255之外）用于EOF。对于较长的文件，
会造成较大的损耗。 ③在压缩文件头写入源文件的总长度%256的值，需要一个字节。由于最后一个字节存在或不存在会影响文件总长%256的值，因此可以根据这个值判断整个压缩文件的最后一字节末尾的0是否在源文件中存在。 （2）压缩程序的效率问题。 在编写压缩解压程序时 ①编写了屏幕输入输出的版本 ②将输入输出语句用位运算封装成一次一个字节的文件输入输出版本 ③为提高输入输出效率，减少系统调用次数，增加了8KB的输入输出缓存窗口 这样一来，每写一位二进制位，就要在内部进行两次函数调用。如果将这些代码合并起来，再针对位运算进行一些优化，显然不利于代码的可读性，但对程序的执行速度将有一定提高。 （3）程序界面更加人性化。 Huffman Tree Demo (C) 2011-12-16 boj Usage: huffman [-c file] [-u file] output_file -c Compress file. e.g. huffman -c test.txt test.huff -u Uncompress file. e.g. huffman -u test.huff test.txt 目前的程序提示如上所示。如果要求实用性，可以考虑加入其他人性化的功能。 三、调研常用的压缩算法，对这些算法进行比较分析 （一）无损压缩算法 ①RLE RLE又叫Run Length Encoding，是一个针对无损压缩的非常简单的算法。它用重复字节和重复的次数来简单描述来代替重复的字节。尽管简单并且对于通常的压缩非常低效，但它有的时候却非常有用（例如，JPEG就使用它）。 变体1：重复次数+字符 文本字符串：A A A B B B C C C C D D D D，编码后得到：3 A 3 B 4 C 4 D。
独立主格结构的用法说明与注意点 一、有关独立主格结构的基本概念 独立主格结构是一个名词或代词（作为逻辑主语），加上一个形容词、副词、介词短语、分词、不定式等在句中作状语。它有以下三个特点： 1. 独立主格结构的逻辑主语与句子的主语不同，它独立存在。 2. 名词或代词与后面的形容词、副词、介词短语、分词、不定式等存在逻辑上的主谓关系。 3. 独立主格结构一般用逗号与主句分开，但与主句之间不能使用任何连接词。 二、独立主格结构的常见形式 独立主格类型1：名词（代词）+现在分词 The question being settled, we went home. 问题解决之后，我们就回家了。 We shall play the match tomorrow, weather permitting. 明天假设天气好，我们就进行比赛。 The monitor being ill, we’d better put the meeting off. 班长病了，我们最好还是延期开会吧。 独立主格类型2：名词（代词）+过去分词 The job finished, we went home. 工作结束后我们就回家了。 The last bus having gone, we had to walk home. 最后一班公车已经走了，我们必须走路回家。 More time given, we should have done the job much better. 如果给我们更多的时间，我们会把工作做得更好。 独立主格类型3：名词（代词）+不定式 Nobody to come tomorrow, we will have to put off the meeting till next week. 如果明天没有人来，我们将把会议推迟到下周。 So many people to help him, he is sure to succeed. 有如此多的人来帮助他，他一定会成功的。 独立主格类型4：名词（代词）+介词短语 The soldiers dashed in, rifle in hand. 士兵们端着枪冲了进来。 A girl came in, book in hand. 一个少女进来了，手里拿着书。 He was waiting, his eyes on her back. 他在等着，眼睛望着她的背影。 独立主格类型5：名词（代词）+形容词或副词 He sat in the front row, his mouth half open. 他坐在前排，嘴半开着。 She sat at the table, collar off, head down, and pen in position, ready to begin the long letter. 她坐在桌前，衣领已解掉，头低了下来，拿好钢笔，准备开始写一封长信。 独立主格类型6：There being +名词（代词） There being nothing else to do, we went home. 没有别的事可做，我们就回家了。 There being no further business, I declare the meeting closed. 没有再要讨论的事了，我宣布散会。 独立主格类型7：It being +名词（代词） It being Christmas, the government offices were closed. 由于圣诞节的缘故，政府机关都休息。 It being a holiday, all the shops were shut. 由于今天是假日，所有商店都关门了。 说明：独立主格结构有时可在其前加上介词with。如： Don’t sleep with the windows open. 别开着窗睡觉。 He stood before his teacher with his head down. 他低着头站在老师面前。 He was lying on the bed with all his clothes on. 他和衣躺在床上。 She came in with a book in her hand. 她手里拿着一本书走了进来。 He fell asleep with the lamp burning. 他没熄灯就睡着了。
一.选择题篇 1. 算法的计算量的大小称为计算的（）。【北京邮电大学2000 二、3 （20/8分）】 A．效率 B. 复杂性 C. 现实性 D. 难度 2. 算法的时间复杂度取决于（）【中科院计算所 1998 二、1 （2分）】 A．问题的规模 B. 待处理数据的初态 C. A和B 3.计算机算法指的是（1）它必须具备（2）这三个特性。【南京理工大学 1999 一、1（2分）【武汉交通科技大学 1996 一、1（ 4分）】 (1) A．计算方法 B. 排序方法 C. 解决问题的步骤序列 D. 调度方法 (2) A．可执行性、可移植性、可扩充性 B. 可执行性、确定性、有穷性 C. 确定性、有穷性、稳定性 D. 易读性、稳定性、安全性 4．一个算法应该是（）。【中山大学 1998 二、1（2分）】 A．程序 B．问题求解步骤的描述 C．要满足五个基本特性 D．A和C. 5. 下面关于算法说法错误的是（）【南京理工大学 2000 一、1（1.5分）】 A．算法最终必须由计算机程序实现 B.为解决某问题的算法同为该问题编写的程序含义是相同的 C. 算法的可行性是指指令不能有二义性 D. 以上几个都是错误的 6. 下面说法错误的是（）【南京理工大学 2000 一、2 （1.5分）】 (1）算法原地工作的含义是指不需要任何额外的辅助空间
（2）在相同的规模n下，复杂度O(n)的算法在时间上总是优于复杂度O(2n)的算法 （3）所谓时间复杂度是指最坏情况下，估算算法执行时间的一个上界 （4）同一个算法，实现语言的级别越高，执行效率就越低 A．(1) B.(1),(2) C.(1),(4) D.(3) 7．从逻辑上可以把数据结构分为（）两大类。【武汉交通科技大学 1996 一、4（2分）】A．动态结构、静态结构 B．顺序结构、链式结构 C．线性结构、非线性结构 D．初等结构、构造型结构 8．以下与数据的存储结构无关的术语是（）。【北方交通大学 2000 二、1（2分）】A．循环队列 B. 链表 C. 哈希表 D. 栈 9．以下数据结构中，哪一个是线性结构（）？【北方交通大学 2001 一、1（2分）】A．广义表 B. 二叉树 C. 稀疏矩阵 D. 串 10．以下那一个术语与数据的存储结构无关？（）【北方交通大学 2001 一、2（2分）A．栈 B. 哈希表 C. 线索树 D. 双向链表 11．在下面的程序段中，对x的赋值语句的频度为（）【北京工商大学 2001 一、10（3分）】FOR i:=1 TO n DO FOR j:=1 TO n DO x:=x+1; A． O(2n) B．O(n) C．O(n2) D．O(log2n)
独立主格结构小结 一．独立主格结构含义 独立主格结构，又叫独立结构（absolute construction）。它在句法上游离于句子主体之外，跟主句没有任何句法联系；但在意义上却与主句紧密联系在一起，共同构成一个完整的语义环境。独立主格结构没有主语和谓语，只有逻辑上的主语，因此，它在句法上不是句子，而是一个独立于句子成分之外的独特结构形式。 独立主格结构可置于句首、句尾，用逗号与主句隔开。 二、独立主格结构的形式 独立主格结构可分为两部分，一部分是名词或代词（主格），起着逻辑主语的作用；另一部分由形容词、副词、名词、分词、不定式、介词短语等构成，表示前面名词或代词的状态、状况或动作。 1）名词／代词＋形容词 I heard that she got injured in the accident，my heart full of worry． 我听说她在这场事故中受了伤，内心充满担忧。 He stood silent in the moon-light，his door open． 月光下，门开着，他默默地站立在那。 2）名词／代词＋现在分词 Winter coming，it gets colder and colder．冬天来了，天气越来越冷了。 The rain having stopped ，he went out for a walk．雨停了，他出去散步。 3）名词／代词＋过去分词 More time given，we should have done it much better． 如果给我们更多的时间，我们会做得更好。 The boy stood there，his right hand raised．那个男生站在那里，右手高举。 4）名词／代词（主格）＋不定式 Here are the first two volumes，the third one to come out next month． 这是前两卷，第三卷将于下月问世。 The two boys said good-bye to each other，one to go home，the other to go to his friend's．两个男孩彼此道了别，一个回了家，另一个去了他朋友家。 5）名词／代词十介词短语 The huntsman entered the forest，gun in hand．那位猎人手里提着枪走进了树林。 注意：这里，gun in hand还可以说成with a gun in his hand，但不可以说a gun in hand或gun in his hand。 6）名词／代词十副词 Nobody in，the thief took a lot of things away． 由于没有人，小偷拿走了许多东西。 Lunch over，he left the house．But he was thinking． 午饭结束，他离开屋。但他还在考虑。 7）名词／代词＋名词 He fought the wolf，a stick his only weapon． 他和狼搏斗着，唯一的武器是一根棍棒。 8）There being +名词（代词）如： There being nothing else to do, we went home. 没有别的事可做，我们就回家了。
数据结构实验总结报告 李博杰PB10000603 一、调试过程中遇到哪些问题？ （1）在二叉树的调试中，从广义表生成二叉树的模块花了较多时间调试。 由于一开始设计的广义表的字符串表示没有思考清晰，处理只有一个孩子的节点时发生了混乱。调试之初不以为是设计的问题，从而在代码上花了不少时间调试。 目前的设计是： Tree = Identifier(Node,Node) Node = Identifier | () | Tree Identifier = ASCII Character 例子：a(b((),f),c(d,e)) 这样便消除了歧义，保证只有一个孩子的节点和叶节点的处理中不存在问题。 （2）Huffman树的调试花了较长时间。Huffman编码本身并不难处理，麻烦的是输入输出。 ①Huffman编码后的文件是按位存储的，因此需要位运算。 ②文件结尾要刷新缓冲区，这里容易引发边界错误。 在实际编程时，首先编写了屏幕输入输出（用0、1表示二进制位）的版本，然后再加入二进制文件的读写模块。主要调试时间在后者。 二、要让演示版压缩程序具有实用性，哪些地方有待改进？ （1）压缩文件的最后一字节问题。 压缩文件的最后一字节不一定对齐到字节边界，因此可能有几个多余的0，而这些多余的0可能恰好构成一个Huffman编码。解码程序无法获知这个编码是否属于源文件的一部分。因此有的文件解压后末尾可能出现一个多余的字节。 解决方案： ①在压缩文件头部写入源文件的总长度（字节数）。需要四个字节来存储这个信息（假定文件长度不超过4GB）。 ②增加第257个字符（在一个字节的0~255之外）用于EOF。对于较长的文件，会造成较大的损耗。 ③在压缩文件头写入源文件的总长度%256的值，需要一个字节。由于最后一个字节存在或不存在会影响文件总长%256的值，因此可以根据这个值判断整个压缩文件的最后一字节末尾的0是否在源文件中存在。 （2）压缩程序的效率问题。 在编写压缩解压程序时 ①编写了屏幕输入输出的版本 ②将输入输出语句用位运算封装成一次一个字节的文件输入输出版本 ③为提高输入输出效率，减少系统调用次数，增加了8KB的输入输出缓存窗口 这样一来，每写一位二进制位，就要在内部进行两次函数调用。如果将这些代码合并起来，再针对位运算进行一些优化，显然不利于代码的可读性，但对程序的执行速度将有一定提高。
第1章绪论 一、选择题 1. 算法的计算量的大小称为计算的（）; A．效率 B. 复杂性 C. 现实性 D. 难度2. 算法的时间复杂度取决于（）; A．问题的规模 B. 待处理数据的初态 C. A和B 3.计算机算法指的是（），它必须具备（）这三个特性; (1)A．计算方法 B. 排序方法 C. 解决问题的步骤序列 D. 调度方法 (2)A．可执行性、可移植性、可扩充性 B. 可执行性、确定性、有穷性 C. 确定性、有穷性、稳定性 D. 易读性、稳定性、安全性4．一个算法应该是（）; A．程序B．问题求解步骤的描述C．要满足五个基本特性D．A和C 5. 下面关于算法说法错误的是（）; A．算法最终必须由计算机程序实现 B.为解决某问题的算法同为该问题编写的程序含义是相同的 C. 算法的可行性是指指令不能有二义性 D. 以上几个都是错误的 6. 下面说法错误的是（）; (1）算法原地工作的含义是指不需要任何额外的辅助空间;（2）在相同的规模n下，复杂度O(n)的算法在时间上总是优于复杂度O(2n)的算法;（3）所谓时间复杂度是指最坏情况下，估算算法执行时间的一个上界;（4）同一个算法，实现语言的级别越高，执行效率就越低 A．(1) B.(1),(2) C.(1),(4) D.(3) 7．从逻辑上可以把数据结构分为（）两大类; A．动态结构、静态结构B．顺序结构、链式结构 C．线性结构、非线性结构D．初等结构、构造型结构 8．以下与数据的存储结构无关的术语是（）; A．循环队列 B. 链表 C. 哈希表 D. 栈9．以下数据结构中，哪一个是线性结构（）; A．广义表 B. 二叉树 C. 稀疏矩阵 D. 串10．以下那一个术语与数据的存储结构无关（）; A．栈 B. 哈希表 C. 线索树 D. 双向链表
北航2002年程序设计与数据结构试题 一、简答题（10’） 1. 数据结构课程是计算机专业的基础课还是专业课，或者专业基础课？（2’） 2. 学习数据结构课程需要哪些课程作为它的基础（举例两门课程）？若没有这些知识，对学习数据 结构课程可能会产生哪些影响？请举例说明（不超过100字）。（4’） 3. 数据结构课程将为那些课程学习奠定必要的基础？请举例说明哪些课程（举例两门课程）用到了 数据结构课程的哪些知识（不超过100字）。（4’） 二、（5’） 请推导出结论：具有0n 个叶结点的哈夫曼树（Huffman ）的分支总数为02(1)n -。 三、单项选择题（2’×15） 1. 线性链表中各链接点之间的地址________。 A. 必须连续 B. 部分地址必须连续 C. 不一定连续 D. 连续与否无所谓 2. 在非空线性链表中由p 所指的链接点后面插入一个由q 所致的链接点的过程是依次执行动作 ________。 A. link(q)←p; link(p)←q; B. link(q)←link(p); link(p)←q; C. link(q)←link(p); p ←q; D. link(p)←q; link(q)←p; 3. 在非空双向循环链表中由q 所指的那个链接点前插入一个p 指的链接点的动作对应的语句依次为 rlink(p)←q, llink(p)←llink(q), llink(q)←p, ________。（空白处为一条赋值语句） A. rlink(q)←p B. rlink(llink(q))←p C. rlink(llink(p))←p D. rlink(rlink(p))←p 4. 在初始为空的堆栈中依次插入元素f, e, d, c, b, a 以后，连续进行了三次删除操作，此时栈顶元素是 ________。 A. c B. d C. b D. e 5. 若某堆栈的输入序列为1, 2, 3, …, n ，输出序列的第1个元素为n ，则第i 个输出元素为________。 A. i B. n i - C. 1n i -+ D. 哪个元素无所谓 6. 求字符串T 在字符串S 中首次出现的位置的操作称为________。 A. 求串的长度 B. 求子串 C. 串的模式匹配 D. 串的连接 7. 若一棵度为7的树有8个度为1的结点，有7个度为2的结点，有6个度为3的结点，有5个度为 4的结点，有4个度为5的结点，有3个度为6的结点，有2个度为7的结点，该树一共有________个叶结点。 A. 35 B. 28 C. 77 D. 78 8. 若一棵二叉树有1001个结点，且无度为1的结点，则叶结点的个数为________。 A. 498 B. 499 C. 500 D. 501 9. 已知某完全二叉树采用顺序存储结构，结点数据信息的存放顺序依次为ABCDEFGH ，该完全二叉 树的后序遍历序列为________。
英语中的五种基本句型结构 一、句型1：Subject (主语) ＋Verb (谓语) 这种句型中的动词大多是不及物动词，所谓不及物动词，就是这种动词后不可以直接接宾语。常见的动词如：work, sing, swim, fish, jump, arrive, come, die, disappear, cry, happen等。如： 1) Li Ming works very hard.李明学习很努力。 2) The accident happened yesterday afternoon.事故是昨天下午发生的。 3）Spring is coming. 4) We have lived in the city for ten years. 二、句型2：Subject (主语) ＋Link. V(系动词) ＋Predicate(表语) 这种句型主要用来表示主语的特点、身份等。其系动词一般可分为下列两类： (1)表示状态。这样的词有：be, look, seem, smell, taste, sound, keep等。如： 1) This kind of food tastes delicious.这种食物吃起来很可口。 2) He looked worried just now.刚才他看上去有些焦急。 (2)表示变化。这类系动词有：become, turn, get, grow, go等。如： 1) Spring comes. It is getting warmer and warmer.春天到了，天气变得越来越暖和。 2) The tree has grown much taller than before.这棵树比以前长得高多了。 三、句型3：Subject(主语) ＋V erb (谓语) ＋Object (宾语) 这种句型中的动词一般为及物动词, 所谓及物动词，就是这种动词后可以直接接宾语，其宾语通常由名词、代词、动词不定式、动名词或从句等来充当。例： 1) He took his bag and left.（名词）他拿着书包离开了。 2) Li Lei always helps me when I have difficulties. (代词)当我遇到困难时，李雷总能给我帮助。 3) She plans to travel in the coming May Day.（不定式）她打算在即将到来的“五一”外出旅游。 4) I don’t know what I should do next. (从句)我不知道下一步该干什么。 注意：英语中的许多动词既是及物动词，又是不及物动词。 四、句型4：Subject(主语)＋Verb(谓语)＋Indirect object(间接宾语)＋Direct object (直接宾语) 这种句型中，直接宾语为主要宾语，表示动作是对谁做的或为谁做的，在句中不可或缺，常常由表示“物”的名词来充当；间接宾语也被称之为第二宾语，去掉之后，对整个句子的影响不大，多由指“人”的名词或代词承担。引导这类双宾语的常见动词有：buy, pass, lend, give, tell, teach, show, bring, send等。如： 1) Her father bought her a dictionary as a birthday present.她爸爸给她买了一本词典作为生日礼物。 2）The old man always tells the children stories about the heroes in the Long March. 老人经常给孩子们讲述长征途中那些英雄的故事。上述句子还可以表达为： 1）Her father bought a dictionary for her as a birthday present. 2）The old man always tells stories about the heroes to the children in the Long March. 五、句型5：Subject(主语)＋Verb (动词)＋Object (宾语)＋Complement(补语) 这种句型中的“宾语＋补语”统称为“复合宾语”。宾语补足语的主要作用或者是补充、说明宾语的特点、身份等；或者表示让宾语去完成的动作等。担任补语的常常是名词、形容词、副词、介词短语、分词、动词不定式等。如： 1）You should keep the room clean and tidy. 你应该让屋子保持干净整洁。（形容词） 2) We made him our monitor.(名词)我们选他当班长。 3) His father told him not to play in the street.(不定式)他父亲告诉他不要在街上玩。
数据结构与算法课程学习总结 2010年 5月 17日 班级：08计本（2）班姓名：谷敏敏学号：0804012023 时光飞逝，转眼之间，经过十几周的学习，“数据结构与算法”这门课程也已经接近尾声。通过学习、实验，我们明白“数据结构与算法”这门课是我们计算机专业人才培养计划中的一门必修的核心课程，同时也是计算机科学与技术专业同学的一门重要的基础专业课，重要之处不言而喻，所以，对于这门课大家也是比较认真投入的，学的也是比较尽心。当然这还与老师独特的教学风格以及不少的实验训练是密不可分的。 对于本学科的知识内容的概括、总结可如下所示： 1.第一章中是介绍的本学科的的一些基础、相关概念，如数据、数据元素、数据类型 以及数据结构的定义。其中，数据结构包括逻辑结构、存储结构和运算集合。逻辑 结构分为四类：集合型、线性、树形和图形结构，数据元素的存储结构分为：顺序 存储、链接存储、索引存储和散列存储四类。紧接着介绍了一些常用的数据运算。 最后着重介绍算法性能分析，包括算法的时间性能分析以及算法的空间性能分析。 2.第二章具体地介绍了顺序表的概念、基本运算及其应用。基本运算有：初始化表、 求表长、排序、元素的查找、插入及删除等。而关于元素查找方法课本例举了多种 方法，有：简单顺序查找、二分查找和分块查找。排序方法有：直接插入排序、希 尔排序、冒泡排序、快速排序、直接选择排序及归并排序等。最后介绍了顺序串的 概念以及字符处理问题，其重点核心内容在于串的模式匹配。 3.第三章介绍的是链表及其应用，链表中数据元素的存储不一定是连续的，还可以占 用任意的、不连续的物理存储区域。与顺序表相比，链表的插入、删除等功能是不 需要移动元素的，只需变化指针的取向即可，算法简单快捷，。链表这一章中介绍 了链表的节点结构、静态与动态链表的概念、链表的基本运算（如求表长、插入、 查找、删除等）、单链表的建立（头插法和尾插法）以及双向循环链表的定义、结 构、功能和基本算法。 4.第四章和第五章是关于堆栈和队列的介绍与应用。堆栈与队列是两种运算受限制的 线性结构。其基本运算方法与顺序表和链表运算方法基本相同，不同的是堆栈须遵 循“先进后出”的规则，对堆栈的操作只能在栈顶进行；而队列要遵循“先进先 出”的规则，课本中列出了两种结构的相应的基本算法，如入栈、出栈、入队、出 队等。在介绍队列时，提出了循环队列的概念，以避免“假溢出”的现象。同时， 对于其应用也分别讲述了如括号匹配问题等。 5.第六章介绍了特殊矩阵和广义表的概念与应用。其中，特殊矩阵包括对称矩阵、三 角矩阵、对角矩阵和稀疏矩阵等，课本中分别详细介绍了它们的存储结构。稀疏矩 阵的应用包括转置和加法运算等。最后介绍了广义表的相关概念及存储结构，关于 关于广义表的应用有：m元多项式的表示问题。 6.第七章是关于二叉树及其应用。在介绍有关概念时，提到了二叉树的性质以及两种 特殊的二叉树：完全二叉树和满二叉树。接着介绍二叉树的顺序存储和链接存储以 及生成算法。重点介绍二叉树的遍历算法（递归算法、先序、中序和后序遍历非递 归算法）和线索二叉树。二叉树的应用：基本算法、哈弗曼树、二叉排序树和堆与 堆排序。本章为本课程重点内容，需要重点掌握。
一、选择题 1. 算法的计算量的大小称为计算的（ B ）。【邮电大学2000 二、3 （20/8分）】 A．效率 B. 复杂性 C. 现实性 D. 难度2. 算法的时间复杂度取决于（C ）【中科院计算所 1998 二、1 （2分）】 A．问题的规模 B. 待处理数据的初态 C. A和B 3.计算机算法指的是（C），它必须具备（B）这三个特性。 (1) A．计算方法 B. 排序方法 C. 解决问题的步骤序列 D. 调度方法 (2) A．可执行性、可移植性、可扩充性 B. 可执行性、确定性、有穷性 C. 确定性、有穷性、稳定性 D. 易读性、稳定性、安全性 【理工大学 1999 一、1（2分）【交通科技大学 1996 一、1（ 4分）】 4．一个算法应该是（ B ）。【大学 1998 二、1（2分）】 A．程序 B．问题求解步骤的描述 C．要满足五个基本特性D．A和C. 5. 下面关于算法说法错误的是（ D ）【理工大学 2000 一、1（1.5分）】 A．算法最终必须由计算机程序实现 B.为解决某问题的算法同为该问题编写的程序含义是相同的 C. 算法的可行性是指指令不能有二义性 D. 以上几个都是错误的 6. 下面说法错误的是（ C ）【理工大学 2000 一、2 （1.5分）】 (1）算法原地工作的含义是指不需要任何额外的辅助空间（2）在相同的规模n下，复杂度O(n)的算法在时间上总是优于复杂度O(2n)的算法 （3）所谓时间复杂度是指最坏情况下，估算算法执行时间的一个上界（4）同一个算法，实现语言的级别越高，执行效率就越低4 A．(1) B.(1),(2) C.(1),(4) D.(3) 7．从逻辑上可以把数据结构分为（ C ）两大类。【交通科技大学 1996 一、4（2分）】 A．动态结构、静态结构 B．顺序结构、链式结构 C．线性结构、非线性结构 D．初等结构、构造型结构 8．以下与数据的存储结构无关的术语是（ D ）。【北方交通大学 2000 二、1（2分）】 A．循环队列 B. 链表 C. 哈希表 D.栈
一、插入排序(Insertion Sort) 1. 基本思想： 每次将一个待排序的数据元素，插入到前面已经排好序的数列中的适当位置，使数列依然有序；直到待排序数据元素全部插入完为止。 2. 排序过程： 【示例】： [初始关键字] [49] 38 65 97 76 13 27 49 J=2(38) [38 49] 65 97 76 13 27 49 J=3(65) [38 49 65] 97 76 13 27 49 J=4(97) [38 49 65 97] 76 13 27 49 J=5(76) [38 49 65 76 97] 13 27 49 J=6(13) [13 38 49 65 76 97] 27 49 J=7(27) [13 27 38 49 65 76 97] 49 J=8(49) [13 27 38 49 49 65 76 97] 1 2Procedure InsertSort(Var R : FileType); 3//对R[1..N]按递增序进行插入排序, R[0]是监视哨// 4 Begin 5 for I := 2 To N Do //依次插入R[2],...,R[n]// 6 begin 7 R[0] := R; J := I - 1; 8 While R[0] < R[J] Do //查找R的插入位置// 9 begin 10 R[J+1] := R[J]; //将大于R的元素后移// 11 J := J - 1 12 end 13 R[J + 1] := R[0] ; //插入R // 14 end 15 End; //InsertSort // 复制代码
绪论 一、选择题 1.算法的计算量的大小称为计算的( 复杂性 A.效率 B. 2. 算法的时间复杂度取决于 A.问题的规模 3. 计算机算法指的是( (1) A .计算方法 法 (2) A .可执行性、 B. 1), B. 4. 5. )。【北京邮电大学 2000二、3 (20/8 C. 现实性 D. 难度 、1 (2 分)] ( )【中科院计算所1998 待处理数据的初态 它必须具备( 排序方法 C. A 和 B 这三个特性。 C. 解决问题的步骤序列 D. 分) 】 调度方 可移植性、可扩充性 B. 可执行性、确定性、有穷性 易读性、稳定性、安全性 、1 ( 4 C.确定性、有穷性、稳定性 【南京理工大学 1999 一、1 (2分) 一个 算法应该是( )。【中山大学 A .程序 B .问题求解步骤的描述 下面关于算法说法错误的是( A. 算法最终必须由计算机程序实现 B. 为解决某问题的算法同为该问题编写的程序含义是相同的 C. 算法的可行性是指指令不能有二义性 D.以上几个都是错误的 下面说法错误的是( )【南京理工大学 2000 一、2 (1.5分)] (1 ) (2) (3) (4) A . D. 【武汉交通科技大学 1996 1998 二、1 (2 分)】 C .要满足五个基本特性 D . A 和C. 分) 】 )【南京理工大学2000 一、1 (1.5分)】 )【南京理工大学 2000 算法原地工作的含义是指不需要任何额外的辅助空间 在相同的规模n 下，复杂度O(n)的算法在时间上总是优于复杂度 O(2n )的算法 所谓时间复杂度是指最坏情况下，估算算法执行时间的一个上界 同一个算法，实现语言的级别越高，执行效率就越低 (1) B.(1),(2) 7.从逻辑上可以把数据结构分为 A.动态结构、静态结构 C.线性结构、非线性结构 &以下与数据的存储结构无关的术语是 A.循环队列 B. 链表 9.以下数据结构中，哪一个是线性结构 A.广义表 B. 二叉树 10 .以下那一个术语与数据的存储结构无关？ A.栈 B. 11 .在下面的程序段中， 分)] 6. C.(1) ,(4) D.(3) ( )两大类。【武汉交通科技大学 1996 一、4 ( 2分)] B .顺序结构、链式结构 .初等结构、构造型结构 )。【北方交通大学 2000二、1 (2分)] 哈希表 D. 栈 )?【北方交通大学 2001 一、1 (2分)] 稀疏矩阵 ) 线索树 C. C. 哈希表 C. 对 x 的赋值语句的频度为( D.串 【北方交通大学2001 一、2 (2分)】 D. 双向链表 )【北京工商大学 2001 一、10 (3 FOR i:=1 FOR j:=1 x:=x+1; A. O(2 n) TO TO DO DO .0(n) 2 C . O(n) D .O(log 2n ) 12.程序段 FOR i:=n-1 DOWNTO 1 DO FOR j:=1 TO i DO
独立主格结构介词使用的问题 在“名词或代词+介词短语”这类独立主格结构中，当其中的介词是in时，其前后的两个名词通常不加任何修饰语（如物主代词或冠词），也不用复数。如： A girl came in, book in hand. 一个少女进来了，手里拿着书。 The soldiers dashed in, rifle in hand. 士兵们端着枪冲了进来。 但如果是其他介词，则不受此限制。如： We walked out, one behind the other. 我们一个接一个地走了出来。 He was waiting, his eyes on her back. 他在等着，眼睛望着她的背影。 The old woman sat down, traces of tears still on her cheeks. 老太太坐了下来，面颊上还带有泪痕 ===================================================================== 独立主格用作伴随状语 独立主格结构在句中一般作状语，表示时间、条件、原因、伴随状况等，还可以作定语。下面给大家列举一些独立主格用作伴随状语的例子： She gazed, her hands clasped to her breast. 她凝视着，双手叉在胸前。 We divided the work, he to dean the window and I to sweep the floor. 我们分了工，他擦窗户，我扫地。 A number of officials followed the emperor, some to hold his robe, others to adjust his girdle and so on. 许多官员尾随皇帝之后，有的拎着皇帝的衣袍，有的则给他整腰带，等等。 Their room was on the third floor, it’s window overlooking the sports ground. 他们的房间在三层楼上，窗户俯视着操场。 He guiding her, they stumbled through the street. 他引着她，两个人蹒跚地穿过那条街。 He, God willing, would be in the village before the second next month. 他，如果上帝允许，将于下月2日前来到这个村庄。 He died in 1892, his death being considered as a national calamity. 他死于1892年，他的逝世被认为是举国的不幸。 独立主格用作原因状语 独立主格结构在句中一般作状语，表示时间、条件、原因、伴随状况等，还可以作定语。下面给大家列举一些独立主格用作原因状语的例子： All our savings gone, we started looking for jobs. 积蓄全部用完了，我们就开始找工作。 The boy leading the way, we had no trouble finding the strange cave. 由那个男孩带路，我们很容易就找到了那奇怪的洞。 The monitor being ill, we’d better put the meeting off. 班长病了，我们最好还是延期开会吧。 The river having risen in the night, the crossing was impossible. 夜里河水上涨，渡河不可能了。 There being no further business to discuss, we all went home. 没有别的事可讨论，我们都回家了。 独立主格用作条件状语