《吕梁学院数据结构习题解析》由会员分享，可在线阅读，更多相关《吕梁学院数据结构习题解析（17页珍藏版）》请在金锄头文库上搜索。
1、本文格式为Word版，下载可任意编辑吕梁学院数据结构习题解析 第2片面 习题解析 第1章 绪论 1.1 选择题 1. 算法的时间繁杂度取决于（ c ） A）问题的规模 B） 待处理数据的初态 C） A和B 2.计算机算法指的是解决问题的步骤序列，它务必具备（ B ） 这三个特性。 A）可执行性、可移植性、可扩展性B） 可执行性、确定性、有穷性C） 确定性、有穷性、稳定性D） 易读性、稳定性、安好性 5从规律上可以把数据布局分为（ C ）两大类。 A）动态布局、静态布局 B）依次布局、链式布局 C）线性布局、非线性布局 D）初等布局、构造型布局 6在下面的程序段中，对x的赋值的语句频度为（ C
2、） for(i=0;i=1;i-) for(j=1;jAj+1) Aj与Aj+1对换； A. O（n） B） O(nlog2n) C） O(n3) D） O(n2) 1.2 填空题 2. 对于给定的n个元素,可以构造出的规律布局有集合、线性布局、树形布局、图状布局或网状布局四种。 4数据布局中评价算法的两个重要指标是：算法的时间繁杂度和空间繁杂度。 5. 数据布局是研讨数据的_规律布局_和_物理布局_以及它们之间的相互关系，并对与这种布局定义相应的_操作（运算）_设计出相应的_算法_。 6一个算法具有5个特性：有穷性_、确定性、可行性，有零个或多个输入、有一个或多个输出。 9已知如下程序段 f
3、or(i=n;i0;i-) 语句1 x=x+1; 语句2 for(j=n;j=i;j-) 语句3 y=y+1; 语句4 语句1执行的频度为_n+1_;语句2执行的频度为_n_；语句3执行的频度为_n(n+3)/2_；语句4执行的频度为_n(n+1)/2_。 10在下面的程序段中，对的赋值语句的频度为_（表示为n的函数） for(i=0;in;i+) for(j=0;ji;j+) for(k=0;kj;k+) =+delta;【答案】1+（1+2）+（1+2+3）+（1+2+n）=n(n+1)(n+2)/6 ， O(n3) 11.下面程序段中带下划线的语句的执行次数的数量级是_。 i=1; wh
4、ile(i=i;j-) s; 【答案】(n+3)(n-2)/2 13. 下面程序段的时间繁杂度为_。(n1) sum=1; for (i=0;sumprior=q; q-next=p; p-prior-next=q; q-prior=p-prior; B） q-prior=p-prior; p-prior-next=q; q-next=p; p-prior=q-next; C） q-next=p; p-next=q; p-prior-next=q; q-next=p; D） p-prior-next=q; q-next=p; q-prior=p-prior; p-prior=q; 4在一个具有
5、n个结点的有序单链表中插入一个新结点并依旧保持有序的时间繁杂度是（C ） A）O(nlog2n） B） O(1） C） O(n） D） O(n2） 5 在一个以 h 为头指针的单循环链中，p 指针指向链尾结点的条件是（ B ） A）p-next=NULL B） p-next=h C）p-next-next=h D） p-data=-1 6对于一个具有n个结点的线性表，建立其单链表的时间繁杂度是（ A ） A）O(n) B） O(1) C）O(nlog2n) D） O(n2) 8在双向链表存储布局中，删除p所指的结点时须修改指针（ A ） A）p-prior-next=p-next p-next
6、-prior=p-prior;B）p-prior=p-prior-prior p-prior-next=p; C）p-next-prior=p p-next=p-next-nextD）p-next=p-prior-prior p-prior=p-next-next; 9线性表采用链式存储时，其元素地址（D ） A）务必是连续的 B）确定是不连续的 C）片面地址是连续的 D）连续与否均可 2 数据布局上机测验与习题解析 2.2 填空题 1线性表L=（a1，a2，an）用数组表示，假定删除表中任一元素的概率一致，那么删除一个元素平均需要移动元素的个数是_。【答案】（n-1）/2 2在单链表中设置头
7、结点的作用是_【答案】主要是使插入和删除等操作统一，在第一个元素之前插入元素和删除第一个结点不必另作判断。另外，不管链表是否为空，链表头指针不变。 3线性表的依次存储是通过_来回响元素之间的规律关系，而链式存储布局是通过_来回响元素之间的规律关系。【答案】（1）数据元素的前后依次 （2）元素中的指针 4当对一个线性表经常举行的是存取操作，而很少举行插入和删除操作时，那么采用_存储布局最节省时间，相反当经常举行插入和删除操作时，那么采用_存储布局最节省时间。【答案】（1）依次 （2）链式 5对于一个具有n个结点的单链表，在已知的结点*p后插入一个新结点的时间繁杂度为_，在给定值为x的结点后插入一
8、个新结点的时间繁杂度为_。【答案】（1）O(1) （2）O(n) 7. 对于双向链表，在两个结点之间插入一个新结点需修改的指针共_4_个，单链表为_2_个。 8. 循环单链表的最大优点是_。【答案】从任一结点启程都可访问到链表中每一个元素。 9若要在一个不带头结点的单链表的首结点*p结点之前插入一个*s结点时，可执行以下操作： s-next=_; p-next=s; t=p-data; p-data= _; s-data=_; 【答案】（1）p-next （2）s-data （3） t 10某线性表采用依次存储布局，每个元素占据4个存储单元，首地址为100，那么下标为11的（第12个）元素的存
9、储地址为144 11带头结点的双循环链表L中只有一个元素结点的条件是_。【答案】L-next-next=L 2.3 判断题 1取线性表的第i个元素的时间同i的大小有关（ ）【答案】 2线性表的特点是每个元素都有一个前驱和一个后继（ ）【答案】 3 依次存储方式的优点是存储密度大，且插入、删除运算效率高（ ）【答案】 4线性表采用链表存储时，结点的存储空间可以是不连续的（ ）【答案】 5链表是采用链式存储布局的线性表，举行插入、删除操作时，在链表中比在依次存储布局中效率高（ ）【答案】 6依次存储方式只能用于存储线性布局（ ）【答案】解析】线性布局、树型布局和图状布局均可用依次存储表示。 9依次
10、存储布局的主要缺点是不利于插入或删除操作（ ）【答案】 10依次存储方式插入和删除时效率太低，因此它不如链式存储方式好（ ）【答案】 2.4 程序设计题 1设依次表va中的数据元素递增有序。试设计一个算法，将x插入到依次表的适当位置上，以保持该表的有序性。 void Insert_SqList(SqList va,int x)/*把x插入递增有序表va中*/ int i; if(va.length MAXSIZE) return; for(i=va.length-1;va.elemixi-) va.elemi+1=va.elemi; va.elemi+1=x; va.length+; /*In
11、sert_SqList*/ 2设 A=（a1，a2，am） 和 B=（b1，b2，bn）均为依次表，试设计一个对比A，B大小的算法（请留神：在算法中，不要破坏原表A和B）。 【算法分析】对比依次表A和B，并用返回值表示结果，值为1，表示AB；值为-1，表示AB.elemi?1:-1; if(A.length=B.length) return 0; return A.lengthB.length?1:-1; /*当两个依次表可以彼此对比的片面完全一致时，哪个较长，哪个就较大*/ /*ListComp */ 3已知指针 ha和 hb分别指向两个单链表的头结点，并且已知两个链表的长度分别为m和n。试
12、设计一个算法将这两个链表连接在一起（即令其中一个表的首元结点连在另一个表的结果一个结点之后），假设指针hc指向连接后的链表的头结点，并要求算法以尽可能短的时间完成连接运算。 【算法分析】1）单链表ha的头结点作为连接后的链表的头结点，即hc=ha； 2）查找单链表ha的结果一个结点，由指针p指向，即p-next=NULL； 3）将单链表hb的首元结点（非头结点）连接在p之后，即p-next=hb-next； 4）回收单链表hb的头结点空间 【算法源代码】void ListConcat(LinkList ha,LinkList hb,LinkList *hc)/*把链表hb接在ha后面形成链表h
13、c*/ *hc=ha; p=ha;/*由指针p指向ha的尾元结点*/ p=p-next; p-next=hb-next; 第2片面 习题解析 3 free(hb); /*ListConcat */ 4试设计一个算法，在无头结点的动态单链表上实现线性表操作INSERT（L，i，b），并和在带头结点的动态单链表上实现一致操作的算法举行对比。【算法分析】1）生成新结点存放元素b，由指针new指向； 2）将new插入在单链表的第i个元素的位置上：若i=1，new插在链表首部；否那么查找第i-1个结点，由指针p指向，然后将new插在p之后。【算法源代码】void Insert(LinkList *L,int i,int b) LinkList new; new=(LinkList*)malloc(sizeof(LNode); new-data=b; if(i=1)
