2009年10月全国高等教育自学考试数据结构导论真题.doc

发布时间：2022-09-24 发布人：admin 分类：说明书资料大小：0.06M 资料格式：doc 举报版权申诉

第1页 / 共4页

2009年10月全国高等教育自学考试数据结构导论真题.doc.pdf-第2页.jpg

第2页 / 共4页

2009年10月全国高等教育自学考试数据结构导论真题.doc.pdf-第3页.jpg

第3页 / 共4页

2009年10月全国高等教育自学考试数据结构导论真题.doc.pdf-第4页.jpg

第4页 / 共4页

文本预览

2009 年 10 月全国高等教育自学考试数据结构导论真题一、单项选择题(本大题共 15 小题，每小题 2 分，共 30 分) 在每小题列出的四个备选项中只有一个是符合题目要求的，请将其代码填写在题后的括号内。错选、多选或未选均无分。 1.在表长为 n 的顺序表上做插入运算，平均要移动的结点数为（） A.n/4 B.n/3 C.n/2 D.n 2.顺序表中有 19 个元素，第一个元素的地址为 200，且每个元素占一个字节，则第 14 个元素的存储地址为（） A.212 B.213 C.214 D.215 3.由顶点 V1，V2，V3 构成的图的邻接矩阵为，则该图中顶点 V1 的出度为（） A.0 B.1 C.2 D.3 4.元素的进栈次序为 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 5.由带权为 9，2，5，7 的四个叶子结点构造一棵哈夫曼树，该树的带权路径长度为（） A.23 B.37 C.44 D.46 6.在已知尾指针的单循环链表中，插入一个新结点使之成为首结点，其算法的时间复杂度为（） A.O（1） B.O（log2n） C.O（n） D.O(n2) 7.已知一个有序表为（13，18，24，35，47，50，62，83，90，115，134），当二分查找值为 90 的元素时，查找成功时需比较的次数为（） A.1 B.2

C.3 D.4 8.在查找顺序表各结点概率相等的情况下，顺序按值查找某个元素的算法时间复杂度为（） A.O(1) B.O(n) C.O( ) D.O(log2n) 9.下列各项键值序列中不是堆的为（） 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} 10.在线性表的下列存储结构中进行插入、删除运算，花费时间最多的是（） A.单链表 B.双链表 C.顺序表 D.单循环链表 11.在栈中进行插入和删除操作的一端称为（） A.栈顶 B.栈底 C.任意位置 D.指定位置 12.用 n 个值构造一棵二叉排序树，它的最大高度为（） A.n/2 B. n C. D.llog2n 13.冒泡排序的时间复杂度是（） A.O(n2) B.O(nlog2n) C.O(n) D.O(log2n) 14.设无向图的邻接表如题 14 图所示，则该图的边数为（）题 14 图 A.4 B.5 C.10

D.20 15.带表头结点链队列的队头和队尾指针分别为 front 和 rear，则判断队空的条件为（） A.front==rear B.front!=NULL C.rear!=NULL D.front==NULL 二、填空题(本大题共 13 小题，每小题 2 分，共 26 分) 请在每小题的空格中填上正确答案。错填、不填均无分。 16.下列程序段的时间复杂度为________。 i=0；s=0； while（i

题 31 图 32.写出题 32 图所示的有向图的邻接矩阵及该图的所有拓扑排序序列。题 32 图 33.写出键值（83，40，63，13，84，35，96，57，39，79，61，15）应用二路归并排序算法从小到大排序后各趟的结果。四、算法设计题(本大题共 2 小题，每小题 7 分，共 14 分) 34.若两棵二叉树 B1 和 B2 皆为空，或者皆不空且 B1 的左、右子树和 B2 的左、右子树分别相似，则称二叉树 B1 和 B2 相似。试编写算法，判别给定两棵二叉树是否相似。 35.设顺序表 va 中的数据元素递增有序。试编写算法实现将 x 插入到顺序表的适当位置上，以保持该表的有序性。

分享到：

赞收藏

资料库

2009年10月全国高等教育自学考试数据结构导论真题.doc

相关推荐

自考

热门标签

最新资料