DS期末复习卷(八)
一、选择题(30分)
1.字符串的长度是指( C )。
(A) 串中不同字符的个数 (B) 串中不同字母的个数
(C ) 串中所含字符的个数 (D) 串中不同数字的个数
2.建立一个长度为n的有序单链表的时间复杂度为( C )
(A) O(n) (B) O(1) © O(n^2) (D) O(log2n)
建立有序单链表的时间复杂度为O(n^2)
3.两个字符串相等的充要条件是( C )。
(A) 两个字符串的长度相等 (B) 两个字符串中对应位置上的字符相等
( C) 同时具备(A)和(B)两个条件 (D) 以上答案都不对
4.设某散列表的长度为100,散列函数H(k)=k % P,则P通常情况下最好选择( B)。
(A) 99 (B) 97 ( C) 91 (D) 93
选一个素数作为模,能够减少发生冲突
5.在二叉排序树中插入一个关键字值的平均时间复杂度为(B )。
(A) O(n) (B) O(log2n) ( C) O(nlog2n) (D) O(n%2)
6.设一个顺序有序表A[1:14]中有14个元素,则采用二分法查找元素A[4]的过程中比较元素的顺序为( C )。
(A) A[1],A[2],A[3],A[4] (B) A[1],A[14],A[7],A[4]
( C) A[7],A[3],A[5],A[4] (D) A[7],A[5] ,A[3],A[4]
1 2 3 4 5 6 7 8 9 10 11 12 13 14
1 2 3 4 5 6
456
4
7.设一棵完全二叉树中有65个结点,则该完全二叉树的深度为( B )。
(A) 8 (B) 7 ( C) 6 (D) 5
假设二叉树的深度为k,则该二叉树最多有2^k - 1个节点,若k为6,则最多有2^6 - 1 = 63个节点,小于65。故该二叉树的深度为7,选B。
8.设一棵三叉树中有2个度数为1的结点,2个度数为2的结点,2个度数为3的结点,则该三叉链权中有( C )个度数为0的结点。
(A) 5 (B) 6 (C ) 7 (D) 8
no=1+n2+2n3+=1+2+4=7
9.设无向图G中的边的集合E={(a,b),(a,e),(a,c),(b,e),(e,d),(d,f),(f,c)},则从顶点a出发进行深度优先遍历可以得到的一种顶点序列为(A )。
(A) aedfcb (B) acfebd ( C) aebcfd (D) aedfbc
abedfc
aedfcb
acedfb
10.队列是一种( A )的线性表。
(A) 先进先出 (B) 先进后出 © 只能插入 (D) 只能删除
二、判断题
1、如果两个关键字的值不等但哈希函数值相等,则称这两个关键字为同义词。( )
对
2、设初始记录关键字基本有序,则快速排序算法的时间复杂度为O(nlog2n)。( )
错
快速排序在基本有序的时候算法时间复杂度是最坏的,此时为o(n^2)。相反在越无序的时候时间复杂度越低,为O(nlogn)。
3、分块查找的基本思想是首先在索引表中进行查找,以便确定给定的关键字可能存在的块号,然后再在相应的块内进行顺序查找。
( )
对
4、二维数组和多维数组均不是特殊的线性结构。( )
错。
数组都是线性结构
5、向二叉排序树中插入一个结点需要比较的次数可能大于该二叉树的高度。( )
错
最坏情况下和树的高度一样,不可能比树的高度要大,在二叉搜索树中查找和二分查找相似。
6、如果某个有向图的邻接表中第i条单链表为空,则第i个顶点的出度为零。( )
对
有向图的邻接表
一行单链表表示该行头结点的出度
7、非空的双向循环链表中任何结点的前驱指针均不为空。( )
对
循环链表是最后一个节点的指针域指向头节点,而不是指向第一个节点,所以双向循环链表是一整个完整的循环。
8、不论线性表采用顺序存储结构还是链式存储结构,删除值为X的结点的时间复杂度均为O(n)。( )
对
9、图的深度优先遍历算法中需要设置一个标志数组,以便区分图中的每个顶点是否被访问过。( )
对
10、稀疏矩阵的压缩存储可以用一个三元组表来表示稀疏矩阵中的非0元素。( )
对
三、填空题
1、设一组初始记录关键字序列为(49,38,65,97,76,13,27,50),则以d=4为增量的一趟希尔排序结束后的结果为
_____________________________。
(49,13,27,50,76,38,65,97)
d=4
[49,76]为一个子序列
[38,13]一个子序列
[65,27]一个子序列
[97,50]一个子序列
各自排序后放回他们在总序列中对应的位置(就是原本的位置交换一下变成升序)。
2、下面程序段的功能是实现在二叉排序树中插入一个新结点,请在下划线处填上正确的内容。
t=(bitree *)malloc(sizeof(bitree))
bstinsert(t->rchild,k)
3、设指针变量p指向单链表中结点A,指针变量s指向被插入的结点X,则在结点A的后面插入结点X需要执行的语句序列:
s->next=p->next; _________________;
p->next=s;
4、设指针变量head指向双向链表中的头结点,指针变量p指向双向链表中的第一个结点,则指针变量p和指针变量head之间的关系
是p=和head=_(设结点中的两个指针域分别为llink和rlink)。
head->rlink
p->llink;
5、设某棵二叉树的中序遍历序列为ABCD,后序遍历序列为BADC,则其前序遍历序列为__________。
CABD
6、完全二叉树中第5层上最少有__________个结点,最多有_________个结点。
1
16(2^(h-1))
7、设有向图中不存在有向边<Vi,Vj>,则其对应的邻接矩阵A中的数组元素A[i][j]的值等于____________。
0
8、设一组初始记录关键字序列为(49,38,65,97,76,13,27,50),则第4趟直接选择排序结束后的结果为__________。
(13,27,38,49,97,76,65,50)
13,38,65,97,76,49,27,50
13,27,65,97,76,49,38,50
13,27,38,65,97,76,49,50
13,27,38,49,97,76,65,50
9、设连通图G中有n个顶点e条边,则对应的最小生成树上有___________条边。
n-1
生成最小生成树需要包含图中各点,因此连接的边数为n- 1。
10、设有一组初始记录关键字序列为(50,16,23,68,94,70,73),则将它们调整成初始堆只需把16与___________相互交换
即可。
50
小根堆
四、算法设计题(20分)
1.设计一个在链式存储结构上统计二叉树中结点个数的算法。
void countnode(bitree* bt, int& count)
{if (bt != 0){count++; countnode(bt->lchild, count);countnode(bt->rchild, count);}
}
2.设计一个算法将无向图的邻接矩阵转为对应邻接表的算法。
typedef struct { int vertex[m]; int edge[m][m]; }gadjmatrix;
typedef struct node1 { int info; int adjvertex; struct node1* nextarc; }glinklistnode;
typedef struct node2 { int vertexinfo; glinklistnode* firstarc; }glinkheadnode;
void adjmatrixtoadjlist(gadjmatrix g1[], glinkheadnode g2[])
{int i, j; glinklistnode* p;for (i = 0; i <= n - 1; i++) g2[i].firstarc = 0;for (i = 0; i <= n - 1; i++) for (j = 0; j <= n - 1; j++)if (g1.edge[i][j] == 1){p = (glinklistnode*)malloc(sizeof(glinklistnode)); p->adjvertex = j;p->nextarc = g[i].firstarc; g[i].firstarc = p;p = (glinklistnode*)malloc(sizeof(glinklistnode)); p->adjvertex = i;p->nextarc = g[j].firstarc; g[j].firstarc = p;}
}
相关文章:

DS期末复习卷(八)
一、选择题(30分) 1.字符串的长度是指( C )。 (A) 串中不同字符的个数 (B) 串中不同字母的个数 (C ) 串中所含字符的个数 (D) 串中不同数字的个数 2.建立一个长度为n的有序单链表的时间复杂度为( C ) (A) O(n) (B) O(1) © …...
第50讲:SQL优化之LIMIT分页查询的优化
文章目录 1.LIMIT分页查询的优化概念2.LIMIT分页查询优化前后的效果2.1.LIMIT分页查询优化前2.2.LIMIT分页查询优化后1.LIMIT分页查询的优化概念 当表中数据量小时,分页查询基本上没有什么压力,查询速度也会很快,但是一般当表的数据量很庞大时,上千万条数据,此时分页查询…...

做独立开发者,能在AppStore赚到多少钱?
成为一名独立开发者,不用朝九晚五的上班,开发自己感兴趣的产品,在AppStore里赚美金,这可能是很多程序员的梦想,今天就来盘一盘,这个梦想实现的概率有多少。 先来了解一些数据: 2022年5月26日&am…...

CSS 基础【快速掌握知识点】
目录 一、什么是CSS 二、CSS发展史 三、CSS基本语法结构 1、语法 2、例如 四、style标签 五、HTML中引入CSS样式 1、行内样式 2、内部样式表 3、外部样式表 六、CSS基本选择器 1、标签选择器 2、类选择器 3、ID选择器 4、总结 5、基本选择器的优先级 七、CSS的…...

Linux 驱动基础
注册驱动模块时给模块传递参数 在一些情况下,我们要动态的改变驱动中某个变量的值,那么就可以在注册时给驱动模块传递参数。 给驱动模块中传递参数,需要定义好接受参数值的全局变量,并调用module_param 来引用它,具体…...
linux 共享内存操作(shm_open、mmap、编译链接库:-lz -lrt -lm -lc都是什么库)
文章目录linux 共享内存操作(shm_open)一、背景二、函数使用说明shm_openftruncate(改变文件大小)mmap共享内存三、示例代码创建内存共享文件并写入数据打开内存共享文件读数据四、问题总结shm_write.c:(.text0x18): undefined re…...

做出改变:农业科技和区块链在为地球的未来而战中的力量
到2050年,全球有100亿人需要养活,全世界都在关注区块链和农业信息化,以推动发展中国家的技术革新。 自成立以来,区块链技术已经找到了多样化和有价值的应用,以帮助提高效率和激励社区在不同领域和行业的参与。 农业是…...
树莓派介绍
文章目录一.树莓派介绍二.树莓派分类一.树莓派介绍 树莓派,(英语:Raspberry Pi,简写为RPi,别名为RasPi / RPI)是为学习计算机编程教育而设计,只有信用卡大小的微型电脑,其系统基于L…...

[神经网络]基干网络之VGG、ShuffleNet
一、VGG VGG是传统神经网络堆叠能达到的极限深度。 VGG分为VGG16和VGG19,其均有以下特点: ①按2x2的Pooling层,网络可以分成若干段 ②每段之内由若干same卷积操作构成,段内Feature Map数量固定不变; ③Feature Map按2的…...

Java 日期时间与正则表达式,超详细整理,适合新手入门
目录 1、java.time.LocalDate类表示日期; 2、java.time.LocalTime类表示时间; 3、java.time.LocalDateTime类表示日期和时间; 4、java.time.format.DateTimeFormatter类用于格式化日期和时间; 5、创建正则表达式对象 6、匹配…...
用Netty实现物联网04:自定义通信协议
上一讲咱们澄清了Netty的一些基本概念,然后也写了一个服务端与客户端通信的简单应答程序。从这一讲开始,就来一步步搭建一个Netty物联网应用。 大多数硬件电子产品,都自带了嵌入式软件,或者说固件。这些嵌入式软件/固件基本上都是用C/C++编写的。由于这些小微电子设备资源极…...

「smardaten」上架钉钉应用中心!让进步再一次发生
使用钉钉的团队小伙伴们,smardaten给您送来福利啦~为了给更多团队提供更优质的应用开发体验,方便用户在线、快速使用无代码,数睿数据近期在【钉钉应用中心】发布smardaten在线版本。继与华为云、亚马逊云建立战略合作之后,smardat…...

3、Maven安装
前言:工具下载地址阿里云盘:Maven:https://www.aliyundrive.com/s/SgHKjQ5doSp提取码: ml40一、什么是maven?Apache Maven是个项目管理和自动构建工具,基于项目对象模型(POM)的概念。作用:完成…...
tkinter
# 隐藏控件 tl.pack_forget() tb.pack_forget() # 显示控件 tl.pack() tb.pack() 如果您使用 grid 布局管理器,则可以使用 grid_remove() 方法将控件隐藏,使用 grid() 方法将控件显示。例如: # 隐藏控件 tl.grid_remove() tb.grid_remove() #…...
Servlet笔记(6):HTTP状态码
1、状态码 代码消息描述100 Continue只有请求的一部分已经被服务器接收,但只要它没有被拒绝,客户端应继续该请求。101 Switching Protocols服务器切换协议。200 OK请求成功。201 Created该请求是完整的,并创建一个新的资源。202 Accepted该请…...

RocketMQ 延迟队列
什么是延迟队列指消息发送到某个队列后,在指定多长时间之后才能被消费。应用场景RocketMQ 延迟队列定时消息(延迟队列)是指消息发送到broker后,不会立即被消费,等待特定时间投递给真正的topic。broker有配置项messageD…...
【精准计时】北斗GPS卫星时钟同步改变精准计时年代
【精准计时】北斗GPS卫星时钟同步改变精准计时年代 【精准计时】北斗GPS卫星时钟同步改变精准计时年代 北斗GPS成精确计时先锋 北斗GPS精确时间自动校准技术,是一种简便的获取北斗GPS精确时间信息的专利技术,具有灵敏度高、不受时间及地域限制等特点…...
【C#基础】C# 面向对象编程
序号系列文章5【C#基础】C# 运算符总结6【C#基础】C# 常用语句讲解7【C#基础】C# 常用数据结构文章目录前言面向对象的 C#1,类的概念2,类的定义3,类成员4,对象5,继承6,多态性结语前言 😊大家好&…...

数据结构与算法入门
目录数据结构概述逻辑结构存储结构算法概述如何理解“大O记法”时间复杂度空间复杂度数据结构概述 数据结构可以简单的理解为数据与数据之间所存在的一些关系,数据的结构分为数据的存储结构和数据的逻辑结构。 逻辑结构 集合结构:数据元素同属于一个集…...

【OpenAI】基于 Gym-CarRacing 的自动驾驶练习项目 | 路径训练功能的实现 | GYM-Box2D CarRacing
限时开放,猛戳订阅! 👉 《一起玩蛇》🐍 💭 写在前面: 本篇是关于多伦多大学自动驾驶专业项目的博客。GYM-Box2D CarRacing 是一种在 OpenAI Gym 平台上开发和比较强化学习算法的模拟环境。它是流行的 Box2…...

wordpress后台更新后 前端没变化的解决方法
使用siteground主机的wordpress网站,会出现更新了网站内容和修改了php模板文件、js文件、css文件、图片文件后,网站没有变化的情况。 不熟悉siteground主机的新手,遇到这个问题,就很抓狂,明明是哪都没操作错误&#x…...
uniapp 对接腾讯云IM群组成员管理(增删改查)
UniApp 实战:腾讯云IM群组成员管理(增删改查) 一、前言 在社交类App开发中,群组成员管理是核心功能之一。本文将基于UniApp框架,结合腾讯云IM SDK,详细讲解如何实现群组成员的增删改查全流程。 权限校验…...

铭豹扩展坞 USB转网口 突然无法识别解决方法
当 USB 转网口扩展坞在一台笔记本上无法识别,但在其他电脑上正常工作时,问题通常出在笔记本自身或其与扩展坞的兼容性上。以下是系统化的定位思路和排查步骤,帮助你快速找到故障原因: 背景: 一个M-pard(铭豹)扩展坞的网卡突然无法识别了,扩展出来的三个USB接口正常。…...
Leetcode 3576. Transform Array to All Equal Elements
Leetcode 3576. Transform Array to All Equal Elements 1. 解题思路2. 代码实现 题目链接:3576. Transform Array to All Equal Elements 1. 解题思路 这一题思路上就是分别考察一下是否能将其转化为全1或者全-1数组即可。 至于每一种情况是否可以达到…...

从WWDC看苹果产品发展的规律
WWDC 是苹果公司一年一度面向全球开发者的盛会,其主题演讲展现了苹果在产品设计、技术路线、用户体验和生态系统构建上的核心理念与演进脉络。我们借助 ChatGPT Deep Research 工具,对过去十年 WWDC 主题演讲内容进行了系统化分析,形成了这份…...
java 实现excel文件转pdf | 无水印 | 无限制
文章目录 目录 文章目录 前言 1.项目远程仓库配置 2.pom文件引入相关依赖 3.代码破解 二、Excel转PDF 1.代码实现 2.Aspose.License.xml 授权文件 总结 前言 java处理excel转pdf一直没找到什么好用的免费jar包工具,自己手写的难度,恐怕高级程序员花费一年的事件,也…...

SCAU期末笔记 - 数据分析与数据挖掘题库解析
这门怎么题库答案不全啊日 来简单学一下子来 一、选择题(可多选) 将原始数据进行集成、变换、维度规约、数值规约是在以下哪个步骤的任务?(C) A. 频繁模式挖掘 B.分类和预测 C.数据预处理 D.数据流挖掘 A. 频繁模式挖掘:专注于发现数据中…...
java调用dll出现unsatisfiedLinkError以及JNA和JNI的区别
UnsatisfiedLinkError 在对接硬件设备中,我们会遇到使用 java 调用 dll文件 的情况,此时大概率出现UnsatisfiedLinkError链接错误,原因可能有如下几种 类名错误包名错误方法名参数错误使用 JNI 协议调用,结果 dll 未实现 JNI 协…...
linux 错误码总结
1,错误码的概念与作用 在Linux系统中,错误码是系统调用或库函数在执行失败时返回的特定数值,用于指示具体的错误类型。这些错误码通过全局变量errno来存储和传递,errno由操作系统维护,保存最近一次发生的错误信息。值得注意的是,errno的值在每次系统调用或函数调用失败时…...

Nuxt.js 中的路由配置详解
Nuxt.js 通过其内置的路由系统简化了应用的路由配置,使得开发者可以轻松地管理页面导航和 URL 结构。路由配置主要涉及页面组件的组织、动态路由的设置以及路由元信息的配置。 自动路由生成 Nuxt.js 会根据 pages 目录下的文件结构自动生成路由配置。每个文件都会对…...