下载文档原格式
计算机专业基础综合数据结构（树和二叉树）历年真题试卷汇编6(总分：88.00，做题时间：90分钟)一、单项选择题(总题数：33，分数：66.00)1.一棵完全二叉树又是一棵( )。
【华中科技大学2006一、7(2分)】A.平衡二叉树B.堆√C.二叉排序树D.哈夫曼(Huffman)树完全二叉树的叶子至多在下面两层上，且一个结点若无左子树，绝不能有右子树。
平衡二叉树任何结点的左右子树的高度差的绝对值不超过1，但其结点的值符合二叉排序树的定义。
平衡二叉树(包括二叉排序树)的树形不一定是完全二叉树。
堆是一个序列，有大堆和小堆，编号为i的结点，其父结点、左右子女结点之间位置的关系，符合完全二叉树父结点、左右子女结点之间的关系，从这点上说，可以把堆看成完全二叉树。
哈夫曼树是二叉树，但树形不一定满足完全二叉树的定义。
2.一棵左子树为空的二叉树在先序线索化后，其中空的链域的个数是( )。
【合肥工业大学1999一、5(2分)】A.不确定B.0C.1D.2 √左子树为空的二叉树的根结点的左线索为空(无前驱)，先序序列的最后结点的右线索为空(无后继)，共2个空链域。
3.一棵左右子树均不空的二叉树在先序线索化后，其中空的链域的个数是( )。
【合肥工业大学2000一、5(2分)】A.0B.1 √C.2D.不确定4.若X是二叉中序线索树中一个有左孩子的结点，且X不为根，则X的前驱为( )。
【南京理工大学1996一、6(2分)】A.X的双亲B.X的右子树中最左的结点C.X的左子树中最右结点√D.X的左子树中最右叶结点5.引入二叉线索树的目的是( )。
【南京理工大学1998一、5(2分)】A.加快查找结点的前驱或后继的速度√B.为了能在二叉树中方便地进行插入与删除C.为了能方便地找到双亲D.使二叉树的遍历结果唯一6.线素二叉树是一种( )结构。
【西安电子科技大学1996一、9(2分)】A.逻辑B.逻辑和存储C.物理√D.线性7.甩个结点的线索二叉树上含有的线索数为( )。
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.Cache存贮器XB.系列机各档不同的数据通路宽度C.指令缓冲寄存器D.虚拟存贮器7、在多用户机器上，应用程序员不能使用的指令是（）A.“执行”指令B.“访管”指令C.“启动IO”指令D“测试与置定”指令8、非线性流水线是指( )A.一次运算中使用流水线中的多个功能段B.一次运算中要多次使用流水线中的某些功能段C.流水线中某些功能段在各次运算中的作用不同D.流水线的各个功能段在各种运算中有不同的组合9、在计算机系统设计中，比较好的方法是( )A.从上向下设计B.从下向上设计C.从两头向中间设计D.从中间开始向上、向下设计10、属计算机系统结构考虑的是（）A.主存采用MOS还是TTLB.主存采用多体交叉还是单体C.主存容量和编址方式D.主存频宽的确定二、填空题11、段式虚拟存贮器是用________表来进行地址映象和变换的。
12、目前已有的向量处理机结构主要采用________和________两种结构。
13、多功能流水线各功能段同时可按不同运算或功能联接工作，称此流水线为________流水线。
数据结构本科试题及答案一、选择题（每题4分，共40分）1. 下列哪一个不是线性结构的特点？A. 有且只有一个根结点B. 每个结点最多有一个前驱和一个后继C. 至少有一个结点D. 结点的存储顺序与数据的逻辑顺序相同答案：D2. 在单链表中，若要删除指针P所指向的结点，则正确的操作是（）A. p = p->nextB. p->next = p->next->nextC. p->next = pD. p = p->next->next答案：B3. 下面关于栈的叙述中，正确的是（）A. 栈是一种先进先出的线性表B. 栈是一种先进后出的线性表C. 栈是一种任意顺序的线性表D. 栈是一种只能插入元素但不能删除元素的线性表答案：B4. 下列关于队列的叙述中，正确的是（）A. 队列是一种先进先出的线性表B. 队列是一种先进后出的线性表C. 队列是一种任意顺序的线性表D. 队列是一种只能插入元素但不能删除元素的线性表答案：A5. 在二叉树中，具有3个结点的二叉树有（）种形态。
A. 2B. 3C. 4D. 5答案：C二、填空题（每题5分，共30分）6. 线性表的顺序存储结构是一种用数组来表示的存储结构，它把线性表的元素存放在地址连续的内存单元中，其数据元素之间的逻辑关系由它们的存储位置来表示。
在线性表的顺序存储结构中，若元素a[i]的存储地址为1000，每个元素占用4个存储单元，则元素a[i+2]的存储地址为______。
答案：10087. 在单链表中，插入操作和删除操作的时间复杂度分别为______和______。
答案：O(1)，O(1)8. 在栈和队列中，栈的操作是______，队列的操作是______。
答案：先进后出，先进先出9. 在二叉树中，若结点X是结点Y的父结点，则结点Y称为结点X的______。
答案：子结点10. 在二叉树中，若结点X没有子结点，则结点X 称为______。
2022年华中科技大学数据科学与大数据技术专业《操作系统》科目期末试卷A（有答案）一、选择题1、假定下列指令已装入指令寄存器，则执行时不可能导致CPU从用户态变为内核态（系统态）的是（）。
A.DIV R0，R1；（R0）/（R1）→ROB.INT n；产生软中断C.NOT RO；寄存器R0的内容取非D.MOV RO，addr；把地址 addr处的内存数据放入寄存器RO中2、用户程序在口态下使用特权指令引起的中断属于（）。
A.硬件故障中断B.程序中断C.外部中断D.访管中断3、有若干并发进程均将一个共享变量count的值加1一次，那么有关count中的值的说法正确的是（）。
I.肯定有不正确的结果II.肯定有正确的结果，III.若控制这些并发进程互斥执行count加1操作，count中的值正确A. I和IIIB.II和IIIC.IIID. I、II和III的说法均不正确4、若系统中有n个进程，则在阻塞队列中进程的个数最多为（）？Α. n B.n-1 C.n-2 D.15、系统中有3个不同的临界资源R1，R2和R3，被4个进程pl，p2，p3 及p4共享。
各进程对资源的需求为：pl申请RI和R2，p2申请R2和R3，p3申请R1和R3，p4申请R2。
若系统出现死锁，则处于死锁状态的进程数至少是（）。
A.1B.2C.3D.46、I/O交通管制程序的主要功能是管理（）的状态信息。
A.设备、控制器和通道B.主存、控制器和通道C.CPU、主存和通道D.主存、辅存和通道7、用户程序发出磁盘1/0请求后，系统的正确处理流程是（）A.用户程序→系统调用处理程序→中断处理程序→设备驱动程序B.用户程序→系统调用处理程序→设备驱动程序→中断处理程序C.用户程序→设备驱动程序→系统调用处理程序→中断处理程序D.用户程序→设备驱动程序→中断处理程序→系统调用处理程序8、操作系统为了管理文件，设计了文件控制块（FCB），文件控制块的建立是（）.A.在调用create（）时B.在调用open（）时C.在调用read（）时D.在调用write（）9、下列文件物理结构中，适合随机访问且易于文件扩展的是（）。
华中科技大学2011年研究生入学考试试题数据结构与算法一．术语解释：（25'）1线性表2树的结点的层次3排序4完全图5最小生成树二．单项选择：（25'）1在数组｛1，2，3，4，5，6，7，8，9，10｝中折半查找5，需要的比较次数是（）A1B2C3D42假定问题规模为N时，某递归算法的时间复杂度记为T（N），已知T(1)=1，T(N)=2T(N/2)+N/2，用O表示的时间复杂度为（）A O(N)B O(NlogN)C O(N²)D O(N²logN)3一棵二叉树的先序便利输出为ABCDEFGH，中序遍历为CBEDAFHG，则其先序遍历输出为（）【此题的确问的是先序遍历】A CBDEAFGHB CBEDAFHGC BCEDFAHG D以上都不对4栈和队列的共同点是（）A先进先出B后进先出C插入删除只能在端点进行D没有共同点5起泡排序的时间复杂度是（C）【此题原试卷将答案附上了】A O(N)B O(NlogN)C O(N²)D O(N²logN)三．简答（60'）1用一个数组实现两个栈，尽可能利用存储空间，写出两个栈的插入、删除操作算法。
2已知一组关键字为｛27、25、23、37、35、33、77、75、73、97、95、93、103｝，按哈希函数H(key)=key Mod11（表长11），用连地址法处理冲突，画出哈希表。
3一个递归函数具有如下形式Void func(int n){if(n>0){func(n/2);printf("d%",n*n);func(n/2);}return;}请依次写出fun(1)，fun(2)，fun(3)，fun(5)执行的结果，其时间复杂度为多少？4一个通信网络中共有九中字符，其概率分别为0.14、0.23、0.15、0.03、0.18、0.1、0.02、0.11、0.04，画出相应的赫夫曼树来设计其赫夫曼编码。
数据结构试卷（一）王彬一、单选题（每题2 分，共20分）1.栈和队列的共同特点是( )。
A.只允许在端点处插入和删除元素B.都是先进后出C.都是先进先出D.没有共同点2.用链接方式存储的队列，在进行插入运算时( ).A. 仅修改头指针B. 头、尾指针都要修改C. 仅修改尾指针D.头、尾指针可能都要修改3.以下数据结构中哪一个是非线性结构？( )A. 队列B. 栈C. 线性表D. 二叉树4.设有一个二维数组A[m][n]，假设A[0][0]存放位置在644(10)，A[2][2]存放位置在676(10)，每个元素占一个空间，问A[3][3](10)存放在什么位置？脚注(10)表示用10进制表示。
cA．688 B．678 C．692 D．6965.树最适合用来表示( )。
A.有序数据元素B.无序数据元素C.元素之间具有分支层次关系的数据D.元素之间无联系的数据6.二叉树的第k层的结点数最多为( d ).A．2k-1 B.2K+1 C.2K-1 D. 2k-17.若有18个元素的有序表存放在一维数组A[19]中，第一个元素放A[1]中，现进行二分查找，则查找A［3］的比较序列的下标依次为( )A. 1，2，3B. 9，5，2，3C. 9，5，3D. 9，4，2，38.对n个记录的文件进行快速排序，所需要的辅助存储空间大致为A. O（1）B. O（n）C. O（1og2n）D. O（n2）9.对于线性表（7，34，55，25，64，46，20，10）进行散列存储时，若选用H（K）=K %9作为散列函数，则散列地址为1的元素有（ c d）个，A．1 B．2 C．3 D．410.设有6个结点的无向图，该图至少应有( )条边才能确保是一个连通图。
A.5B.6C.7D.8二、填空题（每空1分，共26分）1.通常从四个方面评价算法的质量：____ ____、________、________和_______。
2.一个算法的时间复杂度为(n3+n2log2n+14n)/n2，其数量级表示为________。
计算机专业基础综合数据结构（树和二叉树）历年真题试卷汇编6(总分88, 做题时间90分钟)1. 单项选择题1.一棵完全二叉树又是一棵( )。
【华中科技大学2006一、7(2分)】SSS_SINGLE_SELA 平衡二叉树B 堆C 二叉排序树D 哈夫曼(Huffman)树分值: 2答案:B解析：完全二叉树的叶子至多在下面两层上，且一个结点若无左子树，绝不能有右子树。
平衡二叉树任何结点的左右子树的高度差的绝对值不超过1，但其结点的值符合二叉排序树的定义。
平衡二叉树(包括二叉排序树)的树形不一定是完全二叉树。
堆是一个序列，有大堆和小堆，编号为i的结点，其父结点、左右子女结点之间位置的关系，符合完全二叉树父结点、左右子女结点之间的关系，从这点上说，可以把堆看成完全二叉树。
哈夫曼树是二叉树，但树形不一定满足完全二叉树的定义。
2.一棵左子树为空的二叉树在先序线索化后，其中空的链域的个数是( )。
【合肥工业大学1999一、5(2分)】SSS_SINGLE_SELA 不确定B 0C 1D 2分值: 2答案:D解析：左子树为空的二叉树的根结点的左线索为空(无前驱)，先序序列的最后结点的右线索为空(无后继)，共2个空链域。
3.一棵左右子树均不空的二叉树在先序线索化后，其中空的链域的个数是( )。
【合肥工业大学2000一、5(2分)】SSS_SINGLE_SELA 0B 1C 2D 不确定分值: 2答案:B4.若X是二叉中序线索树中一个有左孩子的结点，且X不为根，则X的前驱为( )。
【南京理工大学1996一、6(2分)】SSS_SINGLE_SELA X的双亲B X的右子树中最左的结点C X的左子树中最右结点D X的左子树中最右叶结点分值: 2答案:C5.引入二叉线索树的目的是( )。
【南京理工大学1998一、5(2分)】SSS_SINGLE_SELA 加快查找结点的前驱或后继的速度B 为了能在二叉树中方便地进行插入与删除C 为了能方便地找到双亲D 使二叉树的遍历结果唯一分值: 2答案:A6.线素二叉树是一种( )结构。
2022年华中科技大学软件工程专业《计算机系统结构》科目期末试卷B（有答案）一、选择题1、利用时间重叠概念实现并行处理的是( )。
A.流水处理机B.多处理机C.并行（阵列）处理机D.相联处理机2、与流水线最大吞吐率高低有关的是( )A.各个子过程的时间B.最快子过程的时间C.最慢子过程的时间D.最后子过程的时间3、不同系列的机器之间，实现软件移植的途径不包括( )A.用统一的高级语言B.用统一的汇编语言C.模拟D.仿真4、系列机软件应做到( )。
A.向前兼容，并向上兼容B.向后兼容，力争向上兼容C.向前兼容，并向下兼容D.向后兼容，力争向下兼容5、设16个处理器编号分别为0，1，2，...，15用Cube，互联函数时，第10号处理机与第（）号处理机相联。
A.11B.8C.14D.26、虚拟存储器常用的地址映象方式是( )A.全相联B.段相联C.组相联D.直接7、推出系列机的新机器，不能更改的是( )A.原有指令的寻址方式和操作码B.系统总线的组成C.数据通路宽度D.存贮芯片的集成度8、计算机组成设计不考虑（）A.专用部件设置B.功能部件的集成度C.控制机构的组成D.缓冲技术9、下列关于虚拟存贮器的说法，比较正确的应当是( )A.访主存命中率随页面大小增大而提高B.访主存命中率随主存容量增加而提高C.更换替换算法能提高命中率D.在主存命中率低时，改用堆栈型替换算法，并增大主存容量，可提高命中率10、以下说法中，不正确的是,软硬件功能是等效的，提高硬件功能的比例会：( )A.提高解题速度B.提高硬件利用率C.提高硬件成本D.减少所需要的存贮器用量二、填空题11、多功能流水线各功能段同时只能按某一种功能联接的称为________流水线。
12、流水有部件、处理机、系统等不同等级，多个处理机之间的流水属________级流水，也称________流水。
13、段式存储管理是指________，为此每道程序在系统中都有一个________14、浮点数尾数基值增大。
4一个通信网络中共有九中宇符，其概率分别为0.14、0.23、0.15、0.03、0.18、0.1、0.02、
0.11、0.04，画出相应的赫夫曼树来设计其赫夫曼编码。
5 V，→V2→V3→／＼； V2→v4→vs→／＼ ; V3→vs→V6→／＼ ; V4→〈：
Vs→V1→Vs→／＼ ; v6→Vs→／＼； V1→／＼ ; Vs→V9→／＼ ; V9→八
画出这个逻辑结构的图示，分别写出从V，出发的深度优先和广度优先搜索序列。
四．应用编程题：(40’〉
l在一个整形数组a中既有负数又有正数，编写一个算法将a中所有负数移到整数之前，要求其时间复杂度为0（时，n为数组长度，并且只使用常数个辅助空间。
例如：a[]={l,2,3,4,-l,l,-2,-1,-4｝执行算法后的输出为a[]={-4,-1,-2,-1,l,4,3,2,l}
2编写一个C函数，输入一个二叉树的根节点，返回这棵树中所有值大于0的节点值之和，如果根为空，返回Oo
二叉树的链式存储结构对应的C语言的结点类型定义如下：
typedef struct n d e {
Elem T ype dat a;
structno d e *lchild·
structno d e *rchild·
}B T re e;。
2014年华中科技大学数据结构与算法分析考研试题（部分）
一、填空题：
1、写出数据结构的四种基本逻辑结构
2、写出算法的四种特性
3、一个栈中有六个数字，要求对其进行重新排序，求堆栈的最小容量
4、求出一串数字的非平凡子串个数
5、求一平衡二叉树的成功查找长度和不成功查找长度
….
二、选择题：（略）
三、分析题：
1、给出一个算法过程，要求列出它的开销公式并解出开销函数
2、根据题意画出Huffman前缀码树并求出编码长度
3、该题关于KRUSKAL(V，E，w)的最小生成树算法，由给出的具体算法写出其中元素A
的变化过程，并求出最小生成树的权
4、由题中给出的网络流图求剩余流图，在图中标出最小切割，解出S→t的最大网络流
5、给出一个图，从a开始深度优先搜索，算出每个节点发现和结束的时刻d/f，根据
搜索结果标出图上边的类型
四、算法题：
1、①3②
B
A 4
④7③
根据最短路径延伸算法给出递归表达式，将全成对最短路径填写到题目中的4X4
表格中，并写出表格中某一阴影指定位置的路径
2、证明：A∪(u，v)是图G最小生成树的子集
3、权重函数f，动态划归，写递推式，用伪码描述算法。
数据结构试题及答案
一．是非题（每题1分共10分）
1. 线性表的链式存储结构优于顺序存储结构。
F
2. 栈和队列也是线性表。
如果需要，可对它们中的任一元素进行操作。
F
3．字符串是数据对象特定的线性表。
T
4．在单链表P指针所指结点之后插入S结点的操作是：P->next= S ; S-> next = P->next; F
5．一个无向图的连通分量是其极大的连通子图。
T
6．邻接表可以表示有向图，也可以表示无向图。
T
7．假设B是一棵树，B′是对应的二叉树。
则B的后根遍历相当于B′的中序遍历。
T
8．通常，二叉树的第i层上有2i-1个结点。
F
9．对于一棵m阶的B-树,树中每个结点至多有m 个关键字。
除根之外的所有非终端结点至少有ém/2ù个关键字。
F
10．对于任何待排序序列来说，快速排序均快于起泡排序。
F 二．选择题（每题2分共28分）
1．在下列排序方法中，（c ）方法平均时间复杂度为0(nlogn)，最坏情况下时间复杂度为0(n2)；（ d ）方法所有情况下时间复杂度均为0(nlogn)。
a. 插入排序
b. 希尔排序
c. 快速排序
d. 堆排序
2. 在有n个结点的二叉树的二叉链表表示中，空指针数为（b ）。
a.不定
b.n+1
c.n
d.n-1
3. 下列二叉树中，（a ）可用于实现符号不等长高效编码。
a.最优二叉树
b.次优查找树
c.二叉平衡树
d.二叉排序树
4. 下列查找方法中，（a ）适用于查找有序单链表。
a.顺序查找
b.二分查找
c.分块查找
d.哈希查找
5. 在顺序表查找中，为避免查找过程中每一步都检测整个表是否查找完毕，可采用（a ）方法。
a.设置监视哨
b.链表存贮
c.二分查找
d.快速查找
6. 在下列数据结构中，（ c ）具有先进先出特性，（ b ）具有先进后出特性。
a．线性表b．栈c．队列d．广义表
7．具有m个结点的二叉排序树，其最大深度为（f ），最小深度为（b ）。
a. log 2 m
b. └ log2 m ┘ +1
c. m/2
d .┌ m/2 ┐ -1 e. ┌ m/2 ┐ f. m
8．已知一组待排序的记录关键字初始排列如下：56,34,58,26,79,52,64,37,28,84,57。
下列选择中（c ）是快速排序一趟排序的结果。
（b ）是希尔排序（初始步长为4）一趟排序的结果。
（d ）是基数排序一趟排序的结果。
（a ）是初始堆（大堆顶）。
a. 84，79，64，37，57，52，58，26，28，34，56。
b. 28，34，57，26，56，52，58，37，79，84，64。
c. 28，34，37，26，52，56，64，79，58，84，57。
d. 52，34，64，84，56，26，37，57，58，28，79。
e. 34，56，26，58，52，64，37，28，79，57，84。
f. 34，56，26，58，52，79，37，64，28，84，57。
三．填空题（每题2分共20分）
1．有向图的存储结构有（邻接矩阵）、（邻接表）、（十字链表）等方法。
2．已知某二叉树的先序遍历次序为afbcdeg，中序遍历次序为cedbgfa。
其后序遍历次序为（edcgbfa）。
层次遍历次序为（afbcgde）。
3．设有二维数组A 5 x 7 ,每一元素用相邻的4个字节存储，存储器按字节编址。
已知A00的存储地址为100。
则按行存储时，元素A14的第一个字节的地址是（144）；按列存储时，元素A14的第一个字节的地址是（184）。
4．请在下划线上填入适当的语句，完成以下法算。
Status Preordertraverse(Bitree T,Status(*Visit)(Telemtype e)){
//先序非递归遍历二叉树。
Initstack ( S ); Push ( S,T );
While ( !stackempty( S ) )
{ While ( gettop( S, p )&& p ) { visit (p->data ) ; push(S, p->lchild ;}
Pop ( S , p );
If ( !stackempty(s) ) { pop(S, p) ; push( S, p->rchild ); }
}
return ok;
四、算法设计题（共17分）
1. 单链表结点的类型定义如下：
typedef struct LNode {
int data;
struct LNode *next;
} LNode, *Linklist;
写一算法，将带头结点的有序单链表A和B合并成一新的有序表C。
(注:不破坏A和B的原有结构.)
Merge (Linklist A, Linklist B, Linklist &C )
void Merge ( Linklist A, Linklist B, Linklist &C)
{ C=(Linklist)malloc(sizeof(LNode));
pa=A->next; pb=B->next; pc=C;
while(pa&&pb){
pc->next=(Linklist)malloc(sizeof(LNode)); pc=pc->next;
if(pa->data<=pb->data){
pc->data=pa->data; pa=pa->next; }
else{
pc->data=pb->data; pb=pb->next; } }
if(!pa) pa=pb;
while(pa){
pc->next=(Linklist)malloc(sizeof(LNode));
pc=pc->next; pc->data=pa->data; pa=pa->next; } pc->next=NULL; }
2. 二叉树用二叉链表存储表示。
typedef struct BiTNode {
TelemType data;
Struct BiTNode *lchild, *rchild;
} BiTNode, *BiTree;
编写一个复制一棵二叉树的递归算法。
BiTree CopyTree(BiTree T) {
if (!T ) return NULL;
if (!(newT = (BiTNode*)malloc(sizeof(BiTNode) ) ) )
exit(Overflow);
newT-> data = T-> data;
newT-> lchild = CopyTree(T-> lchild);
newT-> rchild = CopyTree(T-> rchild);
return newT; }。
