数据结构复习题.doc

数据结构复习题一、单项选择题1.不带头结点的单链表head为空的判断条件是( )。A.head=NULL B.head-next=NULLC.head-next=head D.head!=NULL 2.带头结点的单链表head为空的判断条件是( )。A.head=NULL B.head-next=NULLC.head-next=head D.head!=NULL 3.线性表的长度是指（ ）A.顺序存储方式下数组所占的空间大小B.链式存储方式下所有结点占用的空间大小C.表中的元素个数D.所能存储的最大的结点个数4.栈和队列都是（ ）。A.顺序存储的线性表 B.链式存储的线性表C.限制存取点的线性结构 D.限制存取点的非线性结构5.设输入序列为的1,2,3,4,借助一个栈不可以得到的输出序列是( )。A.1,2,3,4 B.3,2,4,1C.4,3,1,2 D.4,3,2,16.单链表中，增加头结点的目的是为了（ ）。A.方便运算的实现 B.用于标识单链表C.使单链表中至少有一个结点 D.用于标识起始点的位置7.从具有n个结点的单链表中查找值等于x的结点时，在查找成功的情况下，平均需比较（ ）个结点。A.n B.n/2C.(n-1)/2 D.(n+1)/28.线性表是具有n个( )的有限序列。A. 表元素 B. 字符C. 数据元素 D. 信息项 9.某二叉树的前序和后序序列正好相同，则该二叉树一定是( )的二叉树。A. 空或只有一个结点 B. 高度等于其结点数 C. 任一结点无左孩子 D. 任一结点无右孩子10.下列排序算法中,第一趟排序完毕后,其最大或最小元素一定在其最终位置上的算法是( )。A. 归并排序 B. 直接插入排序 C. 快速排序 D. 冒泡排序 11.深度为n的二叉树中所含叶子结点的个数最多为（ ）个。A.2n B.n C.2n-1 D.2n-112.某数组第一个元素的存储地址为100，每个元素的长度为2，则第五个元素的地址是（ ）。A.110 B.108 C.100 D.12013.串是（ ）。A.一些符号构成的序列 B.一些字母构成的序列 C.一个以上字符构成的序列 D.任意有限个字符构成的序列14.在一个具有n个顶点的无向图中,要连通全部顶点至少需要( )条边。A.n B.n+1 C.n-1 D.n/215.下列四个关键词序列中,( )不是堆。A.05,23,16,68,94,72,71,73 B.05,16,23,68,94,72,71,73 C.05,23,16,73,94,72,71,68 D.05,23,16,68,73,71,72,94 16.在一个单链表中，已知(*q)结点是(*p)结点的前驱结点，若在(*q)和(*p)之间插入(*s)结点,则执行( )。A.s-next=p-next; p-next=s; B.p-next=s-next; s-next=p;C.q-next=s; s-next=p; D.p-next=s; s-next=q;17.设输入序列为的1,2,3,4,借助一个栈可以得到的输出序列是( )。A.1,3,4,2 B.3,1,4,2C.4,3,1,2 D.4,1,2,318.二分查找法要求查找表中各元素地键值必须是( )排列。A. 递增或递减 B. 递增C. 递减 D.无序19下列排序算法中,某一趟结束后未必能选出一个元素放其最终位置上的是( )。A. 堆排序 B. 冒泡排序C. 快速排序 D. 直接插入排序20.设有5000个无序的元素,希望用最快的速度挑选出其中前5个最大的元素,最好选用( )法。A.冒泡排序 B.快速排序C.堆排序 D.基数排序21.任何一个无向连通图的最小生成树( )。A. 只有一棵 B. 有一棵或多棵C. 一定有多棵 D. 可能不存在22.3个结点可构成（ ）个不同形态的二叉树。A.2 B.3 C.4 D.523.设有6000个无序的元素,希望用最快的速度挑选出其中前6个最大的元素,最好选用( )法。A.冒泡排序 B.快速排序C.堆排序 D.基数排序24.某数组第一个元素的存储地址为200，每个元素的长度为4，则第五个元素的地址是（ ）。A.210 B.208 C.216 D.22025.在一个具有n个顶点的完全无向图的边数为 ( )。A.n(n+1)/2 B. n(n-1)/2 C.n(n-1) D. n(n+1)26.将一棵有100个结点的完全二叉树从根这一层开始，每一层上从左到右依次对结点进行编号，根结点的编号为1，则编号为49的结点的右孩子编号为( )。A.98 B.99 C.50 D.48 27.在线索二叉树中,结点(*t)没有左子树的充要条件是( )。 A. t-left=NULL B. t-ltag=1 C.t-ltag=1 & t-left=NULLD.以上都不对28.链栈和顺序栈相比，有一个较明显的优点是( )。A.通常不会出现栈满的情况 B. 通常不会出现栈空的情况C.插入操作更加方便 C.删除操作更加方便29.对于键值序列72,73,71,23,94,16,5,68,76,103用筛选法建堆，必须从键值为( )的结点开始。A.103 B. 72 C.94 D.2330.对有n个记录的有序表采用二分查找，其平均查找长度的量级为( )。A.O(n) B. O(nlog2n) C. O(1) D. O(log2n)二、填空题1.数据结构的三个方面：数据的 、 、 。2.下面程序段中，执行s语句的次数为 。for (int i=1;i=n;i+) for (int j=1;j=n;j+) s;3.在n个结点的顺序表中插入一个结点需平均移动 个结点，具体移动次数取决于 。4.采用二叉链表存储结构，具有n个结点的二叉树一共有 个指针域，其中 指针域为空。 5.在有序表(12,24,36,48,60,72,84)中二分查找关键词72时所需进行的关键词比较次数为 。 6.图的存储结构最常用的有 和邻接表。7.二叉树的存储结构有 和链式存储结构。8.对于一棵二叉树，设叶子结点数为n0,度为2的结点数为n2,则n0和n2的关系是 。9.一般树的存储结构有双亲表示法、孩子兄弟表示法和 。10.每个结点只有 链接域的链表叫做单链表。11.从逻辑关系上讲，数据结构主要分为两大类：线性结构和 。12.100个结点的完全二叉树的叶子结点数为 。13.图的存储结构最常用的有 和邻接矩阵。14.二叉树的存储结构有顺序存储结构和 。15.一般树的存储结构有双亲表示法、孩子链表表示法和 。16.二叉树的遍历方式有三种： 、 和后根遍历。 17.深度为8的（根的层次号为1）满二叉树有 个叶子结点。18.n个的顶点的连通图的生成树有 条边。19.如果一个有向图中没有 ，则该图的全部顶点可以排成一个拓扑序列。20. 具有64个结点的完全二叉树的深度为 。三、应用题1.已知一棵二叉树的前序遍历的结果是ABECDFGHIJ, 中序遍历的结果是EBCDAFHIGJ, 试画出这棵二叉树。2.把下列森林转化为一棵二叉树。3. 给定表（45,36,56,6,64,78,8,96），按数据元素在表中的次序构造一棵二叉排序树。4. 试分别画出具有3个结点的树和有具有3个结点的二叉树的所有不同形态。5.已知一个图如下所示，若从顶点1出发分别求出其深度优先搜索和广度优先搜索序列。6.根据下图给出的二叉树，求出先序、中序和后序遍历的结点序列。acedfb7.分别用普里姆算法(Prim)和克鲁斯卡尔（Kruskal）算法求出下图的最小生成树。 8.已知数据序列为12,5,9,20,6,31,24,对该数据序列进行排序，试写出快速排序每趟的结果。9.把下图中的二叉树转