1、安徽工程大学数据结构各章作业及实验第一章 一、简答题1 设有数据逻辑结构为： B=（K，R）；K=K1，K2Kn; R=, , , , , , , , , 画出这个逻辑结构的图示，并确定相对于关系R，哪些结点是开始结点，哪些结点是终端结点2 有下列几种用二元组表示的数据结构，画出它们分别对应的逻辑图形表示，并指出它们分别属于何种结构。1) A=（K，R），其中K=a,b,c,d,e,f,g,h; R=r，r=, , , , , 2) B=(K,R),其中K=a,b,c,d,e,f,g,h; R=r， r=, , , , , 二、求下列程序段的时间复杂度(1) for (I=0;In;I+) (
2、4) fact(int n) for (j=0;jm;j+) if (n=1) AIj=0; return 1;(2) I=s=0; else While (sn) return(n*fact(n-1); I+; s+=I; (5) s=0; for(I=0;I=n;I+)(3) I=1; for(j=0;j=n;j+) While (I=n) for(k=0;knext=null C. Head-next=head D. Head!=null 2 在循环双链表P所指接点之前插入S所指结点的操作是_ A. P-prior=S;S-next=P;p-next= S;S -prior=P-prio
3、r B. P-prior=S;P-prior-next=S;S-next= P;S -prior=P-prior C. S-next=P; S-prior=P-prior; P-prior=S;P-right-next=S D. S-next=P; S-prior=P-prior; P-prior-next=S;P-prior=S 3. 双向链表删除P结点，执行的主要语句是_ 4. 在单链表中，在指针P所指结点后面插入一个结点S的语句是_ 5. 在单链表中删除P指针所指结点的的后一个结点的语句是_ 6. 向长度为n的向量第i个元素C（0 in-1 ）之前插入一个元素时，需后移_个元素；删除长度
4、为n的向量第i个元素C（0 in-1 ）之前插入一个元素时，需前移_个元素 第三章作业一 选择、填空题1 判定一个栈（最多n个元素）为空的条件是_;判定为满的条件是_A. S-top!=0 B. S-top= =0C. S-top!=n D. S-top= =n2 一个栈序列：a,b,c,d,e,则栈不可能输出序列_A. abcde B. decba C. dceab D. Edcba3 判定一个队列Q（最多n个元素）为空的条件_是为满的条件是_A. Q-near-Q-front=n B. Q-near-Q-front+1=n C. Q-front=Q-rear D. Q-front=Q-re
5、ar+14 判定循环队列Q（最多n个元素）为空的条件是_;为满的条件是_A. Q-rear=Q-front B. Q-rear=Q-front+1C. Q-front=(Q-rear+1)%nD. Q-front=(Q-rear-1)%n 二 综合题1 设有4个元素ABCD进栈，写出它们所有可能的出栈次序共几种2 设计一个算法，利用栈的基本运算将指定栈中的内容进行逆转 第四章作业 一 填空、选择题 1. _是 C语言中“abcd321ABCD”的子串。 A. abcd B.321AB C.”abcAB” D. “21AB” 2. 有串S1=ABCDEFG，S2=PQRST，设con(x,y)返
6、回串X与串Y的连接串，subs(s,I,j)返回从序号i字符开始的j个字符组成的子串，len(s)返回串s长度，则con(subs(s1,2,len(s2),subs(s1,len(s2),2)的结果串是_(设置串字符从0开始编号) A. BCDEF B. BCDEFG C. BCPQRST D. CDEFGFG3 、串的两种基本存储方式为_ 和 _4、空串是_个字符的串，空白串是_个字符的串二、编程题1 以顺序结构存储串时，写出两串s1,s2首尾相连成一个串，其中s1在前s2在后第五章作业一、选择与判断：1 数组元素间的关系是_(1)_,一维数组和线性表的区别是_(2)_(1) A 线性 B
7、树形 C 既线性又树形 D 非线性又非树形（2）A 前者长度固定，后者长度可变B后前者长度固定，前者长度可变C 两者长度固定D两者长度可变2 二维数组M的元素是4个字符（每个字符占一个存储单元）组成的串，行下标i范围从0到4，下标j范围从0到5，M按行存储时元素M35起始地址与M按列存储时元素_起始地址相同A . M24 B .M34 C .M35 D. M44 3、 设一个有10阶对称矩阵A，采用压缩存储方式，以行序为主存储，a1,1为第一个元素，其地址为1，每个元素站1个地址空间，则a 8,5的地址为_A、13 B、33 C、18 D、404、一个n*n的对称矩阵，如果以行或列为主序放入内
8、存，则容量为_A、n*n B、n*n/2 C、n*(n+1)/2 D、(n+1)*(n+1)/25、稀疏矩阵一般的压缩存储方法有两种，即_和_6、设广义表L=(a,c),(b,d),运算head(head(tail(L)是_7、对于广义表L=(),()，则head(L)是_,L长度是_,tail(L)是_8、设A=(a,b,c); B=(A,(c,d); C=(a,(B,A),(e,f),求head(head(head(tail(c)=_第六章作业一、选择、填空1、设高度为h的二叉树只有度为0和2的结点（第一层为根结点所在的层），则 此类二叉树所包含的结点数至少为_A 2h B 2h-1 C
9、2h+1 D h+12、下图1的二叉树中序遍历为_A abcdgef B dfebagc C dbaefcg D defbagc3、如果T2是由有序树T1转换而来的二叉树，那么T1结点的先序就是T2中结点的_A 先序 B 中序 C 后序 D 层次序 图24、深度为5的二叉树至多有_个结点A 16 B 32 C 31 D 105、根据使用频率为5个字符设计的哈夫曼编码不可能是_ A 111,110,10,01,00 B 000,001,010,011,1C 100,11,10,1,0 D 001,000,01,11,106、如图2所示的二叉树，回答以下问题（1）其中序遍历序列为_（2）其先序遍历
10、序列为_（3）其中后序遍历序列为_（4）该二叉树对应森林是_5、以数据集4，5，6，7，10，12，18为结点权值所构造的哈夫曼树为_,其带权路径长度为_二、简答题：1 假设二叉树bt的存储结构如下：其中bt为树根结点指针，left,right分别为结点的左、右孩子指针域，在这里使用结点编号作为指针域值，0表指针域为空，data表结点数据域，请完成下列各题：（1）画出二叉树bt的逻辑结构（2）写出按先序、中序、后序遍历bt所得到的结点序列62、假设二叉树采用顺序存储结构如下表所示（1）画出二叉树表示（2）写出先序、中序、后序遍历结果（3）写出结点值C的双亲结点，其左右孩子（4）画出把此二叉树还
11、原成森林的图 第七章 图 一选择、填空 1、在一个图中，所有顶点的度数之和等于所有边数的_倍，对于一个有向图，所有等点的入度之和等于所有顶点出度之和的_倍 A、 B、1 C、2 D、4 2、一个有n个顶点的无向图最多有_条边，若采用邻接矩阵表示，则该矩阵的大小是_ A、n B n(n-1)/2 C n-1 D n*n 3、已知一个图，若从顶点a出发按深度有限搜索进行遍历，则可能得到的一种顶点序列是_;若从顶点a出发按广度有限搜索进行遍历，则可能得到的一种顶点序列是_A、abecdf B、aedfcb C、aebcfd D、abcefd4、已知一有向图的邻接表存储结构如图所示，则（1）根据有向图
12、深度有限搜索遍历算法，从顶点V1出发得到的顶点序列是_，根据根据有向图广度有限搜索遍历算法，从顶点V1出发得到的顶点序列是_A、V1V2V3V4V5 B、V1V3V2V4V5C、V1V3V4V5V2 D、V1V4V3V5V2 5、n个顶点的连通图至少_条边A、n B、n-1 C、n*n D、n+1二、书上P2328-1，8-2，8-3实验一、线性表表示及实现实验题目: 线性表顺序和链表表示及实现实验目的：1学会定义线性表顺序存储结构 2 通过对顺序存储结构的分析，掌握线性表动态分配存储及基本操作，熟悉线性表基本操作及函数定义 3 进一步熟悉C语言基本结构，掌握程序头文件，实现文件及主文件关系及
13、各作用实验内容：建立10个数据元素的线性表L=1，2，310指定在第2位置插入元素25，然后删除第4个位置上的元素，分别显示各步骤结果 实验二:顺序栈的实践实验目的：熟练掌握栈的结构、特点及有关概念，学会建立栈的基本操作，了解栈满和栈空的判断条件及描述方法实验内容：建立一个字符栈 用顺序栈设计实现堆栈,堆栈操作集合包括初始化,判断栈空,入栈,出栈,取栈顶元素等(2)设计一个主函数对顺序栈进行测试,如:依次输入数据元素1,2,3,4,5,然后判断栈是否为空,显示栈顶元素,出栈并在屏幕上显示出栈的数据元素实验三：栈和队列的综合应用实验目的：了解并掌握顺序栈及顺序队列的 基本概念和基本操作。熟练掌握
14、栈和队列的 结构及这两种数据结构的 特点，在两种存储结构上实现栈的 基本运算。特别注意栈空，栈满的 判断条件；熟练掌握链队列和顺序循环队列的 基本运算并能简单应用实验题目 ：1、回文是指一个字符串从头到尾和从尾到头都一样，如串“”abcba”，设字符串从输入设备一个一个字符读入，至”#”结束 ，请用顺序栈和顺序队列两种算法判断一 个字符串是否为回文2、请利用所学栈的知识设计一个进制转换器，实现十进制到八进制的转换实验四、 堆分配存储表示的串操作实验目的：了解串的顺序存储的两种表示方式：定长顺序存储和堆分配存储，掌握其基本概念实验内容：利用堆分配存储法，生成两个值等于串常量的串S、T，比较两串的
15、大小，输出结束；在串S的第POS位置上（POS值自己设定）插入串T，并输出新串；计算新串的串长并输出实验要点：利用系统提供的库函数malloc(),realloc()作为串分配或重新分配存储空间，用free函数释放串值所占空间 实验五 稀疏矩阵的转置一 实验目的:了解稀疏矩阵的三元组顺序表的表示方式,掌握矩阵转置运算的操作方法二 实验内容输入一个稀疏矩阵A,建立A的三元组顺序表,求A的转置矩阵B,请用两种转置法实现稀疏矩阵的转置,注意矩阵的建立、输出的实现三 实验要求1 编写源程序2 调试体会实验六 七 二叉树的基本操作【实验目的】1. 熟练掌握树的基本概念、二叉树的基本操作2. 重点掌握二叉
16、树的生成、遍历及求深度等算法。3掌握运用递归方式描述算法及编写递归C程序的方法，提高算法分析和程序设计能力。【实验题目】一、二叉树的基本运算实验【问题描述】二叉树采用二叉链表作存储结构，试编程实现二叉树的如下基本操作：1. 按先序序列构造一棵二叉链表表示的二叉树T；2. 对这棵二叉树进行遍历：先序、中序、后序以及层次遍历序列，分别输出结点的遍历序列；3. 求二叉树的深度/结点数目/叶结点数目；4. 将二叉树每个结点的左右子树交换位置。【实验要求】1 编写源程序2 调试心得二、赫夫曼树与赫夫曼编码【问题描述】 利用Huffman编码进行通信可以大大提高信道利用率，缩短信息传输时间，降低传输成本。
17、但是，这要求在发送端通过一个编码系统对待传数据预先编码，在接受端将传来的数据编码进行译码（复原）。对于有些信道，每端都需要一个完整的编译码系统。试为这样的信息收发站编写一个Huffman的编译码系统。给定一组权值7，9，5，6，10，1，13，15，4，8，构造一棵赫夫曼树，并计算带权路径长度WPL。【算法描述】1. 初始化：从键盘读入n个字符，以及它们的权值，建立Huffman树。（具体算法可参见教材P147的算法6.12）2. 编码：根据建立的Huffman树，求每个字符的Huffman编码。对给定的待编码字符序列进行编码。3. 译码：利用已经建立好的Huffman树，对上面的编码结果译码
18、。译码的过程是分解电文中的字符串，从根结点出发，按字符0和1确定找左孩子或右孩子，直至叶结点，便求得该子串相应的字符。具体算法留给读者完成。4. 打印 Huffman树。【实验要求】1 编写源程序2 画出程序流程图3 调试心得实验八 图的建立和应用【实验目的】1.熟练掌握图的邻接矩阵和邻接表的存储方式；2.实现图的一些基本运算，特别是深度遍历和广度遍历；【实验题目】建立一无向图的深度优先搜索生成树并输出得到的序列【实验要求】1 用邻接表和邻接矩阵两种方法存储图2 编写源程序3 调试心得实验九 查找算法的实现【实验目的】1. 熟练掌握各种静态查找表的查找方法（顺序查找法、折半查找法、索引顺序表查
19、找）；2. 熟练掌握二叉排序树的构造方法和查找算法；3. 掌握描述查找过程的判定树的构造方法，以及按照定义计算各种查找方法在等概率情况下查找成功时的平均查找长度；4. 了解二叉平衡树的建立和维护平衡的方法。 【实验题目】静态查找表可以有不同的表示方法，在不同的表示方法中，实现查找操作的方法也不同。对静态查找表可以用顺序表或线性链表进行表示，也可组织成有序的顺序表，或者是索引顺序表，相应的查找方法可采用顺序查找方法、折半查找方法和索引顺序查找的方法。请用顺序查找方法设计一个有关静态查找表的建立、查找等基本操作的演示程序。【实验要求】1 编写源程序2 调试心得实验十 内部排序算法的实现【实验目的】1、 掌握各种排序算法的思想、方法和稳定性。2、 掌握快速排序、堆排序、归并排序算法的实现。3、 了解每一种排序算法的时间以及空间复杂度。【实验题目】任意给出一组关键字（关键字的个数和值在运行时由键盘输入），分别采用直接插入排序、希尔排序和快速排序算法对其进行排序，并输出每个排序算法得到的序列。【实验要求】1 编写源程序2 调试心得
