暨南大学数据结构考研真题

考研真题：暨南大学2022年[计算机基础综合]考试真题第一部分数据结构一、单项选择题1.含有m个结点的二叉树链式存储结构中空指针的个数为( )。

A．2mB．m-1C．m+1D．m2.下列排序算法中元素的移动次数和关键字的初始排列次序无关的是( )。

A.快速排序B.插入排序C.选择排序D.希尔排序3.一个栈的进栈序列是abcde，则栈的输出序列不可能的是( )。

A．abcdeB．edcbaC．decbaD．dceab4.需要的辅助空间最多的排序算法为( )。

A.归并排序B.快速排序C.基数排序D.堆排序5.哈希表的平均查找长度说法错误的是( )。

A.与处理冲突方法有关而与表的长度无关B.与选用的哈希函数有关C.与哈希表的饱和程度有关D.与表中填入的记录数有关6.有n个顶点、e条边且使用了邻接表存储的有向图进行深度优先遍历，其算法的时间复杂度是( )。

A.O（n+e）B.O（n2）C.O（n+2e）D.O（n*e）7.已知一个长度为11的顺序表，其元素按关键字有序排列，若采用折半查找查找一个其中不存存在的元素，则关键字的比较次数最多是( )。

A．3B．4C．5D．68.一棵完全二叉树上有3001个结点，其中叶子结点的个数是( )。

A.1500B.1501C.1000D.10019.若一棵二叉树度为2的结点有18个，度为1的结点有10个，则度为0的结点个数是( )。

A.46B.28C.19D.1710.m阶B-树是一棵( )。

A.m叉排序树B.m-1叉平衡排序树C.m叉平衡排序树D.m+1叉平衡排序树二、填空题1.已知一棵二叉树的中序遍历序列为GDHBAECIF，后序遍历序列为GHDBEIFCA，那么先序遍历序序列为。

2.若某记录的关键字序列是（491，77，572，16，996，101，863，258，689，325），以第一个关键字为枢轴，写出采用快速排序算法第一趟排序的结果。

3.将对称矩阵A[8][8]的下三角部分逐行存储到起始地址为2000的内存单元中，已知每个元素占4个单元，假设第一个元素是A[0][0]，则A[4][6]的地址是。

2023年招收攻读硕士学位研究生入学考试试题A卷******************************************************************************************** 招生专业与代码：网络空间安全考试科目名称及代码：数据结构830考生注意：所有答案必须写在答题纸（卷）上，写在本试题上一律不给分。

一、单项选择题(每题2分，共20分)1. 以下数据结构中, ( )是非线性数据结构A．字符串B．树C．队列D．栈2. 请选择下面程序段的时间复杂度( )i = 1;while (i <= n)i = i * 3;A. O（n）B. O（log3 n）C. O（n2）D. O（i * n）3. 顺序表中第一个元素的存储地址为120，每个元素的长度为5，则第4个元素的地址为( )A. 135B. 140C. 130D. 1454. 在单链表中，要将L所指节点插入到M所指节点之后，其语句应为( )A. L->next = M+1; M->next = L;B. (*M).next = L; (*L).next = (*M).next;C. L->next = M->next; M->next = L->next;D. L->next = M->next; M->next = L;5. 若让元素1，2，3，4，7依次进栈，则出栈顺序不可能为( )A. 7, 4, 3, 2, 1B. 4, 3, 1, 2, 7C. 2, 1, 7, 4, 3D. 2, 3, 7, 4, 16. 假设栈S与队列Q的初始状态为空，元素e1、e2、e3、e4、e5和e6依次进入栈S，一个元素出栈后即进入Q，若6个元素出队的序列是e2、e4、e3、e6、e5和e1，则栈S 的容量至少为( )A．2 B. 4 C. 3. D.67. 假设以行序列为主序存储二维数组A = array[1..100,1..100]，设每个数据元素占2个存储单元，基地址为10，则LOC[5, 5] = ( )A．808 B．1010 C．818 D．10208. 由3个不同结点可计算出多少种不同的二叉树？( )A. 3B. 4C. 5D. 69. 广度优先遍历类似于二叉树的( )A. 先序遍历B. 中序遍历C. 层次遍历D. 后序遍历10. 设哈希表长为14，哈希函数是H(key)=key%11，表中已有数据的关键字为15，38，61，84共四个，现要将关键字为49的元素加到表中，用二次探测法解决冲突，则放入的位置是( )A．8 B．3 C．5 D．9考试科目：数据结构共 3 页，第 1 页二．填空题(每空2分，共20分)1.设一组初始记录关键字序列为(20，12，42，31，18，14，28)，则根据这些记录关键字构造的二叉排序树的平均查找长度是__________。

2019年广东暨南大学数据结构考研真题一、单项选择题(每题2分，共30分)1.在任意一棵二叉树的先序序列和后序序列中，各叶子之间的相对次序关系()。

A.不一定相同B.互为逆序C.都不相同D.都相同2.深度为4的二叉树至多有结点数为()。

A.18B.14C.15D.163.在一个具有n个顶点的有向图中，若所有顶点的入度数之和为m，则所有顶点的度数之和为()。

A.mB.m-1C.m+1D.2m4.快速排序在()情况下最不利于发挥其长处。

A.被排序的数据量太大.B.被排序数据中含有多个相同的关键字C.被排序的数据完全无序D.被排序的数据已基本有序5.一组记录的关键字为(45,80,55,40,42,85),则利用堆排序的方法建立的初始堆为()。

A.(80,45,55,40,42,85)B.(85,80,55,40,42,45)C.(85,80,55,45,42,40)D.(85,55,80,42,45,40)6.对有18个元素的有序表(下标为1~18)作折半查找,则查找A[3]的比较序列的下标为()。

A.1,2,3B.9,5,2,3C.9,5,3D.9,4,2,37.具有n个顶点的完全有向图的边数为()。

A.n(n-1)/2B.n(n-1)C.n2D.n2-18.利用逐点插入法建立序列(50,72,43,85,75,20,35,45,65,30)对应的二叉排序树以后，查找元素35要进行()。

A.4次B.5次C.3次D.2次9.判定一个有向图是否存在回路除了可以利用拓扑排序方法外，还可以用()。

A.求最短路径的Floyd方法B.求最短路径的Dijkstra方法C.广度优先遍历算法D.深度优先遍历算法10.对于一个具有n个顶点的无向连通图，它包含的连通分量的个数为()。

A.0B.1C.nD.n+111.在一个单链表中,若p所指的结点不是最后一个结点,在p之后插入s所指的结点,则执行()。

A.s->next=p;p->next=sB.p->next=s;s->next=pC.p=s;s->next=p->nextD.s->next=p->next;p->next=s12.设F是由T1、T2和T3三棵树组成的森林，与F对应的二叉树为B，T1、T2和T3的结点数分别为N1、N2和N3，则二叉树B的根结点的左子树的结点数为()。

2020年全国硕士研究生统一入学考试自命题试题B卷********************************************************************************************学科、专业名称：网络空间安全研究方向：网络空间安全083900考试科目名称及代码：数据结构830考生注意：所有答案必须写在答题纸（卷）上，写在本试题上一律不给分。

一、单项选择题(每题2分，共30分)1. 下述关于顺序存储结构优点的说法，哪个是正确的（）A. 插入运算方便B. 可方便地用于各种逻辑结构的存储表示C. 存储密度大D. 删除运算方便2. 假设根结点为第1层，深度为h层的二叉树至少有( ) 个结点(h>1)；A. 2hB. 2h-1C. 2h+1D. 2h-13. 用单向链表来实现容量为n的堆栈时，链表头指针指向堆栈顶部元素，链表尾指针指向堆栈底部元素，则以下说法错误的是( )A. 入栈操作的复杂度为O(1)B. 出栈操作的复杂度为O(1)C. 删除底部元素的复杂度为O(1)D. 插入一个新的堆栈底部元素复杂度为O(1)4. 以下关于递归算法的论述，不正确的是( )A. 递归算法的代码可读性好B. 递归算法可以提高程序运行效率C. 递归调用层次太深有可能造成堆栈溢出D. 递归调用层次太深会占用大量内存5. 设有字符集合{4,6,3,W,S}，将字符序列6W43S中的字符按顺序进入堆栈，出栈可发生在任何时刻。

则以下的出栈序列错误的是（）。

A. 64WS3B. 4W36SC. 6W34SD. WS4366. 在管理城市道路交通网络据时，最适合采用（）数据结构来对其进行存储。

A．有向图B．无向图C．树D．矩阵7. 具有k个顶点的完全有向图的边数为( )。

A. k(k-1)B. k(k-1)/2C. k2-1D. k2+18. 若线性表最常用的操作是增加或者删除某个元素, 则采用( )存储方式节省时间.A. 单链表B. 双链表C. 单循环链表D. 顺序表9. 由权为6,3,2,8的四个叶子结点构造一个哈夫曼树，该树的带权路径长度为（）。

一、判断题（每小题2分，共10分）。

1. 线性表的逻辑顺序与物理顺序总是一致的。

( )2. 堆排序是不稳定的排序方法。

( )3. 在非空二叉树中，任一结点均有两棵二叉树。

( )4. 一个无序的元素序列可以通过构造一棵二叉排序树而变成一个有序的元素序列。

( )5. 在一个有向图中，所有顶点的入度之和等于所有顶点的出度之和。

( )二、单项选择题（每小题2分，共10分）1. 表长为n的顺序存储的线性表，当在任何位置上插入或删除一个元素的概率相等时，插入一个元素需要移动元素的平均次数为（），删除一个元素需要移动元素的平均次数为（）。

A. (n-1)/2B. nC. n-1D. n/22. 对于一个头指针为L的带头结点的单链表，判定该表为空表的条件是（）。

A. L=NULL;B.L->next=NULL;C. L->next==L;D. L!=NULL;3. 以下数据结构中，（）是非线性数据结构。

A. 树B. 字符串C. 数组D. 栈4. 对线性表进行折半查找时，要求线性表必须（）。

A. 以顺序方式存储。

B. 以链式方式存储。

C. 以顺序方式存储，且结点按关键字有序排序。

D. 以链式方式存储，且结点按关键字有序排序。

5.在下面的排序方法中，关键字比较的次数与记录的初始排列次序无关的是（）。

A. 希尔排序B. 冒泡排序C. 插入排序D. 选择排序三、填空题（每小题2分，共10分）1. 在内部排序中，平均比较次数最少的是_________，要求附加的内存容量最大的是_________。

2. 由n个权值构成的赫夫曼树共有_________个结点。

3. 在单链表中，除首元结点外，任一结点的存储位置由_________指示。

4. 栈结构允许进行删除操作的一端称为栈的_________。

5. 设GetHead(p)为求广义表p的表头函数，GetTail(p)为求广义表p的表尾函数。

其中( )是函数符号，运算GetTail(GetHead((a,b),(c,d)))的结果是_________。