下载文档原格式
计算机统考《计算机学科专业基础综合》考研2021年考研真题一、热门考研真题解析42（15分）已知一个带有表头结点的单链表，结点结构为，假设该链表只给出了头指针1ist。
在不改变链表的前提下，请设计一个尽可能高效的算法，查找链表中倒数第k个位置上的结点（k为正整数）。
若查找成功，算法输出该结点的data域的值，并返回1；否则，只返回0。
要求：（1）描述算法的基本设计思想；（2）描述算法的详细实现步骤；（3）根据设计思想和实现步骤，采用程序设计语言描述算法（使用C或C＋＋或JAVA语言实现），关键之处请给出简要注释。
解：（1）算法的基本设计思想定义两个指针变量p和q，初始时均指向头结点的下一个结点。
p指针沿链表移动；当p指针移动到第k个结点时，q指针开始与p 指针同步移动；当p指针移动到链表最后一个结点时，因为p和q相隔k，故q指针所指元素为倒数第k个结点。
以上过程对链表仅进行一遍扫描。
（2）算法的详细实现步骤①count＝0，p和q指向链表表头结点的下一个结点；②若p为空，转⑤；，③若count等于k，则q指向下一个结点；否则，count＝count＋1；④p指向下一个结点，转步骤②；⑤若count等于k，则查找成功，输出该结点的data域的值，返回1；否则，查找失败，返回0；⑥算法结束。
（3）算法实现43（8分）某计算机的CPU主频为500MHz，CPI为5（即执行每条指令平均需要5个时钟周期）。
假定某外设的数据传输率为0.5 MB/s，采用中断方式与主机进行数据传送，以32位为传输单位，对应的中断服务程序包含18条指令，中断服务的其他开销相当于2条指令的执行时间。
请回答下列问题，要求给出计算过程。
（1）在中断方式下，CPU用于该外设I/O的时间占整个CPU时间的百分比是多少？（2）当该外设的数据传输率达到5MB/s时，改用DMA方式传送数据。
假定每次DMA传送块大小为5000B，且DMA预处理和后处理的总开销为500个时钟周期，则CPU用于该外设I/O时间占整个CPU时间的百分比是多少？（假设DMA与CPU 之间没有访存冲突）解：（1）已知主频为500MHz，则时钟周期＝1÷500MHz ＝2ns，因为CPI＝5，所以每条指令平均5×2＝10ns。
2021年广东暨南大学计算机基础综合考研真题招生专业与代码：计算机系统结构081201、计算机软件与理论081202、计算机应用技术081203、电子信息(专业学位) 085400考试科目名称及代码：计算机基础综合848考生注意：所有答案必须写在答题纸（卷）上，写在本试题上一律不给分。
第一部分数据结构（75分）一、单项选择题(每题2分，共20分)1. 某线性表中最常用的操作是在最后一个元素之后插入一个元素和删除第一个元素，则采用（）存储方式最节省运算时间。
A.单链表B.仅有头指针的单向循环链表C.双链表D.仅有尾指针的单向循环链表2. 一个栈的输入序列为1，2，3...，n，若输出序列的第一个元素是n，那么输出第i（1<=i<=n）个元素是（）。
A. n-iB. iC. n-i+1D. 不确定3. 若一颗二叉树具有15个度为2的结点，10个度为1的结点，则度为0的结点个数是（）。
A. 16B. 25C. 40D. 不确定4. 根据使用频率，为5个字符设计的哈夫曼编码不可能是（）。
A. 000，001，010，011，1B. 000，001，01，10，11C. 00，100，101，110，111D. 0000，0001，001，01，15. 设a，b为一棵二叉树上的两个结点，在中序遍历时，a在b前面的条件是（）。
A.a在b的右方B. a在b的左方C. a是b的祖先D. a是b的子孙6. 对一棵二叉排序树按（）遍历，可得到结点值从小到大的排序序列。
A. 先序B. 中序C. 后序D. 层次7. 已知一个有序表为(5，13，19，21，37，56，64，75，80，88，92)，则折半查找64需要比较（）次。
A. 1B. 2C. 3D. 48. 在一个图中，所有顶点的度数之和等于所有边数的（）倍。
A. 1/2B. 1C. 2D. 39. 一个序列中有100000个元素，若只想得到其中前10个最大元素，则最好采用（）方法。
![昆明理工大学2021年[计算机学科基础综合]考研真题](https://img.taocdn.com/s1/m/bf4994053069a45177232f60ddccda38376be114.png)
昆明理工大学2021年[计算机学科基础综合]考研真题数据结构部分一、选择题1.已知10个数据元素（54，28，16，34，73，62，95，60，26，43），按照依次插入结点的方法生成一棵二叉排序树后，则查找值为62的结点所需比较的次数是[ ]。
A. 2B. 3C. 4D. 52.在一棵完全二叉树中，若编号为j 的结点有右孩子，则该结点的编号为[ ] 。
A. 2*j-1B. 2*jC. 2*j+1D. j/23.在线性表的存储结构中，[ ]查找（按关键字查找）、插入、删除速度慢，但顺序存取和随机存取第i个元素速度快；[ ]查找和存取速度快，但插入、删除速度慢；[ ]查找、插入和删除速度快，但不能进行顺序存取；[ ]插入、删除和顺序存取速度快；但查找速度慢。
A. 顺序有序表,散列表，顺序表，链接表B. 顺序有序表，链接表，散列表，顺序表C. 顺序表，顺序有序表，散列表，链接表D. 顺序表，顺序有序表，链接表，散列表4.由分别带权为9，2，5，7的四个叶结点构造一棵哈夫曼树，则该树的带权路径长度是[ ]。
A. 23B.37C. 44D. 465.如果已知一个栈的入栈序列是：1，2，3，．．．，n，其出栈序列是：p1，p2，p3，．．．，pn，若p1=n，则pi为[ ]A．i B．n+i C．n-i D．n-i+16.已知8个数据元素（34，76，45，18，26，54，92，65），按照依次插入结点的方法生成一棵二叉排序树，则最后两层上的结点总数是[ ]。
A. 1B. 2C. 3D. 47.对线性表进行二分查找时，要求线性表必须是[ ]。
A.以顺序方式存储B.以链接方式存储C.以顺序方式存储，且数据元素有序D.以链接方式存储，且数据元素有序8.一个中缀算术表达式a+（b-x）*y，则对应的后缀算术表达式为[ ]。
A. a b x y - * +;B. a b x - + y *;C. a b x - y * +;D. a b x y * - +;9.已知一个有序表为（12，18，24，35，47，50，62，83，90，115，134），当二分查找值为90的元素时，[ ]次比较后查找成功；当二分查找值为47的元素时，[ ] 次比较后查找成功。
2021年计算机考研真题及参考答案_文档视界2018年全国硕士研究生入学统一考试计算机科学与技术学科联考计算机学科专业基础综合试题一、单项选择题：第1～40小题，每小题2分，共80分。
下列每题给出的四个选项中，只有一个选项最符合试题要求。
1．若栈S1中保存整数，栈S2中保存运算符，函数F()依次执行下述各步操作：（1）从S1中依次弹出两个操作数a和b；（2）从S2中弹出一个运算符op；（3）执行相应的运算 b op a；（4）将运算结果压人S1中。
假定S1中的操作数依次是5, 8, 3, 2（2在栈顶），S2中的运算符依次是*, - , +（+在栈顶）。
调用3次F()后，S1栈顶保存的值是。
A. -15B. 15C. -20D. 202. 现有队列Q与栈S，初始时Q中的元素依次是1, 2, 3, 4, 5,6（1在队头），S为空。
若仅允许下列3种操作：①出队并输出出队元素；②出队并将出队元素人栈；③出栈并输出出栈元素，则不能得到的输出序列是。
A. 1, 2, 5, 6, 4, 3B. 2, 3, 4, 5, 6, 1C. 3, 4, 5, 6, 1, 2D. 6, 5, 4, 3, 2, 1）按行优先存人C3. 设有一个12×12的对称矩阵M，将其上三角部分的元素m i, j（1≤i≤j≤12语言的一维数组N中，元素m6, 6在N中的下标是。
A. 50B. 51C. 55D. 664. 设一棵非空完全二叉树T的所有叶结点均位于同一层，且每个非叶结点都有2个子结点。
若T有k个叶结点，则T的结点总数是。
A. 2k-1B. 2kC. k2D. 2k-15. 已知字符集{a, b, c, d, e, f}，若各字符出现的次数分别为6, 3, 8, 2, 10, 4，则对应字符集中各字符的哈夫曼编码可能是。
A. 00, 1011, 01, 1010, 11, 100B. 00, 100, 110, 000, 0010, 01C. 10, 1011, 11, 0011, 00, 010D. 0011, 10, 11, 0010, 01, 0006. 已知二叉排序树如下图所示，元素之间应满足的大小关系是。
【盛世清北】 2021 北京大学 801 计算机专业基础考研真题盛世清北分享：北京大学 801 计算机专业基础考试真题，适用北京大学以下院系 +专业070921 地质学（石油地质学）0701J3 数据科学（数学） 0714J3 数据科学（统计学）0812J3 数据科学（计算机科学与技术）北京大学深圳研究生院 081203 计算机应用技术 北京大学 801 计算机专业基础科目的考研真题为：数据结构：1. 写出 AVL 树并计算平均查找长度。
2. n 个数组成二叉树，证明排序时间复杂度为 O （nlogn ） （ 这个记忆得有点模糊 ）3. 一个数组，有最多 X 个极值，设计一个时间复杂度尽可能低的算法。
、 计算机体系结构：1. 结合流程图阐述乘法器的工作原理，然后对其改进。
2. MIPS 指令集计算机网络： 一个用户通过交换机，集线器向另一个用户发送 IP 报文，问交换机的作用，源地址和 目的地址。
北京大学 801 计算机基础 2018 年研究生入学试题北京大学地球与空间科学学院北京大学前沿交叉学科研究院 北京大学前沿交叉学科研北京大学信息科学技术学院北京大学信息科学技术学院 081201 计算机系统结构 081202 计算机软件与理论0812031.算法复朵度丈具体＞:已知下血一串代码.求英算法时间复杂度: int s =i = 0; While(S ＜n){ S ÷= i; i+÷;)V 备注☆＞；王道2017年真題本质是一样的 A 、O(N) BX O(N A2) C 、 O(IOgN) D 、 类似这样的答案2.线性表龙具体A 下面关于线性表的叙述中，不帀确的是哪些()? ＜备注^卜线性衣的荷储结构链接和顺序3. 伐混洗＜具体a ：给了 卜字符⅛ HAPPY,按照这个顺序入栈，则出栈顺序不可能足堆卯个()A. HAYPPB. HPPAYC.HYAPAD ・ HAEEY＜备栈混洗类题「I,群里冇具体算法代码.但是一般只考选择题.具体算法思想： 采用一个中间栈来记录毎段小栈的信息.复杂废O (∏2＞4.图的邻按矩阵＜H 休、：某连通图的邻按矩阵为A ・若点i 到点j 存在-条长度为m 的埒径，那么可以看哪 个^Raij ⅛否为1() A. A R TnAC. A AlTl D A A (In-I) V 备注☆☆☆＞：5.DES, BFS,连通图相关概念【较一•版冇更改】A 、 采用顺序存储的线性表,B 、 采用顺序存储的线性表,C 、 采用链接存储的线性表,D 、 采用链接存储的线性表.必须占用一片连续的存储单元; 便于进行插入和删除操作. 不必占用一片连续的存储单元; 便T 抽入和删除操作；对于联通无向图.请问以下说法正确的是：A.广度优先⅛⅛½先进后岀：B.连通開的MST ⅛极大连通于图C.广度优先抄索址递归丈现的：Iy毎次深哎优先搜索都能得到一个联通分支；V具体☆☆＞：6.r%M的前，中，后遍历相关类型题V具体叶节点相对顺序前中后序遍历是否一样()A.完全一样B.完全不一样C.前序和后序一样D 前冲和中样一样7.森林.二叉树转换＜具体〉若森林F对应的一叉树R中冇m个点.R的根节点r的右子树貝冇n个节点・那么徐林F中第1额树的结点个数为：A、m-nB、m-n-lC、n÷lD、不确進＜备辻：☆☆☆＞不难，宴砒题&散列农，二次黃找法＜具体☆☆☆☆＞: 希值为ke〉哈希表长14线性衷插入到【15, 38, 61. 84, 8},最后播入49.那么利用二次探测法.49应该放在下标为多少的表顶中？A. 3B. 5C.8D.99.b树与b+树＜其体R B+树不同「B树的待.点之一是A、B树和B+树都是AVL枸R、R树和R+材都能用丁•文件系统C、B树和B+树都冇效支持嗾序仆找D、B树和B+树协竹效文持随机仪找＜备江☆☆☆＞： b树和》树是否支持馳机責找和顺序查找10.<H体A针对以下无向连通因从点I开始.使用D l jkStra 法寻找单源最短路径.依次加入的点是()1. 2、4、3、7. 5、D. ??<备注给了个图，止给出根岛算法所得到的次序王逍上血许多题Fl类似II.归并段、阿路归并，WPL<見体、：若初始归并茂大小分别为，5 9 12 13 14 16 17 18 20 28 3 0 37 42,那么呆住fl并树的带权路径长度WPL是()A.460B.472C.480D 486二■简存题(弟一题6分，第二題8分，第三题9分》：K •颗空AVL树中∙H页序插入｛5942 I 38 |：(1)、严格遵循AVL操作，画出描入启的AVL树(画出每•步〉；(2)、全部插入后.求等慨率下的育找成功的平均检索长皮。
2021年全国硕士研究生招生考试计算机科学与技术学科联考计算机学科专业根底综合试题一、单项选择题：1~40小题，每题2分，共80分。
以下每题给出的四个选项中，只有一个选项符合试题要求。
1.设n是描述问题规模的非负整数，以下程序段的时间复杂度是x=0；while(n>=(x+l)*(x+l))x=x+l；A. O(log n)B. O(n1/2)C. O(n)D. O(n2)2.假设将一棵树T转化为对应的二又树BT，那么以下对BT的遍历中，其遍历序列与T的后根遍历序列相同的是A. 先序遍历B. 中序遍历C. 后序遍历D. 按层遍历3.对n个互不相同的符号进行哈夫曼编码。
假设生成的哈夫曼树共有115个结点，那么n的值是A. 56B. 57C. 58D. 604.在任意一棵非空平衡二又树(AVL树)T1中，删除某结点v之后形成平衡二又树T2，再将w插入T2形成平衡二又树T3。
以下关于T1与T3的表达中，正确的选项是v是T1的叶结点，那么T1与T3可能不相同Ⅱ.假设v不是T1的叶结点，那么T1与T3一定不相同Ⅲ.假设v不是T1的叶结点，那么T1与T3一定相同A. 仅IB. 仅IIC. 仅I、ⅡD. 仅I、Ⅲ5.以下图所示的AOE网表示一项包含8个活动的工程。
活动d的最早开始时间和最迟开始时间分别是A. 3和7B. 12和12C. 12和14D. 15和156.用有向无环图描述表达式(x+y)*((x+y)/x)，需要的顶点个数至少是A. 5B. 6C. 8D. 97.选择一个排序算法时，除算法的时空效率外，以下因素中，还需要考虑的是I.数据的规模Ⅱ.数据的存储方式Ⅲ.算法的稳定性A. 仅ⅢB. 仅I、ⅡC. 仅Ⅱ、Ⅲ、IVD. I、Ⅱ、Ⅲ、Ⅳ8.现有长度为11且初始为空的散列表HT，散列函数是H(key)=key%7，采用线性探查(线性探测再散列)法解决冲突将关键字序列87，40，30，6，11，22，98，20依次插入到HT后，HT查找失败的平均查找长度是A. 4B. 5.25C. 6D. 6.299.设主串T=“abaabaabcabaabc〞，模式串S=“abaab c〞，采用KMP算法进行模式匹配，到匹配成功时为止，在匹配过程中进行的单个字符间的比拟次数是A. 9B. 10C. 12D. 1510. 排序过程中，对尚未确定最终位置的所有元素进行一遍处理称为一“趟〞。
重庆理工大学2021年[计算机学科基础综合]考研真题一、单选题1．算法分析的目的是（）。
A．找出数据结构的合理性B．研究算法中的输入和输出的关系C．分析算法的效率以求改进D．分析算法的易懂性和稳定性2．设某算法完成对n个元素进行处理所需的时间是：T(n)=200log2n+1000n(log2n+100)+100000，则该算法的时间复杂度是（）。
A．O(1)B．O(n)C．O(nlog2n)D．O(nlog2n+log2n)3．若某链表最常用的操作是在最后一个结点之后插入一个元素和删除最后一个元素，则采用（）存储方式最节省运算时间。
A．单链表B．双链表C．单循环链表D．带头结点的双循环链表4．在中缀表达式转化为后缀表达式与后缀表达式求值算法中，都需要用到哪种特殊的数据结构（）。
A．栈B．队列C．二叉树D．堆5．一个队列的入队序列是1，2，3，4，则队列的出队序列只能是（）。
A．4，3，2，1B．1，2，3，4C．1，4，3，2D．3，2，4，16．将含有100个结点的完全二叉树从根结点开始编号，根为0号，后面按从上到下、从左到右的顺序对结点编号，那么编号为41的结点的双亲结点编号为（）。
A．42B．40C．21D．207．如果在某二叉树的前序序列、中序序列和后序序列中，结点b都在结点a的后面（即形如…a…b…），则最有可能的情况是（）。
A．a和b是兄弟B．a是b的双亲C．a是b的左孩子D．a是b的右孩子8．某二叉树的后序遍历序列是dabec，中序遍历序列是debac，其前序遍历序列是（）。
A．acbedB．decabC．deabcD．cedba9．下述编码中，哪一个不是前缀码（）。
A．(0,10,110,111)B．(11,10,001,101,000)C．(00,010,011,1)D．(1,01,000,001)10．一个有n个顶点的无向图最多有（）条边。
A．nB．n(n-1)C．n(n-1)/2D．2n11．在现代操作系统中，采用缓冲技术的主要目的是（）A．改善用户编程环境B．提高CPU的处理速度C．实现与设备无关D．提高设备与CPU之间的并行程度12．下列哪个事件不可能在用户态发生？（）A．系统调用B．外部中断C．进程切换D．缺页13．操作系统是对（）进行管理的软件。
2021考研计算机学科专业根底综合真题及答案一. 单项选择题，每题2分，共80分。
1.为解决计算机与打印机之间速度不匹配的问题，通常设置一个打印数据缓冲区，主机将要输出的数据依次写入该缓冲区，而打印机那么依次从该缓冲区中取出数据。
该缓冲区的逻辑构造应该是A.栈B.队列C.树D.图2.设栈 S 和队列 Q 的初始状态均为空，元素 abcdefg 依次进入栈 S。
假设每个元素出栈后立即进入队列 Q，且7个元素出队的顺序是 bdcfeag，那么栈 S 的容量至少是A.1B.2C.3D.43.给定二叉树图所示。
设 N 代表二叉树的根，L 代表根结点的左子树，R 代表根结点的右子树。
假设遍历后的结点序列为3，1，7，5，6，2，4，那么其遍历方式是A.LRNB.NRLC.RLND.RNL4.以下二叉排序树中，满足平衡二叉树定义的是5.一棵完全二叉树的第6层(设根为第1层)有8个叶结点，那么完全二叉树的结点个数最多是A.39B.52C.111D.1196.将森林转换为对应的二叉树，假设在二叉树中，结点 u 是结点 v 的父结点的父结点，那么在原来的森林中，u 和 v 可能具有的关系是I.父子关系 II.兄弟关系 III. u 的父结点与 v 的父结点是兄弟关系A.只有 IIB.I 和 IIC.I 和 IIID.I、II 和 III7.以下关于无向连通图特性的表达中，正确的选项是I.所有顶点的度之和为偶数 II.边数大于顶点个数减1III.至少有一个顶点的度为1A.只有 IB. 只有 IIC.I 和 IID.I 和 III8.以下表达中，不符合 m 阶 B 树定义要求的是A.根节点最多有 m 棵子树B.所有叶结点都在同一层上C.各结点内关键字均升序或降序排列D.叶结点之间通过指针链接9.关键序列5，8，12，19，28，20，15，22是小根堆(最小堆)，插入关键字3，调整后得到的小根堆是A.3，5，12，8，28，20，15，22，19B. 3，5，12，19，20，15，22，8，28C.3，8，12，5，20，15，22，28，19D. 3，12，5，8，28，20，15，22，1910.假设数据元素序列11，12，13，7，8，9，23，4，5是采用以下排序方法之一得到的第二趟排序后的结果，那么该排序算法只能是A.起泡排序B.插入排序C.选择排序D.二路归并排序11.冯·诺依曼计算机中指令和数据均以二进制形式存放在存储器中，CPU 区分它们的根据是A.指令操作码的译码结果B.指令和数据的寻址方式C.指令周期的不同阶段D.指令和数据所在的存储单元12.一个 C 语言程序在一台32位机器上运行。
2021年考研计算机统考《计算机学科专业基础综合》考研历年真题第一部分备考指南一、大纲解读1大纲的重要性及其注意事项教育部考试中心的《计算机学科专业基础综合考试大纲》规定了考试的范围、要求、形式、试卷结构等，这本小册子是考试中心命题的唯一依据，是考生复习备考必不可少的资料，考生一定要对考试大纲有足够的重视。
在复习的过程中，要从以下几点加以把握：（1）全面复习，重视变化在复习的过程中一定要严格按照《计算机学科专业基础综合考试大纲》来进行备考，据此详细了解计算机学科专业基础综合考试的题型、题量和对各个考点的掌握程度，以便合理分配复习时间。
对于大纲中未列出的考点，可以不用复习，以免浪费时间。
而那些大纲中明确标明要“理解”“掌握”的知识点一定要给予足够的重视。
一般来说，修订的考点往往是该年命题的重点，也是该年的热点。
但这也不是绝对，因为现在考研试题的制定越来越活，而且反押题的趋势也很明显。
所以考生在复习的时候还是要尽量全面的掌握大纲内容。
（2）根据大纲妥善安排复习计划《计算机学科专业基础综合考试大纲》将在每年8月底或9月初由教育部发布，在新大纲没有发布以前，考生可以将最新的计算机考研大纲当作参考，指导自己的复习。
因为考试大纲是不会完全发生变化的，即使有变化，也只会是一些知识点的增加、删减，或者是某些表述的变化，基础知识和重点知识一般不会发生变化。
（3）根据大纲定期检测复习漏洞大纲不但是考研复习的起点，而且在复习的过程中，考生也要经常根据考试大纲对自己定期进行知识检索，看哪些知识点理解了，哪些仍处于模糊状态，以便进行及时的弥补。
只有深入理解大纲规定的需要我们掌握和理解的各个知识点，我们才能找到解题的突破口和切入点。
2大纲的主要内容（1）考试性质计算机学科专业基础综合考试是为高等院校和科研院所招收计算机科学与技术学科的硕士研究生而设置的具有选拔性质的联考科目，其目的是科学、公平、有效地测试考生掌握计算机科学与技术学科大学本科阶段专业基础知识、基本理论、基本方法的水平和分析问题、解决问题的能力，评价的标准是高等院校计算机科学与技术学科优秀本科毕业生所能达到的及格或及格以上水平，以利于各高等院校和科研院所择优选拔，确保硕士研究生的招生质量。
（2）考查目标计算机学科专业基础综合考试涵盖数据结构、计算机组成原理、操作系统和计算机网络等学科专业基础课程。
要求考生系统地掌握上述专业基础课程的基本概念、基本原理和基本方法，能够综合运用所学的基本原理和基本方法分析、判断和解决有关理论问题和实际问题。
（3）考试形式和试卷结构①试卷满分及考试时间本试卷满分为150分，考试时间为180分钟。
②答题方式答题方式为闭卷、笔试。
③试卷内容结构a．数据结构45分；b．计算机组成原理45分；c．操作系统35分；d．计算机网络25分。
（4）试卷题型结构①单项选择题80分（40小题，每小题2分）②综合应用题70分第一部分历年考研真题2009年全国硕士研究生入学统一考试408计算机学科专业基础综合真题及详解一、单项选择题：1～40小题，每小题2分，共80分。
下列每题给出的四个选项中。
只有一个选项是最符合题目要求的。
1为解决计算机主机与打印机之间速度不匹配问题，通常设置一个打印数据缓冲区，主机将要输出的数据依次写入该缓冲区，而打印机则依次从该缓冲区中取出数据。
该缓冲区的逻辑结构应该是（）。
A．栈B．队列C．树D．图【答案】B查看答案【解析】这类问题一般都先分析题目中的数据具有什么操作特性或是结构特性比如“先进后出”、“先进先出”等再判断其逻辑结构。
栈和队列是操作受限的线性表，栈具有先进后出的特性而队列具有先进先出的特性。
由于本题中先进入打印数据缓冲区的文件先被打印，因此打印数据缓冲区具有先进先出性，则它的逻辑结构应该是队列。
2设栈S和队列Q的初始状态均为空，元素a，b，c，d，e，f，g依次进入栈S。
若每个元素出栈后立即进入队列Q，且7个元素出队的顺序是b，d，c，f，e，a，g，则栈S的容量至少是（）。
A．1B．2C．3D．4【答案】C查看答案【解析】由于栈具有先进后出的特性，队列具有先进先出的特性，出队顺序即为人队顺序。
在本题中，每个元素出栈S后立即进入队列Q，出栈顺序即为入队顺序，所以本题中队列的作用形同虚设，根据题意出队顺序即为出栈顺序。
根据出栈顺序可以分析各个元素进出栈的过程：第一个出栈元素为b，表明栈内还有元素a，b出栈前的深度为2；第二个出栈元素为d，栈内元素为a和c，d出栈前的深度为3；c出栈后，剩余元素为a，c出栈前的深度为2；f出栈后，剩余元素为a 和e，f出栈前的深度为3；e出栈后，剩余元素为a，e出栈前的深度为2；a出栈后，无剩余元素，a出栈前的深度为1；g出栈后，无剩余元素，g出栈前的深度为1。
所以栈容量至少是3。
3给定二叉树如下图所示。
设N代表二叉树的根，L代表根结点的左子树，R代表根结点的右子树。
若遍历后的结点序列为3，1，7，5，6，2，4，则其遍历方式是（）。
A．LRNB．NRLC．RLND．RNL【答案】D查看答案【解析】对“二叉树”而言，一般有三条搜索路径：①先上后下的按层次遍历；②先左（子树）后右（子树）的遍历；③先右（子树）后左（子树）的遍历。
其中第1种搜索路径方式就是常见的层次遍历，第2种搜索路径方式包括常见的先序遍历NLR、中序遍历LNR、后序遍历LRN，第3种搜索路径方式则是不常使用的NRL、RNL、RLN。
本题考查的是第3种搜索路径方式的一种情况。
根据遍历的序列以及树的结构图，可以分析出该遍历的顺序是先右子树再跟结点最后左子树，故答案为D。
4下列二叉排序树中，满足平衡二叉树定义的是（）。
【答案】B查看答案【解析】平衡二叉树是指左右子树高度差（平衡因子）的绝对值不超过1的二叉树。
A项中根结点的平衡因子是2；B项中每个结点的平衡因子的绝对值均不超过1；C项中根结点的平衡因子是－2；D项中根结点的平衡因子是3。
5已知一棵完全二叉树的第6层（设根为第1层）有8个叶结点，则该完全二叉树的结点个数最多是（）。
A．39B．52C．111D．119【答案】C查看答案【解析】完全二叉树的一个特点是：叶子结点只能出现在最下层和次下层。
题目中没有说明完全二叉树的高度，首先由完全二叉树的特点确定题目中树的高度。
根据题意，一棵完全二叉树的第6层（设根为第1层）有8个叶结点，可知此二叉树的高度是6或7。
题目中求二叉树的结点数最多的情况，因此此完全二叉树的高度为7。
由于高度为7的完全二叉树的前6层是一棵满二叉树，根据二叉树的性质2可知，高度为6的满二叉树的结点数是26－1＝63。
又根据二叉树的性质1可知，题目中二叉树的第6层结点数是25＝32个结点，已知有8个叶子结点，那么其余32－8＝24个结点均为分支结点，这些结点在第7层上最多有48个子结点（即叶子结点）。
所以此二叉树的结点数最多可达26－1＋（25－8）×2＝111。
6将森林转换为对应的二叉树，若在二叉树中，结点u是结点v的父结点的父结点，则在原来的森林中，u和v可能具有的关系是（）。
Ⅰ．父子关系Ⅱ．兄弟关系Ⅲ．u的父结点与v的父结点是兄弟关系A．只有ⅠB．Ⅰ和ⅡC．Ⅰ和ⅢD．Ⅰ、Ⅱ和Ⅲ【答案】B查看答案【解析】首先，在二叉树中，若结点u是结点v的父结点的父结点，那么u 和v的关系有如下4种情况：接下来，根据森林与二叉树的转换规则，将这4种情况还原成森林中结点的关系。
其中：情况（1），在原来的森林中u是v的父结点的父结点；情况（2），在森林中u是v的父结点；情况（3），在森林中u是v的父结点的兄弟；情况（4），在森林中u与v是兄弟关系。
由此可知，题目中的Ⅰ、Ⅱ是正确的。
7下列关于无向连通图特性的叙述中，正确的是（）。
Ⅰ．所有的顶点的度之和为偶数Ⅱ．边数大于顶点个数减1Ⅲ．至少有一个顶点的度为1A．只有ⅠB．只有ⅡC．Ⅰ和ⅡD．Ⅰ和Ⅲ【答案】A查看答案【解析】在图中，顶点的度TD（V i）之和与边的数目满足关系式：其中，n为图的总结点数，e为总边数。
因此，Ⅰ项正确。
对于Ⅱ、Ⅲ项中的特性不是一般无向连通图的特性，可以轻松地举出反例。
“至少有一个顶点的度为1”的反例如下图（1）所示，“边数大于顶点个数减1”的反例如下图（2）所示。
（1）（2）8下列叙述中，不符合m阶B树定义要求的是（）。
A．根结点最多有m棵子树B．所有叶结点都在同一层上C．各结点内关键字均升序或降序排列D．叶结点之间通过指针链接【答案】D查看答案【解析】B树就是指B-树。
根据B-树的定义，m阶B-树中每个结点最多有m个分支，因此，根结点最多有m棵子树，A项正确；B-树中所有叶结点都在最底层，位于同一层，B项正确；结点内各关键字互不相等且有序排列，C项正确。
但是，所有叶子结点之间通过指针链接，是B＋树的定义，而B-树中没有。
因此，D项是错误的。
9已知关键字序列5，8，12，19，28，20，15，22是小根堆（最小堆），插入关键字3，调整后的小根堆是（）。
A．3，5，12，8，28，20，15，22，19B．3，5，12，19，20，15，22，8，28C．3，8，12，5，20，15，22，28，19D．3，12，5，8，28，20，15，22，19【答案】A查看答案【解析】在堆中插入或删除一个元素后，将不再满足堆的性质。
为了使其成为新堆，在输出堆顶元素后，需要调整剩余元素。
具体过程如图（1）～（5）所示，（1）为原堆，（2）为插入3后，（3）、（4）为调整过程，（5）为调整后的小根堆。
10若数据元素序列11，12，13，7，8，9，23，4，5是采用下列排序方法之一得到的第二趟排序后的结果，则该排序算法只能是（）。
A．起泡排序B．插入排序C．选择排序D．二路归并排序【答案】B查看答案【解析】经过两趟排序后，A项起泡排序的结果是两个最小或最大的元素放到了序列的最终位置；B项插入排序的结果是前三个数有序即可；C项选择排序结果是两个最小的元素在最前面按顺序排好；D项二路归并排序的结果是长度为4的子序列有序，即前4个数排好序，接下来的4个数排好序。
显然题目中的元素序列只能是插入排序第二趟排序后的结果，因此，B项正确。
11冯·诺依曼计算机中指令和数据均以二进制形式存放在存储器中，CPU区分它们的依据是（）。
A．指令操作码的译码结果B．指令和数据的寻址方式C．指令周期的不同阶段D．指令和数据所在的存储单元【答案】C查看答案【解析】在冯·诺依曼结构计算机中指令和数据均以二进制形式存放在同一个存储器中，CPU可以根据指令周期的不同阶段来区分是指令还是数据，通常在取指阶段取出的是指令，其他阶段（分析取数阶段、执行阶段）取出的是数据。
所以，CPU区分指令和数据的依据是指令周期的不同阶段。
