数据结构习题与解析(C语言篇) 答:①A 14找和队列的共同点是① A.都是先进后出 B.都是先进先出 C.只允许在端点处插入和删除元素 D.没有共同点 答:OC 15.表达式a#(b+c)-d的中缀表达式是①。 A. abcdd-+ B.abc+兼d C.abc箫+d一 D.一十黄abcd 答 2.2.2填空题(将正确的答案填在相应的空中) 1.向量搜和队列都是①结构,可以在向量的②位置插入和删除元素;对于找只能在 ③插入和删除元素;对于队列只能在④插入元素和⑤删除元素。 答:①线性②任何③栈顶④队尾⑤队首 2向一个长度为n的向量的第i个元素(1≤≤n+1)之前插入一个元素时,需向后移动 ①个元素。 答:①n-i+1 3向一个长度为n的向量中删除第i个元素(1≤≤n)时,需向前移动①个元素。 答:①n-i 4.向栈中压入元素的操作是① 答:①先移动栈顶指针,后存入元素 5,对栈进行退找时的操作是①。 答:①先取出元素,后移动栈顶指针 6.在一个循环队列中,队首指针指向队首元素的① 答:①前一个位置 7.从循环队列中删除一个元素时,其操作是① 答:①先移动队首元素,后取出元素 8在具有n个单元的循环队列中队满时共有①个元素 答:0n-1 9.一个栈的输入序列是12345,则栈的输出序列43512是① 答:①不可能的 10.一个找的输入序列是12345则栈的输出序列12345是① 答:①可能的
第2章顺序表 23 2.3习题解析 2.3.1向量 已知一个向址A,其中的元素按值非递减有序排列编写一个函数插入一个元素x后 保持该向量仍按递减有序排列 解:本题的算法思想是:先找到适当的位置,然后后移元素空出一个位置,再将x插入 实现本题功能的函数如下 void insert( vector A int n x) 向量A的长度为n* int i j+ i(x>=A[n)A[n-1=x:*若x大于最后的元索·则将其插入到最后* else while(x>=ALi)i-++i 查找插入位置i* for (j=n;>-i;--)A[i+1i=A]/*移出插入x的位置“ ALi=x 将X插入,向量长度增1* 2.已知一个向量中的元素按元素值非递减有序排列,编写一个函数删除向量中多余的 值相同的元素。 解:本题的算法思想是:由于向量中的元素按元素值非递减有序排列,值相同的元素必 为相邻的元素,因此依次比较相邻两个元素,若值相等,则删除其中一个,否则继续向后查 找实现本题功能的函数如下 void del( vector A. int n) 向量A的长度为n*/ int i=1.: while (i<=n-I f(A[!=A[1-1-)i+; *元素值不相等继续向下找*/ else for(j=(i-2)j<=n-)A[i-1]=A[i;/删除第|+1个元素“/ 向量长度减1“ 3.编写一个函数籽个向tA(有n个元素,且任何元素均不为0)分拆成两个向量,使 中大于0的元素存放在B中小于0的元素存放在C中
数据结构习题与解析C语言篇) 解:本题的算法思想是:依次遍历A的元素,比较当前的元素值,大于0者赋给B(假设 有p个元素),小于0者赋给C(假设有q个元素)。实现本题功能的函数如下 old ret (vector A, int n, vector B, int p, vector C, int q) int for(|=1<=n;++) A[>0) { p+十 BP]=ALi; i(A]<0) q+十 CLq]=Ali] 4.已知在一维数组A[1,m+n]中依次存放着两个向量(a1,a2…,,an)和(b;b2… bn),编写一个函数将两个向量的位置互换,即把(b,b,,bn)放到(a1,a2…,am)的前面。 解:本题的算法思想是:由于向量的插入与删除操作需要移动大量的元素,所用时间多, 这里采用先将 A;(a1,a2,,an,b1;b2;,,bn) 的所有元素逆置,即使之变成 A:(b,,,,b2;b1;am 然后将(ba,,b2,b1)逆置为(b1,bz…b),将(an,,,a2,a1)逆置为(a1,a2,,am),这样 便得到最终结果: A:(b1, b 2s,., bn ⊥2 先编写一个逆置的函数如下,其功能是逆置A中AD]到A[h]的部分: vold invert (A, I, h) vector A: int I,h for(=l<=(+h)/2i++)
第2章顺序表 X=A:A=A1→h-:A[-h-1=x:1￥将A[与A[-h一元素互换 邪么,实现本题功能的函数如下: yoid exchang (A.m-n) tor A int mn: invert(A.1. n) *5.编写一个函数从一给定的向址A中删除元素值在x到y(x≤y)之间的所有元素 要求以较高的效率来实现。 解:本题的算法思想是:先将A向量中所有元素值在x到y之间的元素置成一个特殊 的憤(如ω),并不立即刪除它们,然后从最后向前依次扫描.对于该特殊值的元素便移动其 闻的元素将其删除这种算法比每删除一个元素后立即移动其后元素效率要高一些实现 本题功能的过程如下 void de vector A intn.xy↓ if (A[i>=x&&Ali =y)ALi:=t' if(A[i]==0 for(k=ik<=(n-1);k++)A[k2=A[k+1 6.编写个函数用不多3n2的平均比较次数,在一个向址A中找出最大和最小 值的元素。 解:本题的算法思想是:如果在查找出最大和最小值的元素时各扫描一遍所有元素.则 宝少要比较2n次,为此,使用一趟扫描找出最大和最小值的元素。实现本题功能的函数如 void maxmin(A, n)
26 数据结构习题与解析C语言篇) for (i=2ii<=n: i++) if(al>max)max=Ali]e else if(A[i]<min) printf("max= %d min= %d",max, min); 在这个函数中,最坏情况是向量A的元素以递减顺序排列,这时(A[]>max)条件均不 成立,这时比较的次数为n-1,另外每次都要比较A[i]<min,同样所花比较次数为n-1, 因此,总的比较次数为: 2(n-1) 最好的情况是向量A的元素递增次序排列,这时(A[〕>max)条件均成立,不会再执行 else的比较,所以总的比较次数为 平均比较次数为: (2(n-1)+n-1)/2=3n/2-3/2 所以该函数的平均比较次数不多于3n/2。 7.设A=(a1,a2,an)和B=(b1,b2,,b)均为向量,A和B'分别为A和B中除 去最大共同前缀后的子表(例如,A=(x,y,y,z,x,z),B=(x,y,y,z,y,x,x,z),则两者的最 大共同前缀为x,y,y,z,在两向量中除去最大共同前级后的子表分别为a=(x,z),B'=(y, xx,z))。若A'=B'=空表,则A=B;若A′=空表,B≠空表,或两者均不空且A首元小 于B'首元,则A<B;否则A>B。编写一个函数根据上述方法比较A和B的大小 解:本题已经给出了详细的算法,这里不再讨论。实现本题功能的函数如下: vold compare(A, B, m, n) vector a, B vector AS BS i int i=l j,ms=0, ns=0; whe(A[]==B[)i++;/*是最大共同前缀之后的第一个元素的下标“/ AS[-|+1]=A[i]ms++;/*As为A的子表“ for (j=isi<=n i+t)