1、数据结构期末复习练习题( 适用范围：广西电大开放专科计算机类专业 )广西电大理工教学部计算中心第一章 绪 论一、单选题1. 一个数组元素 ai与_的表示等价。A、 *(a+i) B、 a+i C、 *a+i D、 inext = HL; B、p-next = HL; HL = p;C、p-next = HL; p = HL;D、p-next = HL-next; HL-next = p;5在一个单链表 HL 中，若要在指针 q 所指的结点的后面插入一个由指针 p 所指的结点，则执行 。A、q-next = p-next ; p-next = q;B、p-next = q-next; q = p
2、;C、q-next = p-next; p-next = q;D、p-next = q-next ; q-next = p;6在一个单链表 HL 中，若要删除由指针 q 所指向结点的后继结点，则执行 。A、p = q-next ; p-next = q-next;B、p = q-next ; q-next = p;C、p = q-next ; q-next = p-next;D、q-next = q-next-next; q-next = q;二、填空题1在线性表的单链接存储结构中，每个结点包含有两个域，一个叫 域，另一个叫 域。2在下面数组 a 中链接存储着一个线性表，表头指针为 a0.ne
3、xt，则该线性表为 。3对于一个长度为 n 的顺序存储的线性表，在表头插入元素的时间复杂度为 ，在表尾插入元素的时间复杂度为 。4对于一个长度为 n 的单链接存储的线性表，在表头插入元素的时间复杂度为 ，在表尾插入元素的时间复杂度为 。5在线性表的顺序存储中，若一个元素的下标为 i，则它的前驱元素的下标为 ，后继元素的下标为 。6在线性表的单链接存储中，若一个元素所在结点的地址为 p，则其后继结点的地址为 ，若假定 p 为一个数组 a 中的下标，则其后继结点的下标为 。7在循环单链表中，最后一个结点的指针指向 结点。8在双向链表中每个结点包含有两个指针域，一个指向其 结点，另一个指向其 结点。
4、9在循环双向链表中表头结点的左指针域指向 结点，最后一个结点的右指针域指向 结点。10在以 HL 为表头指针的带表头附加结点的单链表和循环单链表中，链表为空的条件分别为 和 。三、应用题1在下面的每个程序段中，假定线性表 La的类型为 List，元素类型 ElemType为int，并假定每个程序段是连续执行的，试写出每个程序段执行后所得到的线性表 La。(1) InitList(La);int a=48,26,57,34,62,79;1026734 2574384560adtnext 86521for(i=0; i=2)试编写出计算 Fib(n)的递归算法和非递归算法，并分析它们的时间复杂度和
5、空间复杂度。第五章 树和二叉树一、填空题1对于一棵具有 n个结点的树，该树中所有结点的度数之和为_。2. 假定一棵三叉树的结点个数为 50，则它的最小深度为_，最大深度为_。3在一棵三叉树中，度为 3的结点数有 2个，度为 2的结点数有 1个，度为 1的结点数为 2个，那么度为 0的结点数有_个。4一棵深度为 5的满二叉树中的结点数为_个，一棵深度为 3的满三叉树中的结点数为_个。5假定一棵树的广义表表示为 A(B(C,D(E,F,G),H(I,J)，则树中所含的结点数为_个，树的深度为_，树的度为_。6假定一棵树的广义表表示为 A(B(C,D(E,F,G),H(I,J)，则度为 3、2、1、
6、0 的结点数分别为_、_、_和_个。7. 假定一棵树的广义表表示为 A(B(C,D(E,F,G),H(I,J)，则结点 H的双亲结点为_，孩子结点为_。8在一棵二叉树中，假定双分支结点数为 5个，单分支结点数为 6个，则叶子结点数为_个。9对于一棵二叉树，若一个结点的编号为 i，则它的左孩子结点的编号为_，右孩子结点的编号为_，双亲结点的编号为_。10在一棵二叉树中，第 5层上的结点数最多为_。11假定一棵二叉树的结点数为 18，则它的最小深度为_，最大深度为_。12一棵二叉树的广义表表示为 a(b(c,d),e(f(,g)，则 e结点的双亲结点为_，左孩子结点为_，右孩子结点为_。13. 一
7、棵二叉树的广义表表示为 a(b(c,d),e(f(,g)，它含有双亲结点_个，单分支结点_个，叶子结点_个。14. 假定一棵二叉树顺序存储在一维数组 a中，则 ai元素的左孩子元素为_，右孩子元素为_，双亲元素(i1)为_。15假定一棵二叉树顺序存储在一维数组 a中，但让编号为 1的结点存入 a0元素中，让编号为 2的结点存入 a1元素中，其余类推，则编号为 i结点的左孩子结点对应的存储位置为_，若编号为 i结点的存储位置用 j表示，则其左孩子结点对应的存储位置为_。16.若对一棵二叉树从 0开始进行结点编号，并按此编号把它顺序存储到一维数组 a中，即编号为 0的结点存储到 a0中，其余类推，
8、则 ai元素的左孩子元素为_，右孩子元素为_，双亲元素(i0)为_。17对于一棵具有 n个结点的二叉树，对应二叉链表中指针总数为_个，其中_个用于指向孩子结点，_个指针空闲着。18. 一棵二叉树广义表表示为 a(b(d(,h),c(e,f(g,i(k)，该树的结点数为_个，深度为_。19. 假定一棵二叉树广义表表示为 a(b(c),d(e,f)，则对它进行的先序遍历结果为_，中序遍历结果为_，后序遍历结果为_，按层遍历结果为_。20. 假定一棵普通树的广义表表示为 a(b(e),c(f(h,i,j),g),d)，则先根遍历结果为_，按层遍历结果为_。二、应用题1. 已知一棵具有 n个结点的完全
9、二叉树被顺序存储于一维数组的 A1An元素中，试编写一个算法打印出编号为 i的结点的双亲和所有孩子。2. 编写一算法，求出一棵二叉树中所有结点数和叶子结点数，假定分别用变参 C1和mlkjihegfbdcaC2统计所有结点数和叶子结点数，初值均为 0。3. 对于右图所示的树：(1) 写出先根遍历得到的结点序列；(2) 写出按层遍历得到的结点序列；(3) 画出转换后得到的二叉树和二叉链表。第六章 二叉树的应用一、单选题1. 从二叉搜索树中查找一个元素时，其时间复杂度大致为_。A、 O(n) B、 O(1) C、 O(log 2n) D、 O(n 2)2. 向二叉搜索树中插入一个元素时，其时间复杂
10、度大致为_。A、 O(1) B、 O(log 2n ) C、 O(n) D、 O( nlog2n)3. 根据 n个元素建立一棵二叉搜索树时，其时间复杂度大致为_。A、 O(n) B、 O(log 2n ) C、 O(n 2) D、 O( nlog2n)4. 从堆中删除一个元素的时间复杂度为_。A、 O(1) B、 O(n) C、 O(log 2n) D、 O( nlog2n)5. 向堆中插入一个元素的时间复杂度为_。A、 O(log 2n) B、 O(n) C、 O(1) D、 O( nlog2n)6. 由权值分别为 3,8,6,2,5的叶子结点生成一棵哈夫曼树，它的带权路径长度为_。A、 2
11、4 B、 48 C、 72 D、 53二、填空题 1. 在一棵二叉搜索树中，每个分支结点的左子树上所有结点的值一定_该结点的值，右子树上所有结点的值一定_该结点的值。2对一棵二叉搜索树进行中序遍历时，得到的结点序列是一个_。3从一棵二叉搜索树中查找一个元素时，若元素的值等于根结点的值，则表明_，若元素的值小于根结点的值，则继续向_查找，若元素的大于根结点的值，则继续向_查找。4在一个堆的顺序存储中，若一个元素的下标为 i，则它的左孩子元素的下标为_，右孩子元素的下标为_。5. 在一个小根堆中，堆顶结点的值是所有结点中的_，在一个大根堆中，堆顶结点的值是所有结点中的_。6当从一个小根堆中删除一个
12、元素时，需要把_元素填补到_位置，然后再按条件把它逐层_调整。三、应用题1. 已知一组元素为(46,25,78,62,12,37,70,29)，画出按元素排列顺序输入生成的一棵二叉搜索树。2. 空堆开始依次向堆中插入线性表（38,64,52,15,73,40,48,55,26,12）中的每个元素，请以线性表的形式给出每插入一个元素后堆的状态。3. 已知一个堆为（12,15,40,38,26,52,48,64） ，若需要从堆中依次删除四个元素，请给出每删除一个元素后堆的状态。4. 有七个带权结点，其权值分别为 3,7,8,2,6,10,14，试以它们为叶子结点构造一棵哈夫曼树，并计算出带权路径长
13、度 WPL。四、算法设计1编写在以 BST为树根指针的二叉搜索树上进行查找值为 item的结点的非递归算法，若查找成功则由 item带回整个结点的值并返回 true，否则返回 false。bool Find( BTreeNode * BST , ElemType HBT.size+;ElemType x=itemint i=HBT.size-1;while ( i != 0 )int j= ;if ( x=HBT.heapj) break;HBT.heapi=x;第七章 图一、填空题1在一个图中，所有顶点的度数之和等于所有边数的_倍。2在一个具有 n个顶点的无向完全图中，包含有_条边，在一个具有 n个顶点的有向完全图中，包含有_条边。 3. 在一个具有 n个顶点的无向图中，要连通所有顶点则至少需要_条边。4表示图的三种存储结构为_、_和_。5. 对于一个具有 n个顶点的图，若采用邻接矩阵表示，则矩阵大小为_。
