2022年数据结构试题集归纳 .pdf

1 数据结构（本）期末综合练习2017 年 5 月有得看就不难综合练习一一、单项选择题1 设有头指针为head 的带有头结点的非空单向循环链表, 指针 p 指向其尾结点, 要删除头结点 , 并使其仍为单向循环链表, 则可利用下述语句head =head-next ;（） 。 A p =head; Bp=NULL; C p-next =head; D head=p; 2在一个单链表中p 指向结点a, q指向结点a 的直接后继结点b，要删除结点b，可执行（） 。 A p-next=q-next ; Bp=q-next; Cp-next=q; Dp-next=q; 3. 以下说法不正确的是 A. 线性表的链式存储结构不必占用连续的存储空间 B 一种逻辑结构只能有唯一的存储结构 C. 一种逻辑结构可以有不同的存储结构D线性表的顺序存储结构必须占用连续的存储空间4在一个单向链表中, 在 p 所指结点之后插入一个s 所指的结点时，可执行（）; 和p-next=s; A p= s; B p-next=s-next; Cp=s-next; D s-next=p-next; 5把数据存储到计算机中，并具体体现( )称为物理结构。 A. 数据元素间的逻辑关系B数据的处理方法C数据的性质 D数据的运算6设有一个长度为23 的顺序表，要删除第8 个元素需移动元素的个数为（） 。 A16 B14 C15 D 13 7链表所具备的特点之一是（） 。 A 可以随机访问任一结点 B需要占用连续的存储空间 C 插入元素的操作不需要移动元素 D 删除元素的操作需要移动元素8设一棵有8 个叶结点的二叉树，度数为1 的结点有3 个 , 则该树共有（）个结点。A20 B18 C17 D16 9图状结构中数据元素的位置之间存在（）的关系。 A一对一 B多对多C一对多 D每一个元素都有一个直接前驱和一个直接后继10一棵具有5 层的完全二叉树，最后一层有4 个结点，则该树总共有（）个结点。 A14 B15 C19 D18 11元素 15，9，11，13 按顺序依次进栈，则该栈的不可能输出序列是（）（进栈出栈可以交替进行）。 A13，11，9，15 B 15，9， 11，13 C 13，11，15，9 D 9， 15 ，13，11 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 1 页，共 29 页 - - - - - - - - - 2 12. 设主串为“ FABcCDABcdEFaBc” ，以下模式串能与主串成功匹配的是（） 。 A. EFaBc B. ABCdE C. DABCC D .FAbcC 13设有一个14 阶的对称矩阵A(第一个元素为a1,1) ，采用压缩存储的方式，将其下三角部分以行序为主序存储到一维数组B中（数组下标从1 开始），则矩阵中元素a4,3在一维数组 B中的下标是（） 。 A9 B10 C11 D 8 14元素 111，113，115，117 按顺序依次进栈，则该栈的不可能输出序列是（） （进栈出栈可以交替进行） 。 A 117，115， 113，111 B111，113，115， 117 C113，111，117，115 D117，115，111， 113 15在一棵二叉树中，若编号为8 的结点存在右孩子，则右孩子的顺序编号为（） 。 A 18 B16 C15 D17 16以下说法不正确的是（） 。 A栈和队列都是线性结构 B栈的特点是后进先出 C. 栈和队列的特点都是先进后出 D队列的特点是先进先出17设一棵哈夫曼树共有14 个非叶结点，则该树总共有（）个结点。 A29 B.27 C30 D28 18设有一个15 阶的对称矩阵A(第一个元素为a1,1) ，采用压缩存储的方式，将其下三角部分以行序为主序存储到一维数组B中（数组下标从1 开始），则矩阵中元素a4,2 在一维数组B中的下标是（） 。A9 B8 C7 D10 19 如图 1 所示的一个图，若从顶点a 出发，按深度优先搜索法进行遍历，则可能得到的一种顶点序列为（） 。 A abecdf Bacfebd Caebcfd Daedbfc 20如图 2 所示的一个图，若从顶点a 出发，按深度优先搜索法进行遍历，则可能得到的一种顶点序列为（） 。 Aacedbf Bacebfd Caebcfd Daedfcb b d f e c a 图 1 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 2 页，共 29 页 - - - - - - - - - 3 二、填空题1. 队列的特点之一是：元素进、出队的次序是:先进 _。2. 序列 13,11,14,12,17,15,采用冒泡排序算法,经一趟冒泡后 ,序列的结果是_。3 _结构中，数据元素间存在一对多的关系。4. 对 16 个元素的序列用冒泡排法进行排序，通常需要进行_趟冒泡。5对稀疏矩阵进行压缩存储，矩阵中每个非零元素对应的三元组包括该元素的三项信息是 _ _。6. 对 9 个元素的一组记录（58，35， 93，20，12，78，56，41，79）进行直接插入排序(由小到大排序 ) ，当把第 7 个记录 56 插入有序表，为寻找插入位置需比较_次。7在对 11 个记录的序列 (12，35, 9, 7 ,2, 11 ,56 , 95 ,37,58 ,60)进行直接插入排序时，当把第 6 个记录 11 插入到有序表时，为寻找插入位置，元素间需比较_次。 （由小到大排列）8结构中的数据元素存在一对多的关系称为_结构。9哈希函数是记录关键字的值与该记录_ _之间所构造的对应关系。10设有一棵深度为5 的完全二叉树，第5 层上有 3 个结点，该树共有_ 个结点。（根所在结点为第1 层）1120 个元素进行冒泡法排序，通常需要进行19 趟冒泡,其中第 10 趟冒泡共需要进行_ _次元素间的比较。12 一棵二叉树中每一个非叶结点的度数都为2，共有 10 个非叶结点，则该树共有_ 个结点。13一棵有 19 个结点的二叉树,采用链式结构存储,该树结构中有_ 个指针域为空。14. 序列 3,1,7,18,6,9,13,12 经一趟归并排序的结果为_ _ _。15中序遍历一棵_树可得到一个有序序列。16 一棵有 16 个叶结点的哈夫曼树，则该树共有_个非叶结点。17二叉排序树插入操作中,新插入的结点总是以树的_ 结点被插入的18_遍历二叉排序树可得到一个有序序列。19. 广义表的 ( a , (d,a ,b) , h , (e ,( (i ,j ) ,k ) ) 深度是 _ 。20. 广义表 ( f , h , (a ,b, d, c) , d , e ,( (i ,j ) ,k ) ) 的长度是 _ _。21. 序列 4 , 2 , 5 , 3 , 8 , 6 , 7, 9,采用归并排序算法(升序 ),经一趟归并后 ,序列的结果_ _。b d f c e a 图 2 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 3 页，共 29 页 - - - - - - - - - 4 22. 广义表的 ( h ,c，g, a , (a ,b) , d , e ,( (i ,j ) ,k ) ) 深度是 _ _。23. 字符串 a1=teijing, a2 = tef , a3= teifang, a4=“tefi最小的是 _。24设有串 p1=”ABADF ”,P2=”ABAFD ” ，P3=”ABADFA ”P4=”ABAF ” , 四个串中最小的是_ 。三、综合题1设查找表为序号1 2 3 4 5 6 7 8 9 10 11 序列4 12 18 19 37 55 65 77 85 86 117 （ 1）画出对上述查找表进行折半查找所对应的判定树（树中结点用下标表示）（ 2）说明成功查找到元素86 需要经过多少次比较？（ 3）求在等概率条件下，成功查找的平均比较次数？2.（1）设有数据集合50，39，17，83，111，14，65，13，91，102，49 ，依次取集合中各数据构造一棵二叉排序树。 (2) 一组记录的关键字序列为（6，9，7，4， 5，8） ，利用堆排序（堆顶元素是最小元素）的方法建立初始堆。(要求用完全二叉树表示) 3. (1) 一组记录的关键字序列为（26，59， 36，18，20，25） ，给出利用堆排序（堆顶元素是最小元素）的方法建立的初始堆（要求以完全二叉树描述） 。(2) 对关键字序列 (26,59,36,18,20,64)采用快速排序，给出以第一个关键字为分割元素，经过一次划分后的结果。4. (1) 如下表为一个长度为10 的有序表，给出按折半查找对该表进行查找的判定树 (2) 按折半查找对该表进行查找，求在等概率情况下查找成功的平均比较次数。为了成功查找72 , 给出元素的比较次数。5(1) 以 1，2，3 ，6，7，8 作为叶结点的权，构造一棵哈夫曼树(2) 给出具有相应权重值的叶结点的哈夫曼编码。四、程序填空题1以下函数在 a0到an-1 中，用折半查找算法查找关键字等于k的记录，查找成功返回该记录的下标，失败时返回-1，完成程序中的空格typedef struct int key; 序号1 2 3 4 5 6 7 8 9 10 序列23 49 39 18 25 60 72 84 55 59 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 4 页，共 29 页 - - - - - - - - - 5 NODE; int Binary_Search(NODE a , int n, int k) int low, mid, high; low=0; high=n-1; while(_(1)_) mid=(_(2)_) if(amid.key=k) return _(3)_; else if ( _(4)_)low=mid+1; else _(5)_; return -1 2.设线性表以不带头结点的单向链表存储，链表头指针为head,以下程序的功能是输出链表中各结点中的数据域data。完成程序中空格部分。#define NULL 0 void main( ) NODE *head ,*p ; p=head; /*p 为工作指针 */ do printf(“%dn”, _(1)_); _(2)_ ; 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 5 页，共 29 页 - - - - - - - - - 6 while(_(3)_); 3.以下程序是前序遍历二叉树的递归算法的程序，完成程序中空格部分（树结构中左、右指针域分别为left 和 right，数据域 data为字符型， BT 指向根结点）。void Inorder (struct BTreeNode *BT) if(BT!=NULL) _(1)_;_(2)_;Inorder(BT- right); 利用上述程序对右图进行前序遍历，结果是_(3)_;4.以下程序是后序遍历二叉树的递归算法的程序，完成程序中空格部分（树结构中左、右指针域分别为left 和 right，数据域 data为字符型， BT 指向根结点）。完成程序中空格部分。void Inorder (struct BTreeNode *BT) if( BT!=NULL) Inorder(BT-left); _(1)_(2)_ 5. 顺序查找算法如下, 完成程序中空格部分。int search (NODE a ,int n , int k ) /* 在 a0,a1 an-1,中查找关键字等于k 的记录，查找成功返回记录的下标，失败时返回-1*/ int i=0; while( i n & ai.key _(1)_) _(2)_ e a b c d f 图 3 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 6 页，共 29 页 - - - - - - - - - 7 if (_(3)_) return i; else return -1; 综合练习一答案一、单项选择题1 C 2 A 3 B 4 D 5 A 6 C 7 C 8B 9 B 10 C 11 C 12 A 13 A 14D 15 D 16C 17 A 18 B 19 D 20 B 二、填空题1先出211,13,12,14,15,17 3树型415 5行下标列下标数组元素64次73 8树形9存储位置1018 1110 12. 21 13 20 14. 1 ，3，7，18，6，9，12，13 15 二叉排序树1615 17. 叶18. 中序19.4 206 21.2 ，4，3，5， 6，8，7，9 223 23.a224. P1 三、综合题名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 7 页，共 29 页 - - - - - - - - - 8 1(1) 55 18 85 4 19 65 86 12 37 77 117 (2) 3 次(3) 平均查找长度=(1+2*2+3*4+4*4)/11=3 2(1) (2) 4 , 5 , 7 , 9 , 6 , 8 4 7 11 8 5 2 10 1 3 9 6 图 4 49 65 102 91 14 111 17 13 50 83 39 图 5 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 8 页，共 29 页 - - - - - - - - - 9 3. (1) 18 ，20， 25，59，26，36 (2) 20 ， 18，26，36，59，64 4. (1) (2)(1+2*2+3*4+4*3)/10=29/10 4 次49 5 75 9 658 图 6 18 20 25 4259 36 图 7 72 5 2 8 1 3 6 4 7 9 10 图 8 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 9 页，共 29 页 - - - - - - - - - 10 5 (1) (2) 1 0000 2 0001 3001 6 01 710 8 11 四、程序填空题1.(1) low=high (2)( low+high)/2 (3) mid; (4) amid.keydata （2）p=p-next （3）p!=NULL 3. （1） printf(“%c”,BT-data) （2） Inorder(BT-left) （3） a b d f e c 6 7 3 8 6 1 3 2 27 15 12 图 9 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 10 页，共 29 页 - - - - - - - - - 11 4（1） Inorder(BT-right) （2） printf(“%c ”,BT-data) 5. (1) !=k (2) i+; (3) ai.key= =k 综合练习二一、单项选择题1设头指针为head 的非空的单向循环链表, 指针 p 指向尾结点 , 则满足表达式（）为真。 A p-next = =NULL Bp= =NULL C p-next= =head Dp= =head 2. 数据的存储结构包括数据元素的表示和（） 。 A . 数据处理的方法 C . 相关算法 D. 数据元素的类型 D. 数据元素间的关系的表示3一种逻辑结构（） 。 A 可以有不同的存储结构 B只能有唯一的存储结构C是指某一种数据元素之间的存储关系 D是指某一种数据元素的性质4在一个头指针为head 的单向链表中，p 指向尾结点，要使该链表成为单向循环链表可执行（） 。 A p= head-next; B head-next=p; Chead-next=p-next; D p-next=head; 5链表所具备的特点之一是（） 。 A 可以随机访问任一结点 B占用连续的存储空间 C 插入删除元素的操作不需要移动元素结点 D 可以通过下标对链表进行直接访问6元素111， 113，115，117 按顺序依次进栈，则该栈的不可能输出序列是（） （进栈出栈可以交替进行） 。 A 117，115， 113，111 B111，113，115，117 C117，115， 111，113 D113，111，117，115 7线性结构中数据元素的位置之间存在（）的关系。 A一对一 B一对多C多对多 D每一个元素都有一个直接前驱和一个直接后继8以下说法正确的是（） 。 A 栈的特点是先进后出B栈的特点是先进先出 C 队列的特点是先进后出 D. 栈和队列的特点都是先进后出9在一个单向链表中p 所指结点之后插入一个s 所指的结点时，可执行（） 。 A p-next= s; s-next= p-next Bp-next=s-next; Cp=s-next Ds-next=p-next; p-next=s; 10设有一个20 阶的对称矩阵A(第一个元素为a1,1) ，采用压缩存储的方式，将其下三名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 11 页，共 29 页 - - - - - - - - - 12 角部分以行序为主序存储到一维数组B中（数组下标从1 开始），则矩阵中元素a6,2 在一维数组B中的下标是（） 。A24 B 17 C16 D23 11元素 11， 13，15，17 按顺序依次进栈，则该栈的不可能输出序列是（）（进栈出栈可以交替进行）。 A 17，15，13，11 B11，13，15，17 C 17，15，11，13 D13，11，17，15 12设一棵有 2n+1 个结点的二叉树，除叶结点外每个结点度数都为2，则该树共有 （）个叶结点。An B n+1 Cn+2 Dn-1 13设有一个20 阶的对称矩阵A(第一个元素为a1,1) ，采用压缩存储的方式，将其下三角部分以行序为主序存储到一维数组B中（数组下标从1 开始），则矩阵中元素a5,2在一维数组 B中的下标是（） 。 A11 B12 C13 D10 14已知如图1所示的一个图，若从顶点a 出发，按广度优先搜索法进行遍历，则可能得到的一种顶点序列为（） 。 Aabecdf Baecbdf Caebcfd Daedfcb 图 1 15设一棵哈夫曼树共有11 个非叶结点，则该树有（）个叶结点。 A22 B10 C11 D12 16线性表以（）方式存储，能进行折半查找。 A关键字有序的顺序 B顺序 C链接 D二叉树17一棵具有38 个结点的完全二叉树，最后一层有（）个结点。 A7 B5 C6 D8 18一棵具有38 个结点的完全二叉树，最后一层有（）个结点。 A 7 B5 C6 D8 19已知如图2 所示的一个图，若从顶点a 出发，按深度优先搜索法进行遍历，则可能得到的一种顶点序列为（） 。 Aabecdf Bacfebd Caebcfd Daedfcb b d f e c a 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 12 页，共 29 页 - - - - - - - - - 13 20 .对一个栈顶指针为top 的链栈进行出栈操作，用变量e 保存栈顶元素的值，则执行（） 。A. e= top-next; top-data=e; B. top=top-next; e=top-data; C. e=top-data; top=top-next; D. top=top-next; e=data; 二、填空题1. 字符串 a1=BEIJING, a2 = BEF , a3= BEFANG , a4=“BEI最小的是_ _。2. 数组 a 经初始化 char a =“English ”; a7中存放的是 _。3把数据存储到计算机中，并具体体现数据元素间的逻辑结构称为_ _。4设有串p1=”ABADF ”,P2=”ABAFD ” ，P3=”ABADFA ” P4= ”ABAF ”, 四个串中最大的是_。5设有一个长度为22 的顺序表，要删除第8个元素需移动元素的个数为_ _。6在一棵二叉树中，若编号为i 的结点存在右孩子，则右孩子的顺序编号为_。7在一棵二叉树中，若编号为i 的结点存在左孩子，则左孩子的顺序编号为_ _。8设有一个长度为20 的顺序表，要插入一个元素，并作为第8 个元素，需移动元素的个数为_。9设一棵有n 个叶结点的二叉树，除叶结点外每个结点度数都为2，则该树共有_ _个结点。10结构中的数据元素存在多对多的关系称为_结构。11在对一组序列(45,29,87,12,6,63,55,37,78)进行直接插入排序时，当把第8 个记录 37 插入到有序表时，为寻找插入位置需比较_次。 （由小到大排序）12设有一棵深度为4 的完全二叉树，第四层上有5 个结点，该树共有_个结点。（根所在结点为第1 层）13 n 个元素进行冒泡法排序，通常需要进行_ _趟冒泡。14一棵二叉树中有n 个非叶结点，每一个非叶结点的度数都为2，则该树共有_ 个叶结点。b d f e c a 图 2 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 13 页，共 29 页 - - - - - - - - - 14 15一棵有 21 个结点的哈夫曼树,该树中有_ 个叶结点。16在对一组记录(55,39,97,22,16,73,65,47,88) 进行直接插入排序时，当把第7 个记录 65 插入到有序表时，为寻找插入位置需比较_次。 (由小到大排序17_遍历二叉排序树可得到一个有序序列。18. n 个元素进行冒泡法排序，第 j 趟冒泡要进行 _ _次元素间的比较。19. 广义表 ( a , (a ,b) , d , e ,( (i ,j ) ,k ) ) 的长度是 _。20一棵有 n 个叶结点的哈夫曼树，则该树共有_个结点。21. 广义表的 ( a , (a ,b) , d , e ,( (i ,j ) ,k ) ) 深度是 _ 。22中序遍历 _可得到一个有序序列。23. 序列 14,12,15,13,18,16,采用冒泡排序算法(升序),经一趟冒泡后,序列的结果是_ _。24广义表 ( (a ,b) , d , e ,( (i ,j ) ,k ) ) 的长度是 _ 。三、综合题1设查找表为 (7,15,21,22,40,58,68,80,88,89,120) , 元素的下标依次为1,2,3,， 11. （ 1）画出对上述查找表进行折半查找所对应的判定树（树中结点用下标表示）（ 2）说明成功查找到元素40 需要经过多少次比较？（ 3）求在等概率条件下，成功查找的平均比较次数？2. （ 1）设有数据集合40 ，29，7，73，101，4，55，2，81，92， 39，依次取集合中各数据构造一棵二叉排序树。 (2)一组记录的关键字序列为（5，8，6，3， 4，7） ，利用堆排序（堆顶元素是最小元素）的方法建立初始堆。( 要求用完全二叉树表示) 3. (1) 一组记录的关键字序列为（47，80，57， 39，41，46） ，给出利用堆排序（堆顶元素是最小元素）的方法建立的初始堆（要求以完全二叉树描述） 。(2) 对关键字序列 ( 47,80,57,39,41,85)采用快速排序，给出以第一个关键字为分割元素，经过一次划分后的结果。(3) 如图 3 所示的二叉树，给出其前序遍历序列。g f a b d e c 图 3 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 14 页，共 29 页 - - - - - - - - - 15 4 (1) 以 2，3，4，7，8，9 作为叶结点的权，构造一棵哈夫曼树(2) 给出上述哈夫曼树叶结点的哈夫曼编码。(3) 一组记录的关键字序列为（37，70，47， 29，31，85） ，利用快速排序，以第一个关键字为分割元素，给出经过一次划分后结果。（由小到大排序）四、程序填空题1以下程序是中序遍历二叉树的递归算法的程序，完成程序中空格部分（树结构中左、右指针域分别为left 和 right，数据域 data为字符型， BT 指向根结点）。void Inorder (struct BTreeNode *BT) if(BT!=NULL) Inorder(BT-left); （1）; （2）; 利用上述程序对右图进行中序遍历，结果是（3）; 2.设线性表为（ 6，10， 16，4） ，以下程序用说明结构变量的方法建立单向链表，并输出链表中各结点中的数据。#define NULL 0 void main( ) NODE a,b,c,d,*head,*p; a.data=6; b.data=10; c.data=16; d.data=4; /*d 是尾结点 */ head= （1）; a.next=&b; b.next=&c; c.next=&d; （2）; /*以上结束建表过程 */ p=head; /*p为工作指针，准备输出链表*/ do printf(“%dn”, （3）); （4）; while( （5）); 3以下冒泡法程序对存放在a1 ，a2 ， an 中的序列进行排序，完成程序中的空格部分，其中n 是元素个数，要求按升序排列。void bsort (NODE a , int n) NODE temp; int i,j,flag; for(j=1; （1） ;j+); e f a b c d 图 4 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 15 页，共 29 页 - - - - - - - - - 16 flag=0; for(i=1; （ 2） ;i+) if(ai.keyai+1.key) flag=1; temp=ai; （3） ; （4） ; if(flag= =0)break; 程序中 flag的功能是（ 5）4.以下程序是中序遍历二叉树的递归算法的程序，完成程序中空格部分（树结构中左、右指针域分别为left 和 right，数据域 data 为字符型， BT 指向根结点） 。void Inorder (struct BTreeNode *BT) if(BT!=NULL) （1）; （2）; Inorder(BT-right); 利用上述程序对右图进行遍历，结果是（3）; 综合练习二答案一、单项选择题1C 2 D 3 A 4 D 5 C 6C 7 A 8A 9 D 10B 11 C 12 B 13 B 14 B 15. D 16A 17. A 18A 19.D 20.C 二、填空题1. a2 2. 字符串的结束符3. 物理结构 (存储结构 ) 4. p2 5. 1462i+1 7 2i 8. 13 9. 2n-1 10 图状e f a b c d 图 5 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 16 页，共 29 页 - - - - - - - - - 17 11. 5 1212 13 n-1 14n+1 15 11 163 17 中序18. n-j 19. 5 20.2n-1 21. 3 22二叉排序树23. 12,14,13,15,16,18 244 三、综合题1(1) (2)4 次(3)ASL=(1+2*2+3*4+4*4)/11=3 2(1) 4 7 11 8 5 2 10 1 3 9 6 图 6 39 55 92 81 4 101 7 2 40 73 29 图 7 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 17 页，共 29 页 - - - - - - - - - 18 (2) 3,4,6,8,5,7 3(1) 39 ，41，46，80，47， 57 (2) 41 ，39，47，57，80，85 (3) abdefcg 4(1) 34 68 57 图 8 39 41 46 47 80 57 图 9 9 7 5 8 9 2 43 33 15 18 图 10 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 18 页，共 29 页 - - - - - - - - - 19 (2）2：0000 40001 5001 810 911 1001 (3) 31,29,37,47,70,85 四、程序填空题1. （1） printf(“%c”,BT-data) （2） Inorder(BT-right) （3） dbeafc 2 （1）&a （2）d-next=NULL （3）p-data （4）p=p-next （5）p!=NULL 3（1） j=n-1 （2） ileft) （2） printf(“%c ” ,BT-data) （3）bedafc 综合练习三一、单项选择题1. 数据的存储结构包括数据元素的表示和（） 。 A . 数据处理的方法 B. 数据元素的类型 C . 相关算法 D. 数据元素间的关系的表示2设有头指针为head 的不带头结点的非空的单向循环链表, 指针 p 指向其尾结点 , 要删除第一个结点, 则可利用下述语句 head=head-next;和（） 。名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 19 页，共 29 页 - - - - - - - - - 20 Ap =head; Bp=NULL; C p-next =head; Dhead=p; 3树状结构中数据元素的位置之间存在（）的关系。 A每一个元素都有一个直接前驱和一个直接后继 B一对一C多对多 D一对多4. 以下说法正确的是( )。 A. 线性表的链式存储结构必须占用连续的存储空间 B. 一种逻辑结构可以有不同的存储结构 C一种逻辑结构只能有唯一的存储结构 D 线性表的顺序存储结构不必占用连续的存储空间5设有一个长度为26 的顺序表，要插入一个元素, 并使它成为新表的第6 个元素 , 需移动元素的个数为（） 。 A21 B22 C20 D19 6把数据存储到计算机中，并具体体现( )称为物理结构。 A数据的处理方法 B数据的性质 C数据的运算 D. 数据元素间的逻辑关系7头指针为head 的带头结点的单向循环链表，p 所指向尾结点，要使该链表成为不带头结点的单向循环链表, 可执行 head=head-nex; 和（） 。 A p= head-next B head-next=p Chead-next=p-next D p-next=head; 8顺序表所具备的特点之一是（） 。 A可以随机访问任一结点 B不需要占用连续的存储空间 C插入元素的操作不需要移动元素 D删除元素的操作不需要移动元素 9 元素 111， 113，115，117 按顺序依次进栈，则该栈的不可能输出序列是（） （进栈出栈可以交替进行） 。 A 117，115， 113，111 B111，113，115， 117 C117，115，111，113 D113，111，117， 115 10图状结构中数据元素的位置之间存在（）的关系。 A一对一 B一对多C多对多 D每一个元素都有一个直接前驱和一个直接后继11以下说法正确的是（） 。 A栈的特点是先进先出 B栈的特点是先进后出 C 队列的特点是先进后出12元素 20， 14，16，18 按顺序依次进栈，则该栈的不可能输出序列是（）（进栈出栈可以交替进行）。 A18，16，14，20 B20，14，16，18 C 18，16，20，14 D14，20，18，16 D. 栈和队列的特点都是后进后出 13. 设有一个20 阶的对称矩阵A(第一个元素为a1,1) ，采用压缩存储的方式，将其下三角部分以行序为主序存储到一维数组B中（数组下标从1 开始） ， 则矩阵元素a6,2 在一维数组B中的下标是（） 。 A21 B17 C28 D 23 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 20 页，共 29 页 - - - - - - - - - 21 14设有一个12 阶的对称矩阵A(左上角第一个元素为a1,1) ，采用压缩存储的方式，将其下三角部分以行序为主序存储到一维数组B中（数组下标从1 开始），则矩阵中元素a5,4在一维数组B中的下标是（） 。 A14 B12 C13 D11 15设有串p1=” ABADF ” ,P2=”ABAFD ” ，P3= ”ABADFA ”,P4=” ABAF ”, 以下四个串中最大的是 ( )。 A p3 B p2 C p1 D p4 16设有一个长度为22 的顺序表，要删除第8 个元素需移动元素的个数为（） 。 A25 B14 C15 D23 17. 数组 a 经初始化 char a =“English ”; a7中存放的是（） 。 A. 字符串的结束符 B. 字符 h C. h D. 变量 h 18 在一棵二叉树中，若编号为5 的结点存在右孩子，则右孩子的顺序编号为（） 。 A12 B9 C11 D10 19. 设主串为“ ABcCDABcdEFaBc” ，以下模式串能与主串成功匹配的是（） 。 A. Bcd B. BCd C. ABC D. Abc 20一棵具有5 层的完全二叉树，最后一层有4 个结点，则该树总共有（）个结点。 A14 B15 C19 D18 21在一棵二叉树中，若编号为i 的结点存在左孩子，则左孩子的顺序编号为（） 。 A 2i+1 B2i-1 C 2i D2i+2 22 .如图 1 所示， 若从顶点 a 出发， 按图的广度优先搜索法进行遍历，则可能得到的一种顶点序列为（） 。 A abcdfge Babcedfg Cacbfedg Dabcfgde 23如图 2 所示，若从顶点a 出发，按图的广度优先搜索法进行遍历，则可能得到的一种顶点序列为（） 。 Aabecdf Baecbdf Caebcfd Daedfcb g f a b d e c 图 1 名师资料总结 - - -精品资料欢迎下载 - - - - -