1、计算机学科专业基础综合数据结构-算法复杂度相关问题专练、线性表及答案解析(总分：92.06，做题时间：90 分钟)一、B单项选择题/B(总题数：21，分数：21.00)1.线性表是_。 A.一个有限序列，可以为空 B.一个有限序列，不能为空 C.一个无限序列，可以为空 D.一个无限序列，不能为空（分数：1.00）A.B.C.D.2.若想在单链表中删除某结点 p(p 既不是第一个，也不是最后一个结点)的直接后继，则应执行_操作。 A.pnext=pnextnext B.p=pnext;pnext=pnextnext C.pnext=pnext D.p=pnextnext（分数：1.00）A.B.
2、C.D.3.已知 L 是带表头结点的单链表，则删除首元结点的语句是_。 A.L=Lnext B.Lnext=Lnextnext C.L=Lnextnext D.Lnext=L（分数：1.00）A.B.C.D.4.用链表表示线性表的优点是_。 A.便于随机存取 B.花费的存储空间较顺序存储少 C.便于插入和删除 D.数据元素的物理顺序与逻辑顺序相同（分数：1.00）A.B.C.D.5.在单链表中，增加一个头结点的目的是为了_。 A.使单链表至少有一个结点 B.标识表结点中首结点的位置 C.方便运算的实现 D.说明单链表是线性表的链式存储（分数：1.00）A.B.C.D.6.已知单链表 A 的长度
3、为 m，单链表 B 的长度为 n，若将 B 链接在 A 的末尾，在没有链尾指针的情况下，算法的时间复杂度应为_。 A.O(1) B.O(m) C.O(n) D.O(m+n)（分数：1.00）A.B.C.D.7.从一个具有 n 个结点的有序单链表中查找其值等于 x 的结点时，在查找成功的情况下，需要平均比较_个结点。 A.n B.n/2 C.(n-1)/2 D.(n+1)/2（分数：1.00）A.B.C.D.8.循环链表的主要优点是_。 A.不再需要头指针了 B.已知某个结点的位置后，能够容易找到它的直接前趋 C.在进行插入、删除运算时，能更好地保证链表不断开 D.从表中的任意结点出发都能扫描到
4、整个链表（分数：1.00）A.B.C.D.9.对顺序存储的线性表，设其长度为 n，在任何位置上插入或删除操作都是等概率的。插入一个元素时平均要移动表中的_个元素。 A.n/2 B.(n+1)/2 C.(n-1)/2 D.n（分数：1.00）A.B.C.D.10.在一个具有 n 个结点的单链表中插入一个新结点，并可以不保持原有顺序的算法的时间复杂度是_。 A.O(1) B.O(n) C.O(n2) D.D(nlog2n)（分数：1.00）A.B.C.D.11.若某线性表中最常用的操作是在最后一个元素之后插入一个元素和删除第一个元素，则采用_存储方式最节省运算时间。 A.单链表 B.仅有头指针的单
5、循环链表 C.双链表 D.仅有尾指针的单循环链表（分数：1.00）A.B.C.D.12.非空的循环单链表 head 的链尾结点(由 p 所指向)满足_。 A.Pnext=NULL; B.P=NULL; C.Pnext=head; D.P=head;（分数：1.00）A.B.C.D.13.在长度为 n 的顺序表的表尾插入一个新元素的时间复杂度为_。 A.O(n) B.O(1) C.O(n2) D.O(log2n)（分数：1.00）A.B.C.D.14.单链表又称为线性链表，在单链表上实施插入和删除操作_。 A.不需移动结点，不需改变结点指针 B.不需移动结点，只需改变结点指针 C.只需移动结点，
6、不需改变结点指针 D.既需移动结点，又需改变结点指针（分数：1.00）A.B.C.D.15.不带表头结点的单链表 first 为空的判定条件是U /U，带表头结点的单链表 first 为空的判定条件是 firstnext=NULL;。 A.first=NULL; B.firstnext=NULL; C.firstnext=first; D.first!=NULL;（分数：1.00）A.B.C.D.16.已知单链表中结点 p 不是链尾结点，若在 p 之后插入结点 s，则应执行_操作。 A.Snext=p;pnext=S; B.pnext=S;Snext=p; C.snext=pnext;p=s;
7、 D.Snext=pnext;pnext=S;（分数：1.00）A.B.C.D.17.一个向量(一种顺序表)，第一个元素的存储地址是 100，每个元素的长度为 2，则第 5 个元素的地址是_。 A.110 B.108 C.100 D.120（分数：1.00）A.B.C.D.18.设 rear 是指向非空的带表头结点的单循环链表的链尾结点的指针。若想删除链表第一个结点，则应执行_操作。 A.s=rear;rear=rearnext;free(s); B.rear=rearnext;free(rear); C.rear=rearnextnext;free(rear); D.s=rearnextne
8、xt;rearnextnext=snext;free(s);（分数：1.00）A.B.C.D.19.设双向循环链表中结点的结构为(data，prior，next)，且不带表头结点。若想在结点 p 之后插入结点s，则应执行_操作。 A.pnext=s;sprior=p;pnextprior=s;snext=pneXt; B.pnext=s;pnextprior=s;sprior=p;snext=pnext; C.sprior=p;snext=pnext;pnext=s;pnextprior=s; D.sprior=p;snext=pnext;pnextprior=s;pnext=s;（分数：1.
9、00）A.B.C.D.20.给定有 n 个元素的一维数组，建立一个有序单链表的时间复杂度是_。 A.O(1) B.O(n) C.O(n2) D.O(nlog2n)（分数：1.00）A.B.C.D.21.在一个单链表中，已知 q 所指结点是 p 所指结点的前驱结点，若在 q 和 p 之间插入 s 结点，则执行_操作。 A.snext=pnext;pnext=s; B.pnext=snext;snext=p; C.qnext=s;snext=p; D.pnext=s;snext=q;（分数：1.00）A.B.C.D.二、B综合应用题/B(总题数：3，分数：71.00)分析以下各程序段的时间复杂度。
10、（分数：18.00）(1).void main() int i=1,k=0,n=10; while(i=n-1) k+=10*i; +i; （分数：2.00）_(2).void main() int i=1,k=0,n=100; do k+=10*i;+i; while(i=n); （分数：2.00）_(3).void main() int i=1,j=0,n=10; while(i+j=n) if(ij) +j; else +i; （分数：2.00）_(4).void main() int n=10,x=n,y=0; while(x=(y+1)*(y+1) +y; （分数：2.00）_(5)
11、.void main() int n=9,i=1; while(i=n) i=i*3; （分数：2.00）_(6).分析以下程序段的时间复杂度。 . i=1; while(i=n) i=i*2; .（分数：2.00）_(7).假设 n 为 2 的乘幂，如 n=2，4，8，16，试求下列程序的时间复杂度及变量 count 的值(以 n 的函数形式表示)。 void counter() int n,x,count; cout“n: “; cinn; count=0; x=2; while(xn/2) x=2*x; +count; coutcountendl; （分数：2.00）_(8).某算法所需
12、时间由下述方程表示，试求出该算法的时间复杂度(以大 O 形式表示)。注意，n 为求解问题的规模，为简单起见，设 n 是 2 的正整数幂。 （分数：2.00）_(9).分析 order 函数的时间复杂度。 order(int j,int n) int i,temp; if(jn) for(i=j;i=n; +i) if(aiaj) temp=ai; ai=aj; aj=temp; +j; order(j,n); /递归调用 （分数：2.00）_斐波那契数列 Fn定义如下：F 0=0，F 1=1，F n=Fn-1+Fn-2，n=2，3，就此斐波那契数列，回答下列问题。（分数：4.00）(1).在递
13、归计算 Fn时，需要对较小的 Fn-1，F n-2，F 1，F 0精确计算多少次?（分数：2.00）_(2).如果用大 O 表示法，递归计算 Fn时递归函数的时间复杂度是多少?（分数：2.00）_设计求解下列问题的算法，并分析其最坏情况的时间复杂度。（分数：49.06）(1).在数组 A1，n中查找值为 K 的元素，若找到则输出其位置 i；否则输出 0 作为标志。（分数：2.23）_(2).找出数组 A1，n中元素的最大值和次最大值。（分数：2.23）_(3).以下算法是在一个有 n 个数据元素的数组 A 中删除第 i 个位置的数组元素，要求当删除成功时数组元素个数减 1，求平均删除一个数组元
14、素需要移动的元素个数是多少?其中，数组下标从 0 至 n-1。 int delete(int A,int n,int i) int j; if(i0|in) return 0; for(j=i+1;jn;+j) Aj-1=Aj;-n; return 1; （分数：2.23）_(4).说明在线性表的链式存储结构中，头指针与头结点之间的根本区别以及头结点与开始结点的关系。（分数：2.23）_(5).请简要比较顺序表和链表各自的特点。（分数：2.23）_(6).编写一个算法实现两个有序(从小到大)顺序表合并成为一个顺序表，合并后的结果放在第一个顺序表中，不另设新的顺序表存储(假设这两个有序顺序表中没
15、有相同的元素)。（分数：2.23）_(7).设 A=(a1，a 2，a m)和 B=(b1，b 2，b n)均为顺序表。若 n=m 且 ai=bi(i=1，n)，则称 A=B；若 ai=bi(i=1，j)且 aj+1b j+1(jnm)，则称 AB；在其他情况下均称 AB。试编写一个比较 A 和B 的算法，当 AB、A=B 或 AB 时分别输出-1、0 或 1。（分数：2.23）_(8).编写一个算法，将 m(m2)个有序(从小到大)顺序表合并成一个有序顺序表，合并过程中不另设新的顺序表存储。（分数：2.23）_(9).设 A 和 B 是两个顺序表，其元素按从小到大的顺序排列。编写一个将 A
16、和 B 中相同元素组成一个新的从大到小的有序顺序表 C 的算法，并分析算法的时间复杂度。（分数：2.23）_(10).设 A 和 B 是两个顺序表，其元素按非递减的顺序排列。编写一个将 A 和 B 中所有元素组成一个新的从小到大的有序顺序表 C 的算法，要求删除重复的元素，并返回 C 表的长度。（分数：2.23）_(11).设有一个表头指针为 h 的单链表，试设计一个算法，通过遍历一趟链表，将链表中所有结点的链方向逆转，如图所示。（分数：2.23）_(12).以下是两个 n 阶方阵的乘积 C=AB，给出该算法的时间复杂度。 void matmult(int n,float AmaxSize,f
17、loat BmaxSize,float CmaxSizemaxSize) int i,j,k; float x; for(i=1;i=n;+i) / for(j=1;j=n;+j) / x=0; / for(k=1;k=n;+k) / x+=Aik*Bkj; / Cij=x; / （分数：2.23）_(13).假设有 n(n1)个线性表顺序地存放在顺序表 S1，m中，令 Fi和 Ri指示第 i 个(1in)表的第 1 个元素和最后 1 个元素在 S 中的位置，并设定 RiFi+1，Fn+1=m+1，如图所示。试写出实现下列要求的算法。（分数：2.23）_(14).设某机器表示的整数不超过 5
18、位十进制数字。试设计一种表示任意长的整数的数据结构，并利用设计的数据结构，写出计算任意给定的两个整数之和的算法。（分数：2.23）_(15).已知在一维数组 A0，m+n-1中依次存放着两个顺序表(a 1，a 2，a m)和(b 1，b 2，b n)。试编写程序，将数组中两个顺序表的位置互换，即将(b 1，b 2，b n)放在(a 1，a 2，a m)的前面。（分数：2.23）_(16).假定数组 A0，n-1中有多个零元素，试写出一个函数，将 A 中所有的非零元素依次移到数组A 的前端。（分数：2.23）_(17).已知 L 为不带表头结点的单链表的表头指针(L 非空)，链表中存储的都是整型
19、数据，试写出实现下列运算的递归算法。 (1)求链表中的最大整数。 (2)求链表的结点个数。 (3)求所有整数的平均值。（分数：2.23）_(18).从左到右及从右到左遍历一个单链表是可能的，其方法是在从左向右遍历的过程中将链接方向逆转，如图所示。图中的指针 p 指向当前正在访问的结点，指针 pr 指向指针 p 所指结点的左侧的结点。此时，指针 p 所指结点左侧的所有结点的链接方向都已逆转。（分数：2.23）_(19).根据一个结点数据类型为整型的单链表生成两个单链表，第一个单链表中包含原单链表中所有数据值为奇数的结点，第二个单链表中包含原单链表中所有数据值为偶数的结点，原有单链表保持不变。（分
20、数：2.23）_(20).已知一个带表头结点的单链表中含有 3 类字符(数字字符、字母字符和其他字符)。试编写一个函数，构造 3 个新的单链表，使每个单链表中只包含同一类字符。要求使用原表的空间，表头结点可以另辟空间。（分数：2.23）_(21).试设计一个实现下述要求的 Locate 运算的函数。设有一个带表头结点的双向链表 L，每个结点有 4个数据成员：指向前驱结点的指针 prior、指向后继结点的指针 next、存放数据的成员 data 和访问频度freq。所有结点的 freq 初始时都为 0。每当在链表上进行一次 Locate(x)操作时，令元素值为 x 的结点的访问频度 freq 加
21、 1，并将该结点前移，链接到与它的访问频度相等的结点后面，使得链表中所有结点保持按访问频度递减的顺序排列，以使频繁访问的结点总是靠近表头。（分数：2.23）_(22).若采用数组来存储一元多项式的系数，则用数组的第 i 个元素存放多项式的 i 次幂项的系数。如对于一元多项式 f(x)=6x6+7x4-10x2+5x+3，可用数组表示，如图所示。（分数：2.23）_计算机学科专业基础综合数据结构-算法复杂度相关问题专练、线性表答案解析(总分：92.06，做题时间：90 分钟)一、B单项选择题/B(总题数：21，分数：21.00)1.线性表是_。 A.一个有限序列，可以为空 B.一个有限序列，不能
22、为空 C.一个无限序列，可以为空 D.一个无限序列，不能为空（分数：1.00）A. B.C.D.解析：2.若想在单链表中删除某结点 p(p 既不是第一个，也不是最后一个结点)的直接后继，则应执行_操作。 A.pnext=pnextnext B.p=pnext;pnext=pnextnext C.pnext=pnext D.p=pnextnext（分数：1.00）A. B.C.D.解析：解析 因为 p 既不是第一个，也不是最后一个结点，所以 p 的直接后继存在。若想删除结点 p 的直接后继，只需要让 p 的后继的后继成为 p 的后继，即 pnext=pnextnext。3.已知 L 是带表头结点
23、的单链表，则删除首元结点的语句是_。 A.L=Lnext B.Lnext=Lnextnext C.L=Lnextnext D.Lnext=L（分数：1.00）A.B. C.D.解析：解析 链表中第一个元素存储在表头结点后面的一个结点中，实际删除的是表头结点后面的结点。4.用链表表示线性表的优点是_。 A.便于随机存取 B.花费的存储空间较顺序存储少 C.便于插入和删除 D.数据元素的物理顺序与逻辑顺序相同（分数：1.00）A.B.C. D.解析：5.在单链表中，增加一个头结点的目的是为了_。 A.使单链表至少有一个结点 B.标识表结点中首结点的位置 C.方便运算的实现 D.说明单链表是线性表的
24、链式存储（分数：1.00）A.B.C. D.解析：6.已知单链表 A 的长度为 m，单链表 B 的长度为 n，若将 B 链接在 A 的末尾，在没有链尾指针的情况下，算法的时间复杂度应为_。 A.O(1) B.O(m) C.O(n) D.O(m+n)（分数：1.00）A.B. C.D.解析：解析 需要搜索并找到 A 的链尾，遍历表 A 的 m 个结点。7.从一个具有 n 个结点的有序单链表中查找其值等于 x 的结点时，在查找成功的情况下，需要平均比较_个结点。 A.n B.n/2 C.(n-1)/2 D.(n+1)/2（分数：1.00）A.B.C.D. 解析：解析 对于有序单链表在查找成功的情况
25、下，其查找性能与一般单链表相同，因为链表存储结构不具备随机存取特点，必须遍历整个链表。8.循环链表的主要优点是_。 A.不再需要头指针了 B.已知某个结点的位置后，能够容易找到它的直接前趋 C.在进行插入、删除运算时，能更好地保证链表不断开 D.从表中的任意结点出发都能扫描到整个链表（分数：1.00）A.B.C.D. 解析：9.对顺序存储的线性表，设其长度为 n，在任何位置上插入或删除操作都是等概率的。插入一个元素时平均要移动表中的_个元素。 A.n/2 B.(n+1)/2 C.(n-1)/2 D.n（分数：1.00）A. B.C.D.解析：解析 本题可以根据插入元素的位置列出一个移动元素个数
26、序列，在末尾插入时，移动元素为0；在第 n 位插入时，移动元素为 n-1；在起始位置插入时，移动元素为 n。由于等概率插入，在每个位置上插入新元素的概率均为 1/(n+1)。因此，平均移动元素为(0+1+2+n)/(n+1)=n/2。10.在一个具有 n 个结点的单链表中插入一个新结点，并可以不保持原有顺序的算法的时间复杂度是_。 A.O(1) B.O(n) C.O(n2) D.D(nlog2n)（分数：1.00）A. B.C.D.解析：解析 此时插在链头即可。 说明 本题的要求是“可以不保持原有顺序”，仅仅是单链表中插入一个结点的时间复杂度。11.若某线性表中最常用的操作是在最后一个元素之后
27、插入一个元素和删除第一个元素，则采用_存储方式最节省运算时间。 A.单链表 B.仅有头指针的单循环链表 C.双链表 D.仅有尾指针的单循环链表（分数：1.00）A.B.C.D. 解析：12.非空的循环单链表 head 的链尾结点(由 p 所指向)满足_。 A.Pnext=NULL; B.P=NULL; C.Pnext=head; D.P=head;（分数：1.00）A.B.C. D.解析：解析 非空单循环链表的尾结点为 p，则其后继结点为链表的头结点 head，即 pnext=head。13.在长度为 n 的顺序表的表尾插入一个新元素的时间复杂度为_。 A.O(n) B.O(1) C.O(n2
28、) D.O(log2n)（分数：1.00）A.B. C.D.解析：解析 在顺序表的表尾插入元素不需要元素的移动，因此在有 n 个元素的顺序表的表尾插入一个新元素，可直接在表的第 n+1 个位置插入，时间复杂度为 O(1)。14.单链表又称为线性链表，在单链表上实施插入和删除操作_。 A.不需移动结点，不需改变结点指针 B.不需移动结点，只需改变结点指针 C.只需移动结点，不需改变结点指针 D.既需移动结点，又需改变结点指针（分数：1.00）A.B. C.D.解析：解析 单链表的插入和删除操作无需改变结点的存储位置，只需要修改相关指针即可；顺序表则不然，一般情况下都需要移动元素，在特殊位置表尾进
29、行这些操作的时候则不需要移动元素。15.不带表头结点的单链表 first 为空的判定条件是U /U，带表头结点的单链表 first 为空的判定条件是 firstnext=NULL;。 A.first=NULL; B.firstnext=NULL; C.firstnext=first; D.first!=NULL;（分数：1.00）A. B.C.D.解析：解析 对于不带头结点的单链表，first 指向开始结点(第一个结点)，链表为空则 first 为空。对于带有头结点的单链表，first 指向表头结点，链表为空则表头结点后面没有结点，即指针firstnext 为空。16.已知单链表中结点 p 不
30、是链尾结点，若在 p 之后插入结点 s，则应执行_操作。 A.Snext=p;pnext=S; B.pnext=S;Snext=p; C.snext=pnext;p=s; D.Snext=pnext;pnext=S;（分数：1.00）A.B.C.D. 解析：解析 插入结点的时候注意不要断链，注意指针操作的顺序：snext=pnext;pnext=s。17.一个向量(一种顺序表)，第一个元素的存储地址是 100，每个元素的长度为 2，则第 5 个元素的地址是_。 A.110 B.108 C.100 D.120（分数：1.00）A.B. C.D.解析：解析 第 5 个元素的地址=100+2(5-1
31、)=108。18.设 rear 是指向非空的带表头结点的单循环链表的链尾结点的指针。若想删除链表第一个结点，则应执行_操作。 A.s=rear;rear=rearnext;free(s); B.rear=rearnext;free(rear); C.rear=rearnextnext;free(rear); D.s=rearnextnext;rearnextnext=snext;free(s);（分数：1.00）A.B.C.D. 解析：解析 假设指向链表尾部的指针为 rear。要删除第一个结点，必须先将表头结点的后继结点地址s=rearnextnext 保存，然后才能进行新的链接操作，让 s
32、的后继链接到表头结点之后rearnextnext=snext，最后进行删除仔 ee(s)。19.设双向循环链表中结点的结构为(data，prior，next)，且不带表头结点。若想在结点 p 之后插入结点s，则应执行_操作。 A.pnext=s;sprior=p;pnextprior=s;snext=pneXt; B.pnext=s;pnextprior=s;sprior=p;snext=pnext; C.sprior=p;snext=pnext;pnext=s;pnextprior=s; D.sprior=p;snext=pnext;pnextprior=s;pnext=s;（分数：1.00
33、）A.B.C.D. 解析：解析 在双向链表结点 p 之后插入新结点 s，等效于在两个链表上执行插入操作，同单链表的插入操作，插入过程中注意不要断链。可以明显看出，选项 A 和选项 B 中第一条语句 pnext=s 就让后继链断掉了。选项 C 和选项 D 的前两条语句 sprior=p;snext=pnext;合理，让 s 的前驱、后继都链接好且未影响原来的两个链，但选项 C 的第三条语句 pnext=s;又断开了后继链，因此本题选 D。20.给定有 n 个元素的一维数组，建立一个有序单链表的时间复杂度是_。 A.O(1) B.O(n) C.O(n2) D.O(nlog2n)（分数：1.00）A
34、.B.C. D.解析：解析 每当插入一个元素时，就必须对整个链表进行遍历找到插入位置。如果需要插入的元素有n 个，则每一次遍历操作的时间复杂度为 O(n)。因此建立有序单链表的时间复杂度为 O(n2)，即链表插入排序。21.在一个单链表中，已知 q 所指结点是 p 所指结点的前驱结点，若在 q 和 p 之间插入 s 结点，则执行_操作。 A.snext=pnext;pnext=s; B.pnext=snext;snext=p; C.qnext=s;snext=p; D.pnext=s;snext=q;（分数：1.00）A.B.C. D.解析：二、B综合应用题/B(总题数：3，分数：71.00)
35、分析以下各程序段的时间复杂度。（分数：18.00）(1).void main() int i=1,k=0,n=10; while(i=n-1) k+=10*i; +i; （分数：2.00）_正确答案：(O(n)解析：(2).void main() int i=1,k=0,n=100; do k+=10*i;+i; while(i=n); （分数：2.00）_正确答案：(O(1)解析：(3).void main() int i=1,j=0,n=10; while(i+j=n) if(ij) +j; else +i; （分数：2.00）_正确答案：(O(n)解析：(4).void main() int n=10,x=n,y=0; while(x=(y+1)*(y+1) +y; （分数：2.00）_正确答案：(*)解析：(5).void main() int n=9,i=1; while(i=n) i=i*3; （分数：2.00）_
