数据结构:期末考 第六次测试(总复习)

一、 单选题 (共50题,100分)

1、表长为n的顺序存储的线性表,当在任何位置上插入或删除一个元素的概率相等时,插入一个元素所需移动元素的平均个数为( D ).(2.0)
A、 (n−1)/2
B、 n
C、 n+1
D、 n/2

2、设栈S和队列Q的初始状态为空,元素e1、e2、e3、e4、e5和e6依次通过栈S,一个元素出栈后即进入队列Q,若6个元素出队的序列为e2、e4、e3、e6、e5和e1,则栈S的容量至少应该为( C )。(2.0)
A、 6
B、 4
C、 3
D、 2

3、设栈的输入序列为1、2、3… n,若输出序列的第一个元素为n,则第i个输出的元素为( B )。(2.0)
A、 不确定
B、 n−i+1
C、 i
D、 n−i

4、在一个长度为n的顺序表中删除第i个元素(1<=i<=n)时,需向前移动( )个元素。(2.0)
A、 n−i
B、 n−i+1
C、 n−i−1
D、 i

5、若长度为n的线性表采用顺序存储结构存储,在第i个位置上插入一个新元素的时间复杂度为( )。(2.0)
A、O(n)
B、 O(1)
C、O( n 2 n^2 n2)
D、O( n 3 n^3 n3)

6、表达式a(b+c)−d的后缀表达式是( )。(2.0)
A、 abcd+−
B、 abc+d−
C、 abc+d−
D、 −+abcd

7、顺序循环队列中(数组的大小为n),队头指示front指向队列的第1个元素,队尾指示rear指向队列最后元素的后1个位置,则循环队列中存放了n - 1个元素,即循环队列满的条件为( )。(2.0)
A、 (rear+1)%n=front−1
B、 (rear+1)%n=front
C、 (rear)%n=front
D、 rear+1=front

8、两个有序线性表分别具有n个元素与m个元素且n≤m,现将其归并成一个有序表,其最少的比较次数是( )。(2.0)
A、n
B、 m
C、 n−1
D、 m+n

9、在一个具有n个结点的有序单链表中插入一个新结点并保持单链表仍然有序的时间复杂度是( )。(2.0)
A、O(1)
B、O(n)
C、O( n 2 n^2 n2)
D、O( n l o g 2 n nlog_{2^n} nlog2n)

10、若从键盘输入n个元素,则建立一个有序单向链表的时间复杂度为( )。(2.0)
A、O(n)
B、O( n 2 n^2 n2)
C、O( n 3 n^3 n3)
D、O( n × l o g 2 n n×log2^n n×log2n)

11、在一个单链表中,若p所指结点不是最后结点,在p之后插入s所指结点,则执行( )。(2.0)
A、 s->next=p;p->next=s;
B、 s->next=p->next;p->next=s;
C、 s->next=p->next;p=s;
D、 p->next=s;s->next=p;

12、前序遍历和后序遍历结果相同的二叉树为( )。(2.0)
A、一般二叉树
B、 只有根结点的二叉树
C、 根结点无左孩子的二叉树
D、 根结点无右孩子的二叉树
E、 所有结点只有左子树的二叉树
F、所有结点只有右子树的二叉树

13、一棵具有5层的满二叉树所包含的结点个数为( )。(2.0)
A.15 B.31 C.63 D.32

14、如果某图的邻接矩阵是对角线元素均为零的上三角矩阵,则此图是( )。(2.0)
A、 有向完全图
B、 连通图
C、 强连通图
D、 有向无环图

15、若邻接表中有奇数个表结点,则一定( )。(2.0)
A、 图中有奇数个顶点
B、 图中有偶数个顶点
C、 图为无向图
D、 图为有向图

16、假设一个有n个顶点和e条弧的有向图用邻接表表示,则删除与某个顶点vi相关的所有弧的时间复杂度是( )。(2.0)
A、 O(n)
B、 O(e)
C、 O(n+e)
D、 O( n ∗ e n*e ne)

17、下列哪一个选项不是图8.34所示有向图的拓扑排序结果( )。(2.0)

A、 AFBCDE
B、 FABCDE
C、 FACBDE
D、 FADBCE

18、判断一个有向图是否存在回路除了可以利用拓扑排序方法外,还可以利用( )。(2.0)
A、 单源最短路Dijkstra算法
B、 所有顶点对最短路Floyd算法
C、 广度优先遍历算法
D、 深度优先遍历算法

19、在一个带权连通图G中,权值最小的边一定包含在G的( )。(2.0)
A、 最小生成树中
B、 深度优先生成树中
C、 广度优先生成树中
D、深度优先生成森林中

20、适用于折半查找的表的存储方式及元素排列要求为( )。(2.0)
A、 链式方式存储,元素无序
B、 链式方式存储,元素有序
C、 顺序方式存储,元素无序
D、 顺序方式存储,元素有序

21、设顺序存储的线性表共有123个元素,按分块查找的要求等分成3块。若对索引表采用顺序查找来确定块,并在确定的块中进行顺序查找,则在查找概率相等的情况下,分块查找成功时的平均查找长度为( )。(2.0)
A、 21
B、 23
C、 41
D、 62

22、已知含10个结点的二叉排序树是一棵完全二叉树,则该二叉排序树在等概率情况下查找成功的平均查找长度等于( )。(2.0)
A、 1.0
B、 2.9
C、 3.4
D、 5.5

23、以下各选项所示的各棵二叉树中,二叉排序树是( )。(2.0)

A、

B、

C、

D、

24、有数据{53,30,37,12,45,24,96},从空二叉树开始逐步插入数据形成二叉排序树,若希望高度最小,则应该选择下列( )的序列输入。(2.0)
A、 37,24,12,30,53,45,96
B、 45,24,53,12,37,96,30
C、 12,24,30,37,45,53,96
D、 30,24,12,37,45,96,53

25、对于哈希函数H(key)=key%13,被称为同义词的关键字是( )。(2.0)
A、 35和41
B、 23和39
C、 15和44
D、 25和51

26、下列序列中,( )是执行第一趟快速排序后得到的序列。(2.0)
A、 [da,ax,eb,de,bb]ff[ha,gc]
B、 [cd,eb,ax,da]ff[ha,gc,bb]
C、 [gc,ax,eb,cd,bb]ff[da,ha]
D、 [ax,bb,cd,da]ff[eb,gc,ha]

27、下面的序列中初始序列构成最小堆(小根堆)的是( )。(2.0)
A、 10、60、20、50、30、26、35、40
B、 70、40、36、30、20、16、28、10
C、 20、60、50、40、30、10、8、72
D、 10、30、20、50、40、26、35、60

28、在下列算法中,( )算法可能出现下列情况:在最后一趟开始之前,所有的元素都不在其最终的位置上。(2.0)
A、 堆排序
B、 插入排序
C、 冒泡排序
D、 快速排序

29、若需在O(nlogn)的时间内完成对数组的排序,且要求排序算法是稳定的,则可选择的排序方法是( )。(2.0)
A、 归并排序
B、 堆排序
C、 快速排序
D、 直接插入排序

30、以下排序方法中,不稳定的排序方法是( )。(2.0)
A、 直接选择排序
B、 二分法插入排序
C、 归并排序
D、 基数排序

31、一个序列中有10000个元素,若只想得到其中前10个最小元素,最好采用( )方法。(2.0)
A、 快速排序
B、 堆排序
C、 插入排序
D、 二路归并排序

32、若要求尽可能快地对实数数组进行稳定的排序,则应选( )。(2.0)
A、 快速排序
B、 堆排序
C、 归并排序
D、基数排序

33、排序的趟数与待排序元素的原始状态有关的排序方法是( )。(2.0)
A、 冒泡排序
B、 快速排序
C、 插入排序
D、 选择排序

34、直接插入排序在最好情况下的时间复杂度为( )。(2.0)
A、 O(n)
B、 O(log n)
C、 O(nlog n)
D、 O(n2)

35、下面程序运行后的输出结果是( )。(2.0)

#include <stdio.h>
void f(int p);
int main()
{  int a[5]={1,2,3,4,5},r=a;
  f(r);
  printf("%d\n",r);
}
void f(int p)
{  p=p+3;
  printf("%d,",p);
}

A、 1,3
B、 3,3
C、 3,1
D、 4,1

36、下面程序的输出结果是什么( )。(2.0)

\#include <stdio.h>
int main( ){
  int x=20,y=40,p;
  p=&x;
  printf("%d,",p);
  p=x+10;
  p=&y;
  printf("%d,",p);
  p=y+20;
  printf("%d,%d\n",x,y);
  return 0;
}

A、 20,40,20,40
B、 20,40,30,60
C、 20,40,20,40
D、 30,60,30,60

37、二维数组M[i][j]的元素是4个字符(每个字符占一个存储单元)组成的串,行下标i的范围是04,列下标j的范围是05,M按行存储时元素M[3][5]的起始地址与M按列存储时地址相同的元素是( )。(2.0)
A、 M[2][4]
B、 M[3][ 4]
C、 M[3][5]
D、 M[4][4]

38、将三对角矩阵A[1…100][1…100]按行优先存入一维数组B[1…298]中,A中元素A[66][65]在数组B中的位置为( )。(2.0)
A、 198
B、 195
C、 197
D、 196

39、按照二叉树的定义,具有三个结点的二叉树有( )棵。(2.0)
A、 5
B、 4
C、 3
D、 6

40、二叉树中第5层上的结点个数最多为( )(2.0)
A、 8
B、 15
C、 16
D、 20

41、一棵完全二叉树上有768个结点,则该二叉树中叶子结点的个数是( ) 。(2.0)
A、 257
B、 258
C、 384
D、 385

42、若G是一个非连通无向图,共有28条边,则该图至少有多少个顶点( )。(2.0)
A、 7
B、 8
C、 9
D、 27

43、【2014统考真题】下列选项中,不可能是快速排序第2趟排序结果是( )。(2.0)
A、 2,3,5,4,6,7,9
B、 2,7,5,6,4,3,9
C、 3,2,5,4,7,6,9
D、 4,2,3,5,7,6,9

44、【2010统考真题】采用递归方式对顺序表进行快速排序。下列关于递归次数的叙述中,正确的是( )。(2.0)
A、 递归次数与初始数据的排列次序无关
B、 每次划分后,先处理较长的分区可以减少递归次数
C、 每次划分后,先处理较短的分区可以减少递归次数
D、递归次数与每次划分后得到的分区的处理顺序无关

45、【2019统考真题】排序过程中,对尚未确定最终位置的所有元素进行一遍处理称为一“趟”。下列序列中,不可能是快速排序第二趟结果的是( )。(2.0)
A、 5,2,16,12,28,60,32,72
B、 2,16,5,28,12,60,32,72
C、 2,12,16,5,28,32,72,60
D、 5,2,12,28,16,32,72,60

46、【2011统考真题】为实现快速排序算法,待排序序列宜采用的存储方式是( )。(2.0)
A、 顺序存储
B、 散列存储
C、 链式存储
D、 索引存储

47、【2010统考真题】对一组数据(2,12,16,88,5,10)进行排序,若前3趟排序结果如下:
第1趟排序结果:2,12,16,5,10,88
第2趟排序结果:2,12,5,10,16,88
第3趟排序结果:2,5,10,12,16,88
则采用的排序的方法可能是( )。(2.0)
A、 冒泡排序
B、 希尔排序
C、 归并排序
D、 基数排序

48、【2012统考真题】在内部排序过程中,对尚未确定最终位置的所有元素进行一遍处理称为一趟排序。下列排序方法中,每趟排序结束后都至少能够确定一个元素最终位置的方法是( )。
Ⅰ.简单选择排序 Ⅱ.希尔排序 Ⅲ.快速排序 Ⅳ.堆排序 Ⅴ.2路归并排序(2.0)

A、 仅Ⅰ、Ⅲ、Ⅳ
B、 仅Ⅰ、Ⅲ、Ⅴ
C、 仅Ⅱ、Ⅲ、Ⅳ
D、 仅Ⅲ、Ⅳ、Ⅴ

49、【2015统考真题】下列排序算法中,元素的移动次数与关键字的初始排列次序无关的是( )。(2.0)
A、 直接插入排序
B、 冒泡排序
C、基数排序
D、 快速排序

50、【2017统考真题】下列排序方法中,若将顺序存储更换为链式存储,则算法的时间效率会降低的是( )。
Ⅰ.插入排序 Ⅱ.选择排序 Ⅲ.冒泡排序 Ⅳ.希尔排序 Ⅴ.堆排序(2.0)
A、 仅Ⅰ、Ⅱ
B、 仅Ⅱ、Ⅲ
C、 仅Ⅲ、Ⅳ
D、 仅Ⅳ、Ⅴ

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:/a/760721.html

如若内容造成侵权/违法违规/事实不符,请联系我们进行投诉反馈qq邮箱809451989@qq.com,一经查实,立即删除!

相关文章

基于matlab的可乐标签模板匹配

1 建模思路 1.图像预处理&#xff1a; 如果目标图像和模板图像是彩色的&#xff08;即RGB图像&#xff09;&#xff0c;则将它们转换为灰度图像&#xff0c;以便在单通道上进行匹配。使用rgb2gray函数进行灰度化。 2.获取模板大小&#xff1a; 使用size函数获取模板图像的高…

骁龙相机拍照流程分析

和你一起终身学习&#xff0c;这里是程序员Android 经典好文推荐&#xff0c;通过阅读本文&#xff0c;您将收获以下知识点: 1.deliverInputEvent 拍照点击事件处理 2.submitRequestList Camera 提交拍照请求 3.createCaptureRequest 拍照请求帧数 骁龙相机通过binder 数据传输…

2006-2020上市公司研发投入金额数据集

2006-2020上市公司研发投入金额数据集https://download.csdn.net/download/a519573917/89501035 目录 上市公司研发投入与企业绩效的关系研究 一、引言 二、文献综述 三、研究设计 四、实证结果与分析 &#xff08;一&#xff09;描述性统计分析 &#xff08;二&#xf…

人工智能在肿瘤:分子亚型分类领域的最新研究进展|顶刊速递·24-07-01

小罗碎碎念 今日推文主题&#xff1a;人工智能在肿瘤/分子亚型分类中的应用 小罗观点 前两天有一位复旦的师兄私聊问了我一些问题&#xff0c;我看完以后觉得大家可能对于“分类”的概念有点不太熟悉&#xff0c;所以我决定写这篇推文系统的梳理一下“分类”和“回归”。 这俩都…

CleanMyMacX2024免费且强大的mac电脑系统优化工具

如果你的Mac电脑出现了存储空间不足、运行缓慢、电池电量消耗过快等问题&#xff0c;那么CleanMyMacX这款软件或许能为你提供解决方案。作为一款强大的系统优化工具&#xff0c;它能够帮助用户清理垃圾文件、优化内存和电池使用&#xff0c;从而提升Mac的性能表现&#xff0c;让…

09_计算机网络模型

目录 OSI/RM七层模型 OSI/RM七层模型 各层介绍及硬件设备 传输介质 TCP/IP协议簇 网络层协议 传输层协议 应用层协议 完整URL的组成 IP地址表示与计算 分类地址格式 子网划分和超网聚合 无分类编址 特殊含义的IP地址 IPv6协议 过渡技术 OSI/RM七层模型 OSI/RM七…

使用 Vue 实现包含单选框的弹窗功能(附Demo)

目录 前言1. Vue22. Vue3 前言 如果在弹窗中单独增设一些选项或者少部分的数据&#xff0c;可用如下的方式 &#xff08;不用单独创建专门的表单样式&#xff09; 如果单纯可以通过基本的按钮传输给后端&#xff0c;可用如下知识点 对于弹窗的基本知识推荐阅读&#xff1a; …

2024年06月CCF-GESP编程能力等级认证Scratch图形化编程四级真题解析

本文收录于《Scratch等级认证CCF-GESP图形化真题解析》专栏,专栏总目录:点这里,订阅后可阅读专栏内所有文章。 一、单选题(共 10 题,每题 2 分,共 30 分) 第1题 小杨父母带他到某培训机构给他报名参加 CCF 组织的 GESP 认证考试的第 1 级,那他可以选择的认证语言有几…

数据资产铸就市场竞争优势:运用先进的数据分析技术,精准把握市场脉搏,构建独特的竞争优势,助力企业实现市场领先地位,赢得持续成功

目录 一、引言 二、数据资产的重要性 三、先进数据分析技术的应用 1、大数据分析技术 2、人工智能与机器学习 3、数据可视化技术 四、精准把握市场脉搏 1、深入了解客户需求 2、预测市场趋势 3、优化资源配置 五、构建独特的竞争优势 1、定制化产品和服务 2、精准营…

zerotier-one自建根服务器方法四

一、简介 前面几篇文章已经写完了安装配置服务器&#xff0c;今天写一下客户端如何连接自建的服务器。 二、准备工作 准备一个有公网IP的云主机。 要稳定性、安全性、不差钱的可以使用阿里、腾讯等大厂的云服务器。 本人穷屌丝一枚&#xff0c;所以我用的是免费的“三丰云…

Firefox 编译指南2024 Windows10-使用Git 管理您的Firefox(五)

1. 引言 在现代软件开发中&#xff0c;版本控制系统&#xff08;VCS&#xff09;是不可或缺的工具&#xff0c;它不仅帮助开发者有效管理代码的变化&#xff0c;还支持团队协作与项目管理。Mercurial 是一个高效且易用的分布式版本控制系统&#xff0c;其设计目标是简洁、快速…

【代码随想录】【算法训练营】【第53天】 [739]每日温度 [496]下一个更大元素I [503]下一个更大元素II

前言 思路及算法思维&#xff0c;指路 代码随想录。 题目来自 LeetCode。 day 48&#xff0c;周六&#xff0c;不能再坚持~ 题目详情 [739] 每日温度 题目描述 739 每日温度 解题思路 前提&#xff1a; 思路&#xff1a; 重点&#xff1a; 代码实现 C语言 [496] 下一…

算法题型归类整理及同类题型解法思路总结(持续更新)

1、最优路线 通用思路 1、递归 #案例1-最优路测路线 题目描述 评估一个网络的信号质量&#xff0c;其中一个做法是将网络划分为栅格&#xff0c;然后对每个栅格的信号质量计算。 路测的时候&#xff0c;希望选择一条信号最好的路线&#xff08;彼此相连的栅格集合&#x…

Unity开箱即用的UGUI面板的拖拽移动功能

文章目录 &#x1f449;一、背景&#x1f449;二、效果图&#x1f449;三、原理&#x1f449;四、核心代码&#x1f449;五&#xff0c;总结 &#x1f449;一、背景 之前做PC项目时常常有面板拖拽移动的需求&#xff0c;今天总结封装一下&#xff0c;做成一个随时随地可复用的…

Linux 安装 Redis 教程

优质博文&#xff1a;IT-BLOG-CN 一、准备工作 配置gcc&#xff1a;安装Redis前需要配置gcc&#xff1a; yum install gcc如果配置gcc出现依赖包问题&#xff0c;在安装时提示需要的依赖包版本和本地版本不一致&#xff0c;本地版本过高&#xff0c;出现如下问题&#xff1a…

【PB案例学习笔记】-25制作一个带底图的MDI窗口

写在前面 这是PB案例学习笔记系列文章的第25篇&#xff0c;该系列文章适合具有一定PB基础的读者。 通过一个个由浅入深的编程实战案例学习&#xff0c;提高编程技巧&#xff0c;以保证小伙伴们能应付公司的各种开发需求。 文章中设计到的源码&#xff0c;小凡都上传到了gite…

Linux CentOS 宝塔 Suhosin禁用php5.6版本eval函数详细图文教程

方法一&#xff1a;PHP_diseval_extension禁用 Linux CentOS 禁用php的eval函数详细图文教程_centos php 禁用 eval-CSDN博客 这个方法make报错&#xff0c;懒得费时间处理&#xff0c;直接用第二种 方法二&#xff1a;suhosin禁用 不支持PHP8&#xff0c;官方只支持PHP7以下…

SpringMVC基础详解

文章目录 一、SpringMVC简介1、什么是MVC2、MVC架构模式与三层模型的区别3、什么是SpringMVC 二、HelloWorld程序1、pom文件2、springmvc.xml3、配置web.xml文件4、html文件5、执行Controller 三、RequestMapping注解1、value属性1.1、基础使用1.2、Ant风格&#xff08;模糊匹配…

《Programming from the Ground Up》阅读笔记:p1-p18

《Programming from the Ground Up》学习第1天&#xff0c;p1-18总结&#xff0c;总计18页。 一、技术总结 1.fetch-execute cycle p9, The CPU reads in instructions from memory one at a time and executes them. This is known as the fetch-execute cycle。 2.genera…

企业化运维(6)_redis数据库

Redis&#xff08;Remote Dictionary Server )&#xff0c;即远程字典服务&#xff0c;是一个开源的使用ANSIC语言编写、支持网络、可基于内存亦可持久化的日志型、Key-Value数据库&#xff0c;并提供多种语言的API。 redis是一个key-value存储系统。和Memcached类似&#xff0…