信息技术2015数据结构重修辅导资料

《信息技术2015数据结构重修辅导资料》由会员分享，可在线阅读，更多相关《信息技术2015数据结构重修辅导资料（23页珍藏版）》请在金锄头文库上搜索。

1、12120(2 )2 (2)222 (2)224 (2)2 2 2(2 )2(1)2kKKKKKKKKkkTTTTTkk L信息技术信息技术 2014 数据结构重修辅导资料数据结构重修辅导资料第一章第一章 绪论绪论第一题：选择题 1、求解下面程序段的时间复杂度。 for(i=0;i1y=0;while(x=(y+1)(y+1)y+; 【分析分析】 这里 y+;是循环体，被反复执行，只要计算出它的执行频度即可。【答案答案】O时间复杂度近似为（n）3、一个算法所需时间由下述归方程表示，试求出该算法的时间复杂性的级别（或阶）以大“O”表示。 11 ( )2 ( )12n T nnTnn 其中：n 是

2、问题的规模，为简单起见，设 n 是 2 的整数幂。 【分析分析】设 n=2k，即 k=log2n则有：2(1)111ynynynyn 所以有 T(n)=n(log2n + 1)，该算法的时间复杂度为 O(nlog2n)。 【答案答案】O(nlog2n) 4、下述函数中渐进时间复杂度最小的是：2log 2222 222. 1( )log1000log2( )1000logC3( )1000logD4( )2 log1000lognATnnnnTnnnTnnnTnnnn 【分析分析】A 和 D 比较，用 D 项减去 A 项得到 nlog2n-2000log2n，显然 D 的值大于 A 的 B 和

3、C 比较，n2显然要小于 nlog2n 值，故 B 的值大于 C 的值。 那么 B 和 D 这两个值中哪个更大呢？当 n 趋近于很大值时 log2n 值要远大于 n2， 所以这道题最小的是 A，最大的是 B。 【答案答案】A 5、计算下列程序中 x=x+1 的语句频度for(i=1;inext 的值要修改为再下一个结点的物理地址，m 结点的后继的后继结点的地址为 p-next- next 【答案】此处应该填上 p-next=p-next-next。 2、顺序表中逻辑上相邻的元素，物理位置_紧邻，单链表中逻辑上相邻的元素，物理位 置_紧邻。 【分析分析】顺序表的特点是逻辑上相邻的元素，物理位置也

4、一定紧邻单链表则不同了，逻辑上相邻的元素，物理位置不一定紧邻。 【答案答案】一定或者也不一定 3、在一个单链表中，已知*q 结点是*p 结点的前驱结点，若在*q 和*p 之间插入*s 结点， 则必须执行_。pm图 2-1pm图 2-2【分析分析】要想在*q 和*p 之间插入一个新的结点，则就是要在建立如下图虚线所示的新的逻 辑关系。虚线代表的含义是*q 指针所指向的结点后继应该修改为*s 指针所指向的新结点，虚线 代表的含义是*p 结点的直接前驱要修改为*s 所指向的结点，c 语言语句分别为： q-next=s s-next=p 还有一点需要注意的是，如果没有 p 指针的话，想在 q 指针后添

5、加新的结点，这两个虚线 所代表的箭头就要有逻辑顺序了，否则就会断掉原来结点的链接。这时应当写为： s-next=q=next; q-next=s; 【答案答案】q-next=s s-next=p 4、表长为 n 的顺序存储的线性表，当在任何位置上后插入或删除一个元素的概率相等时， 插入一个元素所需移动元素的平均个数为_，删除一个元素需要移动元素的平均个数 为_。 【分析分析】在任何位置的概率相等，则要插入一个元素时，n 个结点共有 n+1 个位置，第一 个位置为第一个结点前面，第二个位置为第一个结点后面，故共有 n+1 个位置，每个位置 被选中的概率相等，则每个位置被选中的概率为 1/(n+1

6、)，如果要插入在第一个位置，则要 向后移动 n 个结点，插入第二个位置要移动 n-1 个结点，最后一个位置时，则不需要移动 结点，故共要移动 1+2+3+.+n 个结点，总共为 n(n+1)/2 个结点，则平均移动个数为：11 122nnn n 删除一个元素时，n 个结点共有 n 个位置可以删除，每个位置被选中的概率相等，则每个 位置被选中的概率为 1/n，当要删除第一个位置的元素时，需要向前移动 n-1 个元素，第二qps图 2-3qps图 2-4个位置的元素，需要向前移动 n-2 个元素，最后一个结点时要移动 0 个元素，故共需要移 动 1+2+3+.+n-1=(n-1)n/2，则平均需移

7、动个数为：111 22nnn n 【答案答案】第一个空填 n/2，第二个空填（n-1）/2。 选择题： 1、线性表的顺序存储结构是一种_的存储结构，线性表的链式存储结构是一种 _的存储结构。 A随机存取 B顺序存取 C索引存取 D散列存取 2、对于一个线性，既要求能够进行较快的插入和删除，又要求存储结构能够反映数据 元素之间的逻辑关系，则应该选择_。 A顺序存储方式 B链式存储方式 C散列存储方式 D索引存储方式 3、已知 L 是一个不带头结点的单链表，p 指向其中的一个结点，选择合适的语句实现 在 p 结点的后面插入 s 结点的操作_。 Ap-next=s ; s-next=p-next ;

8、 Bs-next=p-next ; p-next=s ;Cp-next=s ; s-next=p ; Ds-next=p ; p-next=s ; 4、单链表中各结点之间的地址_。 A必须连续 B部分地址必须连续 C不连续 D连续与否都可以 5、在一个长度为 n 的顺序表中向第 i 个元素（0next=p-next; p-next=s; Bp-next=s; s-next=p-next; Cs-next=p; p-next=s-next; Dp-next=s; s-next=p; 参考答案：1、A B 2、B 3、B 4、D 5、B 6、A 7、A 二、 填空题 1、在线性表的顺序存储方式中，

9、元素之间的逻辑关系是通过_来体现的；在链式 存储方式，元素之间的逻辑关系是通过_体现的。 2、对于一个长度为 n 的单链表，在已知的 p 结点后面插入一个新结点的时间复杂度为 _，在 p 结点之前插入一个新结点的时间复杂度为_，在给定值为 e 的结点之 后插入一个新结点的时间复杂度为_。 3、在双向链表中，每个结点包含两个指针域，一个指向_结点，另一个指向_ 结点。 4、对于循环链表来讲，逐个访问各个结点的结束判断条件是（设 P 为指向结点的指 针，L 为链表的头指针）则_。 5、若频繁地对线性表进行插入与删除操作，该线性表应采用_存储结构。 6、在非空线性表中除第一个元素外，集合中每个数据元

10、素只有一个_；除最后 一个元素之外，集合中每个数据元素均只有一个_。 7、线性表中的每个结点最多有_前驱和_后继。 8、_链表从任何一个结点出发，都能访问到所有结点。9、链式存储结构中的结点包含_域，_域。 10、在双向链表中，每个结点含有两个指针域，一个指向_结点，另一个指向 _结点。 11、某带头结点的单链表的头指针 head，判定该单链表非空的条件_。 参考答案： 1、物理顺序 指针 2、O(1) O(n) O(n) 3、前驱 后继 4、p-next= =L 5、链表 6、直接前驱，直接后继 7、1 个直接，1 个直接 8、循环 9、指针，数据 10、前驱，后继 11、head-next

11、!=Null 三、判断题 1、线性表的逻辑顺序与物理顺序总是一致的。( ) 2、线性表的顺序存储表示优于链式存储表示。( ) 3、线性表若采用链式存储表示时所有结点之间的存储单元地址可连续可不连续。( ) 4、二维数组是其数组元素为线性表的线性表。( ) 5、假定有两个用单链有序表表示的集合，则这两个集合的交运算可得到一个新的集 合单链表，其长度小于等于参加运算的任意一个集合单链表的长度。( ) 6、假定有两个用单链有序表表示的集合，则这两个集合的差运算可得到一个新的集 合单链表，其长度小于参加运算的任意一个集合单链表的长度。( ) 7、线性表中的每个结点最多只有一个前驱和一个后继。 （ ）

12、8、线性的数据结构可以顺序存储，也可以链接存储。非线性的数据结构只能链接存 储。 （ ） 9、单链表从任何一个结点出发，都能访问到所有结点 （ ） 10、线性表的顺序存储结构是通过数据元素的存储地址直接反映数据元素的逻辑关系。 （ ）参考答案：1-5 6-10 程序程序题题1、 下述算法的功能是什么? LinkList Demo(LinkList L) / L 是无头结点单链表ListNode *Q,*P;if(LL=L-next;P=L;while (P-next) P=P-next;P-next=Q; Q-next=NULL;return L;/ Demo 答：该算法的功能是，将开始结点摘

13、下链接到终端结点之后成为新的终端结点，而原来的 第二个结点成为新的开始结点，返回新链表的头指针。 2、 顺序表 L 是一个递增有序表，试写一算法，将 x 插入 L 中，并使 L 仍是一个有序表。 答： 因已知顺序表 L 是递增有序表，所以只要从顺序表终端结点（设为 i 位置元素）开 始向前寻找到第一个小于或等于 x 的元素位置 i 后插入该位置即可。在寻找过程中，由于大于 x 的元素都应放在 x 之后，所以可边寻找，边后移元素，当找到 第一个小于或等于 x 的元素位置 i 时，该位置也空出来了。算法如下：void InsertIncreaseList( Seqlist *L , Datatyp

14、e x ) int i;if ( L-length=ListSize)Error(“overflow“);for ( i=L - length ; i0 i-)L-data i =L-data i ; / 比较并移动元素L-data i =x;L - length+; 3、写一算法在单链表上实现线性表的 ListLength(L)运算。 答：由于在单链表中只给出一个头指针，所以只能用遍历的方法来数单链表中的结点个数 了。 算法如下：int ListLength ( LinkList L ) int len=0 ;ListNode *p;p=L; /设该表有头结点while ( p-next ) p=p-next;le