计算机专业基础综合历年真题试卷汇编1

计算机专业基础综合计算机网络（网络层）历年真题试卷汇编1(总分：130.00，做题时间：90分钟)一、单项选择题(总题数：27，分数：62.00)1.如果IP地址为120．14．22．16，掩码为255．255．128．0，则子网地址是____。

【华东理工大学2006年】（分数：2.00）A.120．0．0．0B.120．14．0．0 √C.120．14．22．0D.120．14．22．16解析：解析：考查子网掩码。

由子网掩码可知前17位为子网地址，因此选B。

2.一个网段的网络号为198．90．10．0／27，子网掩码固定为255．255．255．224，最多可以分成____个子网，而每个子网最多具有____个有效地IP地址。

【北京航空航天大学2006年】（分数：2.00）A.8，30 √B.4，62C.16，14D.32，6解析：解析：考查CIDR子网的划分。

由题可知除去网络ID，主机ID有5位二进制数，一位二进制无法分配主机号(排除了0和1就没了)，最少两位二进制表示主机号，因此还剩3位二进制可以表示子网号，所以最多可以分成8个子网。

当5位二进制都表示主机号，即只有一个子网时，每个子网最多具有30个有效的IP地址(排除了全0和全1)。

故选A。

3.下面哪个协议是网络层协议?____。

【重庆邮电大学2007年】（分数：2.00）A.HTTPB.TCPC.DHCPD.ICMP √解析：解析：考查网络层协议。

HTTP和DHCP都是应用层协议，TCP是传输层协议，IP、ARP、ICMP是网络层协议，因此选D。

4.Internet的网络层含有4个重要的协议，分别为____。

【北京理工大学2005年】（分数：2.00）A.IP，ICMP，ARP，UDPB.TCP，ICMP，UDP，ARPC.IP，ICMP，ARP，RARP √D.UDP，IP，ICMP，RARP解析：解析：考查网络层协议。

TCP和LIDP都是传输层协议，IP、ICMP、ARP、RARP(逆地址解析协议)是网络层协议。

计算机专业基础综合计算机组成原理（计算机系统概述）历年真题试卷汇编1(总分：70.00，做题时间：90分钟)一、单项选择题(总题数：29，分数：58.00)1.电了计算机问世至今，新型机器不断推陈出新，但不管怎么更新，依然具有“存储程序”的特点，最早提出这种概念的是____。

【上海交通大学1999年】A.巴贝奇B.冯.诺依曼√C.帕斯卡D.贝尔考查计算机发展历程。

2.对有关数据加以分类、统计、分析，这属于计算机在——方面的应用。

A.数值计算B.辅助设计C.数据处理√D.实时控制考查计算机的发展及应用。

3.冯.诺依曼型计算机的最根本特征是____。

【中科院计算所2001年】A.以运算器为中心B.采用存储程序原理√C.存储器按地址访问D.数据以二进制编码，并采用二进制运算考查冯.诺依曼型计算机基本概念。

冯.诺依曼型计算机的最根本特征是采用存储程序原理，基本工作方式是控制流驱动方式，工作方式的基本特点是按地址访问并顺序执行指令。

4.冯.诺依曼型计算机的基本工作方式是____。

【中科院计算所1998年】A.控制流驱动方式√B.多指令流多数据流方式C.微程序控制方式D.数据流驱动方式考查冯.诺依曼型计算机基本概念。

解析同上。

5.计算机系统采用层次化结构组成系统，从最上层的最终用户到最底层的计算机硬件，其层次化构成为____。

A.高级语言机器一操作系统机器一汇编语言机器一机器语言机器一微指令系统B.高级语言机器一汇编语言机器一机器语言机器一操作系统机器一微指令系统C.高级语言机器一汇编语言机器一操作系统机器一机器语言机器一微指令系统√D.高级语言机器一汇编语言机器一操作系统机器一微指令系统一机器语言机器考查计算机系统层次化结构。

6.计算机系统是由____组成的。

【武汉大学2007年】A.CPU和存储器B.CPU和接口C.运算器和控制器D.硬件系统和软件系统√考查计算机系统概念。

完整的计算机系统包括硬件系统和软件系统。

计算机专业基础综合计算机网络（计算机网络体系结构）历年真题试卷汇编1(总分：62.00，做题时间：90分钟)一、单项选择题(总题数：18，分数：52.00)1.下列不属于计算机网络功能的是____。

【南京师范大学2004年】（分数：2.00）A.提高系统可靠性B.提高工作效率C.分散数据的综合处理D.使各计算机相对独立√解析：解析：考查计算机网络的功能。

计算机网络的三大主要功能是数据通信、资源共享以及分布式处理。

计算机网络使各计算机之间的联系更加紧密而不是相对独立。

2.计算机网络系统的基本组成是____。

【哈尔滨工业大学2008年复试题】（分数：2.00）A.局域网和广域网B.本地计算机网和通信网C.通信子网和资源子网√D.服务器和工作站解析：解析：考查计算机网络的组成。

计算机网络从逻辑功能上可以分为资源子网和通信子网两部分。

资源子网由主机、终端及相关软件资源等组成，它提供各种网络资源与服务。

通信子网由各种传输介质、通信设备和相关的网络协议组成，它为网络提供数据传输、交换和通信控制功能。

3.在计算机网络中，所有的计算机均连接到一条通信传输线路上，在线路两端连有防止信号反射的装置。

这种连接结构称为____。

【华中科技大学2003年】（分数：2.00）A.星形拓扑B.总线拓扑√C.环形拓扑D.树形拓扑解析：解析：考查计算机网络的分类。

总线型拓扑是采用总线传输作为共用的传输介质，将网络中所有的计算机通过相应的硬件接口和电缆直接连接到这根共享总线上。

4.在如下的网络拓扑结构中，具有一定集中控制功能的网络是____。

【中央财经大学2006年】（分数：2.00）A.总线型网络B.星形网络√C.环形网络D.全连接型网络解析：解析：考查计算机网络的分类。

星形拓扑结构便于集中控制，因为端用户之间的通信必须经过中心站。

5.____不是对网络模型进行分层的目标。

【华中科技大学1999年】（分数：2.00）A.提供标准语言B.定义功能执行的方法√C.定义标准界面D.增加功能之间的独立性解析：解析：考查网络体系结构的基本概念。

计算机专业基础综合数据结构（排序）历年真题试卷汇编1(总分：72.00，做题时间：90分钟)一、单项选择题(总题数：15，分数：30.00)1.下列序列中，( )是执行第一趟快速排序后所得的序列。

【福州大学1998一、9(2分)】A.[68，11，18，69] [23，93，73]B.[68，11，69，23] [18，93，73]C.[93，73][68，11，69，23，18] √D.[68，11，69，23，18] [93，73]枢轴是73。

2.适合并行处理的排序算法是( )。

【西安电子科技大学2005一、8(1分)】【电子科技大学2005一、8(1分)】A.选择排序B.快速排序√C.希尔排序D.基数排序3.一组记录的关键字为(46，79，56，38，40，84)，则利用快速排序的方法，以第一个记录为基准得到的一次划分结果为( )。

【北京交通大学2005一、8(2分)【燕山大学2001一、4(2分)】A.(38，40，46，56，79，84)B.(40，38，46，79，56，84)C.(40，38，46，56，79，84) √D.(40，38，46，84，56，79)如何对一趟快速排序的结果在最短的时间内做出正确判断，这里给出建议：首先84应该不动，所以D排除了；接着40应调到序列首，所以A排除了；接着79应调到移走40的空位上，B排除了。

选择答案C，不必再继续做了(假定确有唯一正确答案)。

4.下列排序算法中，( )算法可能会出现下面的情况：初始数据有序时，花费的时间反而最多。

【中南大学2005一、4(2分)】A.快速排序√B.堆排序C.希尔排序D.冒泡排序5.将一组无序的数据重新排列成有序序列，其方法有：( )。

【武汉理工大学2004一、8(3分)】A.拓扑排序B.快速排序√C.堆排序√D.基数排序√6.就平均性能而言，目前最好的内排序方法是( )排序法。

【西安电子科技大学1998一、9(2分)】A.冒泡B.希尔插，AC.交换D.快速√7.如果只想得到1000个元素组成的序列中第5个最小元素之前的部分排序的序列，用( )方法最快。

计算机专业基础综合计算机组成原理（输入／输出(I／O)系统）历年真题试卷汇编1(总分：72.00，做题时间：90分钟)一、单项选择题(总题数：26，分数：52.00)1.CPU在中断响应周期中____。

【南京航空航天大学2000年】（分数：2.00）A.执行中断服务程序B.执行中断隐指令√C.与I／O设备传送数据D.处理故障解析：解析：考查中断周期和中断隐指令。

在中断周期，山中断隐指令自动完成保护断点、寻找中断服务程序入口地址以及硬什关中断的操作。

2.在中断响应周期，CPU主要完成以下工作____。

【南京航空航天大学2000年】（分数：2.00）A.关中断，保护断点，发中断响应信号并形成能转移地址√B.开中断，保护断点，发中断响应信号并形成能转移地址C.关中断，执行中断服务程序D.开中断，执行中断服务程序解析：解析：考查中断响应周期CPU的工作。

在中断响应周期，CPU主要完成关中断，保护断点，发中断响应信号并形成能转移地址的工作，即执行中断隐指令。

3.在中断周期中，由____将允许中断触发器置“0”。

【北京理工大学2006年】（分数：2.00）A.关中断指令√B.中断隐指令C.开中断指令D.清零指令解析：解析：考查关中断指令与中断允许触发器。

在中断周期中，由关中断指令将允许中断触发器置“0”。

4.CPU响应中断时最先完成的步骤是____。

【哈尔滨工业大学2004年】（分数：2.00）A.开中断B.保存断点C.关中断√D.转入中断服务程序解析：解析：考查中断执行流程。

5.在中断服务程序中，保护和恢复现场之前需要____。

【北京理工大学2002年】（分数：2.00）A.开中断B.关中断√C.响应D.恢复解析：解析：考查中断执行流程。

为了保证保护和恢复现场的过程不被中断信号打断，在保护和恢复现场之前需要关中断，等到保护和恢复现场之后，再开中断，以便中断信号可以继续进来。

6.CPU响应中断时，保护两个关键的硬件状态是____。

计算机专业基础综合计算机组成原理（计算机系统概述）历年真题试卷汇编1(总分：70.00，做题时间：90分钟)一、单项选择题(总题数：29，分数：58.00)1.电了计算机问世至今，新型机器不断推陈出新，但不管怎么更新，依然具有“存储程序”的特点，最早提出这种概念的是____。

【上海交通大学1999年】（分数：2.00）A.巴贝奇B.冯.诺依曼√C.帕斯卡D.贝尔解析：解析：考查计算机发展历程。

2.对有关数据加以分类、统计、分析，这属于计算机在——方面的应用。

（分数：2.00）A.数值计算B.辅助设计C.数据处理√D.实时控制解析：解析：考查计算机的发展及应用。

3.冯.诺依曼型计算机的最根本特征是____。

【中科院计算所2001年】（分数：2.00）A.以运算器为中心B.采用存储程序原理√C.存储器按地址访问D.数据以二进制编码，并采用二进制运算解析：解析：考查冯.诺依曼型计算机基本概念。

冯.诺依曼型计算机的最根本特征是采用存储程序原理，基本工作方式是控制流驱动方式，工作方式的基本特点是按地址访问并顺序执行指令。

4.冯.诺依曼型计算机的基本工作方式是____。

【中科院计算所1998年】（分数：2.00）A.控制流驱动方式√B.多指令流多数据流方式C.微程序控制方式D.数据流驱动方式解析：解析：考查冯.诺依曼型计算机基本概念。

解析同上。

5.计算机系统采用层次化结构组成系统，从最上层的最终用户到最底层的计算机硬件，其层次化构成为____。

（分数：2.00）A.高级语言机器一操作系统机器一汇编语言机器一机器语言机器一微指令系统B.高级语言机器一汇编语言机器一机器语言机器一操作系统机器一微指令系统C.高级语言机器一汇编语言机器一操作系统机器一机器语言机器一微指令系统√D.高级语言机器一汇编语言机器一操作系统机器一微指令系统一机器语言机器解析：解析：考查计算机系统层次化结构。

6.计算机系统是由____组成的。

计算机专业基础综合数据结构（树和二叉树）历年真题试卷汇编1(总分：86.00，做题时间：90分钟)一、单项选择题(总题数：27，分数：54.00)1.一棵完全二叉树上有1001个结点，其中叶子结点的个数是( )。

【西安交通大学1996三、2(3分)】（分数：2.00）A.250B.500C.254D.505E.以上答案都不对2.一棵124个叶结点的完全二叉树，最多有( )个结点。

【中国科学技术大学1995十四、3(2分)】（分数：2.00）A.247B.248C.249D.250E.2513.已知一棵完全二叉树中共有626个结点，叶子结点的个数应为( )。

【上海交通大学2005四、6(2分)】（分数：2.00）A.3 11B.3 12C.3 13D.3 14E.其他4.具有300个结点的二叉树，其高度至少应为( )。

【北京理工大学2006五、8(1分)】（分数：2.00）A.6B.7C.8D.95.当结点数目一定时，具有最小深度的二叉树是( )。

【北京航空航天大学2005】（分数：2.00）A.满二叉树B.完全二叉树C.线索二叉树D.二叉排序树6.二叉树的第I层上最多含有的结点数为( )。

【中山大学1998二、7(2分)】【北京理工大学2001六、5(2分)】（分数：2.00）A.2 IB.2 I-1一1C.2 I-1D.2 I一17.从树根(第0层)起，自上到下，逐层从左到右给二叉树的所有结点从1开始编号，则完全二叉树的第h 层的从左到右第k个结点的编号为( )。

【电子科技大学2005一、6(1分)】（分数：2.00）A.2 h +h-1B.2 h一k+1C.2 h +k+1D.2 h一k-18.下列判断中，( )是正确的。

【华南理工大学2006一、2(2分)】（分数：2.00）A.深度为k的二叉树最多有2 k -1个结点(k≥1)，最少有k个结点B.二叉树中不存在度大于2的结点C.对二叉树遍历是指先序、中序或后序遍历中的一种D.构造线索二叉树是为能方便找到每个结点的双亲9.一个具有1025个结点的二叉树的高h为( )。

计算机专业基础综合（计算机网络）历年真题试卷汇编1(总分：62.00，做题时间：90分钟)一、单项选择题(总题数：24，分数：48.00)1.在OSI参考模型中，自下而上第一个提供端到端服务的层次是( )。

A.数据链路层B.传输层√C.会话层D.应用层在OSI参考模型中，自下而上第一个提供端到端服务的层次是传输层。

自下而上疗法一般从检查物理层开始。

自下而上分别称为物理层、数据链路层、网络层、传输层、会话层、表示层和应用层。

传输层是两台计算机经过网络进行数据通信时第一个端到端的层次，具有缓冲作用。

2.在无噪声情况下，若某通信链路的带宽为3kHz，采用4个相位，每个相位具有4种振幅的QAM调制技术，则该通信链路的最大数据传输速率是( )。

A.12Kb／sB.24Kb／s √C.48Kb／sD.96Kb／s1924年奈奎斯特(Nyquist)就推导出在理想低通信道的最高大码元传输速率的公式：理想低通信道的最高大码元传输速率C=2Wlog 2 N(其中W是想低通信道的带宽，N是电平强度)信道带宽与数据传输速率的关系可以用奈奎斯特准则与香农(Shannon)定律捕述。

奈奎斯特定理描述了有限带宽、无噪声信道的最大数据传输速率与信道带宽的关系。

香农定理则描述了有限带宽、有随机热噪声信道的最大传输速率与信道带宽、信噪比之间的关系。

奈奎斯特准则指出：对于二进制数据信号的最大数据传输速率R max与通信信道带宽B(B=f，单位为Hz)的关系可以写为：R max =2*B(b／s)。

香农定理指出：在有随机热噪声的信道上传输数据信号时，数据传输速率R max与信道带宽B、信噪比S／N的关系为： R max =B*log 2 (1+S／N))[以2为底，1+S／N的对数] 式中，R max单位为b／s，带宽B单位为Hz，信噪比S／N通常以dB(分贝)数表示。

若S／N=30(dB)，那么信噪比根据公式：S／N(dB)=10*lg(S／N)则S／N=1000。

计算机专业基础综合计算机网络（物理层）历年真题试卷汇编1(总分：88.00，做题时间：90分钟)一、单项选择题(总题数：32，分数：64.00)1.数据传输速率是指____。

【北京科技大学2004年】（分数：2.00）A.每秒传输的字节数B.电磁波在传输介质上的传播速率C.每秒传输的比特数√D.每秒传输的码元个数解析：解析：考查物理层相关基本概念。

数据传输速率是计算机网络中非常重要的一个概念。

它和第一章中的带宽是同义词，指每秒传输的比特数，单位为bit／s。

码元传输速率指每秒能传输的码元数，单位为Baud(波特)。

另外，数据传输速率并不就是电磁波在传输介质上的传输速率，后者的单位为m／s，两者是完全不同的概念。

2.在同一时刻，通信双方可以同时发送数据的信道通信模式是____。

【西安电子科大2005年】（分数：2.00）A.半双工通信B.单工通信C.数据报D.全双工通信√解析：解析：考查物理层的通信模式。

物理层的数据通信模式有三种：单工通信、半双工通信、全双工通信。

在全双工通信中，通信的双方可以同时发送和接收信息，因此选D。

3.一个码元传输速率为300Baud的信道，如果采用4元制，则其信：道的传输速率为____。

【重庆大学2005年】（分数：2.00）A.300bit／sB.600bit／s √C.1200bit／sD.2400bit／s解析：解析：考查物理层的相关基本概念。

当采用4元制时，一个码元携带2bit的信息，则信息的传输速率为300×2bit／s=600bit／s，因此选B。

4.利用模拟通信信道传输数字信号的方法称为____。

【华中科技大学2001年】（分数：2.00）A.同步传输B.异步传输C.基带传输D.频带传输√解析：解析：考查数据通信方式。

将基带信号直接传送到通信线路上的传输方式称为基带传输。

将基带信号经过调制后送到通信线路上的方式称为频带传输。

5.采用8个相位的调相传输其码元，传输速率为200Baud，则数据传输率为____。

计算机专业基础综合数据结构（串）历年真题试卷汇编1(总分：58.00，做题时间：90分钟)一、填空题(总题数：12，分数：24.00)1.设T和P是两个给定的串，在T中寻找等于P的子串的过程称为(1)，又称P为(2)。

【西安电子科技大学1998二、5(16／6分)】__________________________________________________________________________________________ 正确答案：(正确答案：(1)模式匹配 (2)模式串)2.串是一种特殊的线性表，其特殊性表现在(1) ；串的两种最基本的存储方式是(2)、(3)；两个串相等的充分必要条件是(4)。

【中国矿业大学2000一、3(4分)】__________________________________________________________________________________________ 正确答案：(正确答案：(1)其数据元素都是字符(2)顺序存储(3)链式存储(4)串的长度相等且两串中对应位置的字符也相等)3.使用“求子串”subString(S，pos，len)和“联结”concat(S1，s2)的串操作，可从串s=‘conduction’中的字符得到串t=”cont”，则求t的串表达式为__________。

【北京工业大学2005二、4(3分)】__________________________________________________________________________________________ 正确答案：(正确答案：t=concat(subStIling(s，1，3)，subString(s，7，1)))4.下列程序读入无符号十六进制数(出现的字母为小写)，将其转换为十进制数输出。

请将程序空缺部分补全。

int f(char *s) {int n=0，i；for(i=0；s[i]!="＼0"; i++)n=n*16+(1)；return n；} main() {char s[10]； scanf(“％s”，s)；printf(“％d＼n”(2) )； }【浙江大学2002二(6分)】__________________________________________________________________________________________ 正确答案：(正确答案：(1)(s[i]>=977 s[i]一87：s[i]-48) ／／"a"到"f"的ASCII码是97到102 (2)f(s)) 5.已知U=‘xyxyxyxxyxy’；t=‘xxy’；ASSIGN(S，U)；ASSIGN(V，SUBSTR(S，INDEX(s，t)，LENCt)+1)),ASSIGN(m，‘ww’)求REPLACE(S，y，m)=__________。

计算机专业基础综合数据结构（数组和广义表）历年真题试卷汇编1计算机专业基础综合数据结构（数组和广义表）历年真题试卷汇编1(总分：64.00，做题时间：90分钟)一、单项选择题(总题数：15，分数：34.00)1.数组A[0．．5，0．．6]的每个元素占5个字节，将其按列优先次序存储在起始地址为1000的内存单元中，则元素A[5，5]的地址是( )。

【南京理工大学2001一、13(1．5分)】A.1 175 √B.1 180C.1205D.12102.设7行6列的数组a以列序为主序顺序存储，基地址为1024，每个元素占2个存储单元，第4行第5列的元素(假定无第0行第0列)的存储地址是( )。

【华中科技大学2006一、3(2分)】A.1068B.1086 √C.1084D.10663.若6行5列的数组以列序为主序顺序存储，基地址为1000，每个元素占2个存储单元，则第3行第4列的元素(假定无第0行第0列)的地址是( )。

【华中科技大学2004一、4(1分)】A.1040 √B.1042C.1026D.备选答案A，B，C都不对二维数组A的元素都是6个字符组成的串，行下标i的范围从0到8，列下标j的范围从1到10。

从供选择的答案中选出应填入下列关于数组存储叙述中( )内的正确答案。

(1)存放A至少需要( )个字节；(2)A 的第8 N一和第5行共占( )个字节；(3)若A按行存放，元素A[8，5]的起始地址与A按列存放时的元素( )的起始地址一致。

【山东工业大学2000三、1(4分)】【山东大学1998三、1(4分)】（分数：6.00）(1).(1)A.90B.180C.240D.270E.540 √(2).(2)A.108 √B.1 14C.54D.60E.150(3).(3)A.A[8，5]B.A[3，10] √C.A[5，8]D.A[0，9]4.设二维数组A[1．．m，1,n](即m行n列)按行存储在数组研1一m*n]中，则二维数组元素A[i，j]在一维数组B中的下标为( )。

计算机专业基础综合数据结构（文件）历年真题试卷汇编1(总分90,考试时间90分钟)1. 单项选择题1. 散列文件使用散列函数将记录的关键字值计算转化为记录的存放地址，因为散列函数是一对一的关系，则选择好的( )方法是散列文件的关键。

【哈尔滨工业大学2001二、5(2分)】A. 散列函数B. 除余法中的质数C. 冲突处理D. 散列函数和冲突处理2. 顺序文件采用顺序结构实现文件的存储，对大型的顺序文件的少量修改，要求重新复制整个文件，代价很高，采用( )的方法可降低所需的代价。

【北京邮电大学2000二、8(20／8分)】A. 附加文件B. 按关键字大小排序C. 按记录输入先后排序D. 连续排序3. 用ISAM组织文件适合于( )。

【中科院软件所1998】A. 磁带B. 磁盘4. 下述文件中适合于磁带存储的是( )。

【中科院计算所2000一、7(2分)】A. 顺序文件B. 索引文件C. 散列文件D. 多关键字文件5. 用ISAM和VSAM组织文件属于( )。

【中国科技大学1998二、5(2分)中科院计算所1998二、5(2分)】A. 顺序文件B. 索引文件C. 散列文件6. ISAM文件和V ASM文件属于( )。

【山东大学2001二、5(1分)】A. 索引非顺序文件B. 索引顺序文件C. 顺序文件D. 散列文件7. B+树应用在( )文件系统中。

【北京邮电大学2001一、1(2分)】A. ISAMB. VSAM8. 倒排文件包含有若干个倒排表，倒排表的内容是( )。

【哈尔滨工业大学2005二、8(1分)】A. 一个关键字值和该关键字的记录地址B. 一个属性值和该属性的一个记录地址C. 一个属性值和该属性的全部记录地址D. 多个关键字和它们相对应的某个记录的地址2. 填空题1. 文件可按其记录的类型不同而分成两类，即__________和__________文件。

【西安电子科技大学1998二、6(3分)】2. 从用户的观点看，文件的逻辑结构通常可以区分为两类：一类是如dBASE中数据库文件那样的文件组织结构，称为(1)文件；另一种是诸如用各种文字处理软件编辑成的文本文件，称为(2)文件。

计算机专业基础综合数据结构（树和二叉树）历年真题试卷汇编1计算机专业基础综合数据结构（树和二叉树）历年真题试卷汇编1(总分：86.00，做题时间：90分钟)一、单项选择题(总题数：27，分数：54.00)1.一棵完全二叉树上有1001个结点，其中叶子结点的个数是( )。

【西安交通大学1996三、2(3分)】A.250B.500C.254D.505E.以上答案都不对√2.一棵124个叶结点的完全二叉树，最多有( )个结点。

【中国科学技术大学1995十四、3(2分)】A.247B.248 √C.249D.250E.2513.已知一棵完全二叉树中共有626个结点，叶子结点的个数应为( )。

【上海交通大学2005四、6(2分)】A.3 11B.3 12C.3 13 √D.3 14E.其他4.具有300个结点的二叉树，其高度至少应为( )。

【北京理工大学2006五、8(1分)】A.6B.7C.8D.9 √5.当结点数目一定时，具有最小深度的二叉树是( )。

【北京航空航天大学2005】A.满二叉树B.完全二叉树√C.线索二叉树D.二叉排序树设结点数目是n，n个结点未必是满二叉树，A错。

C和D明显错误。

6.二叉树的第I层上最多含有的结点数为( )。

【中山大学1998二、7(2分)】【北京理工大学2001六、5(2分)】A.2 IB.2 I-1一1C.2 I-1√D.2 I一17.从树根(第0层)起，自上到下，逐层从左到右给二叉树的所有结点从1开始编号，则完全二叉树的第h 层的从左到右第k个结点的编号为( )。

【电子科技大学2005一、6(1分)】A.2 h +h-1 √B.2 h一k+1C.2 h +k+1D.2 h一k-18.下列判断中，( )是正确的。

【华南理工大学2006一、2(2分)】A.深度为k的二叉树最多有2 k -1个结点(k≥1)，最少有k个结点√B.二叉树中不存在度大于2的结点√C.对二叉树遍历是指先序、中序或后序遍历中的一种D.构造线索二叉树是为能方便找到每个结点的双亲9.一个具有1025个结点的二叉树的高h为( )。

计算机专业基础综合数据结构（集合）历年真题试卷汇编1(总分：82.00，做题时间：90分钟)一、综合题(总题数：25，分数：72.00)1.试用关键字序列(33，10，45，20，53，43，31，15，65，40)，构造哈希(Hash)表，设哈希函数为：H(key)=key％11，其中key为关键字，％为求余运算符；用开放定址法处理冲突，用线性探测再散列法查找空位，用长度为14的数据元素组A[14]表示哈希表。

(1)画出该哈希表的存储结构图；(2)假定每个元素的查找概率相等，计算查找成功时的ASL；(3)计算查找不成功时的ASL。

【华中科技大学2007四、25(10分)】（分数：2.00）__________________________________________________________________________________________ 2.采用哈希函数H(k)=3*k mod 13并用线性探测开放地址法处理冲突，在散列地址空间[0．．12]中对关键字序列22，41，53，46，30，13，1，67，51。

(1)构造哈希表(画示意图)；(2)装填因子；等概率下(3)成功的和(4)不成功的平均查找长度。

【北京工业大学2000三(8分)】【烟台大学2007四、4(10分)】（分数：2.00）__________________________________________________________________________________________3.设散列表长度为14 2.00）__________________________________________________________________________________________ 4.常用的构造哈希函数的方法有哪些?若在哈希表中删除一个记录，应如何操作?为什么?已知一组关键字为(19，14，23，01，68，20，84，27，55，11，10，79)，按哈希函数H(Key)=KeyMOD 13和线性探测再散列处理冲突的方法在地址空间A[0．．15]中构造哈希表。

计算机专业基础综合计算机组成原理（输入／输出(I／O)系统）历年真题试卷汇编1(总分：72.00，做题时间：90分钟)一、单项选择题(总题数：26，分数：52.00)1.CPU在中断响应周期中____。

【南京航空航天大学2000年】（分数：2.00）A.执行中断服务程序B.执行中断隐指令√C.与I／O设备传送数据D.处理故障解析：解析：考查中断周期和中断隐指令。

在中断周期，山中断隐指令自动完成保护断点、寻找中断服务程序入口地址以及硬什关中断的操作。

2.在中断响应周期，CPU主要完成以下工作____。

【南京航空航天大学2000年】（分数：2.00）A.关中断，保护断点，发中断响应信号并形成能转移地址√B.开中断，保护断点，发中断响应信号并形成能转移地址C.关中断，执行中断服务程序D.开中断，执行中断服务程序解析：解析：考查中断响应周期CPU的工作。

在中断响应周期，CPU主要完成关中断，保护断点，发中断响应信号并形成能转移地址的工作，即执行中断隐指令。

3.在中断周期中，由____将允许中断触发器置“0”。

【北京理工大学2006年】（分数：2.00）A.关中断指令√B.中断隐指令C.开中断指令D.清零指令解析：解析：考查关中断指令与中断允许触发器。

在中断周期中，由关中断指令将允许中断触发器置“0”。

4.CPU响应中断时最先完成的步骤是____。

【哈尔滨工业大学2004年】（分数：2.00）A.开中断B.保存断点C.关中断√D.转入中断服务程序解析：解析：考查中断执行流程。

5.在中断服务程序中，保护和恢复现场之前需要____。

【北京理工大学2002年】（分数：2.00）A.开中断B.关中断√C.响应D.恢复解析：解析：考查中断执行流程。

为了保证保护和恢复现场的过程不被中断信号打断，在保护和恢复现场之前需要关中断，等到保护和恢复现场之后，再开中断，以便中断信号可以继续进来。

6.CPU响应中断时，保护两个关键的硬件状态是____。

计算机专业基础综合数据结构（线性表）历年真题试卷汇编1(总分：70.00，做题时间：90分钟)一、单项选择题(总题数：9，分数：18.00)1.对于双向循环链表，在P指针所指的结点之后插入s指针所指结点的操作应为( )。

【北京工业大学2004一、1(3分)】（分数：2.00）A.P一>right=s；s一>left=p；p->right一>left=s；s一>right=p一>right；B.P一>right=s；p->right一>left=s； s一>left=p； s一>right=p一>fight；C.s一>left=p； s一>right=p一>right；P一>right=-s；P一>right一>left=s；D.s一>left=p； s一>right=p一>fight；P一>right一>left=s；P一>right=s；√解析：解析：双链表在p指向的结点前或结点后插入结点都可以，但是必须避免“断链”。

本例A和B第一个语句就将p的原后继断链，没必要再浪费时间看这两个选择答案后边的其他语句。

2.设双向循环链表中结点的结构有数据域data，指针域pre和next，链表不带头结点。

若在指针P所指结点之后插入结点S，则应执行下列( )操作。

【南京理工大学2005一、3 (1分)】【北京交通大学2006一、1(2分)】（分数：2.00）A.P一>next=s；s一≥pre=p；P一>next一>pre=s；s一>next=p一>next；B.P一>next=s；P一>next->pre=s；s一≥pre=p；s一>next=p一>next；C.s一>pre=p；s一>nex=p一>next；P一>next=s；P一>next->pre=s；D.s一≥pre=p；s->next=p一>next；P一>next一>pre=s；P一>next=s；√解析：3.在下列双向链表中，已知指针pa指向结点A，若在A、C之间插入指针pb所指的结点B，则依次执行的【华中科技大学2006二、4(2分)】(1)pb一>next=pa->next；(2)pb一>prior=pa；语句序列可以是( )。

计算机专业基础综合计算机网络（传输层）历年真题试卷汇编1(总分：94.00，做题时间：90分钟)一、单项选择题(总题数：22，分数：60.00)1.OSI七层模型中，提供端到端的透明数据传输服务、差错控制和流量控制的层是____。

【南京师范大学2002年】A.物理层B.网络层C.传输层√D.会话层考查传输层提供的服务。

传输层的功能如下：1)复用和分用。

2)传输层提供应用进程间的逻辑通信(即端到端的通信)。

3)对收到的报文进行差错检测。

4)提供两种不同的运输协议(即提供面向连接的服务和无连接的服务)，即面向连接的TCP和无连接的UDP。

TCP协议提供差错控制和流量控制。

2.在下面给出的协议中，——是TCP／IP标准传输层的协议。

【华东理工大学2006年】A.TCP和UDP √B.DNS和SMTPC.RARP和IPD.DNS和FTP考查传输层协议。

B项和D项是应用层协议。

C项是网络层协议。

TCP／IP的传输层有两个不同特性的协议UDP和TCP。

其中，TCP向高层提供面向连接的可靠的字节流服务，而UDP向高层提供面向无连接的不可靠的数据报服务。

因此选A。

3.TCP和UDP具有多路复用功能，与此相关的协议头字段是____。

A.源端口号和目的端口号B.目的IP地址和目的端口号C.源IP地址和源端口号√D.源IP地址和目的IP地址考查传输层功能。

传输层的复用、分用功能与网络层的复用、分用功能不同。

传输层的复用是指发送方不同的应用进程都可以使用同一个传输层协议传送数据，分用是指接收方的传输层在剥去报文的首部后能够把这些数据正确交付到目的应用进程。

多路复用目标端负责检测源IP地址和源端口，判断是否接收。

因此选C。

4.传输层为____之间提供逻辑通信。

A.主机B.进程√C.路由器D.操作系统考查传输层的功能。

传输层提供应用进程间的逻辑通信(即端到端的通信)。

与网络层的区别是，网络层提供的是主机之间的逻辑通信。