2023年自考-自考专业(计算机信息管理)-数据结构导论考试历年全考点试题荟萃附带答案.docxVIP

2023年自考-自考专业(计算机信息管理)-数据结构导论考试历年全考点试题荟萃附带答案 （图片大小可任意调节） 第1卷 一.单选题(共10题) 1.在查找顺序表各结点概率相等的情况下，顺序按值查找某个元素的算法时间复杂度为（） A.O(1) B.O(n) C.O( √n ) D.O(log 2n) 2.如果结点A有3个兄弟结点，而且B为A的双亲，则B的度为（） A.1 B.3 C.4 D.5 3.在栈中进行插入和删除操作的一端称为（） A.栈顶 B.栈底 C.任意位置 D.指定位置 4.已知一个有序表为(13，18，24，35，47，50，62，83，90，115，134)，当二分查找值为90的元素时，查找成功时需比较的次数为（） A.1 B.2 C.3 D.4 5.数据表A中每个元素距其最终位置较近，则最省时间的排序算法是（） A.堆排序 B.插入排序 C.直接选择排序 D.快速排序 6.设字符串S1=″ABCDEFG″，S2=″PQRST″，则运算S=CONCAT(SUBSTR(S1,2,LENGTH(S2)),SUBSTR(S1,LENGTH(S2),2))后S的结果为() A.″BCQR ″ B.″BCDEF ″ C.″ BCDEFG ″ D.″BCDEFEF ″ 7.有关图中路径的定义，表述正确的是（） A.路径是顶点和相邻顶点偶对构成的边所形成的序列 B.路径是不同顶点所形成的序列 C.路径是不同边所形成的序列 D.路径是不同顶点和不同边所形成的集合 8.二叉树的第i(i≥1)层上所拥有的结点个数最多为（） A. B.2i C. D. 9.由带权为 9，2，5，7 的四个叶子结点构造一棵哈夫曼树， 该树的带权路径长度为（） A.23 B.37 C.44 D.46 10.在平衡二叉树中插入一个结点后造成了不平衡，设最低的不平衡结点为A，并且A的左孩子的平衡因子为-1，右孩子的平衡因子为0，则使其平衡的调整方法为() A.LL 型 B.LR 型 C.RL 型 D.RR 型 二.填空题(共3题) 1.若满二叉树的结点数为n，则其高度为______。 2.顺序查找算法的平均查找长度为________。 3.深度为k的二叉树，结点数最多有_______个。 第2卷 一.单选题(共10题) 1.设无向图的邻接表如题14图所示，则该图的边数为（） A.4 B.5 C.10 D.20 2.元素的进栈次序为 A，B，C，D，E，则退栈中不可能的序列是（） A.A，B，C，D，E B.B，C，D，E，A C.E，A，B，C，D D.E，D，C，B，A 3.在表长为n的顺序表上做插入运算，平均要移动的结点数为（） A.n/4 B.n/3 C.n/2 D.n 4.在已知尾指针的单循环链表中，插入一个新结点使之成为首结点，其算法的时间复杂度为（） A.O（ 1） B.（log 2n） C.O（ n） D.O(n 2 ) 5.下列排序算法中，某一趟结束后未必能选出一个元素放在其最终位置上的是（） A.堆排序 B.冒泡排序 C.直接插入排序 D.快速排序 6.组成数据的基本单位是（） A.数据项 B.数据类型 C.数据元素 D.数据变量 7.顺序表中有19个元素，第一个元素的地址为200，且每个元素占一个字节，则第14个元素的存储地址为() A.212 B.213 C.214 D.215 8.冒泡排序的时间复杂度是（） A.O(n 2 ) B.O(nlog 2n) C.O(n) D.O(log 2n) 9.在顺序表中查找第 i 个元素，时间效率最高的算法的时间复杂度为（） A.O(1) B.O(√n ) C.O(log 2n) D.O(n) 10.下列各项键值序列中不是堆的为（） A.{5 ，23，16，68，94，72，71， 73} B.{5 ，16，23，68，94，72，71， 73} C.{5 ，23，16，73，94，72，71， 68} D.{5 ，23，16，68，73，71，72， 94} 二.填空题(共3题) 1.在一个具有n个顶点的无向图中，顶点的度最大可达________。 2.数据的逻辑结构被分为集合结构、 ________、树形结构和图状结构 4 种。 3.线性表中所含结点的个数称为________。 第1卷参考答案 一.单选题 1.参考答案： B 2.参考答案： C 3.参考答案： A 4.参考答案： B 5.参考答案：