热门标签 | HotTags
当前位置:  开发笔记 > 编程语言 > 正文

大连海事大学2019计算机考研,大连海事大学计算机考研——选择部分

题型判断(20*1)选择(10*2)简答(含树和森林的转化,时间复杂度,二叉排序树,平衡二叉树,KMP,Has

题型判断(20*1)+ 选择(10*2)+简答(含树和森林的转化,时间复杂度,二叉排序树,平衡二叉树,KMP,Hash表,程序输出)+证明(15*1) + 编程(15*1)

选择

Head Tail运算从一个表中,用Head(H),Tail(T)分离出一个元素原则:H操作提取第一个元素(原子或广义表);T操作去掉第一个元素(原子或广义表);写顺序是从后往前写例1,L=((( (a,b), e , ( (x), d) ))) 从中提取x初始:((( (a,b), e , ( (x), d) )))第一步,HH(去两个括号):( (a,b), e , ( (x), d) )第二步,T(去掉首元素): ( e , ( (x), d) )第三步,T (去掉首元素): ( ( (x), d) )第四步,H (提取首元素): ( (x), d)第五步,H (提取首元素): (x)第六步,H (提取首元素): x综上,从表中提取X的步骤为:HHHTTHH

2. 二维数组

二维数组,列(行)序为主序顺序存储,告诉一个点的地址,

每个元素占几个存储单元,求另一个点的地址。

分析:这种的画图做就可以,仔细些,难度不大。

3. 单链表存储队列

不带头的单链表存储队列,队头指向队头结点,队尾指向队尾结点,

在进行插入操作时:只需修改队尾指针

分析:链表是顺序存储,插入只能在队尾插入,因此只需要移动队尾指针

4.循环队列

循环队列是【0..m】,则数组的长度是m+1;

因为是队列,所以进队从后面进,移动rear指针;出队从前面出,移动front指针

5.折半查找

有序,顺序表,折半查找, 27个元素, 查找失败时,至少需要与关键字比较的次数:27

分析:折半查找查找失败至少需要与关键字的比较次数:log2(x)向下取整

6.m阶B树

1.非终端结点至多有m个指针,m-1个关键字

至少有(m/2向上取整)个指针,(m/2向上取整)-1 个关键字

2.根结点,至少两个指针(分支),1个关键字

3.所有叶子节点都在同一层上,且不带任何信息。

7.四维数组

例:四维数组B【1..3,2..8,0..5,1..8】以行主序 顺序存储,每个元素占2个存储单元,B【1,4,0,1】地址2000,则B【2,3,4,5】地址?

分析:四维数组B【1..3,2..8,0..5,1..8】(3,7,6,8)(3-1+1,8-2+1,5-0+1,8-1+1)

2000+【(2-1)*7*6*8 + (3-4)*6*8 + (4-0)*8 + (5-1)】*2 = 2648

8.排序

1.冒泡排序:逆序的情况下,比较次数最多

2.比较次数

最好的情况:直接插入排序: O(n)

冒泡:O(n) //最好,直接插,冒的好,即原数列有序

简单选择排序:O(n) //与原始序列无关(折半插入同样无关)

快速:O(n)

希尔: O(n)

归并: O【(log2(n)】

3.时间复杂度

平均情况:快速,希尔,归并,堆 (快些归队): O【nlog2(n)】

其他: O(n)

最坏情况:快速O(n),其他与平均相同

最好情况:简单插入排序:O(n)

4.空间复杂度

快速: O【log2(n)】

归并: O(n),

基数: O(rd),

其余: O(1)

5.辅助空间

堆排序 O(1)

直接选择排序O(1)

归并排序O(1)

快速排序O(log2n)

直接插入排序O(1)

5.每一趟都可以选出一个元素放到其最终位置上的是:

交换类(冒泡,快速)、选择类(简单选择,堆)

6.{50,80,30,40,70,60},快速排序,以第一个为基准,一趟后的结果:

77fe9f977e8e9bd7258dc1c59f236935.png快速排序

9. 查找

对长度为n的顺序表进行顺序查找时,查找失败需要与键值的比较次数:n+1

折半查找,查找失败至少需要的比较次数:log2(n)向下取整

10. 图

例1.G是有8个顶点的非连通简单无向图,该图最多有( 21 )条边

分析:全连通图 边 M 和 点N的关系满足:M = N(N-1) /2

反过来看,即问有()条边,最少有8个点

M = (16-21) , N ≥ 7 ;( 7对应的最大是21,最小是6对应的+1,15+1 = 16)

即当M有(16 -21)条边,连通图最少有 7个顶点, 非连通图最少有8个顶点

所以,M最大为21

例2.G是一个非连通无向图,共有(22-28)条边,该图至少有( 9 )个顶点。

分析:全连通图 边 M 和 点N的关系满足:M = N(N-1) /2

当M = (22-28), N(N-1) /2 ≥(22-28),解得:8≤N<9,即N = 8

因为非连通,所以连通的加1,即8+1 = 9

11. 循环队列

大小为6的数组实现循环队列,front = 3 ,rear = 0;删除一个,进队三个,

front = ? rear = ? (4 , 3)

分析:队列,先进先出。删除在队头front,进入在队尾rear。

5bd540537e66d1e05777a4c7e5c7a5c7.png

12. 图

邻接矩阵 - 稠密图

邻接多重表- 无向图

十字链表 - 有向图

邻接表 - 稀疏图

补充:

1. 一个堆又是一个完全二叉树

2.n个节点的huffman树,有(n+1)/2个叶子节点。

3.在一颗深度为3的树中,有2个度为3的节点,1个度为2的节点,度为0的节点为?

分析:此题中没有度为1的节点,总分支数 = 总节点数 - 1;

即 n0 + n2(1 )+ n3(2) = (2*3 + 1*2) -1

解得:n0 = 6;

4. 65个节点的完全二叉树,(根的层次号为1)的深度为:7

分析:1+2+4+8+16+32 = 63 6层最多63个节点,7层最(64-127)

结语:判断选择的先更新这些,肯定还有漏掉的,以后必定补充上。

明天开始更新答题的,必然每日一更,直到结束!!!

ff658ad1e75eed05b0b43150cb8938d9.png

举报/反馈



推荐阅读
  • 本文节选自《NLTK基础教程——用NLTK和Python库构建机器学习应用》一书的第1章第1.2节,作者Nitin Hardeniya。本文将带领读者快速了解Python的基础知识,为后续的机器学习应用打下坚实的基础。 ... [详细]
  • 浅析python实现布隆过滤器及Redis中的缓存穿透原理_python
    本文带你了解了位图的实现,布隆过滤器的原理及Python中的使用,以及布隆过滤器如何应对Redis中的缓存穿透,相信你对布隆过滤 ... [详细]
  • 探讨Redis的最佳应用场景
    本文将深入探讨Redis在不同场景下的最佳应用,包括其优势和适用范围。 ... [详细]
  • 本文是Java并发编程系列的开篇之作,将详细解析Java 1.5及以上版本中提供的并发工具。文章假设读者已经具备同步和易失性关键字的基本知识,重点介绍信号量机制的内部工作原理及其在实际开发中的应用。 ... [详细]
  • 深入解析 Synchronized 锁的升级机制及其在并发编程中的应用
    深入解析 Synchronized 锁的升级机制及其在并发编程中的应用 ... [详细]
  • 深入解析CAS机制:全面替代传统锁的底层原理与应用
    本文深入探讨了CAS(Compare-and-Swap)机制,分析了其作为传统锁的替代方案在并发控制中的优势与原理。CAS通过原子操作确保数据的一致性,避免了传统锁带来的性能瓶颈和死锁问题。文章详细解析了CAS的工作机制,并结合实际应用场景,展示了其在高并发环境下的高效性和可靠性。 ... [详细]
  • C++ 异步编程中获取线程执行结果的方法与技巧及其在前端开发中的应用探讨
    本文探讨了C++异步编程中获取线程执行结果的方法与技巧,并深入分析了这些技术在前端开发中的应用。通过对比不同的异步编程模型,本文详细介绍了如何高效地处理多线程任务,确保程序的稳定性和性能。同时,文章还结合实际案例,展示了这些方法在前端异步编程中的具体实现和优化策略。 ... [详细]
  • 本文总结了Java初学者需要掌握的六大核心知识点,帮助你更好地理解和应用Java编程。无论你是刚刚入门还是希望巩固基础,这些知识点都是必不可少的。 ... [详细]
  • 【妙】bug称它为数组越界的妙用
    1、聊一聊首先跟大家推荐一首非常温柔的歌曲,跑步的常听。本文主要把自己对C语言中柔性数组、零数组等等的理解分享给大家,并聊聊如何构建一种统一化的学习思想 ... [详细]
  • 本文详细介绍了Java反射机制的基本概念、获取Class对象的方法、反射的主要功能及其在实际开发中的应用。通过具体示例,帮助读者更好地理解和使用Java反射。 ... [详细]
  • JUC(三):深入解析AQS
    本文详细介绍了Java并发工具包中的核心类AQS(AbstractQueuedSynchronizer),包括其基本概念、数据结构、源码分析及核心方法的实现。 ... [详细]
  • Laravel 开发技巧:如何为集合中的每个元素添加递增编号
    本文将介绍如何在 Laravel 集合中为每个数组元素添加递增的编号,帮助开发者更好地管理和操作数据。 ... [详细]
  • 在多线程环境中,IpcChannel的性能表现并未如预期般优于Tcp和Http通道。实际测试结果显示,在IIS6中通过Remoting创建的Ipc通道,其速度比Tcp通道慢了约20倍。本文详细分析了这一现象的原因,并提出了针对性的优化建议,以提升IpcChannel在高并发场景下的性能表现。 ... [详细]
  • 目前我有两张 BMP 图像文件 a.bmp 和 b.bmp,希望将它们按照以下方式进行融合:首先提取 a.bmp 的所有奇数行像素(如第 1、3、5 行),接着获取 b.bmp 的所有偶数行像素(如第 2、4、6 行)。最终目标是将这些行像素交替排列,生成一张新的图像。此过程需要确保像素顺序正确,并保持图像的整体结构和质量。 ... [详细]
  • 深入解析Java虚拟机的内存分区与管理机制
    Java虚拟机的内存分区与管理机制复杂且精细。其中,某些内存区域在虚拟机启动时即创建并持续存在,而另一些则随用户线程的生命周期动态创建和销毁。例如,每个线程都拥有一个独立的程序计数器,确保线程切换后能够准确恢复到之前的执行位置。这种设计不仅提高了多线程环境下的执行效率,还增强了系统的稳定性和可靠性。 ... [详细]
author-avatar
是非涩味_943
这个家伙很懒,什么也没留下!
PHP1.CN | 中国最专业的PHP中文社区 | DevBox开发工具箱 | json解析格式化 |PHP资讯 | PHP教程 | 数据库技术 | 服务器技术 | 前端开发技术 | PHP框架 | 开发工具 | 在线工具
Copyright © 1998 - 2020 PHP1.CN. All Rights Reserved | 京公网安备 11010802041100号 | 京ICP备19059560号-4 | PHP1.CN 第一PHP社区 版权所有