第一章绪习题一
1.有下列几种用二元组表示的数据结构，试画出它们分别对应的图形表示（当出现多个关系时，
对每个关系画出相应的结构图），并指出它们分别属于何种结构。
⑴ A=(K,R)其中
K={a1,a2,a3...,an}
R={}
⑵ B=(K,R)其中
K={a,b,c,d,e,f,g,h}
R={r}
r={
⑶ C=(K,R)其中
K={a,b,c,d,f,g,h}
R={r}
r={
⑷ D=(K,R)其中
K={1,2,3,4,5,6}
R={r}
r={(1,2),(2,3),(2,4),(3,4),(3,5),(3,6),(4,5),(4,6)}
⑸ E=(K,R)其中
K={48,25,64,57,82,36,75,43}
R={r1,r2,r3}
r1={<48,25>,<25,64>,<64,57>,<57,82>,<82,36>,<36,75>,<75,43>}
r2={<48,25>,<48,64>,<64,57>,<64,82>,<25,36>,<82,75>,<36,43>}
r3={<25,36>,<36,43>,<43,48>,<48,57>,<57,64>,<64,75>,<75,82>}
解：⑴是集合结构；⑵是线性结构；⑶⑷是树型结构；⑸散列结构。只作为参考。
2.设计二次多项式ax2+bx+c的一种抽象数据类型，假定起名为QIAdratic,
该类型的数据部分分为三个系数项a、b和c，操作部分为：(请写出下面每一个操作的具体实现)。
⑴初始化数据成员ab和c(假定用记录类型Quadratie定义成员)，每个数据成员的默认值为0。
Quadratic InitQuadratic(float aa=0,float bb=0,float cc=0);
解：
Quadratic InitQuadratic(float aa,float bb,float cc)
{
Quadratic q;
q.a=aa;
q.b=bb;
q.c=cc;
return q;
}
⑵做两个多项式加法,即使对应的系数相加,并返回相加的结果。
Quadratic Add(Quadratic q1,Quadratic q2);
解：
Quadratic Add(Quadratic q1,Quadratic q2);
{
Quadratic q;
q.a=q1.a+q2.a;
q.b=q1.b+q2.b;
q.c=q1.c+q2.c;
return q;
}
⑶根据给定x的值计算多项式的值。
float Eval(Quadratic q,float x);
解：
float Eval(Quadratic q,float x)
{
return(q.a*x*x+q.b*x+q.c);
}
⑷计算方程ax2+bx+c=0的两个实数根，对于有实根、无实根和不是实根方程(即a==0)这三种情况要返回不同的整数值，以便于工作调用函数做不同的处理。int Root(Quadratic q,float& r1,float& r2);
解：
int Root(Quadratic q,float& r1,float& r2)
{
if(q.a==0)return -1;
float x=q.b*q.b-4*q.a*q.c;
if(x>=0){
r1=(float)(-q.b+sqrt(x))/(2*q.a);
r2=(float)(-q.b-sqrt(x))/(2*q.a);
return 1;
}
else
return 0;
}
⑸按照ax**2+bx+c的格式(x2用x**2表示)输出二次多项式，在输出时要注意去掉系数为0的项，并且当b和c的值为负时，其前不能出现加号。
void Print(Quadratic q)
解：
void Print(Quadratic q)
{
if(q.a) cout< if(q.b) if(q.b>0) cout<<"+"< else cout< if(q.c) if(q.c>0) cout<<"+"< else cout< cout< } 3.用c++函数描述下列每一个算法，并分别求出它们的时间复杂度。 ⑴比较同一简单类型的两个数据x1和x2的大小，对于x1>x2,x1=x2和x1 情况分别返回'>''='和'<'字符。假定简单类型用SimpleType表示，它可通过typedef 语句定义为任一简单类型。 解： char compare(SimpleType x1,SimpleType x2) { if(x1>x2) return'>'; else if(x1==x2) return '='; else return'<'; } 其时间复杂度为O(1) ⑵将一个字符串中的所有字符按相反方的次序重新放置。 解： void Reverse(char*p) { int n=strlen(p); for(int i=0;i char ch; ch=p[i] p[i]=p[n-i-1]; p[n-i-1]=ch; } } 其时间复杂度为O(n) ⑶求一维double型数组a[n]中的所有元素之乘积。 解： double product(double a[],int n) { double p=1; for(int i=0;i p*=a[i]; return p; 其时间复杂度为O(n) ⑷计算Σni=0xi/i+1的值。 解： double Accumulate(double x,int n) { double p=1,s=1; for(int i=1;i<=n;i++){ p*=x; s+=p/(i+1); } return s; } 其时间复杂度为O(n) ⑸假定一维数组a[n]中的每个元素值均在[0，200]区间内，分别统计出落在[0， 20) ,[20,50),[50,80),[80,130),[130,200]等各区间的元素个数。 解： int Count(int a[],int n,int c[5])//用数组c[5]保存统计结果 { int d[5]={20,50,80,130,201};//用来保存各统计区间的上限 int i,j; for(i=0;i<5;i++)c[i]=0;//给数组c[5]中的每个元素赋初值0 for(i=0;i { if(a[i]<0||a[i]>200) return 0;//返回数值0表示数组中数据有错，统计失败 for(j=0;j<5;j++)//查找a[i]所在区间 if(a[i] c[j]++;//使统计相应区间的元素增1 } return 1;//返回数值1表示统计成功 } 其时间复杂度为O(n) ⑹从二维整型数组a[m][n]中查找出最大元素所在的行、列下标。 解： void find(int a[M][N],int m,int n,int&Lin,int&Col) //M和N为全局常量，应满足M>=n和N>=n的条件，Lin和Col为引用 //形参，它是对应实参的别名，其值由实参带回 { Lin=0;Col=0; for(int i=0;i for(int j=0;j if(a[i][j]>a[Lin][Col]){Lin=i;Col=j;} 其时间复杂度为O(m*n) 4.指出下列各算法的功能并求出其时间复杂度。 ⑴ int prime(int n) { int i=2; int x=(int)sqrt(n); while(i<=x){ if(n%i==0)break; i++; } if(i>x) return 1; else return 0; } 解： 判断n是否是一个素数，若是则返回数值1，否则返回0。该算法的时间复杂度为 O(n1/2)。 ⑵ int sum1(int n) { int p=1,s=0; for(int i=1;i<=n;i++){ p*=i; s+=p; } return s; } 解： 计算Σi!(上标为n，下标为i=1)的值，其时间的复杂度为O(n)。 ⑶ int sum2(int n) { int s=0; for(int i=1;i<=n;i++){ int p=1; for(int j=1;j<=i;j++) p*=j; s+=p; } return s; } 解： 计算Σi!的值，时间复杂度为O(n2) ⑷ int fun(int n) { int i=1,s=1; while(s s+=++i; return i; } 解： 求出满足不等式1+2+3...+i≥n的最小i值，其时间复杂度为O(n1/2)。 ⑸ void UseFile(ifstream& inp,int c[10]) //假定inp所对应的文件中保存有n个整数 { for(int i=0;i<10;i++) c[i]=0; int x; while(inp>>x){ i=x%10; c[i]++; } } 解： 利用数组c[10]中的每个元素c[i]对应统计出inp所联系的整数文件中个位值同为i的整数个 数，时间复杂度为O(n) ⑹ void mtable(int n) { for(int i=1;i<=n;i++){ for(int j=i;j<=n;j++) cout< < cout< } } 解： 打印出一个具有n行的乘法表，第i行(1≤i≤n)中有n-i+1个乘法项，每个乘法项为i与j( i≤j≤n)的乘积，时间复杂度为O(n2)。 ⑺ void cmatrix(int a[M][N],int d) //M和N为全局整型常量 { for(int i=0;i for(int j=0;j a[i][j]*=d; } 解： 使数组a[M][N]中的每一个元素均详细以d的值，时间复杂度为O(M*N) ⑻ void matrimult(int a[M][N],int b[N][L],int c[M][L]) // { int i,j,k; for(i=0;i for(j=0;j c[i][j]=0; for(i=0;i for(j=0;j for(k=0;k c[i][j]+=a[i][k]*b[k][j]; } 解： 矩阵相乘，即a[M][N]×b[N][L]→c[M][L]，时间复杂度为O(M×N×L)。 5.题目略 ⑴解： void InitSet(Set& s) { for(int i=1;i<=SETSIZE;i++) s.m[i]=0; } ⑵解：void InitSet(Set& s,int a[],int n) { fot(int i=0;i s.m[a[i]]=1; } ⑶解： Set operator + (Set s1,Set s2) { Set s; InitSet(s); for(int i=1;i<=SETSIZE;i++) if((s1.m[i]==1)||s2.m[i]===1)) s.m[i]=1; return s; } ⑷解： Set operator*(Set s1,Set s2) { Set s; InitSet(s); for(int i=1;i<=SETSIZE;i++) if((s1.m[i]==1)&&(s2.m[i]==1)) s.m[i]=1; return s; ⑸解： Boolean operator＾(int elt,Set s) { if(s.m[elt]==1) return True; else return False; } ⑹解： void Inisert(Set& s,int n) { s.m[n]=1; } ⑺解： void Delete(Set& s,int n) { s.m[n]=0; } ⑻解： ostream& operator<<(ostream& ostr,Set& s) { ostr<<'{' for(int i=1;i<=SETSIZE;i++) if(s.m[i]==1) ostr< ostr<<'}'< return ostr; } 第二章线性表习题二 1. ⑴解：(79,62,34,57,26,48) ⑵解：(26,34,48,57,62,79) ⑶解：(48,56,57,62,79,34) ⑷解：(56,57,79,34) ⑸解：(26,34,39,48,57,62) 2. 解： 为了排版方便，假定采用以下输出格式表示单链接表的示意图；每个括号内的数据表示一个元 素结点，其中第一个数据为元素值，第二个数据为后继结点的指针，第一个元素结点前的数值为 表头指针。 ⒈(7(79,6),(62,5),(34,4),(57,3),(26,2),(48,0)) ⒉(3(26,5),(34,2),(48,4),(57,6),(62,7),(79,0)) ⒊(2(48,8),(56,4),(57,6),(62,7),(79,5),(34,0)) ⒋(8(56,4),(57,7),(79,5),(34,0)) 3.对于List类型的线性表,编写出下列每个算法。 ⑴从线性表中删除具有最小值的元素并由函数返回，空出的位置由最后一个元素填补，若 线性表为空则显示出错信息并退出运行。 解： ElemType DMValue(List&L) //从线性表中删除具有最小值的元素并由函数返回,空出的位置 //由最后一个元素填补,若线性表为空则显示出错信息并退出运行 { if(ListEmpty(L)){ cerr<<"List is Empty!"< exit(1); } ElemType x; x=L.list[0]; int k=0; for(int i=1;i ElemType y=L.list[i]; if(y } L.list[k]=L.list[L.size-1]; L.size--; return x; } ⑵从线性表中删除第i个元素并由函数返回。 解：int Deletel(List& L,int i) //从线性表中删除第i个元素并由函数返回 { if(i<1||i>L.size){ cerr<<"Index is out range!"< exit(1); } ElemType x; x=L.list[i-1]; for(int j=i-1;j L.size--; return x; } ⑶向线性表中第i个元素位置插入一个元素。 解：void Inser1(List& L,int i,ElemType x) //向线性表中第i个元素位置插入一个元素 { if(i<1||i>L.size+1){ cerr<<"Index is out range!"< exit(1); } if(L.size==MaxSize) { cerr<<"List overflow!"< exit(1); } for(int j=L.size-1;j>i-1;j--) L.list[j+1]=L.list[j]; L.list[i-1]=x; L.size++; } ⑷从线性表中删除具有给定值x的所有元素。 解：void Delete2(List& L,ElemType x) //从线性表中删除具有给定值x的所有元素 { int i=0; while(i if(L.list[i]==x){ for(int j=i+1;j L.list[j-1]=L.list[j]; L.size--; } else i++; } ⑸从线性表中删除其值在给定值s和t之间(要求s小于t)的所有元素。解：void Delete3(List& L,ElemType s,ElemType t) //从线性表中删除其值在给定值s和t之间的所有元素 { int i=0; while(i if((L.list[i]>=s)&&(L.list[i]<=t)){ for(int j=i+1;j L.size--; } else i++; } ⑹从有序表中删除其值在给定值s和t之间(要求s小于t)的所有元素。解：void Delete4(List& L,ElemType s,ElemType t) //从有序表中删除其值在给定值s和t之间的所有元素 { int i=0; while(i if(L.list[i] else break; if(i While((i+j j++;//求出s和t之间元素的个数 for(int k=i+j;k L.list[k-j]=L.list[k]; L.size-=j; } } ⑺将两个有序表合并成一个新的有序表并由变量返回。 解：void Merge(List& L1,List& L2,List& L3) //将两个有序表合并成一个新的有序表并由变量返回 { if(L1.size+L2.size>MaxSize){ cerr<<"List overflow!"< exit(1); } int i=0,j=0,k=0; while((i if(L1.list[i]<=L2.list[j]) { //将L1中的元素赋给L L.list[k]=L1.list[i]; i++; } else{ //将L2中的元素赋给L L.list[k]=L2.list[j]; j++; } k++; } while(i i++;k++; } while(j L.list[k]=L2.list[j]; j++;k++; } L.size=k; } ⑻从线性表中删除所有其值重复的元素，使其所有元素的值均不同，如对于线性表(2,8,9, 2,5,5,6,8,7,2)，则执行此算法后变为(2,8,9,5,6,7)。 解：void Delete5(List& L) //从线性表中删除所有其值重复的元素,使其所有元素的值均不同 { int i=0; while(i int j=i+1; while(j { //删除重复值为L.list[i]的所有元素 if(L.list[j]==L.list[i]){ for(int k=j+1;k L.list[k-1]=L.list[k]; L.size--; } else j++; } i++; } } 4.对于结点类型为LNode的单链接表,编写出下列每个算法。 ⑴将一个单链接表按逆序链接,即若原单链表中存储元素的次序为a1,a2,...,an,则 逆序链接后变为an,an-1, (1) 解：void Contrary(LNode*&HL) //将一个单多办实事有按逆序链接 { LNode*p=HL;//p指向待逆序的第一个结点，初始指向原表头结点 HL=NULL;//HL仍为逆序后的表头指针，禄始值为空 while(p!=NULL) { //把原单链表中的结点依次进行逆序链接 LNode*q=p; //q指向待处理的结点 p=p->next; //p指向下一个待逆序的结点 //将q结点插入到已陈序单链表的表头 q->next=HL; HL=q; } } ⑵删除单链表中的第i个结点。 解：void Delete1(LNode*&HL,int i) //删除单链表中的第i个结点 { if(i<1||HL==NULL){ cerr<<"Index is out range!"< exit(1); } LNode*ap,*cp; ap=NULL;cp=HL; //cp指向当前结点，ap指向其前驱结点 int j=1; while(cp!=NULL) if(j==i) break; //cp结点即为第i个结点 else{ //继续向后寻找 ap=cp; cp=cp->next; j++; } if(cp==NULL){ cerr<<"Index is out range!"< exit(1); } if(ap==NULL) HL=HL->next; else ap->next=cp->next; delete cp; } ⑶从单链表中查找出所有元素的最大值，该值由函数返回，若单链表为空，则显示出错信息 并停止运行。 解：ElemType MaxValue(LNode*HL) //从单链表中查找出所有元素的最大值，该值由函数返回 { if(HL==NULL){ cerr<<"Linked list is empty!"< exit(1); } ElemType max=HL->data; LNode*p=HL->next; while(p!=NULL){ if(max p=p->next; } return max; } ⑷统计出单链表中结点的值等于给定值x的结点数。 解：int Count(LNode*HL,ElemType x) //统计出单链表中结点的值等于给定值x的结点数 { int n=0; while(HL!=NULL){ if(HL->data==x) n++; HL=HL->next; } return n; } ⑸根据一维数组a[n]建立一个单链表，使单链表中元素的次序与a[n]中元素的次序相同， 并使该算法的时间复杂度为O(n)。 解：void Create(LNode*&HL,ElemType a[],int n) //根据一维数组a[n]建立一个单链表 { InitList(HL); for(int i=n-1;i>=0;i--) InsertFront(HL,a[i]; } ⑹将一个单链表重新链接成有序单链表。 解：void OrderList(LNode*&HL) //将一个单链表重新链接成有序单链表 { LNode* p=HL;//p指向待处理的第一个结点，初始指向原表头结点 HL=NULL; //HL仍为待建立的有序表的表头指针，禄始值为空 while(p!=NULL) { //把原单链表中的结点依次进行有序链接 LNode* q=p; //q指向待处理的结点 p=p->next; //p指向下一个待处理的结点 LNode* ap=NULL,*cp=HL; //cp指向有序表中待比较的结点，ap指向其前驱结点 while(cp!=NULL) { //为插入q结点寻找插入位置 if(q->data break; else{ ap=cp; cp=cp->next; } } //将q结点插入到ap和cpxf hko pp uj q->next=cp; if(ap==NULL) HL=q; else ap->next=q; } } ⑺将两个有序单链表合并成一个有序单链表，合并后使原有单链表为空。解：LNode*Mergel(LNode*&p1,LNode*&p2) //将两个有序单链表合并成一个有序单链表 { LNode a; //a结点作为结果的有序单链表的表头附加结点，这样便于处理，处理 //结束后返回a结点的镄针域的值 LNode*p=&a; //p指向结果的有序单链表的表尾结点 p->next=NULL;//初始指向表头附加结点 while((p1!=NULL)&&(p2!=NULL)) {//处理两个表非空的情况 if(p1->data p->next=p1;p1=p1->next; } else{ p->next=p2;p2=p2->; } p=p->next; } if(p1!=NULL)p->next=p1; if(p2!=NULL)p->next=p2; p1=p2=NULL; return a.next; } ⑻根据两个有序单链表生成一个新的有序单链表，原有单链表保持不变。如假定两个有序单链 表中的元素为(2,8,10,20)和(3,8,9,15,16)，则生成的新单链表中的元素为(2,3,8,8,9,10,15, 16,20)。 解：LNode*Merge2(LNode*p1,LNode*p2) //根据两个有序单链表生成一个新的有序单链表 { LNode a; //用a作为新的有序单链表的表头附加结点 LNode*p=&a; //p指向结果有序单链表的表尾结点 p->next=NULL; //初始指向表头附加结点 while((p1!=NULL&&(p2!=NULL)) { //处理两个表非空时的情况 LNode*newptr=new LNode; if(p1->data { //由p1->data建立新结点，然后p1指针后移 newptr->data=p1->data; p1=p1->next; } else { //由p2->data建立新结点，然后p2指针后移 newptr->data=p2->data; p2=p2->next; } //将newptr结点插入到结果的有序表的表尾 p->next=newptr; p=newptr; } while(p1!=NULL) { //继续处理p1单链表中剩余的结点 LNode*newptr=new LNode; newptr->data=p1->data; p1=p1->next; p->next=newptr; p=newptr; } while(p2!=NULL) { //继续处理p2单链表中剩余的结点 LNode*newptr=new LNode; newptr->data=p2->data; p2=p2->next; p->next=newptr; p=newptr; } p->next=NULL; return a.next; } ⑼根据一个元素类型为整型的单链表生成两个单链表，使得第一个单链表中包含原单链表中所有 元素值为奇数的结点，使得第二个单链表中包含原单链表中所有元素值为偶数的结点。原有单链表 保持不变。 解：void Separate(LNode*HL,LNode*&p1,LNode*&p2) //根据一个单链表HL按条件拆分生成两个单链表p1和p2 { LNode a,b; //a和b结点分别作为p1和p2单链表的表头附加结点 LNode*t1=&a,*t2=&b; //t1和t2分别作为指向p1和p2单链表的 //表尾结点，初始指向表头附加结点 Lnode*p=HL; while(p!=NULL) { //每循环一次产生一个新结点，并把它加入到p1或p2单链表 //的未尾 LNode*newptr=new LNode; if(p->data%2==1){ newptr->data=p->data; t1->next=newptr; t1=newptr; } else{ newptr->data=p->data; t2->next=newptr; t2=newptr; } p=p->next; } t1->next=t2->next=NULL; p1=a.next;p2=b.next; //把指向两个单链表的表头结点的指针分别赋给 //p1和p2返回 } 6.编写一个算法，使用表头附加结点的循环单链表解决约瑟夫(Josephus)问题。其问题是 ：设有n个人围坐在一张圆桌周围，现从某个人开始从1报数，数到m的人出列(即离开坐位， 不参加以后的报数)，接着从出列的下一个人开始重新从1报数，数到m的人又出列，如此下 去直到所有人都出列为止，试求出它们的出列次序。 假如，当n=8、m=4时，若从第一个人(假定每个人的编号依次为1,2...,n)开始报数，则得 到的出列次序为:4,8,5,2,1,3,7,6。 此算法要求以n、m和s(假定从第s个人开始第一次报数)作为值参。 解： void Josephus(int n,int m,int s) //使用带表头附加结点的循环单链表解决约瑟夫问题 { //生成表头附加结点，此时循环单链表为空 LNode*HL=new LNode; HL->next=HL; int i; //生成含有n个结点、结点依次为1,2,...n的带表头结点的循环单链表 for(i=n;i>=1;i--){ //生成新的结点 LNode*newptr=new LNode; newptr->data=i; //把新的结点插入到表头 newptr->next=HL->next; HL->next=newptr; } //从表头开始顺序查找出第s个结点，对应第一个开始报数的人 LNode*ap=HL,*cp=HL->next; for(i=1;i //ap和cp指针后移一个位置 ap=cp; cp=cp->next; //若cp指向了表头附加结点，则仍需后移ap和cp指针，使之指向表头结点if(cp==HL){ap=HL;cp=HL->next;} } //依次使n-1个人出列 for(i=1;i //顺序查找出待出列的人，即为循环结束后cp所指向的结点 for(int j=1;j ap=cp; cp=cp->next; if(cp==HL){ap=HL;cp=HL->next;} } //输出cp结点的值，即出列的人 cout< //从单链表中删除cp结点 ap->next=cp->next; delete cp; //使cp指向被删除结点的后继结点 cp=ap->next; //若cp指向了表头附加结点，则后移ap和cp指针 if(cp==HL){ap=HL;cp=HL->next;} } //使最后一个人出列 cout< //删除表头结点和表头附加结点 delete HL->next; delete HL; } 7.对于在线性表抽象数据类型中定义的每一个操作，写出结点类型为LNode的带头附加结点 的循环单链表上实现的对应算法。 ⑴初始化单链表 解：void InitList(LNode*HL) { HL->next=HL;//将单链表置空 } ⑵删除单链表中的所有结点，使之成为一个空表 void ClearList(LNode*HL) { LNode*cp,*np; cp=HL->next;//将指向第一个结点的指针赋给cp while(cp!=HL)//遍历单链表，向系统交回每一个结点。 { np=cp->next;//保存下一个结点的指针。 delete cp;//删除当前结点。 cp=np;//使下一个结点成为当前结点。 } HL->next=HL;//置单链表为空 } ⑶得到单链表的长度 int ListSize(LNode*HL) { LNode*p=HL->next; int i=0; while(p!=HL){i++;p=p->next;} return i; } ⑷检查单链表是否为空 int ListEmpty(LNode*hl) { return(HL->next==HL); } ⑸得到单链表中第pos个结点中的元素 ElemType GetElem(LNode*HL,int pos) { if(pos<1){ cerr<<"pos is out range!"< exit(1); } LNode* p=HL->next; int i=0; while(p!=HL){ i++; if(i==pos)break; p=p->next; } if(p!=HL)return p->data; else{ cerr<<"pos is out range!"< exit(1); } } ⑹遍历单链表 void TraverseList(LNode*HL) { LNode* p=HL->next; while(p!=HL){ cout< p=p->next; } cout< } ⑺从单链表查找具有给定值的第一个元素 int Find(LNode* HL,ElemType& item) { LNode* p=HL->next; while(p!=HL) if(p->data==item){ item=p->data; return 1; } else p=p->next; return 0; } ⑻更新单链表中具有给定值的第一个元素 int Updata(LNode* HL,const ElemType& item) { LNode* p=HL->next; while(p!=HL)//查找元素 if(p->data==item)break; else p=p->next; if(p==HL)return 0; else{//更新元素 p->data=item; 第一章概论自测题答案 一、填空题 1. 数据结构是一门研究非数值计算的程序设计问题中计算机的操作对象以及它们之间的关系和运算等的学科。 2. 数据结构被形式地定义为（D, R），其中D是数据元素的有限集合，R是D上的关系有限集合。 3. 数据结构包括数据的逻辑结构、数据的存储结构和数据的运算这三个方面的内容。 4. 数据结构按逻辑结构可分为两大类，它们分别是线性结构和非线性结构。 5. 线性结构中元素之间存在一对一关系，树形结构中元素之间存在一对多关系，图形结构中元素之间存在多对多关系。 6．在线性结构中，第一个结点没有前驱结点，其余每个结点有且只有1个前驱结点；最后一个结点没有后续结点，其余每个结点有且只有1个后续结点。 7. 在树形结构中，树根结点没有前驱结点，其余每个结点有且只有1个前驱结点；叶子结 点没有后续结点，其余每个结点的后续结点数可以任意多个。 8. 在图形结构中，每个结点的前驱结点数和后续结点数可以任意多个。 9．数据的存储结构可用四种基本的存储方法表示，它们分别是顺序、链式、索引和散列。 10. 数据的运算最常用的有5种，它们分别是插入、删除、修改、查找、排序。 11. 一个算法的效率可分为时间效率和空间效率。 二、单项选择题 （B）1. 非线性结构是数据元素之间存在一种： A）一对多关系B）多对多关系 C）多对一关系D）一对一关系 （ C ）2. 数据结构中，与所使用的计算机无关的是数据的结构； A) 存储B) 物理 C) 逻辑D) 物理和存储 （C）3. 算法分析的目的是： A) 找出数据结构的合理性 B) 研究算法中的输入和输出的关系 C) 分析算法的效率以求改进 D) 分析算法的易懂性和文档性 （A）4. 算法分析的两个主要方面是： A) 空间复杂性和时间复杂性 B) 正确性和简明性 C) 可读性和文档性 D) 数据复杂性和程序复杂性 （ C ）5. 计算机算法指的是： A) 计算方法 B) 排序方法 C) 解决问题的有限运算序列 D) 调度方法 （B）6. 计算机算法必须具备输入、输出和等5个特性。 A) 可行性、可移植性和可扩充性 B) 可行性、确定性和有穷性 C) 确定性、有穷性和稳定性 D) 易读性、稳定性和安全性 一、单选题（每题 2 分，共20分） 1. 1.对一个算法的评价，不包括如下（B ）方面的内容。 A．健壮性和可读性B．并行性C．正确性D．时空复杂度 2. 2.在带有头结点的单链表HL中，要向表头插入一个由指针p指向的结 点，则执行( )。 A. p->next=HL->next; HL->next=p; B. p->next=HL; HL=p; C. p->next=HL; p=HL; D. HL=p; p->next=HL; 3. 3.对线性表，在下列哪种情况下应当采用链表表示？( ) A.经常需要随机地存取元素 B.经常需要进行插入和删除操作 C.表中元素需要占据一片连续的存储空间 D.表中元素的个数不变 4. 4.一个栈的输入序列为1 2 3，则下列序列中不可能是栈的输出序列的是 ( C ) A. 2 3 1 B. 3 2 1 C. 3 1 2 D. 1 2 3 5. 5.AOV网是一种（）。 A．有向图B．无向图C．无向无环图D．有向无环图 6. 6.采用开放定址法处理散列表的冲突时，其平均查找长度（）。 A．低于链接法处理冲突 B. 高于链接法处理冲突 C．与链接法处理冲突相同D．高于二分查找 7.7.若需要利用形参直接访问实参时，应将形参变量说明为（）参数。 A．值B．函数C．指针D．引用 8.8.在稀疏矩阵的带行指针向量的链接存储中，每个单链表中的结点都具 有相同的（）。 A．行号B．列号C．元素值D．非零元素个数 9.9.快速排序在最坏情况下的时间复杂度为（）。 A．O(log2n) B．O(nlog2n) C．0(n) D．0(n2) 10.10.从二叉搜索树中查找一个元素时，其时间复杂度大致为( )。 A. O(n) B. O(1) C. O(log2n) D. O(n2) 二、二、运算题（每题 6 分，共24分） 1. 1.数据结构是指数据及其相互之间的______________。当结点之间存在M 对N（M：N）的联系时，称这种结构为_____________________。 2. 2.队列的插入操作是在队列的___尾______进行，删除操作是在队列的 ____首______进行。 3. 3.当用长度为N的数组顺序存储一个栈时，假定用top==N表示栈空，则 表示栈满的条件是___top==0___(要超出才为满)_______________。 4. 4.对于一个长度为n的单链存储的线性表，在表头插入元素的时间复杂度 为_________，在表尾插入元素的时间复杂度为____________。 16 void Descend(int &x, int &y, int &z) { int t; if(x while(result[i].sport!=NULL) { switch(result[i].schoolname) { case 'A': score[0].totalscore+=result[i].score; if(result[i].gender==male) score[0].malescore+=result[i].score; else score[0].femalescore+=result[i].score; break; case 'B': score[1].totalscore+=result[i].score; if(result[i].gender==male) score[1].malescore+=result[i].score; else score[1].femalescore+=result[i].score; break; case 'C': score[2].totalscore+=result[i].score; if(result[i].gender==male) score[2].malescore+=result[i].score; else score[2].femalescore+=result[i].score; break; case 'D': score[3].totalscore+=result[i].score; if(result[i].gender==male) score[3].malescore+=result[i].score; else score[3].femalescore+=result[i].score; break; case 'E': score[4].totalscore+=result[i].score; if(result[i].gender==male) score[4].malescore+=result[i].score; else score[4].femalescore+=result[i].score; break; } i++; } for(s='A';s<='E';s++) { printf("School %c:\n",s); printf("Total score of male:%d\n",score[i].malescore); printf("Total score of female:%d\n",score[i].femalescore); printf("Total score of all:%d\n\n",score[i].totalscore); } } 19 Status Series(int ARRSIZE, int a[]) 判断题 1.数据的逻辑结构与数据元素本身的容和形式无关。（√） 2.一个数据结构是由一个逻辑结构和这个逻辑结构上的一个基本运算集构成的整体。（√） 3.数据元素是数据的最小单位。（√） 4.数据的逻辑结构和数据的存储结构是相同的。（×） 5.程序和算法原则上是没有区别的，所以在讨论数据结构时可以通用。（×） 6.从逻辑关系上讲，数据结构主要分为线性结构和非线性结构。（√） 7.数据的存储结构是数据的逻辑结构的存储映像。（×） 8.数据的物理结构是指数据在计算机实际的存储形式。（√） 9.数据的逻辑结构是依赖于计算机的。（×） 10.算法是对解题方法和的描述步骤。（√） 填空题： 1.数据有逻辑结构和存储结构两种结构。 2.数据逻辑结构除了集合以外，还包括线性结构、树形结构和图形结构。 3.数据结构按逻辑结构可分为两大类，它们是线性结构和非线性结构。 4.树形结构和图形结构合称为非线性结构。 5.在树形结构中，除了树根结点以外，其余每个结点只有 1 个前驱结点。 6.在图形结构中，每个结点的前驱结点数和后继结点数可以任意多个。 7.数据的存储结构又叫物理结构。 8.数据的存储结构形式包括顺序存储、链式存储、索引存储和散列存储。 9.线性结构中的元素之间存在一对一的关系。 10.树形结构中的元素之间存在一对多的关系。 11.图形结构的元素之间存在多对多的关系。 12.数据结构主要研究数据的逻辑结构、存储结构和算法（或运算）3个方面 的容。 13.数据结构被定义为（D，R），其中D是数据的有限集合，R是D上的关系的 有限集合。 14.算法是一个有穷指令的集合。 15.算法效率的度量可以分为事先估算和事后统计法。 16.一个算法的时间复杂性是算法输入规模的函数。 17.算法的空间复杂度是指该算法所耗费的存储空间，它是该算法求解问题 规模n的函数。 18.若一个算法中的语句频度之和为T（n）=6n+3nlog2n，则算法的时间复杂度为O （nlog2n ）。 若一个算法中的语句频度之和为T（n）=3n+nlog2n+n2，则算法的时间复杂度为 ___O（n*n）_______ 。 数据结构是一门研究非数值计算的程序设计总是中计算机的操作对象，以及它们之间的关系和运算的学科。 19.串的两种最基本的存储方式是顺序存储方式链式存储方式。 20.两个串相等的充分必要条件是、长度相等对应位置的字符相同。 数据结构试题? 一、?单选题（每题 2 分，共20分） 1.1.???? 对一个算法的评价，不包括如下（ B ）方面的内容。 A．健壮性和可读性B．并行性 C．正确性 D．时空复杂度 2.2.???? 在带有头结点的单链表HL中，要向表头插入一个由指针p指向的结点， 则执行( A )。 A. p->next=HL->next; HL->next=p; B. p->next=HL; HL=p; C. p->next=HL; p=HL; D. HL=p; p->next=HL; 3.3.???? 对线性表，在下列哪种情况下应当采用链表表示？( B ) A.经常需要随机地存取元素 B.经常需要进行插入和删除操作 C.表中元素需要占据一片连续的存储空间 D.表中元素的个数不变 4.4.???? 一个栈的输入序列为 1 2 3，则下列序列中不可能是栈的输出序列的是 ( C ) A. 2 3 1 B. 3 2 1 C. 3 1 2 D. 1 2 3 5.5.???? AOV网是一种（ D ）。 A．有向图 B．无向图 C．无向无环图D．有向无环图 6.6.???? 采用开放定址法处理散列表的冲突时，其平均查找长度（ B ）。 A．低于链接法处理冲突 B. 高于链接法处理冲突 C．与链接法处理冲突相同 D．高于二分查找 7.7.???? 若需要利用形参直接访问实参时，应将形参变量说明为（ D ）参数。 A．值 B．函数 C．指针 D．引用 8.8.???? 在稀疏矩阵的带行指针向量的链接存储中，每个单链表中的结点都具有 相同的（ A ）。 A．行号B．列号 C．元素值 D．非零元素个数 9.9.???? 快速排序在最坏情况下的时间复杂度为（ D ）。 A．O(log 2n) B．O(nlog 2 n) C．O(n) D．O(n2) 10.10. 从二叉搜索树中查找一个元素时，其时间复杂度大致为( C )。 A. O(n) B. O(1) C. O(log 2 n) D. O(n2) 二、运算题（每题 6 分，共24分） 1. 1.?数据结构是指数据及其相互之间的_对应关系(联系)。当结点之间存在M对N（M： N）的联系时，称这种结构为图（或图结构）。 2. 2.队列的插入操作是在队列的__队尾___进行，删除操作是在队列的_对头_进行。 3. 3.??当用长度为N的数组顺序存储一个栈时，假定用top==N表示栈空，则表示栈 满的条件是_top==0__。 4. 4.???对于一个长度为n的单链存储的线性表，在表头插入元素的时间复杂度为 第一章绪论 一、填空题 1．数据是描述客观事物的数、字符以及所有能输入到计算机且能够被计算机程序加工处理的符号集合。____数据元素_____是数据的基本单位；____数据项_______是数据的最小单位。通常被计算机加工处理的数据不是孤立无关的，而是彼此之间存在着某种联系，将这种数据间的联系称为____结构____。 2．数据结构进行形式化定义时，可以从逻辑上认为数据结构DS是_____数据元素的有限集____的集合D和D上____关系的有限集_____的集合R所构成的二元组：DS=（D，R）。 3． 4．一个算法的时间复杂度通常用问题规模大小的函数来表示，当一个算法的时间复杂度与问题规模n大小无关时，则表示为____O(1)______；成正比关系时，则表示为_____O(n)______；成对数关系时，则表示为 ____O(log2n)_______；成平方关系时，则表示为____O(n2)______。 5．数据结构的逻辑结构包括_____线性结构________、树型结构和图型结构三种类型，其中树型结构和图型结构合称为______非线性结构_______；数据结构的存储结构主要包括____顺序________和______链式______两种类型。 6．线性结构的特点是：第一个结点___无____前驱结点，其余结点有且仅有__一_____个前驱结点；最后一个结点__无_____后继结点，其余每个结点有且仅有___一____个后继结点。 7．树型结构的特点是：根结点没有__前驱______结点，其余每个结点有且仅有_____一个___个前驱结点；叶子结点_____无____后继结点，其余结点可以有___任意______个后继结点。 8．图型结构的特点是：每个结点可以有____任意_____个前驱结点和后继结点。 9．程序段for（i=1，s=0；s 第 1 章绪论 课后习题讲解 1. 填空 ⑴（）是数据的基本单位，在计算机程序中通常作为一个整体进行考虑和处理。 【解答】数据元素 ⑵（）是数据的最小单位，（）是讨论数据结构时涉及的最小数据单位。 【解答】数据项，数据元素 【分析】数据结构指的是数据元素以及数据元素之间的关系。 ⑶从逻辑关系上讲，数据结构主要分为（）、（）、（）和（）。 【解答】集合，线性结构，树结构，图结构 ⑷数据的存储结构主要有（）和（）两种基本方法，不论哪种存储结构，都要存储两方面的内容：（）和（）。 【解答】顺序存储结构，链接存储结构，数据元素，数据元素之间的关系 ⑸算法具有五个特性，分别是（）、（）、（）、（）、（）。 【解答】有零个或多个输入，有一个或多个输出，有穷性，确定性，可行性 ⑹算法的描述方法通常有（）、（）、（）和（）四种，其中，（）被称为算法语言。 【解答】自然语言，程序设计语言，流程图，伪代码，伪代码 ⑺在一般情况下，一个算法的时间复杂度是（）的函数。 【解答】问题规模 ⑻设待处理问题的规模为n，若一个算法的时间复杂度为一个常数，则表示成数量级的形式为（），若为n*log25n，则表示成数量级的形式为（）。 【解答】Ο(1)，Ο(nlog2n) 【分析】用大O记号表示算法的时间复杂度，需要将低次幂去掉，将最高次幂的系数去掉。 2. 选择题 ⑴顺序存储结构中数据元素之间的逻辑关系是由（）表示的，链接存储结构中的数据元素之间的逻辑关系是由（）表示的。 A 线性结构 B 非线性结构 C 存储位置 D 指针 【解答】C，D 【分析】顺序存储结构就是用一维数组存储数据结构中的数据元素，其逻辑关系由存储位置（即元素在数组中的下标）表示；链接存储结构中一个数据元素对应链表中的一个结点，元素之间的逻辑关系由结点中的指针表示。 结构设计常用数据 ————————————————————————————————作者：————————————————————————————————日期: ? 混凝土结构设计规范 表３．4.3受弯构件的挠度限值 构件类型挠度限值 吊车梁手动吊车l0/５0０电动吊车l0／6０0 屋盖、楼盖及楼梯构件 当l0<７m时 l0/20０（l0／２ ５0） 当７m≤l0≤9 ｍ时 l0／25０（l0／ 300） 当l0＞９m时 l0／30０(l0/４ 00) 表3．3.5 结构构件的裂缝控制等级及最大裂缝宽度的限值(mm） 环境类别钢筋混凝土结构 预应力混凝土结 构 裂缝控 制等级 w lim 裂缝控 制等级 w lim 一 三级0.３0 （0.4 ０） 三级 0．2０ 二a ０．2０0.1０ 二b 二级——三ａ、三一级—— b 表３.3.２混凝土结构的环境类别环境类 别 条件 一室内干燥环境; 无侵蚀性静水浸没环境 二ａ 室内潮湿环境； 非严寒和非寒冷地区的露天环境； 非严寒和非寒冷地区与无侵蚀性的水或土壤直接接触的环境; 严寒和寒冷地区的冰冻线以下与无侵蚀性的水或土壤直接接触的环境 二b 干湿交替环境； 水位频繁变动环境; 严寒和寒冷地区的露天环境； 严寒和寒冷地区冰冻线以上与无侵蚀性的水或土壤直接接触的环境 三a 严寒和寒冷地区冬季水位变动区环境; 受除冰盐影响环境； 海风环境 三b 盐渍土环境; 受除冰盐作用环境; 海岸环境 四 海水环境 五 受人为或自然的侵蚀性物质影响的环境 表3.5.3 结构混凝土材料的耐久性基本要求 环境等级 最大水胶比 最低强度等级 最大氯离子含量（%） 最大碱含量（k ｇ/m 3） 一 0．60 C ２０ 0．３０ 不限制 环境等级 最大水胶比 最低强度等级 最大氯离子含量（%） 最大碱含量(ｋg/m 3） 二a ０.55 Ｃ２５ 0.20 3.0 二b ０.５０(0.５５） C30（Ｃ 2５） 0．15 三a 0．45(０．5 ０) C3５(C3０） ０.1５ 三b 0.４0 C ４0 0．１0 表8．1.1 钢筋混凝土结构伸缩缝最大间距(m) 结构类型 室内或土 露天 第一章绪论 1．下面是几种数据的逻辑结构S=(D，R)，分别画出对应的数据逻辑结构，并指出它们分别属于何种结构。 D={a，b，c，d，e，f} R={r} (a) r={ 数据结构题集答案 数据结构题集 第一章绪论 一、单选题 1.在数据结构中，从逻辑上可以把数据结构分成【 C 】。 A.动态结构和静态结构 B.紧凑结构和非紧凑结构 C.线性结构和非线性结构 D.内部结构和外部结构 2.数据结构在计算机内存中的表示是指【 A 】。 A.数据的存储结构 B.数据结构 C.数据结构的逻辑结构 D.数据元素之间的关系 3. 【 A 】是数据的最小单位，【 B 】是数据的基本单位。 A.数据项 B.数据元素 C.信息项 D.表元素 4. 计算机所处理数据一般具有某种内在联系，这是指【 B 】。 A.数据与数据之间存在某种关系 B.数据元素与数据元素之间存在某种关系 C.元素内部存在某种结构 D.数据项与数据项之间存在某种关系 5.算法分析的目的是【 C 】。 A.找出数据结构的合理性 B.研究输入和输出的关系 C.分析算法的效率以求改进 D.分析算法的易懂性 6.在存储数据时，不仅要考虑存储各数据元素的值，而且还要存储【 C 】。 A.数据处理的方法 B.数据元素的类型 C.数据元素之间的关系 D.数据的存储方法 7.算法分析的主要任务是分析【 D 】。 A.算法是否具有较好的可读性 B.算法中是否存储语法错误和逻辑错误 C.算法的功能是否符合设计要求 D.算法的执行时间与问题规模之间的关系。 8.数据的运算【 A 】。 A.效率与采用何种存储结构有关 B.是根据存储结构来定义的 C.有算术运算和关系运算两大类 D.必须用程序设计语言来描述 9.算法的计算量的大小称为算法的【 B 】。 A.效率 B.时间复杂度 C.现实性 D.难度 10.连续存储分配时，存储单元的地址【A 】。 A.一定连续 B.一定不连续 C.不一定连续 D.部分连续，部分不连续 二、判断题 1.数据元素是数据结构的最小单位【.×】。 2.数据的逻辑结构说明数据元素之间的顺序关系，它依赖于计算机的存储结构【×.】。 3.数据的逻辑结构指数据元素的各数据项之间的逻辑关系【×.】。 4.算法的优劣与算法的描述语言无关，但与使用的计算机有关【.×】。 5.数据结构的抽象操作的定义与具体实现有关【.×】。 十年结构设计经验的总结 1.关于箱、筏基础底板挑板的阳角问题： (1).阳角面积在整个基础底面积中所占比例极小，干脆砍了。可砍成直角或斜角。 (2).如果底板钢筋双向双排，且在悬挑部分不变，阳角不必加辐射筋，谁见过独立基础加辐射筋的？当然加了也无坏处。 (3).如果甲方及老板不是太可恶的话，可将悬挑板的单向板的分布钢筋改为直径12的，别小看这一改，一个工程省个3、2万不成问题。 2.关于箱、筏基础底板的挑板问题： (1).从结构角度来讲，如果能出挑板，能调匀边跨底板钢筋，特别是当底板钢筋通长布置时，不会因边跨钢筋而加大整个底板的通长筋，较节约。 (2).出挑板后，能降低基底附加应力，当基础形式处在天然地基和其他人工地基的坎上时，加挑板就可能采用天然地基。必要时可加较大跨度的周圈窗井。 (3).能降低整体沉降，当荷载偏心时，在特定部位设挑板，还可调整沉降差和整体倾斜。 (4).窗井部位可以认为是挑板上砌墙，不宜再出长挑板。虽然在计算时此处板并不应按挑板计算。当然此问题并不绝对，当有数层地下室，窗井横隔墙较密，且横隔墙能与内部墙体连通时，可灵活考虑。 (5).当地下水位很高，出基础挑板，有利于解决抗浮问题。 (6).从建筑角度讲，取消挑板，可方便柔性防水做法。当为多层建筑时，结构也可谦让一下建筑。 3.关于箍筋在梁配筋中的比例问题(约10~20%)： 例如一8米跨梁，截面为400X600，配筋：上6根25，截断1/3，下5根25，箍筋：8@100/200(4),1000范围内加密。纵筋总量： 3.85*9*8=281kg,箍筋：0.395*3.5*50=69,箍筋/纵筋=1/4, 如果双肢箍仅为1/8，箍筋相对纵筋来讲所占比例较小，故不必在箍筋上抠门。且不说要强剪弱弯。已经是构造配箍除外。 4.关于梁、板的计算跨度： 一般的手册或教科书上所讲的计算跨度，如净跨的1.1倍等，这些规定和概念仅适用于常规的结构设计，在应用日广的宽扁梁中是不合适的。梁板结构，简单点讲，可认为是在梁的中心线上有一刚性支座，取 第1章 绪论 1.1 简述下列术语：数据，数据元素、数据对象、数据结构、存储结构、数据类型和抽象数据类型。 解：数据是对客观事物的符号表示。在计算机科学中是指所有能输入到计算机中并被计算机程序处理的符号的总称。 数据元素是数据的基本单位，在计算机程序常作为一个整体进行考虑和处理。 数据对象是性质相同的数据元素的集合，是数据的一个子集。 数据结构是相互之间存在一种或多种特定关系的数据元素的集合。 存储结构是数据结构在计算机中的表示。 数据类型是一个值的集合和定义在这个值集上的一组操作的总称。 抽象数据类型是指一个数学模型以及定义在该模型上的一组操作。是对一般数据类型的扩展。 1.2 试描述数据结构和抽象数据类型的概念与程序设计语言中数据类型概念的区别。 解：抽象数据类型包含一般数据类型的概念，但含义比一般数据类型更广、更抽象。一般数据类型由具体语言系统部定义，直接提供给编程者定义用户数据，因此称它们为预定义数据类型。抽象数据类型通常由编程者定义，包括定义它所使用的数据和在这些数据上所进行的操作。在定义抽象数据类型中的数据部分和操作部分时，要求只定义到数据的逻辑结构和操作说明，不考虑数据的存储结构和操作的具体实现，这样抽象层次更高，更能为其他用户提供良好的使用接口。 1.3 设有数据结构(D,R)，其中 {}4,3,2,1d d d d D =，{}r R =，()()(){}4,3,3,2,2,1d d d d d d r = 试按图论中图的画法惯例画出其逻辑结构图。 解： 1.4 试仿照三元组的抽象数据类型分别写出抽象数据类型复数和有理数的定义（有理数是其分子、分母均为自然数且分母不为零的分数）。 解： ADT Complex{ 数据对象：D={r,i|r,i 为实数} 数据关系：R={ 钢筋混凝土结构设计经验数据分享 1、结构类型如何选择？ 解释：（1）对于高度不超过150米的多高层项目一般都选择采用钢筋混凝土结构； （2）对于高度超过150米的高层项目则可能会采用钢结构或混凝土结构类型； （3）对于落后偏远地区的民宅或小工程则可能采用砌体结构类型. 2、结构体系如何选择？ 解释：对于钢筋混凝土结构,当房屋高度不超过120米时,一般均为三大常规结构体系——框架结构、剪力墙结构、框架—剪力墙结构. （1）对于学校、办公楼、会所、医院以及商场等需要较大空间的建筑, 当房屋高度不超过下表时,一般选择框架结构； 当房屋高度超过下表时,一般选择框架-剪力墙结构； 抗震设防烈度 6 度 7度 （0.1g） 7度 （0.15g） 8度 （0.2g） 8度 （0.30g） 框架结构 经济适用 高度（m） 3530252015（2）对于高层住宅、公寓、酒店等隔墙位置固定且空间较小的建筑项目一般选择剪力墙结构.当高层住宅、公寓、酒 店项目底部一层或若干层因建筑功能要求（如大厅或商业）需要大空间时,一般采用部分框支剪力墙结构. （3）对于高度大于100米的高层写字楼,一般采用框架-核心筒结构. 3、广州地区某40米高的办公楼采用框架结构体系合理吗？ 解释：不合理.7度区框架结构经济适用高度为30米,超过30米较多时应在合适的位置（如楼梯、电梯、辅助用房）布置剪力墙,形成框架-剪力墙结构体系.这样子剪力墙承受大部分水平力,大大减小框架部分受力,从而可以减小框架柱、框架梁的截面和配筋,使得结构整体更加经济合理. 4、框架结构合理柱网及其尺寸？ 解释：（1）柱网布置应有规律,一般为正交轴网. （2）普通建筑功能的多层框架结构除个别部位外不宜采用单跨框架,学校、医院等乙类设防建筑以及高层建筑不应采用单跨框架. （3）仅从结构经济性考虑,低烈度区（6度、7度）且风压小（小于0.4）者宜采用用大柱网（9米左右）；高烈度区（8度及以上）者宜采用中小柱网（4~6米左右）. （4）一般情况下,柱网尺寸不超过12米；当超过12米时可考虑采用钢结构. 第一章概论 一、选择题 1、研究数据结构就是研究（Ｄ）。 Ａ. 数据的逻辑结构?B。数据的存储结构 C。数据的逻辑结构和存储结构?D．数据的逻辑结构、存储结构及其基本操作(研究非数值计算的程序设计问题中，计算机操作对象以及他们之间的关系和操作) 2、算法分析的两个主要方面是（Ａ）。 A．空间复杂度和时间复杂度???B。正确性和简单性 C。可读性和文档性D．数据复杂性和程序复杂性 3、具有线性结构的数据结构是（ D ）。(线性结构就是：在非空有限集合中，存在为一个被称为第一个的数据元素和最后一个元素,有除了第一个元素，集合中每一个元素均只有一个前驱，除了最后一个元素有唯一后继)（链表、栈、队列、数组、串） A. 图Ｂ. 树??C．广义表(线性表的推广) D．栈 4、计算机中的算法指的是解决某一个问题的有限运算序列,它必须具备输入、输出、（ B ）等5个特性。 Ａ．可执行性、可移植性和可扩充性? B. 可执行性、有穷性和确定性 C。确定性、有穷性和稳定性??? D. 易读性、稳定性和确定性 5、下面程序段的时间复杂度是( C ）。 for(i=0；i 数据结构试题 一、单项选择 1、若某线性表中最常用的操作是在最后一个元素之后插入和删除元素，则采用___________最节省运算时间. A、单链表 B、仅有头指针的单循环链表 C、仅有尾指针的单循环链表 D、双链表 2、哈夫曼树的带权路径长度WPL等于___________. A、除根以外的所有结点的权植之和 B、所有结点权值之和 C、各叶子结点的带权路径长度之和 D、根结点的值 3、设输入序列为1,2,3,4,5，借助一个栈不可能得到的输出序列是___________. A、1,2,3,4,5 B、1,4,3,2,5 C、4,1,3,2,5 D、1,3,2,5,4 4、20个结点的完全二叉树，其高度为___________. A、3 B、2 C、4 D、5 5、栈和队列都是___________. A、顺序存储的线性结构 B、链式存储的线性结构 C、限制存储点的线性结构 D、限制存储点的非线性结构 6、已知完全二叉树有30个结点，则整个二叉树有___________个度为1的结点. A、0 B、1 C、2 D、不确定 7、对于N个结点的完全无向图，其边数是___________ A、N B、N2 C、N(N-1)/2 D、N(N-1) 8、队列的特点是 A、先进先出 B、先进后出 C、后进先出 D、不进不出 9、连通分量是的极大连通子图。 A、有向图 B、树 C、无向图 D、图 10、现有一“遗传”关系：设x是y的父亲，则x可以把它的属性遗传给y。表示该遗传关系最适合的数据结构为.............................. A、向量 B、树 C、图 D、二叉树 11、栈和队列都是（）. A、线性结构 B、链式存储的线性结构 C、线性结构或非线性结构 D、非线性结构 12、二叉树第J层有（）个结点 A、J B、2J C、J+1 D、不能确定 13、若图G中（）是有向的，则称此图为有向图. 严蔚敏 数据结构C 语言版答案详解 第1章 绪论 1.1 简述下列术语：数据，数据元素、数据对象、数据结构、存储结构、数据类型和抽象数据类型。 解：数据是对客观事物的符号表示。在计算机科学中是指所有能输入到计算机中并被计算机程序处理的符号的总称。 数据元素是数据的基本单位，在计算机程序中通常作为一个整体进行考虑和处理。 数据对象是性质相同的数据元素的集合，是数据的一个子集。 数据结构是相互之间存在一种或多种特定关系的数据元素的集合。 存储结构是数据结构在计算机中的表示。 数据类型是一个值的集合和定义在这个值集上的一组操作的总称。 抽象数据类型是指一个数学模型以及定义在该模型上的一组操作。是对一般数据类型的扩展。 1.2 试描述数据结构和抽象数据类型的概念与程序设计语言中数据类型概念的区别。 解：抽象数据类型包含一般数据类型的概念，但含义比一般数据类型更广、更抽象。一般数据类型由具体语言系统内部定义，直接提供给编程者定义用户数据，因此称它们为预定义数据类型。抽象数据类型通常由编程者定义，包括定义它所使用的数据和在这些数据上所进行的操作。在定义抽象数据类型中的数据部分和操作部分时，要求只定义到数据的逻辑结构和操作说明，不考虑数据的存储结构和操作的具体实现，这样抽象层次更高，更能为其他用户提供良好的使用接口。 1.3 设有数据结构(D,R)，其中 {}4,3,2,1d d d d D =，{}r R =，()()(){}4,3,3,2,2,1d d d d d d r = 试按图论中图的画法惯例画出其逻辑结构图。 解： 1.4 试仿照三元组的抽象数据类型分别写出抽象数据类型复数和有理数的定义（有理数是其分子、分母均为自然数且分母不为零的分数）。 解： ADT Complex{ 数据对象：D={r,i|r,i 为实数} 数据关系：R={ 结构工程师十年设计经验总结 1关于箱、筏基础底板挑板的阳角问题： (1)阳角面积在整个基础底面积中所占比例极小,干脆砍了.可砍成直角或斜角. (2)如果底板钢筋双向双排,且在悬挑部分不变,阳角不必加辐射筋,谁见过独立基础加辐射筋的？当然加了也无坏处. (3)如果甲方及老板不是太可恶的话,可将悬挑板的单向板的分布钢筋改为直径12的,别小看这一改,一个工程省个3、2万不成问题. 2关于箱、筏基础底板的挑板问题： 1)从结构角度来讲,如果能出挑板,能调匀边跨底板钢筋,特别是当底板钢筋通长布置时,不会因边跨钢筋而加大整个底板的通长筋,较节约. (2)出挑板后,能降低基底附加应力,当基础形式处在天然地基和其他人工地基的坎上时,加挑板就可能采用天然地基.必要时可加较大跨 度的周圈窗井. (3)能降低整体沉降,当荷载偏心时,在特定部位设挑板,还可调整沉降差和整体倾斜. (4)窗井部位可以认为是挑板上砌墙,不宜再出长挑板.虽然在计算时此处板并不应按挑板计算.当然此问题并不绝对,当有数层地下室,窗井横隔墙较密,且横隔墙能与内部墙体连通时,可灵活考虑. (5)当地下水位很高,出基础挑板,有利于解决抗浮问题. (6)从建筑角度讲,取消挑板,可方便柔性防水做法.当为多层建筑时,结构也可谦让一下建筑. 3关于箍筋在梁配筋中的比例问题(约10~20%)： 例如一8米跨梁,截面为400X600,配筋：上6根25,截断1/3,下5根25,箍筋范围内加密.纵筋总量：385*9*8=281kg,箍筋： 0395*35*50=69,箍筋/纵筋=1/4,如果双肢箍仅为1/8,箍筋相对纵筋来讲所占比例较小,故不必在箍筋上抠门.且不说要强剪弱弯.已经是构造配箍除外. 4关于梁、板的计算跨度： 一般的手册或教科书上所讲的计算跨度,如净跨的11倍等,这些规定和概念仅适用于常规的结构设计,在应用日广的宽扁梁中是不合适的.梁板结构,简单点讲,可认为是在梁的中心线上有一刚性支座,取消梁的概念,将梁板统一认为是一变截面板.在扁梁结构中,梁高比板厚大不了多少时,应将计算长度取至梁中心,选梁中心处的弯距和梁厚,及梁边弯距和板厚配筋,取二者大值配筋.（借用台阶式独立基础变截面处的概念）柱子也可认为是超大截面梁,所以梁配筋时应取柱边弯距.削峰是正常的,不削峰才有问题. 5纵筋搭接长度为若干倍钢筋直径d,一般情况下,d取钢筋直径的较小值,这是有个前提,即大直径钢筋强度并未充分利用.否则应取钢筋直径的较大值.如框架结构顶层的柱子纵筋有时比下层大,d应取较大的钢筋直径,甚至纵筋应向下延伸一层.其实,两根钢筋放一起,用铁丝捆 数据结构试卷 数据结构试卷 数据结构试卷 数据结构试卷 数据结构试卷 数据结构试卷 数据结构试卷 数据结构试卷 数据结构试卷 数据结构试卷 （一） （二） （三） （四） （五） （六） （七 ）（八 ） （九 ） （十 ） 9 12 15 17 19 21 24 数据结构试卷 数据结构试卷 数据结构试卷 数据结构试卷 数据结构试卷 数据结构试卷 数据结构试卷 数据结构试卷 数据结构试卷 数据结构试卷 （一） （二） （三 ） （四 ） （五 ） （六） （七） （八） （九） （十 ） 27 28 29 31 33 35 37 38 39 40 数据结构试卷(一) 、单选题(每题 栈和队列的共同特点是(A ) 。 A. 只允许在端点处插入和删除元素 B. 都是先进后出 C. 都是先进先出 D. 没有共同点 用链接方式存储的队列，在进行插入运算时 (C ). 头、尾指针都要修改 头、尾指针可能都要修改 (D ) 线性表 2分，共20分) 1. 2. A. C. 3. A. 4. 仅修改头指针 B. 仅修改尾指针 D. 以下数据结构中哪一个是非线性结构? 队列 B.栈 C. 设有一个二维数组 A[m][ n]，假设 个空间，问 676(10)，每个元素占 制表示。 .688 D. 二叉树 A[2][2]存放位置在 (10)存放在什么位置？脚注(10)表示用10进 A[0][0] 存放位置在644(10), A[3][3] .678 C C ） 。 B. A 5.树最适合用来表示( A.有序数据元素 C.元素之间具有分支层次关系的数据 二叉树的第k 层的结点数最多为(D ). k .2 -1 B.2K+1 C.2K-1 若有18个元素的有序表存放在一维数组 6. A 7. 692 D . 696 D. 无序数据元素 乙间无联系的数 据 元素之 f k-1 D. 2 A[19]中，第一个元素放 A[1]中，现进行二 分查找，则查找 A : 3 ]的比较序列的下标依次为 (C ) A. 1 , 2, 3 B. 9 , 5, 2, 3 C. 9 , 5, 3 D. 9 , 4, 2, 3 对n 个记录的文件进行快速排序，所需要的辅助存储空间大致为 D. O 8. A. O (1) B. O (n ) C. O (1og 2n ) D. O (n2) 9. 对于线性表(7, 34, 55, 25, 64, 46, 20, 10)进行散列存储时，若选用 H (K ) =K %9作为散列函数，则散列地址为 1的元素有(D )个， A . 1 B . 2 C . 3 10. 设有6个结点的无向图，该图至少应有 ( A.5 B.6 C.7 D.8 二、填空题(每空 1分，共26分) 1.通常从四个方面评价算法的质量： _ 高效率 _______ 和―强壮性 _______ 。 1. 一个算法的时间复杂度为(n 3 +nlog 2n+14n)/ n 2 ,其数量级表示为 —o(n) ____________________ 。 2. 假定一棵树的广义表表示为 A (C, D (E , F , G , H( I , J )),则树中所含的结点数为 __________ 个，树的深度为 ____________ ，树的度为 ___________ 。 .4 条边才能确保是一个连通图。 正确性 易读性数据结构习题解答
数据结构试题及答案(免费)
数据结构题集c语言版答案严蔚敏吴伟民[1]
数据结构题集与答案
数据结构试题及答案
数据结构习题集
数据结构习题与答案
结构设计常用数据
数据结构习题集(积分)
数据结构题集答案复习过程
结构设计经验的总结
数据结构习题集答案解析_清华大学版
【结构设计】钢筋混凝土结构设计经验数据分享
数据结构试题及答案
数据结构习题集
严蔚敏数据结构题集(C语言版)完整答案.doc
【结构设计】结构工程师十年设计经验总结
十套数据结构试题与答案
相关主题
文本预览