下载文档原格式
得分一、单项选择题（10 小题，每小题 2 分，共 20 分）1．设栈 S 和队列 Q 的初始状态为空，元素 e1,e2,e3,e4,e5,e6 依次通过栈 S，一个元素出栈后即进入队列 Q，若 6 个元素出队的顺序是 e2,e4,e3,e6,e5,e1，则栈 S 的容量至少应该是（）。
BA．2B．3C．4D．62．由 4 个叶子结点构造一棵哈夫曼树，该树的总结点数是（A．4 B．5 C．6D）。
D．73．对于长度为m（m>1）的指定序列，通过初始为空的一个栈、一个队列后，错误的叙述是）。
（DA．若入栈和入队列的序列相同，则出栈序列和出队序列可能相同B．若入栈和入队列的序列相同，则出栈序列和出队序列可以互为逆序C．入队序列与出队序列关系为1:1，而入栈序列与出栈序列关系是1: n (n≥1)D．入队序列与出队序列关系为1: n (n≥1)，而入栈序列与出栈序列关系是1:14．在一个单链表 HL 中，若要删除由指针 q 所指结点的后继结点，则执行（A）。
A．p=q->next; q->next=p->next; C．p=q->next; p->next=q->next;B．p=q->next; q->next=p;D．q->next= q->next->next; q->next=q;5．假设有如下遗产继承规则：丈夫和妻子可以相互继承遗产；子女可以继承父亲或母亲的遗产；子女之间不能相互继承。
则表示该遗产继承关系的数据结构应该是（）。
A．树B．图C．线性表D．集合B6．设数组 S[n]作为两个栈 S1 和 S2 的存储空间，对任何一个栈只有当 S[n]全满时才不能进行进栈操作。
为这两个栈分配空间的最佳方案是（A．S1 的栈底位置为 0，S2 的栈底位置为n-1B．S1 的栈底位置为 0，S2 的栈底位置为n/2C．S1 的栈底位置为 0，S2 的栈底位置为nD．S1 的栈底位置为 0，S2 的栈底位置为 1A）。
（完整版）哈尔滨工业大学数据库试题（含答案）试卷一（哈尔滨工业大学）一、选择题（每题1分，共20分）1.在数据管理技术的发展过程中，数据独立性最高的是（）阶段。
A. 数据库系统B. 文件系统C. 人工管理D. 数据项管理2. （）是存储在计算机内的有结构的数据集合。
A. 网络系统B. 数据库系统C. 操作系统D. 数据库3. 在数据库的三级模式结构中，描述数据库中全体数据的全局逻辑结构和特征的是（）。
A. 外模式B. 内模式C. 存储模式D. 模式4. 作为关系数据系统，最小应具备的关系运算是（）。
A. 排序、索引、统计B. 选择、投影、连接C. 关联、更新、排序D. 显示、打印、制表5. 在select语句中使用group by Sno时，Sno 必须出现在（）子句中。
A. whereB. fromC. selectD. having6. 在where语句的条件表达式中，与零个或多个字符匹配的通配符是（）。
A. *B. ?C. %D. _7. 对关系模式进行分解时，要求保持函数依赖，最高可以达到（）。
A. 2NFB. 3NFC. BCNFD. 4NF8. 在关系模式R（U，F）中，Y∈XF+是X→Y是否成立的（）。
A. 充分必要条件B. 必要条件C. 充分条件D. 既不充分也不必要条件9. 在关系数据库设计阶段中，完成关系模式设计的阶段是（）。
A. 需求分析阶段B. 概念设计阶段C. 逻辑设计阶段D. 物理设计阶段10. 基本E-R图就是数据库的（）。
A. 外模式B. 逻辑模式C. 内模式D. 概念模式11. 从数据流图构造E-R图时，选择实体一般应先考虑数据流图中的（）。
A. 数据项B. 数据流C. 数据处理D. 数据存储12. 以下（）不是当前常用的存取方法。
A. 索引方法B. 聚簇方法C. HASH方法D. 链表方法13. 事务一旦提交，对数据库的改变是永久的，这是事务的（）。
A. 原子性B. 一致性C. 隔离性D. 持久性14. 并发控制要解决的根本问题是保持数据库状态的（）。
哈尔滨工程大学计算机科学与技术学院816计算机专业基础综合（自命题①数据结构，②计算机组成原理）历年考研真题汇编最新资料，WORD格式，可编辑修改！目录说明：2016年公布的专业目录中，科目名称改为“816计算机专业基础综合（自命题①数据结构，②计算机组成原理）”，本书收录2001～2008年的真题，以供参考。
2004年哈尔滨工程大学计算机科学与技术学院816数据结构考研真题2003年哈尔滨工程大学计算机科学与技术学院816数据结构考研真题哈尔滨工程大学2003年数据结构试题一、判断题(每小题一分，共十分)1．数据结构，数据元素，数据项在计算机中的映象（表示）分别称为存储结构，结点，数据域。
对2．线性表的逻辑顺序与存储顺序总是一致的。
错3．广义表的表头或是元素或是一个广义表，而表尾总是一个广义表。
对4．拓扑排序是一种内部排序的算法。
错5．字符串是一种特殊的线性表，其特殊性体现在数据元素是一个字符。
对6．若线索二叉树有n个结点，则必有n+1条不空的指向树中结点的线索。
错7．稀疏矩阵的压缩存储方法一般有三元组和十字链表两种。
对8．在AOE网中，一定有不止一条关键路径。
错9．二维数组是其数据元素为线性表的线性表。
对10．一个栈的输入序列是12345，则输出序列43512是可能的。
错二、单项选择（每小题2分，共20分）1．数据结构从逻辑上可以分成线性和非线性两种结构。
2．哈希（Hash）法查找的基本思想是根据关键字值来决定记录的存储位置。
3．利用栈求表达式（（A-B）-C）-(D-(E-F)),操作数栈须有4 项。
4．图的广度优先搜索算法类似于二叉树的按层遍历操作。
5．在所有排序方法中关键字比较次数与记录初始排列次序有关的是插入排序。
6．二维数组A的行下标从1到8，列下标从1到10，若每个元素占3个单元，则该数组按“以列序为主序”存放时，A[5][8]的起始位置是180 7．表达式a*(b+c)-d的后缀表示（逆波兰式）是abc+*d－8．在一个具有n个结点的单链表中查找，查找成功时需要平均计较(n+1)/2 结点。
哈尔滨工程大学-考研数据结构真题-12 哈尔滨工程大学试卷考试科目: 数据结构A 卷题号一二三四五总分分数评卷人一、单项选择题（每空1分，共15分）1、以下数据结构中，从逻辑结构看，（）和其他数据结构不同。
A．树 B．字符串 C．队列 D．栈 2、对于顺序存储的线性表，访问结点和增加、删除结点的时间复杂度为（）。
A．O(n) O(n) B．O(n) O(1) C．O(1) O(n) D．O(1) O(1) 3、有六个元素A，B，C，D，E，F的顺序进栈，（）不是合法的出栈序列。
A．DEFCBA B．EDCBFA C．EFDBCA D．EDCFBA 4、字符串“ABCDEF”的子串有（）个。
A．19 B．20 C．21 D．22 5、顺序表中插入一个元素，需要平均移动的元素个数为（）。
A．(n-1)/2 B．n/2 C．(n+1)/2 D．n-1 6、非空的单循环链表head的尾结点（由P所指向）满足（）。
A．p->next ==NULL B．p==NULL C．p->next==head D．p==head 7、若A是中序线索二叉树中的一个结点，且A不为根，则A的前驱为( )。
A．A的右子树中最右的结点 B．A的左子树中最左的结点 C．A的右子树中最左的结点 D．A的左子树中最右的结点 8、如某二叉树有30个叶子结点，有20个结点仅有一个孩子，则该二叉树中有两个孩子的结点数为（）。
A．29 B．30 C．31 D．19 9、二维数组A的每个元素是由8个字符组成的串，其行下标i=0,1,…,9,列下标j=1,2,…,10。
若A按行序为主序存储，元素A[8][7]的起始地址与当A按列序为主序存储时的元素（）的起始地址相同（设每个字符占一个字节）。
A．A[7][9] B．A[6][8] C．A[7][8] D．A [6][9] 10、图的深度优先遍历算法类似于二叉树的（）。
A．中序遍历 B．先序遍历 C．后序遍历 D．按层遍历 11、在无向图的邻接表存储结构中，结点的个数是图中边个数的（）倍。
全国2004年10月卷答案一、单项选择题DABAC CCBDA ABABD// 5.可以简单的计算，空域为3->7，总共5个，对长则为21 - 5 = 167.c//BDBABDABDABBDA123失败，比较3次BDBABDABDABBDA1失败，比较1次BDBABDABDABBDA12失败，比较2次BDBABDABDABBDA1失败，比较1次BDBABDABDABBDA123成功，比较3次共计10次10.dA/B/ | \C D F|E二、填空题16.（一组）运算17. 直接前驱18. SXSSXXSSXSSXXX19. 模式匹配20. 5n - 6N+2N-2+2N-4=5N-6// n阶5对角阵// 1 1 1 0 0 ............// 1 1 1 1 0 ............// 1 1 1 1 1 0 ..........// 0 1 1 1 1 1 0.........// 0 0 1 1 1 1 1 0 ......// ....0 1 1 1 1 1 0 ....// ......................// ......................21. 50// 63 < 100 < 127, 最下一层叶子数:100 - 63 = 37// 倒数第2层叶子数:32 - [ 37 / 2 ] = 13 []向上取整22. 径？23. 待排关键字（记录）？24. 有序的？25. ?// 一些概念题，因为没书，很久没接触了，可能不准确。
三、解答题略28划分后左边:(55) (28) (73) (91) (37) 右边:（64），（19），（82），（46）第一次Merge之后:(28,55)(73) (91) (37) 右边:（64），（19），（82），（46)第二次Merge之后:(28,55)(73,91) (37) 右边:（64），（19），（82），（46)第三次Merge之后:(28,55,73,91)(37) 右边:（64），（19），（82），（46)第四次Merge之后:(28,37,55,73,91) 右边:（64），（19），（82），（46)第五次Merge之后:(28,37,55,73,91) 右边:（19,64），（82), (46)所以.....28，37，55，73，91，19，64，82，46四、算法阅读题30.1) p = pre->next; 或 p = L->next; // p指向第一个结点2) p->next = Lc->next; // 数据大于c的p结点插入Lc链表表头3) p = pre->next; 或 p = p->next; // 下一个结点31.此题有误，... if ((i=!t)!=0) ... 应该是 ... if( ( i = !i ) != 0 ) ...1) 1,3,5,7,6,4,22) 堆栈S中的元素依次出栈，奇数次序的入栈T,偶数次序的入队Q32.图G的邻接矩阵不对称，因此，是有向图1) 52) 计算有向图G中的端点i（第i+1个端点)的度，包括出度和入度3) O(n)33. 此题明显有错误if( low > high )应为if( low < high )因为if(){...}里有while( low < high )1) -8, -3, -2, -1, 4, 2, 5, 7：-8 -3 2 -1 -2 4 5 72) 将数组R中的前n个数调整为所有负数在前，所有整数在后五、算法设计题34. 看原型，应该是要使用递归了,题目很傻地把解法都告诉我们了。
第 1 章 绪论一、选择题1. 算法的计算量的大小称为计算的（ ）。
【北京邮电大学 2000 二、 3( 20/8 分） 】A . 效 率B.复杂性C.现实性 D. 难度2. 算法的时间复杂度取决于（ ）【 中科院计算所 1998 二、 1（ 2 分）】A.问题的规模B. 待处理数据的初态C. A 和 B3. 计算机算法指的是（ 1），它必须具备（ 2） 这三个特性。
（1） A ．计算方法 B. 排序方法 C. 解决问题的步骤序 列 D. 调度方法（2） A ．可执行性、可移植性、可扩充性 B. 可执行性、确定性、有穷性 C. 确定性、有穷性、稳定性 D. 易读性、稳定性、安全 性B. 为解决某问题的算法同为该问题编写的程序含义是相同的C. 算法的可行性是指指令不能有二义性 误的 6.下面说法错误的是（）【南京理工大学 2000 一、 2 （1.5 分）】（1）算法原地工作的含义是指不需要任何额外的辅助空间（2）在相同的规模 n 下，复杂度0（n ）的算法在时间上总是优于复杂度 0（2"）的算法（ 3）所谓时间复杂度是指最坏情况下，估算算法执行时间的一个上界（ 4）同一个算法，实现语言的级别越高，执行效率就越低A . （1） B.（1）,（2）7. 从逻辑上可以把数据结构分为（ 4（ 2 分）】A .动态结构、静态结构 C.线性结构、非线性结构 8. 以下与数据的存储结构无关的术语是（ 分）】A . 循 环 队 列 表 D. 栈9. 以下数据结构中，哪一个是线性结构（ 分）】A . 广 义 表C.（1）,（4）D.（3））两大类。
【武汉交通科技大学 1996 B.顺序结构、链式结构D.4．【南京理工大学 一个算法应该是（ A .程序性5. 1999 一、 1（ 2 分） 【武汉交通科技大学 ）。
【中山大学 1998 二、B .问题求解步骤的描述D. A 和 C.下面关于算法说法错误的是（A. 算法最终必须由计算机程序实现 1996 一、1（ 4 分）】1（2 分）】 C.要满足五个基本特 ）【南京理工大学2000 一、 1（ 1.5 分）】D. 以上几个都是错）。
数据结构试卷及参考答案（五）一、选择题(20分)1．数据的最小单位是（）。
(A)数据项(B)数据类型(C)数据元素(D)数据变量2．设一组初始记录关键字序列为(50，40，95，20，15，70，60，45)，则以增量d=4的一趟希尔排序结束后前4条记录关键字为（）。
(A)40，50，20，95(B)15，40，60，20(C)15，20，40，45(D)45，40，15，203．设一组初始记录关键字序列为(25，50，15，35，80，85，20，40，36，70)，其中含有5个长度为2的有序子表，则用归并排序的方法对该记录关键字序列进行一趟归并后的结果为（）。
(A)15，25，35，50，20，40，80，85，36，70(B)15，25，35，50，80，20，85，40，70，36(C)15，25，35，50，80，85，20，36，40，70(D)15，25，35，50，80，20，36，40，70，854．函数substr(“DATASTRUCTURE”，5，9)的返回值为（）。
(A)“STRUCTURE”(B)“DATA”(C)“ASTRUCTUR”(D)“DATASTRUCTURE”5．设一个有序的单链表中有n 个结点，现要求插入一个新结点后使得单链表仍然保持有序，则该操作的时间复杂度为（）。
(A)O(log 2n)(B)O(1)(C)O(n 2)(D)O(n)6．设一棵m 叉树中度数为0的结点数为N 0，度数为1的结点数为N l ，……，度数为m 的结点数为Nm，则N 0=（）。
(A)N l +N 2+……+Nm (B)l+N 2+2N 3+3N 4+……+(m-1)Nm(C)N 2+2N 3+3N 4+……+(m-1)Nm (D)2N l +3N 2+……+(m+1)Nm7．设有序表中有1000个元素，则用二分查找查找元素X 最多需要比较（）次。
(A)25(B)10(C)7(D)18．设连通图G 中的边集E={(a ，b)，(a ，e)，(a ，c)，(b ，e)，(e ，d)，(d ，f)，(f ，c)}，则从顶点a 出发可以得到一种深度优先遍历的顶点序列为（）。
哈尔滨工业大学1999年数据结构考研试题（图2、3缺失）一. 名词分析（15分）1.广义表2.最小生成树3.散列表4.堆5.随机文件二. 试分别画出具有3个结点的树和3个结点的二元树的所有不同形态（同构的算一个）。
（6分）三. 本题给出一个子程序的框图，如图2，试填完完善此算法框图。
该子程序用来寻找第一个均出现在三个整数单向链表F1，F2，F3中的相同整数。
假定调用该子程序前，这三个整数链表已按从小到大的次序排序，单向链表的形式如下图1的例子所示。
（15分）（注：在图2中的框图中：found和exit均为布尔型的变量，可取值为true和false。
Val是整型变量，用来存放F1，F2，F3中无相同的整数found 的值为false，否则found的值为true。
F1^.link表示访问found结点的link域）。
四假设一株二元树，按其后根顺序的结点排序为：H，I，D，J，E，B，F，G，C，A而按中根顺序的结点排序为：H，D，I，B，E，J，A，C，F，G（1）试画出这株二元树。
（7分）（2）画出它的线索二元树。
（7分）五已知集合S={7，3，4，6，19，14，16，9，22，11}，试按照自左而右的顺序依次取出S中的每个元素，逐步建立一株对应于S的二元查找树。
试画出所得到的二元查找树（不要求给算法）。
（8分）六本题给出的是将数组a的元素a1,a3…,an从大到小排序的子程序的框图，如图3，填空完善此算法框图。
该子程序采用改进的选择排序方法，该方法基本于以下思想：在选择第一大元过程中：a1与aj ( j = n , n –1…,2)逐个比较，若发现aj1>a1,则aj1与a1交换，交换后新的aj1有性质aj1>= at ( j1<t<n )。
若再有aj2 > ai ( j2 < j1 ),aj2与at (j2 < t <= n )。
如在挑选第一大元过程中，与a1交换的元素有k ( k >= 0 )个，依次为aj1,aj2,…,ajk,哈尔滨工业大学2001年数据结构考研试题考试科目：数据结构报考专业：计算机科学与技术一．填空（总分：10分，每一题2分）1．对于一个具有n个结点的单链表，在已知的结点*p后插入一个新结点的时间复杂度为________, 在给定为x的结点后插入一个新结点的时间复杂度为________。
第1章绪论1 •简述下列概念：数据、数据元素、数据项、数据对象、数据结构、逻辑结构、存储结构、抽象数据类型。
答案：数据：是客观事物的符号表示，指所有能输入到计算机中并被计算机程序处理的符号的总称。
如数学计算中用到的整数和实数，文本编辑所用到的字符串，多媒体程序处理的图形、图像、声音、动画等通过特殊编码定义后的数据。
数据元素：是数据的基本单位，在计算机中通常作为一个整体进行考虑和处理。
在有些情况下，数据元素也称为元素、结点、记录等。
数据元素用于完整地描述一个对象，如一个学生记录，树中棋盘的一个格局（状态）、图中的一个顶点等。
数据项：是组成数据元素的、有独立含义的、不可分割的最小单位。
例如，学生基本信息表中的学号、姓名、性别等都是数据项。
数据对象：是性质相同的数据元素的集合，是数据的一个子集。
例如：整数数据对象是集合N={0, ± 1，土2，…}，字母字符数据对象是集合C={ ‘A',‘ B',…，‘ Z', ‘a',‘ $,•••,‘ z' }, 学生基本信息表也可是一个数据对象。
数据结构：是相互之间存在一种或多种特定关系的数据元素的集合。
换句话说，数据结构是带“结构”的数据元素的集合，“结构”就是指数据元素之间存在的关系。
逻辑结构：从逻辑关系上描述数据，它与数据的存储无关，是独立于计算机的。
因此，数据的逻辑结构可以看作是从具体问题抽象出来的数学模型。
存储结构：数据对象在计算机中的存储表示，也称为物理结构。
抽象数据类型：由用户定义的，表示应用问题的数学模型，以及定义在这个模型上的一组操作的总称。
具体包括三部分：数据对象、数据对象上关系的集合和对数据对象的基本操作的集合。
2•试举一个数据结构的例子，叙述其逻辑结构和存储结构两方面的含义和相互关系。
答案：例如有一张学生基本信息表，包括学生的学号、姓名、性别、籍贯、专业等。
每个学生基本信息记录对应一个数据元素，学生记录按顺序号排列，形成了学生基本信息记录的线性序列。
哈工大2004年硕士研究生入学考试试题 《数据结构》答案及解析
一、 填空题 解答： 1、 ()1%mn + 或 ()1modmn + 【备注】本题主要考查考生对循环队列的数组实现过程中 关于空对与满队的区分 ，同时还考查，如何利用数组来实现循环队列，即依赖于数学意义上的求模运算来实现。 2、 第一 【备注】本题主要考查考生对二叉树中 关于前序、中序、后序遍历定义的理解，由教材中的理论可知，无论在上述三种遍历中的哪种方式中，在某子树中，同一层级上的左孩子一定在右孩子的前面首先被遍历。因此，可以将该题抽象为或者简化为如下形式（这也是 二叉树的一般形式）：
由题意，显然答案如上。 3、 9、4、6、7、8 【备注】本题主要考查考生对二分查找（即折半查找）算法的理解。在二分算法中，需要注意的是，每次对low、mid、up的选取（通过关键字进行比较即可得到）。由教材中关于对二分查
找算法的描述可知：()/2midlowup = + （注意这是两个整型数相加后与整数2作除法，其结果仍为整数，即对数学意义上的结果进行取整。），下一次可能需要继续查找的区间为两种情况：[],1lowmid − 或者 []1,midup+ 。因此，可以得到本题的查找区间分别
为： ()117/29mid=+=、()18/24mid=+=、()58/26mid=+=、()78/27mid=+=、
()88/28mid=+=
4、 N 和 2logN⎡⎤⎢⎥ 【备注】本题主要考查考生对快速排序算法的理解，同时还考察了考生对二分查找、二元查找树、二叉树、算法的最坏情况、算法的最好情况等知识点的理解。该题有一定的难度。由所学
根左右知识可知：快速排序算法的关键还是类似于二分的思想，那就是每次都将区间分割为三个集合（其中基准元本身单独构成了一个集合），然后依次递归下去。显然，我们可以将这种剖分方式与二分查找对应起来，由二分查找可知，整个二分查找过程其实就是对应于一个二元查找树，其查找效率与相应的二元查找树的深度相关。因此，在快速分类算法中，其查找效率也是和由这些给定的关键字构成的集合的大小N相关的。换句话说，就是快速分类的效率应该与具有相同规模大小的二叉树的查找效率是相同的。由二叉树的基本特性可知。给定的规模为N的二叉树，其最大高度为N（即二叉树退化为一个线性单向链
表），其最小高度至少为2
logN⎡⎤
⎢⎥。二快速分类过程的递归调用次数就是对这样的一棵二叉
树进行遍历的深度。 5、 生成初始归并段 和 基于某归并分类算法进行多遍归并生成单一归并段 【备注】本题主要考查考生外部分类过程的理解，比较简单。 6、 011 （答案可能不唯一） 【备注】本题主要考查考生对Huffman编码算法的理解与运用，计算量稍大些，需要将给定的Huffman树构造出来。由题意，可以得到如下的Huffman树（含构造过程）：
0.12 B A
0.22 KE
I 0.27 0.31 RF
0.04 0.08
0.15
0.10.120.150.16
0.12 B A 0.22KE0.04 0.08 0.10.120.12BAI 0.270.040.080.15 0.22K E0.1 0.120.12 B A
0.04 0.08 字符编码分别为： B A K E I R F C
0.12BA
I 0.270.31 RF
0.040.080.150.150.16
0.580.22 K E
0.1 0.12
C0.2
0.42 1 0
0 0 0
0
00
11
1 1
11
1
0.12 B A 0.22 K
E
I 0.27 0.31RF
0.04 0.08 0.150.10.12 0.150.16C
0.2
0.420.58
0.12 B A
0.22KE
I 0.27 0.31 RF
0.04 0.08
0.15
0.10.12
0.150.16
C0.2
0.42 1000 1001 010 011 101 110 111 00 字符的Huffman编码平均长度为：
()()040.080.0430.10.120.150.150.1620.22.92NiiiWPLlω==
=∗++∗+++++∗=
∑
7、 索引区 和 数据区 【备注】本题主要考查考生对文件中基本概念的理解。
二、 单项选择 解答： 1、 D 【备注】本题主要考查考生对二叉树的三种遍历方式、表达式的二叉树描述的理解。可以首先由给定的表达式的中缀形式恢复出一棵二叉树，然后再写出它的后缀形式。对应的表达式树形式如下： 【技巧】由四则混合运算的优先性和结合性原则，同时考虑中缀表达式的实际意义，可以知道，给定的表达式中可以认为是由两个部分组成，即类似于AB−，这样，就可以将题中的
表达式做简化，变成仅含有三个节点的二叉树形，显然，减号应该作为这颗简化的二叉树的树根。在后续遍历中，它将最后出现。因此，答案只有D是正确的。
2、 B 【备注】本题主要考查队列的应用。由实际情况可以知道，打印过程都是先发送的文件将首先被成功打印，因此，作为打印机与主机之间的缓冲区，应该设计成队列结构。 3、 C 【备注】本题主要考查栈的出栈顺序。由栈的特点“先进后出”可以得到在入栈和出栈过程中，
a b c d
e
--* + / 所需栈容量的最小值。 【技巧】考试过程中，可以画出一个数组结构，用来模拟栈。 4、 B 【备注】本题主要考查考生对关键活动的概念理解。 5、 C 【备注】本题主要考查考生对各种分类算法的时间效率及算法的稳定性的理解和应用。在常见的分类算法中，他们的时间效率、所需辅助空间及稳定性对照如下：
6、 A 【备注】本题主要考查考生对各种分类算法的时间效率及算法的稳定性的理解和应用。请参考上一题中的表格。 7、 A 【备注】本题主要考查考生对线性表、表归并等基本概念的理解和应用。由题意，其最少的比较次数发生在下列情况：设有两个有序线性表A[1…N]和B[1…N]，不妨设他们都是递增
的，若满足[1][]ABN≥或者[][1]ANB≤，则应该是比较次数最少的。此时，只需要
比较N次即可归并成一个有序表。 8、 C 【备注】本题主要考查考生对快速分类的理解和应用。一般地，快速分类算法适用于下列情况：待分类的数据集合较大且非基本有序。 9、 D 【备注】本题主要考查考生对文件常用的组织方式的基本特点（优点与缺点）及应用的理解和记忆。常见的文件组织方式有： 顺序文件（文件的各个纪录按照逻辑顺序存放外存的连续区域中，记录的顺序通常都是按照主关键字的大小排列的；适用于适用简单查询，且所有的检索和更新都是批处理的情况）； 索引文件（将文件中的各个记录的关键字与其所处地址构成一个数对[即索引]，并保存起来，就可得到索引文件；它在存储器上将分为两个区域：索引区和数据区；建立文件时，按照数据存入的先后次序来建立索引项，待数据全部存入后，再将索引项按照关键字递增或递减顺序重新排列；查找时，首先将索引区域中的信息读入，查找到七关键字所对应的的记录地址，然后再将该地址对应的存储区域读取进来即可；通常可以分为索引顺序文件和索引非顺序文件，索引顺序文件一般分为三个区：索引区、基本数据区、溢出数据区）； 散列文件（文件的各个记录采用散列方式组织，每个记录通过其关键字可由散列函数直接获取其地址；通常对那些关键字的取值范围分布较广，而实际关键字取值的数目优很少的数据集合）； 链式文件（文件中的所有记录都将按照主关键字的某种次序用链接字链接起来，整个文件对应于一个链表；在应用中，通常采用链接式盒索引式相结合的方法来组织文件结构[有时也称为索引链接文件]以提高查询效率）； 倒排文件（文件中的记录本身可以以任何方式存储，可以顺序存储，也可以链式存储；适用于多关键字的查找；具有相同关键字的所有记录被链接在一起，但这种链接信息[通常是链接指针信息]不保存在原始记录中，而是单独保存在某个索引中，因此从索引中就可以找到具有同一关键字值的所有记录）。
三、 判断题
解答： 1、 【备注】本题主要考查考生对各种查找算法中平均查找长度ASL的理解和记忆。
顺序查找的ASL为()()()()11111212NNiiiiASLPCiNNNN===∗=∗=∗++++=∑∑ ； 折半查找的ASL为（二分查找的过程可以与从其相应的判定树的根到被查找的结点的一条路径相对应，比较的次数恰好就是判定树的深度，因此可以借助于二元判定树来求得二分查
找的平均查找长度）。设表长为N，树深()12logNH+⎡⎤
=
⎢⎥，
()()
()()
1111212121log1log1NNiiiiiNNASLPCiNNN−==+
+
=∗=∗∗+=∗−
≈−
∑∑
分块查找的ASL为（分块查找实际上就是将查找分为两步走，第一步找到所属块，第二步在所属快内部找到某个关键字。因此整个算法的平均查找长度就是这两次查找的平均查找长
