2008年华南理工大学831计算机专业综合(数据结构、操作系统)考研试题

【华南理⼯⼤学2012年考研专业课真题】计算机专业综合（数据结构、操作系统）2012831华南理⼯⼤学2012年攻读硕⼠学位研究⽣⼊学考试试卷（请在答题纸上做答，试卷上做答⽆效，试后本卷必须与答题纸⼀同交回）科⽬名称：计算机专业综合(数据结构、操作系统)适⽤专业：计算机技术(专硕)本卷满分：150分共 4 页数据结构部分⼀、选择题（每⼩题2分，共20分）1. 设数组a[1..10,5..15]的元素以⾏为主序存放，每个元素占⽤4个存储单元，则数组元素a[i,j] (1≤i≤10,5≤j≤15)的地址计算公式为______________。

A．a-204+2i+j B. a-204+40i+4j C．a-84+i+j D. a-64+44i+4j2. 给定⼀个有n个元素的线性表。

若采⽤顺序存储结构，则在等概率前提下，向其插⼊⼀个元素需要移动的元素个数平均为______________。

A．n+1 B. n/2 C．(n+1)/2 D. n3. 采⽤邻接表表⽰⼀有向图，若图中某顶点的⼊度和出度分别为d1和d2，则该顶点对应的单链表的节点数为______________。

A．d1 B. d2 C．d1-d2 D. d1+d24. 设有100个节点，⽤⼆分法查找时，最⼤⽐较次数是______________。

A．25 B. 50 C．10 D. 75. 若长度为n的线性表采⽤顺序存数结构，在其第i个位置插⼊⼀个新元素算法的时间复杂度是______________。

A．O(log2n) B.O(1) C．O(n) D. O (n2)6. ⼀棵124个叶结点的完全⼆叉树最多有__________个结点。

A．247 B. 248 C．249 D. 2507. 将上万个⼀组⽆序并且不相等的正整数序列，存放于顺序存储结构中，采⽤__________⽅法能够最快地查找出其中最⼤的正整数。

A．快速排序 B. 插⼊排序C．选择排序 D. 归并排序8. 前序遍历序列和中序遍历序列相同的⼆叉树为__________。

华南理工考研计算机历年真题华南理工大学2004年攻读硕士学位研究生入学考试试卷（试卷上做答无效，请在答题纸上做答，试后本卷必须与答题纸一同交回）科目名称：计算机专业综合一(组成原理、数据结构、操作系统)适用专业：计算机系统结构、计算机应用技术、软件工程、计算机应用技术I. 计算机组成原理试题（50分）一．填空题（共10分）1．计算机的工作过程主要是周而复始地A、B和C的过程。

2．在浮点运算中，当运算结果阶码大于所能表示的A时称为溢出，若阶码用双符号S0′S0的移码表示，则当S0′S0 =B时为溢出。

3．双端口存储器和多模块交叉存储器属于A 存储器结构；前者采用 B 并行技术，后者采用 C 并行技术。

4．在微程序控制器中，一般采用较简单的A 、B 二级时序体制。

5．CPU响应中断时保护两个关键的硬件状态是A 和B 。

二．选择题（共6分）1．设浮点数的阶为8位（其中1位阶符），用移码表示，尾数为24位（其中1位数符），用原码表示。

则它所能表示的最大规格化正数是（）。

A．(27-1)×(1-2-23 ) B．×(1-2-23 )C．×(1-2-23 ) D．×(1-2-22 )2．下列说法正确的是（）。

A. 微程序控制方式和硬布线方式相比较，前者可以使指令的执行速度更快B. 若采用微程序控制方式，则可用μPC取代PCC. 控制存储器可以用ROM实现D. 指令周期也称为CPU周期3．下列说法正确的是（）。

A. 程序中断过程是由硬件和中断服务程序共同完成的B. 每条指令的执行过程中，每个总线周期要检查一次有无中断请求C. 检测有无DMA请求，一般安排在一条指令执行过程的末尾D. 中断服务程序的最后指令是无条件转移指令三．完成下列各题（共36分）1．设[A]补＝an-1an-2…a1 a0，式中an-1为补码符号位，求证真值：（8分）2．假设主存只有a，b，c三个页框，组成a进c 出的FIFO队列进程，访问页面的序列是0，1，3，4，3，2，0，2，1，3，2号。

计算机专业基础综合数据结构（查找）历年真题试卷汇编1(总分108,考试时间90分钟)1. 单项选择题1. 顺序查找法适合于存储结构为____的线性表。

【北京航空航天大学2002年】A. 顺序存储结构或链式存储结构B. 散列存储结构C. 索引存储结构D. 压缩存储结构2. 若查找每个记录的概率均等，则在具有n个记录的连续顺序文件中采用顺序查找法查找一个记录，其平均查找长度(ASL)为____。

【北京航空航天大学2004年】A. (n—1)／2B. n／2C. (n+1)／2D. n3. 当采用分块查找时，数据的组织方式为____。

【太原科技大学2007年】A. 数据分成若干块，每块内数据有序B. 数据分成若干块，每块内数据不必有序，但块间必须有序，每块内最大(或最小)的数据组成索引块C. 数据分成若干块，每块内数据有序，每块内最大(或最小)的数据组成索引块D. 数据分成若干块，每块(除最后一块外)中数据个数需相同4. 对有2500个记录的索引顺序表(分块表)进行查找，最理想的块长为____。

【华中科技大学2007年】A. 50B. 125C. 500D. [log22500]5. 下面关于二分查找的叙述正确的是____。

【南京理工大学1996年】A. 表必须有序，表可以顺序方式存储，也可以链表方式存储B. 表必须有序且表中数据必须是整型、实型或字符型C. 表必须有序，而且只能从小到大排列D. 表必须有序，且表只能以顺序方式存储6. 当n足够大时，在按值有序的顺序表中进行折半查找，当查找概率相等的情况下，其查找成功的平均查找长度是____。

【北京航空航天大学2002年】A. (n+1)／2B. n／2C. log2(n+1)一1D. log2(n+1)7. 在具有15个记录的排序连续顺序文件上采用折半查找方法查找一个文件中不存在的记录．需要进行____次关键字值的比较。

【北京航空航天大学2004年】A. 0B. 4C. 5D. 158. 对一个长度为50的有序表进行折半查找，最多比较____次就能查找出结果。

810华南理工大学2008年攻读硕士学位研究生入学考试试卷（请在答题纸上做答，试卷上做答无效，试后本卷必须与答题纸一同交回）科目名称：物流信息基础（含数据库、数据结构）适用专业：物流工程与管理共 10 页说明：本卷分为数据库和数据结构共两部分内容，全卷满分150分，其中数据库部分满分80分，数据结构满分70分。

I．数据库部分一．单项选择题，共10题，每题2分。

1.域（Domain）的概念是（ ）。

A.属性的存储空间B.属性的取值范围C.属性的物理空间D.属性的复杂程度2.组成关系数据库内模式的是（ ）。

A.数据的概念模型B.存储文件的物理结构C.概念模式与内模式的映射关系D.以上都不是3.在通常情况下，下面的关系中不可以作为关系数据库的关系是（ ）。

A．R1（学生号，学生姓名，性别）B．R2（学生号，学生姓名，班级号）C．R3（学生号，学生姓名，宿舍号）D．R4（学生号，学生姓名，简历）4.参加差运算的两个关系（ ）。

A．属性个数可以不相同B．属性个数必须相同C．一个关系包含另一个关系的属性D．属性名必须相同5.SQL中，与NOT IN 等价的操作符是（ ）。

A．=SOME B．<>SOMEC．=ALL D．<>ALL6.关系模式S（A，B，C，D）中，存在函数依赖：A→B，C→D，D→C，则z SC（Sno, Cno, Grade）我们规定：若某同学选了一门课，但该同学不参加该课程考试，则该同学在该门课程的成绩取NULL值。

已知“数据库”这门课程的编号（Cno）为“DB001”，甲开发人员编写以下SQL语句计算该课程平均分：Select sum(Grade)/Count(Sno) from SC where Cno=’DB001’而乙开发人员则认为该句SQL应该为：Select avg(Grade) from SC where Cno=’DB001’数据库管理员丙认为在结果上两者是等价的，但由于乙使用的是系统函数，所以执行效率更高，所以推荐使用乙的写法。

华南理工大学考研真题2010计算机专业综合831华南理工大学2010年攻读硕士学位研究生入学考试试卷（试卷上做答无效，请在答题纸上做答，试后本卷必须与答题纸一同交回）科目名称：计算机专业综合（数据结构和操作系统）适用专业：计算机技术共 4 页数据结构部分一、选择题（每小题2分，共20分）1．判断一个循环队列QU(最多元素为m0)为满队列的条件是（）。

A、QU->front==QU?rearB、QU->front!=QU?rearC、 QU->front==(QU?rear+1)%m0D、QU->front!=(QU?rear+1)%m02．向一个栈顶指针为HS的链栈中插入一个s所指结点时，则执行（）。

A、HS?next=s;B、s?next=HS?next; HS?next=s;C、s?next=HS; HS=s;D、s?next=HS; HS=HS?next;3．设矩阵A是一个对称矩阵，为了节省存储，将其下三角部分按行序存放在一维数组B[1,n(n-1)/2]中，对下三角部分中任一元素a i,j(i≥j),在一维数组B中下标k的值是（）。

A、i(i-1)/2+j-1B、i(i-1)/2+jC、i(i+1)/2+j-1D、i(i+1)/2+j4. 设有一个无向图G=(V,E)和G'=(V',E')，如果G'为G的生成树，则下面不正确的说法是( )。

A. G'为G的子图B. G'为G的一个无环子图C. G'为G的极小连通子图且V'=VD. G'为G的连通分量5.在线索化二叉树中，t所指结点没有左子树的充要条件是（）。

A、t?left=NULLB、t?ltag=1C、t?ltag=1且t?left=NULLD、以上都不对6. 具有五层结点的二叉平衡树至少有（）个结点。

A、10B、12C、15D、177. 采用邻接表存储的图的深度优先遍历算法类似于二叉树的（）。

第一章绪论本次练习有19题，你已做19题，已提交19题，其中答对19题。

.A. B. C..A. B. C.A. B. C.答题： 对. 错. （已提交）参考答案：×问题解析：2. 数据结构中，与所使用的计算机无关的是数据的 结构；A. 存储B. 物理C. 逻辑D. 物理和存储答题： A. B. C. D. （已提交）参考答案：C问题解析：3. 计算机算法指的是：A. 计算方法B. 排序方法C. 解决问题的有限运算序列D. 调度方法答题： A. B. C. D. （已提交）参考答案：C问题解析：3. 数据的逻辑结构是指数据的各数据项之间的逻辑关系。

（ ）答题： 对. 错. （已提交）参考答案：×问题解析：4. 计算机算法必须具备输入、输出和 等5个特性。

A. 可行性、可移植性和可扩充性B. 可行性、确定性和有穷性C. 确定性、有穷性和稳定性D. 易读性、稳定性和安全性答题： A. B. C. D. （已提交）参考答案：B问题解析：4. 数据的物理结构是指数据在计算机内的实际存储形式。

（ ）答题： 对. 错. （已提交）参考答案：√问题解析：. . . . . . . .本次练习有32题，你已做32题，已提交32题，其中答对15题。

当前页有10题，你已做10题，已提交10题，其中答对9题。

1.下述哪一条是顺序存储结构的优点？（）A．存储密度大B．插入运算方便C．删除运算方便D．可方便地用于各种逻辑结构的存储表示答题： A. B. C. D. （已提交）参考答案：A问题解析：2.下面关于线性表的叙述中，错误的是哪一个？（）A．线性表采用顺序存储，必须占用一片连续的存储单元。

B．线性表采用顺序存储，便于进行插入和删除操作。

C．线性表采用链接存储，不必占用一片连续的存储单元。

D．线性表采用链接存储，便于插入和删除操作。

答题： A. B. C. D. （已提交）参考答案：B问题解析：3.线性表是具有n个（）的有限序列（n>0）。

2022年华南理工大学计算机科学与技术专业《计算机系统结构》科目期末试卷A（有答案）一、选择题1、推出系列机的新机器，不能更改的是( )A.原有指令的寻址方式和操作码B.系统总线的组成C.数据通路宽度D.存贮芯片的集成度2、计算机系统结构不包括（）A.主存速度B.机器工作状态C.信息保护D.数据表示3、从计算机系统结构上讲，机器语言程序员所看到的机器属性是（）A.计算机软件所要完成的功能B.计算机硬件的全部组成C.编程要用到的硬件组织D.计算机各部件的硬件实现。

4、下列说法正确的是（）A."一次重叠"是一次解释一条指令B."一次重叠"是同时解释相邻两条指令C.流水方式是同时只能解释两条指令D."一次重叠"是同时可解释很多条指令5、非线性流水线是指( )A.一次运算中使用流水线中的多个功能段B.一次运算中要多次使用流水线中的某些功能段C.流水线中某些功能段在各次运算中的作用不同D.流水线的各个功能段在各种运算中有不同的组合6、计算机系统的层次结构按照由高到低的顺序分别为（）。

A.高级语言机器级，汇编语言机器级，传统机器语言机器级，微程序机器级B.高级语言机器级，应用语言机器级，汇编语言机器级，微程序机器级C.应用语言机器级，传统机器语言机器级，汇编语言机器级，操作系统机器级D.应用语言机器级，操作系统机器级，微程序机器级，传统机器语言机器级7、对汇编语言程序员透明的是（）A.I/O方式中的DMA访问B.浮点数据表示C.访问方式保护D.程序性中断8、计算机系统结构不包括( )。

A.主存速度B.机器工作状态C.信息保护D.数据9、除了分布处理、MPP和机群系统外，并行处理计算机按其基本结构特征可分为流水线计算机，阵列处理机，多处理机和（）四种不同的结构。

A.计算机网络B.控制流计算机C.机群系统D.数据流计算机10、对机器语言程序员透明的是（）A.中断字B.主存地址寄存器C.通用寄存器D.条件码11、设16个处理器编号分别为0，1，2，...，15用Cube，互联函数时，第10号处理机与第（）号处理机相联。

计算机专业基础综合数据结构（图）历年真题试卷汇编6(总分：60.00，做题时间：90分钟)一、单项选择题(总题数：6，分数：12.00)1.有n个顶点、e条边的图G采用邻接表存储，则拓扑排序算法的时间复杂度为( )。

【南京理工大学2005一、2(1分)】A.O(n)B.O(n+e) √C.O(n * e)D.O(n 2 )2.在下列网中，( )是边不带权值的图。

【华南理工大学2007】A.邮电图B.AOV网√C.公路网D.AOE网3.关键路径是AOE网中( )。

【中南大学2003一、10(1分)】A.从始点到终点的最短路径B.从始点到终点的最长路径√C.从始点到终点的边数最多的路径D.从始点到终点的边数最少的路径4.下面关于求关键路径的说法不正确的是( )。

【南京理工大学1998一、12(2分)】A.求关键路径是以拓扑排序为基础的B.一个事件的最早开始时间同以该事件为尾的弧的活动最早开始时间相同C.一个事件的最迟开始时间为以该事件为尾的弧的活动最迟开始时间与该活动的持续时间的差√D.关键活动一定位于关键路径上C的叙述有误。

一个事件的最迟开始时间，是该事件所有后继事件(顶点)最迟开始时间和相应活动持续时间差的最小值。

例如，某事件(设为E)有3个后继事件(顶点)，它到3个后继事件有3条弧(活动)，求出3个后继事件和弧头指向它的那个活动的持续时间的差，取最小值就得到E的最迟开始时间。

5.下列关于AOE网的叙述中，不正确的是( )。

【北方交通大学1999一、7(3分)】【北京工业大学1999一、1(2分)】【哈尔滨工业大学2004二、3(1分)】A.关键活动不按期完成就会影响整个工程的完成时间B.任何一个关键活动提前完成，那么整个工程将会提前完成√C.所有的关键活动提前完成，那么整个工程将会提前完成D.某些关键活动若提前完成，那么整个工程将会提前完成B之所以错误，是因为只有减少所有关键路径上共有的关键活动，才能缩短工期。

[考研类试卷]计算机专业基础综合数据结构（集合）历年真题试卷汇编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，则该树共有__________个结点。

831华南理工大学2013年攻读硕士学位研究生入学考试试卷（试卷上做答无效，请在答题纸上做答，试后本卷必须与答题纸一同交回）科目名称：计算机专业综合(数据结构、操作系统)适用专业：计算机技术(专硕)共4页数据结构一．选择题（每小题2分，共20分）1.一个非空二叉树的中序序列是DBEACGF，后序序列是DEBGFCA，则其前序序列是____。

A）ABCDEFG B）ABDEFGC C）ABEFGDE D）ABDECFG2.顺序存储的循环队列，存储空间大小为n，队头结点下标为front，队尾结点下标为rear。

则此循环队列中的元素个数为______。

A）n+front-rear B)rear-front+1C)(rear-front)%n D)(n+rear-front+1)%n 3.下列排序方法中，平均情况下的时间复杂度是O(nlogn)且稳定的方法是___。

A）归并排序B）快速排序C）简单插入排序D）堆排序4.深度为5的5阶B树，第4层（根结点为第1层）共有最少______个关键字。

A）66B）53C）20D）795.已知广义表((c),(a),(d),((d,f)))，则以下说法正确的是_____。

A）表长为4，表头为(c)，表尾为((d,f))B）表长为4，表头为(c)，表尾为((a),(d),((d,f)))C）表长为5，表头为(c)，表尾为fD）表长为5，表头为©，表尾为((d),((d,f))6.向一棵空的二叉排序树中逐个插入5,28,4,16,32,21,3,9，则查找9的查找长度为______。

A）1B)2C)3D)47.设有一个AOE网，有3条关键路径，共有15个关键活动，下面的说法_____是正确的。

A）提前完成这15个关键活动之外的活动可以缩短工期B）这三条关键路径长度相同C）提前完成这3条关键路径中的任何一个关键活动都能缩短工期D）改变这15个关键活动之外的活动不会影响工期8.一个有向图，有n个顶点，e条边，则对其邻接表以下说法正确的是_____。

华南理工大学2004年攻读硕士学位研究生入学考试试卷（试卷上做答无效，请在答题纸上做答，试后本卷必须与答题纸一同交回）科目名称：计算机专业综合一(组成原理、数据结构、操作系统)适用专业：计算机系统结构、计算机应用技术、软件工程、计算机应用技术I. 计算机组成原理试题（50分）一．填空题（共10分）1．计算机的工作过程主要是周而复始地A、B和C的过程。

2．在浮点运算中，当运算结果阶码大于所能表示的A时称为溢出，若阶码用双符号S0′S0的移码表示，则当S0′S0 =B时为溢出。

3．双端口存储器和多模块交叉存储器属于A存储器结构；前者采用 B 并行技术，后者采用 C 并行技术。

4．在微程序控制器中，一般采用较简单的A、B 二级时序体制。

5．CPU响应中断时保护两个关键的硬件状态是A和 B 。

二．选择题（共6分）1．设浮点数的阶为8位（其中1位阶符），用移码表示，尾数为24位（其中1位数符），用原码表示。

则它所能表示的最大规格化正数是（）。

A．(27-1)×(1-2-23 )B．×(1-2-23 )C．×(1-2-23 ) D．×(1-2-22 )2．下列说法正确的是（）。

A. 微程序控制方式和硬布线方式相比较，前者可以使指令的执行速度更快B. 若采用微程序控制方式，则可用μPC取代PCC. 控制存储器可以用ROM实现D. 指令周期也称为CPU周期3．下列说法正确的是（）。

A. 程序中断过程是由硬件和中断服务程序共同完成的B. 每条指令的执行过程中，每个总线周期要检查一次有无中断请求C. 检测有无DMA请求，一般安排在一条指令执行过程的末尾D. 中断服务程序的最后指令是无条件转移指令三．完成下列各题（共36分）1．设[A]补＝an-1an-2…a1 a0，式中an-1为补码符号位，求证真值：（8分）2．假设主存只有a，b，c三个页框，组成a进c出的FIFO队列进程，访问页面的序列是0，1，3，4，3，2，0，2，1，3，2号。

计算机专业基础综合数据结构（集合）历年真题试卷汇编7(总分：72.00，做题时间：90分钟)一、单项选择题(总题数：21，分数：42.00)1.对线性表进行二分查找时，要求线性表必须( )。

【南京理工大学2005一、11(1分)】【燕山大学2001一、5(2分)】（分数：2.00）A.以顺序方式存储B.以顺序方式存储，且数据元素有序。

√C.以链接方式存储D.以链接方式存储，且数据元素有序解析：2.当在一个有序的顺序存储表上查找一个数据时，即可用折半查找，也可用顺序查找，但前者比后者的查找速度( )。

【南京理工大学1997一、7(2分)】（分数：2.00）A.必定快B.不一定C.在大部分情况下要快√D.取决于表递增还是递减解析：3.请指出在顺序有序表(2、5、7、10、14、15、18、23、35、41、52)中，用“折半查找法”查找关键字14需做的比较次数为( )。

【北京工业大学2005一、3(2分)】（分数：2.00）A.2B.3C.4 √D.5解析：4.折半查找有序表(5，8，10，22，36，50，53，88)，若查找元素70，则需依次与表中元素(关键字)( )进行比较，查找结果是“失败”。

【华中科技大学2006一、11(2分)】（分数：2.00）A.36，53B.22，50，53，88 √C.36，53，88D.22，53，88解析：5.具有12个关键字的有序表，折半查找的平均查找长度为( )。

【中山大学。

1998二、10(2分)】【烟台大学2007一、17(2分)】（分数：2.00）A.3．1 √B.4C.2．5D.5解析：6.对一个长度为50的有序表进行折半查找，最多比较( )次就能查找出结果。

【北京邮电大学2005一、8(2分)】（分数：2.00）A.6 √B.7C.8D.9解析：解析：长度50(31<50<63)的有序表的判定树高度是6，所以，最多比较6次。

7.折半查找有序表(2，10，25，35，40，65，70，75，81，82，88，100)，若查找元素75，需要依次与表中元素( )进行比较。

计算机专业基础综合数据结构（排序）历年真题试卷汇编7(总分：66.00，做题时间：90分钟)一、单项选择题(总题数：15，分数：30.00)1.下述几种排序方法中，要求内存量最大的是( )。

【中南大学2005一、6(2分)】A.归并排序√B.快速排序C.插入排序D.选择排序2.快速排序方法在( )情况下最不利于发挥其长处。

【华南理工大学2007】A.要排序的数据量太大B.要排序的数据中含有多个相同值C.要排序的数据个数为奇数D.要排序的数据已基本有序√3.当待排序列基本有序时，下列排序方法中( )最好。

【北京邮电大学2005一、10 (2分)】A.直接插入排序√B.快速排序C.堆排序D.归并排序4.设被排序的结点序列共有N个结点，在该序列中的结点已十分接近排序的情况下，用直接插入法、归并法和一般的快速排序法对其排序，这些算法的时间复杂性应为( )。

【上海交通大学2005四、5(2分)】A.O(N)，O(N)，O(N)B.O(N)，O(N*log 2 N)，O(N*log 2 N)C.O(N)，O(N*log 2 N)，O(N 2 ) √D.O(N 2 )，O(N*log 2 N)，O(N 2 )5.数据序列(8，9，10，4，5，6，20，1，2)只能是下列排序算法中的( )的两趟排序后的结果。

【合肥工业大学1999一、3(2分)】A.选择排序B.冒泡排序C.插入排序√D.堆排序对于A、B和D三种排序方法两趟排序后，序列的首部或尾部的两个元素应是有序的两个极值，而给定的序列并不满足。

6.一个排序算法的时间复杂度与( )有关。

【华中科技大学2004一、8(1分)】A.排序算法的稳定性B.所需比较关键字的次数√C.所采用的存储结构D.所需辅助存储空间的大小7.对一组数据(84，47，25，15，21)排序，数据的排列次序在排序的过程中的变化为(1)84 47 25 15 21 (2)15 47 25 84 21 (3)15 21 25 84 47 (4)15 21 25 47 84则采用的排序是( )。

831华南理工大学2010年攻读硕士学位研究生入学考试试卷（试卷上做答无效，请在答题纸上做答，试后本卷必须与答题纸一同交回）科目名称：计算机专业综合（数据结构和操作系统）适用专业：计算机技术共 4 页数据结构部分一、选择题（每小题2分，共20分）1．判断一个循环队列QU(最多元素为m0)为满队列的条件是（）。

A、QU->front==QUÆrearB、QU->front!=QUÆrearC、 QU->front==(QUÆrear+1)%m0D、QU->front!=(QUÆrear+1)%m02．向一个栈顶指针为HS的链栈中插入一个s所指结点时，则执行（ ）。

A、HSÆnext=s;B、sÆnext=HSÆnext; HSÆnext=s;C、sÆnext=HS; HS=s;D、sÆnext=HS; HS=HSÆnext;3．设矩阵A是一个对称矩阵，为了节省存储，将其下三角部分按行序存放在一维数组B[1,n(n-1)/2]中，对下三角部分中任一元素a i,j(i≥j),在一维数组B中下标k的值是（）。

A、i(i-1)/2+j-1B、i(i-1)/2+jC、i(i+1)/2+j-1D、i(i+1)/2+j4. 设有一个无向图G=(V,E)和G'=(V',E')，如果G'为G的生成树，则下面不正确的说法是( )。

A. G'为G的子图B. G'为G的一个无环子图C. G'为G的极小连通子图且V'=VD. G'为G的连通分量5.在线索化二叉树中，t所指结点没有左子树的充要条件是（）。

A、tÆleft=NULLB、tÆltag=1C、tÆltag=1且tÆleft=NULLD、以上都不对6. 具有五层结点的二叉平衡树至少有（）个结点。