2017年电大本科《数据结构（本）》期末复习试题及答案

2017 年电大本科数据结构（本）期末复习试题及答案  一、单项选择题  1栈和队列的共同特点是（）。  。  3对一个栈顶指针为 链栈进行入栈操作，通过指针变量 p 生成入栈结点，则执行：p=(p->a;和（）。  p;p=p; p=p=4树状结构中数据元素的位置之间存在（）的关系。  A每一个元素都有一个直接前驱和一个直接后继 B一对一  C多对多 D一对多  5设头指针为 非空的单向链表 ,指针 p 指向尾结点 ,则通过以下操作 () 可使其成为单向循环链表。  A p-> p; C p-> p=6设有一个长度为 26 的顺序表，要插入一个元素 ,并使它成为新表的第 6 个元素 ,需  移动元素的个数为（）。  A 21B 22C 20D 19 7一种逻辑结构（）。  A只能有唯一的存储结构 B可以有不同的存储结构  C与存储该逻辑结构的计算机相关 D是指某一种数据元素的性质  8头指针为 带头结点的单向循环链表， p 所指向尾结点，要使该链表成为  不带头结点的单向循环链表 ,可执行 （）。  A p=p C p->p->9把数据存储到计算机中，并具体体现数据元素间的逻辑结构称为（）。  A存储结构 B逻辑结构  C数据元素的存储 10元素 111， 113， 115， 117 按顺序依次进栈，则该栈的不可能输出序列是（）（进  栈出栈可以交替进行）。  A 117， 115， 113， 111B 111， 113， 115， 117 C 117， 115， 111， 113D 113， 111， 117， 115 11图状结构中数据元素的位置之间存在（）的关系。  A一对一 B一对多  C多对多 D每一个 元素都有一个且只有一个直接前驱和一个直接后继  12以下说法正确的是（）。  A栈的特点是先进先出  B栈的特点是先进后出  C队列的特点是先进后出  13一个单链表中 ,在 p 所指结点之后插入一个 s 所指的结点时，可执行 : s->p->（）。  A s=p-> p->s->C p=s-> p->s; 0 阶的对称矩阵 A(第一个元素为 )，采用压缩存储的方式，将其下三  角部分以行序为主序 存储到一维数组 B 中（数组下标从 1 开始），则矩阵元素  在一维数组 B 中的下标是（）。  A 21B 28C 17D 23 15元素 12， 14， 16， 18 顺序依次进栈，则该栈的不可能输出序列是（）。  （进栈出栈可以交替进行）。  A 18， 16， 14， 12B 12， 14， 16， 18 D 14， 12， 18， 16D 18， 16， 12， 14 16设有串  ,   , ,以下四个串中最大的是 ()。  A 7设有一 个 30 阶的对称矩阵 A(第一个元素为 )，采用压缩存储的方式，将其  下三角部分以行序为主序存储到一维数组 B 中（数组下标从 1 开始），则矩阵中元  素  在一维数组 B 中的下标是（）。  A 41B 32C 18D 38 a 经初始化 =“ ;a7中存放的是（）。  h C. h h 19设有一个长度为 32 的顺序表，要删除第 8 个元素需移动元素的个数为（）。  A 15B 22C 14D 24  以下模式串能与主串成功匹配的是（）。  编号为 i 的结点存在右孩子，则右孩子的顺序编号为（）。  A 222i+1D 2i+2 22在一棵二叉树中，若编号为 i 的结点存在左孩子，则左孩子的顺序编号为（）。  A 2i+1B 222i+2 23一棵具有 16 个结点的完全二叉树，共有（）层。 (设根结点在第一层 ) A 7B 6C 4D 5 24如图 1 所示，若从顶点 a 出发，按图的广度优先搜索法进行遍历，则可能得  到的一种顶点 序列为（）。  A 5如图 2 所示，若从顶点 a 出发，按图的深度优先搜索法进行遍历，则可能得  到的一种顶点序列为（）。  A 6线性表以（）方式存储，能进行折半查找。  A链接 B顺序 C关键字有序的顺序 D二叉树  子串是 ()。  A.“.“C.“.“321a” 28一棵具有 38 个结点的完全 二叉树，最后一层有（）个结点。  A 7B 5C 6D 8 29如图 3 所示，若从顶点 a 出发，按广度优先搜索法进行遍历，则可  能得到的一种顶点序列为（）。  A  的拓扑序列是 ()。  A 52346B 23645 C 、填空题  可采用三元组表，一个有 10 行的稀疏矩阵 A 共有 97 个  零元素，其相应的三元组表共有 3 个元素。该矩阵 A 有列。  2结构中的数据元素存在多对多的关系称为 _结构。  3在单向链表中， q 指向 p 所指结点的直接后继结点，要删除 q 所指结点，可以用  操作 _=q->  元素进行冒泡法排序，第 j 趟冒泡要进行 _次元素间的比较。  阵中每个非零元素对应的三元组包括该元素的行下标、列下标和 _三项信息。  6中序遍历 _树可得到一个有序序列。  _。  ,3,4,1,2,5,9,采用直接选择排序算法 ,当进行了两趟选择后 ,结果 序列为 ()。  9 n 个元素进行冒泡法排序，通常需要进行 _趟冒泡。  10 广义表 (a,b),d,e,(i,j),k)的长度是 _。  11中序遍历二叉排序树可得到一个 _的序列。  c， a,(a,b),d,e,(i,j),k)深度是 _。  c,a,(a,b),d,e,(i,j),k)的长度是 _。  可采用三元组表，一个有 10 行 10 列的稀疏矩阵 A 共有 95 个零元素，其相应的三元组表共 有个元素。  c,a,(a,b),d,e,(i,j),k)深度是 _。  16在对一组记录 (50,49,97,22,16,73,65,47,88)进行直接插入排序时，当把第 7 个记录 65 插入到有序表时，为寻找插入位置需比较 _次。  空的判定条件为 _。   个叶结点的哈夫曼树 ,该树中总共有 _个结点。  言中 ,字符串“ E”存储时占个字节。   的完全二叉树，第四层上 有 5 个结点，该树共有 _个结点。  （根所在结点为第 1 层）。  21一棵二叉树中有 n 个非叶结点，每一个非叶结点的度数都为 2，则该树共有 _ 个叶结点。  22设有一个长度为 40 的顺序表，要删除第 8 个元素需移动元素的个数为 _。 23在对一组记录 (55,39,97,22,16,73,65,47,88)进行直接插入排序时，当把第 7 个记录 65 插入到有序表时，为寻找插入位置需比较 _次。  =“ p=a; p!= 0 )n+;p+;结果中， n 的值是 _。  三、综合题  1设查找表为 (1,10,11,14,23,27,29,55,68),元素的下标依次为 1,2,3,， 9。  （ 1）画出对上述查找表进行折半查找所对应的判定树（树中结点用下标表示）。  （ 2）说明成功查找到元素 14,需要依次经过与哪些元素的比较？共几次比较？  （ 3）求在等概率条件下，成功查找的平均比较次数？  . 2有一个长度为 11 的有序表 (1,2,11,15,24,28,30,56,69,70,80),元 素的下标依次为  1,2,3, ,11，按折半查找对该表进行查找。  (1）画出对上述查找表进行折半查找所对应的判定树。  （ 2）说出成功查找到元素 56,需要依次经过与哪些元素的比较？  （ 3）说出不成功查找元素 72,需要进行元素比较的次数？  3  (1)以 3， 4， 5， 8， 9，作为叶结点的权，构造一棵哈夫曼树。  (2)给出相应权重值叶结点的哈夫曼编码。  (3)n 个叶结点的哈夫曼树，总共有多少个结点？  4.(1)一组记录的关键字序列为（ 57， 90， 67， 50， 51， 56），利用堆排序（堆顶元素是最小元素）的方法建 立初始堆（要求以完全二叉树描述）。  (2)对关键字序列 (56,51,71,54,46,106)利用快速排序，以第一个关键字为分割元素，  给出经过一次划分后结果。  (3)一组记录的关键字序列为（ 60,47， 80， 57， 39， 41， 46,30），利用归并排序的方法 ,分别给出 (1,1)归并、 (2,2)归并、 (4,4)归并的结果序列。  四、程序填空题  1以下是中序遍历二叉树的递归算法的程序，完成程序中空格部分（树结构中左、  右指针域分别为  据域 字符型， 向根结点）。  T) T!= （ 1） ; （ 2） ; T-> 利用上述程序对右图进行遍历，结果是（ 3） ; 16， 20， 26， 24），以不带头结点的单向链表存储，链表头指针为 下程序的功能是输出链表中各结点中的数据域   # p; p=*p 为工作指针 */ %dn”,_(1)_); _(2)_; _(3)_); 3以下冒泡法程序对存放在 a1， a2， an中的序列进行排序，完成程序中的空格部分，其中 n 是元素个数，要求按升序排列。  ,j,j=1;（ 1） ;j+); ; i=1;（ 2） ;i+) if(aiai+1; ai; （ 3） ; （ 4） ; if(0) 设有序列 6， 4， 5， 8， 2， 1，给出由该程序经过两趟冒泡后的结果序列（ 5）   a1,a2, an中的记录进行直接选择排序，完成  程序中的空格    , j,k; i=1;4 数组元素  6二叉排序树  7后出  8 1， 2， 4， 8， 3， 5， 9 9 0 4 11有序  12 3 13 6 14 5 15 3 16 3 8 9  22 32 4 7 三、综合题  1  (1) (2)按序号 5,2,3,4。按元素 23， 10， 11， 144 次  (3)1+2*2+3*4+4*2)/9=25/9 2  (1) (2)28,69,30,56 (3)4 次  3. (1) (2)3:000 4:001 5:01 8:10 9:11 (3)2  (1) (2)46,51,54,56,71,106 (3)(47,60)(57,80)(39,41)(30,46) (47,57,60,80)(30,39,41,46) (30,39,41,46,47,57,60,80) 四、程序填空题  1.（ 1） T->（ 2）  %c” ,（ 3）  （ 1） p-> 2） p=p-> 3） p!=  （ 1） （）。  A p= p= p;D p->)。   )。  存储结构必须占用连续的存储空间  C一种逻辑结构只能有唯一的存储结构  D线性表的顺序存储结构不必占用连续的存储空间  5设有一个长度为 18 的顺序表，要删除第 7 个元素需移动元素的个数为（）。  A 13B 12C 11D 10 6把数据存储到计算机中，并具体体现 ()称为物理结构。  A数据的处理方法 B数据的性质  C数据的运算 。  A)和 (C)两个条件  应位置上的字符相等 8顺序表所具备的特点之一是（）。  A可以随机访问任一结点 B不需要占用连续的存储空间  C插入元素的操作不需要移动元素 D删除元素的操作不需要移动元素  已知尾指针的条件  下 ,选用下列（）存储方式最节省运算时间。    10图状结构中数据元素的位置之间存在（）的关系。  A一对一 B一对多  C多对多 D每一个元素都有一个直接前驱和一个直接后继  11元素 13， 15， 19， 20 顺序依次进栈，则该栈的不可能输出序列是（）。  进栈出栈可以交替进行）。  A 20， 19， 15， 13B 13， 15， 19， 20 C 19， 13， 15， 20D 15， 13， 20， 19 12元素 20， 14， 16， 18 按顺序依次进栈，则该栈的不可能输出序列是（）  （进栈出栈可以交替进行）。  A 18， 16， 14， 20 B 20， 14， 16， 18 C 18， 16， 20， 14 D 14， 20， 18， 16 13设指针 q 指向单链表中结点 A，指针 p 指向单链表中结点 A 的后继结点 B，则在  表中 删除结点 B 的操作为（）。  =q；  p-> q->  p；  14设有一个 12 阶的对称矩阵 A(左上角第一个元素为 )，采用压缩存储的方式，将其下三角部分以行序为主序存储到一维数组 B 中（数组下标从 1 开始），则矩阵中元素  在一维数组 B 中的下标是（）。  A 12B 14C 13D 11 )。  .16设有一个长度为 22 的顺序表，要删除第 8 个元素需移动元素的个数为（）。  A 25B 14C 15D 23 进行插入运算时 ()。  指针都需要修改  指针都不需要修改  18在一棵二叉树中，若编号为 5 的结点存在右孩子，则右孩子的顺序编号为（）。  A 12B 9C 11D 10       最大的是（）。  0一棵具有 5 层的完全二叉树，最后一层有 4 个结点，则该树总共有（）个结点。  A 14B 15C 19D 18 21设有一个 20 阶的对称矩阵 A(第一个元素为 )，采用压缩存储的方式，将其  下三角部分以行序为主序存储到一维数组 B 中（数组下标从 1 开始），则矩阵中元  素  在一维数组 B 中的下标是（）。  A 23B 17C 21D 18  所示，若从顶点 a 出发，按图的广度优先搜索法进行遍历，则可能得到的一种顶点序列为（）。  A )。  子树上所有结点的值  均大于根结点的值。则该树为二叉排序树。  小于其右子  树上所有结点的值 ,则该树为二叉排序树。  于其右孩子的值。则该树  为二叉排序树。   子串是（）。  A. 21B.   321a  k 层的结点数最多为 ()。  a 经初始化 =“ ;a1中存放的是（）。  n C. n D. E   所示，若从顶点 6 出发，按深度优先搜索法进行遍历，则可能得到的一种顶点序列为（）。  A 6,9,3,2,8,7,4B 6,9,2,3,7,8,4C 6,2,7,9,8,4,3D 6,2,8,7,9,3,4 28如图 3 所示，若从顶点 a 出发，按图的深度优先搜索法进行遍历， 则可能得  到的一种顶点序列为（）。  A  所示，若从顶点 a 出发，按广度优先搜索法进行遍历，则可能得  到的一种顶点序列为（）。  A  的拓扑序列是 ()。  A 56423D 52364 二、填空题  =“ ;该字符串在计算机中存储时占 _个字节。  素进、出栈的 次序是 :先进 _。  3结构中的数据元素存在多对多的关系称为 _结构。  4对稀疏矩阵进行压缩存储，矩阵中每个非零元素对应的三元组包括该元素的三项信息是_。  可采用三元组表，一个有 8 行的稀疏矩阵 A 共有 92 个  零元素，其相应的三元组表共有 4 个元素。该矩阵 A 有 _列。  6在对 10 个记录的序列 (9， 35,19,77,2,10,53,45,27,68)进行直接插入排序时，当把第 6 个记录 10 插入到有序表时，为寻找插入位置，元素间需比较 _次。（按升序排序）    别为队头和队尾指针，最大存储空间元素为 用少用一个存储空间的模式，则判断循环链队列为空的条件是 _为真。   , , , 小的是 _。  元素进行冒泡法排序，第 j 趟冒泡要进行 _次元素间的比较。  10 10 个元素进行冒泡法排序， ,其中第 5 趟冒泡共需要进行 _次元素间的比较。  11设有一棵深度 为 4 的完全二叉树，第四层上有 5 个结点，该树共有 _个结点。（根所在结点为第 1 层）  12 _遍历一棵二叉排序树可得到一个有序序列。  13中序遍历一棵 _树可得到一个有序序列。  c,(a,b,c),(d,e,f),(i,j),k)的长度是 _。  ,4,5,1,2,6,10,采用直接选择排序算法 ,当进行了两趟选择后 ,结果序列为_。  c,(b,a,b),f,e,(i,j),k)深度是 _。  (a,b),d,e,(i,j),k)的长度是 _。  ,2,5,3,8,6,采用冒泡排序算法 (升序 ),经一趟冒泡后 ,结果序列是 _。  c， a,(a,b),d,e,(i,j),k)深度是 _。  ,3,4,1,2,5,9,采用直接选择排序算法 ,当进行了两趟选择后 ,结果序列为_。  _方式存储需要占用连续的存储空间。  _方式存储可以随 机访问。  _的顺序方式存储，可以用二分法排序。  ,6， 5， 1,2,4,3,8， 7 经过一趟 (1,1)归并后的结果序列为 _。  三、综合题  1  （ 1）设有数据集合 40， 29， 7， 73， 101， 4， 55， 2， 81， 92， 39，依次取集合中各  数据构造一棵二叉排序树。  (2)在上述二叉排序树上进行查找，给出成功查找到元素 92 的查找路径 ,其中共经过了多少次元素间的的比较。  (3)有一个长度为 10 的有序表，按折半查找对该表进行查找，给出在等概率情况下查  找成功的平均比较次数为。  2设查找表为  序号  1 2 3 4 5 6 7 8 9 10 11 序列  8 16 22 23 41 59 69 81 89 90 121 （ 1）画出对上述查找表进行折半查找所对应的判定树。  （ 2）说明成功查找到元素 90 需要经过多少次比较？  （ 3）说明不成功查找元素 82，依次与哪些元素进行了比较，需要经过多少次比较？  3. (1)以 2， 3， 4， 7， 8， 9 作为叶结点的权，构造一棵哈夫曼树，  (2)给出相应权重值叶结点的哈夫曼编码。  (3)一组记录的关键字序列为（ 47， 80， 57， 39， 41， 46），利用堆排序的方法建立的初始堆（堆顶元素是最小元素 ,以树的形式给出）。  4. (1)一组记录的关键字序列为（ 36， 69， 46， 28， 30， 35），给出利用堆排序（堆顶  元素是最小元素）的方法建立的初始堆（要求以完全二叉树描述）。  (2)对关键字序列 (36,69,46,28,30,74)采用快速排序，给出以第一个关键字为分割  元素，经过一次划分后的结果。  (3)设有数据集合 30,73,101,4,8,9,2,81，依次取集合中各数据构造一棵二叉排序树。  四、  程序填空题   1,3,7,5），以下程序用说明结构变量的方法建立单向链表，并输出  链表中各结点中的数据。   # b,c,d,*p; ; 0; 6; ;/*d 是尾结点 */  1） ; b; c; d; （ 2） ;/*以上结束建表过程 */ p=*p 为工作指针，准备输出链表 */  %dn” ,（ 3） ); （ 4） ; p!= 画出按该程序建立的单向链表的示意图，说明程序运行结束后 p 的指向。（ 5）  2设查找表为  序号  1 2 3 4 5 6 7 8 9 10 11 序列  8 16 22 23 41 59 69 81 89 90 121 （ 1）画出对上述查找表进行折半查找所对应的判定树。  （ 2）说明成功查找到元素 90 需要经过多少次比较？  （ 3）说明不成功查找 元素 82，依次与哪些元素进行了比较，