下载文档原格式
一、填空题（共20分，每空1分）。
1.数据结构是研究数据元素之间抽象化的相互关系和这种关系在计算机中的存储结构表示，通常有下列四种存储结构：（1）、（2）、（3）和（4）。
2.评价算法的标准很多，通常是以执行算法所需要的（5）和所占用的（6）来判别一个算法的优劣。
3.队列操作的原则是（7），栈的插入和删除操作在（8）进行。
4.对循环队列Q，它的最大存储空间是MAXSIZE，队头指针是front，队尾指针是rear，采用少用一个存储单元的方法解决假溢出时，队满的判断条件是（9），队空的判断条件是（10）。
5.在以head 为表头指针的带有头结点的单链表和循环单链表中，判断链表为空的条件分别为（11）和（12）。
6.假设二维数组A[6][8]，每个元素用相邻的4个字节存储，存储器按字节编址，已知A[0][0]的存储位置为100，按行优先顺序存储的元素A[2][5]的第一个字节的地址为（13）。
7.空格串的长度为串中所包含（14）字符的个数，空串的长度为（15）。
8.有向图G 用邻接矩阵A[n][n] 存储表示，其第i 行的所有元素之和等于顶点i 的（16）。
9.在关键字序列(12 ，23 ，34 ，45 ，56 ，67 ，78 ，89 ，91) 中折半查找关键字为89和25的结点时，所需进行的比较次数分别为（17）和（18）。
10.请说出两种处理哈希冲突的方法（19）、_（20）_。
二、选择题（共20分，每题2分）。
1.对线性表，在下列哪种情况下应采用链式存储结构？（）A.经常需要随机存取元素B.经常需要进行插入和删除操作C.表中元素的个数不变D.表中元素需要占据一片连续的存储空间2.从一个具有n个结点的单链表中查找其值等于x结点时，在查找成功情况下，则平均比较（）个结点。
A.nB.n/2C.(n-1)/2D.(n+1)/23.若对某线性表最常进行的操作是在最后一个元素之后插入和删除第一个元素，则采用（）存储方式最节省运算时间。
数据结构试题一、单选题1、在数据结构的讨论中把数据结构从逻辑上分为（C ）A 内部结构与外部结构B 静态结构与动态结构C 线性结构与非线性结构D 紧凑结构与非紧凑结构。
2、采用线性链表表示一个向量时，要求占用的存储空间地址（D ）A 必须是连续的B 部分地址必须是连续的C 一定是不连续的D 可连续可不连续3、采用顺序搜索方法查找长度为n的顺序表时，搜索成功的平均搜索长度为（ D ）。
A nB n/2C (n-1)/2D (n+1)/24、在一个单链表中，若q结点是p结点的前驱结点，若在q与p之间插入结点s，则执行（ D ）。
A s→link = p→link; p→link = s;B p→link = s; s→link = q;C p→link = s→link; s→link = p;D q→link = s; s→link = p;5、如果想在4092个数据中只需要选择其中最小的5个，采用（ C ）方法最好。
A 起泡排序B 堆排序C 锦标赛排序D 快速排序6、设有两个串t和p，求p在t中首次出现的位置的运算叫做（ B ）。
A 求子串B 模式匹配C 串替换D 串连接7、在数组A中，每一个数组元素A[i][j]占用3个存储字，行下标i从1到8，列下标j从1到10。
所有数组元素相继存放于一个连续的存储空间中，则存放该数组至少需要的存储字数是（ C ）。
A 80B 100C 240D 2708、将一个递归算法改为对应的非递归算法时，通常需要使用（ A ）。
A 栈B 队列C 循环队列D 优先队列9、一个队列的进队列顺序是1, 2, 3, 4，则出队列顺序为（ C ）。
10、在循环队列中用数组A[0..m-1] 存放队列元素，其队头和队尾指针分别为front和rear，则当前队列中的元素个数是（ D ）。
A ( front - rear + 1) % mB ( rear - front + 1) % mC ( front - rear + m) % mD ( rear - front + m) % m11、一个数组元素a[i]与（ A ）的表示等价。
数据结构练习试卷1(题后含答案及解析)题型有：1. 选择题选择题（每小题1分，共75分）下列各题A、B、C、D四个选项中，只有一个选项是正确的，请将此选项涂写在答题卡相应位置上，答在试卷上不得分。
1．数据结构主要研究数据的______。
A．逻辑结构B．存储结构C．逻辑结构和存储结构D．逻辑结构和存储结构及其运算的实现正确答案：D解析：数据结构是相互之间存在一种或多种特定关系的数据元素的集合。
数据结构一般包括三方面的内容：①数据之间的逻辑关系。
从逻辑关系上描述数据，与数据的存储无关。
②数据的存储结构。
存储结构分为顺序结构和链式结构，是逻辑结构在计算机存储器中的表示，它包括数据元素的表示和关系的表示。
③数据的运算。
也就是在数据上所施加的一系列操作。
只考虑操作的功能是怎样的，暂不考虑如何实现。
综上所述，本题的正确答案为选项D。
知识模块：数据结构2．在数据结构中，结点(数据元素)及结点间的相互关系组成数据的逻辑结构。
按逻辑结构的不同，数据结构通常可分为______两类。
A．线性结构和非线性结构B．紧凑结构和稀疏结构C．动态结构和静态结构D．内部结构和外部结构正确答案：A解析：在数据结构中，结点(数据元素)及结点间的相互关系组成数据的逻辑结构。
按逻辑结构的不同，数据结构通常可分为线性结构和非线性结构两类。
本题正确答案为选项A。
知识模块：数据结构3．下面叙述不正确的是______。
A．算法的执行效率与数据的存储结构有关B．算法的空间复杂度是指执行这个算法所需要的内存空间C．算法的有穷性是指算法必须能在执行有限个步骤之后终止D．算法的时间复杂度是指执行这个算法所需要的时间正确答案：D解析：算法的时间复杂度是指执行算法所需要的计算工作量，故D选项不正确。
知识模块：数据结构4．数据的存储结构是指______。
A．数据所占的存储空间量B．数据的逻辑结构在计算机中的表示C．数据在计算机中的顺序存储方式D．存储在外存中的数据正确答案：B解析：数据的存储结构是数据元素在计算机存储器内的表示。
《数据结构(Java语言版)》试卷1
一、选择题（每题5分，共25分）
1.
在Java中，哪种数据结构不支持“修改”操作？
A. ArrayList
B. LinkedList
C. HashSet
D. HashMap
2.
下列哪个算法的时间复杂度为O(nlogn)？
A. 冒泡排序
B. 快速排序
C. 插入排序
D. 选择排序
3.
以下哪个是栈（Stack）数据结构的特性？
A. 先入后出（FILO）
B. 先入先出（FIFO）
C. 按值访问
D. 按索引访问
4.
下列哪个是队列（Queue）数据结构的特性？
A. 先入后出（FILO）
B. 先入先出（FIFO）
C. 按值访问
D. 按索引访问
5.
在Java中，哪种数据结构可以存储重复的元素？
A. HashSet
B. TreeSet
C. ArrayList
D. LinkedList
6.
二、填空题（每空3分，共18分）
1.在Java中，ArrayList是基于____________实现的。
2.二叉树的深度为h，则最多有____________个节点。
3.图的遍历方法有____________和____________。
4.堆排序的时间复杂度为____________。
5.链表的特点是每个节点包含两部分：和。
三、简答题（每题10分，共20分）
1.简述数组和链表的区别。
2.简述二叉树的中序遍历过程。
数据结构试卷一、填空殖（每空1分共20分)1.数据的物理结构主要包括___顺序存储结构__________和_链式_____________两种情况。
2.设一棵完全二叉树中有500个结点，则该二叉树的深度为_______9___;若用二叉链表作为该完全二叉树的存储结构，则共有______501_____个空指针域.3.设输入序列为1、2、3，则经过栈的作用后可以得到_____6______种不同的输出序列。
4.设有向图G用邻接矩阵A[n][n]作为存储结构，则该邻接矩阵中第i行上所有元素之和等于顶点i的___出度_____,第i列上所有元素之和等于顶点i的____入度____。
5.设哈夫曼树中共有n个结点,则该哈夫曼树中有___0_____个度数为1的结点。
6.设有向图G中有n个顶点e条有向边，所有的顶点入度数之和为d,则e和d的关系为____e=d_____。
7.____中序______遍历二叉排序树中的结点可以得到一个递增的关键字序列(填先序、中序或后序）.8.设查找表中有100个元素,如果用二分法查找方法查找数据元素X,则最多需要比较_____7___次就可以断定数据元素X是否在查找表中。
9.不论是顺序存储结构的栈还是链式存储结构的栈，其入栈和出栈操作的时间复杂度均为______1______。
10.设有n个结点的完全二叉树，如果按照从自上到下、从左到右从1开始顺序编号,则第i个结点的双亲结点编号为___i/2_________,右孩子结点的编号为____2i+1_______。
11.设一组初始记录关键字为（72，73,71，23,94,16,5），则以记录关键字72为基准的一趟快速排序结果为_____5 16 71 23 72 94 73______。
12.设有向图G中有向边的集合E=｛〈1，2〉，<2,3>，〈1，4〉，〈4,2>，〈4，3〉｝，则该图的一种拓扑序列为___1 4 2 3___。
《数据结构》单元测试1一、选择题（每题2分，共40分）1．数据的最小单位是（ A）。
(A) 数据项(B) 数据类型(C) 数据元素(D) 数据变量2. 栈和队列的共同特点是( A )。
(A)只允许在端点处插入和删除元素(B)都是先进后出(C)都是先进先出(D)没有共同点3. 用链接方式存储的队列，在进行插入运算时( D )。
(A)仅修改头指针(B)头、尾指针都要修改(C)仅修改尾指针 (D)头、尾指针可能都要修改4. 以下数据结构中哪一个是非线性结构？( D )(A)队列(B)栈(C)线性表(D)二叉树5．函数substr(“DATASTRUCTURE”，5，9)的返回值为（ A ）。
(A) “STRUCTURE”(B) “DATA”(C) “ASTRUCTUR”(D) “DATASTRUCTURE”6．设一个有序的单链表中有n个结点，现要求插入一个新结点后使得单链表仍然保持有序，则该操作的时间复杂度为（ D）。
(A) O(log2n) (B) O(1) (C) O(n2) (D) O(n)7．设一棵m叉树中度数为0的结点数为N0，度数为1的结点数为Nl，……，度数为m的结点数为Nm，则N0=（ B）。
(A) Nl+N2+……+Nm(B) 1+N2+2N3+3N4+……+(m-1)Nm(C) N2+2N3+3N4+……+(m-1)Nm (D) 2Nl+3N2+……+(m+1)Nm 8．设有序表中有1000个元素，则用二分查找查找元素X最多需要比较（ B）次。
(A) 25 (B) 10 (C) 7 (D) 19. 二叉树的第k层的结点数最多为( D )。
(A)2k-1 (B) 2K+1 (C) 2K-1 (D)2k-110. 树最适合用来表示( C )。
(A)有序数据元素(B)无序数据元素(C)元素之间具有分支层次关系的数据 (D)元素之间无联系的数据个权构成一棵Huffman树，其节点总数为( A )。
数据结构试卷一一、选择题20分1．组成数据的基本单位是 ;A 数据项B 数据类型C 数据元素D 数据变量2．设数据结构A=D,R,其中D={1,2,3,4},R={r},r={<1,2>,<2,3>,<3,4>,<4,1>},则数据结构A 是 ;A 线性结构B 树型结构C 图型结构D 集合3．数组的逻辑结构不同于下列的逻辑结构;A 线性表B 栈C 队列D 树4．二叉树中第ii≥1层上的结点数最多有个;A 2iB 2iC 2i-1D 2i-15．设指针变量p指向单链表结点A,则删除结点A的后继结点B需要的操作为 ;A p->next=p->next->nextB p=p->nextC p=p->next->nextD p->next=p6．设栈S和队列Q的初始状态为空,元素E1、E2、E3、E4、E5和E6依次通过栈S,一个元素出栈后即进入队列Q,若6个元素出列的顺序为E2、E4、E3、E6、E5和E1,则栈S的容量至少应该是 ;A 6B 4C 3D 27．将10阶对称矩阵压缩存储到一维数组A中,则数组A的长度最少为 ;A 100B 40C 55D 808．设结点A有3个兄弟结点且结点B为结点A的双亲结点,则结点B的度数数为 ;A 3B 4C 5D 19．根据二叉树的定义可知二叉树共有种不同的形态;A 4B 5C 6D 710.设有以下四种排序方法,则的空间复杂度最大;A 冒泡排序B 快速排序C 堆排序D 希尔排序二、填空题30分1.设顺序循环队列Q0：m-1的队头指针和队尾指针分别为F和R,其中队头指针F指向当前队头元素的前一个位置,队尾指针R指向当前队尾元素所在的位置,则出队列的语句为F =____________;;2.设线性表中有n个数据元素,则在顺序存储结构上实现顺序查找的平均时间复杂度为___________,在链式存储结构上实现顺序查找的平均时间复杂度为___________;3.设一棵二叉树中有n个结点,则当用二叉链表作为其存储结构时,该二叉链表中共有________个指针域,__________个空指针域;4.设指针变量p指向单链表中结点A,指针变量s指向被插入的结点B,则在结点A的后面插入结点B的操作序列为______________________________________;5.设无向图G中有n个顶点和e条边,则其对应的邻接表中有_________个表头结点和_________个表结点;6.设无向图G中有n个顶点e条边,所有顶点的度数之和为m,则e和m有______关系;7.设一棵二叉树的前序遍历序列和中序遍历序列均为ABC,则该二叉树的后序遍历序列为__________;8.设一棵完全二叉树中有21个结点,如果按照从上到下、从左到右的顺序从1开始顺序编号,则编号为8的双亲结点的编号是___________,编号为8的左孩子结点的编号是_____________;9.下列程序段的功能实现子串t在主串s中位置的算法,要求在下划线处填上正确语句;int indexchar s , char t{i=j=0;whilei<strlens && j<strlent ifsi==tj{i=i+l; j=j+l;}else{i=_______; j=______;}if j==strlentreturni-strlent;else return -1;}10.设一个连通图G中有n个顶点e条边,则其最小生成树上有________条边;三、应用题30分1．设完全二叉树的顺序存储结构中存储数据ABCDE,要求给出该二叉树的链式存储结构并给出该二叉树的前序、中序和后序遍历序列;2．设给定一个权值集合W=3,5,7,9,11,要求根据给定的权值集合构造一棵哈夫曼树并计算哈夫曼树的带权路径长度WPL;3．设一组初始记录关键字序列为19,21,16,5,18,23,要求给出以19为基准的一趟快速排序结果以及第2趟直接选择排序后的结果;4．设一组初始记录关键字集合为25,10,8,27,32,68,散列表的长度为8,散列函数Hk=k mod 7,要求分别用线性探测和链地址法作为解决冲突的方法设计哈希表;5．设无向图G所右图所示,要求给出该图的深度优先和广度优先遍历的序列并给出该图的最小生成树;四、算法设计题20分1.设计判断单链表中结点是否关于中心对称算法;2.设计在链式存储结构上建立一棵二叉树的算法;3.设计判断一棵二叉树是否是二叉排序树的算法;数据结构试卷一参考答案一、选择题二、填空题1. F+1 % m2. On,On3. 2n,n+14. s->next=p->next; s->next=s5. n, 2e6. m=2e7. CBA8. 4,169. i-j+1,010. n-1三、应用题1. 链式存储结构略,前序ABDEC,中序DBEAC,后序DEBCA;2. 哈夫曼树略,WPL=783. 18,5,16,19,21,23,5,16,21,19,18,234. 线性探测：6827322510876543210ΛΛ 链地址法：276832251086543210>->->->->->-h h h h h h h 5. 深度：125364,广度：123456,最小生成树T 的边集为E={1,4,1,3,3,5,5,6,5,6}四、算法设计题1. 设计判断单链表中结点是否关于中心对称算法;typedef struct {int s100; int top;} sqstack;int lklistsymmetrylklist head{sqstack stack; = -1; lklist p;forp=head;p=0;p=p->next {++; =p->data;}forp=head;p=0;p=p->next if p->data== =; else return0;return1;}2. 设计在链式存储结构上建立一棵二叉树的算法;typedef char datatype;typedef struct node {datatype data; struct node lchild,rchild;} bitree;void createbitreebitree &bt{char ch; scanf"%c",&ch;ifch=='' {bt=0; return;}bt=bitreemallocsizeofbitree; bt->data=ch;createbitreebt->lchild; createbitreebt->rchild;}3.设计判断一棵二叉树是否是二叉排序树的算法;int minnum=-32768,flag=1;typedef struct node{int key; struct node lchild,rchild;}bitree;void inorderbitree bt{if bt=0{inorderbt->lchild; ifminnum>bt->keyflag=0; minnum=bt->key; inorderbt->rchild;} }。
广州大学2017-2018学年第二学期试卷课程《数据结构》考试形式（闭卷，考试）物理与电子工程学院电子系电子061、062、063 专业学号姓名一、判断题（对打√，错打×。
每题1分，共15分）1、顺序存储结构只能用于存储线性结构。
( )2、在线性表的顺序存储结构中，插入和删除元素时，移动元素的个数与该元素的位置有关。
( )3、在线性表的链式存储结构中，逻辑上相邻的元素在物理位置上不一定相邻( )。
4、二叉树的前序遍历序列中，任意一个结点均处在其子树结点的前面( )。
5、二叉树的前序和后序遍历序列能惟一确定这棵二叉树( )。
6、在无向图中，边的条数是结点度数之和( )。
7、图的邻接矩阵必定是对称矩阵( )。
8、二叉树是度最大为2的有序树( )。
9、结点数固定的二叉树中，完全二叉树具有最小路径长度( )。
10、中序线索树中，右线索若不为空，则一定指向其双亲结点( )。
11、有向图用邻接矩阵表示，容易实现求结点度数的操作( )。
12、按深度优先搜索遍历图时，与始点相邻的结点先于不与始点相邻的结点访问( )13、若有向图的邻接矩阵中对角线以下元素均为零，则该图的拓扑排序序列必定存在( )。
14、若有向图G中包含一个环，则G的结点间不存在拓扑排序( )。
15、图的拓扑排序序列是唯一的( )。
二、选择题（每题2分，共20分）1.数据结构被形式定义为（D，S），其中D是（）的有限集合，S是D上的（）有限的集合。
A．算法 B．数据元素C．数据操作D．逻辑结构E．操作F．映像G．存储H．关系2.设n为正整数。
下列程序段中前置以记号@的语句的频度为（）。
i=1;k=0;while(i<n-1){@ k+=10*i;i++;}A．n B．n-1 C．n-2 D．n-33.线性表若采用链式存储结构时，要求内存可用存储单元的地址（）。
A．必须是连续的B．部分地址必须是连续的C．一定是不连续的D．连续不连续都可以4.在解决计算机主机与打印机之间速度不匹配问题时，通常设置一个打印数据缓冲区。
第2页 共 2页8、一棵二叉树高度为h ，所有结点的度或为0或为2，则这棵二叉树最少有( )个结点。
A ．2hB ．2h-1C ．2h+1D ．h+19、对二叉树的结点从1开始进行连续编号，要求每个结点的编号大于其左、右孩子的编号，同一结点的左右孩子中，其左孩子的编号小于其右孩子的编号，可采用( )次序的遍历实现编号。
A ．先序B ．中序C ．后序D ．按层次遍历10、一棵二叉树的先序遍历序列为ABCDEFG ，它的中序遍历序列可能是（ ）。
A ．CABDEFGB ．ABCDEFGC ．DACEFBGD ．ADBCFEG11、一棵有n 个结点的二叉树，按层次从上到下，同一层从左到右顺序存储在一维数组A[1..n]中，则二叉树中第i 个结点（i 从1开始用上述方法编号）的右孩子在数组A 中的位置是（ ）A ．A[2i](2i<=n)B ．A[2i+1](2i+1<=n)C ．A[i-2]D ．条件不充分，无法确定12、一个n 个顶点的连通无向图，其边的个数至少为（ ）。
A ．n-1B ．nC ．n+1D ．nlogn13、下列关于AOE 网的叙述中，不正确的是（ ）。
A ．关键活动不按期完成就会影响整个工程的完成时间B ．任何一个关键活动提前完成，那么整个工程将会提前完成C ．所有的关键活动提前完成，那么整个工程将会提前完成D ．某些关键活动提前完成，那么整个工程将会提前完成 14、下面关于折半查找的叙述正确的是( )。
A ．表必须有序，表可以顺序方式存储，也可以链表方式存储C ．表必须有序，而且只能从小到大排列B ．表必须有序且表中数据必须是整型，实型或字符型D ．表必须有序，且表只能以顺序方式存储A．直接插入排序B．起泡排序C．快速排序D．直接选择排序二、判断题（每空1分，共10分）1、数据的逻辑结构说明数据元素之间的顺序关系，它依赖于计算机的储存结构。
( )2、对任何数据结构，链式存储结构一定优于顺序存储结构。
C、直接选择排序D、堆排序7、下面关于图的存储的叙述中，哪一个是正确的。
（ A ）A、用相邻矩阵法存储图,占用的存储空间数只与图中结点个数有关,与边数无关B、用相邻矩阵法存储图,占用的存储空间数只与图中边数有关,与结点个数无关C、用邻接表法存储图，占用的存储空间数只与图中结点个数有关，与边数无关D、用邻接表法存储图，占用的存储空间数只与图中边数有关，与结点个数无关8、首先访问结点的左子树，然后访问该结点，最后访问结点的右子树，这种遍历称为( C )A、前序遍历B、后序遍历C、中序遍历D、层次遍历按深度优先遍历的结点序列为( A ) 9、. 给定下列有向图和初始结点V1,A、V1，V2，V4，V5，V3B、V1，V3，V4，V5，V2C、V1，V2，V5，V3，V4D、V1，V2，V3，V4，V510、在一个长度为n的顺序表中向第i个元素（0≤i≤n）位置插入一个新元素时，需要从后向前依次后移（ B ）个元素。
A、 n-iB、 n-i+1C、 n-i-1D、 i11、利用3, 6, 8, 12这四个值作为叶结点的权值生成一棵霍夫曼树，该树的带权路径长度为（ A ）。
A、 55B、 29C、 58D、 3812、一棵树的广义表表示为a (b, c (e, f (g) ), d)，当用左子女-右兄弟链表表示时，右指针域非空的结点个数为（ C ）。
A、 1B、 2C、 3D、 413、设有一个n´n的对称矩阵A，将其下三角部分按行存放在一个一维数组B中，A[0][0]存放于B[0]中，那么第i行的对角元素A[i][i]存放于B中（ A ）处。
A、(i+3)*i/2B、(i+1)*i/2C、(2n-i+1)*i/2D、(2n-i-1)*i/214、设有一个二维数组A[10][20]，按列存放于一个连续的存储空间中，A[0][0]的存储地址是200，每个数组元素占1个存储字，则A[6][2]的地址为（ A ）。
A、226B、322C、341D、34215、对长度为10的顺序表进行搜索，若搜索前面5个元素的概率相同，均为1/8，搜索后面5个元素的概率相同，均为3/40，则搜索到表中任一元素的平均搜索长度为（ C ）。
A、 5.5B、 5C、39/8D、19/4二、填空题（每空1分，共15分）1、队列的插入操作在_队尾_进行，删除操作在___队头___进行。
2、设有一个顺序栈S，元素s1，s2，s3，s4，s5，s6依次进栈，如果6个元素的出栈顺序为s2，s3，s4，s6，s5，s1，则顺序栈的容量至少应为___3___。
已知一棵二叉树的中序和前序序列如下，求该二叉树的后序序列。
中序序列：e，b，d，c，a，g，i，h，j，f前序序列：a，b，c，d，e，f，g，h，i，j后序序列： c，e，d，b，i，j，h，f，a3、阅读下列算法, 并把缺失的语句补上ListNode * Merge1 ( ListNode *& p1, ListNode *& p2) {//将两个带表头结点的有序单链表合并成一个有序单链表。
ListNode a; //a结点是结果有序单链表的表头结点ListNode *p = &a; //p指向结果有序单链表的表尾结点p->link = NULL;while ( p1 != NULL && p2 != NULL ) { //两个表非空时if ( p1->data < p2->data ) {(1) ;p1 = p1->link;}else { p->link = p2; p2 = p2->link; }(2) ;}if ( p1 != NULL ) p->link = p1;else p->link = p2;(3) ;return (4) ;}答案：(1) p->link = p1(2) p = p->link(3) p1 = p2 = NULL(4) a.link4、写出下列程序段的输出结果:void main( ) {queue Q; char x = 'e', y = 'c';Q.EnQueue ( 'h' ); Q.EnQueue ( 'r' ); Q.EnQueue ( y );Q.DeQueue(Q,x); Q.EnQueue ( x ); Q.DeQueue ( x );Q.EnQueue ( 'a' );while (!Q.IsEmpty ( ) ) { Q.DeQueue ( y ); cout << y; }cout << y << endl;}输出结果：______ char ________________5、一棵高度为5的完全二叉树中，最多包含有__63____个结点。
假定根结点的高度为0。
6、下面给出了冒泡排序算法，请填写算法中的空框，使算法正确。
(10分)typedef struct{int key；datatypeinfo;//设datatype已经定义}node；void BubbleSort ( node R[])//R中元素个数为n个{ int i,j;Boolean flag；node X；for(i=1;i<=n-1;i++){.(1). flag=FALSE;for(j=n-1;j>=i;j--)if( (2) R[j+1].key..)＜R[j].key{ flag =TURE；X=R[j];.. (3) R[j]=R[j+1].;R[j＋1]= X;}if(. (4) (!flag).)return;}}// 算法结束7、二维数组是一种非线性结构，其中的每一个数组元素最多有__两___个直接前驱（或直接后继）。
三、简答题（每题5分，共25分）1、判断以下序列是否是最小堆？如果不是, 将它调整为最小堆。
(1) { 100, 86, 48, 73, 35, 39, 42, 57, 66, 21 }(2) { 12, 70, 33, 65, 24, 56, 48, 92, 86, 33 }。
答案：(1) { 100, 86, 48, 73, 35, 39, 42, 57, 66, 21 }为最大堆。
调整为最小堆后为{ 21, 35, 39, 57, 86, 48, 42, 73, 66, 100 }(2) { 12, 70, 33, 65, 24, 56, 48, 92, 86, 33 }不是最小堆。
调整为最小堆后为{ 12, 24, 33, 65, 33, 56, 48, 92, 86, 70 }2、在一棵空的二叉查找树中依次插入关键字序列为20、30、8、12、34、5、60、3、1，29，请画出所得到的二叉查找树。
答案如图：3、画出下列网络的最小生成树。
答案如图4、假设用于通信的电文仅由A-H八个字母组成，字母在电文中出现的频率分别为7，19，2，6，32，3，21，10。
试为这八个字母设计哈夫曼编码。
图：5、下述算法的功能是什么?LinkList Demo(LinkList L){ // L 是无头结点单链表ListNode *Q,*P;if(L&&L->next){Q=L;L=L->next;P=L;while (P->next) P=P->next;P->next=Q; Q->next=NULL;}return L;}// Demo答案：该算法的功能是：将开始结点摘下链接到终端结点之后成为新的终端结点，而原来的第二个结点成为新的开始结点，返回新链表的头指针。
三、算法设计题（每题15分，共30分）1、试写一算法写出用二叉链表表示给定二叉树的叶结点总数。
(15分)求叶结点数问题#include <stdio.h>#include <malloc.h>typedef char Datatype;//以下为二叉链表的结构定义typedef struct node{Datatype data;node *lchild;node *rchild;}BinTreeNode;typedef BinTreeNode *BinTree;void CreatBinTree(BinTree *T){ //构造二叉链表。
T是指向根的指针，故修改了*T就修改了实参char ch;if ((ch=getchar())==' ')*T=NULL;else{ //读入非空格*T=(BinTreeNode *)malloc(sizeof(BinTreeNode));//生成结点(*T)->data=ch;CreatBinTree(&(*T)->lchild); //构造左子树CreatBinTree(&(*T)->rchild); //构造右子树}}//*****************以下为题目要求算法**********************//int GetLeaves( BinTree root){//求叶结点总数static int leaf=0;//此l用于记叶结点数，注意用静态变量if(root){ //递归计算叶结点数if(!(root->lchild||root->rchild))leaf++; //如果该结点无左右孩子，则叶子数加1GetLeaves(root->lchild);//算左子数的叶结点数GetLeaves(root->rchild);//算右子树的叶结点数}return leaf; //返回结果}//***********算法结束**************//void main(){ //以下为验证程序BinTree root;CreatBinTree(&root);int leaves=GetLeaves(root);printf("Total leaves=%d",leaves);}2、假设以两个元素依值递增有序排列的线性表A和B分别表示两个集合（即同一表中的元素各不相同），现要求另辟空间构成一个线性表C,其元素为A和B 中元素的交集，且表C中的元素也依值递增有序排列。
试对单链表编写求C的算法。
（15分）解：void LinkList_Intersect(LinkList A,LinkList B,LinkList &C){ p=A->next;q=B->next;pc=(LNode*)malloc(sizeof(LNode));C=pc;while(p&&q){ if(p->data<q->data) p=p->next;else if(p->data>q->data) q=q->next;else{s=(LNode*)malloc(sizeof(LNode));s->data=p->data;pc->next=s;pc=s;p=p->next;q=q->next;} }//while}//LinkList_Intersect第11 页共8页。
