广东暨南大学2022年[数据结构]考试真题.docxVIP

考研真题：暨南大学2022年[数据结构]考试真题 一、单项选择题 1.下述关于顺序存储结构优点的说法，哪个是正确的( ) A.插入运算方便 B.可方便地用于各种逻辑结构的存储表示 C.存储密度大 D.删除运算方便 2.假设根结点为第1层，深度为h 层的二叉树至少有( )个结点(h1); A.2h B.2h-1 C.2h+1 D.2h-1 3.用单向链表来实现容量为 n 的堆栈时，链表头指针指向堆栈顶部元素，链表尾 指针指向堆栈底部元素，则以下说法错误的是( ) A.入栈操作的复杂度为〇(1) B.出栈操作的复杂度为O(1) C.删除底部元素的复杂度为O(1) D.插入一个新的堆栈底部元素复杂度为〇(1) 4.以下关于递归算法的论述，不正确的是( ) A.递归算法的代码可读性好 B.递归算法可以提高程序运行效率 C.递归调用层次太深有可能造成堆栈溢出 D.递归调用层次太深会占用大量内存 5.设有字符集合{4,6,3,W,S}, 将字符序列6W43S 中的字符按顺序进入堆栈，出 栈可发生在任何时刻。则以下的出栈序列错误的是( )。 A.64WS3 B.4W36S C.6W34S D.WS436 6.在管理城市道路交通网络据时，最适合采用( )数据结构来对其进行存储。 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.30 ( )。 A.36 B.35 C.34 D.33 10.为了提高哈希表的查找效率，以下方法说法不正确的是( )。 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.6 13.有一个100*90的整数稀疏矩阵，其中非0元素个数为10;设每个整数占用3 个字节，则用三元组表示该矩阵时，总共需要的存储空间为( ) 字 节 。 B. 33 C. 90 D.99 14.在一个双向链表中，当删除结点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. MV C. M=N D.NV 二、填空题 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, 则队满的条件 是 o 8.G 是一个非连通无向图，共有28条边，则该图至少有 个顶点。 9. 数据表中有10000个元素，如果仅要求求出其中最大的10个元素，则采用 排序算法最节省时间。 三 . 判断题 1. 对 n 个记录进行插入排序，最多只需要〇(nlog(n))次两两比较