网站首页资讯习题 正文

1-预备知识 [01:50:21 18段]

资料与测验随堂测验

1、以下各语言书写的代码可认为其功能是相同的。对于该代码，哪项判断是正确的？ C/C++： #include <stdio.h> int hehe(){ printf("hehe"); hehe(); return 0; } int main(){ hehe(); return 0; } Java语言： public class Main{ public static int hehe() { System.out.println("hehe"); hehe(); return 0; } public static void main(String args[]) { hehe(); } } Python语言： def hehe(): print("hehe") hehe() return 0 hehe()
    A、代码有错，无法运行。
    B、代码可以运行，并在有限次函数调用后结束。
    C、代码可以运行，将产生无限次函数递归调用（不考虑机器出故障、停电等意外因素）。
    D、以上都不对。

2、函数必须有返回值。

2-数组与字符串 [02:49:24 30段]

资料与测验随堂测验

1、这道题是给使用C/C++语言的同学准备的。使用其他语言的同学，随便猜一项答案就好啦。 以下C/C++代码： void func(_______ , int); int main( ){ int array[10][20]; int n; // 省略array和n的初始化 func(array, n); return 0; } 第1行的函数原型（函数声明）中，______部分的第一个参量应该是
    A、int [ ][ ]
    B、int **
    C、int *[20]
    D、int (*)[20]

2、这道题是给使用Java语言的同学准备的。使用其他语言的同学，随便猜一项答案就好啦。 以下语句，正确的是：
    A、int a1[][] = new int[3][4];
    B、int a2[3][4] = new int[][];
    C、int a3[][4] = new int[3][];
    D、int a4[3][] = new int[][4];

3、以下哪个正则表达式与字符串 a 不匹配？
    A、abc
    B、[abc]
    C、[a-z]
    D、a*

3-线性结构 [05:20:03 47段]

资料与测验随堂测验

1、顺序表不适合进行下列哪种操作？
    A、随机查找（即：查找表中第k项元素）
    B、顺序查找（即：从表头开始依次查找每一项）
    C、随机插入或删除（即：在表中第k个位置插入元素或删除表中第k项元素）
    D、尾部插入或删除（即：在表尾插入元素或删除表尾元素）

2、单链表不适合进行下列哪种操作？
    A、顺序查找（即：从表头开始依次查找每项元素）
    B、表头插入或删除（即：在表头插入元素或删除表头元素）
    C、表中插入或删除（即：对于给出位置的表中某元素a，在a之后插入元素或删除a之后的一个元素）
    D、表尾插入或删除（即：在表尾插入元素或删除表尾元素）

3、“栈”是后进后出表。

4、“队列”是先进先出表。

5、循环队列的实现，必然是当“队列满”的时候，顺序表（数组）中还有一个空位置。

6、顺序栈的初始化，必定是 top = -1

期中考试（占总评40%）

数据结构与算法实战期中考试

1、一棵AVL树的前序遍历序列是20,5,1,10,30 ，中序遍历序列是 1,5,10,20,30 ， 则插入数字8之后，该树应该做哪一种旋转？
    A、LL旋转
    B、LR旋转
    C、RL旋转
    D、RR旋转

2、以下说法正确否？请选出一项你认为最合适的答案
    A、未排序的数组进行二分查找的时间复杂度是O(N)
    B、二叉搜索树中查找元素x的时间复杂度是O(logN)
    C、AVL树中查找元素x的时间复杂度是O(logN)
    D、所有说法都正确

3、对一棵非空二叉树T，若T的度为2的结点有40个，则T中叶子结点的个数
    A、一定是39
    B、一定是40
    C、一定是41
    D、未定，跟二叉树的形态相关

4、如果一个线性表最常用的操作是访问一个随机位置、插入和删除最后一个元素，则最有效率的数据结构是
    A、双链表
    B、单向循环链表
    C、带有空头结点的双向循环链表
    D、顺序表

5、对于有N个节点的单链表，时间复杂度为O(N) 的操作是
    A、在p指针指向的节点之后插入一个新节点
    B、删除p指针指向的节点之后的一个节点
    C、删除头节点
    D、删除p指针所指向的节点（p指向的不是头节点）

6、元素A B C D依次入栈，出栈时机随意，则以下（ ）是不可能的出栈序列。
    A、ABCD
    B、DCBA
    C、DCAB
    D、ABDC

7、以下这段程序：for(i=0; i<=n; i++) // i从0到n的外循环，每次i递增1 for(j=i; j>=0; j/=2) // j从i到0的内循环， 每次 j变为上一次的一半 printf("%d\n", j); // 打印j 时间复杂度是：
    A、
    B、
    C、
    D、

8、若某二叉树的中序遍历序列是 DBACE ，则可以推断出的结论是
    A、该树的根结点是结点A
    B、该树的左子树的最左边结点是结点D
    C、结点E一定不是该树的左子树的结点
    D、该树共有三层

9、采用顺序存储的栈 ，若数组容量是 MaxSize，栈初始化时操作是 top=0 , 则判断栈满的语句是
    A、top == 0
    B、top == -1
    C、top == MaxSize - 1
    D、top == MaxSize

10、如果一组数据的最常用的操作，是在这组数当中删除值为x的元素（并且，不要求保持该组数据的次序），则以下四种数据结构中，哪一种最适合这个操作？
    A、单链表
    B、双链表
    C、双向循环链表
    D、顺序表

11、以下两段代码： A： for (int i=0; i<10; i++) printf("*"); //循环打印10个* B： for (int i=0; i<10000; i++) printf("*"); //循环打印10000个*的时间复杂度都是O(1）吗？ 以下说法正确的是：
    A、不是O(1)。A代码的时间复杂度是O(10)，B代码的时间复杂度是O(10000)。
    B、都是O(1)，表示运行时间都是1。
    C、都是O(1)，表示运行时间都是常数，也就是说A代码和B代码的运行时间相同。
    D、都是O(1)，表示运行时间是常数，意思是说，两段代码的运行时间，不随着问题规模N的变化而变化。

12、已知一棵二叉树的先序遍历序列是ABC,　则以下哪个序列是不可能的中序遍历序列？请选择最佳答案。
    A、ABC
    B、CBA
    C、CAB
    D、选项中有两个以上（包括两个）序列是不可能的中序序列。

13、以下时间复杂度最高的是
    A、
    B、
    C、
    D、

14、表达式3+2*5-3*(5-2) 对应的逆波兰式（后缀式）是
    A、25*352-*3+-
    B、325*+352-*-
    C、25*3+-(352-*)
    D、325352*-*+-

15、循环队列是用单向循环链表实现的。

16、二叉搜索树的最小值一定在其左子树上。

17、后缀式 1 2 + 3 * 4 - 5 / 的值是（只填写值，不要填写等号、空格等无关字符；使用英文半角数字——如123等，不要使用全角数字——如１２３等）

18、一棵树的后序遍历序列是 FDEBGCA , 其中序遍历序列是 FDBEACG , 则它的前序遍历序列是（参照题干的格式使用英文半角大写字母，中间不要填写空格、逗号等无关字符，不要使用全角字母——例如ＡＢＣ等）

19、一棵10层的二叉树（层数从1开始计算），最多有_____个节点 （填写半角英文阿拉伯数字——如123等，不要添加正负号、空格等无关字符，不要使用全角数字——如１２３等）

20、将序列{5, 2, 7, 3, 4, 1, 9, 8}中的数字按序一个一个插入到初始为空的二叉搜索树中，所得到的树的中序遍历序列是____ （填写英文半角数字，中间不填写空格、逗号等，两边不要加括号，例如——123，不要使用全角数字——例如１２３等）

期末考试（占总评60%）

数据结构与算法实战期末考试

1、以下这段代码 for(i=0; i<N; i++) //i从0循环到N-1，每次循环 +1 for(j=i; j<N; j+=j) //j从i循环到N-1，每次循环 +j printf("%d,%d\n", i, j); // 打印i和j 的时间复杂度是：
    A、
    B、
    C、
    D、

2、由分别带权为3、5、8、10的四个叶子结点构成一棵哈夫曼树，该树的带权路径长度为：
    A、26
    B、34
    C、50
    D、52

3、以下对于堆和哈夫曼树的描述，正确的是：
    A、堆一定是一棵完全二叉树，因此适合采用链式存储实现。
    B、堆的任意非叶节点的左右子树（如果非空）互换，仍然是堆。
    C、哈夫曼树中没有度为1的结点。
    D、哈夫曼树的叶结点一定都在同一层。

4、以下排序算法中，额外空间复杂度最高的是：
    A、简单选择排序
    B、快速排序
    C、冒泡排序
    D、归并排序

5、以下排序算法中，平均时间复杂度与最坏情况下时间复杂度不相同的是：
    A、简单选择排序
    B、冒泡排序
    C、归并排序
    D、快速排序

6、以下排序算法，稳定的是：
    A、快速排序
    B、归并排序
    C、希尔排序
    D、堆排序

7、以下不属于贪心法求解的问题是：
    A、构造哈夫曼树
    B、无负边的图中求解单源最短路径（Dijkstra法）
    C、Prim法求解最小生成树
    D、八皇后问题

8、将元素序列{20，1，35，56，12，7，29，82，666，2223} 按顺序插入一个初始为空的、大小为13的散列表中。散列函数为： H(key) = key % 13 。当第一次发现冲突时，正要插入散列表的元素是：
    A、7
    B、20
    C、56
    D、82

9、给定如下图所示的有向图 哪一项是该图的拓扑排序序列：
    A、ACFBDEG
    B、BEADCFG
    C、ABCDFEG
    D、BADCEGF

10、假设某顺序栈的栈顶下标为top，则栈的初始化操作是：
    A、一定是 top = 0
    B、一定是 top = -1
    C、top = 0 或 top = -1 都可以，与之相对应的，栈满也有两种不同的表示方法
    D、其它三个说法都不正确

11、关于最小生成树，说法正确的是：
    A、一个连通图的最小生成树必定是唯一的
    B、一个连通图的最小生成树有可能不唯一，但不同最小生成树的各边权值之和必定相等
    C、一个图有最小生成树，则这个图必定没有环
    D、其它三个说法都不正确

12、以下不属于分治法（或一般不用分治法求解）的是：
    A、快速排序
    B、归并排序
    C、求集合元素中第K大的数
    D、迷宫路径探索问题

13、对一棵非空二叉树T，若T的叶子节点有20个，则T中度为2的节点个数：
    A、一定是19
    B、一定是20
    C、一定是21
    D、未定，跟二叉树的形态相关

14、“不相交集”（也叫“并查集”）中，在查找时要进行路径压缩，则关于求并（union）运算，以下说法正确的是：
    A、按高度求并（union-by-height）不适用
    B、按大小求并（union-by-size）不适用
    C、按大小求并（union-by-size）和 按高度求并（union-by-height） 都不适用
    D、按大小求并（union-by-size）和 按高度求并（union-by-height） 都适用

15、基于比较的排序的最坏情况时间复杂度的下限是：
    A、
    B、
    C、
    D、

16、如果输入元素的顺序是 A B C D E， 要想使得输出元素的顺序是 A B C D E，则以下说法正确的是：
    A、只能使用栈（Stack）
    B、只能使用队列（Queue）
    C、栈和队列都可以使用
    D、栈和队列都不可以使用

17、对于二叉搜索树（Binary Search Tree），以下说法正确的是：
    A、二叉搜索树的查找时间效率是
    B、二叉搜索树的前序遍历序列，是从小到大排列的
    C、二叉搜索树的查找算法与二分法查找是等价的
    D、同样一组数据，如果按照不同顺序插入到一棵初始状态为空的二叉搜索树当中，则产生的二叉搜索树形态有可能不同。

18、对于经常需要求顶点入度的稀疏图，比较适合的存储结构是：
    A、邻接矩阵
    B、邻接表
    C、逆邻接表
    D、顺序表（数组）存储的邻接矩阵的上三角或下三角部分

19、要想删除最大堆（优先队列）中的某个不在堆顶的元素，恰当的操作是：
    A、直接删除，然后从该元素的子树中找一个合适的元素放入被删元素的位置。
    B、直接删除，然后把堆的最末位置的元素放入被删元素的位置，再做调整。
    C、将元素的值调整到足够大，使元素上升到堆顶，然后删除堆顶
    D、将元素的值调整到足够小，使元素下沉到堆的末尾，然后删除堆末尾。

20、如下图所示，插入元素5之后，AVL树进行旋转 这个旋转是：
    A、LL旋转（LL单旋、左左单旋）
    B、RR旋转（RR单旋、右右单旋）
    C、LR旋转（LR双旋、左右双旋）
    D、RL旋转（RL双旋、右左双旋）

21、以下各树，不是堆的有：
    A、
    B、
    C、
    D、

22、能与字符串 abcaabc#xyyzzy 匹配的正则表达式有：
    A、[a-z]*#[a-z]*
    B、[abc]*#[xyz]*
    C、abc*#xyyzzy
    D、[a-z]*

23、对于下图： 以下哪些选项是从顶点B出发的深度优先搜索序列：
    A、B F C A G D E
    B、B F G C A E D
    C、B A C F G D E
    D、B A D C F G E

24、对于下图： 以下哪些选项是从顶点B出发的广度优先搜索序列：
    A、B A D E F C G
    B、B F D E A G C
    C、B A D E F G C
    D、B A C F G D E

25、对于下图： 使用Kruskal算法去最小生成树，我们选择加入生成树的第三条边有可能是：
    A、(A, B)
    B、(C, D)
    C、(B, D)
    D、(A, D)

26、最大堆（大顶堆、max-heap）从根结点到其它任一结点的路径上的所有结点值是从大到小排列的。

27、一棵有9层结点的完全二叉树（层次从1开始计数），至少有255个结点。

28、若有向图G存在拓扑排序序列，则G一定是弱连通的。

29、AVL树T的最小元素一定位于树根的左子树。

30、图的深度优先遍历非递归算法通常采用栈实现，广度优先遍历非递归算法通常采用队列实现。

31、一个无向图G，若某顶点v到其它每个顶点都有至少一条路径，则图G只有1个连通分量。

32、若图G为连通图，则G的生成树是G的包含全部n个顶点的一个极大联通子图。

33、若图G为连通图且不存在拓扑排序序列，则图G必有环。

34、如果获知二叉树前、中、后序遍历序列的任意两种，一定可以确定第三种。

35、有向图的邻接矩阵是对称矩阵。

36、如果无向完全图G中有78条边，则G的生成树有_______ 条边。（填写半角阿拉伯数字如1234567890，不要添加空格等其它字符）

37、一棵二叉树的前序遍历序列是ABDFECGHK，中序遍历序列是DBEFAGHCK，则它的后序遍历序列是 _________. (填写半角大写字母且不要添加空格，格式如ABCDEFG）.

38、对于下图： 使用Prim算法从顶点W开始获取最小生成树， 我们选择加入生成树的第二条边的权值是__________

39、后缀式（postfix expression，也叫逆波兰式， reverse Polish notation）1 2 + 3 4 - / 5 6 * + 的值是____________. (如果结果不是整数，四舍五入保留一位小数。如结果为正数，不需要添加+号。请使用半角阿拉伯数字、小数点和负号如-012345.6789填写，不要添加空格等其它字符)

40、若一个无向图有10个顶点、2个连通分量，则这个图最多有__________条边。