MOOC 数据结构(天津财经大学)1458282162 最新慕课完整章节测试答案

第一章绪论单元测试

1、单选题：
​______ 是数据的最小单位。‌​‌
选项：
A: 数据项
B: 数据元素
C: 信息项
D: 表元素
答案: 【 数据项】

2、单选题：
‍以下说法不正确的是 ______。‌
选项：
A: 数据可由若干个数据元素构成
B: 数据项可由若干个数据元素构成 
C: 数据元素是数据的基本单位
D: 数据项是不可分割的最小标识单位
答案: 【 数据项可由若干个数据元素构成 】

3、单选题：
‍数据结构是指 ______ 的集合以及它们之间的关系。‌
选项：
A: 计算方法
B: 数据元素
C: 结构
D: 数据 
答案: 【 数据元素】

4、单选题：
​计算机所处理的数据一般具备某种内在联系，这是指 ______。‌
选项：
A: 元素内部具有某种结构
B: 数据项和数据项之间存在某种关系
C: 元素和元素之间存在某种关系 
D: 数据和数据之间存在某种关系
答案: 【 元素和元素之间存在某种关系 】

5、单选题：
‎在数据结构中，与所使用的计算机无关的是数据的 ______ 结构。‍
选项：
A: 物理
B: 逻辑和存储
C: 存储
D: 逻辑
答案: 【 逻辑】

6、单选题：
‏数据的逻辑结构可以分为 ______ 两类。​
选项：
A: 紧凑结构和非紧凑结构
B: 动态结构和静态结构
C: 内部结构和外部结构
D: 线性结构和非线性结构
答案: 【 线性结构和非线性结构】

7、单选题：
‎数据的逻辑结构是指 ______ 关系的整体。‏
选项：
A: 数据元素之间逻辑
B: 数据项之间逻辑
C: 数据类型之间
D: 存储结构之间
答案: 【 数据元素之间逻辑】

8、单选题：
​以下是数据结构中 ______ 属非线性结构。‌
选项：
A: 栈
B: 串
C: 队列
D: 平衡二叉树
答案: 【 平衡二叉树】

9、单选题：
‏以下属于逻辑结构是 ______。‌
选项：
A: 顺序表
B: 有序表
C: 双链表
D: 单链表
答案: 【 有序表】

10、单选题：
​以下不属于存储结构是 ______。‍
选项：
A: 顺序表
B: 单链表
C: 邻接表
D: 线性表
答案: 【 线性表】

11、单选题：
‏在计算机中存储数据时，通常不仅要存储各数据元素的值，而且还有存储 ______。‍
选项：
A: 数据的处理方法
B: 数据元素的类型 
C: 数据元素之间的关系
D: 数据的存储方法
答案: 【 数据元素之间的关系】

12、单选题：
‏数据结构在计算机内存中的表示是指 ______。‌
选项：
A: 数据的存储结构
B: 数据结构
C: 数据的逻辑结构 
D: 数据元素之间的关系
答案: 【 数据的存储结构】

13、单选题：
​在数据的存储中，一个节点通常存储一个 ______。‌
选项：
A: 数据结构
B: 数据类型
C: 数据元素
D: 数据项
答案: 【 数据元素】

14、单选题：
‍在决定选取任何类型的存储结构时，一般不多考虑 ______。‌
选项：
A: 各节点的值如何
B: 节点个数的多少
C: 对数据有哪些运算
D: 所用编程语言实现这种结构是否方便
答案: 【 各节点的值如何】

15、单选题：
‍数据在计算机的存储器中表示时，逻辑上相邻的两个元素对应的物理地址也是相邻的，这种存储结构称之为 ______。‍
选项：
A: 路基结构
B: 顺序存储结构
C: 链式存储结构
D: 以上都对
答案: 【 顺序存储结构】

16、单选题：
‏数据采用链式存储结构时，要求 ______。‌
选项：
A: 每个节点占用一片连续的存储区域
B: 所有节点占用一片连续的存储区域
C: 节点的最后一个数据域是指针类型
D: 每个节点有多少个后继就设多少个指针域
答案: 【 每个节点占用一片连续的存储区域】

17、单选题：
‍数据的运算 ______。‎
选项：
A: 是根据存储结构来定义的效率
B: 与采用何种存储结构有关
C: 有算术运算和关系运算两大类
D: 必须用程序设计语言来描述
答案: 【 与采用何种存储结构有关】

18、单选题：
‎_______ 不是算法的基本特性。‏
选项：
A: 可行性
B: 指令序列长度有限
C: 在规定的时间内完成 
D: 确定性
答案: 【 在规定的时间内完成 】

19、单选题：
​计算机中算法指的是解决某一问题的有限运算序列，它必须具备输入、输出、_______。‌
选项：
A: 可行性、可移植性和可扩充性
B: 可行性、有穷性和确定性
C: 确定性、有穷性和稳定性
D: 易读性、稳定性和确定性
答案: 【 可行性、有穷性和确定性】

20、单选题：
‏一个算法具有 ________  等设计目标。‏
选项：
A: 可行性
B: 至少有一个输入
C: 确定性 
D: 健壮性
答案: 【 健壮性】

21、单选题：
​以下关于算法的说法正确的是 ____________。‏
选项：
A: 算法最终必须由计算机程序实现
B: 算法等同于程序
C: 算法的可行性是指指令不能有二义性
D: 其他几个都是错误的
答案: 【 其他几个都是错误的】

22、单选题：
​算法的时间复杂度与 _______ 有关。‍
选项：
A: 问题规模
B: 计算机硬件性能
C: 编译程序质量
D: 程序设计语言
答案: 【 问题规模】

23、单选题：
‌算法分析的主要任务之一是分析 _______。‍
选项：
A: 算法是否具有较好地可读性
B: 算法中是否存在语法错误
C: 算法的功能是否符合设计要求
D: 算法的执行时间和问题规模之间的关系
答案: 【 算法的执行时间和问题规模之间的关系】

24、单选题：
‌算法的时间复杂度为O(n2)，表明该算法的 _______。‌
选项：
A: 问题规模是
B: 执行时间等于
C: 执行时间与成正比
D: 问题规模与成正比
答案: 【 执行时间与成正比】

25、单选题：
‍算法分析的目的是 _______。‏
选项：
A: 找出数据结构的合理性
B: 研究算法中输入和输出的关系
C: 分析算法的效率以求改进
D: 分析算法的易读性和文档性
答案: 【 分析算法的效率以求改进】

26、单选题：
‌以下函数中时间复杂度最小的是 _______。‍
选项：
A: T1(n)=nlog2n+5000n
B: T2(n)=-8000n
C: T3(n)=-6000n
D: T4(n)=20000log2n
答案: 【 T4(n)=20000log2n】

27、单选题：

以下说法中错误的是  _______。

‏

（1）原地工作算法的含义是指不需要任何额外的辅助空间

‏

（2）在相同的问题规模下n下，时间复杂度为O(nlog2n)的算法在执行时间上总是优于时间复杂度为O()的算法

‏

（3）时间复杂度通常是指最坏情况下，估计算法执行时间的一个上限

‏

（4）一个算法的时间复杂度与实现算法的语言无关

‏

‏

‏选项：
A: （1）
B: （1）、（2）
C: （1）、（4）
D: （3）
答案: 【 （1）、（2）】

28、单选题：
‌以下数据结构中哪一个是非线性结构？‍
选项：
A: 队列
B: 栈
C: 线性表
D: 二叉树
答案: 【 二叉树】

29、单选题：
下面程序的时间复杂为 _______。‌‏for（i=1，s=0； i<=n； i++） {t=1；for(j=1；j<=i；j++) t=t*j；s=s+t；}‌‏‌
选项：
A: O(n)
B: O()
C: O( )
D: O()
答案: 【 O()】

30、单选题：

‍一个算法的时间复杂度为(+log2n+14n)/，其数量级表示为  _______。

‍选项：
A: O(n) 
B: O()
C: O()
D: O()
答案: 【 O(n) 】

31、单选题：

​取算法的时间复杂度为O（），当n=5时执行时间为50s，当n=15时，执行时间为_______。

‍选项：
A: 3375
B: 1350
C: 2025
D: 675
答案: 【 1350】

32、单选题：
下面程序的时间复杂度为 _______。‎void fun( int n) { int i=1; while (i<=n) i=i*2}‎‎‎
选项：
A: O(n)
B: O()
C: O(log2n)
D: O(nlog2n)
答案: 【 O(log2n)】

33、单选题：
​下面程序的时间复杂度为 _______。‌​void fun( int n) { int i=1; while (i<=n) i=i*3}‌​‌
选项：
A: O(n) 
B: O()
C: O(nlog3n) 
D: O(log3n)
答案: 【 O(log3n)】

34、单选题：
‍下面程序的时间复杂度为 _______。‏‍void fun( int n) { int i=1, k=100; while (i<=n) {k++;  i+=2;} }‏‍‏
选项：
A: O(n)
B: O()
C: O(log2n)   
D: O(nlog2n)
答案: 【 O(n)】

35、单选题：
‍链表不具有的特点是            。‍
选项：
A: 插入、删除不需要移动元素
B: 可随机访问任一元素
C: 不必事先估计存储空间
D: 所需空间与线性长度成正比例
答案: 【 可随机访问任一元素】

36、单选题：
‌线性表是具有n个           的有限序列。‍‌‍
选项：
A: 表元素
B: 字符
C: 数据元素
D: 数据项
答案: 【 数据元素】

37、单选题：
‎从逻辑上可以把数据结构分为         。‌
选项：
A:  动态结构、静态结构
B: 顺序结构、链式结构
C: 线性结构、非线性结构 
D: 图结构、树状结构
答案: 【 线性结构、非线性结构 】

38、单选题：
​以下属于顺序表优点的是         。‌
选项：
A: 插入元素方便
B: 删除元素方便
C: 存储密度小
D: 以上都不对
答案: 【 以上都不对】

39、单选题：
‏算法指的是         。‏‏‏
选项：
A: 计算机程序
B: 解决问题的方法
C: 查找或排序过程
D: 求解特定问题的指令有限序列
答案: 【 求解特定问题的指令有限序列】

40、单选题：

‏某算法的时间复杂度为O()，表明该算法的         。

​选项：
A: 问题规模是 
B: 执行时间等于
C: 执行时间与正比
D: 问题规模与正比
答案: 【 执行时间与正比】

41、单选题：
‍数据结构在计算机内存中的表示是指       。‌
选项：
A: 数据的存储结构
B: 数据结构
C: 数据的逻辑结构
D: 数据元素之间的关系
答案: 【 数据的存储结构】

42、单选题：
‍下列哪一个不是数据结构研究的内容（    ）。‎
选项：
A: 数据间的逻辑关系
B: 数据元素值的大小
C: 数据的存储方式
D: 数据的运算
答案: 【 数据元素值的大小】

43、单选题：
‎算法分析的目的是（   ）。​
选项：
A: 找出数据结构的合理性
B: 研究算法中的输入和输出的关系
C: 分析算法的效率以求改进
D: 析算法的易懂性和文档性
答案: 【 分析算法的效率以求改进】

44、单选题：
‏二叉树是非线性数据结构，所以（    ）。‌
选项：
A: 它不能用顺序存储结构存储
B: 它不能用链式存储结构存储
C: 顺序存储结构和链式存储结构都能存储
D: 顺序存储结构和链式存储结构都不能使用
答案: 【 顺序存储结构和链式存储结构都能存储】

45、单选题：
‎计算机算法必须具备输入、输出、(      )5个特性。‎
选项：
A: 可行性、可移植性和可扩充性
B: 可行性、确定性和有穷性
C: 确定性、有穷性和稳定性
D: 易读性、稳定性和安全性
答案: 【 可行性、确定性和有穷性】

46、单选题：
‌数据结构研究的内容不涉及（   ）。​
选项：
A: 算法用哪个高级语言来描述
B: 数据的运算如何实现
C: 数据如何组织
D: 数据如何存储
答案: 【 算法用哪个高级语言来描述】

第二章线性表单元测试

1、单选题：
​线性表是具有n个 ______ 的有限序列。‍
选项：
A: 表元素
B: 字符
C: 数据元素
D: 数据项
答案: 【 数据元素】

2、单选题：
‍线性表是 _______。‌
选项：
A: 一个有限序列，可以为空
B: 一个有限序列不可以为空
C: 一个无限序列，可以为空
D: 一个无限序列，不可以为空
答案: 【 一个有限序列，可以为空】

3、单选题：
‎关于线性表的正确说法是 _______。‏
选项：
A: 每个元素都有一个前驱和一个后继元素
B: 线性表中至少有一个元素
C: 表中元素的排序顺序必须是由小到大或由大到小
D: 除第一个元素和最后一个元素外，其余元素有且仅有一个前驱和一个后继元素
答案: 【 除第一个元素和最后一个元素外，其余元素有且仅有一个前驱和一个后继元素】

4、单选题：
‌线性表采用链表存储时，其存放各个元素的单元地址是 _______。‎
选项：
A: 必须是连续的
B: 一定是不连续的
C: 部分地址必须是连续的
D: 连续与否均可以
答案: 【 连续与否均可以】

5、单选题：
​链表不具备的特点是 _______。​
选项：
A: 可随机访问任一节点
B: 插入删除不需要移动元素
C: 不必事先估计存储空间
D: 所需空间与其长度成正比
答案: 【 可随机访问任一节点】

6、单选题：
‏线性表的静态链表存储结构与顺序存储结构相比，优点是 _______。‌
选项：
A: 所有的操作算法实现简单
B: 便于随机存取
C: 便于插入和删除
D: 便于利用零散的存储器空间
答案: 【 便于插入和删除】

7、单选题：
‍线性表的顺序存储结构和链式存储结构相比，优点是 _______。‎
选项：
A: 所有的操作算法实现简单
B: 便于随机存取 
C: 便于插入和删除
D: 节省存储空间
答案: 【 便于随机存取 】

8、单选题：
‏设线性表有n个元素，以下操作中，_______在顺序表上实现比在链表上实现效率高。‍
选项：
A: 输入第i（1<=i<=n）个元素值
B: 交换第1个元素第2个元素的值
C: 顺序输出这n个元素的值
D: 输出与给定值x相等的元素在线性表中的符号
答案: 【 输入第i（1<=i<=n）个元素值】

9、单选题：
‎对于一个线性表，既要求能够较快地进行插入和删除操作，又要求存储结构能够反映数据元素之间的逻辑关系，则应采用  _______ 存储结构。‍
选项：
A: 顺序
B: 链式
C: 散列
D: 索引
答案: 【 链式】

10、单选题：
​设线性表中有n个元素，以下操作，_______ 在单链表上实现要比在顺序表上实现效率高。‍
选项：
A: 删除指定位置元素的后一个元素
B: 在第n个元素的后面插入一个新元素
C: 顺序输出前k个元素
D: 交换第i个元素和第n-i+1个元素的值
答案: 【 删除指定位置元素的后一个元素】

11、单选题：
‎以下属于顺序表的优点是  _______。​
选项：
A: 插入元素方便
B: 删除元素方便
C: 存储密度大
D: 以上都不对
答案: 【 存储密度大】

12、单选题：
‍要求线性表采用静态空间分配方式，且插入和删除操作时不需要移动元素，采用的存储结构是  _______。‌
选项：
A: 单链表
B: 静态链表
C: 双链表
D: 顺序表
答案: 【 静态链表】

13、单选题：
‏如果最常用的操作时取第i个元素及前驱元素，则采用  _______ 存储方式最节省时间。‌
选项：
A: 单链表
B: 双链表
C: 循环单链表
D: 顺序表
答案: 【 顺序表】

14、单选题：
‌与单链表相比，双链表的优点之一是  _______。‌
选项：
A: 插入、删除操作更简单
B: 可以进行随机访问
C: 可以省略表头指针或表尾指针
D: 访问前后相邻节点更方便
答案: 【 访问前后相邻节点更方便】

15、单选题：
‎在长度为n的顺序表中插入一个元素的时间复杂度为 _______。‏
选项：
A: O(n) 
B:  O()
C: O(log2n)   
D: O(1)
答案: 【 O(n) 】

16、单选题：
‌在长度为n的顺序表中删除一个元素的时间复杂度为 _______。‎
选项：
A:  O(1)       
B:  O()
C: O(log2n)
D: O(n)
答案: 【 O(n)】

17、单选题：
​在两个各有n个元素的递增有序顺序表归并成一个有序顺序表，其最少的比较次数为_______。‏
选项：
A: n
B: 2n-1
C: 2n
D: n-1
答案: 【 n】

18、单选题：
‎将两个长度为n、m的递增有序表归并成一个有序顺序表，其最少的比较次数是_______。（MIN表示取最小值）‍
选项：
A: n
B: m
C: MIN(m, n)
D: 不确定
答案: 【 MIN(m, n)】

19、单选题：
‌在带头节点的单链表L为空的判定条件是 _______。​
选项：
A:  L==NULL
B: L->NEXT==NULL
C:  L->NEXT==L
D:  L!=NULL
答案: 【 L->NEXT==NULL】

20、单选题：
​对于一个具有n个元素的线性表，建立其单链表的时间复杂度为  _______。‍
选项：
A:  O(log2n)
B: O(1)
C:  O(n)
D:  O()
答案: 【  O(n)】

21、单选题：
‍在单链表中查找指定值的节点的时间复杂度是  _______。‏
选项：
A: O(log2n)
B: O(1)
C: O() 
D: O(n)
答案: 【 O(n)】

22、单选题：
‍以下关于单链表的叙述中，不正确的是 _______。‌
选项：
A: 节点除自身信息外还包括指针域，因此存储密度小于顺序存储结构
B: 逻辑上相邻的元素物理上不必相邻
C: 可以通过头节点直接计算第i个节点的存储地址
D: 插入、删除运算操作简单，不必移动节点
答案: 【 可以通过头节点直接计算第i个节点的存储地址】

23、单选题：
‌在单链表中，增加一个头节点的目的是为了 _______。‍
选项：
A: 使单链表至少有一个节点
B: 标识链表中重要节点的位置
C: 方便运算的实现 
D: 说明单链表是线性表的链式存储结构
答案: 【 方便运算的实现 】

24、单选题：
‍在一个具有n个节点的有序单链表中插入一个新节点并仍然保持有序的时间复杂度是 _______。‌
选项：
A: O(nlog2n)
B: O(1)
C:  O(n)
D: O()
答案: 【  O(n)】

25、单选题：
‌将长度为m的单链表链接在长度为n的单链表之后的算法时间复杂度为 _______。‏
选项：
A: O(1)
B: O(n)
C: O(m)
D: O(m+n)
答案: 【 O(n)】

26、单选题：
‍已知一个长度为n的单链表中所有节点是递增有序的，以下叙述中正确的是 _______。‍
选项：
A: 插入一个节点使之有序的算法的时间复杂度为O(1)
B: 删除最大值节点使之有序的算法的时间复杂度为 O(1)
C: 找最小值节点的算法的时间复杂度为 O(1)
D: 以上都不对
答案: 【 找最小值节点的算法的时间复杂度为 O(1)】

27、单选题：
‌在一个长度为n（n>1）的带头节点的单链表上，另设有尾指针r（指向尾节点），执行_______操作与链表的长度有关。‍
选项：
A: 删除单链表中的第一个元素
B: 删除单链表的尾节点
C: 在单链表中第一个元素前插入一个新节点
D: 在单链表最后一个元素后插入一个新节点
答案: 【 删除单链表的尾节点】

28、单选题：
‍在一个双链表中，在*p节点之后插入节点*q的操作是 _______。‍
选项：
A: q->prior = p；p-> next=q；p -> next -> prior =q； q ->next = p -> next；
B: q ->next = p -> next；p -> next -> prior =q；p-> next=q；q->prior = p；
C: p-> next=q；q->prior = p；q ->next = p -> next；p -> next -> prior =q；
D: p -> next -> prior =q；q->prior = p；p-> next=q；q ->next = p -> next；
答案: 【 q ->next = p -> next；p -> next -> prior =q；p-> next=q；q->prior = p；】

29、单选题：
‌在一个双链表中，在*p节点之前插入节点*q的操作是 _______。‍
选项：
A: p -> prior = q；q-> next=p；p -> prior ->next=q； q ->prior= p -> prior；
B: q ->prior= p -> prior；p -> prior ->next=q；q-> next=p；p -> prior = q->next；
C: q-> next=p；p -> next=q；q-> prior ->next= q；q-> next=p；
D: p -> prior ->next=q；q-> next=p；q -> prior = p->prior；p -> prior = q；
答案: 【 p -> prior ->next=q；q-> next=p；q -> prior = p->prior；p -> prior = q；】

30、单选题：
‎在一个双链表中， 删除*p节点的操作是 _______。‌
选项：
A: p -> prior –>next= p-> next；p ->next-> prior = p -> prior；
B: p ->prior= p -> prior -> prior；p -> prior ->prior = p；
C: p-> next -> prior = p；p-> next=p-> next-> next；
D: p -> next= p->prior -> prior；p-> prior = p->prior->prior；
答案: 【 p -> prior –>next= p-> next；p ->next-> prior = p -> prior；】

31、单选题：
​在一个双链表中， 删除*p节点之后的一个节点，其时间复杂度为_______。‍
选项：
A: O(nlog2n) 
B: O(1) 
C: O(n)
D: O()
答案: 【 O(1) 】

32、单选题：
‏非空的循环单链表L的尾节点（由p所指向）满足 _______。‎
选项：
A: p-> next == NULL
B: p == NULL
C: p -> next == L
D:  p==L
答案: 【 p -> next == L】

33、单选题：
‏带表头结点的双循环链表L为空表的条件是 _______。​
选项：
A: L== NULL
B: L-> next -> prior == NULL
C: L -> prior == NULL
D: L -> next == L  
答案: 【 L -> next == L  】

34、单选题：
‍某线性表最常用的操作是在尾元素之后插入一个元素和删除尾元素，则采用 _______ 存储方式最节省运算时间。‌
选项：
A: 单链表
B: 循环单链表
C: 双链表
D: 循环双链表
答案: 【 循环双链表】

35、单选题：
‏如果对含有n（n>1）个元素的线性表的运算只有4种，即删除第一个元素、删除尾元素、在第一个元素前面插入新元素、在尾元素的后面插入新元素，则最好使用_______。‍
选项：
A: 只有尾节点指针没有头节点的循环单链表
B: 只有尾节点指针没有头节点的非循环双链表
C: 只有开始数据节点指针没有尾节点指针的循环双链表
D: 既有表头指针也有表尾指针的循环单链表
答案: 【 只有开始数据节点指针没有尾节点指针的循环双链表】

36、单选题：
​在某线性表最常用的操作是在尾元素之后插入一个元素和删除第一个元素。故采用_______ 存储方式最节省时间。‎
选项：
A: 单链表
B: 仅有头节点指针的循环单链表
C: 双链表
D: 仅有尾指针的循环单链表
答案: 【 仅有尾指针的循环单链表】

37、单选题：
​​​两个表长都为n、不带表头结点的单链表，结点类型都相同，头指针分别为h1与h2，且前者是循环链表，后者是非循环链表，则 _______。​
选项：
A: 对于两个链表来说，删除首节点的操作，其时间复杂度都是O(1)
B: 对于两个链表来说，删除尾节点的操作，其时间复杂度都是O(n)
C: 循环链表要比非循环链表占用更多的内存空间
D: h1和h2是不同类型的变量
答案: 【 对于两个链表来说，删除尾节点的操作，其时间复杂度都是O(n)】

38、单选题：
‍在长度为n的 _______ 上，删除第一个元素，其算法的时间复杂度为O(n)。‎
选项：
A: 只有表头指针的不带表头节点的循环单链表
B: 只有表尾指针的不带表头节点的循环单链表
C: 只有表尾指针的带表头节点的循环单链表
D: 只有表头指针的带表头节点的循环单链表
答案: 【 只有表头指针的不带表头节点的循环单链表】

39、单选题：
‎下面关于线性表的叙述错误的是 _______。‎
选项：
A: 线性表采用顺序存储必须占用一片连续的存储空间        
B: 线性表采用链式存储不必占用一片连续的存储空间
C: 线性表采用链式存储便于插入和删除操作的实现
D: 线性表采用顺序存储便于插入和删除操作的实现
答案: 【 线性表采用顺序存储便于插入和删除操作的实现】

40、单选题：
‏对于双链表，在两个节点之间插入一个新节点是，需要修改 _______ 个指针域。‎
选项：
A: 1
B: 2
C: 3
D: 4
答案: 【 4】

41、单选题：
​在单链表中，要删除某一指定的节点，必须找到该节点的 _______ 节点。‍
选项：
A: 后继
B: 头节点
C: 前驱
D: 尾节点
答案: 【 前驱】

42、单选题：
​求一个单链表长度的算法的时间复杂度为 （     ）。​
选项：
A: O(log2n)
B:   O(n)
C: O(1) 
D:  O()
答案: 【   O(n)】

43、单选题：
‎在顺序表中删除一个元素所需要的时间（    ）。‍
选项：
A: 与删除元素的位置及顺序表的长度都有关
B: 只与删除元素的位置有关
C: 与删除任何其他元素所需要的时间相等
D: 只与顺序表的长度有关
答案: 【 与删除元素的位置及顺序表的长度都有关】

44、单选题：
‏某算法在含有n（n≥1）个节点的单链表中查找值为x节点，其时间复杂度是（    ）。‏
选项：
A: O（log2n）
B: O(1) 
C: O(n)
D: O（）
答案: 【 O(n)】

45、单选题：
​以下关于单链表的叙述中正确的是（    ）。‍​Ⅰ. 节点除自身信息外还包括指针域，存储密度小于顺序表‍​Ⅱ. 找第i个节点的时间为O(1)‍​Ⅲ. 在插入、删除运算时不必移动节点‍​‍
选项：
A: 仅Ⅰ、Ⅱ 
B: 仅Ⅱ、Ⅲ
C: 仅Ⅰ、Ⅲ
D: Ⅰ、Ⅱ、Ⅲ
答案: 【 仅Ⅰ、Ⅲ】

46、单选题：
‌设线性表中有n个元素，以下操作，(     ) 在单链表上实现要比在顺序表上实现效率高。‏‌‏
选项：
A: 在第n个元素的后面插入一个新元素
B: 顺序输出前k个元素
C: 交换第i个元素和第n-i+1个元素的值
D: 删除指定位置元素的后一个元素
答案: 【 删除指定位置元素的后一个元素】

47、单选题：
‌如果最常用的操作时取第i个元素及前驱元素，则采用(      ) 存储方式最节省时间。​
选项：
A: 单链表  
B: 顺序表
C: 循环单链表
D: 双链表
答案: 【 顺序表】

48、单选题：
‍在一个具有n个节点的有序单链表中插入一个新节点并仍然保持有序的时间复杂度是 (    )。‏
选项：
A: O() 
B: O(1)
C:  O(n) 
D: O(nlog2n)
答案: 【  O(n) 】

49、单选题：
‌在一个双链表中，在*p节点之后插入节点*q的操作是（   ）。‍
选项：
A: q ->next = p -> next；p -> next -> prior =q；p-> next=q；q->prior = p；
B: p-> next=q；q->prior = p；q ->next = p -> next；p -> next -> prior =q；
C: p -> next -> prior =q；q->prior = p；p-> next=q；q ->next = p -> next；
D: q->prior = p；p-> next=q；p -> next -> prior =q； q ->next = p -> next；
答案: 【 q ->next = p -> next；p -> next -> prior =q；p-> next=q；q->prior = p；】

50、单选题：
‏如果对含有n（n>1）个元素的线性表的运算只有4种，即删除第一个元素、删除尾元素、在第一个元素前面插入新元素、在尾元素的后面插入新元素，则最好使用（     ）。‍
选项：
A: 只有尾节点指针没有头节点的循环单链表   
B: 只有尾节点指针没有头节点的非循环双链表
C: 既有表头指针也有表尾指针的循环单链表
D: 只有开始数据节点指针没有尾节点指针的循环双链表
答案: 【 只有开始数据节点指针没有尾节点指针的循环双链表】

51、单选题：
‍下列关于线性表的叙述中，错误的是 （    ）。‌‍‌
选项：
A: 采用顺序存储，必须占用一片连续的存储单元，存储密度大
B: 采用顺序存储，便于进行插入和删除操作
C: 采用链式存储，不必占用一片连续的存储单元，存储密度小
D: 采用链式存储，便于插入和删除操作
答案: 【 采用顺序存储，便于进行插入和删除操作】

52、单选题：
‏若线性表最常用的操作使存取任一指定序号的元素和在最后进行插入和删除操作，则利用（   ）存储方式最节省时间。‌‏‌
选项：
A: 顺序表
B: 双向链表
C: 双向循环链表
D: 单向循环链表
答案: 【 顺序表】

53、单选题：
‏某线性表中最常用的操作使在最后一个元素之后插入一个元素和删除第一个元素，则采用（   ）存储方式最节省时间。‍‏‍
选项：
A: 单链表
B: 不带头结点的单向循环链表
C: 双向链表
D: 不带头结点且有尾指针的单向循环链表
答案: 【 不带头结点且有尾指针的单向循环链表】

54、单选题：
​将两个有n个元素的有序表归并成一个有序表，其最少的比较次数为（   ）。​​​
选项：
A: n
B: 2n-1 
C: 2n
D: n-1
答案: 【 n】

55、单选题：
‍带头结点的双向循环链表L为空的条件是（   ）。‌‍‌
选项：
A:  L==NULL 
B: L->next->prior==NULL
C: L->prior==NULL
D: L-> next==L &&  L->prior==L
答案: 【 L-> next==L &&  L->prior==L】

56、单选题：
‌设线性表有n个数据元素，以下操作种，（   ）在顺序表上实现比在链表上实现的效率更高。​
选项：
A: 输出第i(1≤i≤n)个元素
B: 交换第1个元素与第2个元素
C: 顺序输出n个元素的值 
D: 输出与给定值x相等的元素在线性表中的序号
答案: 【 输出第i(1≤i≤n)个元素】

57、单选题：
‍在顺序表中插入或删除一个元素的时间复杂度为（    ）。‌
选项：
A: O(n) 
B: O(log2n)  
C:  O() 
D: O(1)
答案: 【 O(n) 】

58、单选题：
​若某表最常用的操作是在最后一个结点之后插入一个结点或删除第一个结点，则采用（  ）存储结构最节省运算时间。‏​‏
选项：
A: 单链表
B: 带头指针的循环单链表
C: 双向链表
D: 带头指针的循环双向链表
答案: 【 带头指针的循环双向链表】

59、单选题：
‌已知两个长度分别为m和n的升序链表，若将它们归并为一个长度为m+n的非降序链表，则最坏情况下的时间复杂度为（    ）。‏‌‏
选项：
A: O(min(m,n))
B: O(m×n) 
C: O(m+n)
D: O(max(m,n))
答案: 【 O(m+n)】

60、单选题：
‎下列程序的时间复杂度为（   ）。‎‎count=0;‎‎for(k=1; k<n; k*=2)‎‎   for(j=0; j<n; j++) count++;‎
选项：
A: O(n) 
B: O(log2n) 
C: O(nlog2n) 
D: O()
答案: 【 O(nlog2n) 】

61、单选题：
‏下列函数的时间复杂度为（   ）。‌‏int fact(int n) {   //n>0‌‏  if (n<=1) return 1;‌‏      return n*fact(n-1); ‌‏ }‌
选项：
A: O(n)
B:  O(log2n)
C: O(1)
D: O()

答案: 【 O(n)】

62、单选题：
‏设n为描述问题规模的非负整数，下面程序段的时间复杂度为（   ）。‎‏x =2;‎‏while(x<n/2) x=2*x;‎
选项：
A: O(n)
B: O(log2n) 
C: O(1)
D: O()
答案: 【 O(log2n) 】

63、单选题：
‎下列函数的时间复杂度是（   ）。‌int func(int n) {‌int i=0, sum=0;‌while(sum<n)sum+=++i;‌return i;   ‌}‌
选项：
A: O(n)
B: O(logn) 
C: O(nlogn)
D: O()
答案: 【 O()】

64、单选题：
设n是描述问题规模的非负整数，下列程序段的时间复杂度是（   ）。‎x=0;‎while(n>=(x+1)*(x+1))x=x+1;‎
选项：
A: O(n) 
B: O(logn)
C: O() 
D: O()
答案: 【 O()】

65、单选题：
‎已知一个带有表头结点的双向链表L，prev和next分别是指向其直接前驱和直接后继结点的指针，现要删除指针p所指的结点，正确的语句序列是（   ）。‏
选项：
A: p->next->prev=p->prev; p->prev->next=p->prev; free(p);
B: p->next->prev=p->next; p->prev->next=p->next; free(p);
C: p->next->prev=p->next; p->prev->next=p->prev; free(p);
D: p->next->prev=p->prev; p->prev->next=p->next; free(p);
答案: 【 p->next->prev=p->prev; p->prev->next=p->next; free(p);】

66、单选题：

‍已知表头元素为c的单链表在内存中的存储状态如下表所示：

‎

‍

‎

‍现将f存放于1014H处并插入到单链表中，若f在逻辑上位于a和e之间，则a, e, f的“链接地址”依次是（  ）。

‎

‍

‎选项：
A: 1010H, 1014H ,1004H
B: 1010H, 1004H, 1014H
C: 1014H, 1010H, 1004H
D: 1014H, 1004H, 1010H
答案: 【 1014H, 1004H, 1010H】

67、单选题：
‎在只有头指针且长度为n（n≥1）的双向链表L中，在尾节点之后插入一个新节点的时间复杂度为（ ）。‏
选项：
A: O(1)
B: O(n)
C: O(nlog2n)
D: O()
答案: 【 O(n)】

68、单选题：
​在一个单链表L中， 已知P的前趋节点为Q，将S结点插入L中作为P的前趋，则执行的操作是（   ）。​
选项：
A: S->next= P->next; P->next=S;
B: Q->next=S;S->next=P;
C: P->next= S->next; S->next=P;
D: P->next=S;S->next=Q;
答案: 【 Q->next=S;S->next=P;】

第三章栈和队列单元测试

1、单选题：
‏元素A、B、C、D依次进栈后，栈顶元素是 _______。‍
选项：
A: A
B: B
C: C
D: D
答案: 【 D】

2、单选题：
经过以下运算后， x的值是 _______。‍InitStack (s); Push(s, a); Push(s, b); Pop(s, x); GetTop(s,x)‍‎‍
选项：
A: a
B: b
C: 1
D: 0
答案: 【 a】

3、单选题：
经过以下栈运算后，StackEmpty(s)的值是 _______。‌InitStack (s); Push(s, a); Push(s, b); Pop(s, x); Pop(s,y)‌‌‌
选项：
A: a
B: b
C: 1
D: 0
答案: 【 1】

4、单选题：
已知一个栈的进栈序列是ABC，出栈序列为CBA，经过栈的操作是 _______。‍‏‍
选项：
A: push,pop,push,pop,push,pop
B: push, push, push, pop, pop, pop
C: pu