安徽工程大学数据结构各章作业与实验

1、第一章 一、简答题1 设有数据逻辑结构为： B=（K，R）；K=K1，K2Kn; R=<K1,K3>,<K1,K8>, <K2,K3>, <K2,K4>, <K2,K5>, <K3,K9>, <K5,K6>, <K8,K9>, <K9,K7>, <K4,K7>, <K4,K6> 画出这个逻辑结构的图示，并确定相对于关系R，哪些结点是开始结点，哪些结点是终端结点2 有下列几种用二元组表示的数据结构，画出它们分别对应的逻辑图形表示，并指出它们分别属于何种结构。1) A

2、=（K，R），其中K=a,b,c,d,e,f,g,h; R=r，r=<a,b>,<b,c>, <c,d>, <d,e>, <e,f>, <f,g>, <g,h>2) B=(K,R),其中K=a,b,c,d,e,f,g,h; R=r， r=<d,b>,<d,g>, <d,a>, <b,c>, <g,e>, <g,h>, <e,f> 二、求下列程序段的时间复杂度(1) for (I=0;I<n;I+) (4) fact(int

3、 n) for (j=0;j<m;j+) if (n<=1) AIj=0; return 1;(2) I=s=0; else While (s<n) 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;k<I+j;k+) I=I*3; s+; 第二章 一.选择、填空： 1 不带头结点的单链表head为空的判定条件是_ ； 带头结点的单链表head为空的判定条件是_ A. head=null B. hea

4、d->next=null C. Head->next=head D. Head!=null 2 在循环双链表P所指接点之前插入S所指结点的操作是_ A. P->prior=S;S->next=P;p->next= S;S ->prior=P->prior 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->

5、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 ）之前插入一个元素时，需后移_个元素；删除长度为n的向量第i个元素C（0 in-1 ）之前插入一个元素时，需前移_个元素 第三章作业一 选择、填空题1 判定一个栈（最多n个元素）为空的条件是_;判定为满的条件

6、是_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->rear+14 判定循环队列Q（最多n个元素）为空的条件是_;为满的条

7、件是_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)返回

8、串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树

9、形 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的对称矩阵，如果以行或列为主序放入内存

10、，则容量为_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 2

11、h+1 D h+12、下图1的二叉树中序遍历为_A abcdgef B dfebagc C dbaefcg D defbagc3、如果T2是由有序树T1转换而来的二叉树，那么T1结点的先序就是T2中结点的_A 先序 B 中序 C 后序 D 层次序abcdgcefhiabcdgef图1 图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

12、）其中序遍历序列为_（2）其先序遍历序列为_（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的双亲结

13、点，其左右孩子（4）画出把此二叉树还原成森林的图 第七章 图 一选择、填空 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、已知一

14、有向图的邻接表存储结构如图所示，则（1）根据有向图深度有限搜索遍历算法，从顶点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语

15、言基本结构，掌握程序头文件，实现文件及主文件关系及各作用实验内容：建立10个数据元素的线性表L=1，2，310指定在第2位置插入元素25，然后删除第4个位置上的元素，分别显示各步骤结果 实验二:顺序栈的实践实验目的：熟练掌握栈的结构、特点及有关概念，学会建立栈的基本操作，了解栈满和栈空的判断条件及描述方法实验内容：建立一个字符栈 用顺序栈设计实现堆栈,堆栈操作集合包括初始化,判断栈空,入栈,出栈,取栈顶元素等(2)设计一个主函数对顺序栈进行测试,如:依次输入数据元素1,2,3,4,5,然后判断栈是否为空,显示栈顶元素,出栈并在屏幕上显示出栈的数据元素实验三：栈和队列的综合应用实验目的：了解并掌

16、握顺序栈及顺序队列的 基本概念和基本操作。熟练掌握栈和队列的 结构及这两种数据结构的 特点，在两种存储结构上实现栈的 基本运算。特别注意栈空，栈满的 判断条件；熟练掌握链队列和顺序循环队列的 基本运算并能简单应用实验题目 ：1、回文是指一个字符串从头到尾和从尾到头都一样，如串“”abcba”，设字符串从输入设备一个一个字符读入，至”#”结束 ，请用顺序栈和顺序队列两种算法判断一 个字符串是否为回文2、请利用所学栈的知识设计一个进制转换器，实现十进制到八进制的转换实验四、堆分配存储表示的串操作实验目的：了解串的顺序存储的两种表示方式：定长顺序存储和堆分配存储，掌握其基本概念实验内容：利用堆分配存

17、储法，生成两个值等于串常量的串S、T，比较两串的大小，输出结束；在串S的第POS位置上（POS值自己设定）插入串T，并输出新串；计算新串的串长并输出实验要点：利用系统提供的库函数malloc(),realloc()作为串分配或重新分配存储空间，用free函数释放串值所占空间 实验五 稀疏矩阵的转置一 实验目的:了解稀疏矩阵的三元组顺序表的表示方式,掌握矩阵转置运算的操作方法二 实验内容输入一个稀疏矩阵A,建立A的三元组顺序表,求A的转置矩阵B,请用两种转置法实现稀疏矩阵的转置,注意矩阵的建立、输出的实现三 实验要求1 编写源程序2 调试体会实验六 七 二叉树的基本操作【实验目的】1. 熟练掌握

18、树的基本概念、二叉树的基本操作2. 重点掌握二叉树的生成、遍历及求深度等算法。3掌握运用递归方式描述算法及编写递归C程序的方法，提高算法分析和程序设计能力。【实验题目】一、二叉树的基本运算实验【问题描述】二叉树采用二叉链表作存储结构，试编程实现二叉树的如下基本操作：1. 按先序序列构造一棵二叉链表表示的二叉树T；2. 对这棵二叉树进行遍历：先序、中序、后序以及层次遍历序列，分别输出结点的遍历序列；3. 求二叉树的深度/结点数目/叶结点数目；4. 将二叉树每个结点的左右子树交换位置。【实验要求】1 编写源程序2 调试心得二、赫夫曼树与赫夫曼编码【问题描述】 利用Huffman编码进行通信可以大大

19、提高信道利用率，缩短信息传输时间，降低传输成本。但是，这要求在发送端通过一个编码系统对待传数据预先编码，在接受端将传来的数据编码进行译码（复原）。对于有些信道，每端都需要一个完整的编译码系统。试为这样的信息收发站编写一个Huffman的编译码系统。给定一组权值7，9，5，6，10，1，13，15，4，8，构造一棵赫夫曼树，并计算带权路径长度WPL。【算法描述】1. 初始化：从键盘读入n个字符，以及它们的权值，建立Huffman树。（具体算法可参见教材P147的算法6.12）2. 编码：根据建立的Huffman树，求每个字符的Huffman编码。对给定的待编码字符序列进行编码。3. 译码：利用已经建立好的Huffman树，对上面的编码结果译码。译码的过程是分解电文中的字符串，从根结点出发，按字符'0'和'1'确定找左孩子或右孩子，直至叶结点，便求得该子串相应的字符。具体算法留给读者完成。4. 打印 Huffman树。【实验要求】1 编写源程序2 画出程序流程图3 调试心得实验八 图的建立和应用【实验目的】1