注意：此页面搜索的是所有试题
安阳师范学院-计算机应用技术-数据结构
算法的特征是什么？
一般情况下，算法中基本操作重复执行的的 某个函数f(n),算法的时间量度记作：T(n)=O(f(n))它表示随问题规模n的增大，算法执行时间的增长率和f(n)的增长率相同，称作算法的渐进时间复杂度，简称时间复杂度
链式存储结构的特点是借助_______来表示数据元素之间的逻辑关系。数据的存储结构是其逻辑结构在计算机中的___________。
如果某算法对于规模为n的问题的时间耗费为T（n）=3n3，在一台计算机上运行时间为t秒，则在另一台运行速度是其64倍的机器上，用同样的时间能解决的问题规模是原问题规模的________倍。称算法的时间复杂度为O(f(n))，其含义是指算法的执行时间和_______的数量级相同。
估算算法时间复杂度时考虑的问题规模通常是指算法求解问题的_________。若一个算法中的语句频度之和为T(n)=3720n+4nlogn，则算法的时间复杂度为________。
数据的逻辑结构在计算机存储器内的表示，称为数据的____________。当问题的规模n趋向无穷大时，算法执行时间T(n)的数量级被称为算法的________。
以下函数中，h是带头结点的双向循环链表的头指针。 (1)说明程序的功能； (2)当链表中结点数分别为1和6(不包括头结点)时，请写出程序中while循环体的执行次数。 int f(DListNode *h) { DListNode *p,*q; int j=1; p=h->next; q=h->prior; while(p!=q && p->prior!=q) if(p->data==q->data) { p=p->next; q=q->prior; } else j=0; return j; }
下列程序的功能是将所有小于0的元素移到全部大于等于0的元素之前。例如，有7个整数的原始序列为(x,x,-x,-x,x,x,-x)，变换后数组中保存的序列是(-x,-x,-x,x,x,x,x)。请在程序处填入合适的内容，使其成为完整的算法。 f30(int a［］，int n) { int k，m,temp； m= (1) ； while (a［m］<0 &&m<n) m= (2) ； k=m; while (k<n) { while(a［k］>=0&&k<n) k= (3) ； if(k<n) { temp=a［k］； a［k］=a［m］； a［m］= (4) ； m= (5) ； } } } (1) (2) (3) (4) (5)
已知线性表的存储结构为顺序表，阅读下列算法，并回答问题： （1）设线性表L=（21，-7，-8，19，0，-11，34，30，-10），写出执行f30(&L)后的L状态； （2）简述算法f30的功能。 void f30 (SeqList *L) { int i,j; for (i=j=0;i<L->length; i++) if(L->data[i]>=0){ if(i!=j)L->data[j]=L->data[i]; j++； } L->length=j; } (1) (2)
已知用有序链表存储整数集合的元素。阅读算法f30，并回答下列问题： （1）写出执行f30（a,b）的返回值，其中a和b分别为指向存储集合{2，4，5，7，9，12}和{2，4，5，7，9}的链表的头指针； （2）简述算法f30的功能； （3）写出算法f30的时间复杂度。 int f30(LinkList ha,LinkList hb) { //LinkList是带有头结点的单链表 //ha和hb分别为指向存储两个有序整数集合的链表的头指针 LinkList pa,pb; pa=ha->next; pb=hb->next; while(pa && pb && pa->data==pb->data) { pa=pa->next; pb=pb->next; } if(pa==NULL && pb==NULL) return 1; else return 0; } (1) (2) (3)
阅读下列算法，并回答问题： (1)设顺序表L=(3,7,11,14,20,51)，写出执行f30(&L,15)之后的L； (2)设顺序表L=(4,7,10,14,20,51)，写出执行f30(&L,10)之后的L； (3)简述算法的功能。 void f30(SeqList*L, DataType x) { int i =0, j; while (i<L->length && x>L->data［i］)i++; if(i<L->length && x==L->data［i］) { for(j=i+1;j<L->length;j++) L->data［j-1］=L->data［j］; L->length--; } else { for(j=L->length;j>i;j--) L->data［j］=L->data［j-1］; L->data［i］=x; L->length++; } } (1) (2) (3)
已知单链表的结点结构为 data next 下列算法对带头结点的单链表L进行简单选择 排序，使得L中的元素按值从小到大排列，请在空缺处填入合适的内容，使其成为完整的算法。 void SelectSort(LinkedList L) { LinkedList p,q,min; DataTypercd; p=_________(1) while(p!=NULL)( min=p q=p->next; while(q!=NULL)( if__________(2)min=q; q=q->next;) if______(3)( rcd=p->data; p->data=min->data; min->data=rcd;) ________; ) )
阅读下列程序 void f32(int A[],int n) { int i,j,m=l,t； for (i=0; i<n-l&&m; i++) { for (j=0； j<n； j++) printf(“%d ”,A[j])； printf(“＼n”); m=0： for (j=1; j<n-i; j++) if (A[j-1]>A[j]) { t=A[j-l]; A[j-1]=A[j]； A[j]=t； m=1； } } } 回答问题： 已知整型数组A[ ]={34,26,15,89,42}，写出执行函数调用f32(A,5)后的输出结果。
阅读下列算法，并回答下列问题： (1)该算法采用何种策略进行排序? (2)算法中R[n+1]的作用是什么? Typedef struct { KeyType key; infoType otherinfo; } nodeType; typedef nodeType SqList［MAXLEN］; void sort(SqList R,int n) { //n小于MAXLEN-1 int k;i; for(k=n-1;k>=1;k--) if(R[k].key>R[k+1].key) { R[n+1]=R[k]; for(i=k+1;R[i].key<R[n+1].key;i++) R[i-1]=R[i]; R[i-1]=R[n+1]; } }
已知顺序表的表结构定义如下： #define MAXLEN 100 typedef int KeyType; typedef struct { KeyType key; InfoType otherinfo; } NodeType； typedef NodeType SqList[MAXLEN]; 阅读下列程序。 Int f33(SqList R，NodeType X, int p, int q) { int m; if (p>q) return -1; m=(p+q)／2； if (R[m].key==X.key) return m; if (R[m].key>X.key) return f33(R,X,p,m-l); else return f33(R,X,m+l,q); } 请回答下列问题： (1)若有序的顺序表R的关键字序列为(2,5，13,26,55,80,105)，分别写出X.key=18和X.key=26时，执行函数调用f33(R,X,0,6)的函数返回值。 (2)简述算法f33的功能。
一般情况下，算法中基本操作重复执行的的 某个函数f(n),算法的时间量度记作：T(n)=O(f(n))它表示随问题规模n的增大，算法执行时间的增长率和f(n)的增长率相同，称作算法的渐进时间复杂度，简称时间复杂度
链式存储结构的特点是借助_______来表示数据元素之间的逻辑关系。数据的存储结构是其逻辑结构在计算机中的___________。
如果某算法对于规模为n的问题的时间耗费为T（n）=3n3，在一台计算机上运行时间为t秒，则在另一台运行速度是其64倍的机器上，用同样的时间能解决的问题规模是原问题规模的________倍。称算法的时间复杂度为O(f(n))，其含义是指算法的执行时间和_______的数量级相同。
估算算法时间复杂度时考虑的问题规模通常是指算法求解问题的_________。若一个算法中的语句频度之和为T(n)=3720n+4nlogn，则算法的时间复杂度为________。
数据的逻辑结构在计算机存储器内的表示，称为数据的____________。当问题的规模n趋向无穷大时，算法执行时间T(n)的数量级被称为算法的________。
以下函数中，h是带头结点的双向循环链表的头指针。 (1)说明程序的功能； (2)当链表中结点数分别为1和6(不包括头结点)时，请写出程序中while循环体的执行次数。 int f(DListNode *h) { DListNode *p,*q; int j=1; p=h->next; q=h->prior; while(p!=q && p->prior!=q) if(p->data==q->data) { p=p->next; q=q->prior; } else j=0; return j; }
下列程序的功能是将所有小于0的元素移到全部大于等于0的元素之前。例如，有7个整数的原始序列为(x,x,-x,-x,x,x,-x)，变换后数组中保存的序列是(-x,-x,-x,x,x,x,x)。请在程序处填入合适的内容，使其成为完整的算法。 f30(int a［］，int n) { int k，m,temp； m= (1) ； while (a［m］<0 &&m<n) m= (2) ； k=m; while (k<n) { while(a［k］>=0&&k<n) k= (3) ； if(k<n) { temp=a［k］； a［k］=a［m］； a［m］= (4) ； m= (5) ； } } } (1) (2) (3) (4) (5)
已知线性表的存储结构为顺序表，阅读下列算法，并回答问题： （1）设线性表L=（21，-7，-8，19，0，-11，34，30，-10），写出执行f30(&L)后的L状态； （2）简述算法f30的功能。 void f30 (SeqList *L) { int i,j; for (i=j=0;i<L->length; i++) if(L->data[i]>=0){ if(i!=j)L->data[j]=L->data[i]; j++； } L->length=j; } (1) (2)
已知用有序链表存储整数集合的元素。阅读算法f30，并回答下列问题： （1）写出执行f30（a,b）的返回值，其中a和b分别为指向存储集合{2，4，5，7，9，12}和{2，4，5，7，9}的链表的头指针； （2）简述算法f30的功能； （3）写出算法f30的时间复杂度。 int f30(LinkList ha,LinkList hb) { //LinkList是带有头结点的单链表 //ha和hb分别为指向存储两个有序整数集合的链表的头指针 LinkList pa,pb; pa=ha->next; pb=hb->next; while(pa && pb && pa->data==pb->data) { pa=pa->next; pb=pb->next; } if(pa==NULL && pb==NULL) return 1; else return 0; } (1) (2) (3)
阅读下列算法，并回答问题： (1)设顺序表L=(3,7,11,14,20,51)，写出执行f30(&L,15)之后的L； (2)设顺序表L=(4,7,10,14,20,51)，写出执行f30(&L,10)之后的L； (3)简述算法的功能。 void f30(SeqList*L, DataType x) { int i =0, j; while (i<L->length && x>L->data［i］)i++; if(i<L->length && x==L->data［i］) { for(j=i+1;j<L->length;j++) L->data［j-1］=L->data［j］; L->length--; } else { for(j=L->length;j>i;j--) L->data［j］=L->data［j-1］; L->data［i］=x; L->length++; } } (1) (2) (3)
已知单链表的结点结构为 data next 下列算法对带头结点的单链表L进行简单选择 排序，使得L中的元素按值从小到大排列，请在空缺处填入合适的内容，使其成为完整的算法。 void SelectSort(LinkedList L) { LinkedList p,q,min; DataTypercd; p=_________(1) while(p!=NULL)( min=p q=p->next; while(q!=NULL)( if__________(2)min=q; q=q->next;) if______(3)( rcd=p->data; p->data=min->data; min->data=rcd;) ________; ) )
阅读下列程序 void f32(int A[],int n) { int i,j,m=l,t； for (i=0; i<n-l&&m; i++) { for (j=0； j<n； j++) printf(“%d ”,A[j])； printf(“＼n”); m=0： for (j=1; j<n-i; j++) if (A[j-1]>A[j]) { t=A[j-l]; A[j-1]=A[j]； A[j]=t； m=1； } } } 回答问题： 已知整型数组A[ ]={34,26,15,89,42}，写出执行函数调用f32(A,5)后的输出结果。
阅读下列算法，并回答下列问题： (1)该算法采用何种策略进行排序? (2)算法中R[n+1]的作用是什么? Typedef struct { KeyType key; infoType otherinfo; } nodeType; typedef nodeType SqList［MAXLEN］; void sort(SqList R,int n) { //n小于MAXLEN-1 int k;i; for(k=n-1;k>=1;k--) if(R[k].key>R[k+1].key) { R[n+1]=R[k]; for(i=k+1;R[i].key<R[n+1].key;i++) R[i-1]=R[i]; R[i-1]=R[n+1]; } }
已知顺序表的表结构定义如下： #define MAXLEN 100 typedef int KeyType; typedef struct { KeyType key; InfoType otherinfo; } NodeType； typedef NodeType SqList[MAXLEN]; 阅读下列程序。 Int f33(SqList R，NodeType X, int p, int q) { int m; if (p>q) return -1; m=(p+q)／2； if (R[m].key==X.key) return m; if (R[m].key>X.key) return f33(R,X,p,m-l); else return f33(R,X,m+l,q); } 请回答下列问题： (1)若有序的顺序表R的关键字序列为(2,5，13,26,55,80,105)，分别写出X.key=18和X.key=26时，执行函数调用f33(R,X,0,6)的函数返回值。 (2)简述算法f33的功能。