C++数据结构面试题

1. /*节点数据结构*/  
2. struct link{  
3.     int data;  
4.     link * next;  
5. };  
6.   
7. /* 
8. *判断是否有环的方法 
9. * 
10. *参数来头节点的指针 
11. */  
12. bool isLoop(link * head){  
13.     //p1步长为1；p2步长为2  
14.     link* p1 = head,*p2 = head;  
15.       
16.     //如果只有一个节点或两个节点，直接return false  
17.     if(head == NULL || head->next == NULL){  
18.         return false;  
19.     }  
20.       
21.     //循环前进，直到p2走到NULL或p2追上p1  
22.     do{  
23.         p1 = p1->next;  
24.         p2 = p2->next->next;  
25.     }while(p2 && p2->next && p1!=p2);  
26.   
27.     //如果有环  
28.     if(p1 == p2){  
29.         return true;  
30.     else  
31.         return false;  
32. }  

1. /*节点数据结构*/  
2. struct linka{  
3.     int data;  
4.     link * next;  
5. };  
6.   
7. /* 
8. *反转 
9. * 
10. *参数：头节点的指针的引用 
11. */  
12. bool reverse(link * &head){  
13.     //只有一个节点，即不用反转，直接返回  
14.     if(head == NULL)  
15.         return;  
16.   
17.     //定义3个辅助指针,pre指向当前要反转的节点的前一个节点；cur为当前要反转的节点；ne指向当前反转的节点的下一个节点  
18.     linka * pre,*cur,*ne;  
19.     //初始化指针  
20.     pre = head;  
21.     cur = head->next;  
22.     //循环，直到cur为NULL  
23.     while(cur){  
24.         ne = cur->next;  
25.         cur->next = pre;  
26.         pre = cur;  
27.         cur = ne;  
28.     }  
29.       
30.     //反转到最后，设置头节点指针  
31.     head->next = NULL;  
32.     head = pre;  
33. }  

1. /*节点数据结构*/  
2. struct linka{  
3.     int data;  
4.     link * next;  
5. };  
6.   
7. /* 
8. *反转 
9. * 
10. *参数：头节点的指针的引用 
11. */  
12. linka * reverse(linka * p,link * &head){  
13.     if(p == NULL || p->next == NULL){  
14.         head = p;  
15.         return p;  
16.     }else {  
17.         linka* tmp = reverse(p->next,head);  
18.         tmp->next = p;  
19.         return p;     
20.     }  
21. }  

1. <pre name="code" class="cpp">#include <iostream>  
2. using namespace std;  
3.   
4. /* 单链表节点 */  
5. struct node{  
6.     int value;  
7.     node* next;  
8. };  
9.   
10. /* 给单链表添加节点 */  
11. void insertNode(node* head, int value){  
12.     node* p = head->next;  
13.     if ( p == NULL ){  
14.        p = new node;  
15.        p->value = value;  
16.        p->next = NULL;  
17.        head->next = p;  
18.        return;  
19.     }  
20.   
21.     while ( p->next != NULL ){  
22.        p = p->next;  
23.     }  
24.     node* tmp = new node;  
25.     tmp->value = value;  
26.     tmp->next = NULL;  
27.     p->next = tmp;  
28. }  
29.   
30. /* 遍历输出链表节点 */  
31. void print(node* head){  
32.     node* p = head->next;  
33.     while ( p != NULL ){  
34.        cout << p->value << " ";  
35.        p = p->next;  
36.     }  
37.     cout << endl;  
38. }  
39.   
40.   
41. /* 下面实现不使用任何库函数， 利用交换的方法在原空间实现整体有序。 方法是先确定哪一个链表 
42. 的第一个节点的值小，把这个链表的头结点作为合并后链表的头结点，然后比较2个有序链表的当前节点 
43. 的值，如果代表最后合并链表的值小，则不用交换，否则把两个值交换，最后合并链表始终保持两个值中 
44. 的小值。另一个链表由于交换了一个元素，当前元素可能影响该链表的有序递增，对其进行调整使其保持 
45. 递增有序，然后重复上述动作，直到一个链表遍历结束，然后把剩余的链表连接起来就行。*/  
46.   
47. /* 调整链表的第一个节点，使其变成递增有序 */  
48. void chg2sort(node* head, node* &p){  
49.   
50.     if (head->next == NULL ){ //没有节点，直接返回  
51.         return;  
52.     }  
53.   
54.     node* s = head;  
55.     while ( s->next != p ){ //s指向p的前一个节点  
56.        s = s->next;  
57.     }  
58.   
59.     //下面的一段找到第一个大于p节点值的节点  
60.     node* q = p;  
61.     node* r = q;  
62.       
63.     while ( q != NULL ){  
64.       
65.        if ( q->value <= p->value ){  
66.         r = q; //r始终指向q的前一个节点  
67.         q = q->next;  
68.        }else {  
69.         break;  
70.        }  
71.     }  
72.   
73.     //下面调整指针，其实可以统一写出来，为了阅读清晰把q为NULL和非NULL分开写出来  
74.       
75.     if ( q == NULL ){  
76.        r->next = p;  
77.        s->next = p->next;  
78.        p->next = NULL;  
79.     }else if ( q != NULL ){  
80.        s->next = p->next;  
81.        r->next = p;  
82.        p->next = q;  
83.     }  
84.       
85.     //由于链表进行了调换，当前链表指针也需要改变  
86.     p = s->next;  
87. }  
88.   
89.   
90. /* 两个有序链表进行合并 */  
91. node* merge(node* head1, node* head2){  
92.     node* head; //合并后的头指针  
93.     node* p = head1->next;  
94.     node* q = head2->next;  
95.   
96.     //有一个链表为空的情况，直接返回另一个链表  
97.     if ( p == NULL ){  
98.        head = head2;  
99.        return head;  
100.     }else if ( q == NULL ){  
101.        head = head1;  
102.        return head;  
103.     }  
104.   
105.     //两个都不为空,先确定哪个链表作为合并后的链表  
106.     if ( (p != NULL) && (q != NULL) ){  
107.        if ( p->value < q->value ){  
108.         head = head1;  
109.        }else{  
110.         head = head2;  
111.        }  
112.     }  
113.   
114.     node* p_prior; //始终指向p节点的前一个节点  
115.     node* q_prior;  
116.   
117.     while ( (p != NULL) && (q != NULL) ){  
118.        if ( p ->value < q->value ){  
119.             if ( head == head1 ){//如果链表1的值小于链表2的值，链表1的指针向下指  
120.                  p_prior = p;  
121.                  p = p->next;  
122.             }else if ( head == head2 ){  
123.                  //进行当前节点值的交换  
124.                  int tmp = p->value;  
125.                  p->value = q->value;  
126.                  q->value = tmp;  
127.                  chg2sort(head1, p); //交换元素后的调整  
128.                  q_prior = q;  
129.                  q = q->next;  
130.             }  
131.        }else if ( p->value == q->value ){//链表1的值等于链表2时，两链表指针都向下指  
132.             p_prior = p;  
133.             p = p->next;  
134.             q_prior = q;  
135.             q = q->next;  
136.        }else if ( p->value > q->value ){  
137.             if ( head == head1 ){//如果链表1的值大于链表2的值，交接两节点的值后，排序链表2后，再下指  
138.                  int tmp = p->value;  
139.                  p->value = q->value;  
140.                  q->value = tmp;  
141.                  chg2sort(head2, q);  
142.                  p_prior = p;  
143.                  p = p->next;  
144.             }else if ( head == head2 ){  
145.                  q_prior = q;  
146.                  q = q->next;  
147.             }  
148.        }  
149.     }  
150.   
151.     if ( p != NULL ){  
152.        q_prior->next = p;  
153.     }  
154.   
155.     if ( q != NULL ){  
156.        p_prior->next = q;  
157.     }  
158.   
159.     return head;  
160. }  
161.   
162. int main(){  
163.     /* 建立有序链表A */  
164.     int a[5] = {1, 5, 8, 10, 20};  
165.     node* headA = new node;  
166.     headA->next = NULL;  
167.       
168.     for (int i = 0; i < 5; ++i){  
169.        insertNode(headA, a[i]);  
170.     }  
171.       
172.     print(headA);  
173.   
174.     /* 建立有序链表B */  
175.     int b[3] = {3, 4, 9};  
176.     node* headB = new node;  
177.     headB->next = NULL;  
178.       
179.     for (int i = 0; i < 3; ++i){  
180.        insertNode(headB, b[i]);  
181.     }  
182.       
183.     print(headB);  
184.   
185.     head = merge(headA, headB);  
186.     print(head);  
187.       
188.     return 0;  
189. }  

1. Node* mergeAction(Node* head1, Node* head2){  
2. //两个链表的合并操作   
3.         Node* head=(Node*)malloc(sizeof(Node));   
4.         Node* q=head; //q指向合并后的链表的最后一个  
5.         while(head1 && head2){ //  
6.                 if(head1->data<=head2->data){   
7.                         Node* p=(Node*)malloc(sizeof(Node)); //p是新生节点的指针  
8.                         p->data=head1->data;   
9.                         p->next=NULL;   
10.                         q->next=p;   
11.                         q=q->next;   
12.                         head1=head1->next;   
13.                 }   
14.                 else if(head1->data > head2->data){   
15.                         Node* p=(Node*)malloc(sizeof(Node));   
16.                         p->data=head2->data;   
17.                         p->next=NULL;   
18.                         q->next=p;   
19.                         q=q->next;   
20.                         head2=head2->next;   
21.                 }   
22.         }   
23.         return head->next;   
24. }  

1. bool findcommon2(int a[], int size1,int b[],int size2){  
2.     int i = 0, j = 0;  
3.       
4.     while(i<size1 && j<size2){  
5.         if(a[i]==b[j])  
6.             return true;  
7.           
8.         if(a[i]>b[j])  
9.             j++;//j标记b数组  
10.           
11.         if(a[i]<b[j])  
12.             i++;//i标记a数组  
13.     }  
14.       
15.     return false;  
16. }  

1. char * reverse_word(const char *str){  
2.     int len = strlen(str);  
3.     char * restr = new char[len+1];  
4.       
5.     strcpy(restr,str);  
6.       
7.     //首尾交换，i是首的索引 j是尾的索引  
8.     for(int i=0,j=len-1;i<j;i++,j--){  
9.         char tmp = restr[i];  
10.         restr[i] = restr[j];  
11.         restr[j] = tmp;  
12.     }  
13.       
14.     //再把每个单词反转  
15.     int i,j,k = 0;  
16.     while(k<len){  
17.         i=j=k;  
18.         while(restr[j]!=‘ ‘ && restr[j]!=‘\0‘)  
19.             j++;//j为空格的索引  
20.           
21.         k = j+1;//k为  
22.         j--;  
23.           
24.         //反转单词  
25.         for(;i<j;i++,j--){  
26.             char tmp = restr[i];  
27.             restr[i] = restr[j];  
28.             restr[j] = tmp;  
29.         }  
30.     }  
31.       
32.     return restr;  
33. }  

1. #include <stack>  
2. using namespace std;  
3.   
4. //reverse the string ‘s1‘ ,the substring ‘token‘  
5. const char * reverse(const char * s1, const char * token){  
6.     assert(s1 && token);  
7.       
8.     stack<char> stack1;  
9.       
10.     const char * ptoken = token, *head = s1, *rear =s1;  
11.       
12.     while(*head !=‘‘){  
13.         while(*head !=‘‘ && *ptoken == *head){  
14.             ptoken++;  
15.             head++;  
16.         }  
17.           
18.         if(*ptoken==‘‘){  
19.             const char *p;  
20.               
21.             for(p=head-1;p>=rear;p--){  
22.                 stark1.push(*p);  
23.             }  
24.               
25.             ptoken = token;  
26.             rear = head;  
27.         }else{  
28.             stack1.push(*rear);  
29.             head = ++rear;  
30.             ptoken = token;  
31.         }  
32.     }  
33.       
34.     char * returnV = new char[strlen(s1)+1];  
35.     int i=0;  
36.       
37.     while(!stack1.empty()){  
38.         returnV[i++] = stack1.top();  
39.         stack1.top();  
40.     }  
41.       
42.     returnV[i]="";  
43.     return returnV;  
44. } 

     

1.    在一个单链表中p所指结点之前插入一个s (值为e)所指结点时，可执行如下操作：
q=head;
while (q->next!=p)   q=q->next;
s= new   Node; s->data=e;
q->next=     ; //填空
s->next=     ; //填空


2.    线性表的顺序存储结构是一种 的存储结构，而链式存储结构是一种___的存储结构。
A．随机存取     B．索引存取 C．顺序存取 D．散列存取


3.    线性表若采用链式存储结构时，要求内存中可用存储单元的地址___。
A. 必须是连续的    B. 部分地址必须是连续的
C. 一定是不连续的 D. 连续或不连续都可以

4.    在一个单链表中，已知q所指结点是p所指结点的前驱结点，若在q和p之间插入s结点，则执行____。
A. s->next=p->next;   p->next=s; B. p->next=s->next;   s->next=p;
C. q->next=s; s->next=p;        D. p->next=s; s->next=q;


5.    在一个单链表中，若p所指结点不是最后结点，在p之后插入s所指结点，则执行____。
A.   s->next=p;   p->next=s;    B. s->next=p->next;   p->next=s;
C.   s->next=p->next;   p=s;    C. p->next=s;   s->next=p;


6.    在一个单链表中，若删除p所指结点的后续结点，则执行____。
A. p->next= p->next->next； B. p= p->next;   p->next= p->next->next；
C. p->next= p->next;       D. p= p->next->next；

7.    链表不具备的特点是 ____ 。
A 可随机访问任何一个元素              B 插入、删除操作不需要移动元素
C 无需事先估计存储空间大小              D 所需存储空间与线性表长度成正比

8.    以下关于线性表的说法不正确的是 。  
A 线性表中的数据元素可以是数字、字符、记录等不同类型。  
B 线性表中包含的数据元素个数不是任意的。  
C 线性表中的每个结点都有且只有一个直接前趋和直接后继。  
D 存在这样的线性表：表中各结点都没有直接前趋和直接后继。

9.    在一个长度为n的顺序表中删除第i个元素，要移动 个元素。如果要在第i个元素前插入一个元素，要后移( )个元素。 N-I N-I+1




--------------------------------------------------------------------------------------------------
1.    栈操作数据的原则是( )，队列操作数据的原则是 ( ) 。

2.    在栈中，可进行插入和删除操作的一端称    。

3.    栈和队列都是____结构；对于栈只能在____插入和删除元素；对于队列只能在____插入元素和____删除元素。

4.    栈结构通常采用的两种存储结构是    和    。

5.    计算机在运行递归程序时，要用到    提供的栈。

6.    一个栈的入栈序列a，b，c，d，e，则栈的不可能的输出序列是____。
A. edcba B. decba C. dceab D. abcde

7.    一个队列的数据入列序列是1，2，3，4，则队列的出队时输出序列是____ 。
A. 4，3，2，1        B. 1，2，3，4 C. 1，4，3，2        D. 3，2，4，1


8.    判断一个表达式中左右括号是否匹配，采用 ____ 实现较为方便。
A 线性表的顺序存储        B 队列        C 线性表的链式存储        D 栈

9.    栈与一般线性表区别主要在方面    。
A 元素个数        B 元素类型        C 逻辑结构        D 插入、删除元素的位置

10.    “假上溢”现象会出现在     中。  
A   循环队列             B 队列             C 链队列             D 顺序队列

11.    在一个链队中，假设F和R分别是队首和队尾指针，则删除一个结点的运算是 。  
A   R=F->next;       B   R=R->next;       C   F=F->next;             D   F=R->next;

12.    表达式a*(b+c)-d的后缀表达式是 。
A．abcd*+-             B. abc+*d-             C. abc*+d-             D. -+*abcd