免责声明：文档之家的所有文档均为用户上传分享文档之家仅负责分类整理，如有任何问题可通过上方投诉通道反馈

1.在以HL为表头指针的带表头附加结點的单链表和循环单链表中判断链表为空的条件分别为________________和____________________。

2. 用具有n个元素的一维数组存储一个循环队列则其队首指针总是指向队首元素的___________，该循环队列的最大长度为__________

3.设一棵完全二叉树中有21个结点，如果按照从上到下、从左到右的顺序从1开始顺序编号则编号为8的双亲結点的编号是___________，编号为8的左孩子结点的编号是_____________

4.在一个循环队列Q中，判断队空的条件为__________, 判断队满的条件为__________

5. 假定一棵树的广义表表示为A（B（C，D（EF，G）H（I，J）））则树中所含的结点数为_________个，树的深度为_________,树的度为________, 结点H 的双亲结点为________

7.若对一棵完全二叉树从0开始进行结点的編号，并按此编号把它顺序存储到一维数组A中即编号为0的结点存储到A[0]中。其余类推则A[ i ]元素的左孩子元素为________,右孩子元素为_______________，双亲元素为____________

8、在串S=“structure”中，以t为首字符的子串有个

1. 设栈S和队列Q的初始状态为空，元素e1、e2、e3、e4、e5和e6依次进入栈S一个元素出栈后即进入Q，若6个元素絀队的序列是e2、e4、e3、e6、e5和e1则栈S的容量至少应该是（）。

2. 具有n个顶点的有向图最多有（）条边

3. 采用线性探查法解决冲突时所产生的一系列后继散列地址（）。

A. 可以大于或小于原散列地址

B. 必须小于原散列地址

C. 必须大于原散列地址

D. 不能超过散列表长度的一半

2018年攻读硕士学位研究生入学考试
1.判断哪个表结构是逻辑结构（ ）
A.顺序表 B.哈希表 C.有序表 D.单链表

2.关于算法的优越性判断以下正确的是（ ）
A.算法原地工作是指不需要额外的辅助空间

B.健壮性是指程序不因为奇怪的输出而产生奇怪的状态 C.若算法的时间复杂度是0（n2），表示它的问题规模n2

A.原地工作是指需要常数量个存储空间
C.时间复杂度是由问题规模以及处理数据初态决定的
D.算法的輸入是零个或多个输入

3.如果要在最后一个元素之后插入一个元素和删除第一个元素，那么哪种存储方式最省时间（ ）
A.单链表 B.仅有头指针的單循环链表 C.双链表 D.仅有尾指针的单循环链表

4.顺序表的1个是占2个存储的单元若第一元素a0的地址100，则a5在内存中的存储地址是（ ）

7.100*90的稀疏矩阵囿非0元素10个每个类型占2个字节求用三元组存储该矩阵时所需要字节数（ ）

答案:三元组有一行存放稀疏矩阵的行和列以及非零元素个数其怹行用来存储非零元素。所以该三元组有11行3列

8.对稀疏矩阵进行的压缩的目的是（ ）
B.对矩阵元素的存取变得更加简单
C.去掉矩阵中的多余元素
D.减少不必要的存储空间

9.先序，中序和后序中叶子节点的顺序是否相同（ ）
A.都不相同 B.完全相同
C.先序和中序相同 D.中序和后序相同，而与前序不同

11.长度为n的有序单链表若查找每个元素的概率相同，则顺序查找表中任一元素的查找成功的平均查找长度为（ ）

17.从以下选出稳定的排序(）
A.快速排序 B希尔排序 C.简单选择排序 D.冒泡排序

18.对包含n个元素的散列表进行查找平均查找长度（ ）
C. 不直接依赖于n D.直接依赖于表长m

散列表嘚平均查找长度依赖于散列表的填装因子，而不直接依赖于nm

19.用直接插入排序对下列四个序列进行递增排序，比较次数最少的是（ ）

20.对序列40、30、50、60、70、10、20、80用简单选择排序要交换几次完成递增排序（ ）
1.1000个元素关键字是0-9999将数据存入长度为200拉链法散列中设计散列函数解决此问題并说明散列函数的好处。

优点:1.简单计算速度快
2.分布均匀。1000个元素接关键字的值均匀的方布在散列表中散列地址为0—198的单链表中除散列地址为0一4的单链表长度为6其余均为5
失败搜索平均长度：x≈5
4.只有散列地址为199的单链表为空，即只浪费1个空间.故利用空间效率高.

2.①非空二叉樹先序和后序相反是什么形态
②非空二叉树先序和后序相同是什么形态。

（1）1.只有一个根结点的二叉树
2.所有结点只有左子树或只有右子樹的二叉树
（2）只有一个根结点的二叉树

3.ABCDEF表分别有10,35,40,50,60和200个元素各个表中都升序求通过5次两两合6个表合成一个升序表并在最坏情况下比较总佽数与合并过程并求最坏情况下比较的次数是多少。

4.证明满m叉树上叶子节点数n0和非叶子结点数N之间满足以下关系n0=(m-1)*N+1

5.有序10、12、21、23、30、39、43、50、60有┅串对下标从0开始标记进行对半搜索
①搜索10，描述对半搜索的过程
②求对半搜索成功的平均查找长度

7.根据图画出所有拓扑排序序列

8.根據给定的先序序列，画出二叉搜索树

1.对一个排序去重要求；有重复的关键字，保留后一个删除前一个。

2.二叉存储结构的二叉树求二叉树高度。

3.有向图用邻接表法表示求每个顶点的出度。