考研类试卷计算机专业基础综合数据结构

1、找顺序存储或链式存储的线性表,平均比较次数为 1 ,二分法查找只适用于查找顺序存储的有序表,平均比较次数为 2 .在此假定为线性表中结点数,且每次查找都是成功的.2 1AN1B 2log2NC log2NDN23 2AN1B 2log2NC。

2、 A.5 B.6 C.7 D.8分数:1.00A.B.C.D.3.下列关于无向连通图特性的叙述中,正确的是.所有顶点的度之和为偶数边数大于顶点个数减 1至少有一个顶点的度为 1 A.只有 B.只有 C.和 D.和分数:1.00A.B.C.D。

3、数目U U. A.nn B.nn1 C.n2 D.nn1分数:2.00A.B.C.D.3.在图采用邻接表存储时,求最小生成树的 Prim算法的时间复杂度为U U. A.On B.One C.On2 D.On3分数:2.00A.B.C.D.4。

4、A.75,65,30,15,25,45,20,10B.75,65,45,10,30,25,20,15C.75,45,65,30,15,25,20,10D.75,45,65,10,25,30,20,153.一组记录的关键码为46,79,56。

5、为 4的希尔排序一趟扫描的结果. A.an,bai,deng,fang,li,shi,tang,wan B.an,tang,deng,wan,shi,bai,fang,li C.li,deng,an,shi,bai,fang,tang,wa。

6、的算法 A.Prim普里姆算法 B.Kruskal克鲁斯卡尔算法 C.罗巴赫算法 D.其他算法分数:1.00A.B.C.D.2.邻接表是图的一种. A.顺序存储结构 B.链接存储结构 C.索引存储结构 D.散列存储结构分数:1.00A.B。

7、数为,二分法查找只适用于查找顺序存储的有序表,平均比较次数为.在此假定 N 为线性表中结点数,且每次查找都是成功的.分数:4.00A.N1B.2log2NC.log2ND.N2E.Nlog2NFN2A.N1B.2log2NC.log2ND。

8、omn返回一个 0到 n1之间的随机整数包括 0与 n1在内.分数:10.001.Hkeykeyn分数:2.502.Hkey1分数:2.503.HkeyKeyrandomnn分数:2.504.Hkeykeypn;其中 pn是不大于 n的最大。

9、别设在这片内存空间的两端,这样,当 时,才产生上溢.分数:10.00A空B满C.上溢D.下溢A空B满C.上溢D.下溢A.n1BnC.n1D.n2A.长度B.深度C.栈顶D.栈底A.两个栈的栈顶同时到达栈空间的中心点B.其中一个栈的栈顶到达栈。

10、删除和查找2.在线性表中的每一个表元素都是数据对象,它们是不可再分的.分数:2.00A.数据项B.数据记录C.数据元素D.数据字段3.对于顺序存储的线性表,其算法的时间复杂度为 O1的运算应是.分数:2.00A.将 n 个元素从小到大排序B。

11、则此二叉树中所包含的结点个数至少有;已知二叉树有 50个叶结点,有 30个度为 1的结点,则该二叉树的总结点数为.分数:5.00A.2d1B.2d1C.2d1D.2d1A.129B.130C.131D.1321.设森林中有三棵树,第一第二和。

12、2.从顺序表中删除第 i个元素并由函数返回被删元素的值.如果 i不合理或顺序表为空则显示出错信息并退出运行.分数:4.003.向顺序表中第 i个位置插入一个新的元素 x.如果 i不合理则显示出错信息并退出运行.分数:4.004.从顺序表中删。

13、2.编号为 i 的结点的父结点若存在的编号是多少分数:4.003.编号为 i 的结点的第 k 个子女结点若存在的编号是多少分数:4.004.编号为 i 的结点有右兄弟的条件是什么其右兄弟结点的编号是多少分数:4.005.若结点个数为 n。

14、2.若查找每个记录的概率均等,则在具有 n 个记录的连续顺序文件中采用顺序查找法查找一个记录,其平均查找长度 ASL 为 .分数:2.00A.n 一 12B.n2C.n12D.n顺序查找法适用于查找顺序存储或链式存储的线性表,平均比较次数为。

15、2.下面是一个求最小生成树的算法,其中 G是连通无向图,T 是所求的生成树. T:G: While T 中存在回路 do begin在 T中找一条权值最大的边 e; T:T 一e; T 中去掉 e边 EnD 试问该算法是哪一种求最小生成树的。

16、简单无向图,在其邻接矩阵中共有个零元素,该邻接矩阵是一个.而用邻接矩阵存储有向图时某一个顶点 i 的入度等于该矩阵的.分数:8.00A.权值B.顶点C边D.边与顶点均AeB.2eC.n2eD.n22eA.上三角矩阵B.稀疏矩阵C.对角矩阵D。

17、二路归并排序D冒泡排序3 下列内部排序算法中,在初始序列已基本有序除去 n 个元素中的某 k 个元素后即呈有序,kn的情况下,排序效率最高的算法是 .A冒泡排序B堆排序C直接插入排序D二路归并排序4 下列排序算法中, 每一趟都能选出一个元素。

18、堆排序快速排序归并排序的关系是 .A堆排序快速排序归并排序B堆排序归并排序快速排序C堆排序归并排序快速排序D堆排序快速排序归并排序3 一组记录的关键码为25,48,16,35,79,82,23,40,36,72,其中,含有5 个长度为 2。

19、2.采用简单选择排序,比较次数与移动次数分别为 .分数:2.00A.On,Olog 2 nB.Olog 2 n,On 2 C.On 2 ,OnD.Onlog 2 n,On3.就排序算法所用的辅助空间而言,堆排序快速排序归并排序的关系是 .分。

20、2.下面给出的 4 种排序方法中, 排序法是不稳定性排序法.分数:2.00A.插入B.冒泡C.二路归并D.堆3.下列内部排序算法中,其比较次数或交换次数与序列初态无关的算法是 .分数:2.00A.快速排序B.直接插入排序C.二路归并排序D。