计算机专业基础综合数据结构(集合)历年真题试卷汇编9

计算机专业基础综合数据结构（排序）历年真题试卷汇编1(总分：72.00，做题时间：90分钟)一、单项选择题(总题数：15，分数：30.00)1.下列序列中，( )是执行第一趟快速排序后所得的序列。

【福州大学1998一、9(2分)】A.[68，11，18，69] [23，93，73]B.[68，11，69，23] [18，93，73]C.[93，73][68，11，69，23，18] √D.[68，11，69，23，18] [93，73]枢轴是73。

2.适合并行处理的排序算法是( )。

【西安电子科技大学2005一、8(1分)】【电子科技大学2005一、8(1分)】A.选择排序B.快速排序√C.希尔排序D.基数排序3.一组记录的关键字为(46，79，56，38，40，84)，则利用快速排序的方法，以第一个记录为基准得到的一次划分结果为( )。

【北京交通大学2005一、8(2分)【燕山大学2001一、4(2分)】A.(38，40，46，56，79，84)B.(40，38，46，79，56，84)C.(40，38，46，56，79，84) √D.(40，38，46，84，56，79)如何对一趟快速排序的结果在最短的时间内做出正确判断，这里给出建议：首先84应该不动，所以D排除了；接着40应调到序列首，所以A排除了；接着79应调到移走40的空位上，B排除了。

选择答案C，不必再继续做了(假定确有唯一正确答案)。

4.下列排序算法中，( )算法可能会出现下面的情况：初始数据有序时，花费的时间反而最多。

【中南大学2005一、4(2分)】A.快速排序√B.堆排序C.希尔排序D.冒泡排序5.将一组无序的数据重新排列成有序序列，其方法有：( )。

【武汉理工大学2004一、8(3分)】A.拓扑排序B.快速排序√C.堆排序√D.基数排序√6.就平均性能而言，目前最好的内排序方法是( )排序法。

【西安电子科技大学1998一、9(2分)】A.冒泡B.希尔插，AC.交换D.快速√7.如果只想得到1000个元素组成的序列中第5个最小元素之前的部分排序的序列，用( )方法最快。

计算机专业基础综合数据结构（排序）历年真题试卷汇编1(总分：72.00，做题时间：90分钟)一、单项选择题(总题数：15，分数：30.00)1.下列序列中，( )是执行第一趟快速排序后所得的序列。

【福州大学1998一、9(2分)】A.[68，11，18，69] [23，93，73]B.[68，11，69，23] [18，93，73]C.[93，73][68，11，69，23，18] √D.[68，11，69，23，18] [93，73]枢轴是73。

2.适合并行处理的排序算法是( )。

【西安电子科技大学2005一、8(1分)】【电子科技大学2005一、8(1分)】A.选择排序B.快速排序√C.希尔排序D.基数排序3.一组记录的关键字为(46，79，56，38，40，84)，则利用快速排序的方法，以第一个记录为基准得到的一次划分结果为( )。

【北京交通大学2005一、8(2分)【燕山大学2001一、4(2分)】A.(38，40，46，56，79，84)B.(40，38，46，79，56，84)C.(40，38，46，56，79，84) √D.(40，38，46，84，56，79)如何对一趟快速排序的结果在最短的时间内做出正确判断，这里给出建议：首先84应该不动，所以D排除了；接着40应调到序列首，所以A排除了；接着79应调到移走40的空位上，B排除了。

选择答案C，不必再继续做了(假定确有唯一正确答案)。

4.下列排序算法中，( )算法可能会出现下面的情况：初始数据有序时，花费的时间反而最多。

【中南大学2005一、4(2分)】A.快速排序√B.堆排序C.希尔排序D.冒泡排序5.将一组无序的数据重新排列成有序序列，其方法有：( )。

【武汉理工大学2004一、8(3分)】A.拓扑排序B.快速排序√C.堆排序√D.基数排序√6.就平均性能而言，目前最好的内排序方法是( )排序法。

【西安电子科技大学1998一、9(2分)】A.冒泡B.希尔插，AC.交换D.快速√7.如果只想得到1000个元素组成的序列中第5个最小元素之前的部分排序的序列，用( )方法最快。

[考研类试卷]计算机专业基础综合数据结构（图）历年真题试卷汇编9 一、综合题1 下面的邻接表表示一个给定的无向图。

(1)给出从顶点v1开始，对图G用深度优先搜索法进行遍历时的顶点序列；(2)给出从顶v1，1开始，对图G用广度优先搜索法进行遍历时的顶点序列。

【复旦大学1998六(10分)】1 给出图G：2 画出G的邻接表表示图；3 根据你画出的邻接表，以顶点①为根，画出G的深度优先生成树和广度优先生成树。

【南开大学1997五(14分)】【烟台大学2007四、3(15分)】4 已知一个有向图如图所示，则从顶点a出发进行深度优先遍历，写出所有可能得到的DFS序列。

【北京交通大学2006四、4(5分)】4 解答下面的问题：【西安电子科技大学2000计算机应用六(10分)】5 如果每个指针需要4字节，每个顶点的标号占2字节，每条边的权值占2字节。

下图采用哪种表示法所需的空间较多?为什么?6 写出下图从顶点1开始的：DFS树。

7 如下所示的连通图，请画出：(1)以顶点①为根的深度优先生成树；(5分)(2)如果有关节顶点，请找出所有的关节顶点。

(5分)【清华大学l 998七(10分)】7 某田径赛中各选手的参赛项目表如下：设项目A，B，…，F各表示一数据元素，若两项目不能同时举行，则将其连线(约束条件)。

8 根据此表及约束条件画出相应的图状结构模型，并画出此图的邻接表结构；9 写出从元素A出发按“广度优先搜索”算法遍历此图的元素序列。

【北京科技大学1999五2000五(12分)】10 考虑下图：(1)从顶点A出发，求它的深度优先生成树。

(2)从顶点E出发，求它的广度优先生成树。

(3)根据普利姆(Prim)算法，求它的最小生成树。

【上海交通大学1999六(12分)】11 在什么情况下，Prim算法与Kruskual算法生成不同的MST?【西安电子科技大学2000计算机应用一、11(5分)】12 已知一个无向图如下图所示，要求分别用Prim和Kruskal算法生成最小生成树(假设以①为起点，试画出构造过程)。

[考研类试卷]计算机专业基础综合数据结构（排序）历年真题试卷汇编9一、综合题1 如果只要找出一个具有n个元素的集合的第k(1≤k≤n)个最小元素，你所学过的排序方法中哪种最适合?给出实现的思想。

【北方交通大学1998六(10分)】2 设结点个数为n，请问采用堆排序法进行排序，其时间复杂性是多少?请以大O 形式给出，并给出证明。

【上海交通大学2004四(10分)】2 已知待排序的序列为(503，87，512，6l，908，170，897，275，653，462)，试完成下列各题。

3 根据以上序列建立一个堆(画出第一步和最后堆的结果图)，希望先输出最小值。

4 输出最小值后，如何得到次小值(并画出相应结果图)。

【同济大学2001二(10分)】4 试将关键字序列(56，塾，55，67，46，58，18，88)5 调整成一个初始大顶堆，用二叉树形式说明调整过程；6 简要说明如何从初始大顶堆开始进行排序。

【华中科技大学2007四、24(10分)】7 一组记录的关键字为(50，79，8，56，32，41，85)，给出利用重建堆方法建立的初始堆(堆顶最大)，并给出堆排序的过程。

【吉林大学2007二、5(4分)】8 已知序列{503，87，512，61，908，170，897，275，653，462)将其调整为堆(大堆顶，即K i≥K2i，K i≥K2i+1)。

【中国海洋大学2006一、4(8分)】9 给定关键字序列(20，18，9，86，72，12，27，40)。

试将该序列建成小根堆。

10 判断下面的每个结点序列是否表示一个堆，如果不是堆，请把它调整成堆。

①100，90，80，60，85，75，20，25，10，70，65，50②100，70，50，20，90，75，60，25，10，85，65，80【复旦大学1997二(8分)】11 全国有10000人参加物理竞赛，只录取成绩优异的前10名，并将他们从高分到低分输出。

计算机专业基础综合数据结构（集合）历年真题试卷汇编5(总分66,考试时间90分钟)1. 单项选择题1. 含有n个非叶子结点的m阶B一树至少包含( )个关键字。

【北京交通大学20041A. (m-1)*nB. nC. n*(m／2-1)D. (n一1)*(m／2-1)+12. 理论上，散列表的平均比较次数为( )次。

【北京邮电大学2005一、9(2分)】A. 1B. 2C. 4D. n3. 散列函数有一个共同的性质，即函数值应当以( )取其值域的每个值。

【西安电子科技大学2001计算机应用一、7(2分)】【北京邮电大学。

1999一、4(2分)】A. 最大概率B. 最小概率C. 平均概率D. 同等概率4. 将10个元素散列到100000个单元的哈希表中，则( )产生冲突。

【北京邮电大学2001一、4(2分)】A. 一定会B. 一定不会C. 仍可能会5. 采用链地址法解决冲突的哈希表中，查找成功的平均查找长度( )。

【北京交通大学2005一、6(2分)2007】A. 直接与关键字个数有关B. 直接与装填因子有关C. 直接与表的容量有关D. 直接与哈希函数有关6. 下面关于哈希(Hash，杂凑)查找的说法正确的是( )。

【南京理工大学1998一、10(2分)】【烟台大学2007一、1 8(2分)】A. 哈希函数构造的越复杂越好，因为这样随机性好，冲突小B. 除留余数法是所有哈希函数中最好的C. 不存在特别好与坏的哈希函数，要视情况而定D. 若需在哈希表中删去一个元素，不管用何种方法解决冲突都只要简单地将该元素删去即可7. 在构造哈希表方面，下面的说法( )是正确的。

【华南理工大学2005一、1(2分)】A. 再散列在处理冲突时不会产生“聚集”B. 散列表的装载因子越大，说明空间利用率越好，因此应使装载因子尽量大C. 散列函数选得好可减少冲突现象D. 对于任何具体关键字都不可能找到不产生冲突的散列函数8. 在构造散列表方面，下面的说法( )是正确的。

计算机专业基础综合数据结构（集合）历年真题试卷汇编3(总分60,考试时间90分钟)2. 填空题1. 一棵含有15个关键字的4阶B树，其非叶结点数最少不能少于__________个，最多可以为__________个。

【中国科学技术大学1997二、4(4分)】2. 对于m=4(4阶)的B一树，如果根的层次为第1层，则高度为2的B一树最少要存储__________个关键字，最多可以保存__________个关键字。

【北京理工大学2005二、4(2分)】3. 具有n个关键字的B树的查找路径长度不会大于__________。

【中科院计算机1999二、2(1分)】4. 127阶B一树中每个结点最多有(1)个关键字；除根结点外所有非终端结点至少有(2)棵子树；65阶B+树中除根结点外所有结点至少有(3)个关键字；最多有(4)棵子树；【北方交通大学1999二、5(4分)】5. 设高为h的m阶B一树上共有k个关键字，则其叶子结点有__________个。

【北京交通大学2006二、8(2分)】6. 高度为h的2-3树中叶子结点的数目至多为__________。

【西安电子科技大学1999软件一、6(2分)】7. 哈希表用__________确定记录的存储位置。

【北京理工大学2005二、5(2分)】8. 在哈希造表中，不同的关键字产生同一哈希地址的现象，称为__________。

【北京理工大学2006十、6(1分)】9. 设已知n个关键字具有相同的散列函数值，并且采用线性探测再散列方法处理冲突，将这n个关键字散列到初始为空的地址空间中，一共发生了__________次散列冲突。

【北京航空航天大学2006一、9(1分)】【西安电子科技大学2001软件一、7(2分)】6. 综合题1. 设有n个值不同的元素存于顺序结构中，试问：你能否用比(2n一3)少的比较次数选出这n个元素中的最大值和最小值?若能，请说明是如何实现的；在最坏情况下，至少要进行多少次比较。

计算机专业基础综合数据结构（概论）历年真题试卷汇编1(总分：64.00，做题时间：90分钟)一、单项选择题(总题数：15，分数：32.00)1.以下哪个数据结构不是多型数据类型?( )【中山大学1999一、3(1分)】（分数：2.00）A.栈B.广义表C.有向图D.字符串√解析：2.以下数据结构中，( )是非线性数据结构【中山大学1999一、4】（分数：2.00）A.树√B.字符串C.队D.栈解析：3.下列数据中，( )是非线性数据结构。

【北京理工大学2001六、1(2分)】（分数：2.00）A.栈B.队列C.完全二叉树√D.堆解析：解析：栈、队列是线性结构，堆是元素的序列，存在一维数组中，可以看成是线性结构。

完全二叉树是非线性结构，只是由于双亲和子女编号间存在固定关系，用一维数组存储更好。

4.连续存储设计时，存储单元的地址( )。

【中山大学1999一、1(1分)】（分数：2.00）A.一定连续√B.一定不连续C.不一定连续D.部分连续，部分不连续解析：5.以下属于逻辑结构的是( )。

【西安电子科技大学应用2001一、1】（分数：2.00）A.顺序表B.哈希表C.有序表√D.单链表解析：6.算法的计算量的大小称为计算的( )。

【北京邮电大学2000二、3(20／8分)】（分数：2.00）A.效率B.复杂性√C.现实性D.难度解析：7.算法的时间复杂度取决于( )。

【中科院计算所1998二、1(2分)】（分数：2.00）A.问题的规模B.待处理数据的初态C.A和B √解析：计算机算法指的是(1)，它必须具备(2)这三个特陛。

【南京理工大学1999一、1(2分)】（分数：4.00）(1).(1)（分数：2.00）A.计算方法B.排序方法C.解决问题的步骤序列√D.调度方法解析：(2).(2)（分数：2.00）A.可执行性、可移植性、可扩充性B.可执行性、确定性、有穷性√C.确定性、有穷性、稳定性D.易读性、稳定性、安全性解析：8.一个算法应该是( )。

计算机专业基础综合数据结构（集合）历年真题试卷汇编1(总分：82.00，做题时间：90分钟)一、综合题(总题数：25，分数：72.00)1.试用关键字序列(33，10，45，20，53，43，31，15，65，40)，构造哈希(Hash)表，设哈希函数为：H(key)=key％11，其中key为关键字，％为求余运算符；用开放定址法处理冲突，用线性探测再散列法查找空位，用长度为14的数据元素组A[14]表示哈希表。

(1)画出该哈希表的存储结构图；(2)假定每个元素的查找概率相等，计算查找成功时的ASL；(3)计算查找不成功时的ASL。

【华中科技大学2007四、25(10分)】（分数：2.00）__________________________________________________________________________________________ 2.采用哈希函数H(k)=3*k mod 13并用线性探测开放地址法处理冲突，在散列地址空间[0．．12]中对关键字序列22，41，53，46，30，13，1，67，51。

(1)构造哈希表(画示意图)；(2)装填因子；等概率下(3)成功的和(4)不成功的平均查找长度。

【北京工业大学2000三(8分)】【烟台大学2007四、4(10分)】（分数：2.00）__________________________________________________________________________________________3.设散列表长度为14 2.00）__________________________________________________________________________________________ 4.常用的构造哈希函数的方法有哪些?若在哈希表中删除一个记录，应如何操作?为什么?已知一组关键字为(19，14，23，01，68，20，84，27，55，11，10，79)，按哈希函数H(Key)=KeyMOD 13和线性探测再散列处理冲突的方法在地址空间A[0．．15]中构造哈希表。

可编辑修改精选全文完整版第一章概论一、选择题1、研究数据结构就是研究（ D ）。

A. 数据的逻辑结构B. 数据的存储结构C. 数据的逻辑结构和存储结构D. 数据的逻辑结构、存储结构及其基本操作2、算法分析的两个主要方面是（ A ）。

A. 空间复杂度和时间复杂度B. 正确性和简单性C. 可读性和文档性D. 数据复杂性和程序复杂性3、具有线性结构的数据结构是（ D ）。

A. 图B. 树C. 广义表D. 栈4、计算机中的算法指的是解决某一个问题的有限运算序列.它必须具备输入、输出、（ B ）等5个特性。

A. 可执行性、可移植性和可扩充性B. 可执行性、有穷性和确定性C. 确定性、有穷性和稳定性D. 易读性、稳定性和确定性5、下面程序段的时间复杂度是（ C ）。

for(i=0;i<m;i++)for(j=0;j<n;j++)a[i][j]=i*j;A. O(m2)B. O(n2)C. O(m*n)D.O(m+n)6、算法是（ D ）。

A. 计算机程序B. 解决问题的计算方法C. 排序算法D. 解决问题的有限运算序列7、某算法的语句执行频度为（3n+nlog2n+n2+8）,其时间复杂度表示（ C ）。

A. O(n)B. O(nlog2n)C. O(n2)D.O(log2n)8、下面程序段的时间复杂度为（ C ）。

i=1;while(i<=n)i=i*3;A. O(n)B. O(3n)C. O(log3n)D. O(n3)9、数据结构是一门研究非数值计算的程序设计问题中计算机的数据元素以及它们之间的（）和运算等的学科。

A. 结构B. 关系C. 运算D. 算法10、下面程序段的时间复杂度是（A ）。

i=s=0;while(s<n){i++;s+=i;}A. O(n)B. O(n2)C. O(log2n)D. O(n3)11、抽象数据类型的三个组成部分分别为（ A）。

A. 数据对象、数据关系和基本操作B. 数据元素、逻辑结构和存储结构C. 数据项、数据元素和数据类型D. 数据元素、数据结构和数据类型12、通常从正确性、易读性、健壮性、高效性等4个方面评价算法的质量.以下解释错误的是（）。

[考研类试卷]计算机专业基础综合数据结构（集合）历年真题试卷汇编5.doc[考研类试卷]计算机专业基础综合数据结构（集合）历年真题试卷汇编5一、填空题1 对于具有144个记录的文件，若采用分块查找法，且每块长度为8，则平均查找长度为__________。

【北方交通大学2001二、8】2 有一个2000项的表，欲采用等分区间顺序查找方法进行查找，则每块的理想长度是 (1)，分成 (2) 块最为理想，平均查找长度是 (3) 。

【中国矿业大学2000一、6(3分)】3 分块检索中，若索引表和各块内均用顺序查找，则有900个元素的线性表分成__________块最好；若分成25块，其平均查找长度为__________。

【北京工业大学1999一、5(2分)】4 执行顺序查找时，储存方式可以是(1)，二分法查找时，要求线性表(2)，分块查找时要求线性表(3)，而散列表的查找，要求线性表的存储方式是(4)。

【山东大学1998一、1(3分)】5 查找是非数值程序设计的一个重要技术问题，基本上分成(1)查找，(2)查找和(3)查找。

处理哈希冲突的方法有(4)、(5)、(6)和(7)。

【华北计算机系统工程研究所1999一(5分)】6 如果按关键码值递增的顺序依次将关键码值插入到二叉排序树中，则对这样的二叉排序树检索时，平均比较次数为__________。

【山东大学1999二、1(4分)】7 在含有n个结点的二叉排序树中查找一个关键字，进行关键字比较次数的最大值是__________。

【北京交通大学2004一、15(2分)】8 在二叉排序树上成功地找到一个结点，在平均情况下的时间复杂性是：__________，在最坏情况下的时间复杂性是__________。

【上海交通大学2004五、1(15／4分)】9 AVL树__________是完全二叉树；完全二叉树__________是AVL 树。

【电子科技大学2005二、5(1分)】10 一棵深度为k的平衡二叉树，其每个非终端结点的平衡因子均为0，则该树共有__________个结点。