数据结构期末测试.doc

计算机 专业 数据结构 试卷1 一、单项选择题(在每小题的四个备选答案中，选出一个正确答案，并将正确答案的序号填在题干的括号内。每小题1分，共20分) 1. 在具有n个结点的有序单链表中插入一个新结点并使链表仍然有序的时间复杂度是( ) A).O(1) B).O(n) C).O(nlogn) D).O(n2) 2.一个栈的输入序列为H、I、J 、K，在进栈过程中可以出栈，则下列序列中可能是栈的输出序列的是( ) A）J H K I B）H J K I C）K H I J D）I K H J 3. 链栈与顺序栈相比，比较明显的优点是( ) A）插入操作更加方便 B）删除操作更加方便 C）不会出现下溢的情况 D）不会出现上溢的情况 4.若线性表最常用的操作是存取第i个元素及其前趋的值，则采取( )存储方式节省时间。 A）单连表 B）双连表 C）单循环连表 D）顺序表 5.求顶点对之间最短路径的FLOYD算法的时间复杂度为( ) A）O(n) B）O(n+e) C）O(n3) D）O(n×e) 6.设有7个结点的无向图，该图至少应有( )条边才能确保是一个连通图。 A）5 B）6 C）7 D）8 7.在判断一个表达式中圆括号是否配对的算法中，采用下述( )数据结构较合适。 A）线性表 B）栈 C）队列 D0树 8.队列操作的原则是( ) 9.下列方法中，不稳定的排序是（ ）A）后进先出 B）先进先出 C）只能进行插入 D）只能进行删除 A)冒泡排序 B)堆排序 C)直接插入排序 D)归幷排序 10.将一棵有50个结点的完全二叉树从根这一层开始，每一层上从左到右依次对结点进行编号，根结点的编号为1，则编号为24的结点的左孩子编号为( ) A）49 B）47 C）50 D）48 11. 采用两类不同存储结构的字符串可分别简称为( ) A).主串和子串 B).顺序串和链串 C).目标串和模式串 D).变量串和常量串 12.深度为n的二叉树中所含叶子结点的个数最多为( )个。 A).2n B).n C).2n-1 D).2n-1 13.树最适合用来表示( )。 A.有序数据元素 B.无序数据元素 C.元素之间具有分支层次关系的数据 D.元素之间无联系的数据 14..下列说法错误的是( )。 A.一个图的邻接矩阵表示是唯一的 B.一个图的邻接表表示是不唯一的 C.一个图的生成树必为该图的极小连通子图 D.一个无环有向图的拓扑排序序列必唯一 15.连通的无向图G有n个顶点，图的生成树有( )条边。 A. n B.n-1 C.n(n-1)/2 D.n/2 16.线性表是（ ） A.一个以上的元素构成的序列 B. 一个以上的元素构成的集合 C.任意个有限元素构成的集合 D. 任意个有限元素构成的序列 17. 已知广义表的表头为a，表尾为(b,c)，则此广义表为( ) A.(a,(b,c)) B.(a,b,c) C.((a),b,c) D.((a,b,c)) 18.设有一个有序表，分别用顺序查找法和二分查找法查找一个给定的键值，比较次数分别为s和b。在查找成功的情况下，s和b的关系为（ ） A. s=b B.sb C.sb D.不能确定 19. 在单链表中，指针p指向元素为x的结点，实现“删除x的后继”的语句是( ) A.p=p-next; B.p-next=p-next-next; C.p-next=p; D.p=p-next-next; 20.稀疏矩阵一般采用（ ）方法压缩存储。 A.三维数组 B.单链表 C. 三元组表 D.散列表 二、填空题(共10分，每题1分) （1）当问题的规模n趋向无穷大时，算法执行时间T(n