第8章数组类型习题及答案

C程序设计(第四版)谭浩强_课后习题答案第8章第8章善于利用指针2208.1指针是什么2208.2指针变量2228.2.1使用指针变量的例子2228.2.2怎样定义指针变量2238.2.3怎样引用指针变量2248.2.4指针变量作为函数参数2268.3通过指针引用数组2308.3.1数组元素的指针2308.3.2在引用数组元素时指针的运算2318.3.3通过指针引用数组元素2338.3.4用数组名作函数参数2378.3.5通过指针引用多维数组2458.4通过指针引用字符串2558.4.1字符串的引用方式2558.4.2字符指针作函数参数2598.4.3使用字符指针变量和字符数组的比较2638.5指向函数的指针2668.5.1什么是函数指针2668.5.2用函数指针变量调用函数2668.5.3怎样定义和使用指向函数的指针变量2688.5.4用指向函数的指针作函数参数2708.6返回指针值的函数2748.7指针数组和多重指针2778.7.1什么是指针数组2778.7.2指向指针数据的指针2808.7.3指针数组作main函数的形参2828.8动态内存分配与指向它的指针变量2858.8.1什么是内存的动态分配2858.8.2怎样建立内存的动态分配2858.8.3void指针类型2878.9有关指针的小结288习题2918-1#include <stdio.h>int main(){ void swap(int *p1,int *p2);int n1,n2,n3;int *p1,*p2,*p3;printf("input three integer n1,n2,n3:");scanf("%d,%d,%d",&n1,&n2,&n3);p1=&n1;p2=&n2;p3=&n3;if(n1>n2) swap(p1,p2);if(n1>n3) swap(p1,p3);if(n2>n3) swap(p2,p3);printf("Now,the order is:%d,%d,%d\n",n1,n2,n3); return 0;}void swap(int *p1,int *p2){int p;p=*p1; *p1=*p2; *p2=p;}#include <stdio.h>#include <string.h>int main(){void swap(char *,char *);char str1[20],str2[20],str3[20];printf("input three line:\n");gets(str1);gets(str2);gets(str3);if(strcmp(str1,str2)>0) swap(str1,str2);if(strcmp(str1,str3)>0) swap(str1,str3);if(strcmp(str2,str3)>0) swap(str2,str3);printf("Now,the order is:\n");printf("%s\n%s\n%s\n",str1,str2,str3);return 0;}void swap(char *p1,char *p2){char p[20];strcpy(p,p1);strcpy(p1,p2);strcpy(p2,p);}8-3#include <stdio.h>int main(){ void input(int *);void max_min_value(int *);void output(int *);int number[10];input(number);max_min_value(number);output(number);return 0;}void input(int *number){int i;printf("input 10 numbers:");for (i=0;i<10;i++)scanf("%d",&number[i]);}void max_min_value(int *number){ int *max,*min,*p,temp;max=min=number;for (p=number+1;p<number+10;p++)if (*p>*max) max=p;else if (*p<*min) min=p;temp=number[0];number[0]=*min;*min=temp;if(max==number) max=min;temp=number[9];number[9]=*max;*max=temp; }void output(int *number){int *p;printf("Now,they are: ");for (p=number;p<number+10;p++)printf("%d ",*p);printf("\n");}8-4#include <stdio.h>int main(){void move(int [20],int,int);int number[20],n,m,i;printf("how many numbers?");scanf("%d",&n);printf("input %d numbers:\n",n);for (i=0;i<n;i++)scanf("%d",&number[i]);printf("how many place you want move?"); scanf("%d",&m);move(number,n,m);printf("Now,they are:\n");for (i=0;i<n;i++)printf("%d ",number[i]);printf("\n");return 0;}void move(int array[20],int n,int m){int *p,array_end;array_end=*(array+n-1);for (p=array+n-1;p>array;p--)*p=*(p-1);*array=array_end;m--;if (m>0) move(array,n,m);}8-5#include <stdio.h>int main(){int i,k,m,n,num[50],*p;printf("\ninput number of person: n="); scanf("%d",&n);p=num;for (i=0;i<n;i++)*(p+i)=i+1;i=0;k=0;m=0;while (m<n-1){if (*(p+i)!=0) k++;if (k==3){*(p+i)=0;k=0;m++;}i++;if (i==n) i=0;}while(*p==0) p++;printf("The last one is NO.%d\n",*p); return 0;}8-6#include <stdio.h>int main(){int length(char *p);int len;char str[20];printf("input string: ");scanf("%s",str);len=length(str);printf("The length of string is %d.\n",len); return 0;}int length(char *p){int n;n=0;while (*p!='\0'){n++;p++;}return(n);}8-7#include <stdio.h>#include <string.h>int main(){void copystr(char *,char *,int);int m;char str1[20],str2[20];printf("input string:");gets(str1);printf("which character that begin to copy?"); scanf("%d",&m);if (strlen(str1)<m)printf("input error!");else{copystr(str1,str2,m);printf("result:%s\n",str2);}return 0;}void copystr(char *p1,char *p2,int m){int n;n=0;while (n<m-1){n++;p1++;}while (*p1!='\0'){*p2=*p1;p1++;p2++;}*p2='\0';}8-8#include <stdio.h>int main(){int upper=0,lower=0,digit=0,space=0,other=0,i=0; char *p,s[20];printf("input string: ");while ((s[i]=getchar())!='\n') i++;p=&s[0];while (*p!='\n'){if (('A'<=*p) && (*p<='Z'))++upper;else if (('a'<=*p) && (*p<='z'))++lower;else if (*p==' ')++space;else if ((*p<='9') && (*p>='0'))++digit;else++other;p++;}printf("upper case:%d lower case:%d",upper,lower);printf(" space:%d digit:%d other:%d\n",space,digit,other); return 0;}8-9#include <stdio.h>int main(){void move(int *pointer);int a[3][3],*p,i;printf("input matrix:\n");for (i=0;i<3;i++)scanf("%d %d %d",&a[i][0],&a[i][1],&a[i][2]);p=&a[0][0];move(p);printf("Now,matrix:\n");for (i=0;i<3;i++)printf("%d %d %d\n",a[i][0],a[i][1],a[i][2]);return 0;}void move(int *pointer){int i,j,t;for (i=0;i<3;i++)for (j=i;j<3;j++){t=*(pointer+3*i+j);*(pointer+3*i+j)=*(pointer+3*j+i);*(pointer+3*j+i)=t;}}8-10-1#include <stdio.h>int main(){void change(int *p);int a[5][5],*p,i,j;printf("input matrix:\n");for (i=0;i<5;i++)for (j=0;j<5;j++)scanf("%d",&a[i][j]);p=&a[0][0];change(p);printf("Now,matrix:\n");for (i=0;i<5;i++){for (j=0;j<5;j++)printf("%d ",a[i][j]);printf("\n");}return 0;}void change(int *p){int i,j,temp;int *pmax,*pmin;pmax=p;pmin=p;for (i=0;i<5;i++)for (j=i;j<5;j++){if (*pmax<*(p+5*i+j)) pmax=p+5*i+j;if (*pmin>*(p+5*i+j)) pmin=p+5*i+j;}temp=*(p+12);*(p+12)=*pmax;*pmax=temp;temp=*p;*p=*pmin;*pmin=temp;pmin=p+1;for (i=0;i<5;i++)for (j=0;j<5;j++)if (((p+5*i+j)!=p) && (*pmin>*(p+5*i+j))) pmin=p+5*i+j;temp=*pmin;*pmin=*(p+4);*(p+4)=temp;pmin=p+1;for (i=0;i<5;i++)for (j=0;j<5;j++)if (((p+5*i+j)!=(p+4))&&((p+5*i+j)!=p)&&(*pmin>*(p+5*i+j)))pmin=p+5*i+j;temp=*pmin;*pmin=*(p+20);*(p+20)=temp;pmin=p+1;for (i=0;i<5;i++)for (j=0;j<5;j++)if (((p+5*i+j)!=p) && ((p+5*i+j)!=(p+4)) && ((p+5*i+j)!=(p+20)) && (*pmin>*(p+5*i+j)))pmin=p+5*i+j;temp=*pmin;*pmin=*(p+24);*(p+24)=temp;}8-10-2#include <stdio.h>int main(){void change(int *p);int a[5][5],*p,i,j;printf("input matrix:\n");for (i=0;i<5;i++)for (j=0;j<5;j++)scanf("%d",&a[i][j]);p=&a[0][0];change(p);printf("Now,matrix:\n");for (i=0;i<5;i++){for (j=0;j<5;j++)printf("%d ",a[i][j]);printf("\n");}return 0;}void change(int *p) //交换函数{int i,j,temp;int *pmax,*pmin;pmax=p;pmin=p;for (i=0;i<5;i++) //找最大值和最小值的地址,并赋给pmax,pmin for (j=i;j<5;j++){if (*pmax<*(p+5*i+j)) pmax=p+5*i+j;if (*pmin>*(p+5*i+j)) pmin=p+5*i+j;}temp=*(p+12); //将最大值与中心元素互换*(p+12)=*pmax;*pmax=temp;temp=*p; //将最小值与左上角元素互换*p=*pmin;*pmin=temp;pmin=p+1;//将a[0][1]的地址赋给pmin，从该位置开始找最小的元素for (i=0;i<5;i++) //找第二最小值的地址赋给pminfor (j=0;j<5;j++){if(i==0 && j==0) continue;if (*pmin > *(p+5*i+j)) pmin=p+5*i+j;}temp=*pmin; //将第二最小值与右上角元素互换*pmin=*(p+4);*(p+4)=temp;pmin=p+1;for (i=0;i<5;i++) //找第三最小值的地址赋给pminfor (j=0;j<5;j++){if((i==0 && j==0) ||(i==0 && j==4)) continue;if(*pmin>*(p+5*i+j)) pmin=p+5*i+j;}temp=*pmin; // 将第三最小值与左下角元素互换*pmin=*(p+20);*(p+20)=temp;pmin=p+1;for (i=0;i<5;i++) // 找第四最小值的地址赋给pminfor (j=0;j<5;j++){if ((i==0 && j==0) ||(i==0 && j==4)||(i==4 && j==0)) continue;if (*pmin>*(p+5*i+j)) pmin=p+5*i+j;}temp=*pmin; //将第四最小值与右下角元素互换*pmin=*(p+24);*(p+24)=temp;}8-11-1#include <stdio.h>#include <string.h>int main(){void sort(char s[][6]);int i;char str[10][6];printf("input 10 strings:\n");for (i=0;i<10;i++)scanf("%s",str[i]);sort(str);printf("Now,the sequence is:\n"); for (i=0;i<10;i++)printf("%s\n",str[i]);return 0;}void sort(char s[10][6]){int i,j;char *p,temp[10];p=temp;for (i=0;i<9;i++)for (j=0;j<9-i;j++)if (strcmp(s[j],s[j+1])>0){strcpy(p,s[j]);strcpy(s[j],s[+j+1]);strcpy(s[j+1],p);}}8-11-2#include <stdio.h>#include <string.h>int main(){void sort(char (*p)[6]);int i;char str[10][6];char (*p)[6];printf("input 10 strings:\n");for (i=0;i<10;i++)scanf("%s",str[i]);p=str;sort(p);printf("Now,the sequence is:\n"); for (i=0;i<10;i++)printf("%s\n",str[i]);return 0;}void sort(char (*s)[6]){int i,j;char temp[6],*t=temp;for (i=0;i<9;i++)for (j=0;j<9-i;j++)if (strcmp(s[j],s[j+1])>0){strcpy(t,s[j]);strcpy(s[j],s[+j+1]);strcpy(s[j+1],t);}}8-12#include <stdio.h>#include <string.h>int main(){void sort(char *[]);int i;char *p[10],str[10][20];for (i=0;i<10;i++)p[i]=str[i];printf("input 10 strings:\n");for (i=0;i<10;i++)scanf("%s",p[i]);sort(p);printf("Now,the sequence is:\n"); for (i=0;i<10;i++)printf("%s\n",p[i]);return 0;}void sort(char *s[]){int i,j;char *temp;for (i=0;i<9;i++)for (j=0;j<9-i;j++)if (strcmp(*(s+j),*(s+j+1))>0){temp=*(s+j);*(s+j)=*(s+j+1);*(s+j+1)=temp;}}8-13#include<stdio.h>#include<math.h>int main(){float integral(float(*)(float),float,float,int);//对integarl函数的声明float fsin(float); //对fsin函数的声明float fcos(float); //对fcos函数的声明float fexp(float); //对fexp函数的声明float a1,b1,a2,b2,a3,b3,c,(*p)(float);int n=20;printf("input a1,b1:");scanf("%f,%f",&a1,&b1);printf("input a2,b2:");scanf("%f,%f",&a2,&b2);printf("input a3,b3:");scanf("%f,%f",&a3,&b3);p=fsin;c=integral(p,a1,b1,n);printf("The integral of sin(x) is:%f\n",c);p=fcos;c=integral(p,a2,b2,n);printf("The integral of cos(x) is:%f\n",c);p=fexp;c=integral(p,a3,b3,n);printf("The integral of exp(x) is:%f\n",c);return 0;}float integral(float(*p)(float),float a,float b,int n){int i;float x,h,s;h=(b-a)/n;x=a;s=0;for(i=1;i<=n;i++){x=x+h;s=s+(*p)(x)*h;}return(s);}float fsin(float x){return sin(x);}float fcos(float x){return cos(x);}float fexp(float x){return exp(x);}8-14#include <stdio.h>int main(){void sort (char *p,int m);int i,n;char *p,num[20];printf("input n:");scanf("%d",&n);printf("please input these numbers:\n");for (i=0;i<n;i++)scanf("%d",&num[i]);p=&num[0];sort(p,n);printf("Now,the sequence is:\n");for (i=0;i<n;i++)printf("%d ",num[i]);printf("\n");return 0;}void sort (char *p,int m) // 将n个数逆序排列函数{int i;char temp, *p1,*p2;for (i=0;i<m/2;i++){p1=p+i;p2=p+(m-1-i);temp=*p1;*p1=*p2;*p2=temp;}}8-15#include <stdio.h>int main(){void avsco(float *,float *);void avcour1(char (*)[10],float *);void fali2(char course[5][10],int num[],float *pscore,float aver[4]); void good(char course[5][10],int num[4],float *pscore,float aver[4]); int i,j,*pnum,num[4];float score[4][5],aver[4],*pscore,*paver;char course[5][10],(*pcourse)[10];printf("input course:\n");pcourse=course;for (i=0;i<5;i++)scanf("%s",course[i]);printf("input NO. and scores:\n");printf("NO.");for (i=0;i<5;i++)printf(",%s",course[i]);printf("\n");pscore=&score[0][0];pnum=&num[0];for (i=0;i<4;i++){scanf("%d",pnum+i);for (j=0;j<5;j++)scanf("%f",pscore+5*i+j);}paver=&aver[0];printf("\n\n");avsco(pscore,paver); // 求出每个学生的平均成绩avcour1(pcourse,pscore); // 求出第一门课的平均成绩printf("\n\n");fali2(pcourse,pnum,pscore,paver); // 找出2门课不及格的学生printf("\n\n");good(pcourse,pnum,pscore,paver); // 找出成绩好的学生return 0;}void avsco(float *pscore,float *paver) // 求每个学生的平均成绩的函数{int i,j;float sum,average;for (i=0;i<4;i++){sum=0.0;for (j=0;j<5;j++)sum=sum+(*(pscore+5*i+j)); //累计每个学生的各科成绩average=sum/5; //计算平均成绩*(paver+i)=average;}}void avcour1(char (*pcourse)[10],float *pscore) // 求第一课程的平均成绩的函数{int i;float sum,average1;sum=0.0;for (i=0;i<4;i++)sum=sum+(*(pscore+5*i)); //累计每个学生的得分average1=sum/4; //计算平均成绩printf("course 1:%s average score:%7.2f\n",*pcourse,average1);}void fali2(char course[5][10],int num[],float *pscore,float aver[4])// 找两门以上课程不及格的学生的函数{int i,j,k,labe1;printf(" ==========Student who is fail in two courses======= \n"); printf("NO. ");for (i=0;i<5;i++)printf("%11s",course[i]);printf(" average\n");for (i=0;i<4;i++){labe1=0;for (j=0;j<5;j++)if (*(pscore+5*i+j)<60.0) labe1++;if (labe1>=2){printf("%d",num[i]);for (k=0;k<5;k++)printf("%11.2f",*(pscore+5*i+k));printf("%11.2f\n",aver[i]);}}}void good(char course[5][10],int num[4],float *pscore,float aver[4]) // 找成绩优秀学生(各门85以上或平均90分以上)的函数{int i,j,k,n;printf(" ======Students whose score is good======\n");printf("NO. ");for (i=0;i<5;i++)printf("%11s",course[i]);printf(" average\n");for (i=0;i<4;i++){n=0;for (j=0;j<5;j++)if (*(pscore+5*i+j)>85.0) n++;if ((n==5)||(aver[i]>=90)){printf("%d",num[i]);for (k=0;k<5;k++)printf("%11.2f",*(pscore+5*i+k));printf("%11.2f\n",aver[i]);}}}8-16#include <stdio.h>int main(){char str[50],*pstr;int i,j,k,m,e10,digit,ndigit,a[10],*pa;printf("input a string:\n");gets(str);pstr=&str[0]; /*字符指针pstr置于数组str 首地址*/pa=&a[0]; /*指针pa置于a数组首地址*/ndigit=0; /*ndigit代表有多少个整数*/i=0; /*代表字符串中的第几个字符*/j=0;while(*(pstr+i)!='\0'){if((*(pstr+i)>='0') && (*(pstr+i)<='9'))j++;else{if (j>0){digit=*(pstr+i-1)-48; /*将个数位赋予digit*/k=1;while (k<j) /*将含有两位以上数的其它位的数值累计于digit*/{e10=1;for (m=1;m<=k;m++)e10=e10*10; /*e10代表该位数所应乘的因子*/digit=digit+(*(pstr+i-1-k)-48)*e10; /*将该位数的数值\累加于digit*/k++; /*位数K自增*/}*pa=digit; /*将数值赋予数组a*/ndigit++;pa++; /*指针pa指向a数组下一元素*/j=0;}}i++;}if (j>0) /*以数字结尾字符串的最后一个数据*/ {digit=*(pstr+i-1)-48; /*将个数位赋予digit*/k=1;while (k<j) /* 将含有两位以上数的其它位的数值累加于digit*/{e10=1;for (m=1;m<=k;m++)e10=e10*10; /*e10代表位数所应乘的因子*/digit=digit+(*(pstr+i-1-k)-48)*e10; /*将该位数的数值累加于digit*/k++; /*位数K自增*/}*pa=digit; /*将数值赋予数组a*/ndigit++;j=0;}printf("There are %d numbers in this line, they are:\n",ndigit);j=0;pa=&a[0];for (j=0;j<ndigit;j++) /*打印数据*/printf("%d ",*(pa+j));printf("\n");return 0;}8-17#include<stdio.h>int main(){int strcmp(char *p1,char *p2);int m;char str1[20],str2[20],*p1,*p2;printf("input two strings:\n");scanf("%s",str1);scanf("%s",str2);p1=&str1[0];p2=&str2[0];m=strcmp(p1,p2);printf("result:%d,\n",m);return 0;}int strcmp(char *p1,char *p2) //两个字符串比较函数{int i;i=0;while(*(p1+i)==*(p2+i))if (*(p1+i++)=='\0') return(0); //相等时返回结果0return(*(p1+i)-*(p2+i)); //不等时返回结果为第一个不等字符ASCII码的差值}8-18#include <stdio.h>int main(){char *month_name[13]={"illegal month","January","February","March","April", "May","June","july","August","September","October", "November","December"};int n;printf("input month:\n");scanf("%d",&n);if ((n<=12) && (n>=1))printf("It is %s.\n",*(month_name+n));elseprintf("It is wrong.\n");return 0;}8-19-1#include <stdio.h>#define NEWSIZE 1000 //指定开辟存区的最大容量char newbuf[NEWSIZE]; //定义字符数组newbufchar *newp=newbuf; //定义指针变量newp，指向可存区的始端char *new(int n) //定义开辟存区的函数new,开辟存储区后返回指针{if (newp+n<=newbuf+NEWSIZE) // 开辟区未超过newbuf数组的大小{newp+=n; // newp指向存储区的末尾return(newp-n); // 返回一个指针,它指向存区的开始位置}elsereturn(NULL); // 当存区不够分配时,返回一个空指针}8-19-2#include <stdio.h>#define NEWSIZE 1000char newbuf[NEWSIZE];char *newp=newbuf;void free(char *p) //释放存区函数{if (p>=newbuf && p< newbuf + NEWSIZE)newp=p;}8-20#define LINEMAX 20 /*定义字符串的最大长度*/int main(){int i;char **p,*pstr[5],str[5][LINEMAX];for (i=0;i<5;i++)pstr[i]=str[i]; /*将第i个字符串的首地址赋予指针数组pstr 的第i个元素*/ printf("input 5 strings:\n");for (i=0;i<5;i++)scanf("%s",pstr[i]);p=pstr;sort(p);printf("strings sorted:\n");for (i=0;i<5;i++)printf("%s\n",pstr[i]);}sort(char **p) /*冒泡法对5个字符串排序函数*/{int i,j;char *temp;for (i=0;i<5;i++){for (j=i+1;j<5;j++){if (strcmp(*(p+i),*(p+j))>0) /*比较后交换字符串地址*/{temp=*(p+i);*(p+i)=*(p+j);*(p+j)=temp;}}}return 0;}8-21#include<stdio.h>int main(){void sort(int **p,int n);int i,n,data[20],**p,*pstr[20];printf("input n:\n");scanf("%d",&n);for (i=0;i<n;i++)pstr[i]=&data[i]; //将第i个整数的地址赋予指针数组pstr 的第i个元素printf("input %d integer numbers:",n);for (i=0;i<n;i++)scanf("%d",pstr[i]);p=pstr;sort(p,n);printf("Now,the sequence is:\n");for (i=0;i<n;i++)printf("%d ",*pstr[i]);printf("\n");return 0;}void sort(int **p,int n){int i,j,*temp;for (i=0;i<n-1;i++){for (j=i+1;j<n;j++){if (**(p+i)>**(p+j)) //比较后交换整数地址{temp=*(p+i);*(p+i)=*(p+j);*(p+j)=temp;}}}}。

第六~第八章基本概念练习题第6章数组一、选择题。

1. 以下对一维数组a的正确定义是：A)char a（10）；B) int a[]；C)int k＝5，a[k]；D）char a[3]={‘a’,’b’,’c’};2.以下能对一维数组a进行初始化的语句是: ( )A. int a[5]=(0,1,2,3,4,)B. int a(5)={}C. int a[3]={0,1,2}D. int a{5}={10*1}；3.在C语言中对一维整型数组的正确定义为。

A)int a(10); B)int n=10,a[n];C)int n;a[n]; D)#define N 10int a[N];4. 若二维数组a有m列，则在a[i][j]之前的元素个数为A. j*m+iB. i*m+jC. i*m+j-1D. i*m+j+1*5. 下列说法中错误的是A 构成数组的所有元素的数据类型必须是相同的B 用指针法引用数组元素允许数组元素的下标越界C 一维数组元素的下标依次是1、2、3……·D 定义数组时的长度可以是整型常量表达式6. 假定int类型变量占用两个字节，其有定义：int x[10]={0,2,4};，则数组x在内存中所占字节数是A) 3 B) 6 C) 10 D) 207.若有说明：int a[][3]={{1,2,3},{4,5},{6,7}}; 则数组a的第一维的大小为: ( )A. 2B. 3C. 4D.无确定值8.以下定义语句中，错误的是( )A) int a[]={1,2}; B) char *a;C) char s[10]=“test”; D) int n=5,a[n];9.下面程序段的输出结果是: ( )int i;、int x[3][3]={1,2,3,4,5,6,7,8,9};for (i=0;i<3;i++)printf("%d ",x[i][2-i]);A) 1 5 9 B) 1 4 7 C) 3 5 7 D) 3 6 9二．分析题。

数据结构C语言版第2版课后习题答案数据结构（C语言版）（第2版）课后习题答案李冬梅2015.3第1章绪论 0第2章线性表 (4)第3章栈和队列 (14)第4章串、数组和广义表 (27)第5章树和二叉树 (34)第6章图 (43)第7章查找 (55)第8章排序 (66)第1章绪论1•简述下列概念：数据、数据元素、数据项、数据对象、数据结构、逻辑结构、存储结构、抽象数据类型。

答案：数据：是客观事物的符号表示，指所有能输入到计算机中并被计算机程序处理的符号的总称。

如数学计算中用到的整数和实数，文本编辑所用到的字符串，多媒体程序处理的图形、图像、声音、动画等通过特殊编码定义后的数据。

数据元素：是数据的基本单位，在计算机中通常作为一个整体进行考虑和处理。

在有些情况下，数据元素也称为元素、结点、记录等。

数据元素用于完整地描述一个对象，如一个学生记录，树中棋盘的一个格局（状态）、图中的一个顶点等。

数据项：是组成数据元素的、有独立含义的、不可分割的最小单位。

例如，学生基本信息表中的学号、姓名、性别等都是数据项。

数据对象：是性质相同的数据元素的集合，是数据的一个子集。

例如：整数数据对象是集合N={0，± 1，±2，…}，字母字符数据对象是集合C={ ‘ A',' B',…，'b'，…，‘ z' }，学生基本信息表也可是一个数据对象。

数据结构：是相互之间存在一种或多种特定关系的数据元素的集合。

换句话说，数据结构是带“结构”的数据元素的集合，“结构”就是指数据元素之间存在的关系。

逻辑结构：从逻辑关系上描述数据，它与数据的存储无关，是独立于计算机的。

因此，数据的逻辑结构可以看作是从具体问题抽象出来的数学模型。

存储结构：数据对象在计算机中的存储表示，也称为物理结构。

抽象数据类型：由用户定义的，表示应用问题的数学模型，以及定义在这个模型上的一组操作的总称。

第8章习题参考答案1. 如果认为CPU等待设备的状态信号是处于非工作状态(即踏步等待),那么在下面几种主机与设备之间的数据传送中：A主机与设备是串行工作的；B 主机与设备是并行工作的，C 主程序与设备是并行运行的。

A .程序查询方式B .程序中断方式C . DMA方式2. 中断向量地址是B。

A•子程序入口地址 B •中断服务程序入口地址C•中断服务程序入口地址指示器 D •例行程序入口地址3•利用微型机制作了对输入数据进行采样处理的系统。

在该系统中，每抽取一个输入数据就要中断CPU 一次，中断处理程序接收采样的数据，将其放到主存的缓冲区内。

该中断处理需时x秒，另一方面缓冲区内每存储n个数据，主程序就将其取出进行处理，这种处理需时y秒。

因此该系统可以跟踪到每秒 A 次的中断请求。

A . n/ (n 次 + y)B . n/(x + y) n C. min(1 /x, n/y)4•采用DMA方式传送数据时，每传送一个数据就要占用一个 C 的时间。

A .指令周期B .机器周期C.存储周期 D .总线周期5. 通道的功能是：⑴ 控制外围设备，⑵ 组织外围设备和内存之间进行数据传输______ 。

按通道的工作方式分，通道有选择通道、数组多路通道和字节多路通道三种类型。

6. 在图8.9中，当CPU对设备B的中断请求进行服务时，如设备A提出请求，CPU能够响应吗？为什么？如果设备B 一提出请求总能立即得到服务，问怎样调整才能满足此要求？答：不能，因为A、B是同级别的中断。

要使设备B一提出请求总能立即得到服务，除非将B提高到上一级，并令IM3=0，即构成一个3级IR。

7. 在图& 9中，假定CPU取指并执行一条指令的时间为t1,保护现场需t2,恢复现场需t3,中断周期需t4，每个设备的设备服务时间为t A , t B,…，t G。

试计算只有设备A , D, G时的系统中断饱和时间。

答：依次处理设备A，设备D，设备G的时间为：T1 = t1+t2+t3+t4+t AT2 = t1+t2+t3+t4+t DT3 = t1+t2+t3+t4+t G总时间为T = T1+T2+T 3 = 3*( t 1+t2+t3+t4)+ t A + t D + t G&设某机有5级中断；L o, L1, L2, L3, L4，其中断响应优先次序为：L o最高，L1次之，L4最低。

第8章测试题及答案整理注：不保证全部正确，如有错误自行更改一.选择题1.假脱机技术是指。

A.联机同时外围设备操作技术B.对换技术和覆盖技术C.SPOOLing技术D.A和C2.缓冲技术中的缓冲池在中。

A.主存B.外存C.ROMD.寄存器3.引入缓冲的主要目的是。

A.改善CPU和I/O设备之间速度不匹配B.节省内存C.提高的CPU利用率D.高I/O设备的效率4.CPU输出数据的速度远远高于打印机的打印速度，为了解决这一矛盾，可采用。

A.并行技术B.通道技术C.缓冲技术D.虚存技术5.为了使多个进程能同时处理输入和输出，最好使用结构的缓冲技术。

A.缓冲池B.闭缓冲区环C.单缓冲区D.双缓冲区6.通过硬件和软件的功能扩充，把原来独立的设备改造成能为若干用户共享的设备，这种设备称为。

A.存储设备B.系统设备C.用户设备D.虚拟设备7.如果I/O设备与存储设备进行数据交换不经过CPU来完成，这种数据交换方式是。

A.程序查询B.中断C.DMAD.无条件存取8.中断发生后，应保留。

A.缓冲区指针B.关键寄存器内容C.被中断的程序D.页表9.下面的不属于设备管理机构。

A.JCBB.DCTC.COCTD.CHCT解析：JCB作业控制块、DCT设备控制表、COCT控制器控制表、CHCT通道控制表10.大多数低速设备都属于设备。

A.独享B.共享C.虚拟D.Spool11. 是直接存取的存储设备。

A.磁盘B.磁带C.打印机D.键盘显示终端12.以下叙述中正确的为。

A.在现代计算机中，只有I/O设备才是有效的中断源B.在中断处理过程中必须屏蔽中断C.同一用户所使用的I/O设备也可能并行工作D.Spooling是脱机I/O系统13. 是操作系统中采用的以空间换取时间的技术。

A.SpoolingB.虚存技术C.覆盖与交换D.通道解析：时间->空间（虚存）、空间->时间（Spooling）14.Spooling技术，实质是将转化为共享设备的技术。

第8章数组和广义表[能力要求]（1）计算机基础知识：掌握线性表的概念以及顺序表和链表的基本操作。

（2）分析问题：针对具体的问题，要能够运用线性表去进行分析，逐步找到解决问题的方法。

（3）具有概念化和抽象化能力：针对具体的应用和实际的问题，能够运用线性表对问题进行抽象，提取它的逻辑结构和存储结构。

（4）发现问题和表述问题：在具体的工程中，能够发现工程中涉及到顺序表和链表的问题，并能够明确表述。

（5）建模：在具体的工程中，能够使用线性表进行建模，设计合理的数据结构和相应的算法。

（6）解决方法和建议：在具体工程应用中，发现了关于线性表的问题，要能够解决问题，并提出合理的建议。

（7）定义功能、概念和结构：使用线性表这种逻辑结构处理一些具体问题，实现系统的功能。

（8）设计过程的分段与方法：采取不同的阶段去设计（概念设计、详细设计）一个具体的线性表的应用项目。

（9）软件实现过程：了解系统中各个模块中的关于线性表的设计；讨论算法（数据结构、控制流程、数据流程）；使用编程语言实施底层设计（编程）。

8.1知识点：数组的定义和顺序存储一、选择题1①常对数组进行的两种基本操作是（）。

A．建立与删除 B．索引和修改C．对数据元素的存取和修改D．查找与索引2①下面说法中，不正确的是（）。

A．数组是一种线性结构B．数组是一种定长的线性表结构C．除了插入与删除操作外，数组的基本操作还有存取、修改、检索和排序等D．数组的基本操作有存取、修改、检索和排序等，没有插入与删除操作3②数组A中，每个元素的长度为3个字节，行下标I从1到8，列下标J从1到10，从首地址SA开始连续存放在存储器内，该数组占用的字节数为（）。

A．80 B．100 C．240 D．2704②在二维数组A[9][10]中，每一个数组元素A[i][j] 占用3个存储空间，所有数组元素相继存放于一个连续的存储空间中，则存放该数组至少需要的存储空间是（）。

A． 80 B．100 C．240 D．2705②设有一个n*n的对称矩阵A，将其下三角部分按行存放在一个一维数组B中，A[0][0]存放于B[0]中，那么第I行的对角元素A[I][I]存放于B中（）处。

第8章习题参考答案1．如果认为CPU等待设备的状态信号是处于非工作状态(即踏步等待)，那么在下面几种主机与设备之间的数据传送中： A 主机与设备是串行工作的；B 主机与设备是并行工作的，C 主程序与设备是并行运行的。

A．程序查询方式B．程序中断方式C．DMA方式2．中断向量地址是 B 。

A．子程序入口地址B．中断服务程序入口地址C.中断服务程序入口地址指示器D．例行程序入口地址3．利用微型机制作了对输入数据进行采样处理的系统。

在该系统中，每抽取一个输入数据就要中断CPU一次，中断处理程序接收采样的数据，将其放到主存的缓冲区内。

该中断处理需时x秒，另一方面缓冲区内每存储n个数据，主程序就将其取出进行处理，这种处理需时y秒。

因此该系统可以跟踪到每秒 A 次的中断请求。

A．n／(n×x＋y) B．n／(x＋y)·n C．min(1／x，n／y)4．采用DMA方式传送数据时，每传送一个数据就要占用一个 C 的时间。

A．指令周期B．机器周期C．存储周期D．总线周期5．通道的功能是：(1) 控制外围设备，(2) 组织外围设备和内存之间进行数据传输。

按通道的工作方式分，通道有选择通道、数组多路通道和字节多路通道三种类型。

6．在图8.9中，当CPU对设备B的中断请求进行服务时，如设备A提出请求，CPU能够响应吗?为什么?如果设备B一提出请求总能立即得到服务，问怎样调整才能满足此要求? 答：不能，因为A、B是同级别的中断。

要使设备B一提出请求总能立即得到服务，除非将B提高到上一级，并令IM3=0，即构成一个3级IR。

7．在图8．9中，假定CPU取指并执行一条指令的时间为t1，保护现场需t2，恢复现场需t3，中断周期需t4，每个设备的设备服务时间为t A，t B，…，t G。

试计算只有设备A，D，G 时的系统中断饱和时间。

答：依次处理设备A，设备D，设备G的时间为：T1 =t1+t2+t3+t4+t AT2 = t1+t2+t3+t4+t DT3 = t1+t2+t3+t4+t G总时间为T = T1+T2+T3 = 3*( t1+t2+t3+t4)+ t A + t D + t G8．设某机有5级中断；L0，L1，L2，L3，L4，其中断响应优先次序为：L0最高，L1次之，L4最低。

第8章排序1．选择题（1）从未排序序列中依次取出元素与已排序序列中的元素进行比较，将其放入已排序序列的正确位置上的方法，这种排序方法称为（）。

A．归并排序B．冒泡排序C．插入排序D．选择排序（2）从未排序序列中挑选元素，并将其依次放入已排序序列（初始时为空）的一端的方法，称为（）。

A．归并排序B．冒泡排序C．插入排序D．选择排序（3）对n个不同的关键字由小到大进行冒泡排序，在下列（）情况下比较的次数最多。

A．从小到大排列好的B．从大到小排列好的C．元素无序D．元素基本有序（4）对n个不同的排序码进行冒泡排序，在元素无序的情况下比较的次数最多为（）。

A．n+1 B．n C．n-1 D．n(n-1)/2 （5）快速排序在下列（）情况下最易发挥其长处。

A．被排序的数据中含有多个相同排序码B．被排序的数据已基本有序C．被排序的数据完全无序D．被排序的数据中的最大值和最小值相差悬殊（6）对n个关键字作快速排序，在最坏情况下，算法的时间复杂度是（）。

A．O(n) B．O(n2)C．O(nlog2n) D．O(n3)（7）若一组记录的排序码为（46, 79，56，38，40，84），则利用快速排序的方法，以第一个记录为基准得到的一次划分结果为（）。

A．38，40，46，56，79，84 B．40，38，46，79，56，84C．40，38，46，56，79，84D．40，38，46，84，56，79 （8）下列关键字序列中，（）是堆。

A．16，72，31，23，94，53 B．94，23，31，72，16，53C．16，53，23，94，31，72 D．16，23，53，31，94，72（9）堆是一种（）排序。

A．插入B．选择C．交换D．归并（10）堆的形状是一棵（）。

A．二叉排序树B．满二叉树C．完全二叉树D．平衡二叉树（11）若一组记录的排序码为（46，79，56，38，40，84），则利用堆排序的方法建立的初始堆为（）。