(NEW)西安理工大学计算机科学与工程学院863数据结构历年考研真题汇编

2020年中科院计算机863考研真题回忆（题号和顺序仅供参考）选择题（选择题记住的不多了）1.进程进入临界区时首先要执行什么指令（特权指令、原子指令、向量指令，xx指令）2.对称密码和非对称密码的（不会，具体题也忘啦）3.用户使用操作系统资源时通过什么方法（系统调用）4.三级页表，虚拟地址24位，每级页号占8位，每个页表项4B，页面大小1KB，先一进程大小128KB，问其页表大小为（1KB，2KB，3KB，4KB）5.对称多处理系统能在多个处理器上同时运行线程还是进程6.下列措施是为了实现保密性的是（根目录只有root能访问）7.下列不是死锁预防措施的是（两阶段加锁，重启系统，假脱机，按顺序分配资源）8.RAID6的特征（6块磁盘并行，可以容忍1？2？3？块磁盘损坏）9.第一次打开文件时的操作（把超级快读入内存，把inode读入内存，xxx）10.CPU流水线5阶段时间分别为xxxns，问你时钟频率最高是多少11.采用程序查询方式，每次程序执行需xxx个周期，每秒需执行xxx次，主频给出，求程序查询占用时间比例问答题41.一般的文件系统在磁盘上有哪些组成部分，分别有哪些功能？42.进程共5个页面，工作集大小为4，给出一组页面访问顺序，问分别采用FIFO、LRU、Optimum（最优置换）算法时缺页次数及缺页时替换的分别为哪个页43.给出一个cache-主存地址转换结构图，问你cache的映射方式、总大小、块大小、写回策略等等（主要是看懂图，看出来是四路组相连）44.给了一个局域网拓扑图，主机通过交换机连接了一个www服务器和一个DNS服务器，让你简述访问www服务器主页的过程，用了哪些协议，分别是什么功能45.一个单周期CPU，5个阶段（取指、析址、执行、访存、写回）第一问问你一条指令执行时间，第二问将执行和访存结合成一个阶段（2选1）问你此时指令执行时间，第三问问这。

2022年西安理工大学数据科学与大数据技术专业《计算机组成原理》科目期末试卷B（有答案）一、选择题1、有效容量为128KB的Cache，每块16B，8路组相联。

字节地址为1234567H的单元调入该Cache，其tag应为（）。

A.1234HB.2468HC.048DHD.12345H2、若数据在存储器中采用以低字节地址为字地址的存放方式（小端存储），则十六进制数12345678H按自己地址由小到大依次存为（）。

A.12345678B.87654321C.78563412D.341278563、float型数据通常用IEEE754标准中的单精度浮点数格式表示。

如果编译器将float型变量x分配在一个32位浮点寄存器FR1中，且x=-8.25，则FR1的内容是（）。

A.C1040000HB.C2420000HC. C1840000HD.CIC20000H4、串行运算器结构简单，其运算规律是（）。

A.由低位到高位先行进行进位运算B.由低位到高位先行进行借位运算C.由低位到高位逐位运算D.由高位到低位逐位运算5、下列关于浮点数加减法运算的叙述中，正确的是（）。

I.对阶操作不会引起阶码上溢或下溢Ⅱ.右归和尾数舍入都可能引起阶码上溢Ⅲ.左归时可能引起阶码下溢IV.尾数溢出时结果不一定溢出A.仅Ⅱ、ⅢB. 仅I、Ⅱ、ⅢC.仅I、Ⅲ、IⅣD. I、Ⅱ、Ⅲ、Ⅳ6、下列关于多总线结构的叙述中，错误的是（）。

A.靠近CPU的总线速度较快B.存储器总线可支持突发传送方式C.总线之间需通过桥接器相连D.PCI-Expressx16采用并行传输方式7、某总线共有88根信号线，其中数据总线为32根，地址总线为20根，控制总线36根，总线工作频率为66MHz、则总线宽度为（），传输速率为（）A.32bit 264MB/sB.20bit 254MB/sC.20bit 264MB/sD.32bit 254MB/s8、下列关于配备32位微处理器的计算机的说法中，正确的是（）。

第10章排序及答案后面红色部分一、选择题1．某内排序方法的稳定性是指( )。

【南京理工大学 1997 一、10（2分）】A．该排序算法不允许有相同的关键字记录 B．该排序算法允许有相同的关键字记录C．平均时间为0（n log n）的排序方法 D．以上都不对2．下面给出的四种排序法中( )排序法是不稳定性排序法。

【北京航空航天大学 1999 一、10 （2分）】A. 插入B. 冒泡C. 二路归并D. 堆积3．下列排序算法中，其中（）是稳定的。

【福州大学 1998 一、3 (2分)】A. 堆排序，冒泡排序B. 快速排序，堆排序C. 直接选择排序，归并排序D. 归并排序，冒泡排序4．稳定的排序方法是（）【北方交通大学 2000 二、3（2分）】A．直接插入排序和快速排序 B．折半插入排序和起泡排序C．简单选择排序和四路归并排序 D．树形选择排序和shell排序5．下列排序方法中，哪一个是稳定的排序方法？（）【北方交通大学 2001 一、8（2分）】A．直接选择排序 B．二分法插入排序 C．希尔排序 D．快速排序6．若要求尽可能快地对序列进行稳定的排序，则应选（A．快速排序 B．归并排序 C．冒泡排序）。

【北京邮电大学 2001 一、5（2分）】7．如果待排序序列中两个数据元素具有相同的值，在排序前后它们的相互位置发生颠倒，则称该排序算法是不稳定的。

（）就是不稳定的排序方法。

【清华大学 1998 一、3 (2分）】A．起泡排序 B．归并排序 C．Shell排序 D．直接插入排序 E．简单选择排序8．若要求排序是稳定的，且关键字为实数，则在下列排序方法中应选（）排序为宜。

A．直接插入 B．直接选择 C．堆 D．快速 E．基数【中科院计算所 2000 一、5（2分）】9．若需在O(nlogn)的时间内完成对数组的排序，且要求排序是稳定的，则可选择的排序方2法是（）。

A. 快速排序B. 堆排序C. 归并排序D. 直接插入排序【中国科技大学 1998 二、4（2分）】【中科院计算所 1998 二、4（2分）】10．下面的排序算法中，不稳定的是（）【北京工业大学 1999 一、2 (2分)】A.起泡排序B.折半插入排序C.简单选择排序D.希尔排序E.基数排序F.堆排序。

数据结构考研真题及其答案HEN system office room 【HEN16H-HENS2AHENS8Q8-HENH1688】一、选择题1. 算法的计算量的大小称为计算的（ B ）。

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

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

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

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

计算机专业基础综合数据结构（排序）历年真题试卷汇编6(总分：108.00，做题时间：90分钟)一、单项选择题(总题数：44，分数：88.00)1.某内部排序方法的稳定性是指____。

【南京理工大学1997年】（分数：2.00）A.该排序算法不允许有相同的关键字记录B.该排序算法允许有相同的关键字记录C.平均时间为O(nlogn)的排序方法D.以上都不对√解析：解析：考查排序算法的稳定性。

如果排序前后有相同关键字的记录的前后顺序不变，则称此排序是稳定的。

2.若要求尽可能快地对序列进行稳定的排序，则应选____。

【北京邮电大学2001年】（分数：2.00）A.快速排序B.归并排序√C.冒泡排序D.根排序解析：解析：考查排序算法的稳定性及算法效率。

归并排序和冒泡排序是稳定的，冒泡排序的平均时间复杂度为O(n 2 )，归并排序的平均时间复杂度为O(nlog 2 n)。

3.下列排序方法中，____是稳定的排序方法。

【北方交通大学2001】（分数：2.00）A.直接选择排序B.二分法插入排序√C.希尔排序D.快速排序解析：解析：考查稳定的排序算法有哪些。

插入排序、冒泡排序、二路归并排序、基数排序是稳定的排序算法，选择排序、希尔排序、快速排序、堆排序属于不稳定排序。

4.对有n个记录的表做直接插入排序，在最好情况下，需比较____次关键字。

【华中科技大学2006年】（分数：2.00）A.n-1 √B.n+1C.n／2D.n(n-1)／2解析：解析：考查最好情况下直接插入排序比较次数。

在最好的情况下，即初始序列有序列，则每次循环只需与前一个元素比较1次，且不需要移动，总的比较次数为n—1。

5.对n个不同的数据利用冒泡法从小到大排序，在下列哪种情况下元素交换的次数最多____。

【北京交通大学2007年】（分数：2.00）A.从大到小排列好的√B.从小到大排列好的C.元素无序D.元素基本有序解析：解析：考查冒泡排序最差的情况。

理工大学计算机专业基础历考研真题汇编附答案新编Company number【1089WT-1898YT-1W8CB-9UUT-92108】北京理工大学计算机专业基础历年考研真题汇编最新资料，WORD格式，可编辑修改！目录说明：2006、2007年计算机专业基础科目代码是477，2016年计算机专业基础的科目代码是813，本书以此为准此外，本书还收录了4套兄弟院校计算机基础考研真题。

第一部分考研真题考研真题汇编2007年北京理工大学477计算机专业基础考研真题2006年北京理工大学477计算机专业基础考研真题第二部分兄弟院校真题汇编2014年北京科技大学文法学院829计算机基础考研真题北京科技大学2014年硕士学位研究生入学考试试题试题编号： 829 试题名称：计算机基础（共1 页）适用专业：教育经济与管理（45分）。

二、分析信息技术在高校课堂教学中应用的相关影响因素（45分）三、论述数据挖掘技术在教育中的应用（60分）北京科技大学2013年硕士学位研究生入学考试试题试题编号： 829 试题名称：计算机基础（共 1 页）适用专业：教育经济与管理说明：所有答案必须写在答题纸上，做在试题或草稿纸上无效。

1．何为信息技术教育？试设计一个教师-学生教学互动网站。

（70分）2．如何进行高校综合性学生网站评价？（80分）北京科技大学2011年硕士学位研究生入学考试试题试题编号： 829 试题名称：计算机基础（共 1 页）适用专业：教育经济与管理说明：所有答案必须写在答题纸上，做在试题或草稿纸上无效。

可以带笔、尺和计算器。

一、填空题（每题3分，10题共30分）1．网络互连的目的就是实现更广泛的( )。

2．CIS系统的硬件连接件主要包括( )和通信媒体。

3．SNMP管理操作中，trap操作用来( )。

4．无线连接主要有通过微波连接和通过( )两种方式。

5．为了防止网络受到物理危害应采取( )的措施。

6．IP地址分( )和( )两部分。

2022年西安理工大学计算机科学与技术专业《数据库原理》科目期末试卷A（有答案）一、填空题1、在设计局部E-R图时，由于各个子系统分别有不同的应用，而且往往是由不同的设计人员设计，所以各个局部E-R图之间难免有不一致的地方，称为冲突。

这些冲突主要有______、______和______3类。

2、视图是一个虚表，它是从______导出的表。

在数据库中，只存放视图的______，不存放视图对应的______。

3、关系代数运算中，基本的运算是______________、______________、______________、______________和______________。

4、在一个关系R中，若每个数据项都是不可再分割的，那么R一定属于______。

5、设某数据库中有商品表（商品号，商品名，商品类别，价格）。

现要创建一个视图，该视图包含全部商品类别及每类商品的平均价格。

请补全如下语句： CREATE VIEW V1（商品类别，平均价格）AS SELECT商品类别，_____FROM商品表GROUP BY商品类别；6、数据仓库主要是供决策分析用的______，所涉及的数据操作主要是______，一般情况下不进行。

7、在SQL语言中，为了数据库的安全性，设置了对数据的存取进行控制的语句，对用户授权使用____________语句，收回所授的权限使用____________语句。

8、若事务T对数据对象A加了S锁，则其他事务只能对数据A再加______，不能加______，直到事务T释放A上的锁。

9、DBMS的完整性控制机制应具备三个功能：定义功能，即______；检查功能，即______；最后若发现用户的操作请求使数据违背了完整性约束条件，则采取一定的动作来保证数据的完整性。

10、数据库恢复是将数据库从______状态恢复到______的功能。

二、判断题11、关系中任何一列的属性取值是不可再分的数据项，可取自不同域中的数据。

[考研类试卷]计算机专业基础综合数据结构（集合）历年真题试卷汇编5.doc[考研类试卷]计算机专业基础综合数据结构（集合）历年真题试卷汇编5一、填空题1 对于具有144个记录的文件，若采用分块查找法，且每块长度为8，则平均查找长度为__________。

【北方交通大学2001二、8】2 有一个2000项的表，欲采用等分区间顺序查找方法进行查找，则每块的理想长度是 (1)，分成 (2) 块最为理想，平均查找长度是 (3) 。

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

【北京工业大学1999一、5(2分)】4 执行顺序查找时，储存方式可以是(1)，二分法查找时，要求线性表(2)，分块查找时要求线性表(3)，而散列表的查找，要求线性表的存储方式是(4)。

【山东大学1998一、1(3分)】5 查找是非数值程序设计的一个重要技术问题，基本上分成(1)查找，(2)查找和(3)查找。

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

【华北计算机系统工程研究所1999一(5分)】6 如果按关键码值递增的顺序依次将关键码值插入到二叉排序树中，则对这样的二叉排序树检索时，平均比较次数为__________。

【山东大学1999二、1(4分)】7 在含有n个结点的二叉排序树中查找一个关键字，进行关键字比较次数的最大值是__________。

【北京交通大学2004一、15(2分)】8 在二叉排序树上成功地找到一个结点，在平均情况下的时间复杂性是：__________，在最坏情况下的时间复杂性是__________。

【上海交通大学2004五、1(15／4分)】9 AVL树__________是完全二叉树；完全二叉树__________是AVL 树。

【电子科技大学2005二、5(1分)】10 一棵深度为k的平衡二叉树，其每个非终端结点的平衡因子均为0，则该树共有__________个结点。

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

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

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

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

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

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

2022年西安理工大学数据科学与大数据技术专业《计算机组成原理》科目期末试卷A（有答案）一、选择题1、下面关于计算机Cache的论述中，正确的是（）。

A.Cache是一种介于主存和辅存之间的存储器，用于主存和辅存之间的缓冲存储B.如果访问Cache不命中，则用从内存中取到的字节代替Cache中最近访问过的字节C.Cache的命中率必须很高，一般要达到90%以上D.Cache中的信息必须与主存中的信息时刻保持一致2、在全相联映射、直接映射和组相联映射中，块冲突概率最小的是（）。

A.全相联映射B.直接映射C.组相联映射D.不一定3、ALU属于（）。

A.时序电路B.控制器C.组合逻辑电路D.寄存器4、有如下C语言程序段：（）short si=-32767；unsigned short usi=si；执行上述两条语句后，usi的值为A.-32767B.32767C.32768D.327695、假设有7位信息码010101，则低位增设偶校验位后的代码和低位增设奇校验位后的代码分别为（）。

A.01101010 01101010B.0101010 01101011C.01101011 01101010D.01101011 011010116、下列关于同步总线的说法中，正确的有（）。

I.同步总线一般按最慢的部件来设置公共时钟II.同步总线一般不能很长III.同步总线一般采用应答方式进行通信IV.通常，CPU内部总线、处理器总线等采用同步总线A. I，IIB. I，II，IVC.III，IVD.II，III，IV7、总线的半同步通信方式是（）。

A.既不采用时钟信号，也不采用握手信号B.只采用时钟信号，不采用握手信号C.不采用时钟信号，只采用握手信号D.既采用时钟信号，又采用握手信号8、计算机（）负责指令译码。

A.算术逻辑单元B.控制单元（或者操作码译码器）C.存储器电路D.输入/输出译码电路9、CPU中的译码器要用（）。

2021年西安理工大学数据科学与大数据技术专业《计算机组成原理》科目期末试卷B（有答案）一、选择题1、采用八体并行低位交叉存储器，设每个体的存储容量为32K×16位，存储周期为400ns，下述说法中正确的是（）。

A.在400ns内，存储器可向CPU提供2位二进制信息B.在l00ns内，每个体可向CPU提供27位二进制信息C.在400ns内，存储器可向CPU提供2位二进制信息D.在100ns内，每个体可向CPU提供2位二进制信息2、关于LRU算法，以下论述正确的是（）。

A.LRU算法替换掉那些在Cache中驻留时间最长且未被引用的块B.LRU算法替换掉那些在Cache中驻留时间最短且未被引用的块C.LRU算法替换掉那些在Cache中驻留时间最长且仍在引用的块D.LRU算法替换掉那些在Cache中驻留时间最短且仍在引用的块3、并行加法器中，每位全和的形成除与本位相加两数数值位有关外，还与（）有A.低位数值大小B.低位数的全和C.高位数值大小D.低位数送来的进位4、若x=103，y=-25，则下列表达式采用8位定点补码运算时，会发生溢出的是（）。

A.x+yB.-x+yC.x-yD.x-y5、假设编译器规定int 和shot类型长度分别为32位和16位，若有下列C语言语句：unsigned short x=65530；unsigned int y=x；得到y的机器数为（）。

A.00007FFAHB.0000 FFFAHC.FFFF 7FFAHD.FFFF FFFAH6、控制总线主要用来传送（）。

I.存储器和1/O设备的地址码II.所有存储器和I/O设备的时序信号III.所有存储器和1/O设备的控制信号IV.来自I/O设备和存储器的响应信号A.II、IIIB. I，III，IVC. III，IVD.II，III. IV7、在集中式总线控制中，响应时间最快的是（）。

A.链式查询B.计数器定时查询C.独立请求D.分组链式查询8、下列关于计算机操作的单位时间的关系中，正确的是（）。

2022年西安理工大学计算机科学与技术专业《数据结构与算法》科目期末试卷A（有答案）一、选择题1、若需在O（nlog2n）的时间内完成对数组的排序，且要求排序是稳定的，则可选择的排序方法是（）。

A.快速排序B.堆排序C.归并排序D.直接插入排序2、将两个各有N个元素的有序表归并成一个有序表，其最少的比较次数是（）。

A.NB.2N-1C.2ND.N-13、静态链表中指针表示的是（）。

A.下一元素的地址B.内存储器的地址C.下一元素在数组中的位置D.左链或右链指向的元素的地址4、下面关于串的叙述中，不正确的是（）。

A.串是字符的有限序列B.空串是由空格构成的串C.模式匹配是串的一种重要运算D.串既可以采用顺序存储，也可以采用链式存储5、循环队列A[0..m-1]存放其元素值，用front和rear分别表示队头和队尾，则当前队列中的元素数是（）。

A.（rear-front+m）%mB.rear-front+1C.rear-front-1D.rear-front6、若一棵二叉树的前序遍历序列为a，e，b，d，c，后序遍历序列为b， c，d，e，a，则根结点的孩子结点（）。

A．只有e B．有e、b C．有e、c D．无法确定7、下列选项中，不能构成折半查找中关键字比较序列的是（）。

A．500，200，450，180 B．500，450，200，180C．180，500，200，450 D．180，200，500，4508、有关二叉树下列说法正确的是（）。

A.二叉树的度为2B.一棵二叉树的度可以小于2C.二叉树中至少有一个结点的度为2D.二叉树中任何一个结点的度都为29、一棵非空的二叉树的前序序列和后序序列正好相反，则该二叉树一定满足（）。

A.其中任意一个结点均无左孩子B.其中任意一个结点均无右孩子C.其中只有一个叶结点D.其中度为2的结点最多为一个10、数据序列（8，9，10，4，5，6，20，1，2）只能是下列排序算法中的（）的两趟排序后的结果。

西安理工大学计算机科学与工程学院硕士研究生入学考试课程《数据结构》考试大纲科目代码：863科目名称：数据结构第一部分考试说明一、考试性质数据结构是计算机各专业的专业基础课。

考核目标是测试计算机科学与技术及相近各专业的本科毕业生对于该课程的知识掌握程度,以保证被录取者具有本学科基本的专业理论基础及程序设计能力,以利于计算机科学与技术及软件工程学科的导师择优选拔硕士研究生。

考试对象为参加全国硕士研究生入学考试的本科毕业生和具有同等学力的在职人员。

二、考试范围各种基本类型的数据结构的概念、特征、操作、存储表示和基本应用；各种基本查找表的概念、特征及其查找方法；基本的内排序方法及其应用；用C语言(或C++)进行算法描述,并对算法进行分析。

三、评价目标考查基本概念、基本知识、基本方法的基础上，注重考查学生运用基本知识来分析和解决实际问题的能力,注重考查算法和程序设计的能力。

具体要求见本考试大纲第二部分的“考查要点”。

四、考试形式与试卷结构1.答卷方式:闭卷,笔试。

2.答题时间:180 分钟。

3.考查内容及其考查比例基本概念、基本知识、基本方法约占50%～60%；综合应用、算法和程序设计与算法分析约占50%～40%。

4.试卷结构与考试题型试卷共150分,基本的考试题型有：(1)单项选择题和多项选择题(基本概念)；(2)填空题(基本知识、基本方法)；(3)简答题（概念理解）；(4)应用题(基本方法的应用)；(5)算法和程序设计题；五、教材和参考书教材: 《数据结构》(C语言版)，严蔚敏、吴伟民编著,清华大学出版社,2009.6第二部分考查要点1.数据结构基本概念和术语1）了解数据元素、数据结构、抽象数据类型、存储结构等概念；了解算法概念及算法设计的基本要求；2）掌握算法分析方法、语句的频度和估算时间复杂度、空间复杂度分析方法。

2.线性表1）理解线性表的定义和基本操作；线性表的抽象数据类型定义；2）掌握线性表的顺序存储结构及应用方法；3）掌握线性表的链式存储结构(单链表,双链表,循环链表)。

西安理⼯考研数据结构初试题西安理⼯⼤学2016年攻读硕⼠学位研究⽣⼊学考命题纸考试科⽬：数据结构863⼀、单项选择题(共30分，每⼩题2分)1、考虑将栈定义为顺序存储的栈还是链式存储的栈，是在选择数据的( d )。

a.逻辑结构b.物理结构c.相互关系d.操作⽅法2、在⼀个长度为n的顺序线性表中顺序査找值为x的元素时，查找成功时的平均查找长度为( c )(假定找每个元素的概率都相等)a.nb.(n+1)/2c.n/2d.(n-1)/23、组成数据的基本单位是( c )。

a.数据项b.数据类型c.数据元素d.数据变量4、设数据结构A=(D，R)，其中D={1，2，3，4}，R={r}，r={<1，2>，<2，3>，<2，4>，<4，1>}，则数据结构A是( c )。

a.线性结构b树型结构 c.图型结构 d.集合5、深度为K(K>=1)的⼆叉树⾄多有(c)个结点。

a.2k+1b.2k-1c.2k-1d.2k-16、设某完全⽆向图中有n个顶点，则该完全⽆向图中有(a)条边。

a.n(n-1)/2b.n(n-1)c.n2d.n2-17、⼆叉链表作为⼆叉树的存储结构，在具有n(n>0)个结点的⼆叉链表中空链域的个数为( c )a.2n-1b. n-1c. n+1d.2n+18、已知⼀个有向图的邻接矩阵，要想删除所有以第i个点为起始点的弧，应该(c)a.删除邻接矩阵的第i⾏b.除邻接矩阵的第i列c.将邻接矩阵的第i⾏置零d.将邻接矩阵的第i列置零9、设⽆向图G中有n个点e条边，则其对应的邻接表中的表头结点和表结点的个数分别为(d)。

课本164页a. n, eb.e,nc. 2n, ed.n,2e10、设某强通图中有n个顶点，则该强道通图中⾄少有(c)条边。

a. n(n-1)b. n+1c. nd. n(n+1)11、下列四种排序中( a )的空间复杂度最⼤。