2020 年广东暨南大学数据结构考研真题学科、专业名称：网络空间安全研究方向：网络空间安全 083900考试科目名称及代码：数据结构 830考生注意：所有答案必须写在答题纸（卷）上，写在本试题上一律不给分。一、 单项选择题(每题 2 分，共 30 分) 1. 下述关于顺序存储结构优点的说法，哪个是正确的（ ）A. 插入运算方便 B. 可方便地用于各种逻辑结构的存储表示C. 存储密度大 D. 删除运算方便2. 假设根结点为第 1 层，深度为 h 层的二叉树至少有( ) 个结点(h>1)； A. 2h B. 2h-1 C. 2h+1 D. 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. 64WS3 B. 4W36S C. 6W34S D. WS4366. 在管理城市道路交通网络据时，最适合采用（ ）数据结构来对其进行存储。A．有向图 B．无向图 C．树 D．矩阵7. 具有 k 个顶点的完全有向图的边数为( )。 A. k(k-1) B. k(k-1)/2 C. k2-1 D. k2+1 8. 若线性表最常用的操作是增加或者删除某个元素, 则采用( )存储方式节省时间.A. 单链表 B. 双链表 C. 单循环链表 D. 顺序表9. 由权为 6,3,2,8 的四个叶子结点构造一个哈夫曼树，该树的带权路径长度为（ ）。A. 36 B. 35 C. 34 D. 3310. 为了提高哈希表的查找效率，以下方法说法不正确的是( )。A. 设计好的哈希函数 B. 增加哈希函数的个数 C. 增大存储空间 D. 采用更好的地址冲突解决方法11. 以下数据结构中哪一个是非线性结构？( ) A. 队列 B. 栈 C. 线性表 D. 二叉树12. 对于一个整数集合{11，37，29，55，80，46，73，17}进行散列存储时，若选用函数H（K）= K %9 作为散列(哈希)函数，则散列地址为 1 的元素有（ ）个。A．3 B．4 C．5 D．613. 有一个 100*90 的整数稀疏矩阵，其中非 0 元素个数为 10；设每个整数占用 3 个字节，则用三元组表示该矩阵时，总共需要的存储空间为( )字节。A．30 B．33 C．90 D．9914. 在一个双向链表中，当删除结点 p 时，错误的操作序列为 ( )。 A. p=p->prev; p->next->prev=p; p->next=p->next->next; B. p=p->next; p->prev=p->prev->prev; p->prev->next=p; C. p->prev->next=p->next; p->next->prev=p->prev; D. p=p->prev; p->next=p->next->next; p->next->prev=p;15. 在一个具有 V 个顶点的有向连通图中，若所有顶点的入度数之和为 N，所有顶点的出度之和为 M，则以下说法正确的是（ ）。A．V=(M+N)/2 B．M>V C．M=N D．N>V二、填空题(每空 2 分，共 20 分)1. 对 n 个不同的排序码进行冒泡排序，在元素无序的情况下比较的次数为 。2. 在 单 链 表 中 ， 要 将 m 所 指 结 点 插 入 到 n 所 指 结 点 之 后 ， 其 语 句 表 示 为 。3. 设有数组 A[i][j]，数组的每个元素长度为 3 字节，i 的值为 1 到 8，j 的值为 1 到 10，数组从内存首地址 BA 开始顺序存放，当用以列为主存放时，元素 A[5][8]的存储首地址为 。4. 设哈夫曼树中有 199 个结点，则该哈夫曼树中有 个叶子结点。5. 对 22 个记录的有序表作折半查找，当查找失败时候，至多需要比较 次关键字，至少需要比较 次关键字。6. 由 3 个结点可以构造出 种不同的二叉树。7. 最大容量为 s 的循环队列，队尾指针是 rear，队头是 front，则队满的条件是 。8. G 是一个非连通无向图，共有 28 条边，则该图至少有 个顶点...
