数据结构论述试题及答案

数据结构论述试题及答案

单项选择题（每题2分，共10题）1.线性表采用顺序存储时，其地址（）A.一定连续B.部分连续C.不一定连续D.都不连续2.栈的特点是（）A.先进先出B.先进后出C.随机进出D.只进不出3.队列的“先进先出”特性是指（）A.最早插入队列中的元素总是最后被删除B.当同时进行插入、删除操作时，总是插入操作优先C.每当有删除操作时，总是要先做一次插入操作D.最先插入队列中的元素总是最先被删除4.树最适合用来表示（）A.有序数据元素B.无序数据元素C.元素之间具有分支层次关系的数据D.元素之间无联系的数据5.具有10个顶点的无向图，边的总数最多为（）A.10B.45C.90D.1006.对n个记录的文件进行快速排序，所需要的辅助存储空间为（）A.O(1)B.O(logn)C.O(n)D.O(n^2)7.哈希表的平均查找长度（）A.与处理冲突方法有关而与表的长度无关B.与处理冲突方法无关而与表的长度有关C.与处理冲突方法有关且与表的长度有关D.与处理冲突方法无关且与表的长度无关8.下列排序算法中，平均时间复杂度最小的是（）A.冒泡排序B.选择排序C.插入排序D.快速排序9.若某完全二叉树的深度为h，则该完全二叉树中至少有（）个节点A.2^(h-1)B.2^(h-1)-1C.2^hD.2^h-110.在一个单链表中，若要删除p节点的后续节点，则执行（）A.p=p->next;B.p->next=p->next->next;C.p->next=p;D.p=p->next->next;多项选择题（每题2分，共10题）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.邻接矩阵B.邻接表C.十字链表D.邻接多重表7.以下排序算法中，稳定的排序算法有（）A.冒泡排序B.插入排序C.归并排序D.选择排序8.哈希函数的构造方法有（）A.直接定址法B.除留余数法C.数字分析法D.平方取中法9.完全二叉树的特点有（）A.叶子节点只能出现在最下两层B.最下层的叶子节点一定集中在左部连续位置C.倒数第二层若有叶子节点，一定都在右部连续位置D.度为1的节点只有0个或1个10.以下关于双向链表说法正确的是（）A.可以双向遍历B.插入操作比单链表复杂C.每个节点有两个指针域D.查找操作效率高于单链表判断题（每题2分，共10题）1.线性表的顺序存储结构优于链式存储结构。（）2.栈和队列都是特殊的线性表。（）3.二叉树的前序遍历和中序遍历结果不同。（）4.无向图中所有顶点的度之和等于边数的2倍。（）5.快速排序在最坏情况下的时间复杂度为O(n^2)。（）6.哈希表中冲突是不可避免的。（）7.堆排序是一种稳定的排序算法。（）8.一棵满二叉树一定是完全二叉树。（）9.单链表的删除操作不需要移动元素。（）10.队列的插入操作在队头进行。（）简答题（每题5分，共4题）1.简述栈和队列的区别。栈是先进后出的数据结构，操作在栈顶进行；队列是先进先出的数据结构，入队在队尾，出队在队头。2.简述图的邻接矩阵和邻接表存储结构的优缺点。邻接矩阵优点是简单直观，便于判断顶点间是否有边；缺点是存储稀疏图浪费空间。邻接表优点是存储稀疏图节省空间；缺点是判断顶点间是否有边较复杂。3.简述插入排序的基本思想。将未排序数据插入已排序序列的合适位置。初始已排序序列只有第一个元素，然后依次将后面元素插入已排好序的序列中。4.简述二叉树的中序遍历递归算法。若二叉树为空，返回。否则，先中序遍历左子树，访问根节点，再中序遍历右子树。讨论题（每题5分，共4题）1.讨论在不同应用场景下如何选择合适的数据结构。在需要频繁插入、删除操作时，链式结构合适，如单链表；需要快速查找，哈希表或平衡二叉树较好；元素有序且访问顺序固定，顺序表可行；表示层次关系用树，网状关系用图。2.分析排序算法中稳定性的重要性。在一些特定应用中，稳定性很关键。比如按成绩排序学生记录，若排序算法不稳定，相同成绩学生记录顺序可能改变，若还有其他关联信息，可能导致错误结果，稳定排序能保证相同元素原有顺序。3.探讨哈希表中处理冲突的方法及其优缺点。开放定址法优点是简单直观，缺点是可能形成聚集现象。链地址法优点是不会产生聚集，缺点是增加指针空间开销。再哈希法计算复杂但可减少冲突。不同方法适用于不同情况。4.论述树和二叉树在数据表示和处理上的联系与区别。联系：二叉树是树的特殊形式，很多树的处理算法可借鉴二叉树。区别：树节点孩子数无限制，二叉树节点最多两个孩子；二叉树有严格左右之分，树无；二叉树遍历方法更丰富规范。答案单项选择题1.A2.B3.D4.C5.B6.B7.C8.D9.A10.B多项选择题1.AB2.AC