问答题

设计求解下列问题的算法，并分析其最坏情况的时间复杂度。设某机器表示的整数不超过5位十进制数字。试设计一种表示任意长的整数的数据结构，并利用设计的数据结构，写出计算任意给定的两个整数之和的算法。

答案：将用户输入的正整数按各位数字存放在一个顺序表中，这样就变成了两个顺序表中的数字相加。实现本题功能的程序代码如下： int...

你可能感兴趣的试题

分析以下各程序段的时间复杂度。void main() { int i=1,k=0,n=10; while(i＜=n-1) { k+=10*i; ++i; } }

答案： O(n)

分析以下各程序段的时间复杂度。void main() { int i=1,k=0,n=100; do { k+=10*i;++i; } while(i==n); }

答案： O(1)

斐波那契数列F_n定义如下：F₀=0，F₁=1，F_n=F_n-1+F_n-2，n=2，3，…就此斐波那契数列，回答下列问题。在递归计算F_n时，需要对较小的F_n-1，F_n-2，…，F₁，F₀精确计算多少次

答案：从题中可知：F₀=0，F₁=1，F₂=1，F_...

设计求解下列问题的算法，并分析其最坏情况的时间复杂度。在数组A[1，…，n]中查找值为K的元素，若找到则输出其位置i；否则输出0作为标志。

答案：算法如下： int locate(datatype A[],datatype k) //datatype为C语言标准数据...

斐波那契数列F_n定义如下：F₀=0，F₁=1，F_n=F_n-1+F_n-2，n=2，3，…就此斐波那契数列，回答下列问题。如果用大O表示法，递归计算F_n时递归函数的时间复杂度是多少

答案：设计算F_n的时间复杂度为T(n)，有
T(n)=T(n-1)+T(n-2)＜2T(n-1)...

分析以下各程序段的时间复杂度。void main() { int i=1,j=0,n=10; while(i+j＜=n) if(i＞j) ++j; else ++i; }

答案： O(n)

设计求解下列问题的算法，并分析其最坏情况的时间复杂度。找出数组A[1，…，n]中元素的最大值和次最大值。

答案：算法如下： void max(datatype A[],datatype m,datatype sm) //dataty...

设计求解下列问题的算法，并分析其最坏情况的时间复杂度。
以下算法是在一个有n个数据元素的数组A中删除第i个位置的数组元素，要求当删除成功时数组元素个数减1，求平均删除一个数组元素需要移动的元素个数是多少其中，数组下标从0至n-1。 int delete(int A[],int n,int i) { int j; if(i＜0||i＞n) return 0; for(j=i+1;j＜n;++j) A[j-1]=A[j]; --n; return 1; }

答案：这个算法的时间复杂度随删除数据的位置不同而不同。当删除最后一个位置的数组元素时有i=n-1,j=i+1=n，此时因不需移...

设计求解下列问题的算法，并分析其最坏情况的时间复杂度。说明在线性表的链式存储结构中，头指针与头结点之间的根本区别以及头结点与开始结点的关系。

答案：用链表存储结构来表示线性表时，链表的头指针一般指向其第一个结点，它有标识链表的作用。头结点的作用在于统一相关操作，如对链...

分析以下各程序段的时间复杂度。void main() { int n=9,i=1; while(i＜=n) i=i*3; }

答案： O(log₃n)

设计求解下列问题的算法，并分析其最坏情况的时间复杂度。请简要比较顺序表和链表各自的特点。

答案： (1)基于空间的比较。 1)存储分配的方式：顺序表的存储空间是静态分配的。链表的存储空间是动态分配的。 2)存储密度...

分析以下各程序段的时间复杂度。分析以下程序段的时间复杂度。 ... i=1; while(i＜=n) i=i*2; ...

答案：此处循环体里面是i=i*2，即每循环一次，i值增加一倍，所以执行次数与n之间是以2为底的对数关系，故时间复杂度为O(lo...

设计求解下列问题的算法，并分析其最坏情况的时间复杂度。编写一个算法实现两个有序(从小到大)顺序表合并成为一个顺序表，合并后的结果放在第一个顺序表中，不另设新的顺序表存储(假设这两个有序顺序表中没有相同的元素)。

答案：可以按照如下策略实现顺序表A和B的合并过程：从A和B的最后一个元素逐个向前进行比较，将较大的元素先定位在A中。代码如下...

分析以下各程序段的时间复杂度。假设n为2的乘幂，如n=2，4，8，16，…试求下列程序的时间复杂度及变量count的值(以n的函数形式表示)。 void counter() { int n,x,count; cout＜＜"n: "; cin＞＞n; count=0; x=2; while(x＜n/2) { x=2*x; ++count; } cout＜＜count＜＜endl; }

答案： n与count的关系如下：
当n=2⁰时，count=0；当n=2¹...

设计求解下列问题的算法，并分析其最坏情况的时间复杂度。设A=(a₁，a₂，…，a_m)和B=(b₁，b₂，…，b_n)均为顺序表。若n=m且a_i=b_i(i=1，…，n)，则称A=B；若a_i=b_i(i=1，…，j)且a_j+1＜b_j+1(j＜n≤m)，则称A＜B；在其他情况下均称A＞B。试编写一个比较A和B的算法，当A＜B、A=B或A＞B时分别输出-1、0或1。

答案：本题算法思想：先找出A和B中前面对应位置相同的结点，用指针i和j分别指示A和B中不同元素的下标，根据指针i和j提供的信息...

分析以下各程序段的时间复杂度。某算法所需时间由下述方程表示，试求出该算法的时间复杂度(以大O形式表示)。注意，n为求解问题的规模，为简单起见，设n是2的正整数幂。

答案：设n=2^m，则
T(n)=T(2^m)=2T(2^m-1

设计求解下列问题的算法，并分析其最坏情况的时间复杂度。编写一个算法，将m(m≥2)个有序(从小到大)顺序表合并成一个有序顺序表，合并过程中不另设新的顺序表存储。

答案：将线性表A和B合并的过程如下：从A的最后一个元素和B的第一个元素开始分别向前、向后进行比较，将较大的元素先定位在A中。 ...

分析以下各程序段的时间复杂度。分析order函数的时间复杂度。 order(int j,int n) { int i,temp; if(j＜n) { for(i=j;i＜=n; ++i) if(a[i]＜a[j]) { temp=a[i]; a[i]=a[j]; a[j]=temp; } ++j; order(j,n); //递归调用 } }

答案： order()函数是一个递归排序过程，设T(n)是排序n个元素所需要的时间。在排序n个元素时，算法的计算时间主要花费在递...

设计求解下列问题的算法，并分析其最坏情况的时间复杂度。设A和B是两个顺序表，其元素按从小到大的顺序排列。编写一个将A和B中相同元素组成一个新的从大到小的有序顺序表C的算法，并分析算法的时间复杂度。

答案：本算法是从A和B的最后两个元素开始比较，若相等，将其值放入C的第一个元素中，如此直到A和B中的所有元素比较完毕。实现本题...

设计求解下列问题的算法，并分析其最坏情况的时间复杂度。设A和B是两个顺序表，其元素按非递减的顺序排列。编写一个将A和B中所有元素组成一个新的从小到大的有序顺序表C的算法，要求删除重复的元素，并返回C表的长度。

答案：此题简单，程序代码如下： int unions(int A[],int na,int B[],int nb,int C[...

设计求解下列问题的算法，并分析其最坏情况的时间复杂度。设有一个表头指针为h的单链表，试设计一个算法，通过遍历一趟链表，将链表中所有结点的链方向逆转，如图所示。

答案： void Reverse(LNode *&h) { //设单链表没有表头结点，h直接指示链表首元结点。链表全部逆转后，h...

设计求解下列问题的算法，并分析其最坏情况的时间复杂度。以下是两个n阶方阵的乘积C=A×B，给出该算法的时间复杂度。 void matmult(int n,float A[][maxSize],float B[][maxSize],float C[maxSize][maxSize]) { 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+=A[i][k]*B[k][j]; //⑤ C[i][j]=x; //⑥ } }

答案：在算法中，语句①的循环控制变量i要增加到n+1，测试i＞n成立才会终止，所以它的频度是n+1，但是它的循环体却只能执行n...

设计求解下列问题的算法，并分析其最坏情况的时间复杂度。假设有n(n＞1)个线性表顺序地存放在顺序表S[1，…，m]中，令F[i]和R[i]指示第i个(1≤i≤n)表的第1个元素和最后1个元素在S中的位置，并设定R[i]＜F[i+1]，F[n+1]=m+1，如图所示。试写出实现下列要求的算法。

(1)在第i个表中的第j项后面插入1个元素，仅当整个顺序表空间填满时，不允许进行插入操作。 (2)删除第i个表中的第j个元素，要求在删除第j个元素后，该表仍为顺序存储的线性表。

答案：本题实质上是将n个线性表(长度可能不相同)放于一个连续空间(长度为m)，来解决这些线性表的插入和删除问题。 (1)的算法...

设计求解下列问题的算法，并分析其最坏情况的时间复杂度。设某机器表示的整数不超过5位十进制数字。试设计一种表示任意长的整数的数据结构，并利用设计的数据结构，写出计算任意给定的两个整数之和的算法。

答案：将用户输入的正整数按各位数字存放在一个顺序表中，这样就变成了两个顺序表中的数字相加。实现本题功能的程序代码如下： int...

设计求解下列问题的算法，并分析其最坏情况的时间复杂度。已知在一维数组A[0，…，m+n-1]中依次存放着两个顺序表(a₁，a₂，…，a_m)和(b₁，b₂，…，b_n)。试编写程序，将数组中两个顺序表的位置互换，即将(b₁，b₂，…，b_n)放在(a₁，a₂，…，a_m)的前面。

答案：分析：只需将顺序表整体逆转，然后再对子表分别逆转，即可满足题目要求。
由此可以写出如下程序代码：
voi...

设计求解下列问题的算法，并分析其最坏情况的时间复杂度。假定数组A[0，…，n-1]中有多个零元素，试写出一个函数，将A中所有的非零元素依次移到数组A的前端。

答案：因为数组是一种直接存取的数据结构，在一维数组中元素不是像顺序表那样集中存放于表的前端，而是根据元素下标直接存放于数组某个...

设计求解下列问题的算法，并分析其最坏情况的时间复杂度。已知L为不带表头结点的单链表的表头指针(L非空)，链表中存储的都是整型数据，试写出实现下列运算的递归算法。 (1)求链表中的最大整数。 (2)求链表的结点个数。 (3)求所有整数的平均值。

答案： (1)求链表中的最大整数的程序代码如下： int Max(LNode *L) //递归算法：求链表中的最大值 { ...

设计求解下列问题的算法，并分析其最坏情况的时间复杂度。从左到右及从右到左遍历一个单链表是可能的，其方法是在从左向右遍历的过程中将链接方向逆转，如图所示。图中的指针p指向当前正在访问的结点，指针pr指向指针p所指结点的左侧的结点。此时，指针p所指结点左侧的所有结点的链接方向都已逆转。

(1)编写一个算法，从任意给定的位置(pr，p)开始，将指针p右移k个结点。如果p移出链表，则将p置为NULL，并让pr停留在链表最右边的结点上。 (2)编写一个算法，从任意给定的位置(pr，p)开始，将指针pr左移k个结点。如果pr移出链表，则将pr置为NULL，并让p停留在链表最左边的结点上。

答案： (1)假设输入的p和pr都是指向待处理链表的合法位置的指针，指针p右移k个结点并逆转pr之前(包括pr)的所有结点的链接...

设计求解下列问题的算法，并分析其最坏情况的时间复杂度。根据一个结点数据类型为整型的单链表生成两个单链表，第一个单链表中包含原单链表中所有数据值为奇数的结点，第二个单链表中包含原单链表中所有数据值为偶数的结点，原有单链表保持不变。

答案： void Separate(LNode *&HL,LNode *&L1,LNode *&L2) { //将一个单链表HL...

设计求解下列问题的算法，并分析其最坏情况的时间复杂度。已知一个带表头结点的单链表中含有3类字符(数字字符、字母字符和其他字符)。试编写一个函数，构造3个新的单链表，使每个单链表中只包含同一类字符。要求使用原表的空间，表头结点可以另辟空间。

答案： void Separate1(LNode *&LA,LNode *&LB,LNode *&LC) { //原来的单链表是...

设计求解下列问题的算法，并分析其最坏情况的时间复杂度。试设计一个实现下述要求的Locate运算的函数。设有一个带表头结点的双向链表L，每个结点有4个数据成员：指向前驱结点的指针prior、指向后继结点的指针next、存放数据的成员data和访问频度freq。所有结点的freq初始时都为0。每当在链表上进行一次Locate(x)操作时，令元素值为x的结点的访问频度freq加1，并将该结点前移，链接到与它的访问频度相等的结点后面，使得链表中所有结点保持按访问频度递减的顺序排列，以使频繁访问的结点总是靠近表头。

答案：算法用到4个双向循环链表的主要操作：①正向搜索寻找满足要求的结点；②把该结点从链中摘下；③反向根据访问计数寻找插入位置；...

设计求解下列问题的算法，并分析其最坏情况的时间复杂度。若采用数组来存储一元多项式的系数，则用数组的第i个元素存放多项式的i次幂项的系数。如对于一元多项式f(x)=6x⁶+7x⁴-10x²+5x+3，可用数组表示，如图所示。

(1)试编写一个算法，求两个一元多项式的和。 (2)试编写一个算法，求两个一元多项式的乘积。

答案：如果用如题意所述的数组来存放多项式，则多项式的结构定义的程序代码如下：
typedef struct node<...