数据结构方面的笔试题.doc

《数据结构方面的笔试题.doc》由会员分享，可在线阅读，更多相关《数据结构方面的笔试题.doc（17页珍藏版）》请在得力文库 - 分享文档赚钱的网站上搜索。

1、1.打开注册表编辑器定位到：HKEY_LOCAL_MACHINE|SOFTWARE|Microsoft|Windows|CurrentVersion|Uninstall，并在 Uninstall 中建立一个名为 KB 的子键。（如果已经存在则无需建立）2.修改 KB 子键的“默认”值，将其值设置为：This Key is required to STOP Windows Update from prompting for an install。然后关闭注册表编辑器并重新启动 Windows。3.重新启动 Windows 后，再次打开注册表编辑器，定位到：HKEY_LOCAL_MACHINE|S

2、OFTWARE|Microsoft|Updates|Windows XP|SPX（其中 SPX 的 X 是数字，如果你的系统是 Windows XP SP2，则 X 是 3；如果是 Windows XP SP1，则 X 是 2），把这个注册表项中的 KB 子键删除。然后关闭注册表编辑器并重新启动 Windows。典型的约瑟夫环问题。原问题比你的问题要复杂一点。我以前写的程序：1.用数组。# include stdio.h# define SIZE 100main() int m,n,i; int arraySIZE; printf(约瑟夫环求解,当前设置最大人数为%d.n,SIZE); pri

3、ntf(报数上限:n); scanf(%d,&m); printf(总人数为:n); scanf(%d,&n); for(i=0;in;i+) printf(第%d人的密码为:,i+1); scanf(%d,&arrayi); joseph(array,m,n);int joseph(a,m,n)int a,m,n; int bSIZE; /*计录编号数组.*/ int i; /*计数器.*/ int flag=0; int code; /*删取人的号码.*/ int sum=n; /*现存人数.*/ int point=0; /*当前报数人的位置.*/ int num=m; for(i=0;

4、in;i+) /*计录数组.*/ bi=i+1; while(sum!=0) /*当人数不为零时继续循环.*/ for(i=1;i=sum) /*当前报数位置超过最后一人时从第一人报起.*/ point=1; else point+; num=apoint-1; /*取密码.*/ code=bpoint-1; /*取号码.*/ for(i=point;inum); printf(密码:); scanf(%d,&p2-secret); p1=(struct player *)malloc(LEN); p2-next=p1; while(p2-num!=0); p-next=head; free(

5、p1);void delete(struct player *head,int m) int i; struct player *p,*q; int sum; p=head; sum=m; while(n!=0) for(i=1;inext; printf(%d,p-num); sum=p-secret; q-next=p-next; p=p-next; n=n-1; 题目：有n个人围成一圈，顺序排号。从第一个人开始报数（从1到3报数），凡报到3的人退出圈子，问最后留下的是原来第几号的那位。1. 程序分析：2.程序源代码：#define nmax 50main()int i,k,m,n,num

6、nmax,*p;printf(please input the total of numbers:);scanf(%d,&n);p=num;for(i=0;in;i+)*(p+i)=i+1;i=0;k=0;m=0;while(m next!=NULL)/*输出新建单链表后的各元素*/ printf(%d,p- next -data); p=p- next; printf(n); h= inverse(h); /*调用nzlb（逆置链表）函数*/ while(h- next!=NULL)/*输出逆置后的单链表各元素*/ printf(%d,h- next -data); h=h- next; g

7、etch(); /*调用getch函数，不知道什么意思的自己查查！*/ slink * creatslink() /*新建链表函数*/ slink *h,*l,*a; int i; h=( slink *)malloc(sizeof(slink); /*创建头结点*/ h- next =NULL; a=h; for(i=0;idata=i; a- next =l; a=a- next; a- next =NULL; return h; slink * inverse (slink *h) /*逆置链表函数*/ slink *p,*q; p=h- next; h- next =NULL; whi

8、le(p!=NULL) q=p; p=p- next; q- next =h- next; h- next =q; return h; 单链表逆置算法单链表逆置算法struct nodeint num;struct node *next;struct node* reverse(struct node *head)/head 链表头结点struct node *p,*temp1,*temp2; if(head=NULL_) return head; /|head-next=NULLp=head-next;head-next=NULL;while(_) /p!=NULL或ptemp1=head;

9、_; /head=p;temp2=p;p=p-next;_; /temp2-next=temp1;或head-next=temp1;/Match while statenmentreturn head; /返回逆置后的链表的头结点 struct nodeint num;struct node *next;struct node* reverse(struct node *head)/head 链表头结点struct node *p,*temp1,*temp2; if(head=NULL|head-next=NULL) return head; p=head-next;head-next=NUL

10、L;while(p!=NULL或p)temp1=head;head=p; temp2=p;p=p-next;temp2-next=temp1;或head-next=temp1; /Match while statenmentreturn head; /返回逆置后的链表的头结点 最大子列和 n的阶乘中有多少个0 10进制to2进制 单链表逆置 判断链表中是否有环 文件中有多少行#ifndef MYLIST_H#define MYLIST_H#include struct listnodeint value;listnode *next;listnode ( int num ): value (n

11、um), next (NULL);class Mylistpublic:Mylist ();Mylist ();void Insert ( int value ) ;std:string GetEntireList ();void Reverse ();private:listnode *head;#endif/-#include Mylist.husing namespace std;Mylist:Mylist ()head = NULL;Mylist:Mylist()if ( head != NULL )listnode *temp = head ;while ( head != NULL

12、 )temp = head-next;delete head;head = temp;void Mylist:Insert ( int value )if ( head = NULL )head = new listnode ( 0 );listnode *curnode = new listnode ( value );listnode *temp = head;while ( temp-next != NULL ) temp = temp-next;temp-next = curnode;string Mylist:GetEntireList ()string str = ;listnod

13、e *temp = head-next ;while ( temp != NULL )str += temp-value + 0 ;str += ;temp = temp-next;return str;void Mylist:Reverse ()if ( head = NULL | head-next = NULL )return;listnode *end = head;while ( end-next != NULL )end = end-next;listnode *curnode = head-next;while ( curnode != end )/ 将curnode从链表中删除

14、head-next = curnode-next;/将curnode插入到end后面curnode-next = end-next;end-next = curnode;curnode = head-next;/ 判断链表中是否存在着环bool Mylist:HasaCycle ()listnode *itr1 = NULL;listnode *itr2 = NULL;/ 如果链表为空则返回falseif ( head = NULL | head != NULL & ( head-next = NULL ) )return false;itr1 = head-next;itr2 = itr1-

15、next;if ( itr2 = NULL )return false;/ 如果head-next指向了head ，或者itr1-head 指向了itr1，或者itr1-next指向了head,有环if ( itr1 = head | itr2 = itr1 | itr2 = head )return true;/ head - itr1 - itr2 - * while ( itr1 != NULL & itr2 != NULL & itr2-next != NULL )if ( itr1 = itr2 | itr2-next = itr1 )return true;itr1 = itr1-

16、next;itr2 = itr2-next-next;return false;/=/ test。cpp#include #include #include #include #include #include Mylist.husing namespace std;/=/ 获得data。txt文件中有多少行int GetTotalLineCount ()ifstream ifs;ifs.open ( data.txt, ios:in );int count = 1 ;/string p;/while ( getline( ifs, p ) ) +count; char ch;while (

17、ifs.get( ch ) ) if ( ch = n)+count;ifs.close();return count;/=/计算正整数num的阶乘中有多少个0const int FIVE = 5;/ 得到不大于 num的5的最大次方，如 num = 5 时返回 1， 26 时返回 2int LowerNearestPow ( int num )int powoffive = 1;while ( pow ( FIVE, powoffive ) 0 )zerocount += num / pow ( FIVE, lowernearestpow ) ; -lowernearestpow;retur

18、n zerocount;/=/ 将10进制正整数num转化为2进制数const int TWO = 2 ;string DecimalToBin ( unsigned int num )if ( num = 0 )return 0;string binform = ;while ( num 0 )binform.insert ( binform.begin(), num % TWO + 0 );num /= TWO ;return binform;/=/ 求一个整数数组的最大子列和 int MaxSubArraySum ( int *array, int size )int sum = 0;w

19、hile ( size = 0 )if ( arraysize 0 )sum += array size ;else if ( arraysize 0 )if ( sum = 0 )sum = arraysize;/ end of else-size;/ end of while return sum;/=void main ()/int count = GetTotalLineCount ();/cout count endl; /while ( 1 )/cout 请输入一个数，本程序将计算这个数的阶乘中有多少个0： num ;/cout GetZerosofXFactorial ( num

20、 ) endl;/while ( 1 )/cout 请输入一个正整数，本程序将计算这个数的二进制形式： num ;/cout DecimalToBin ( num ) endl;/Mylist intlist;/for ( int i=0; i8; +i )/intlist.Insert ( i );/string str = intlist.GetEntireList ();/cout 在逆置之前链表内容为： str endl;/intlist.Reverse();/str = intlist.GetEntireList ();/cout 在逆置之后链表内容为： str endl;/int

21、sum = -1, -2, 0, -4, -6, -1; / -1/ 1, 2, -1, -4, 6, 1; / 10/int size = sizeof( sum ) / sizeof(int) - 1;/cout MaxSubArraySum ( sum , size ) endl;又n个人围成一圈,顺序排号.从第一个人开始报数(从1到m报数),凡报到m的人退出圈子,问最后留下的是原来第几号?链表:#include#includetypedef struct nodeint info;struct node *next;node *tbuildhlink(int n)/*带头节点的尾插法*

22、/node *head,*s,*p2;int i=1;head=(node *)malloc(sizeof(node);p2=head;while(iinfo=i;p2-next=s;p2=s;i+;if(p2)p2-next=head;return(head); void Display(struct node* head)node *p;p=head-next;if(!p)printf(nthe hlink is empty!);else printf(nthe value of the hlink is:n);while(p!=head) printf(%d-,p-info);p=p-n

23、ext;printf(n);int delete_node(struct node *head,intn,int m)int count=1,sum=n;struct node *p,*pre;pre=head;p=pre-next;while(sum1)if(p=head)p=p-next;if(countnext;count+;if(count=m)if(p=head)p=p-next;printf(第%d个人出列.n,p-info);pre-next=p-next;free(p);p=pre-next;count=1;sum-;return(pre-info);int main()node *head;int n,m;printf(输入n,m:);scanf(%d%d,&n,&m);head=tbuildhlink(n);Display(head);printf(最后剩下第%d个.n,delete_node(head,n,m);return(0);