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

1、广度优先遍历算法类似于树的 .北京交通大学 2007分数:2.00A.中序遍B.先序遍历C.后序遍D.按层次遍历3.执行 操作时,需要使用队列作辅助存储空间.华中科技大学 2006一12 分分数:2.00A.查找哈希Hash表B.广度优先搜。

2、00A.要排序的数据量太大B.要排序的数据中含有多个相同值C.要排序的数据个数为奇数D.要排序的数据已基本有序3.当待排序列基本有序时,下列排序方法中 最好.北京邮电大学 2005 一10 2 分分数:2.00A.直接插入排序B.快速排序。

3、北京邮电大学 2005一92 分分数:2.00A.1B.2C.4D.n3.散列函数有一个共同的性质,即函数值应当以 取其值域的每个值.西安电子科技大学 2001计算机应用一72 分 北京邮电大学.1999 一42 分分数:2.00A.最大。

4、11,69,23,18D.68,11,69,23,18 93,732.适合并行处理的排序算法是 .西安电子科技大学 2005 一81 分电子科技大学 2005 一81 分分数:2.00A.选择排序B.快速排序C.希尔排序D.基数排序3.一。

5、2.求图的最小生成树有两种算法,算法适合于求稀疏图的最小生成树.南京理工大学 2001二62 分北京交通大学 2005二72 分分数:2.003.Prim普里姆算法适用于求的网的最小生成树;Kruskal克鲁斯卡尔算法适用于求的网的最小生成。

6、分数:2.00A.堆排序,冒泡排序B.快速排序,堆排序C.直接选择排序,归并排序D.归并排序,冒泡排序3.稳定的排序方法是 .北方交通大学 2000 二32 分分数:2.00A.直接插入排序和快速排序B.折半插入排序和起泡排序C.简单选择排。

7、2.设 S1S2 为串,请给出使 S12S2S1 成立的所有可能的条件为连接符.国防科技大学 1999一长沙铁道学院 1997三53 分分数:2.003.已知:sxyz,txz.试利用联结求子串和置换等基本运算,将 s转化为 t.北方交通大。

8、有 0 个或多个输入量B.健壮性C.正确性D.可行性3.下面程序的时间复杂性为 .南京理工大学 2004 一41 分forint i0;iA.On 2 B.OmnC.Om 2 D.Omn4.在下列算法中,xx2的执行次数是 .华中科技大学 。

9、数据元素有序2.当在一个有序的顺序存储表上查找一个数据时,即可用折半查找,也可用顺序查找,但前者比后者的查找速度 .南京理工大学 1997一72 分分数:2.00A.必定快B.不一定C.在大部分情况下要快D.取决于表递增还是递减3.请指出在。

10、华南理工大学 2007分数:2.00A.邮电图B.AOV网C.公路网D.AOE网3.关键路径是 AOE网中 .中南大学 2003一101 分分数:2.00A.从始点到终点的最短路径B.从始点到终点的最长路径C.从始点到终点的边数最多的路径。

11、2.下列函数是在无向图的邻接表中删除一条边的算法,请完善该程序. V0id deledgeALGraphG,int i, int j EdgeNodep,q; pG 一adj listifirstedge; iffG 一adjlistifi。

12、2.设结点个数为 n,请问采用堆排序法进行排序,其时间复杂性是多少请以大 O 形式给出,并给出证明.上海交通大学 2004 四10 分分数:2.00已知待排序的序列为503,87,512,6l,908,170,897,275,653,462。

13、于 x分的学生人数 int head1,mid,rearN; domidheadrear2; ifxaji; ifi3.下列算法是利用折半查找算法在一个有序表中插入一个元素 X,并保持表的有序性.请将程序中空白处填上适当的语句完成功能. i。

14、4的数据元素组 A14表示哈希表.1画出该哈希表的存储结构图;2假定每个元素的查找概率相等,计算查找成功时的 ASL;3计算查找不成功时的 ASL.华中科技大学 2007四2510分分数:2.002.采用哈希函数 Hk3k mod 13并用。

15、件中采用顺序查找法查找一个记录,其平均查找长度ASL为.北京航空航天大学 2004 年分数:2.00A.n12B.n2C.n12D.n3.当采用分块查找时,数据的组织方式为.太原科技大学 2007 年分数:2.00A.数据分成若干块,每块内。

16、2.n个顶点的连通无向图,其边的条数至少为.哈尔滨工业大学 2000二21 分分数:2.003.如果具有 n个顶点的图是一个环,则它有棵生成树.中南大学 2005二92 分分数:2.004.N个顶点的连通图的生成树含有条边.中山大学 199。

17、大学 2001七7 分分数:2.002.用关键字 1,2,3,4 的四个结点1能构造出几种不同的二叉排序树其中2最优查找树有几种3AVL树有几种4完全二叉树有几种试画出这些二叉排序树.北京工业大学 1997二35 分分数:2.003.可以生。

18、2.1对于有向无环图,叙述求拓扑有序序列的步骤;2对于以下的图,写出它的四个不同的拓扑有序序列.南开大学 1998二12 分 分数:2.003.有向图的拓扑排序能否用图的深度搜索模式来查找若能,请简述方法;若不能,请简述原因.西北大学 20。

19、2.有一个 2000项的表,欲采用等分区间顺序查找方法进行查找,则每块的理想长度是 1,分成 2 块最为理想,平均查找长度是 3 .中国矿业大学 2000一63 分分数:2.003.分块检索中,若索引表和各块内均用顺序查找,则有 900个元。

20、V,E中含有 7个顶点,要保证图 G在任何情况下都是连通的,则需要的边数最少是 .2010 年全国试题 72分分数:2.00A.6B.15C.16D.213.对下图进行拓扑排序,可以得到不同拓扑序列的个数是 .2010 年全国试题 82分 。