一、填空题
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)。
发表回复