c++数据结构面试题（附答案）

c++数据结构面试题（附答案）

1.设一组初始关键字记录关键字为(20,15,14,18,21,36,40,10)，则一轮冒泡排序结束后的结果为?

答案：

升序：15,14,18,20,21,36,10,40
   降序：20,15,18,21,36,40,14,10

2.写一个函数实现选择排序？ 答案：

void choiceSort(int n[], int size)
{
for (int i = 0; i < size - 1; i++)
{
	int k = i; //表示当前的最小值下标
	for (int j = i + 1; j < size; j++)
	{
		if (n[j] < n[k])
		{
			k = j;
		}
	}
	if (k != i)
	{
		swap(n[k], n[i]);
	}
}
}

3.实现删除顺序表vector中的所有偶数？ 答案：

vector<int> v;
vector<int>::iterator it = v.begin();
for(;it != v.end();)
{
if(*it % 2 == 0)
{
it = v.erase(it);
}else
{
++it;
}
}

4.list的erase函数的参数和返回值分别为什么类型和表示什么含义？ 答案：

参数：指向要删除元素的迭代器
返回值：删除元素的下一个元素的迭代器

5.在一个单链表中,已知q所指结点是p所指结点的前驱结点,若在q和p之间插入s结点的代码? 答案：

q->pnext = s;
s->pnext = p;

6.在双向链表的p所指结点之后插入s所指结点的代码？ 答案：

s->pfront = p;
s->pnext = p->pnext;
p->pnext->pfront = s;
p->pnext = s;

7.实现队列的翻转？ 答案：

queue<int> q;
stack<int> s;
for(int i = 1;i <= 10;i++)
{
    q.push(i);
}
while(!q.empty())
{
    int num = q.front();
    s.push(num);
    q.pop();
}

8.list和vector的区别？ 答案：

1.list：内存不一定连续，方便添加删除，不方便随机访问。
2.vector:内存连续，不方便添加删除，方便随机访问。

short* * ptr;
int(*ptr)[3];
  char*(*ptr)[4];
int* ptr[3];
short* ptr[3][4];

ptr = ptr + 1.分别写出上面ptr类型时偏移时1的大小为多少个字节？ 答案：

4/12/16/4/16

10.链表结点声明如下： struct ListNode { int m_nKey; ListNode * m_pNext; }; 实现查找单链表中的倒数第k个结点（k > 0）(10分)

ListNode * getKthNode(ListNode * pHead, unsigned int k); 答案：

ListNode * getKthNode(ListNode * pHead, unsigned int k) // 函数名前面的R代表反向
{
if (k == 0 || pHead == NULL) // 这里k的计数是从1开始的，若k为0或链表为空返回NULL
	return NULL;

	ListNode * pAhead = pHead;
	ListNode * pBehind = pHead;
	while (k > 1 && pAhead != NULL) // 前面的指针先走到正向第k个结点
	{
			pAhead = pAhead->m_pNext;
			k--;
	}
if ( pAhead == NULL)     // 结点个数小于k，返回NULL
	return NULL;
while (pAhead->m_pNext != NULL)  // 前后两个指针一起向前走，直到前面的指针指向最后一个结点
{
	pBehind = pBehind->m_pNext;
	pAhead = pAhead->m_pNext;
}
return pBehind;  // 后面的指针所指结点就是倒数第k个结点
}