计算机专业基础综合数据结构

1、路归并排序D.冒泡排序3.下列内部排序算法中，在初始序列已基本有序(除去 n个元素中的某 k个元素后即呈有序，kn)的情况下，排序效率最高的算法是_。
（分数：1.00）A.冒泡排序B.堆排序C.直接插入排序D.二路归并排序4.下列排序算法中，_每一趟都能选出一个元素放在最终位置上，并且是不稳定的。
（分数：1.00）A.冒泡排序B.希尔排序C.简单选择排序D.直接插入排序5.下列排序方法中，时间复杂性不受数据初始状态影响，恒为 O(log 2 n)的是_。
（分数：1.00）A.堆排序B.冒泡排序C.直接选择排序D.快速排序6.下列排序算法中，某一趟结束后未必能选出一个元素放在其最终位置上的是_。
（分数：1.00）A.选择排序B.冒泡排序C.归并排序D.堆排序7.下列排序算法中，在每一趟都能选出一个元素放到其最终位置上，并且其时间性能受数据初始特性影响的是_。
（分数：1.00）A.直接插入排序B.归并排序C.直接选择排序D.堆排序对初始状态为递增序列的表按递增顺序排序，最省时间的是( 8 )算法，最费时间的是( 9 )算法。
A.堆。

2、 A.5 B.6 C.7 D.8（分数：1.00）A.B.C.D.3.下列关于无向连通图特性的叙述中，正确的是_。
所有顶点的度之和为偶数边数大于顶点个数减 1至少有一个顶点的度为 1 A.只有 B.只有 C.和 D.和（分数：1.00）A.B.C.D.4.对于具有 n(n1)个顶点的强连通图，其有向边的条数至少是_。
A.n+1 B.n C.n-1 D.n-2（分数：1.00）A.B.C.D.5.下列有关图的说法中正确的是_。
A.在图结构中，顶点不可以没有任何前驱和后继 B.具有 n个顶点的无向图最多有 n(n-1)条边，最少有 n-1条边 C.在无向图中，边的条数是结点度数之和 D.在有向图中，各顶点的入度之和等于各顶点的出度之和（分数：1.00）A.B.C.D.6.对于一个具有 n个顶点和 e条边的无向图，若采用邻接矩阵表示，则该矩阵大小是_，矩阵中非零元素的个数是 2e。
A.n B.(n-1)2 C.n-1 D.n2（分数：1.00）A.B.。

3、数目U /U。
A.n*n B.n(n+1) C.n/2 D.n*(n-1)（分数：2.00）A.B.C.D.3.在图采用邻接表存储时，求最小生成树的 Prim算法的时间复杂度为U /U。
A.O(n) B.O(n+e) C.O(n2) D.O(n3)（分数：2.00）A.B.C.D.4.若一个图的边集为(A，B)， (A，C)， (B，D)， (C，F)， (D，E)， (D，F)，则从顶点 A开始对该图进行广度优先搜索，得到的顶点序列可能为U /U。
A.A，B，C，D，E，F B.A，B，C，F，D，E C.A，B，D，C，E，F D.A，C，B，F，D，E（分数：2.00）A.B.C.D.5.已知有向图 G=(V，E)，其中 V=V1，V2，V3，V4，V5，V6，V7，E=V1，V2，V1，V3，V1，V4，V2，V5，V3，V5，V3V6，V4，V6，V5，V7，V6，V7)，G 的拓扑序列是U /U。
A.V1。

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，38，40，84)，则利用快速排序的方法，以第一个记录为基准得到的一次划分结果为 _ 。
（分数：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.数据序列(8，9，10，4，5，6，20，1，2)只能是下列排序算法中 _ 的两趟排序后的结果。
（分数：2.00）A.选择排序B.冒泡排序C.插入排序D.堆排序5.对一组数据(84，47，25，15，21)排序，数据的排列次序在排序的过程中的变化为 _ 。
(1)84 47 25 15 21 (2)1 5 47 25 84 21 (3)15 21 25 84 47 (4)1 5 21 25 47 84 则采用的排序是 _ 。
（分数：2.00）A.选择。

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，wan D.shi，bai，an，li，tang，deng，fang，wan（分数：2.00）A.B.C.D.2.以下关于希尔排序的说法中，正确的是_。
A.当待排序元素序列的初始排列基本有序时，希尔排序比直接插入排序快 B.当待排序元素序列的初始排列基本逆序时，希尔排序比直接插入排序快 C.当待排序元素序列的初始排列基本有序时，希尔排序比起泡排序快 D.当待排序元素序列的初始排列基本逆序时，希尔排序比起泡排序慢（分数：2.00）A.B.C.D.3.在内排序的过程中，通常需要对待排序元素序列的排序码做多趟扫描。
采用不同的排序方法将产生不同的排序中间结果，设要将集合tang，deng，an，wan，shi，bai，fang，li)中的排序码按升序排列，则_是以第一个元素为分界元素的快速排序一趟扫描的结果。

6、的算法?_ A.Prim(普里姆)算法 B.Kruskal(克鲁斯卡尔算法) C.罗巴赫算法 D.其他算法（分数：1.00）A.B.C.D.2.邻接表是图的一种_。
A.顺序存储结构 B.链接存储结构 C.索引存储结构 D.散列存储结构（分数：1.00）A.B.C.D.3.下面试图对图中路径进行定义，说法正确的是_。
A.由顶点和相邻顶点序列构成的边所形成的序列 B.由不同顶点所形成的序列 C.由不同边所形成的序列 D.上述定义都不是（分数：1.00）A.B.C.D.4.无向图中顶点个数为 n，那么边数最多为_。
A.n-1 B.n(n-1)/2 C.n(n+1)/2 D.n2（分数：1.00）A.B.C.D.5.在一个具有 n(n0)个顶点的连通无向图中，至少需要的边数是_。
A.n B.n+1 C.n-1 D.n/2（分数：1.00）A.B.C.D.6.以下叙述中正确的是_。
对有向图 G，如果以任一顶点出发进行一次深度优先或广度优先搜索能。

7、2.若查找每个记录的概率均等，则在具有 n 个记录的连续顺序文件中采用顺序查找法查找一个记录，其平均查找长度 ASL 为( )。
（分数：2.00）A.(n 一 1)2B.n2C.(n+1)2D.n顺序查找法适用于查找顺序存储或链式存储的线性表，平均比较次数为( (1) )，二分法查找只适用于查找顺序存储的有序表，平均比较次数为( (2) )。
在此假定为线性表中结点数，且每次查找都是成功的。
（分数：4.00）(1).(1)（分数：2.00）A.N+1B.2log 2 NC.log 2 ND.N2(2).(2)（分数：2.00）A.N+1B.2log 2 NC.log 2 ND.N23.适用于折半查找的表的存储方式及元素排列要求为( )。
（分数：2.00）A.链接方式存储，元素无序B.链接方式存储，元素有序C.顺序方式存储，元素无序D.顺序方式存储，元素有序4.具有 12 个关键字的有序表，折半查找的平均查找长度为( )。
（分数：2.00）A.31B.4C.25D.55.折半查找的时间复杂性为( )。
（分数：2.00）A.O(n 2 )B.O(n)C.O(。

8、2.下面是一个求最小生成树的算法，其中 G是连通无向图，T 是所求的生成树。
T：=G： While T 中存在回路 do begin在 T中找一条权值最大的边 e； T：=T 一e； (T 中去掉 e边) EnD 试问该算法是哪一种求最小生成树的算法?( )（分数：2.00）A.Prim(普里姆)算法B.Kruskal(克鲁斯卡尔算法)C.罗巴赫算法D.其他算法3.邻接表是图的一种( )。
（分数：2.00）A.顺序存储结构B.链接存储结构C.索引存储结构D.散列存储结构4.下面试图对图中路径进行定义，说法正确的是( )。
（分数：2.00）A.由顶点和相邻顶点序列构成的边所形成的序列B.由不同顶点所形成的序列C.由不同边所形成的序列D.上述定义都不是5.无向图中顶点个数为 n，那么边数最多为( )。
（分数：2.00）A.n一 1B.n(n一 1)2C.n(n+1)2D.n 26.在一个具有 n(n0)个顶点的连通无向图中，至少需要的边数是( )。
（分数：2.00）A.nB.n+1C.n一 1D.n27.以下叙述中正确的是( )。
I对有向。

9、二路归并排序（D）冒泡排序3 下列内部排序算法中，在初始序列已基本有序(除去 n 个元素中的某 k 个元素后即呈有序，kn)的情况下，排序效率最高的算法是( )。
（A）冒泡排序（B）堆排序（C）直接插入排序（D）二路归并排序4 下列排序算法中，( ) 每一趟都能选出一个元素放在最终位置上，并且是不稳定的。
（A）冒泡排序（B）希尔排序（C）简单选择排序（D）直接插入排序5 下列排序方法中，时间复杂性不受数据初始状态影响，恒为 O(nlog2n)的是( )。
（A）堆排序（B）冒泡排序（C）直接选择排序（D）快速排序6 下列排序算法中，某一趟结束后未必能选出一个元素放在其最终位置上的是( )。
（A）选择排序（B）冒泡排序（C）归并排序（D）堆排序7 下列排序算法中，在每一趟都能选出一个元素放到其最终位置上，并且其时间性能受数据初始特性影响的是( )。
（A）直接插入排序（B）归并排序（C）直接选择排序（D）堆排序7 对初始状态为递增序列的表按递增顺序排序，最省时间的是( (1) )算法，最费时间的是( (2) )算法。
8 (1)（A）堆排序（B）快速排序（C）插入排序（D）归并。

10、数为_，二分法查找只适用于查找顺序存储的有序表，平均比较次数为_。
在此假定 N 为线性表中结点数，且每次查找都是成功的。
（分数：4.00）A.N+1B.2log2NC.log2ND.N/2E.Nlog2NFN2A.N+1B.2log2NC.log2ND.N/2E.Nlog2NFN22.下面关于二分查找的叙述正确的是_。
（分数：2.00）A.表必须有序，表可以顺序方式存储，也可以链表方式存储B.表必须有序且表中数据必须是整型、实型或字符型C.表必须有序，而且只能从小到大排列D.表必须有序，且表只能以顺序方式存储二叉查找树的查找效率与二叉树的_有天，在_时查找效率最低。
（分数：4.00）A.高度B.结点的多少C.树形D.结点的位置A.结点太多B.完全二叉树C.呈单枝树D.结点太复杂3.当采用分块查找时，数据的组织方式为_。
（分数：2.00）A.数据分成若干块，每块内数据有序B.数据分成若干块，每块内数据不必有序，但块间必须有序，每块内最大(或最小)的数据组成索引块C.数据分成若干块，每块内数据有序，每块内最大(或最小)的数据组成索。

11、om(n)返回一个 0到 n-1之间的随机整数(包括 0与 n-1在内)。
（分数：10.00）(1).H(key)=key/n（分数：2.50）_(2).H(key)=1（分数：2.50）_(3).H(key)=(Key+random(n)%n（分数：2.50）_(4).H(key)=key%p(n)；其中 p(n)是不大于 n的最大素数（分数：2.50）_。

12、别设在这片内存空间的两端，这样，当 () 时，才产生上溢。
（分数：10.00）A空B满C.上溢D.下溢A空B满C.上溢D.下溢A.n-1BnC.n+1D.n/2A.长度B.深度C.栈顶D.栈底A.两个栈的栈顶同时到达栈空间的中心点B.其中一个栈的栈顶到达栈空间的中心点C.两个栈的栈顶在栈空间的某一位置相遇D.两个栈均不空，且一个栈的栈顶到达另一个栈的栈底1.设 abcdef 以所给的次序进栈，若在进栈操作时，允许退栈操作，则下面得不到的序列为_。
（分数：2.00）A.fedcbaB.bcafedC.dcefbaD.cabdef2.栈在_中应用。
（分数：2.00）A.递归调用B.子程序调用C.表达式求值D.以上都是3.表达式 a*(b+c)-d 的后缀表达式是_。
（分数：2.00）A.abcd*+-B.abc+*d-C.abc*+d-D.-+*abcd4.用链接方式存储的队列，在进行删除运算时_。
（分数：2.00）A.仅修改头指针B.仅修改尾指针C.头、尾指针都要修改D.头、尾指针可能都要修改5.设 A 是 nn 的对称矩阵，将 A 。

13、删除和查找2.在线性表中的每一个表元素都是数据对象，它们是不可再分的_。
（分数：2.00）A.数据项B.数据记录C.数据元素D.数据字段3.对于顺序存储的线性表，其算法的时间复杂度为 O(1)的运算应是_。
（分数：2.00）A.将 n 个元素从小到大排序B.从线性表中删除第 i 个元素(1in)C.查找第 i 个元素(1in)D.在第 i 个元素后插入一个新元素(1in)4.下面的叙述正确的是_。
（分数：2.00）A.线性表在链式存储时，查找第 i 个元素的时间同 i 的值无关B.线性表在链式存储时，查找第 i 个元素的时间同 i 的值成反比C.线性表在顺序存储时，查找第 i 个元素的时间同 i 的值成正比D.线性表在顺序存储时，查找第 i 个元素的时间同 i 的值无关通常查找线性表数据元素的方法有 () 和 () 两种方法，其中 () 是一种只适合于顺序存储结构但 () 的方法；而 () 是一种对顺序和链式存储结构均适用的方法。
（分数：6.00）A.顺序查找B.循环查找C.条件查找D.折半查找A.顺序查找B.随机查找C.折半查找D.。

14、则此二叉树中所包含的结点个数至少有_；已知二叉树有 50个叶结点，有 30个度为 1的结点，则该二叉树的总结点数为_。
（分数：5.00）A.2d+1B.2d-1C.2d-1D.2d-1A.129B.130C.131D.1321.设森林中有三棵树，第一、第二和第三棵树中的结点个数分别为 m1、m2 和 m那么在由该森林转化成的二叉树中根结点的右子树上的结点个数是_。
（分数：2.50）A.m1+m2B.m2+m3C.m3+m1D.m1+m2+m32.用 n个权值构造出来的 Huffman树的结点个数是_。
（分数：2.50）A.2n-1B.2nC.2n+1D.n+13.在下列关于二叉树遍历的说法中错误的是_。
（分数：2.50）A.在一棵二叉树中，假定每个结点最多只有左子女，没有右子女，对它分别进行前序遍历和后序遍历，则具有相同的遍历结果B.在一棵二叉树中，假定每个结点最多只有左子女，没有右子女，对它分别进行中序遍历和后序遍历，则具有相同的遍历结果C.在一棵二叉树中，假定每个结点最多只有左子女，没有右子女，对它分别进行前序遍历和按层遍历，则。

15、堆排序、快速排序、归并排序的关系是( )。
（A）堆排序快速排序归并排序（B）堆排序归并排序快速排序（C）堆排序归并排序快速排序（D）堆排序快速排序归并排序3 一组记录的关键码为(25，48，16，35，79，82，23，40，36，72)，其中，含有5 个长度为 2 的有序表，按归并排序的方法对该序列进行一趟归并后的结果为( )。
（A）16，25，35，48，23，40，79，82，36，72（B） 16，25，35，48，79，82，23，36，40，72（C） 16，25，48，35，79，82，23，36，40，72（D）16，25，35，48，79，23，36，40，72，824 已知 10 个数据元素为(54，28，16，34，73，62，95，60，26，43)，对该序列按从小到大排序，经过一趟冒泡排序后的序列为( )。
（A）16，28，34，54，73，62，60，26，43，95（B） 28，16，34，54，62，73，60，26，43，95（C） 28，16，34，54，62，60，73，26，43，95（D）16，28，34，54，62，6。

16、(2).从顺序表中删除第 i个元素并由函数返回被删元素的值。
如果 i不合理或顺序表为空则显示出错信息并退出运行。
（分数：4.00）_(3).向顺序表中第 i个位置插入一个新的元素 x。
如果 i不合理则显示出错信息并退出运行。
（分数：4.00）_(4).从顺序表中删除具有给定值 x的所有元素。
（分数：4.00）_(5).从顺序表中删除其值在给定值。

17、(2).编号为 i 的结点的父结点(若存在)的编号是多少?（分数：4.00）_(3).编号为 i 的结点的第 k 个子女结点(若存在)的编号是多少?（分数：4.00）_(4).编号为 i 的结点有右兄弟的条件是什么?其右兄弟结点的编号是多少?（分数：4.00）_(5).若结点个数为 n。

18、2.采用简单选择排序，比较次数与移动次数分别为( )。
（分数：2.00）A.O(n)，O(log 2 n)B.O(log 2 n)，O(n 2 )C.O(n 2 )，O(n)D.O(nlog 2 n)，O(n)3.就排序算法所用的辅助空间而言，堆排序、快速排序、归并排序的关系是( )。
（分数：2.00）A.堆排序快速排序归并排序B.堆排序归并排序快速排序C.堆排序归并排序快速排序D.堆排序快速排序归并排序4.一组记录的关键码为(25，48，16，35，79，82，23，40，36，72)，其中，含有 5 个长度为 2 的有序表，按归并排序的方法对该序列进行一趟归并后的结果为( )。
（分数：2.00）A.16，25，35，48，23，40，79，82，36，72B.16，25，35，48，79，82，23，36，40，72C.16，25，48，35，79，82，23，36，40，72D.16，25，35，48，79，23，36，40，72，825.已知 10 个数据元素为(54，28，16，34，73，62，95，60，26，43)，对。

19、简单无向图，在其邻接矩阵中共有_个零元素，该邻接矩阵是一个_。
而用邻接矩阵存储有向图时某一个顶点 i 的入度等于该矩阵的_。
（分数：8.00）A.权值B.顶点C边D.边与顶点均AeB.2eC.n2-eD.n2-2eA.上三角矩阵B.稀疏矩阵C.对角矩阵D.对称矩阵A.第 i 行中值为 1 的元素个数B.所有值为 1 的元素总是C.第 i 行及第 i 列中值为 1 的元素总个数D.第 i 列中值为 1 的元素个数图的深度优先搜索类似于树的_次序遍历，图的广度优先搜索类似于树的_次序遍历。
（分数：4.00）A.先根B.中根C.后根D.层次A.先根B.中根C.后根D.层次一个连通图的生成树是包含图中所有顶点的一个_子图。
n(n1)个顶点的强连通图中至少含有_条有向边。
（分数：4.00）A.极小B.连通C.极小连通D.无环A.n-1BnC.n(n-1)/2D.n(n-1)1.在一个带权连通图 G 中，权值最小的边一定包含在 G 的_生成树中。
（分数：2.00）A.最小B.任何C.广度优先D.深度优先在用 Dijk。

20、2.下面给出的 4 种排序方法中，( )排序法是不稳定性排序法。
（分数：2.00）A.插入B.冒泡C.二路归并D.堆3.下列内部排序算法中，其比较次数(或交换次数)与序列初态无关的算法是( )。
（分数：2.00）A.快速排序B.直接插入排序C.二路归并排序D.冒泡排序4.下列内部排序算法中，在初始序列已基本有序(除去 n 个元素中的某 k 个元素后即呈有序，kn)的情况下，排序效率最高的算法是( )。
（分数：2.00）A.冒泡排序B.堆排序C.直接插入排序D.二路归并排序5.下列排序算法中，( )每一趟都能选出一个元素放在最终位置上，并且是不稳定的。
（分数：2.00）A.冒泡排序B.希尔排序C.简单选择排序D.直接插入排序6.下列排序方法中，时间复杂性不受数据初始状态影响，恒为 O(nlog 2 n)的是( )。
（分数：2.00）A.堆排序B.冒泡排序C.直接选择排序D.快速排序7.下列排序算法中，某一趟结束后未必能选出一个元素放在其最终位置上的是( )。
（分数：2.00）A.选择排序B.冒泡排序C.归并排序D.堆排序8.下列排序算法中，在每一趟都能选出一个元素放。