STL-题目解析

下面有关vector和list的区别，描述错误的是( )

A.vector拥有一段连续的内存空间，因此支持随机存取，如果需要高效的随机存取,应该使用vector

B.list拥有一段不连续的内存空间，如果需要大量的插入和删除，应该使用list

C.vector::iterator支持“+”、“+=”、“<”等操作符

D.list::iterator则不支持“+”、“+=”、“<”等操作符运算，但是支持了[ ]运算符

解析：

A.如果想大量随机读取数据操作，vector是首选的容器

B.如果想大量的插入和删除数据，list效率较高，是首选

C.由于vector底层是连续空间，其迭代器就是相应类型的指针，所以支持对应的操作

D.list迭代器不支持[]运算符

以下代码实现了从表中删除重复项的功能，请选择其中空白行应填入的正确代码（）

template<typename T>
void removeDuplicates(list<T> &aList)
{T curValue;list<T>::iterator cur, p;cur = aList.begin();while (cur != aList.end()){curValue = *cur;//空白行 1p=++cur;while (p != aList.end()){if (*p == curValue){//空白行 2p == cur ? cur = p = aList.erase(p) : p = aList.erase(p);}else{p++;}}}
}
A. p=cur+1;aList.erase(p++);
B. p=++cur; p == cur ? cur = p = aList.erase(p) : p = aList.erase(p);
C. p=cur+1;aList.erase(p);
D. p=++cur;aList.erase(p);

解析：首先选B 选项

A.C 错误，迭代p需要迭代不重复节点的下一节点，p = cur+1;std::list 的迭代器是双向迭代器，它们不支持使用加法运算符（+）来直接前进到某个特定的位置。

B.D分析：D：中空白行2是当需要找到重复值时进行节点删除，当删除时当前迭代器会失效，因此需要将迭代器p往后迭代， p = aList.erase§这样迭代器才会向后移动，因为在erase()函数会删除指定迭代器位置上的元素，并返回指向被删除元素下一个位置的迭代器。如果删除的是容器中的最后一个元素，则返回的是容器末尾的迭代器，即end()迭代器。

B：p=++cur;这段代码中p和cur都指向curValue的下一个元素，故可能出现 *p == curValue，且 p == cur，当出现这种情况时，需要删除p指向的元素，并将cur和p向后移动，如果只是p = aList.erase§时，cur迭代器会失效。

以下程序输出结果为( )

int main()
{int ar[] = { 0,1, 2, 3, 4,  5, 6, 7, 8, 9 };int n = sizeof(ar) / sizeof(int);list<int> mylist(ar, ar+n); list<int>::iterator pos = find(mylist.begin(), mylist.end(), 5);reverse(mylist.begin(), pos);reverse(pos, mylist.end());list<int>::const_reverse_iterator crit = mylist.crbegin();while(crit != mylist.crend()){cout<<*crit<<" ";++crit;}cout<<endl;
}
A.4 3 2 1 0 5 6 7 8 9
B.0 1 2 3 4 9 8 7 6 5
C.5 6 7 8 9 0 1 2 3 4
D.5 6 7 8 9 4 3 2 1 0

分析:list::iterator pos = find(mylist.begin(), mylist.end(), 5); //找到5的位置

reverse(mylist.begin(), pos);//逆置0 1 2 3 4 为 4 3 2 1 0

reverse(pos, mylist.end()); //逆置5 6 7 8 9 为 9 8 7 6 5

逆置完成之后其数据为：4 3 2 1 0 9 8 7 6 5

list::const_reverse_iterator crit = mylist.crbegin(); //反向迭代器进行反向访问

while(crit != mylist.crend()){}

所以答案为:5 6 7 8 9 0 1 2 3 4

// 将以下代码适配到vector和list中做反向迭代器，理解反向迭代器的原理
namespace bit
{// 适配器 -- 复用template<class Iterator, class Ref, class Ptr>struct Reverse_iterator{Iterator _it;};// vector和list反向迭代器实现
}

namespace bit
{// 将以下代码适配到vector和list中做反向迭代器，理解反向迭代器的原理// 适配器 -- 复用template<class Iterator, class Ref, class Ptr>struct Reverse_iterator{Iterator _it;typedef Reverse_iterator<Iterator, Ref, Ptr> Self;Reverse_iterator(Iterator it):_it(it){}Ref operator*(){Iterator tmp = _it;return *(--tmp);}Ptr operator->(){return &(operator*());}Self& operator++(){--_it;return *this;}Self& operator--(){++_it;return *this;}bool operator!=(const Self& s){return _it != s._it;}};template<class T>class vector{public:typedef T* iterator;typedef const T* const_iterator;// 反向迭代器适配支持typedef Reverse_iterator<iterator, T&, T*> reverse_iterator;typedef Reverse_iterator<const_iterator, const T&, const T*> const_reverse_iterator;const_reverse_iterator rbegin() const{// list_node<int>*return const_reverse_iterator(end());}const_reverse_iterator rend() const{return const_reverse_iterator(begin());}reverse_iterator rbegin(){return reverse_iterator(end());}reverse_iterator rend(){return reverse_iterator(begin());}iterator begin(){return _start;}iterator end(){return _finish;}const_iterator begin() const{return _start;}const_iterator end() const{return _finish;}// ...}

namesapce std
{template<class T>class list{typedef list_node<T> Node;public:typedef __list_iterator<T, T&, T*> iterator;	typedef __list_iterator<T, const T&, const T*> const_iterator;// 反向迭代器适配支持typedef Reverse_iterator<iterator, T&, T*> reverse_iterator;typedef Reverse_iterator<const_iterator, const T&, const T*> const_reverse_iterator;const_iterator begin() const{// list_node<int>*return const_iterator(_head->_next);}const_iterator end() const{return const_iterator(_head);}iterator begin(){return iterator(_head->_next);//return _head->_next;}iterator end(){return iterator(_head);}const_reverse_iterator rbegin() const{// list_node<int>*return const_reverse_iterator(end());}const_reverse_iterator rend() const{return const_reverse_iterator(begin());}reverse_iterator rbegin(){return reverse_iterator(end());}reverse_iterator rend(){return reverse_iterator(begin());}//...}
}

下面程序的输出结果正确的是( )

int main()
{int array[] = { 1, 2, 3, 4, 0, 5, 6, 7, 8, 9 };int n = sizeof(array) / sizeof(int);list<int> mylist(array, array+n);auto it = mylist.begin();while (it != mylist.end()){if(* it != 0)cout<<* it<<" ";elseit = mylist.erase(it);++it;}return 0;
}
A.1 2 3 4 5 6 7 8 9
B. 1 2 3 4 6 7 8 9
C.程序运行崩溃
D.1 2 3 4 0 5 6 7 8 9

对于list有迭代器it, 当erase(it)后，说法错误的是( )

A.当前迭代器it失效

B.it前面的迭代器仍然有效

C.it后面的迭代器失效

D.it后面的迭代器仍然有效

分析：选C ，erase()函数会删除指定迭代器位置上的元素，并返回指向被删除元素下一个位置的迭代器。如果删除的是容器中的最后一个元素，则返回的是容器末尾的迭代器，即end()迭代器。

下面有关vector和list的区别，描述正确的是( )

A.两者在尾部插入的效率一样高

B.两者在头部插入的效率一样高

C.两者都提供了push_back和push_front方法

D.两者都提供了迭代器，且迭代器都支持随机访问

分析：选A，vector由于在头部插入数据效率很低，所以没有提供push_front方法

下列代码的运行结果是（）

void main()
{stack<char> S;char x,y;x='n';y='g';7S.push(x);S.push('i');S.push(y);S.pop();S.push('r');S.push('t');S.push(x);S.pop();S.push('s');while(!S.empty()){x = S.top();S.pop();cout<<x;};cout<<y;
}
A.gstrin	B.string	C.srting	D.stirng

分析：选B，

下列代码的运行结果是（）

void main()
{queue<char> Q;char x,y;x='n';y='g';Q.push(x);Q.push('i');Q.push(y);Q.pop();Q.push('r');Q.push('t');Q.push(x);Q.pop();Q.push('s');while(!Q.empty()){x = Q.front();Q.pop();cout<<x;};cout<<y;
}
A.gstrin	B.grtnsg	C.srting	D.stirng

分析：选B，

一个栈的输入顺序是a,b,c,d,e则下列序列中不可能是出栈顺序是( )

A.e,d,a,c,b

B.a,e,d,c,b

C.b,c,d,a,e

D.b,c,a,d,e

分析：选A

以下是一个二叉树的遍历算法，queue是FIFO队列，请参考下面的二叉树，根节点是root，正确的输出是( )

2 3

4 5 6 7

queue.push(root);
while(!queue.empty())
{node = queue.top();queue.pop();                             output(node->value)    //输出节点对应数字if(node->left)queue.push(node->left);if(node->right)queue.push(node->right);   
}
A.1376254
B.1245367
C.1234567
D.1327654

分析：选C

. - 力扣（LeetCode）

#include<stack>
class MinStack {
public:stack<int> mystack;stack<int> minstack;MinStack() {}void push(int val) {if(minstack.empty()||val<=minstack.top()){minstack.push(val);}mystack.push(val);}void pop() {if(minstack.top()==mystack.top()){minstack.pop();}mystack.pop();}int top() {return mystack.top();}int getMin() {return minstack.top(); }};/*** Your MinStack object will be instantiated and called as such:* MinStack* obj = new MinStack();* obj->push(val);* obj->pop();* int param_3 = obj->top();* int param_4 = obj->getMin();*/

分析：

栈的压入、弹出序列_牛客题霸_牛客网

class Solution {public:/*** 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可*** @param pushV int整型vector* @param popV int整型vector* @return bool布尔型*/bool IsPopOrder(vector<int>& pushV, vector<int>& popV) {stack<int> mystack;while (!popV.empty()) {if (!pushV.empty()) {mystack.push(pushV.front());pushV.erase(pushV.begin());}while (mystack.top() == popV.front()) {mystack.pop();popV.erase(popV.begin());if(popV.empty()){return true;}if(mystack.empty()){break;}}if (pushV.empty() && !popV.empty()) {return false;;}}return true;}};

思路分析：

逆波兰表达式

class Solution {
public:int evalRPN(vector<string>& tokens) {stack<int> mystack;while(!tokens.empty()){if(tokens.front()=="+"){tokens.erase(tokens.begin());int a = mystack.top();mystack.pop();int b = mystack.top();mystack.pop();mystack.push(a+b);}else if(tokens.front()=="-"){tokens.erase(tokens.begin());int a = mystack.top();mystack.pop();int b = mystack.top();mystack.pop();mystack.push(b-a);}else if(tokens.front()=="/"){tokens.erase(tokens.begin());int a = mystack.top();mystack.pop();int b = mystack.top();mystack.pop();mystack.push(b/a);}else if(tokens.front()=="*"){tokens.erase(tokens.begin());int a = mystack.top();mystack.pop();int b = mystack.top();mystack.pop();mystack.push(b*a);}else{mystack.push(stoi(tokens.front()));tokens.erase(tokens.begin());}}int ret = mystack.top();return ret;}
};