《数据结构章节练习题》由会员分享，可在线阅读，更多相关《数据结构章节练习题（21页珍藏版）》请在金锄头文库上搜索。
1、1数据结构章节练习题第一章 绪 论一、单选题1.一个数组元素 ai与_的表示等价。A、 *(a+i) B、 a+i C、 *a+i D、 &a+i 2.下面程序段的时间复杂度为_。for(int i=0; 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;C、q
2、-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.next，则
3、该线性表为_。3对于一个长度为 n 的顺序存储的线性表，在表头插入元素的时间复杂度为_，在表尾插入元素的时间复杂度为_。4对于一个长度为 n 的单链式存储的线性表，在表头插入元素的时间复杂度为_，在表尾插入元素的时间复杂度为_。5在线性表的顺序存储中，若一个元素的下标为 i，则它的前驱元素的下标为_，后继元素的下标为_。36在线性表的单链式存储中，若一个元素所在结点的地址为 p，则其后继结点的地址为_，若假定 p 为一个数组 a 中的下标，则其后继结点的下标为_。7在循环单链表中，最后一个结点的指针指向_结点。8在双向链表中每个结点包含有两个指针域，一个指向其_结点，另一个指向其_结点。9在循
4、环双向链表中表头结点的左指针域指向_结点，最后一个结点的右指针域指向_结点。10在以 HL 为表头指针的带表头结点的单链表和循环单链表中，链表为空的条件分别为_和_。三、应用题1在下面的每个程序段中，假定线性表 La 的类型为 List，元素类型 ElemType 为 int，并假定每个程序段是连续执行的，试写出每个程序段执行后所得到的线性表 La。(1) InitList(La);int a=48,26,57,34,62,79;for(i=0; i=2)试编写出计算 Fib(n)的递归算法和非递归算法，并分析它们的时间复杂度和空间复杂度。第四章 稀疏矩阵和广义表一、单选题1.在稀疏矩阵的带行
5、指针向量的链接存储中，每个行单链表中的结点都具有相同的_。A、 行号 B、 列号 C、 元素值 D、 地址2.设一个广义表中结点的个数为 n，则求广义表深度算法的时间复杂度为_。A、 O(1) B、 O(n) C、 O(n2) D、 O(log2n)二、填空题1.在一个稀疏矩阵中，每个非零元素所对应的三元组包括该元素的_、_和_三项。2.在稀疏矩阵所对应的三元组线性表中，每个三元组元素按_为主序、_为辅序的次序排列。3.在初始化一个稀疏矩阵的函数定义中，矩阵形参应说明为_参数。4.在稀疏矩阵的顺序存储中，利用一个数组来存储非零元素，该数组的长度应_对应三元组线性表的长度。5在稀疏矩阵的带行指针
6、向量的链式存储中，每个结点包含有_个域，在相应的十字链接存储中，每个结点包含有_个域。6在稀疏矩阵的十字链接存储中，每个结点的 down 指针域指向_相同的下一个结点，right 指针域指向_相同的下一个结点。7一个广义表中的元素分为_元素和_元素两类。8一个广义表的深度等于_嵌套的最大层数。9在广义表的存储结构中，每个结点均包含有_个域。10在广义表的存储结构中，单元素结点与表元素结点有一个域对应不同，各自分别为_域和_域。11若把整个广义表也看为一个表结点，则该结点的 tag 域的值为_，next 域的值为_。三、应用题61. 已知一个稀疏矩阵如下图所示： 0 4 0 0 0 0 00 0
7、 0 -3 0 0 18 0 0 0 0 0 00 0 0 5 0 0 00 -7 0 0 0 2 00 0 0 6 0 0 0具有 6 行7 列的一个稀疏矩阵(1)写出它的三元组线性表；(2)给出它的顺序存储表示；(3)给出它的转置矩阵的三元组线性表和顺序存储表示；2.画出下列每个广义表的带表头附加结点的链接存储结构图并分别计算出它们的长度和深度。(1) A=()(2) B=(a,b,c)(3) C=(a,(b,(c)(4) D=(a,b),(c,d)(5) E=(a,(b,(c,d),(e)(6) F=(a,(b,(),c),(d),e)第五章 树和二叉树（一）一、填空题1对于一棵具有 n
8、 个结点的树，该树中所有结点的度数之和为_。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、0 的结点数分别为_、_、_和_个。7假定
9、一棵树的广义表表示为 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一棵二叉树的广义表表示为 a(b(c,d)
10、,e(f(,g)，它含有双亲结点_个，单分支结点_个，叶子结点_个。14假定一棵二叉树顺序存储在一维数组 a 中，则 ai元素的左孩子元素为_，右孩子元素为_，双亲元素(i1)为_。715假定一棵二叉树顺序存储在一维数组 a 中，但让编号为 1 的结点存入 a0元素中，让编号为 2 的结点存入 a1元素中，其余类推，则编号为 i 结点的左孩子结点对应的存储位置为_，若编号为 i 结点的存储位置用 j 表示，则其左孩子结点对应的存储位置为_。16若对一棵二叉树从 0 开始进行结点编号，并按此编号把它顺序存储到一维数组 a 中，即编号为 0 的结点存储到 a0中，其余类推，则 ai元素的左孩子元素
11、为_，右孩子元素为_，双亲元素(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 个结点的完全二叉树被顺序存储于一维数组的 A1A
12、n元素中，试编写一个算法打印出编号为 i 的结点的双亲和所有孩子。2编写一算法，求出一棵二叉树中所有结点数和叶子结点数，假定分别用变参 C1 和 C2 统计所有结点数和叶子结点数，初值均为 0。第六章 二叉树的应用（二）一、单选题1. 从二叉搜索树中查找一个元素时，其时间复杂度大致为_。A、 O(n) B、 O(1) C、 O(log2n) D、 O(n2)2. 向二叉搜索树中插入一个元素时，其时间复杂度大致为_。A、 O(1) B、 O(log2n ) C、 O(n) D、 O(nlog2n)3. 根据 n 个元素建立一棵二叉搜索树时，其时间复杂度大致为_。A、 O(n) B、 O(log2
13、n ) C、 O(n2) D、 O(nlog2n)4. 从堆中删除一个元素的时间复杂度为_。A、 O(1) B、 O(n) C、 O(log2n) D、 O(nlog2n)5. 向堆中插入一个元素的时间复杂度为_。A、 O(log2n) B、 O(n) C、 O(1) D、 O(nlog2n)6. 由权值分别为 3,8,6,2,5 的叶子结点生成一棵哈夫曼树，它的带权路径长度为_。A、 24 B、 48 C、 72 D、 53二、填空题 1. 在一棵二叉搜索树中，每个分支结点的左子树上所有结点的值一定_该结点的值，右子树上所有结点的值一定_该结点的值。2对一棵二叉搜索树进行中序遍历时，得到的结点序列是一个_。3从一棵二叉搜索树中查找一个元素时，若元素的值等于根结点的值，则表明_，若元素的值小于根结点的值，则继续向_
