还剩5页未读，继续阅读
文本内容:
《数据结构》作业
一、选择题
1.线性表的顺序存储结构是一种—的存储结构，线性表的链式存储结构是一种—的存储结构a.随机存储；b.顺序存储；c.索引存取；d.HASH存取
2.一个栈的入栈序列是a,b,c,d,e,则栈的不可能的输出序列是oa.edcba;b.decba;c.dceab;d.abcde
3.一个队列的入队序列是1,2,3,4,则队列的输出序列是oa.4,3,2,1;b.1,2,3,4;c.1,4,3,2;d.3,2,4,
14.在一个单链表中，已知p结点是q结点的直接前驱结点，若在p和q之间插入结点s,则执行的操作是oa.s-nxet=p-next;p-next=s;b.p-next=s-next;s-next=p;c.q-next=s;s-next=p;d.p-next=s;s-next=q;
5.设有两个串p,q,求q在P中首次出现的位置的运算称作oa.联接b.模式匹配c.求子串d,求串长
6.二维数组M的成员是6个字符每个字符占一个存储单元组成的串，行下标i的范围从0到8,列下标j的范围从1到10,则存放M至少需要个字节a.90b.180c.240d.
5407.在线索二叉树中，结点p没有左子树的充要条件是o a.p-lch=NULL b.p-ltag==lc.p-ltag==l且p-lch=NULLd.以上都不对
8.在栈操作中，输入序列为A,B,C,D,不可能得到的输出序列为A、A,B,C,D B、D,C,B,AC、A,C,D,B D、C,A,B,D
9.已知某二叉树的后序序列是dabec,中序序列是debac,则它的先序序列是A、acbed B、decab C、deabc Dcedba
10.设矩阵A是一个对称矩阵，为了节省存储空间，将其下三角部分见下图按行序存放在一维数组B[L.nn-1/2]中，对任一上三角部分元素附i Y/,在一维数组B的存放位置是A^-D+/1R77-1122见心+心+/c iDm
2211.图G中有n个顶点，n-l条边，那么图G一定是一棵树吗？A、一定是B、一定不是C、不一定
12.用某种排序方法对关键字序列{25,84,21,47,15,27,68,35,20}进行排序时，元素序列的变化情况如下
①{25,84,21,47,15,27,68,35,20}
②{20,15,21,25,47,27,68,35,84}3{15,20,21,25,35,27,47,68,84}
④{15,20,21,25,27,35,47,68,84}则所采用的排序方法是oA、快速排序B、希尔排序C、归并排序D、选择排序
13.表达式a*b+c-d的后缀表示式是oa.abcd—*+;b.abc+*d-;c.abc*+d1;d.一*a+bcd;
14.在双向循环链表中的结点P之后插入结点S的操作是a.p-next=s;s-prior=p;p-next-prior=s;s-next=p-next;b.p-next=s;p-next-prior=s;s-prior=p;s-next=p-next;c.s-prior=p;s-next=p-next;p-next=s;p-next-prior=s;d.s-prior=p;s-next=p-next;p-next-prior=s;p-next=s;
15.如下图所示循环队列，其中的数据元素个数是b.Q.rear-Q.front+m%mc.Q.rear-Q.frontQ.reard.Q.rear-Q.front+1e.Q.rear-Q.front%m
16.串是一种特殊的线性表，其特殊性体现在oa.可以顺序存储b.数据元素是一个字符c.可以链接存储d.数据元素可以是多个字符
17.数组A中，每个元素的长度是3个字节，行下标i从1到8,列下标j从1到10,从首地址SA开始连续存放在存储器内，存放该数组的单元数是oa.80b.100c.240d.
27018.已知某二叉树的先序遍历序列是abdgcefh,中序遍历序列是dgbaechf,则其后序遍历的结点访问顺序序列是Oa.bdgcefhab.gdbecfhac.bdgaechfd.gdbehfca
19.线索二叉树是一种结构a.逻辑b.逻辑和存储c.物理d.线性
20.在一个有向图中，所有顶点的入度之和等于所有顶点的出度之和的倍a.1/2b.1c.2d.
321.采用分块查找时，若线性表中共有625个元素，查找每个元素的概率相同，假设采用顺序查找来确定元素所在的块时，则每块应分为个元素的块时，查找效率最佳a.10b.25c.6d.
62522.一个栈的输入序列是12345,则栈的不可能输出序列是oa.54321b.45321c.43512d.
1234523.完全二叉树一定是满二叉树吗？oa.一定是b.不是c.不一定24线性表采用链式存储结构时其地址o.a.必须是连续的b.部分地址必须是连续的c.一定是不连续的d.连续不连续都可以
25.具有线性结构的数据结构是oa.树b.图C.广义表d.栈
26.下图为顺序队列的初始情况，设a,b,c相继出队列，e,f相继入队列，则指针Q.front和列rear分别为Oa.2,5b.3,5c.3,6d.4,6
二、填空题
1.设n行n列的下三角阵A已经压缩存储到一维数组S[
0.•里户-1]中，若按行序为主序存储，则对应的在S中的存储位置是O
2.广义表a,b,c,d的长度是,深度是o
3.深度为k的完全二叉树至少有个结点，至多有个结点，若按自上而下，从左到右的次序给结点编号从1开始，则编号最小的叶子结点的编号是o
4.根据有向图的宽度优先遍历算法，对下图2所示有向图从顶点vl出发进行搜索，所得到的顶点遍历序列是O图
25.有一个有序表为｛1,3,9,12,32,41,45,62,75,77,82,95,100,当二分查找值为82的元素时，需要经过次比较就找到
6.是数据的最小单位7在双向链表中，每个结点有两个指针域，一个是指向，另一个指向o.
8.设栈ST用顺序存储结构表示，则栈ST为空的条件是o
9.两个串相等的充分必要条件是和对应位置上的字符相等
10.对于深度为h的二叉树至多有个结点
11.将一个A
[15]
[15]的对称矩阵压缩存储到一个一维数组中，该数组的长度至少为o
三、算法应用题
1.数据集｛4,5,6,7,10,12,18｝为结点权值构造Huffman树，请给出构造所得的Huffman树，并求其带权路径长度
2.假设一棵二叉树的先序序列是EBADCFHGIKJ,中序序列是ABCDEFGHIJK请画出该二叉树
3.已知一颗二叉排序树如下图所示，若依次删除
93、
19、
87、48结点，试分别画出每删除一个结点后得到的二叉排序树
4.已知关键字序列{19,01,23,14,55,20,84,27,68,11,10,77},采用哈希函数Hkey=key%13,和2开放地址法的线性探测再散列方法解决冲突，已知其装填因子=—,试对该关键字序列构造哈希表，并3求其查找成功时的平均查找长度
5.画出和下列已知序列对应的森林F:森林的先序遍历序列是ABCDEFGHIJKL；森林的中序遍历序列是CBEFDGAJIKLHo
6.假设用于通讯的电文仅由8个字母组成，字母在电文中出现的频率分别为
0.07,
0.19,
0.02,
0.06,
0.32,
0.03,
0.21,
0.10o请给这8个字母设计哈夫曼编码
7.对下图所示的无向带权图，
①给出其邻接矩阵，并按Prim算法求其最小生成树；
②给出其邻接表，并按Kruskal算法求其最小生成树
8.我们已经知道对长度为n的记录序列进行快速排序时，所需进行的比较次数依赖于这n个元素的初始排列试问
①n=7时在最好情况下需进行多少次比较请说明理由
②对n=7给出一个最好情况的初始排列实例
9.下列算法为斐波那契查找算法int FibSearchSqList r,KeyType k{j=l；while fibjn+l j=j+l;mid=n-fibj-l+l;//若fibj=n+1,则mid=fibjT fl=fib j-2;f2=fib j-3;found=false;whilemid!=0!found switchcasek==r[mid],key:found=true;break;case kr[mid[.key:if!f2mid=O;else{mid=mid-f2;t=fl-f2;fl=f2;break;f2-t;}case kr[mid].key:if f1=1mid=0;else{mid=mid+f2;fl=fl-f2;f2=f2-f1;}break;if foundreturn mid;else return0;}//FibSearch其中fibi为斐波那契序列试画出对长度为20的有序表进行斐波那契查找的判定树，并求其等概率时查找成功的平均查找长度
10.对下图所示的A0E网络，计算各活动的最早开始时间e i和最迟开始时间1D,各事件的最早发生时间ve⑴和vl（i）；并列出各条关键路径
四、算法设计题
1.设线性表4=（卬,电，・・・，〃）5=（4/2，・・・,久），试写一按下列规则和并45为线性表的算法，即使得=也鬣，粼+1，…，2）当机时；或者=（6，々，/也，…,〃，小……，々川）当根上〃时C线性表A,3和C均以单链表作存储结构,且C表利用A表和表中的结点空间构成B注意单链表的长度值掰和〃均未显示存储
2.试完成二叉树按层次（同一层自左至右）遍历的算法
3.试完成求无向图的连同分量个数的算法
4.试写一算法将两个递增有序的带头结点的单链表合并为一个非递增有序的带头结点的单链表（利用原表结点空间）
5.设顺序表va中的数据元素递增有序（数据元素的类型是整型）试写一算法，将x插入到顺序表的适当位置上，以保持该表的有序性
五、简答题
1.画出广义表a,b,c,,d,e,f的存储图链式
2.分别画出具有3个结点的树和具有3个结点的二叉树的所有形态
六、证明题
1.试证明若借助栈由输入序列1,2,…,〃得到的输出序列为小，〃2,・・・,〃〃它是输入序列的一个排列，则在输出序列中不可能出现这样的情况存在使得i Yj Yk PjY PkY Pi
2.试证明在一棵满k叉树上的叶子结点数〃和非叶子结点数%之间满足一下关系%=左。
个人认证
优秀文档
获得点赞 0
