数据结构习题(1).docx

《数据结构习题(1).docx》由会员分享，可在线阅读，更多相关《数据结构习题(1).docx（5页珍藏版）》请在第一文库网上搜索。

1、第一章绪论讨论题：1 .常用的存储表示方法有哪几种？2 .算法的时间复杂度仅与问题的规模相关吗？思考题：设n为正整数。试确定下列各程序段中前置以记号的语句的频度:(1)1=1;k=0;whi1e(i=-1)k+=10*i;1+；(2) i=1;k=0;dok+=10*i;i+；whi1e(i=-1);(3) i=1;k=0;whi1e(i=-1)i+；k+=10*i;(4) k=0;for(i=1;i=n;i+)for(j=i;j=n;j+)k+;(5) for(i=1;i=n;i+)for(j=1;j=i;j+)for(k=1;k=j;k+)x+=de1ta;(6) i=1;j=0;whi1

2、e(i+jj)j+；e1sei+;(7) x=n;/n是不小于1的常数y=0;whi1e(x=(y+1)*(y+1)y+;)(8) x=91;y=100;whi1e(y0)if(x100)x-=10;y-;e1sex+;第二章线性表讨论题：1 .为什么在单循环链表中设置尾指针比设置头指针更好？2 .何时选用顺序表、何时选用链表作为线性表的存储结构为宜？思考题：1 .指出以下算法中的错误和低效之处，并把它改写为一个既正确又高效的算法。StatusDe1eteK(Sq1ist&a,intI,intk)/本过程从顺序存储结构的线性表a中删除第I个元素起的k个元素。e1sefor(count=1;co

3、untk;count+)/删除一个元素rreturnOK;/De1eteK2 .假设某个单向循环链表的长度大于1,且表中既无头结点也无头指针。已知S为指向链表中某个结点指针，试编写算法在链表中删除指针s所指结点的前驱结点。第三章栈和队列讨论题：1 .若以1234作为双端队列的输入序列，试分别求出满足以下条件的输出序列：D能由输入受限的双端队列得到，但不能由输出受限的双端队列得到的输出序列；2)能由输出受限的双端队列得到，但不能由输入受限的双端队列得到的输出序列；3)既不能由输入受限的双端队列得到，也不能由输出受限的双端队列得到的输出序列。2 .进栈序列为123,则可能得到的出栈序列是什么？3

4、.如果进栈序列为123456,则能否得到435612和135426的出栈序列，并请说明为什么不能得到。思考题：1.设两个栈共享空间vOm-1,两栈的栈底分别设在向量的两端，且每个元素占一个分量。试设计这两个栈的插入和删除算法。简述以下算法的功能。(1) voidDemo1(SeqStack*S)intI;arr64;n=0;whi1e(StackEmpty(S)arrn+=Pop(S);for(1=0,Kn;I+)Push(S,arrI);/Demo1(2) voidDemo3(CirQueue*Q)/设DataTyPe为int型intx;SeqStackS;InitStack(&S);whi

5、1e(!QueueEmpty(Q)x=DeQueue(Q);Push(&S,x);whi1e(!StackEmpty(&s)x=Pop(&S);EnQueue(Q,x);/Demo3第四章串思考题：串与普通的线性表的区别？第五章数组和广义表讨论题：1 .疏矩阵的稀疏程度达到多少时，采用三元组存储的空间节省于数组存储？思考题：2 .设有三对角矩阵An*n,将其三条对角线上的元素逐行地存储到向量B03n-3中，使得Bk=aij,求：1)用I,j表示k的下标变换公式。2)用k表示1j的下标变换公式3 .利用广义表的GetHead和GetTai1操作写出函数表达式，把原子banana分别从下列广义表中

6、分离出来。11=(app1e,pear,banana,orange);12=(app1e),pear),banana),orange);13=(app1e,(pear,(banana),orange);第六章树和二叉树讨论题：1 .试分别画出具有3个结点的树和3个结点的二叉树的所有不同形态。2 .已知在一棵含有n个结点的树中，只有度为k的分支结点和度为O的叶子结点。试求该树含有的叶子结点的数目。思考题：1试分别推导含个结点和含n个叶子结点的完全三叉树的深度Ho2.找出所有满足下列条件的二叉树：D它们在先序遍历和中序遍历时，得到的结点访问序列相同；2）它们在后序遍历和中序遍历时，得到的结点访问序

7、列相同；3）它们在先序遍历和后序遍历时，得到的结点访问序列相同；_假设一棵二叉树的前序序列为Ebadcfhgikj和中序序列为abcdefghijko请画出该树。第七章图讨论题：1 .已知以二维数组表示的图的邻接矩阵。如何画出自某个顶点出发进行遍历所得的深度优先生成树和广度优先生成树。2 .如何画出有向无环图中全部可能的拓扑有序序列。思考题：采用邻接表存储结构，编写一个判别无向图中任意给定的两个顶点之间是否存在一条长度为k的简单路径的算法。第九章查找讨论题：1.若对大小均为的有序的顺序表和无序的顺序表分别进行顺序查找，试在下列三种情况下分别讨论两者在等概时的平均查找长度是否相同？D查找不成功，

8、即表中没有关键字等于给定值K的记录；2）查找成功，且表中只有一个关键字等于给定值K的记录；3）查找成功，且表中有若干个关键字等于给定值K的记录，一次查找要求找出所有记录。此时的平均查找长度应考虑找到所有记录时所用的比较次数。思考题：1 .在一棵空的二叉查找树中依次插入关键字序列为20、30、8、12、34、5、60、5、1,29,请画出所得到的二叉查找树。2 .画出对长度为18的有序的顺序表进行二分查找的判定树，并指出在等概率时查找成功的平均查找长度，以及查找失败时所需的最多的关键字比较次数。3 .画出对长度为10的有序表进行折半查找的判定树，并求其等概时查找成功的平均查找长度。4 .已知如下

9、所示长度为12的表（Jan,Feb,Mar,Apr,May,June,Ju1y,Aug,Sep,Oct,Nov,Dec）试按表中元素的顺序依次插入一棵初始为空的二叉排序树，请画出插入完成之后的平衡二叉排序树，并求其在等概率的情况下查找成功的平均查找长度。第十章内部排序讨论题:1 .以关键字序列（265,301,751,129,937,863,742,694,076,438）为例,分别写出执行以下排序算法的各趟排序结束时，关键字序列的状态。1）直接插入排序2）希尔排序3）冒泡排序4）快速排序5）直接选择排序6）堆排序7）归并排序8）基数排序上述方法中，哪些是稳定的排序?哪些是非稳定的排序?对不稳定的排序试举出一个不稳定的实例。思考题：以单链表作为存储结构实现直接插入排序算法。第十二章文件讨论题:1什么是索引顺序文件？2 .分析ISAM文件（INDEXEDSEQUENTIA1ACCESSMETHORD）和VSAM文件（VIRTUA1STORAGEACCESSMETHORD）的应用场合、优缺点等。3 .简单比较文件的多重表和倒排表组织方式各自特点。思考题：简单比较文件的多重表和倒排表组织方式各自特点。