[考研类试卷]计算机专业基础综合数据结构(概论)历年真题试卷汇编2.doc

计算机专业基础综合历年真题试卷汇编2(总分：60.00，做题时间：90分钟)一、单项选择题(总题数：16，分数：32.00)1.单项选择题1-40小题。

下列每题给出的四个选项中，只有一个选项是最符合题目要求的。

（分数：2.00）__________________________________________________________________________________________解析：2.若无向图G=(V，E)中含有7个顶点，要保证图G在任何情况下都是连通的，则需要的边数最少是_______。

（分数：2.00）A.6B.15C.16 √D.21解析：解析：要保证无向图G在任何情况下都是连通的，即任意变动图G中的边，G始终保持连通，首先需要G的任意6个结点构成完全连通子图G1，需n(n-1)／2=6×(6-1)／2=15条边，然后再添一条边将第7个结点与G1连接起来，共需16条边。

3.下列关于图的叙述中，正确的是_______。

Ⅰ．回路是简单路径Ⅱ．存储稀疏图，用邻接矩阵比邻接表更省空间Ⅲ．若有向图中存在拓扑序列，则该图不存在回路（分数：2.00）A.仅ⅡB.仅Ⅰ、ⅡC.仅Ⅲ√D.仅Ⅰ、Ⅲ解析：解析：第一个顶点和最后一个顶点相同的路径称为回路；序列中顶点不重复出现的路径称为简单路径；回路显然不是简单路径，故Ⅰ错误；稀疏图是边比较少的情况，此时用邻接矩阵的空间复杂度为O(n 2)，必将浪费大量的空间，而邻接表的空间复杂度为O(n+e)，应该选用邻接表，故Ⅱ错误。

存在回路的有向图不存在拓扑序列，若拓扑排序输出结束后所余下的顶点都有前驱，则说明只得到了部分顶点的拓扑有序序列，图中存在回路，故Ⅲ正确。

4.设图的邻接矩阵A如下所示。

各顶点的度依次是_______（分数：2.00）A.1，2，1，2B.2，2，1，1C.3，4，2，3 √D.4，4，2，2解析：解析：邻接矩阵A为非对称矩阵，说明图是有向图，度为入度加出度之和。

计算机专业基础综合计算机组成原理（指令系统）历年真题试卷汇编2(总分：76.00，做题时间：90分钟)一、单项选择题(总题数：20，分数：40.00)1.在指令的相对寻址方式中，其相对的基准地址是____。

【西安电子科技大学2007年】（分数：2.00）A.基址寄存器B.变址寄存器C.堆栈指示器D.程序计数器√解析：解析：考查相对寻址方式的基本概念。

相对寻址是把程序计数器PC的内容加上指令格式中的形式地址而形成操作数的有效地址，即EA=(Pc)+A，故基准地址是程序计数器。

2.相对寻址方式中，指令所提供的相对地址实质上是一种____。

【哈尔滨工程大学2003年】（分数：2.00）A.立即数B.内存地址C.以本条指令在内存中首地址为基准位置的偏移量D.以下条指令在内存中首地址为基准位置的偏移量√解析：解析：考查相对地址的概念。

相对寻址方式中，EA=(PC)+A(A为形式地址)，当执行本条指令时，PC 已完成加1，故以下条指令为基准位置。

3.____寻址方式用来支持浮动程序设计。

【中科院计算所2000年】（分数：2.00）A.相对寻址√B.变址寻址C.寄存器间接寻址D.基址寻址解析：解析：考查相对寻址方式的作用。

相对寻址的优点：操作数的地址不是固定的，它随着PC值的变化而变化，并且与指令地址之间总是相差一个固定值，因此便于程序浮动。

4.设相对寻址的转移指令占2个字节，第一字节为操作码，第二字节为位移量(用补码表示)，每当CPU从存储器取出一个字节时，即自动完成(PC)+1→PC。

设当前指令地址为3008H，要求转移到300FH，则该转移指令第二字节的内容应为____。

若当前指令地址为300FH，要求转移到3004H，则该转移指令第二字节的内容为____。

【哈尔滨工业大学2007年】（分数：2.00）A.05H，F2HB.07H，F3HC.05H，F3H √D.07H，F2H解析：解析：考查相对寻址方式。

计算机专业基础综合数据结构（集合）历年真题试卷汇编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分)】__________________________________________________________________________________________正确答案：(正确答案：成功 =(6*1+2*3+5+7)／10=24／10(3)ASL 失败=(4+3+2+1+2+1+1+2+1+9+8)／11=34／1 1。

计算方法参见上面58题(3)。

)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分)】__________________________________________________________________________________________正确答案：(正确答案：装填因子=9／13=0．7 (3)ASL SUCC =11／9 (4)ASL UNSUCC =29／13)3.设散列表长度为14，散列函数，其中i为键值中第一个字母在字母表中的序号，若键值的输入顺序为Jan，Feb，Mar，Apr，May，Jun，Jul，Aug，Sep，Oct，Nov，Dec，用拉链法处理冲突，要求：(1)构造散列表；(2)求出在等概率情况下，查找成功的平均查找长度。

一.选择题篇1. 算法的计算量的大小称为计算的（）。

【北京邮电大学2000 二、3 （20/8分）】A．效率 B. 复杂性 C. 现实性 D. 难度2. 算法的时间复杂度取决于（）【中科院计算所 1998 二、1 （2分）】A．问题的规模 B. 待处理数据的初态 C. A和B3.计算机算法指的是（1）它必须具备（2）这三个特性。

【南京理工大学 1999 一、1（2分）【武汉交通科技大学 1996 一、1（ 4分）】(1) A．计算方法 B. 排序方法 C. 解决问题的步骤序列 D. 调度方法(2) A．可执行性、可移植性、可扩充性 B. 可执行性、确定性、有穷性C. 确定性、有穷性、稳定性D. 易读性、稳定性、安全性4．一个算法应该是（）。

【中山大学 1998 二、1（2分）】A．程序 B．问题求解步骤的描述 C．要满足五个基本特性 D．A和C.5. 下面关于算法说法错误的是（）【南京理工大学 2000 一、1（1.5分）】A．算法最终必须由计算机程序实现B.为解决某问题的算法同为该问题编写的程序含义是相同的C. 算法的可行性是指指令不能有二义性D. 以上几个都是错误的6. 下面说法错误的是（）【南京理工大学 2000 一、2 （1.5分）】(1）算法原地工作的含义是指不需要任何额外的辅助空间（2）在相同的规模n下，复杂度O(n)的算法在时间上总是优于复杂度O(2n)的算法（3）所谓时间复杂度是指最坏情况下，估算算法执行时间的一个上界（4）同一个算法，实现语言的级别越高，执行效率就越低A．(1) B.(1),(2) C.(1),(4) D.(3)7．从逻辑上可以把数据结构分为（）两大类。

【武汉交通科技大学 1996 一、4（2分）】A．动态结构、静态结构 B．顺序结构、链式结构C．线性结构、非线性结构 D．初等结构、构造型结构8．以下与数据的存储结构无关的术语是（）。

【北方交通大学 2000 二、1（2分）】A．循环队列 B. 链表 C. 哈希表 D. 栈9．以下数据结构中，哪一个是线性结构（）？【北方交通大学 2001 一、1（2分）】A．广义表 B. 二叉树 C. 稀疏矩阵 D. 串10．以下那一个术语与数据的存储结构无关？（）【北方交通大学 2001 一、2（2分）A．栈 B. 哈希表 C. 线索树 D. 双向链表11．在下面的程序段中，对x的赋值语句的频度为（）【北京工商大学 2001 一、10（3分）】FOR i:=1 TO n DOFOR j:=1 TO n DOx:=x+1;A． O(2n) B．O(n) C．O(n2) D．O(log2n)12．程序段 FOR i:=n-1 DOWNTO 1 DOFOR j:=1 TO i DOIF A[j]>A[j+1]THEN A[j]与A[j+1]对换；其中 n为正整数，则最后一行的语句频度在最坏情况下是（）【南京理工大学1998一、1(2分)】A. O（n）B. O(nlogn)C. O(n3)D. O(n2)13．以下哪个数据结构不是多型数据类型（）【中山大学 1999 一、3（1分）】A．栈 B．广义表 C．有向图 D．字符串14．以下数据结构中，（）是非线性数据结构【中山大学 1999 一、4】A．树 B．字符串 C．队 D．栈15. 下列数据中，（）是非线性数据结构。

计算机专业基础综合计算机组成原理（输入／输出(I／O)系统）历年真题试卷汇编2(总分：64.00，做题时间：90分钟)一、单项选择题(总题数：25，分数：50.00)1.计算机的外部设备是指____。

（分数：2.00）A.输入／输出设备B.外存储器C.输入／输出设备和外存储器√D.电源解析：解析：考查计算机外部设备的概念。

除主机以外的硬件装置统称为外部设备或外围设备，包括输入／输出设备和外存储器。

2.下列说法正确的是____。

（分数：2.00）A.计算机中一个汉字内码在主存中占用4BB.输出的字型码16×16点阵在缓冲存储区中占用32B √C.输出的字型码16×16点阵在缓冲存储区中占用16BD.以上说法都不对解析：解析：考查基本概念。

计算机中一个汉字内码在主存中占用2B，输出的字型码16×16点阵在缓冲存储区中占用(16×16／8)B=32B。

3.对于字符显示器，主机送给显示器的是打印字符的____。

【北京理工大学2002年】（分数：2.00）A.AscII码√B.列点阵码C.BCD码D.行点阵码解析：解析：考杏字符显示器。

当显示器刷新显示时，首先要从缓冲存储器中读出一个要显示的字符编码，即打印字符的ASCII码，然后以此编码为依据，到字符发生器读取该字符的第1行光点信息，然后通过并串转换电路，变成串行信息送到CRT显示。

对于字符显示器来说，生机送给显示器的是打印字符的ASCII 码，而从字符发生器中取出的是字符的行点阵码。

4.在打印机或显示器的字库中，存放着字符的____。

【北京理工大学2002年】（分数：2.00）A.二进制码B.ASCII码C.BCD码D.点阵编码√解析：解析：考查打印机和显示器的字符存放方式。

在打印机或显示器的字库中，存放着字符的点阵编码。

5.CRT的分辨率为1024×1024像素，像素的颜色数为256，则刷新存储器的容量为____。

考研统考计算机基础真题及答案前言计算机技术在信息时代中扮演着重要角色，而计算机专业的考试则是计算机相关职位的必备条件。

考研统考计算机基础涵盖计算机组成原理、计算机网络、操作系统、数据结构、算法和编程语言等方面，对了解和掌握计算机基础知识具有重要作用。

本篇文档总结了考研统考计算机基础真题及其答案，以方便考生备考和提高成绩。

考研统考计算机基础真题以下是考研统考计算机基础的部分真题，供读者参考。

1. 计算机网络题目1以下哪项属于网络层协议？A. IP协议B. TCP协议C. HTTP协议D. FTP协议题目2简单网管代理协议指的是：A. TelnetB. SMTPC. SNMPD. HTTP2. 操作系统题目1进程的状态有哪些？题目2死锁的必要条件是什么？3. 数据结构题目1链表中结点的结构是什么？题目2用递归实现求n!的值。

4. 算法题目1快速排序的时间复杂度是什么？题目2在一个已排好序的数组中查找某个元素，应该采用什么算法？5. 编程语言题目1以下哪个是Python中的for循环语句？A. foreachB. whileC. do whileD. for题目2以下代码输出的结果是什么？def foo(a=[]):a.append(1)print(a)foo() # [1]foo() # [1, 1]foo() # [1, 1, 1]考研统考计算机基础答案以下是考研统考计算机基础真题的答案。

1. 计算机网络题目1答案：A题目2答案：C2. 操作系统题目1答案：就绪、运行和阻塞。

题目2答案：请求和保持、不剥夺、持有和等待、循环等待。

3. 数据结构题目1答案：由指向数据域和指向下一结点的指针域组成。

题目2答案：def factorial(n):if n ==1or n ==0:return1return n * factorial(n -1)print(factorial(5)) # 1204. 算法题目1答案：O(nlogn)题目2答案：二分查找算法。

数据结构考研真题及其答案完整版数据结构是计算机科学与技术领域中的一门重要课程，也是计算机考研中必考的一门科目。

通过研究数据结构，可以帮助我们更好地理解和应用计算机算法，提高计算机程序的效率和性能。

为了帮助考生更好地备考数据结构，本文将分享一些数据结构考研真题及其答案，供考生参考。

一、选择题1. 下列关于栈的叙述中，错误的是（）A. 栈是一种线性数据结构，具有后进先出（LIFO）的特点B. 栈可以用数组实现，也可以用链表实现C. 栈的插入和删除操作都是在同一端进行的D. 栈的插入和删除操作的时间复杂度都是O(1)答案：C解析：栈的插入操作叫做入栈，删除操作叫做出栈。

入栈和出栈操作都是在栈顶进行的，而不是同一端。

2. 假设要对n个整数关键字进行排序，以下排序算法中，平均时间复杂度最小的是（）A. 冒泡排序B. 快速排序C. 归并排序D. 直接插入排序答案：C解析：归并排序的时间复杂度是O(nlogn)，平均时间复杂度最小。

二、填空题1. 下列关于图的遍历顺序的说法中，正确的是：深度优先搜索访问的顺序是________，广度优先搜索访问的顺序是________。

答案：前序遍历，层次遍历解析：深度优先搜索即前序遍历，广度优先搜索即层次遍历。

2. 给定一个最小堆，若删除堆顶元素后，需要对堆进行调整，所采用的操作是________。

答案：下滤解析：删除堆顶元素后，将最后一个叶子节点放到堆顶，然后进行下滤操作。

三、简答题1. 请简要说明动态规划算法的基本思想和应用场景。

答：动态规划算法的基本思想是将问题分解为多个子问题，通过求解子问题的最优解来得到原问题的最优解。

它通常适用于具有重叠子问题和最优子结构性质的问题。

动态规划算法可以大大减少问题的重复计算，提高算法的效率和性能。

它在求解最短路径、最长公共子序列、背包问题等具有广泛的应用。

2. 请简要介绍红黑树的特点和应用场景。

答：红黑树是一种自平衡的二叉查找树，它具有以下特点：1) 每个节点都有一个颜色，红色或黑色；2) 根节点是黑色的；3) 叶子节点（NIL节点）都是黑色的；4) 如果一个节点是红色的，则它的两个子节点都是黑色的；5) 从根节点到叶子节点的路径上，不同路径上黑节点的个数相同。

计算机专业基础综合数据结构（集合）历年真题试卷汇编2(总分64, 做题时间90分钟)2. 填空题1.对于具有144个记录的文件，若采用分块查找法，且每块长度为8，则平均查找长度为__________。

【北方交通大学2001二、8】SSS_TEXT_QUSTI分值: 2答案:正确答案：14计算过程如下：144／8=18块，索引表顺序查找，故(18+1)／2+(8+1)／2=14。

2.有一个2000项的表，欲采用等分区间顺序查找方法进行查找，则每块的理想长度是 (1)，分成 (2) 块最为理想，平均查找长度是 (3) 。

【中国矿业大学2000一、6(3分)】SSS_TEXT_QUSTI分值: 2答案:正确答案：(1)45 (2)45 (3)46(索引表顺序查找)3.分块检索中，若索引表和各块内均用顺序查找，则有900个元素的线性表分成__________块最好；若分成25块，其平均查找长度为__________。

【北京工业大学1999一、5(2分)】SSS_TEXT_QUSTI分值: 2答案:正确答案：30，31．5(索引表顺序查找)4.执行顺序查找时，储存方式可以是(1)，二分法查找时，要求线性表(2)，分块查找时要求线性表(3)，而散列表的查找，要求线性表的存储方式是(4)。

【山东大学1998一、1(3分)】SSS_TEXT_QUSTI分值: 2正确答案：(1)顺序存储或链式存储 (2)顺序存储且有序(3)块内顺序存储，块间有序 (4)散列存储5.查找是非数值程序设计的一个重要技术问题，基本上分成(1)查找，(2)查找和(3)查找。

处理哈希冲突的方法有(4)、(5)、(6)和(7)。

【华北计算机系统工程研究所1999一(5分)】SSS_TEXT_QUSTI分值: 2答案:正确答案：(1)静态查找表 (2)动态查找表 (3)哈希表 (4)开放定址方法(5)链地址方法 (6)再哈希 (7)建立公共溢出区6.如果按关键码值递增的顺序依次将关键码值插入到二叉排序树中，则对这样的二叉排序树检索时，平均比较次数为__________。

计算机专业基础综合计算机网络（网络层）历年真题试卷汇编2(总分132, 做题时间90分钟)1. 单项选择题1.一个校园网中的4个部门都已经建立了自己的以太网，所有计算机使用的操作系统都相同，现在需要将这些部门的局域网互联起来，而且每个部门使用不同的网络地址(即每个部门一个子网)，应当选择的互联设备是____。

SSS_SINGLE_SELA 第2层交换机B 集线器C 路由器D 网桥分值: 2答案:C解析：考查异构网络互联。

能够互联不同网络地址的应该是网络层设备，第2层交换机和网桥是数据链路层设备，集线器是物理层设备，只有路由器是网络层设备，因此选C。

2.需要将一个局域网分为多个IP子网时，应当选用的网络互联设备是____。

SSS_SINGLE_SELA 中继器或集线器B 网桥C 路由器D 网关分值: 2答案:C解析：考查网络互联。

解决划分子网问题需要的也是网络层设备，中继器是物理层设备，而网关是在传输层上以实现网络互联，是最复杂的网络互联设备，仅用于两个高层协议不同的网络互联。

网关既可以用于广域网互联，也可以用于局域网互联。

网关是一种充当转换重任的计算机系统或设备，在使用不同的通信协议、数据格式或语言，甚至体系结构完全不同的两种系统之间，网关是一个翻译器。

3.在计算机网络中，能将异种网络互联起来，实现不同网络协议相互转换的网络互联设备是____。

【中南大学2007年】SSS_SINGLE_SELA 局域网交换机B 集线器C 路由器D 网关分值: 2答案:D解析：考查异构网络互联。

关4.在OSI中，完成整个网络系统内连接工作，为上一层提供整个网络范围内两个终端用户之间数据传输通路工作的是____。

【华中科技大学2001年】SSS_SINGLE_SELA 物理层B 数据链路层C 网络层D 运输层分值: 2答案:C解析：考查网络层的功能。

网络层的主要功能有：异构网络互联、路由选择与转发、拥塞控制、网络管理等。

计算机专业基础综合数据结构（概论）历年真题试卷汇编1(总分：64.00，做题时间：90分钟)一、单项选择题(总题数：15，分数：32.00)1.以下哪个数据结构不是多型数据类型?( )【中山大学1999一、3(1分)】（分数：2.00）A.栈B.广义表C.有向图D.字符串√解析：2.以下数据结构中，( )是非线性数据结构【中山大学1999一、4】（分数：2.00）A.树√B.字符串C.队D.栈解析：3.下列数据中，( )是非线性数据结构。

【北京理工大学2001六、1(2分)】（分数：2.00）A.栈B.队列C.完全二叉树√D.堆解析：解析：栈、队列是线性结构，堆是元素的序列，存在一维数组中，可以看成是线性结构。

完全二叉树是非线性结构，只是由于双亲和子女编号间存在固定关系，用一维数组存储更好。

4.连续存储设计时，存储单元的地址( )。

【中山大学1999一、1(1分)】（分数：2.00）A.一定连续√B.一定不连续C.不一定连续D.部分连续，部分不连续解析：5.以下属于逻辑结构的是( )。

【西安电子科技大学应用2001一、1】（分数：2.00）A.顺序表B.哈希表C.有序表√D.单链表解析：6.算法的计算量的大小称为计算的( )。

【北京邮电大学2000二、3(20／8分)】（分数：2.00）A.效率B.复杂性√C.现实性D.难度解析：7.算法的时间复杂度取决于( )。

【中科院计算所1998二、1(2分)】（分数：2.00）A.问题的规模B.待处理数据的初态C.A和B √解析：计算机算法指的是(1)，它必须具备(2)这三个特陛。

【南京理工大学1999一、1(2分)】（分数：4.00）(1).(1)（分数：2.00）A.计算方法B.排序方法C.解决问题的步骤序列√D.调度方法解析：(2).(2)（分数：2.00）A.可执行性、可移植性、可扩充性B.可执行性、确定性、有穷性√C.确定性、有穷性、稳定性D.易读性、稳定性、安全性解析：8.一个算法应该是( )。