数据结构与算法-考研试题(计算机统考 2023年顺序表)

单项选择（2023年计算机统考）

下列对顺序存储的有序表 (长度为 n)实现给定操作的算法中平均时间复杂度为 O(1)的是【】

A、查找包含指定值元素的值

B、插入包含指定值元素的算法

C、删除第 i 个元素的算法

D、获取第 i 个值的算法

答案解析

D

【解析】

顺序表即顺序存储存储的线性表，其特点是：支持随机访问，但插入和删除比较麻烦。

链表即链式存储的线性表，其特点是：插入和删除比较容易，但不支持随机访问。

顺序表中只有随机访问元素时间复杂度为O(1) ，即根据元素位置（下标）访问元素时间复杂度为 O(1)。顺序存储的有序表即有序数组。

选项A，在有序数组中查找包含指定值的元素的位置最快的方法是用二分查找，时间复杂度为 O(logn) .

选项B，在有序数组中插入包含指定值的元素最快的方法是：首先用二分查找找到插入元素的位置，时间复杂度为 O(logn)；然后把位于插入元素后面的元素的位置后移一格，平均时间复杂度为 O(n). 综上，总的时间复杂度为 O(n).

选项C，删除第 i 个元素的最快的方法是：首先利用顺序表支持随机访问的性质找到第 i 个元素并删除，时间复杂度为 O(1)；然后把位于插入元素后面的元素的位置前移一格，平均时间复杂度为 O(n). 综上，总的时间复杂度为 O(n).

讨论

数据结构与算法

对n个关键码构成的序列采用直接插入排序法进行升序排序的过程是：在插入第i个关键码ki时，其前面的 i-1 个关键码已排好序，因此令k与 ki-1、ki-2、…，依次比较，最多到 k1为止，找到插入位置并移动相关元素后将ki插入有序子序列的适当位置，完成本趟(即第 i-1 趟)排序。以下关于直接插入排序的叙述中，正确的是【】。

对于下面的有向图，采用邻接链表存储时，顶点 0的表结点个数为2，顶点3的表结点个数为0，顶点1的表结点个数为【】。

对于下面的有向图，其邻接矩阵是一个【】的矩阵。

对下图所示的二叉树进行中序遍历(左子树、根结点、右子树)的结果是【】。

对关键码序列(12，24，15，56，20，87，69，9)采用散列法进行存储和查找，并设散列函数为H(Key)=Key%11(%表示整除取余运算)。采用线性控查法（顺地探查可用存储单元）解决冲突所构造的散列表为【】。

对关键码序列(9，12，15，20，24，29，56，69，87)进行二分查找(折半查找)，若要查找关键码15，则需依次与【】进行比较。

对于初始为空的栈S，入栈序列为a、b、c、d，且每个元素进栈、出栈各1次。若出栈序列的第一个元素为d，则合法的出栈序列为【】。

递归函数执行时，需要【】来提供支持。

表示“以字符a开头且仅由字符a、b构成的所有字符串”的正规式为【】。

下图所示的非确定有限自动机(s0为初态，s3为终态)可识别字符串【】。

顺序表

含有n个元素的线性表用顺序存储方式时，对其运算速度最快的操作是【】。

含有n个元素的线性表采用顺序存储方式时，对其运算速度最快的操作是【】。

含有n个元素的线性表采用顺序存储，等概率删除其中任一个元素，平均需要移动【】个元素。

对于长度为n的线性表(即n个元素构成的序列)，若采用顺序存储结构(数组存储)，则在等概率下，删除一个元素平均需要移动的元素数为【】。

若某线性表长度为n且采用顺序存储方式，则运算速度最快的操作是【】。

顺序表存储方式只能用于存储线性结构。

若长度为n的线性表采用顺序存储结构，在其第i个位置插入一个新元素的算法时间复杂度为【】。（1≤i≤n+1）

设A是一个线性表（a1,a1,...,an），采用顺序存储结构，则在等概率的前提下，平均每插入一个元素需要移动的元素个数为多少？若元素插在ai与ai+1之间（0≤i≤n-1）的概率为，则平均每插入一个元素所要移动的元素个数又是多少？

假设线性表的长度为n，且采用顺序存储结构存储。当在线性表的任何位置上插入一个数据元素的概率相同时，插入一个数据元素需要移动元素的平均个数为【】。

表长为n的顺序存储的线性表，当在任何位置上插入或删除一个元素的概率相等时，插入一个元素所需移动元素的平均个数为_______，删除一个元素需要移动元素的平均个数为_______。供选择的答案：A.(n-1)/2 B.n C.n+1 D.n-1 E.n/2 F.(n+1)/2 G.(n-2)/2

线性表

函数 Reverselist(LinkList headptr)的功能是将含有头结点的单链表就地逆置。处理思路是将链表中的指针逆转，即将原链表看成由两部分组成，已经完成逆置的部分和未完成逆置的部分，令s指向未逆置部分的第一个结点，并将该结点插入已完成部分的表头(头结点之后)，直到全部结点的指针域都修改完成为止。例如，某单链表如图所示，逆置过程中指针s的变化情况如图(a)(b)所示。链表结点类型定义如下：typedef struct Node{ int data， struct Node *next;}Node， *LinkList;void ReverseList (LinkList headptr){//含头结点的单链表就地逆置， headptr为头指针 LinkList p，s; if(__(1)__) return;//空链表(仅有头结点)时无需处理 p=__(2)__;//令p指向第一个元素结点 if (!p->next) return;//链表中仅有一个元素结点时无需处理 s= p->next;//s指向第二个元素结点 __(3)__=NULL;//设置第一个元素结点的指针域为空 while (s){ p=s;//令p指向未处理链表的第一个结点 s=__(4)__; p-> next= headptr-> next;//将p所指结点插入已完成部分的表头 headptr-> next=__(5)__; }}

线性表采用单循环链表存储的主要特点是【】

线性表的静态链表存储结构与顺序存储结构相比优点是【】

线性表是具有n个【】的有限序列。

在含有n个元素的顺序表中，算法时间复杂度为O(1)的操作是【】

线性表选用顺序存储结构表示的适用场合是____________________。

下列描述中，正确的是【】

线性表采用链表存储时，结点和结点内部的存储空间可以是不连续的。【】

将长度为n的单链表接在长度为m的单链表之后的算法时间复杂度为__________。

双向链表的优势是____________________。