欢迎来到天天文库
浏览记录
ID:5619735
大小:87.50 KB
页数:9页
时间:2017-12-20
《数据结构算法复习题》由会员上传分享,免费在线阅读,更多相关内容在教育资源-天天文库。
1、1.统计单链表HL中节点的值等于给定值X的节点数intCountX(LNode*HL,ElemTypex) {inti=0;LNode*p=HL;//i为计数器 while(p!=NULL) {if(P->data==x)i++; p=p->next; }//while,出循环时i中的值即为x结点个数 returni; }//CountX2.设有一组初始记录关键字序列(K1,K2,…,Kn),要求设计一个算法能够在O(n)的时间复杂度内将线性表划分成两部分,其中左半部分的每个关键字均小于Ki,右半
2、部分的每个关键字均大于等于Ki。voidquickpass(intr[],ints,intt){inti=s,j=t,x=r[s];while(ix)j=j-1;if(i3、,*q;intt;if(head==04、5、head->next==0)return;elsefor(q=head,p=head->next;p!=0;p=q->next){for(s=head;s!=q->next;s=s->next)if(s->data>p->data)break;if(s==q->next)q=p;else{q->next=p->next;p->next=s->next;s->next=p;t=p->data;p->data=s->data;s->data=t;}}}4.设计6、在顺序有序表中实现二分查找的算法。structrecord{intkey;intothers;};intbisearch(structrecordr[],intk){intlow=0,mid,high=n-1;while(low<=high){mid=(low+high)/2;if(r[mid].key==k)return(mid+1);elseif(r[mid].key>k)high=mid-1;elselow=mid+1;}return(0);}1.栈和队列的共同特点是()。A.只允许在端点处7、插入和删除元素B.都是先进后出C.都是先进先出D.没有共同点2.用链接方式存储的队列,在进行插入运算时().A.仅修改头指针 B.头、尾指针都要修改C.仅修改尾指针D.头、尾指针可能都要修改3.以下数据结构中哪一个是非线性结构?()A.队列 B.栈C.线性表D.二叉树4.设有一个二维数组A[m][n],假设A[0][0]存放位置在644(10),A[2][2]存放位置在676(10),每个元素占一个空间,问A[3][3](10)存放在什么位置?脚注(10)表示用10进制表示。A.688B.6788、C.692D.6965.树最适合用来表示()。A.有序数据元素B.无序数据元素C.元素之间具有分支层次关系的数据D.元素之间无联系的数据6.二叉树的第k层的结点数最多为().A.2k-1B.2K+1C.2K-1 D.2k-17.若有18个元素的有序表存放在一维数组A[19]中,第一个元素放A[1]中,现进行二分查找,则查找A[3]的比较序列的下标依次为()A.1,2,3B.9,5,2,3C.9,5,3D.9,4,2,38.对n个记录的文件进行快速排序,所需要的辅助存储空间大致为A.O(1) 9、B.O(n) C.O(1og2n)D.O(n2)1.对于线性表(7,34,55,25,64,46,20,10)进行散列存储时,若选用H(K)=K%9作为散列函数,则散列地址为1的元素有()个,A.1B.2C.3D.42.设有6个结点的无向图,该图至少应有()条边才能确保是一个连通图。A.5B.6C.7D.8下面程序的时间复杂为()for(i=1,s=0;i<=n;i++){t=1;for(j=1;j<=i;j++)t=t*j;s=s+t;}(A)O(n)(B)O(n2)(C)O(n3)(D)O(10、n4)3.设指针变量p指向单链表中结点A,若删除单链表中结点A,则需要修改指针的操作序列为()。(A)q=p->next;p->data=q->data;p->next=q->next;free(q);(B)q=p->next;q->data=p->data;p->next=q->next;free(q);(C)q=p->next;p->next=q->next;free(q);(D)q=p->next;p->data=q->data;free(q);4.设有n个待排序的记录关键字
3、,*q;intt;if(head==0
4、
5、head->next==0)return;elsefor(q=head,p=head->next;p!=0;p=q->next){for(s=head;s!=q->next;s=s->next)if(s->data>p->data)break;if(s==q->next)q=p;else{q->next=p->next;p->next=s->next;s->next=p;t=p->data;p->data=s->data;s->data=t;}}}4.设计
6、在顺序有序表中实现二分查找的算法。structrecord{intkey;intothers;};intbisearch(structrecordr[],intk){intlow=0,mid,high=n-1;while(low<=high){mid=(low+high)/2;if(r[mid].key==k)return(mid+1);elseif(r[mid].key>k)high=mid-1;elselow=mid+1;}return(0);}1.栈和队列的共同特点是()。A.只允许在端点处
7、插入和删除元素B.都是先进后出C.都是先进先出D.没有共同点2.用链接方式存储的队列,在进行插入运算时().A.仅修改头指针 B.头、尾指针都要修改C.仅修改尾指针D.头、尾指针可能都要修改3.以下数据结构中哪一个是非线性结构?()A.队列 B.栈C.线性表D.二叉树4.设有一个二维数组A[m][n],假设A[0][0]存放位置在644(10),A[2][2]存放位置在676(10),每个元素占一个空间,问A[3][3](10)存放在什么位置?脚注(10)表示用10进制表示。A.688B.678
8、C.692D.6965.树最适合用来表示()。A.有序数据元素B.无序数据元素C.元素之间具有分支层次关系的数据D.元素之间无联系的数据6.二叉树的第k层的结点数最多为().A.2k-1B.2K+1C.2K-1 D.2k-17.若有18个元素的有序表存放在一维数组A[19]中,第一个元素放A[1]中,现进行二分查找,则查找A[3]的比较序列的下标依次为()A.1,2,3B.9,5,2,3C.9,5,3D.9,4,2,38.对n个记录的文件进行快速排序,所需要的辅助存储空间大致为A.O(1)
9、B.O(n) C.O(1og2n)D.O(n2)1.对于线性表(7,34,55,25,64,46,20,10)进行散列存储时,若选用H(K)=K%9作为散列函数,则散列地址为1的元素有()个,A.1B.2C.3D.42.设有6个结点的无向图,该图至少应有()条边才能确保是一个连通图。A.5B.6C.7D.8下面程序的时间复杂为()for(i=1,s=0;i<=n;i++){t=1;for(j=1;j<=i;j++)t=t*j;s=s+t;}(A)O(n)(B)O(n2)(C)O(n3)(D)O(
10、n4)3.设指针变量p指向单链表中结点A,若删除单链表中结点A,则需要修改指针的操作序列为()。(A)q=p->next;p->data=q->data;p->next=q->next;free(q);(B)q=p->next;q->data=p->data;p->next=q->next;free(q);(C)q=p->next;p->next=q->next;free(q);(D)q=p->next;p->data=q->data;free(q);4.设有n个待排序的记录关键字
此文档下载收益归作者所有