部分c、c++笔试题集锦(11)

网上收集的c/c++的笔试题,将部分整理成节,上传后大家方便。不是很全,但是可以作为笔试的参考吧。

什么问题。但是在复杂的数据元素序列组合中，只是根据单一的某一个关键值排序，直接选择排序则不保证其稳定性，这是直接选择排序的一个弱点。

面试题27：编程实现堆排序

堆排序编程实现： #include <stdio.h> 14 void createHeep(int ARRAY[],int sPoint, int Len) //生成大根堆 { while( ( 2 * sPoint + 1 ) < Len ) { int mPoint = 2 * sPoint + 1 ; if( ( 2 * sPoint + 2 ) < Len ) { if(ARRAY[ 2 * sPoint + 1 ] < ARRAY[ 2 * sPoint + 2 ] ) { mPoint = 2*sPoint+2; } } if(ARRAY[ sPoint ] < ARRAY[ mPoint ]) //堆被破坏，需要重新调整 { int tmpData= ARRAY[ sPoint ]; //交换sPoint与mPoint的数据 ARRAY[ sPoint ] = ARRAY[ mPoint ]; ARRAY[ mPoint ] = tmpData; sPoint = mPoint ; } else { break; //堆未破坏，不再需要调整 } } return; } void heepSort( int ARRAY[], int Len ) //堆排序 { int i=0; for ( i = ( Len / 2 – 1 ); i >= 0; i– ) //将Hr[0，Lenght-1]建成大根堆 { createHeep(ARRAY, i, Len); } for ( i = Len – 1; i > 0; i– ) { int tmpData = ARRAY[0]; //与最后一个记录交换 ARRAY[0] = ARRAY; ARRAY = tmpData; createHeep( ARRAY, 0, i ); //将H.r[0..i]重新调整为大根堆 } return; } int main( void ) 15

{ int ARRAY[] ={ 5, 4, 7, 3, 9, 1, 6, 8, 2}; printf(“Before sorted:\n”); //打印排序前数组内容 for ( int i = 0; i < 9; i++ ) { printf(“%d “, ARRAY); } printf(“\n”); heepSort( ARRAY, 9 ); //堆排序 printf(“After sorted:\n”); //打印排序后数组内容 for( i = 0; i < 9; i++ ) { printf( “%d “, ARRAY ); } printf( “\n” ); return 0; }

说明：堆排序，虽然实现复杂，但是非常的实用。另外读者可是自己设计实现小堆排序的算法。虽然和大堆排序的实现过程相似，但是却可以加深对堆排序的记忆和理解。 面试题28：编程实现基数排序 #include <stdio.h> #include <malloc.h> #define LEN 8 typedef struct node //队列结点 { int data; struct node * next; }node,*QueueNode; typedef struct Queue //队列 { QueueNode front; QueueNode rear; }Queue,*QueueLink; QueueLink CreateNullQueue( QueueLink &Q) //创建空队列 { Q = NULL; Q = ( QueueLink )malloc( sizeof( Queue ) ); if( NULL == Q ) { printf(“Fail to malloc null queue!\n”); return NULL; } 16

Q->front = ( QueueNode )malloc( sizeof( node ) ); Q->rear = ( QueueNode )malloc( sizeof( node ) ); if( NULL == Q->front || NULL == Q->rear ) { printf(“Fail to malloc a new queue’s fornt or rear!\n”); return NULL; } Q->rear = NULL; Q->front->next= Q->rear; return Q; } int lenData( node data[], int len) //计算队列中各结点的数据的最大位数 { int m = 0; int temp = 0; int d; for( int i = 0; i < len; i++) { d = data.data; while( d > 0) { d /= 10; temp ++; } if( temp > m ) { m = temp; } temp = 0; } return m; } QueueLink Push( QueueLink &Q , node node ) //将数据压入队列 { QueueNode p1,p; p =( QueueNode )malloc( sizeof( node ) ); if( NULL == p ) { printf(“Fail to malloc a new node!\n”); return NULL; } p1 = Q->front; while(p1->next != NULL) { p1 = p1->next; } p->data = node.data; p1->next = p; p->next = Q->rear; 17

return NULL; } node Pop( QueueLink &Q) //数据出队列 { node temp; temp.data = 0; temp.next = NULL; QueueNode p; p = Q->front->next; if( p != Q->rear ) { temp = *p; Q->front->next = p->next; free( p ); p = NULL; } return temp; } int IsEmpty( QueueLink Q)

百度搜索“77cn”或“免费范文网”即可找到本站免费阅读全部范文。收藏本站方便下次阅读，免费范文网，提供经典小说教育文库部分c、c++笔试题集锦(11)在线全文阅读。