数据结构与算法(Python版)《数据结构》试题(A卷).docx

《数据结构》考试试卷（A卷） 班级：? ? ? ? ? 姓名：? ? ? ? 学号：? ? ? ? 分数：? ? ? ? 题号 一 二 三 四 五 六 七 八 九 十 总分 得分 评卷人 一. 单项选择题(每题2分，共30分) (1) 一个栈的入栈序列为1 2 3 4，以下出栈序列不可能得到的是(? ? ) A. 1 3 2 4? ? ? B. 2 3 4 1 C. 4 3 1 2? ? ? D. 3 4 2 1 (2) 若一个二叉树具有10个度为2的结点，则度为0的结点的个数为(? ? ) A. 9? B. 10? C. 11? D. 不确定 (3) 链式结构线性表的特点是：(? ? ) A. 便于随机存取? ? B. 花费的存储空间比顺序结构少 C. 便于插入和删除? ? D. 元素的物理顺序与逻辑顺序一致 (4) 一个二叉树的前序遍历序为ABCDEFG，则中序遍历序可能是：(? ? ) A. CABDEFG? B. ABCDEFG? ? ? ? C. DACEFBG? D. EABCDFG （5）树最适合用来表示(? ? ? )。 A.有序数据元素? ? ? ? ? ? ? ? ? ? ? B.无序数据元素 C.元素之间具有分支层次关系的数据? ? D.元素之间无联系的数据 (6) 下列有关图遍历的说法中不正确的是：(? ? ) A．连通图的深度优先搜索是一个递归过程。 B．图的广度优先搜索中邻接点的寻找具有“先进先出”的特征。 C．非连通图不能用深度优先搜索法。 D．图的遍历要求每一顶点仅被访问一次。 (7) 若已知待排序序列基本有序，则效率最高的排序方法是：(? ? ) A. 直接插入排序? ? ? ? B. 直接选择排序 C. 快速排序? ? ? ? D. 归并排序 (8) 对一棵完全二叉树按层次遍历序进行递增编号，根结点编号为1，那么编号为49的结点的左子的编号是：(? ? ) A. 98? ? B. 99? ? C. 50? ? D. 48 (9) 下列序列中不符合堆的定义的是：(? ? ) A. a c d g h m p q r x B. a c m d h p x g o r C. a d p r c q x m h g D. a d c m p g h x r q (10) 下列排序方法中，相同关键字元素的顺序不会被改变的排序方法是：(? ? ) A. 希尔排序法? ? B. 堆排序法? C. 快速排序? ? D. 归并排序法 (11) 在有n个叶结点的哈夫曼树上，结点总数为：(? ? ) A. 2n? ? ? B. 2n+1? ? ? C. 2n-1? ? ? D. 不确定 (12) 对于关键字值序列(12、13、11、18、60、15、7、18、25、100)建堆，调整的起点是：(? ? ) A. 100? ? B. 12? ? C. 60? ? D. 15 (13) 下列关键字序列中，是执行完一趟快速排序后得到的序列的是：(? ? ) A. [da,ax,eb,de,bb]ff[ha,gc]? ? ? ? B. [cd,eb,ax,da]ff[ha,gc,bb] C. [gc,ax,eb,cd,bb]ff[da,ha]? ? ? ? ? D. [ax,bb,cd,da]ff[eb,gc,ha] (14) 若从二叉树的任一结点出发到根的路径上所经过的结点序列按其关键字有序，则该二叉树是：(? ? ) A. 二叉排序树? ? ? B. 平衡二叉树? ? C. 堆? D. 哈夫曼树 (15) 在平衡二叉树中插入一个结点后造成了不平衡，设最低的不平衡结点为A，并已知A的左孩子的平衡因子为0右孩子的平衡因子为1，则应采取的调整型是：(? ? ) A. LL? B. LR? C. RL? D. RR 二.? 填空题(每题2分，共20分) （1）通常从四个方面评价算法的质量：______ 、______ 、______和_________。 （2） 若用链表存储一棵二叉树时，每个结点除数据域外，还有指向左孩子和右孩子的两个指针。在这种存储结构中，n个结点的二叉树共有________个指针域，其中有________个指针域是存放了地址，有________________个指针是空指针。 （3）AOV网是一种___________的图。 （4） 在一个具有n个顶点的无向完全图中，包含有________条边，在一个具有n个顶点的有向完全图中，包含有________条边。 三. 判断题 (每题2分，共30分) (1) 由二叉树的前序和后序遍历序可以推导出其中序遍历序。(? ? ) (2) 线性表的逻辑顺序和物理顺序总是一致的。(? ? ) (3) 有向图的邻接表结构比邻接矩阵结构要节省空间。(? ? ) (4) 栈和