数据结构重修作业题.docx
《数据结构重修作业题.docx》由会员分享，可在线阅读，更多相关《数据结构重修作业题.docx（18页珍藏版）》请在冰点文库上搜索。
数据结构重修作业题
第一章绪论
一、选择题
3.在数据结构中，从逻辑上可以把数据结构分成（）
（A）动态结构和静态结构（B）紧凑结构和非紧凑结构
（C）线性结构和非线性结构（D）内部结构和外部结构
5.算法分析的目的是（）。
（A）找出数据结构的合理性（B）研究算法中的输入和输出的关系
（C）分析算法的效率以求改进（D）分析算法的易懂性和文档性
二、判断题
1.数据的机内表示称为数据的存储结构。
（）
2.算法就是程序。
（）
5.算法的时间复杂度取决于问题的规模和待处理数据的初态。
（）
三、填空题
1.数据逻辑结构包括________、________、_________和_________四种类型,其中树形结构和图形结构合称为_____。
2.在线性结构中,第一个结点____前驱结点,其余每个结点有且只有______个前驱结点；最后一个结点______后续结点,其余每个结点有且只有_______个后续结点。
3.在树形结构中,树根结点没有_______结点,其余每个结点有且只有_______个前驱结点；叶子结点没有________结点,其余每个结点的后续结点可以_________。
4.在图形结构中,每个结点的前驱结点数和后续结点数可以_________。
5.线性结构中元素之间存在________关系,树形结构中元素之间存在______关系,图形结构中元素之间存在_______关系。
8.链式存储结构与顺序存储结构相比较,主要优点是________________________________。
9.设有一批数据元素,为了最快的存储某元素,数据结构宜用_________结构,为了方便插入一个元素,数据结构宜用____________结构。
四、算法分析题,求下列算法段的语句频度及时间复杂度
for（i=1;i<=n;i++）
for（j=1;j<=i;j++）
for（k=1;k<=j;k++）
x=i+j-k;
第二章线性表
一、选择题
1.一个线性表第一个元素的存储地址是100,每个元素的长度为2,则第5个元素的地址是（）
（A）110（B）108（C）100（D）120
2.向一个有127个元素的顺序表中插入一个新元素并保持原来顺序不变，平均要移动（）个元素。
（A）64（B）63（C）63.5 （D）7
3.线性表采用链式存储结构时，其地址（）。
（A）必须是连续的（B）部分地址必须是连续的
（C）一定是不连续的（D）连续与否均可以
4.在一个单链表中，若p所指结点不是最后结点，在p之后插入s所指结点，则执行（）
（A）s.next=p;p.next=s;（B）s.next=p.next;p.next=s;
（C）s.next=p.next;p=s;（D）p.next=s;s.next=p;
5.在一个单链表中，若删除p所指结点的后续结点，则执行（）
（A）p.next=p.next.next;（B）p=p.next;p.next=p.next.next;
（C）p.next=p.next;（D）p=p.next.next;
6.下列有关线性表的叙述中，正确的是（）
（A）线性表中的元素之间隔是线性关系
（B）线性表中至少有一个元素
（C）线性表中任何一个元素有且仅有一个直接前趋
（D）线性表中任何一个元素有且仅有一个直接后继
7.线性表是具有n个（）的有限序列（n≠0）
（A）表元素（B）字符（C）数据元素 （D）数据项
二、判断题
1.线性表的链接存储，表中元素的逻辑顺序与物理顺序一定相同。
（）
3.线性结构的特点是只有一个结点没有前驱，只有一个结点没有后继，其余的结点只有一个前驱和后继。
（）
三、填空题
1.已知P为单链表中的非首尾结点，在P结点后插入S结点的语句为：
_______________________。
2.顺序表中逻辑上相邻的元素物理位置（）相邻，单链表中逻辑上相邻的元素物理位置_________相邻。
四、算法设计题
对于结点类型为LNode的单链表，编写出下列每个算法。
（1）删除单链表中的第i个结点。
（2）在有序单链表中插入一个元素x的结点。
（3）从单链表中查找出所有元素的最大值，该值由函数返回，若单链表为空，则显示出错信息并停止运行。
（4）统计出单链表中结点的值等于给定值x的结点数。
第三章栈和队列
一、选择题
1.一个栈的入栈序列是a,b,c,d,e,则栈的不可能的输出序列是（）。
（A）edcba（B）decba（C）dceab（D）abcde
2.栈结构通常采用的两种存储结构是（）。
（A）线性存储结构和链表存储结构（B）散列方式和索引方式
（C）链表存储结构和数组（D）线性存储结构和非线性存储结构
3.判定一个栈ST（最多元素为m0）为空的条件是（）。
（A）ST.top!
=0（B）ST.top==0
（C）ST.top!
=m0（D）ST.top=m0
4.判定一个栈ST（最多元素为m0）为栈满的条件是（）。
（A）ST.top!
=0（B）ST->top==0
（C）ST.top!
=m0-1（D）ST.top==m0-1
5.一个队列的入列序列是1,2,3,4,则队列的输出序列是（）。
（A）4,3,2,1（B）1,2,3,4（C）1,4,3,2（D）3,2,4,1
6.循环队列用数组A[0,m-1]存放其元素值,已知其头尾指针分别是front和rear则当前队列中的元素个数是（）
（A）（rear-front+m）%m（B）rear-front+1（C）rear-front-1（D）rear-front
7.栈和队列的共同点是（）
（A）都是先进后出（B）都是先进先出
（C）只允许在端点处插入和删除元素（D）没有共同点
9.4个元素a1，a2，a3和a4依次通过一个栈，在a4进栈前，栈的状态，则不可能的出栈序是（ ）
（A）a4，a3，a2，a1 （B）a3，a2，a4，a1
（C）a3，a1，a4，a2 （D）a3，a4，a2，a1
10.以数组Q[0..m－1]存放循环队列中的元素，变量rear和qulen分别指示循环队列中队尾元素的实际位置和当前队列中元素的个数，队列第一个元素的实际位置是（ ）
（A）rear－qulen （B）rear－qulen＋m
（C）m－qulen （D）1＋（rear＋m－qulen）%m
二、填空题
1.栈的特点是_______________________,队列的特点是__________________________。
2.线性表、栈和队列都是_____________________结构,可以在线性表的______________位置插入和删除元素，对于栈只能在________插入和删除元素，对于队列只能在_______插入元素和_________删除元素。
3.一个栈的输入序列是12345,则栈有输出序列12345是____________。
（正确/错误）
4.设栈S和队列Q的初始状态皆为空，元素a1，a2，a3，a4，a5和a6依次通过一个栈，一个元素出栈后即进入队列Q，若6个元素出队列的顺序是a3，a5，a4，a6，a2，a1则栈S至少应该容纳_____个元素。
三、算法设计题
1.链栈的出栈入栈算法。
2.顺序循环队列的出队入队算法.
第四章串和数组
一、选择题
1.下列关于串的叙述中，正确的是（）
（A）一个串的字符个数即该串的长度（B）一个串的长度至少是1
（C）空串是由一个空格字符组成的串
（D）两个串S1和S2若长度相同，则这两个串相等
2.二维数组M的元素是4个字符（每个字符占一个存储单元）组成的串,行下标i的范围从0到4,列下标j的范围从0到5,M按行存储时元素M[3][5]的起始地址与M按列存储时元素（）的起始地址相同。
（A）M[2][4]（B）M[3][4]（C）M[3][5]（D）M[4][4]
3.数组A[8][10]中,每个元素A的长度为3个字节,从首地址SA开始连续存放在存储器内,存放该数组至少需要的单元数是（）。
（A）80（B）100（C）240（D）270
4.数组A[8][10]中,每个元素A的长度为3个字节,从首地址SA开始连续存放在存储器内,该数组按行存放时,元素A[7][4]的起始地址为（）。
（A）SA+141（B）SA+144（C）SA+222（D）SA+225
5.数组A[8][10]中,每个元素A的长度为3个字节,从首地址SA开始连续存放在存储器内,该数组按列存放时,元素A[4][7]的起始地址为（）。
（A）SA+141（B）SA+180（C）SA+222（D）SA+225
6.稀疏矩阵一般的压缩存储方法有两种,即（）。
（A）二维数组和三维数组（B）三元组和散列
（C）三元组和十字链表（D）散列和十字链表
7.若采用三元组压缩技术存储稀疏矩阵,只要把每个元素的行下标和列下标互换,就完成了对该矩阵的转置运算,这种观点（）。
（A）正确（B）错误
8.设矩阵A是一个对称矩阵,为了节省存储,将其下三角部分按行序存放在一维数组B[1,n（n-1）/2]中,对下三角部分中任一元素ai,j（i<=j）,在一组数组B的下标位置k的值是（）。
（A）i（i-1）/2+j-1（B）i（i-1）/2+j（C）i（i+1）/2+j-1（D）i（i+1）/2+j
4.串是一种特殊的线性表,其特殊性表现在（）
（A）可以顺序存储（B）数据元素是一个字符
（C）可以链式存储（D）数据元素可以是多个字符
5．设串S1=‘ABCDEFG’,s2=‘PQRST’,函数CONCAT（X，Y）返回X和Y串的连接串，SUBSTR（S，I，J）返回串S从序号I开始的J个字符组成的字串，LENGTH（S）返回串S的长度，则CONCAT（SUBSTR（S1，2，LENGTH（S2）），SUBSTR（S1，LENGTH（S2），2））的结果串是（）
（A）BCDEF（B）BCDEFG（C）BCPQRST（D）BCDEFEF
2、填空题
1.己知二维数组A[m][n]采用行序为主方式存储,每个元素占k个存储单元,并且第一个元素的存储地址是LOC（A[0][0]）,则A[0][0]的地址是_____________________。
2.二维数组A[10][20]采用列序为主方式存储,每个元素占一个存储单元,并且A[0][0]的存储地址是200,则A[6][12]的地址是________________。
3.有一个10阶对称矩阵A,采用压缩存储方式（以行序为主,且A[0][0]=1）,则A[8][5]的地址是__________________。
4.设n行n列的下三角矩阵A已压缩到一维数组S[1..n*（n+1）/2]中,若按行序为主存储,则A[i][j]对应的S中的存储位置是________________。
5.若A是按列序为主序进行存储的4×6的二维数组,其每个元素占用3个存储单元,并且A[0][0]的存储地址为1000,元素A[1][3]的存储地址为___________,该数组共占用_______________个存储单元。
三、算法设计
1.串的模式匹配算法。
第五章树与二叉树
3.二叉树的前序遍历序列中,任意一个结点均处在其子女结点的前面,这种说法（）
（A）正确（B）错误（C）不同情况下答案不确定
4.由于二叉树中每个结点的度最大为2,所以二叉树是一种特殊的树,这种说法（）
2.正确（B）错误（C）不同情况下答案不确定
5.设高度为h的二叉树上只有度为0和度为2的结点,则此类二叉树中所包含的结点数至少为（）。
（A）2h（B）2h-1（C）2-35-3+1（D）h+1
6.已知某二叉树的后序遍历序列是dabec。
中序遍历序列是debac,它的前序遍历序列是（）。
（A）acbed（B）decab（C）deabc（D）cedba
7.如果T2是由有序树T转换而来的二叉树,那么T中结点的前序就是T2中结点的（）
（A）前序（B）中序（C）后序（D）层次序
8.某二叉树的前序遍历结点访问顺序是abdgcefh,中序遍历的结点访问顺序是dgbaechf,则其后序遍历的结点访问顺序是（）。
（A）bdgcefha（B）gdbecfha（C）bdgaechf（D）gdbehfca
9.二叉树为二叉排序树的充分必要条件是其任一结点的值均大于其左孩子的值、小于其右孩子的值。
这种说法（）
（A）正确（B）错误（C）不同情况下答案不确定
10.按照二叉树的定义,具有3个结点的二叉树有（）种。
（A）3（B）4（C）5（D）6
11.在一非空二叉树的中序遍历序列中,根结点的右边（）
（A）只有右子树上的所有结点（B）只有右子树上的部分结点
（C）只有左子树上的部分结点（D）只有左子树上的所有结点
12.树最适合用来表示（）。
（A）有序数据元素（B）无序数据元素
（C）元素之间具有分支层次关系的数据（D）元素之间无联系的数据
13.任何一棵二叉树的叶结点在先序、中序和后序遍历序列中的相对次序（）
（A）不发生改变（B）发生改变（C）不能确定D.以上都不对
15.对一个满二叉树,m个树叶,n个结点,深度为h,则（）
（A）n=h+m（B）h+m=2n（C）m=h-1（D）n=2h-1
16.如果某二叉树的前序为stuwv,中序为uwtvs,那么该二叉树的后序为（）
（A）uwvts（B）vwuts（C）wuvts（D）wutsv
17.具有五层结点的二叉平衡树至少有（）个结点。
（A）10（B）12（C）15（D）17
3.已知一棵树边的集合为｛，,，，，，，，，，，，｝，画出这棵树，并回答下列问题：
哪个结点是根结点？
1 哪些结点是叶子结点？
2 哪个结点是结点G的双亲结点？
3 哪些结点是结点G的祖先结点？
4 哪些结点是结点G的孩子结点？
5 哪些结点是结点E的子孙结点？
6 哪些结点是结点E的兄弟结点？
哪些是结点F的兄弟结点？
7 结点B和N的层次分别是多少？
8 树的深度是多少？
1）以结点C为根的子树的深度是多少？
4.已知一棵二叉树的先序、中序和后序序列如下，其中各有一部分未给出其值，请构造出该二叉树。
先序：
A_CDEF_H_J中序：
C_EDA_GFI_后序：
C__BHGJI__
5.已知一棵树的度为4，其中度为4的结点的数目为3，度为3的结点的数目为4，度为2的结点的数目为54.按照下列给定二叉树的先序遍历序列、中序遍历和后序遍历序列，分别构造出二叉树。
1 先序遍历序列：
EBADCFHGIKJ中序遍历系列：
ABCDEFGHIJK
2 中序遍历序列：
ACBGEDF后序遍历序列：
ABCDEFG
3 度为1的结点的数目为2，请求出该树中的叶子结点的数目。
二、判断题
1.二叉树中任何一个结点的度都是2。
（）
2.由二叉树结点的先根序列和后根序列可以唯一地确定一棵二叉树。
（）
3.一棵哈夫曼树中不存在度为1的结点。
（）
4.平衡二叉排序树上任何一个结点的左、右子树的高度之差的绝对值不大于2（）
6.
三、填空题
3.若结点A有三个兄弟（包括A本身）,并且B是A的双亲结点,B的度是_______________
4.若一棵具有n个结点的二叉树采用标准链接存储结构,那么该二叉树所有结点共有_______个空指针域。
5.已知二叉树的前序序列为ABDEGCFHIJ,中序序列为DBGEAHFIJC,写出后序序列_______________。
6.已知二叉树的后序序列为FGDBHECA,中序序列为BFDGAEHC,并写出前序序列_________________。
7.找出满足下列条件的二叉树
1）先序和中序遍历，得到的结点访问顺序一样。
_________________________
2）后序和中序遍历，得到的结点访问顺序一样。
_________________________
3）先序和后序遍历，得到的结点访问顺序一样。
__________________________
9.一棵二叉树有67个结点，这些结点的度要么是0，要么是2。
这棵二叉树中度为2的结点有______________________个。
10.含有100个结点的树有_______________________________________条边。
四、问答题
4.有七个带权结点,其权值分别为3,7,8,2,6,10,14,试以它们为叶结点构造一棵哈夫曼树（请按照每个结点的左子树根结点的权小于等于右子树根结点的权的次序构造〉,并计算出带权路径长度WPL及该树的结点总数。
5.有一电文共使用五种字符a,b,c,d,e,其出现频率依次为4,7,5,2,9。
（1）试画出对应的编码哈夫曼树（要求左子树根结点的权小于等于右子树根结点的权）。
（2）求出每个字符的晗夫曼编码。
（3）求出传送电文的总长度。
（4）并译出编码系列1100011100010101的相应电文。
第七章图
一、判断题
1.一个无向图的邻接矩阵中各非零元素之和与图中边的条数相等。
（）
2.一个有向图的邻接矩阵中各非零元素之和与图中边的条数相等。
（）
3.一个对称矩阵一定对应着一个无向图。
（）
4.一个有向图的邻接矩阵一定是一个非对称矩阵。
（）
二、选择题
1.在一个无向图中,所有顶点的度数之和等于所有边数的（）倍。
（A）1/2（B）1（C）2（D）4
2.在一个有向图中,所有顶点的入度之和等于所有顶点的出度之和的（）倍。
（A）1/2（B）1（C）2（D）4
3.一个有n个顶点的无向图最多有（）条边。
（A）n（B）n（n-1）（C）n（n-1）/2（D）2n
4.具有4个顶点的无向完全图有（）条边。
（A）6（B）12（C）16（D）20
5.具有6个顶点的无向图至少应有（）条边才能确保是一个连通图。
（A）5（B）6（C）7（D）8
6.在一个具有n个顶点的无向图中,要连通全部顶点至少需要（）条边。
（A）n（B）n+1（C）n-1（D）n/2
7.对于一个具有n个顶点的无向图,若采用邻接矩阵表示,则该矩阵的大小（）
（A）n（B）（n-1）2（C）n-1（D）n2
8.对于一个具有n个顶点和e条边的无向图,若采用邻接表表示,则表头向量的大小为（），所有邻接表中的结点总数是（）。
①（A）n（B）n+1（C）n-1（D）n+e
②（A）e/2（B）e（C）2e（D）n+e
9.采用邻接表存储的图的深度优先遍历算法类似于二叉树的（）。
（A）先序遍历（B）中序遍历（C）后序遍历（D）按层遍历
10.采用邻接表存储的图的宽度优先遍历算法类似于二叉树的（）。
（A）先序遍历（B）中序遍历（C）后序遍历（D）按层遍历
11.判定一个有向图是否存在回路除了可以利用拓扑排序方法外,还可以利用（）.
（A）求关键路径的方法（B）求最短路径的Dijkstm方法
（C）宽度优先遍历算法（D）深度优先遍历算法
12.用Prim算法求下列连通的带权图的最小代价生成树，在算法执行的某刻，已选取的顶点集合U＝{1，2，5}，边的集合TE＝{（1，2），（2，5）}，要选取下一条权值最小的边，应当从（）组中选取。
（A）{（1，4），（3，4），（3，5），（2，5）}
（B）{（5，4），（5，3），（5，6）}
（C）{（1，2），（2，3），（3，5）}
（D）{（3，4），（3，5），（4，5），（1，4）}
三、填空题
1.n个顶点的连通图至少_____________条边。
2.在一个无环有向图G中，若存在一条从顶点i到顶点j的弧，则在顶点的拓扑序列中，顶点i与顶点j的先后次序是_________________。
3.在一个无向图的邻接表中，若表结点的个数是m，则图中边的条数是________________条。
4.如果从一个顶点出发又回到该顶点，则此路径叫做_______。
5.如果从一无向图的任意顶点出发进行一次深度优先搜索即可访问所有顶点，则该图一定是____________。
6.若采用邻接表的存储结构，则图的广度优先搜索类似于二叉树的________遍历。
7.一个连通图的生成树是该图的________连通子图。
若这个连通图有n个顶点,则它的生成树有________条边。
第八章查找
一、判断题
1.用二分查找法对一个顺序表进行查找，这个顺序表可以是按各键值排好序的，也可以是没有按键值排好序的。
（）
3.哈希表的定义函数H（key）=key%p（p<=m）这种方法是直接定址法。
（）
2、填空题
1.顺序查找法的平均查找长度为__________，二分查找法的平均查找长度为________，分块查找法（以顺序查找确定块）的平均查找长度为__________，分块查找法（以二分查找确定块）的平均查找长度为__________。
2.在各种查找方法中,平均查找长度与结点个数n无关的查法方法是_________
3.二分查找的存储结构仅限于_________,且是__________。
4.在分块查找方法中,首先查找__________,然后再查找相应的___________。
5.长度为255的表,采用分块查找法,每块的最佳长度是____________。
7.假设在有序线性表A[1..20]上进行二分查找,则比较一次查找成功的结点数为_________,则比较二次查找成功的结点数为__________,则比较三次查找成功的结点数为_________,则比较四次查找成功的结点数为________,则比较五次查找成功的结点数为_________,平均查找长度为_________。
9.己知一个有序表为（12,18,20,25,29,32,40,62,83,90,95,98）,当二分查找值为29和90的元素时,分别需要________次和____________次比较才能查找成功；若采用顺序查找时,分别需要___________次和_________次比较才能查找成功。
三、选择题
1.顺序查找法适合于存储结构为（）的线性表。
（A）散列存储（B）顺序存储或链接存储（C）压缩存储（D）索引存储
2.对线性表进行二分查找时,要求线性表必须（）。
（A）以顺序方式存储（B）以链接方式存储
（C）以顺序方式存储,且结点按关键字有序排序
（D）以链接方式存储,且结点按关键字有序排序
3.采用顺序查找方法查找长度为n的线性表时,每个元素的平均查找长度为（）
（A）n（B）n/2（C）（
升级会员 