数据结构（线性表习题1）

因为题目比较多，那我就一天更新一点点吧~

1 线性表可以用顺序表和链表存储，试问：

（1）两种储存各有哪些优缺点；

顺序表：

优点：

存储密度大

可以随机存储任意元素

缺点：

存储空间不灵活，浪费储存空间

静态存储，不能自动扩充

运算空间复杂度高，插入，删除需要移动大量的元素

链表：

优点：

结点空间可以动态申请和释放；

插入和删除不需要移动数据元素

缺点：

储存密度小，每个结点域占额外空间

非随机存储元素

（2）如果有n个表同时共存，并且在处理过程中各表的长度会发生动态变化，表的总数也可能自动改变，在这种情况下，应该选用哪种储存，为什么？

选链式存储结构，可以动态申请空间，不受表长度的限制，表中插入，删除操作的时间复杂度为O（1）

（3）若线性表的总数基本稳定，且很少进行插入和删除，但要求以最快的速度存取线性表中的元素，那么应采用哪种存储结构？为什么？

选用顺序存储结构，顺序表可以随机存取，时间复杂度为O(1)

2顺序表的插入和删除要求仍然保持各个元素原来的次序，设在等概率情况下，对127个元素顺序表进行插入，平均需要移动多少个元素，删除一个元素又平均需要移动多少个元素？

 若设顺序表中已有 n = last+1 个元素，last 是顺序表的数据成员，表明最
后表项的位置。又设插入或删除表中各个元素的概率相等，则在插入时因有 n+1
个插入位置(可以在表中最后一个表项后面追加)，每个元素位置插入的概率为
1/(n+1)，但在删除时只能在已有 n 个表项范围内删除，所以每个元素位置删除
的概率为 1/n。
 

插入：

AMN=1/(n+1)*(对xi进行求和）

=(1/(n+1))*(0+n)*(n+1)/2

=n/2

删除:

AMN=1/n*(对xi移动的次数进行求和）

=(1/n)((0+n-1)*n)/2    (等差数列求和公式的应用）

=（n-1)/2

本质上是求期望

∴插入时平均移动元素个数 AMN(Averagy Moving Number )为 127/2 删除时平均移动元素个数 AMN 为 126/2

4 判断下列叙述的对错

（1）

const int maxSize=30;

char a[maxSize];

则这种数组在程序执行过程中不能扩充

对

 

（2）如果采用如下方法定义一维字符数组

const int maxSize =30;

char*a=new char[maxSize];

则这种数组在程序执行过程中不能被执行

错

（3）数组是一种静态的储存空间分配，就是说，在程序设计过程中必须预先定义数组的数据类型和储存空间的大小，由编译程序在编译时进行分配；

错

在运行期间也可以分配

int(*p)[6];
p=(int(*)[6])malloc(sizeof(int[6])*1);

*p是个int[6](而不是int*) ,sizeof(*p)是24而不是4 ,也就是说在堆上创建了一个int[6]，但这个空间是在运行期分配的

（4）

二维数组可以视为数组元素为一维数组的一维数组，所以，二维数组不是线性结构

（5）

数组是一种复杂的数据结构，数组元素之间的关系既不是线性的也不是树型的；

错，一对一的线性关系

（6）顺序表可以利用一维数组表示，因此顺序表和一维数组在结构上是一致的，它们可以通用；

错，数组存储只是顺序存储中的最简单的方式，不能将两者描述为相同；

（7）在顺序表中，逻辑相邻的元素在物理上不一定相邻

对，假如使用链式存储结构

（8）顺序表和一维数组一样，都可以按照下标随机访问，顺序表还可以从某一指定元素开始，向后或者向前逐个元素随机访问；

错，顺序表有顺序存储和链式存储，假如使用的方式为链式存储则不能按照下标访问；

（9）n阶三对角阵总共n^2个矩阵元素最多只有3*n-2个非0元素，因此它们是稀疏矩阵

对

（10）插入与删除操作时数据结构中最基本的两个操作，因此这两种操作在数组中也经常使用

错误，不知道是不是因为连接词的原因，还有，好像不常见吧；

（11）使用三元组表示稀疏矩阵中的非0元素能节省时间

对

（12）用字符数组储存长度为n的字符串，数组长度至少为n+1;

对，字符串是以‘\0’结尾的， 所以如果字符串长度为n。也就是有n个字符，那么加上‘\0’就是有 n+1个字符。

设有一个线性表（e0,e1,...en-1)存放在一个一维数组A【arraySize]中的前n个位置，请编写一个函数将这个线性表原地逆置，即将数组的前n个原址内容置换为（en-1,en-2...e1,e0).

函数：

template  

void reverse(T A[ ],int n)//传入参数和数组,由于类型未知，所以使用类模板

T temp;//设置临时变量

for(int i=0;i<（n-1)/2;i++)

{

temp=A[i];

a[i]=a[n-i-1];

a[n-i-1]=temp;}

//交换值,这里有个规律，就是交换（n-1)/2次，第i项和第n-1-i项交换；

2

假设数组A[arraySize]有很多个非0元素，试写出一个函数，将Az中所有元素的非0元素依次转移到数组A的前端A[i](0<=i<=arraySize)

我的思路：

总感觉有点不对劲

template

void fun(T A[],int n)

{

for(int i=0;i

{

if(A[i]=0)

{

for(int j=i;j

{

A[j]=A[j+1];

}

} } }

参考书的思路：

/* 参考书思路代码：将所有非0元素移动到A数组的前端 */
/* a[]指的是要被移动的数组；a指的是数组中的元素个数 */
void moveElement(int a[],int n) {// i记录从左向右为0的元素下标；j记录从左向右非0的元素下标 
    int i=-1;// i记录零元素的下标 
    int j=0;// j记录非零元素的下标
    while(j         // 从左向右寻找非零元素 
        while(a[j]==0){
            j++;
        }
        // 从左向右寻找零元素 
        while(a[i]!=0){
            i++;
        }
        // 交换零元素与非零元素
        if(a[j]!=0&&a[i]==0){
            int temp=a[i];
            a[i]=a[j];
            a[j]=temp;
            i++;
            j++;
        } 
    } 
}

3试着编写一个函数，将一个有n个非0元素的整数一维数组A[n]拆分成两个一维数组，使得A【】中大于0的元素存放在B[]中，小于0的元素存放在C[]中；
 

void fenjie(int A[],int B[],intC[],int n,int &pb,int &pc);//传入数组，后面使用引用目的是可以修改
{
    pb=pc=-1;
    for (int k=0;k         if (A[k] > 0)
            B[++pb] = A[k];
        else C[++pc]=A[k];
    }
}

使用引用是题目的关键，突破口；

4已知在一维数组A[m+n]中依次存放着两个顺序表（a0,a2...am-1)和（b0,b2...bn-1)

试着编写一个函数，将数组中两个顺序表的位置互换，即将（b0,b2...bn-1)存放在（a0,a2...am-1）前面；

思路：

将A[m]逆序再将A[n]逆序，最后将A[m+n]整体逆序；

这里不懂得话可以简单写个数组测试一下；

template

int turnover( A[],int m,int n);//传入参数

{

int temp;

for(int i=0;i<(m-1)/2;i++){//对A1进行逆序

temp=A[i];

A[i]=A[m-i-1];

A[m-i-1]=temp;

}

for(int j=m;j

temp=A[j];

A[j]=A[m+n-1-j];

A[m+n-1-j]=temp;}

for(int k=0;k<(m+n)/2;k++)//整体逆序

{

temp=A[k];

A[k]=A[m+n-1-k];

A[m+n-1-k]=temp;}}