当前位置: 首页 > news >正文

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.字符串的长度是指&#xff08; C &#xff09;。 (A) 串中不同字符的个数 (B) 串中不同字母的个数 (C ) 串中所含字符的个数 (D) 串中不同数字的个数 2.建立一个长度为n的有序单链表的时间复杂度为&#xff08; C &#xff09; (A) O(n) (B) O(1) © …...

第50讲:SQL优化之LIMIT分页查询的优化

文章目录 1.LIMIT分页查询的优化概念2.LIMIT分页查询优化前后的效果2.1.LIMIT分页查询优化前2.2.LIMIT分页查询优化后1.LIMIT分页查询的优化概念 当表中数据量小时,分页查询基本上没有什么压力,查询速度也会很快,但是一般当表的数据量很庞大时,上千万条数据,此时分页查询…...

做独立开发者,能在AppStore赚到多少钱?

成为一名独立开发者&#xff0c;不用朝九晚五的上班&#xff0c;开发自己感兴趣的产品&#xff0c;在AppStore里赚美金&#xff0c;这可能是很多程序员的梦想&#xff0c;今天就来盘一盘&#xff0c;这个梦想实现的概率有多少。 先来了解一些数据&#xff1a; 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 驱动基础

注册驱动模块时给模块传递参数 在一些情况下&#xff0c;我们要动态的改变驱动中某个变量的值&#xff0c;那么就可以在注册时给驱动模块传递参数。 给驱动模块中传递参数&#xff0c;需要定义好接受参数值的全局变量&#xff0c;并调用module_param 来引用它&#xff0c;具体…...

linux 共享内存操作(shm_open、mmap、编译链接库:-lz -lrt -lm -lc都是什么库)

文章目录linux 共享内存操作&#xff08;shm_open&#xff09;一、背景二、函数使用说明shm_openftruncate&#xff08;改变文件大小&#xff09;mmap共享内存三、示例代码创建内存共享文件并写入数据打开内存共享文件读数据四、问题总结shm_write.c:(.text0x18): undefined re…...

做出改变:农业科技和区块链在为地球的未来而战中的力量

到2050年&#xff0c;全球有100亿人需要养活&#xff0c;全世界都在关注区块链和农业信息化&#xff0c;以推动发展中国家的技术革新。 自成立以来&#xff0c;区块链技术已经找到了多样化和有价值的应用&#xff0c;以帮助提高效率和激励社区在不同领域和行业的参与。 农业是…...

树莓派介绍

文章目录一.树莓派介绍二.树莓派分类一.树莓派介绍 树莓派&#xff0c;&#xff08;英语&#xff1a;Raspberry Pi&#xff0c;简写为RPi&#xff0c;别名为RasPi / RPI&#xff09;是为学习计算机编程教育而设计&#xff0c;只有信用卡大小的微型电脑&#xff0c;其系统基于L…...

[神经网络]基干网络之VGG、ShuffleNet

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

Java 日期时间与正则表达式,超详细整理,适合新手入门

目录 1、java.time.LocalDate类表示日期&#xff1b; 2、java.time.LocalTime类表示时间&#xff1b; 3、java.time.LocalDateTime类表示日期和时间&#xff1b; 4、java.time.format.DateTimeFormatter类用于格式化日期和时间&#xff1b; 5、创建正则表达式对象 6、匹配…...

用Netty实现物联网04:自定义通信协议

上一讲咱们澄清了Netty的一些基本概念,然后也写了一个服务端与客户端通信的简单应答程序。从这一讲开始,就来一步步搭建一个Netty物联网应用。 大多数硬件电子产品,都自带了嵌入式软件,或者说固件。这些嵌入式软件/固件基本上都是用C/C++编写的。由于这些小微电子设备资源极…...

「smardaten」上架钉钉应用中心!让进步再一次发生

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

3、Maven安装

前言&#xff1a;工具下载地址阿里云盘&#xff1a;Maven&#xff1a;https://www.aliyundrive.com/s/SgHKjQ5doSp提取码: ml40一、什么是maven?Apache Maven是个项目管理和自动构建工具&#xff0c;基于项目对象模型&#xff08;POM&#xff09;的概念。作用&#xff1a;完成…...

tkinter

# 隐藏控件 tl.pack_forget() tb.pack_forget() # 显示控件 tl.pack() tb.pack() 如果您使用 grid 布局管理器&#xff0c;则可以使用 grid_remove() 方法将控件隐藏&#xff0c;使用 grid() 方法将控件显示。例如&#xff1a; # 隐藏控件 tl.grid_remove() tb.grid_remove() #…...

Servlet笔记(6):HTTP状态码

1、状态码 代码消息描述100 Continue只有请求的一部分已经被服务器接收&#xff0c;但只要它没有被拒绝&#xff0c;客户端应继续该请求。101 Switching Protocols服务器切换协议。200 OK请求成功。201 Created该请求是完整的&#xff0c;并创建一个新的资源。202 Accepted该请…...

RocketMQ 延迟队列

什么是延迟队列指消息发送到某个队列后&#xff0c;在指定多长时间之后才能被消费。应用场景RocketMQ 延迟队列定时消息&#xff08;延迟队列&#xff09;是指消息发送到broker后&#xff0c;不会立即被消费&#xff0c;等待特定时间投递给真正的topic。broker有配置项messageD…...

【精准计时】北斗GPS卫星时钟同步改变精准计时年代

【精准计时】北斗GPS卫星时钟同步改变精准计时年代 【精准计时】北斗GPS卫星时钟同步改变精准计时年代 北斗GPS成精确计时先锋   北斗GPS精确时间自动校准技术&#xff0c;是一种简便的获取北斗GPS精确时间信息的专利技术&#xff0c;具有灵敏度高、不受时间及地域限制等特点…...

【C#基础】C# 面向对象编程

序号系列文章5【C#基础】C# 运算符总结6【C#基础】C# 常用语句讲解7【C#基础】C# 常用数据结构文章目录前言面向对象的 C#1&#xff0c;类的概念2&#xff0c;类的定义3&#xff0c;类成员4&#xff0c;对象5&#xff0c;继承6&#xff0c;多态性结语前言 &#x1f60a;大家好&…...

数据结构与算法入门

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

【OpenAI】基于 Gym-CarRacing 的自动驾驶练习项目 | 路径训练功能的实现 | GYM-Box2D CarRacing

限时开放&#xff0c;猛戳订阅&#xff01; &#x1f449; 《一起玩蛇》&#x1f40d; &#x1f4ad; 写在前面&#xff1a; 本篇是关于多伦多大学自动驾驶专业项目的博客。GYM-Box2D CarRacing 是一种在 OpenAI Gym 平台上开发和比较强化学习算法的模拟环境。它是流行的 Box2…...

通过Wrangler CLI在worker中创建数据库和表

官方使用文档&#xff1a;Getting started Cloudflare D1 docs 创建数据库 在命令行中执行完成之后&#xff0c;会在本地和远程创建数据库&#xff1a; npx wranglerlatest d1 create prod-d1-tutorial 在cf中就可以看到数据库&#xff1a; 现在&#xff0c;您的Cloudfla…...

鸿蒙中用HarmonyOS SDK应用服务 HarmonyOS5开发一个医院挂号小程序

一、开发准备 ​​环境搭建​​&#xff1a; 安装DevEco Studio 3.0或更高版本配置HarmonyOS SDK申请开发者账号 ​​项目创建​​&#xff1a; File > New > Create Project > Application (选择"Empty Ability") 二、核心功能实现 1. 医院科室展示 /…...

Springcloud:Eureka 高可用集群搭建实战(服务注册与发现的底层原理与避坑指南)

引言&#xff1a;为什么 Eureka 依然是存量系统的核心&#xff1f; 尽管 Nacos 等新注册中心崛起&#xff0c;但金融、电力等保守行业仍有大量系统运行在 Eureka 上。理解其高可用设计与自我保护机制&#xff0c;是保障分布式系统稳定的必修课。本文将手把手带你搭建生产级 Eur…...

让AI看见世界:MCP协议与服务器的工作原理

让AI看见世界&#xff1a;MCP协议与服务器的工作原理 MCP&#xff08;Model Context Protocol&#xff09;是一种创新的通信协议&#xff0c;旨在让大型语言模型能够安全、高效地与外部资源进行交互。在AI技术快速发展的今天&#xff0c;MCP正成为连接AI与现实世界的重要桥梁。…...

以光量子为例,详解量子获取方式

光量子技术获取量子比特可在室温下进行。该方式有望通过与名为硅光子学&#xff08;silicon photonics&#xff09;的光波导&#xff08;optical waveguide&#xff09;芯片制造技术和光纤等光通信技术相结合来实现量子计算机。量子力学中&#xff0c;光既是波又是粒子。光子本…...

Java求职者面试指南:Spring、Spring Boot、MyBatis框架与计算机基础问题解析

Java求职者面试指南&#xff1a;Spring、Spring Boot、MyBatis框架与计算机基础问题解析 一、第一轮提问&#xff08;基础概念问题&#xff09; 1. 请解释Spring框架的核心容器是什么&#xff1f;它在Spring中起到什么作用&#xff1f; Spring框架的核心容器是IoC容器&#…...

NXP S32K146 T-Box 携手 SD NAND(贴片式TF卡):驱动汽车智能革新的黄金组合

在汽车智能化的汹涌浪潮中&#xff0c;车辆不再仅仅是传统的交通工具&#xff0c;而是逐步演变为高度智能的移动终端。这一转变的核心支撑&#xff0c;来自于车内关键技术的深度融合与协同创新。车载远程信息处理盒&#xff08;T-Box&#xff09;方案&#xff1a;NXP S32K146 与…...

A2A JS SDK 完整教程:快速入门指南

目录 什么是 A2A JS SDK?A2A JS 安装与设置A2A JS 核心概念创建你的第一个 A2A JS 代理A2A JS 服务端开发A2A JS 客户端使用A2A JS 高级特性A2A JS 最佳实践A2A JS 故障排除 什么是 A2A JS SDK? A2A JS SDK 是一个专为 JavaScript/TypeScript 开发者设计的强大库&#xff…...

基于IDIG-GAN的小样本电机轴承故障诊断

目录 🔍 核心问题 一、IDIG-GAN模型原理 1. 整体架构 2. 核心创新点 (1) ​梯度归一化(Gradient Normalization)​​ (2) ​判别器梯度间隙正则化(Discriminator Gradient Gap Regularization)​​ (3) ​自注意力机制(Self-Attention)​​ 3. 完整损失函数 二…...

Git 3天2K星标:Datawhale 的 Happy-LLM 项目介绍(附教程)

引言 在人工智能飞速发展的今天&#xff0c;大语言模型&#xff08;Large Language Models, LLMs&#xff09;已成为技术领域的焦点。从智能写作到代码生成&#xff0c;LLM 的应用场景不断扩展&#xff0c;深刻改变了我们的工作和生活方式。然而&#xff0c;理解这些模型的内部…...