2022CCF非专业级别软件能力认证第一轮(CSP-J)提高级C++语言试题一、单项选择题（共15题，每题2分，共计30分；每题有且仅有一个正确选项）1.以下哪种功能没有涉及C++语言的面向对象特性支持：（）。A.C++中调用printf函数B.C++中调用用户定义的类成员函数C.C++中构造一个class或structD.C++中构造来源于同一基类的多个派生类答：选A。printf是C语言中就有的函数，定义类（class）或结构体(struct)，类成员函数，构造派生类等等，都是面向对象语言才支持的操作。2.有6个元素，按照6,5,4,3,2,1的顺序进入栈S，请问下列哪个出栈序列是非法的（）。A.543612B.453126C.346521D.234156答：选C。C中当4出栈时，4前入栈的6,5一定都在栈中，情况为：栈底-6-5。所以接下来不可能是6出栈，只能是5出栈。3.运行以下代码片段的行为是（）。intx=101;inty=201;int*p=&x;Int*q=&y;p=q;A.将x的值赋为201B.将y的值赋为101C.将q指向x的地址D.将p指向y的地址答：选D。把q赋值给p，也就是让p从指向x的指针变为指向y的指针,指向y的指针就是y的地址。4.链表和数组的区别包括（）。A.数组不能排序，链表可以B.链表比数组能存储更多的信息C.数组大小固定，链表大小可动态调整D.以上均正确答：选C。选项A：数组和链表都能做排序，一旦申请数组，数组的长度就是固定的了。而链表可以申请和释放结点，大小可以动态调整。5.对假设栈S和队列Q的初始状态为空。存在e1~e6六个互不相同的数据，每个数据按照进栈S、出栈S、进队列Q、出队列Q的顺序操作，不同数据间的操作可能会交错。已知栈S中依次有数据e1、e2、e3、e4、e5和e6进栈，队列Q依次有数据e2、e4、e3、e6、e5和e1出队列。则栈S的容量至少是（）个数据。A.2B.3C.4D.6答：选B。栈是后进先出，队列是先进先出。队列出队的顺序，就是队列入队的顺序。而队列入队的顺序，就是栈出栈的顺序。6.对表达式a+(b-c)*d的前缀表达式为（），其中+、-、*是运算符。A.*+a-bcdB.+a*-bcdC.abc-d*+D.abc-+d答：选B。画出该表达式的表达式树，前序遍历表达式树即为前缀表达式7.假设字母表{a,b,c,d,e}在字符串出现的频率分别为10%,15%,30%,16%,29%。若使用哈夫曼编码方式对字母进行不定长的二进制编码，字母d的编码长度为（）位。A.1B.2C.2或3D.3答：选B构建出如下哈夫曼树，d的编码01。还能构造出不同的哈夫曼树，但编码长度都是28.一棵有n个结点的完全二叉树用数组进行存储与表示，已知根结点存储在数组的第1个位置。若存储在数组第9个位置的结点存在兄弟结点和两个子结点，则它的兄弟结点和右子结点的位置分别是（）。A.8、18B.10、18C.8、19D.10、19答：选C完全二叉树用数组存储，第i结点的左孩子的位置为2*i，右孩子的位置为2*i+1，双亲的位置为i/2；因此位置9的结点是第4结点的右孩子，该结点的兄弟结点是4的左孩子，位置为9-1=8，9的右孩子的位置为9*2+1=19。9.考虑由N个顶点构成的有向连通图，采用邻接矩阵的数据结构表示时，该矩阵中至少存在（）个非零元素。A.N-1B.NC.N+1D.N2答：选A。n个顶点的连通图最少有n-1条边，因此至少存在n-1个非零元素。10.以下对数据结构的表述不恰当的一项为：（）。A.图的深度优先遍历算法常使用的数据结构为栈。B.栈的访问原则为后进先出，队列的访问原则是先进先出。C.队列常常被用于广度优先搜索算法。D.栈与队列存在本质不同，无法用栈实现队列。答：选D图的深度优先遍历算法最常用递归来实现，递归使用了栈的结构，广度优先搜索算法使用队列实现；选项D中，栈与队列本质上都是功能受限的线性表，本质并无不同，非用来栈实现队列的功能也可以的，只是效率显然不如直接使用队列。11.以下哪组操作能完成在双向循环链表结点p之后插入结点s的效果（其中，next域为结点的直接后继，prev域为结点的直接前驱）：（）。A.p->next->prev=s;s->prev=p;p->next=s;s->next=p->next;B.p->next->prev=s;p->next=s;s->prev=p;s->next=p->next;C.s->prev=p;s->next=p->next;p->next=s;p->next->prev=s;D.s->next=p->next;p->next->prev=s;s->prev=p;p->next=s;答：选D。p->next=s语句使得p->next的值发生了变化；s->next=p->next;与p->next->prev=s;中...
