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

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

（1）反转一个链表。循环算法。 List reverse(List n) { if(!n) //判断链表是否为空，为空即退出。 { return n; } list cur = n.next; //保存头结点的下个结点 list pre = n; //保存头结点 list tmp; 8

pre.next = null; //头结点的指针指空，转换后变尾结点 while ( NULL != cur.next ) //循环直到cur.next为空 { tmp = cur; //实现如图10.3—图10.5所示 tmp.next = pre pre = tmp; cur = cur.next; } return tmp; //f返回头指针 }

（2）反转一个链表。递归算法。 List *reverse( List *oldList, List *newHead = NULL ) { List *next = oldList-> next; //记录上次翻转后的链表 oldList-> next = newHead; //将当前结点插入到翻转后链表的开头 newHead = oldList; //递归处理剩余的链表 return ( next==NULL )? newHead: reverse( t, newHead ); } 说明：循环算法就是图10.2—图10.5的移动过程，比较好理解和想到。递归算法的设计虽有一点难度，但是理解了循环算法，再设计递归算法就简单多了。

面试题 21：简述队列和栈的异同 队列和栈都是线性存储结构，但是两者的插入和删除数据的操作不同，队列是“先进先出”，栈是“后进先出”。

注意：区别栈区和堆区。堆区的存取是“顺序随意”，而栈区是“后进先出”。栈由编译器自动分配释放 ，存放函数的参数值，局部变量的值等。其操作方式类似于数据结构中的栈。堆一般由程序员分配释放， 若程序员不释放，程序结束时可能由OS回收。分配方式类似于链表。

它与本题中的堆和栈是两回事。堆栈只是一种数据结构，而堆区和栈区是程序的不同内存存储区域。 面试题22：能否用两个栈实现一个队列的功能

结点结构体： typedef struct node { int data; node *next; }node,*LinkStack; 创建空栈： LinkStack CreateNULLStack( LinkStack &S) { S = (LinkStack)malloc( sizeof( node ) ); //申请新结点 if( NULL == S) { printf(“Fail to malloc a new node.\n”); 9

return NULL; } S->data = 0; //初始化新结点 S->next = NULL; return S; }

栈的插入函数： LinkStack Push( LinkStack &S, int data) { if( NULL == S) //检验栈 { printf(“There no node in stack!”); return NULL; } LinkStack p = NULL; p = (LinkStack)malloc( sizeof( node ) ); //申请新结点 if( NULL == p) { printf(“Fail to malloc a new node.\n”); return S; } if( NULL == S->next) { p->next = NULL; } else { p->next = S->next; } p->data = data; //初始化新结点 S->next = p; //插入新结点 return S; } 出栈函数： node Pop( LinkStack &S) { node temp; temp.data = 0; temp.next = NULL; if( NULL == S) //检验栈 { printf(“There no node in stack!”); return temp; } temp = *S; 10

if( S->next == NULL ) { printf(“The stack is NULL,can’t pop!\n”); return temp; } LinkStack p = S ->next; //节点出栈 S->next = S->next->next; temp = *p; free( p ); p = NULL; return temp; } 双栈实现队列的入队函数： LinkStack StackToQueuPush( LinkStack &S, int data) { node n; LinkStack S1 = NULL; CreateNULLStack( S1 ); //创建空栈 while( NULL != S->next ) //S出栈入S1 { n = Pop( S ); Push( S1, n.data ); } Push( S1, data ); //新结点入栈 while( NULL != S1->next ) //S1出栈入S { n = Pop( S1 ); Push( S, n.data ); } return S; }

说明：用两个栈能够实现一个队列的功能，那用两个队列能否实现一个队列的功能呢？结果是否定的，因为栈是先进后出，将两个栈连在一起，就是先进先出。而队列是

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