数据结构算法复习题

《数据结构算法复习题》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

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(i

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个待排序的记录关键字