教育材料《数据结构》-习题库

PAGE18数据结构（Java语言描述）PAGE7习题一1．简述下列术语：数据、结点、逻辑结构、存储结构、数据处理、数据结构和数据类型。2．试根据以下信息：校友姓名、性别、出生年月、毕业时间、所学专业、现在工作单位、职称、职务、电话等，为校友录构造一种适当的数据结构（作图示意），并定义必要的运算和用文字叙述相应的算法思想。3．什么是算法？算法的主要特点是什么？4．如何评价一个算法？习题二1．什么是顺序存储结构？什么是链式存储结构？2．线性表的顺序存储结构和链式存储结构各有什么特点？3．设线性表中数据元素的总数基本不变，并很少进行插入或删除工作，若要以最快的速度存取线性表中的数据元素，应选择线性表的何种存储结构？为什么?4．线性表的主要操作有哪些？5．简述数组与顺序存储结构线性表的区别和联系。6．顺序表和链表在进行插入操作时，有什么不同？7．画出下列数据结构的图示：=1\*GB3①顺序表=2\*GB3②单链表=3\*GB3③双链表=4\*GB3④循环链表8．试给出求顺序表长度的算法。9．给出删除单链表中值为k的结点的前驱结点的算法。10．试给出依次输出单链表中所有数据元素的算法。11．试给出求单链表长度的算法。12．若多项式A=a1x+a2x2+…+an-1xn-1+anxn,B=b1x+b2x2+…+bn-1xn-1+bnxn以单链表存储,试给出多项式相减A-B的算法。13．请生成多项式A=5+9x+11x6+14x11-21x15+18x18和B=8x+12x3+2x6-14x11+12x15，并输出A+B的结果。习题三1．简述栈和线性表的区别和联系。2．何为栈和队列？简述两者的区别和联系。3．若依次读入数据元素序列{a,b,c,d}进栈，进栈过程中允许出栈，试写出各种可能的出栈元素序列。4．将下列各算术运算式表示成波兰式和逆波兰式：(A*(B+C)+D)*E-F*GA*(B-D)+H/(D+E)-S/N*T(A-C)*(B+D)+(E-F)/(G+H)5．写出算术运算式3+4/25*8-6的操作数栈和运算符栈的变化情况。6．若堆栈采用链式存储结构，初始时为空，试画出a,b,c,d四个元素依次进栈后栈的状态，然后再画出此时的栈顶元素出栈后的状态。7．试写出函数Fibonacci数列的递归算法和非递归算法。F1=0(n=1)F2=1，(n=2)┆Fn=Fn-1+Fn-2(n>2)8．在一个类型为staticlist的一维数组A[0…m-1]存储空间建立两个链接堆栈，其中前两个单元的next域用来存储两个栈顶指针，从第3个单元起作为空闲存储单元空间提供给两个栈共同使用。试编写一个算法把从键盘上输入的n个整型数（n<=m-2，m>2）按照下列条件进栈：（1）若输入的数小于100，则进第一个栈。（2）若输入的数大于等于100，则进第二个栈。9．试证明：若借助栈由输入序列1，2，3，…，n得到输出序列P1，P2，P3，…，Pn（它是输入序列的一个排列），则在输出序列中不可能出现这样的情况：存在i<j<k，使得Pj<Pk<Pi。10．对于一个具有m个单元的循环队列，写出求队列中元素个数的公式。11．简述设计一个结点值为整数的循环队列的构思，并给出在队列中插入或删除一个结点的算法。12．有一个循环队列q(n)，进队和退队指针分别为r和f；有一个有序线性表A[M]，请编一个把循环队列中的数据逐个出队并同时插入到线性表中的算法。若线性表满则停止退队，并保证线性表的有序性。13．设有栈stack，栈指针top=n-1，n>0；有一个队列Q(m)，其中进队指针r，试编写一个从栈stack中逐个出栈并同时将出栈的元素进队的算法。习题四1．简述空串与空格串、串变量与串常量、主串与子串、串名与串值每对术语的区别？2．两个字符串相等的充分条件是什么？3．串有哪几种存储结构？4．已知两个串：s1=”fgcdbcabcadr”,s2=”abc”,试求两个串的长度，判断串s2是否是串s1的子串，并指出串s2在串s1中的位置。5．已知：s1=〃I’mastudent〃，s2=〃student〃，s3=〃teacher〃，试求下列各运算的结果：s1.indexOf(s2);s1.indexOf(s3);s2.charat(3);s3.substring(2,5);6.给本章中定义的静态存储结构字符串类StatStr添加一个print()方法，打印出该字符串。7．给本章中定义的动态态存储结构字符串类LinkStr添加一个print()方法，打印出该字符串。8．设计一个类来测试本章中定义的StatStr类的求字符串长度和求子串的方法是否正确。习题五1．按行优先存储方式，写出三维数组A[3][2][4]在内存中的排列顺序及地址计算公式（假设每个数组元素占用L个字节的内存单元，a[0][0][0]的内存地址为Loc(a[0][0][0])。2．按列优先存储方式，写出三维数组A[3][2][4]在内存中的排列顺序及地址计算公式（假设每个数组元素占用L个字节的内存单元，a[0][0][0]的内存地址为Loc(a[0][0][0])。3．试写一个算法，查找十字链表中某一非零元素x。4．给定矩阵A如下，写出它的三元组表和十字链表。5．试编写一个以三元组形式输出用十字链表表示的稀疏矩阵中非零元素及其下标的算法。6．给定一个稀疏矩阵如下：用快速转置实现该稀疏矩阵的转置，写出转置前后的三元组表及开始的每一列第一个非零元的位置pot[col]的值。7．广义表是线性结构还是非线性结构?为什么?8．求下列广义表的运算的结果。（1）head((p,h,w))（2）tail((b,k,p,h))（3）head(((a,b),(c,d)))（4）tail(((b),(c,d)))（5）head(tail(((a,b),(c,d))))（6）tail(head(((a,b),(c,d))))（7）head(tail(head(((a,d),(c,d)))))（8）tail(head(tail(((a,b),(c,d)))))9．画出下列广义表的图形表示。（1）A(b,(A,a,C(A)),C(A))（2）D(A(),B(e),C(a,L(b,c,d)))10．画出第9题的广义表的单链表表示法和双链表表示法。习题六1．已知如图6-24所示的树，请回答下列问题：（1）哪些结点是叶子结点？（2）树的度是多少？（3）找出所有层次为4的结点；（4）画出该树的不定长结点表示。2．给定结点A、B、C，可以构成多少不同形状的树？多少不同形状的二叉树？3．请将图6-24所示的树转换成一棵二叉树，并分别按先序、中序、后序三种方式遍历之。4．若一棵二叉树的先序遍历和中序遍历的结果分别为ABDEHCFGI和DBEHAFCIG，试画出该树。5．写出按层次遍历二叉树的方法，同一层次按自左到右的次序。6．写出统计一棵二叉树中叶子结点个数的算法。7．写出计算一棵二叉树深度的算法。图6-24树8．一份成绩单如下，将其构造成一棵二叉排序树，并写出其中序遍历的结果。学号123456789成绩60.547.080.376.090.653.283.393.075.59．给定一组权值：3，3，7，7，11，13，17，试构造一棵哈夫曼树，并计算出带权路径长度。10．给定字符串：ABCDBDCBDBACB，请按此信息构造哈夫曼树，求出每一字符的哈夫曼编码。习题七1．对n个顶点的无向图G，采用邻接矩阵表示，如何判别下列有关问题：（1）图中有多少条边?（2）任意两个顶点i和j是否有边相连?（3）任意一个顶点的度是多少?2．图7-27所示的有向图是强连通的吗?请列出所有简单路径，并给出其邻接矩阵、邻接表和逆邻接表。3．按顺序输入顶点对：(1，2)，(1，6)，(2，6)，(1，4)，(6，4)，(1，3)，(3，4)，(6，5)，(4，5)，(1，5)，(3，5)，根据第7.2.2节中的算法CREATADJLIST画出相应的邻接表。并写出在该邻接表上，从顶点4开始搜索所得的DFS和BFS序列。4．对图7-28所示的有向图，画出从顶点vl开始的遍历所得到的DFS和BFS森林。5．对图7-29所示的连通网络，请分别用PRIM算法和KRUSKAL算法构造该网络的最小生成树。图7-27有向图图7-28有向图图7-29连通网络图习题八1．设有一组关键字序列{12，7，2，30，8，28，4，10，5，60，25，9，1，56，34，78}，当用折半查找算法查找关键字7，5，67时，其比较次数分别是多少？2．用C语言改写折半查找过程，使其成为递归过程并上机验证。3．设单链表的结点是按关键字从小到大排列的，试写出对此链表的查找算法，并说明是否可以采用折半查找。4．已知关键字集合{2，3，15，8，1，25，16，35，9，22，30，39，18，33，27，26}，按平均查找长度ASL最小的原则，画出分块存储示意图。5．什么是哈希表、哈希函数？哈希法中为什么会出现冲突？6．删除散列表中某结点，应如何操作？习题九1．请编写一个以单链表为存储结构的插入排序算法。2．已知关键字序列为{29，75，17，90，111，13}，请分别用插入排序、选择排序、希尔排序、冒泡排序对其进行排序，并写出排序过程。3．请编写一个以单链表为存储结构的选择排序算法。4．写出长度分别为n1，n2，n3的有序表的3路归并排序算法。5．已知关键字序列为{10，2，12，33，4，25，0，7，17，9，19}，