考研类试卷计算机数据结构汇编

1、广度优先遍历算法类似于树的( )。
【北京交通大学 2007】（分数：2.00）A.中序遍B.先序遍历C.后序遍D.按层次遍历3.执行( )操作时，需要使用队列作辅助存储空间。
【华中科技大学 2006一、1(2 分)】（分数：2.00）A.查找哈希(Hash)表B.广度优先搜索图C.先序(根)遍历二叉树D.深度优先搜索图4.图的 BFS生成树的树高比：DFS 生成树的树高( )。
【青岛大学 2004一、8(3 分)】（分数：2.00）A.小或相等B.小C.大或相等D.大5.无向图 G=(V,E)，其中：V=a，b，c，d,e，f，E=(a，b)，(a，e)，(a，c)，(b，e)，(c，f)，(f,d)，(e，d)，对该图进行深度优先遍历，得到的顶点序列正确的是( )。
【南京理工大学 2001一、14(15分)】（分数：2.00）A.a，b，e，c，d,fB.a，c，f,e ，b，dC.a，e，b，c,f,dD.a，e，d,f, c，b6.设图如下所示，在下面的 5个序列中，符合深度优先遍历的序列有多少? ( )。
【南京理工大学 2000一、20(15 分)】 （分数：2.0。

2、00）A.要排序的数据量太大B.要排序的数据中含有多个相同值C.要排序的数据个数为奇数D.要排序的数据已基本有序3.当待排序列基本有序时，下列排序方法中( )最好。
【北京邮电大学 2005 一、10 (2 分)】（分数：2.00）A.直接插入排序B.快速排序C.堆排序D.归并排序4.设被排序的结点序列共有 N 个结点，在该序列中的结点已十分接近排序的情况下，用直接插入法、归并法和一般的快速排序法对其排序，这些算法的时间复杂性应为( )。
【上海交通大学 2005 四、5(2 分)】（分数：2.00）A.O(N)，O(N)，O(N)B.O(N)，O(N*log 2 N)，O(N*log 2 N)C.O(N)，O(N*log 2 N)，O(N 2 )D.O(N 2 )，O(N*log 2 N)，O(N 2 )5.数据序列(8，9，10，4，5，6，20，1，2)只能是下列排序算法中的( )的两趟排序后的结果。
【合肥工业大学 1999 一、3(2 分)】（分数：2.00）A.选择排序B.冒泡排序C.插入排序D.堆排序6.一个排序算法的时间复杂度与( )有关。
【华中科技大学 2004 一、8(。

3、北京邮电大学 2005一、9(2 分)】（分数：2.00）A.1B.2C.4D.n3.散列函数有一个共同的性质，即函数值应当以( )取其值域的每个值。
【西安电子科技大学 2001计算机应用一、7(2 分)】 【北京邮电大学。
1999 一、4(2 分)】（分数：2.00）A.最大概率B.最小概率C.平均概率D.同等概率4.将 10个元素散列到 100000个单元的哈希表中，则( )产生冲突。
【北京邮电大学 2001一、4(2 分)】（分数：2.00）A.一定会B.一定不会C.仍可能会5.采用链地址法解决冲突的哈希表中，查找成功的平均查找长度( )。
【北京交通大学 2005一、6(2 分)2007】（分数：2.00）A.直接与关键字个数有关B.直接与装填因子有关C.直接与表的容量有关D.直接与哈希函数有关6.下面关于哈希(Hash，杂凑)查找的说法正确的是( )。
【南京理工大学 1998一、10(2 分)】【烟台大学2007一、1 8(2 分)】（分数：2.00）A.哈希函数构造的越复杂越好，因为这样随机性好，冲突小B.除留余数法是所有哈希函数中最好的C.不存在特别好与坏的哈希函数，要。

4、11，69，23，18D.68，11，69，23，18 93，732.适合并行处理的排序算法是( )。
【西安电子科技大学 2005 一、8(1 分)】【电子科技大学 2005 一、8(1 分)】（分数：2.00）A.选择排序B.快速排序C.希尔排序D.基数排序3.一组记录的关键字为(46，79，56，38，40，84)，则利用快速排序的方法，以第一个记录为基准得到的一次划分结果为( )。
【北京交通大学 2005 一、8(2 分)【燕山大学 2001 一、4(2 分)】（分数：2.00）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)4.下列排序算法中，( )算法可能会出现下面的情况：初始数据有序时，花费的时间反而最多。
【中南大学 2005 一、4(2 分)】（分数：2.00）A.快速排序B.堆排序C.希尔排序D.冒泡排序5.将一组无序的数据重新排列成有序序列，其方法有：( )。
【武汉理工大学 2004 一、8(3 分)】（分数：2.00）A.拓扑排序B.快。

5、2.求图的最小生成树有两种算法，_算法适合于求稀疏图的最小生成树。
【南京理工大学 2001二、6(2 分)】【北京交通大学 2005二、7(2 分)】（分数：2.00）_3.Prim(普里姆)算法适用于求_的网的最小生成树；Kruskal(克鲁斯卡尔)算法适用于求_的网的最小生成树。
【厦门大学 1999一、4(204)】（分数：2.00）_4.克鲁斯卡尔算法的时间复杂度为_，它对_图较为适合。
【中科院计算所 1999二、3(2分)】（分数：2.00）_。

6、分数：2.00）A.堆排序，冒泡排序B.快速排序，堆排序C.直接选择排序，归并排序D.归并排序，冒泡排序3.稳定的排序方法是( )。
【北方交通大学 2000 二、3(2 分)】（分数：2.00）A.直接插入排序和快速排序B.折半插入排序和起泡排序C.简单选择排序和四路归并排序D.树形选择排序和 Shell 排序4.下列排序方法中，哪一个是稳定的排序方法?( )。
【北方交通大学 2001 一、8(2 分)】（分数：2.00）A.直接选择排序B.二分法插入排序C.希尔排序D.快速排序5.下列排序算法中，( )是稳定排序。
【北京理工大学 2007 一、10(1 分)】（分数：2.00）A.希尔排序B.快速排序C.堆排序D.直接插入排序6.如果待排序序列中两个数据元素具有相同的值，在排序前后它们的相互位置发生颠倒，则称该排序算法是不稳定的。
( )就是不稳定的排序方法。
【清华大学 1998 一、3(2 分)】（分数：2.00）A.起泡排序B.归并排序C.Shell 排序D.直接插入排序E.简单选择排序7.若要求排序是稳定的，且关键字为实数，则在下列排序方法中应选( )排序为宜。
【中科院计算所 2。

7、2.设 S1、S2 为串，请给出使 S1$2=S2S1 成立的所有可能的条件(为连接符)。
【国防科技大学 1999一】【长沙铁道学院 1997三、5(3 分)】（分数：2.00）_3.已知：s=(xyz)+*，t=(x+z)*。
试利用联结、求子串和置换等基本运算，将 s转化为 t。
【北方交通大学 1996一、3(5 分)】【山东科技大学 2002一、6(5 分)】（分数：2.00）_4.s是字符数组，s0中存放的是该字符串的有效长度，假设 s17中字符串的内容为“abcabaa“，说明下列程序的功能及执行结果。
#define len 8 int k nlen， 。

8、有 0 个或多个输入量B.健壮性C.正确性D.可行性3.下面程序的时间复杂性为( )。
【南京理工大学 2004 一、4(1 分)】for(int i=0；iA.O(n 2 )B.O(m*n)C.O(m 2 )D.O(m+n)4.在下列算法中，“x=x*2”的执行次数是( )。
【华中科技大学 2006 一、16(2 分)】int suanfa(int n)int i，j，x=1;for(i=0；iA.m(n+1)2B.Nlog 2 nC.n 2D.n(n 一 1)25.执行下列算法 suanfa2(1000)，输出结果是( )。
【华中科技大学 2006 一、17(2 分)】void suanfa2(int n)int i=i;while(in： for(int i=0;imi; change(m，0，n 一 1)； for(i=0；in： for(int i=0;imi; change(m，0，n 一 1)； for(i=0；in；i+)coutmi_。

9、数据元素有序2.当在一个有序的顺序存储表上查找一个数据时，即可用折半查找，也可用顺序查找，但前者比后者的查找速度( )。
【南京理工大学 1997一、7(2 分)】（分数：2.00）A.必定快B.不一定C.在大部分情况下要快D.取决于表递增还是递减3.请指出在顺序有序表(2、5、7、10、14、15、18、23、35、41、52)中，用“折半查找法”查找关键字14需做的比较次数为( )。
【北京工业大学 2005一、3(2 分)】（分数：2.00）A.2B.3C.4D.54.折半查找有序表(5，8，10，22，36，50，53，88)，若查找元素 70，则需依次与表中元素(关键字)( )进行比较，查找结果是“失败”。
【华中科技大学 2006一、11(2 分)】（分数：2.00）A.36，53B.22，50，53，88C.36，53，88D.22，53，885.具有 12个关键字的有序表，折半查找的平均查找长度为( )。
【中山大学。
1998 二、10(2 分)】【烟台大学 2007一、17(2 分)】（分数：2.00）A.31B.4C.25D.56.对一个长度为 50的有序表进行折半查找。

10、华南理工大学 2007】（分数：2.00）A.邮电图B.AOV网C.公路网D.AOE网3.关键路径是 AOE网中( )。
【中南大学 2003一、10(1 分)】（分数：2.00）A.从始点到终点的最短路径B.从始点到终点的最长路径C.从始点到终点的边数最多的路径D.从始点到终点的边数最少的路径4.下面关于求关键路径的说法不正确的是( )。
【南京理工大学 1998一、12(2 分)】（分数：2.00）A.求关键路径是以拓扑排序为基础的B.一个事件的最早开始时间同以该事件为尾的弧的活动最早开始时间相同C.一个事件的最迟开始时间为以该事件为尾的弧的活动最迟开始时间与该活动的持续时间的差D.关键活动一定位于关键路径上5.下列关于 AOE网的叙述中，不正确的是( )。
【北方交通大学 1999一、7(3 分)】【北京工业大学 1999一、1(2 分)】【哈尔滨工业大学 2004二、3(1 分)】（分数：2.00）A.关键活动不按期完成就会影响整个工程的完成时间B.任何一个关键活动提前完成，那么整个工程将会提前完成C.所有的关键活动提前完成，那么整个工程将会提前完成D.某些关键活动若提前完成，那。

11、2.下列函数是在无向图的邻接表中删除一条边的算法，请完善该程序。
V0id deledge(ALGraph*G，int i， int j) EdgeNode*p，*q; p=G 一adj listifirstedge； if()fG 一adjlistifirstedge=p 一next; free(p)；) elsewhile(p 一next 一adjvex!=j ) p=G 一adj lisjfirstedge ； if(p 一adjvex= =i)G一adj listjfirstedge=p 一12ext； free(p)；) elsefwhile(p 一12ext 一adlvex!=i p 一next) ； if(p 一next!=null)q=p 一next；free(q)；) 【东南大学2005数据结构部分三(10 分)】（分数：2.00）_。

12、2.设结点个数为 n，请问采用堆排序法进行排序，其时间复杂性是多少?请以大 O 形式给出，并给出证明。
【上海交通大学 2004 四(10 分)】（分数：2.00）_已知待排序的序列为(503，87，512，6l，908，170，897，275，653，462)，试完成下列各题。
（分数：4.00）(1).根据以上序列建立一个堆(画出第一步和最后堆的结果图)，希望先输出最小值。
（分数：2.00）_(2).输出最小值后，如何得到次小值(并画出相应结果图)。
【同济大学 2001 二(10 分)】（分数：2.00）_。

13、于 x分的学生人数* int head=1，mid，rear=N; domid=(head+rear)2； if(x=aj)i+； if(i_3.下列算法是利用折半查找算法在一个有序表中插入一个元素 X，并保持表的有序性。
请将程序中空白处填上适当的语句完成功能。
int bininsert(sqlist r，int x，int n)将 x插入到 r1-n中并保持其有序性 int low：1，high=13，mid，flag=l，pos，i； 插入的位置为 pos while( (1) size：int； lchild， rchild， parent8： tree；END；一个结点 x的 size域的值是以该结点为根的子树中结点的总数(包括 x本身)。
例如，下图中 x所指结点的 size值为 设树高为 h，试写一时间为 O(h)的算法Rank(T：tree；x：node)。

14、4的数据元素组 A14表示哈希表。
(1)画出该哈希表的存储结构图；(2)假定每个元素的查找概率相等，计算查找成功时的 ASL；(3)计算查找不成功时的 ASL。
【华中科技大学 2007四、25(10分)】（分数：2.00）_2.采用哈希函数 H(k)=3*k mod 13并用线性探测开放地址法处理冲突，在散列地址空间012中对关键字序列 22，41，53，46，30，13，1，67，5(1)构造哈希表(画示意图)；(2)装填因子；等概率下(3)成功的和(4)不成功的平均查找长度。
【北京工业大学 2000三(8 分)】【烟台大学 2007四、4(10 分)】（分数：2.00）_3.设散列表长度为 14，散列函数 （分数：2。

15、件中采用顺序查找法查找一个记录，其平均查找长度(ASL)为_。
【北京航空航天大学 2004 年】（分数：2.00）A.(n1)2B.n2C.(n+1)2D.n3.当采用分块查找时，数据的组织方式为_。
【太原科技大学 2007 年】（分数：2.00）A.数据分成若干块，每块内数据有序B.数据分成若干块，每块内数据不必有序，但块间必须有序，每块内最大(或最小)的数据组成索引块C.数据分成若干块，每块内数据有序，每块内最大(或最小)的数据组成索引块D.数据分成若干块，每块(除最后一块外)中数据个数需相同4.对有 2500 个记录的索引顺序表(分块表)进行查找，最理想的块长为_。
【华中科技大学 2007 年】（分数：2.00）A.50B.125C.500D.log 2 25005.下面关于二分查找的叙述正确的是_。
【南京理工大学 1996 年】（分数：2.00）A.表必须有序，表可以顺序方式存储，也可以链表方式存储B.表必须有序且表中数据必须是整型、实型或字符型C.表必须有序，而且只能从小到大排列D.表必须有序，且表只能以顺序方式存储6.当 n 足够大时，在。

16、2.n个顶点的连通无向图，其边的条数至少为_。
【哈尔滨工业大学 2000二、2(1 分)】（分数：2.00）_3.如果具有 n个顶点的图是一个环，则它有_棵生成树。
【中南大学 2005二、9(2 分)】（分数：2.00）_4.N个顶点的连通图的生成树含有_条边。
【中山大学 1998一、9(1 分)】（分数：2.00）_5.若无向图满足_。

17、大学 2001七(7 分)】（分数：2.00）_2.用关键字 1，2，3，4 的四个结点(1)能构造出几种不同的二叉排序树?其中(2)最优查找树有几种?(3)AVL树有几种?(4)完全二叉树有几种?试画出这些二叉排序树。
【北京工业大学 1997二、3(5 分)】（分数：2.00）_3.可以生成下图所示的二叉排序树的关键字初始序列有几种?试写出其中的任意 4种。
【电子科技大学2005三、2(6 分)】 （分数：2.00）_4.设二叉排序树中关键字由 1到 1000。

18、2.(1)对于有向无环图，叙述求拓扑有序序列的步骤；(2)对于以下的图，写出它的四个不同的拓扑有序序列。
【南开大学 1998二(12 分)】 （分数：2.00）_3.有向图的拓扑排序能否用图的深度搜索模式来查找?若能，请简述方法；若不能，请简述原因。
【西北大学 2000二、8(5 分)】（分数：2.00）_4.下图是带权的有向图 G的邻接表表示法，求：(1)以结点 V1出发深度遍历图 G所得的结点序列；(2)以结点 V1出发广度遍历图 G所得的结点序列；(3)从结点 V1到。

19、2.有一个 2000项的表，欲采用等分区间顺序查找方法进行查找，则每块的理想长度是 (1)，分成 (2) 块最为理想，平均查找长度是 (3) 。
【中国矿业大学 2000一、6(3 分)】（分数：2.00）_3.分块检索中，若索引表和各块内均用顺序查找，则有 900个元素的线性表分成_块最好；若分成 25块，其平均查找长度为_。
【北京工业大学 1999一、5(2 分)】（分数：2.00）_4.执行顺序查找时，储存方式可以是(1)，二分法查找时，要求线性表(2)，分块查找时要求线性表(3)，而散列表的查找，要求线性表。

20、V,E)中含有 7个顶点，要保证图 G在任何情况下都是连通的，则需要的边数最少是( )。
【2010 年全国试题 7(2分)】（分数：2.00）A.6B.15C.16D.213.对下图进行拓扑排序，可以得到不同拓扑序列的个数是( )。
【2010 年全国试题 8(2分)】 （分数：2.00）A.4B.3C.2D.14.下列关于图的叙述中，正确的是( )。
【2011 年全国试题 8(2分)】I回路是简单路径存储稀疏图，用邻接矩阵比邻接表更省空间若有向图中存在拓扑序列，则该图不存在回路（分数：2.00）A.仅B.仅 I、C.仅D.仅 I、5.对有 n个结点、e 条边且使用邻接表存储的有向图进行广度优先遍历，其算法时间复杂度是( )。
【2012 年全国试题 5(2分)】（分数：2.00）A.O(n)B.O(e)C.O(n+e)D.O(ne)6.若用邻接矩阵存储有向图，矩阵中主对角线以下的元素均为零，则关于该图拓扑序列的结论是( )。
【2012 年全国试题 6(2分)】（分数：2.00）A.存在，且唯一B.存在，且不唯一C.存在，可能不唯一D.无法确定是否存在7.对。