数据结构与算法-等级考试试题(程序员软考 2014年秋顺序表)

单项选择（2014年秋程序员软考）

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

A、访问第i个元素(1≤i≤n)

B、删除第i个元素(1≤i≤n)

C、在第i个元素(1≤i≤n)之后插入一个新元素

D、查找与特定值相匹配的元素

答案解析

A

【解析】

线性表(a₁,a₂,…,a_n)采用顺序存储方式如下图所示，其逻辑上相邻的元素物理位置也是相邻的，因此，按照序号访问元素的速度是很快的。

访问第i个元素(1≤i≤n)的元素，仅需计算出a₁的存储位置再进行内存的随机访问操作即可，以LOC(a_i)表示线性表中第一个元素的存储位置，L表示每个元素所占存储单元的个数，则计算LOC(a_i)的方式如下:

LOC(a_i)=LOC(a₁)+(i-1)XL

再分析其他运算，不在表尾插入或删除时就需要移动其他元素，这是比较耗时的。查找与特定值相匹配的元素时，需要经过一个与表中多个元素进行比较的过程，相对于随机访问第i个元素，消耗更多时间。

讨论

数据结构与算法

已知某带权图G的邻接表如下所示，其中表结点的结构为:以下关于该图的叙述中，正确的是【】。

数组是程序语言提供的基本数据结构，对数组通常进行的两种基本操作是数组元素的【】。

某二叉排序树如下所示，新的元素45应作为【】插入该二叉树中。

完全二叉树的特点是叶子结点分布在最后两层，且除最后一层之外，其他层的结点数都达到最大值，那么25个结点的完全二叉树的高度(即层数)为【】。

特殊矩阵是非零元素有规律分布的矩阵，以下关于特殊矩阵的叙述中，正确的是【】。

设有字符串S和P，串的模式匹配是指确定【】。

以下关于栈和队列的叙述中，错误的是【】。

线性表采用单链表存储时的特点是【】。

正规式(ab|c)(0|1|2)表示的正规集合中有【】个元素。

若需在O(log2n)的时间内完成对数组的排序，且要求排序是稳定的，则可选择的排序方法是【】。

顺序表

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

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

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

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

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

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

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

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

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

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

线性表

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

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

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

在非空双向循环链表中q所指的结点后面插入p所指的结点的过程已经依次进行了以下3步：p->llink=q；p->rlink=q->rlink；q->rlink=p；第4步应该是____________________；（写出该步对应的语句）。

已知结点指针p、q分别表示双向链表中任意两个相邻结点（即p->rlink=q且q->llink=p），请写出删除q所指结点的程序段。

试写出在双向链表da中的插入操作算法，算法中插入位置的获取可直接引入getnodep(da,i)，其中参数da为双向链表，i是要插入的数据，要求算法中含有双向链表da的结点结构描述。

假设有两个按元素值递增有序排列的线性表A和B，均以带头结点的单链表作为存储结构，编写算法将A表和B表归并成一个按元素值递减有序排列的线性表C，并要求利用原表（A表和B表）的结点空间存放表C。

没有提供指针类型的语言，无法构造链式结构，该说法【】

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

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