关于数据结构和算法:南京晓庄学院数据结构与算法习题册2线性表

一、填空题

1. 在程序表中，等概率状况下，插入和删除一个元素均匀需挪动___个元素，具体挪动元素的个数与___和___无关。参考解答：表长的一半
表长和插入地位

解析：在程序表中插入 1 个元素，则能插入的地位为第 1 个地位、第 2 个地位、第 3 个地位、...、第 n + 1 个地位；故在第 i 个地位上插入一个结点的概率为 1 /(n+1)。如果在第 1 个地位插入元素，则本来的 n 个元素，从最初 1 个元素开始需顺次挪动 1 位，总共需挪动 n 个元素；如果在第 2 个地位插入元素，则本来的第 2 个地位的元素往后的每 1 个元素，从最初 1 个元素开始需顺次挪动 1 位，总共需挪动 n - 1 个元素；如果在第 n + 1 个地位插入元素，则无需挪动元素，总共需挪动 0 个元素。故插入一个元素均匀需挪动的元素个数 =

$$
\begin{aligned}
&\frac{1}{n+1}*n+\frac{1}{n+1}*n-1+…\frac{1}{n+1}*0\\
&=\frac{1}{n+1}*[n+(n-1)+…+1]\\
&=\frac{1}{n+1}*\frac{n*(n+1)}{2}\\
&=\frac{n}{2}
&\end{aligned}
$$

即插入一个元素均匀需挪动一半的元素。

2. 在一个长度为 n 的程序表的第 i（1≤i≤n+1）个元素之前插入一个元素，需向后挪动
___个元素，删除第 i（1≤i≤n）个元素时，需向前挪动___个元素。参考解答：n-i+1
n-i

解析：在第 i 个元素之前插入 1 个元素，即表明需将第 i 个元素，始终到第 n 个元素进行后移操作，第 i 个元素到第 n 个元素，共有 (n-i+1) 个元素，故需向后挪动 (n-i+1) 个元素。删除第 i 个元素，则意味着需将第 i + 1 个元素，到第 n 个元素进行前移操作，第 i + 1 个元素到第 n 个元素，共有 (n-i)【n-(i+1)+1】个元素，故需向前挪动(n-i) 个元素。3. 在单循环链表中，由 rear 指向表尾，在表尾插入一个结点 s 的操作程序是___；删除开始结点的操作程序为___
参考解答：表尾插入 1 个结点 s 的操作程序：s->next=rear->next;
rear->next=s;
rear=s;

解析：

二、选择题

1. 数据在计算机存储器内示意时物理地址与逻辑地址雷同并且是间断的，称之为：A. 存储构造
B. 逻辑构造
C. 顺序存储构造
D. 链式存储构造
参考解答：C

解析：存储构造：数据结构在计算机中的示意(又称为映像)，也称为物理构造。逻辑构造：数据元素之间的逻辑关系，即从逻辑关系上形容数据。顺序存储：把逻辑上相邻的元素存储在物理地位上也相邻的存储单元中，元素之间的关系
由存储单元的邻接关系来间接体现。链式存储：不要求逻辑上相邻的元素在物理地位上也相邻，借助批示元素存储地址的指针来示意元素
之间的逻辑关系。故 C 选项合乎题意。附思维导图：

2. 在 n 个结点的程序表中，算法的工夫复杂度是 O（1）的操作是：A. 拜访第 i 个结点（1≤i≤n）和求第 i 个结点的间接前驱（2≤i≤n）B. 在第 i 个结点后插入一个新结点（1≤i≤n）C. 删除第 i 个结点（1≤i≤n）D. 将 n 个结点从小到大排序
参考解答：A
解析：准备常识：线性表的顺序存储称为程序表。它是用一组地址间断的存储单元顺次存储线性表中的数据元素，从而使得逻辑上相邻的两个元素在物理地位上也相邻。A. 程序表最次要的特点是随机拜访，即通过首地址和元素序号可在 O(1)内找到指定的元素。故
A 选项正确。B. 程序表的插入均匀工夫复杂度为 O(n)，故排除 B 选项。C. 程序表的删除均匀工夫复杂度为 O(n)，故排除 C 选项。D. 程序表排序的工夫复杂度不可能是 O(1)。

3. 线性表 L 在状况下实用于应用链式构造实现。A. 需常常批改 L 中的结点值 
B. 需一直对 L 进行删除插入
C.L 中含有大量的结点 
D.L 中结点结构复杂
参考解答：B
解析：链式构造的线性表，插入和删除操作不须要挪动元素，只需批改头指针。故 B 选项合乎题意。

4. 单链表的存储密度
A. 大于 1 
B. 等于 1    
C. 小于 1 
D. 不能确定
参考解答：C
解析：(见下图)

三、判断题

1. 线性表的逻辑程序和存储程序总是统一的。参考解答：谬误

解析：顺序存储的线性表，即程序表，逻辑程序和存储程序总是统一的；链式存储的线性表，即链表，只具备逻辑上的程序性，链表中的元素离散地散布在存储空间中。故应改为线性表的逻辑程序总是统一的。存储构造并不总是统一的。2. 线性表的顺序存储构造优于链接存储构造。参考解答：谬误

解析：存储构造并没有相对的优劣之分；线性表的顺序存储的益处是能实现元素的随机拜访，以及存储密度高；线性表的链式存储的益处是插入、删除元素时，无需挪动元素。3. 设 p、q 是指针，若 p =q，则 *p=*q。参考解答：谬误

解析：(见下图)

4. 线性构造的基本特征是：每个元素有且仅有一个间接前驱和一个间接后继。参考解答：谬误

解析：第 1 个元素没有间接前驱；最初 1 个元素没有间接后继。

四、简答题

1. 剖析下列状况下，采纳何种存储构造更好些。(1)若线性表的总长度根本稳固，且很少进行插入和删除操作，但要求以最快的速度存取线性表中的元素。参考解答：程序构造
(2)如果 n 个线性表同时并存，并且在处理过程中各表的长度会动静发生变化。参考解答：链式存储
(3)形容一个城市的设计和布局。参考解答：链式存储

解析：

五、算法设计题

参考解答：
贴一下参考答案

这边，我还特意去写了一下 c ++ 代码。

#include <stdio.h>

void swap(int &a, int &b) {
    int temp = a;
    a = b;
    b = temp;
}

void Adjust(int A[], int n) {
    int i = 0, j = n - 1;
    while (i < j) {while (A[i] % 2 != 0) {i++;}
        while (A[j] % 2 == 0) {j--;}
        if (i < j) {swap(A[i], A[j]);
        }
    }
}

void Print(int A[],int n) {
    int i;
    for (i = 0; i < n; i++) {printf("%2d", A[i]);
    }
}

int main() {int A[10] = {1,6,5,7,6,9,3,2,7,4};
    Adjust(A,10);
    Print(A, 10);
    return 0;
}

后果如下：

还真能实现数组的前半部分都是奇数，后半局部全是偶数。while 循环外面嵌套的 2 个 while 循环是要害，
思维就是第 1 个 while 循环，找出偶数，第 2 个 while 循环，找出奇数，接着两者替换。

留神：C++ 反对传援用，而 C 语言不反对，如果要应用传援用，需将文件后缀改成 cpp。

参考解答：

void ListInsert(int x){if(elenum=arrsize){return;}
    int i,j;
    for(i=0;i<elenum;i++){if(A[i]>x){break;}
    }
    for(j=elenum-1;j>=i;j--){A[j+1]=A[j];
    }
    A[i]=x;
}

执行次数为 elenum 次，前 i 次用来找出插入的地位，前面 elenum- i 次用来挪动插入地位及之后的元素。
工夫复杂度为 O(n)。