[2017年整理]数据结构复习题目

上传人:豆浆 文档编号:916467 上传时间:2017-05-21 格式:DOC 页数:30 大小:906.77KB
返回 下载 相关 举报
[2017年整理]数据结构复习题目_第1页
第1页 / 共30页
[2017年整理]数据结构复习题目_第2页
第2页 / 共30页
[2017年整理]数据结构复习题目_第3页
第3页 / 共30页
[2017年整理]数据结构复习题目_第4页
第4页 / 共30页
[2017年整理]数据结构复习题目_第5页
第5页 / 共30页
点击查看更多>>
资源描述

《[2017年整理]数据结构复习题目》由会员分享,可在线阅读,更多相关《[2017年整理]数据结构复习题目(30页珍藏版)》请在金锄头文库上搜索。

1、第 1 章 概论练习题一、单项选择题1在数据结构中,从逻辑上可以把数据结构分为(B )A紧凑结构和非紧凑结构 B线性结构和非线性结构C内部结构和外部结构 D动态结构和静态结构2若结点的存储地址与其关键字之间存在某种映射关系,则称这种存储结构为(D)A顺序存储结构 B链式存储结构C索引存储结构 D散列存储结构3算法分析的两个主要方面是(B )A正确性和简明性 B时间复杂性和空间复杂性C可读性和可维护性 D数据复杂性和程序复杂性4线性表采用链式存储结构时,要求内存中可用存储单元地址(A)A不一定连续的 B部分地址必须是连续的C必须是连续的 D一定是不连续的5算法指的是(C)A计算机程序 B解决问题

2、的计算方法C解决问题的有限运算序列 D排序算法二、填空题6数据结构一般包括逻辑结构 、存储结构和数据运算三个方面的内容7数据的逻辑结构可分为线性结构 、非线性结构两大类8数据的存储结构(物理结构)一般可以用顺序存储结构 、链式存储结构、索引存储结构及散列存储结构等四种存储方法表示9在选用求解一个问题的算法时,除了首先考虑算法是“正确的”之外,还主要考虑执行算法所需要的时间、执行算法所需要的存储空间及算法应易于理解、易于编程、易于调试等三点。10设有一批数据元素,为了最快地存取某元素,宜用顺序 结构存储,为了方便的插入一个元素,宜用链式结构存储三、应用题设 n 为正整数,利用大“O”记号,写出下

3、列各程序段的时间复杂度11 for (i = 1; i = (s + 1) * (s + 1)s = s + 1;分析:语句 “s = s + 1;”执行 次,故该程序段的时间复杂度为O( )n n13 x = 1;sum = 0;for (i = 0; i next = headC head next = NULL Dhead = NULL4在单循环链表中,p 指向表任一结点,判断表不是访问结束的条件是(B )Ap != NULL Bp != head Cp next != head Dp next != NULL5在一个单链表中,已知 q 指向 p 所指向结点的前趋结点,若在 p、q 所指

4、结点之间插入一个 s 所指向的新结点,则执行的操作是(A)Aq next = s; s next = p Bp next = s; s next = q C s next = p next; p next = s Dp next = s next; s next = p6在一个单链表中,若删除 p 指向结点的后继结点,则执行的操作是(A)Aq = p next; p next = p next next; free(q);Bp = p next; q = p next; p = q next; free(q);C q = p next next; p = p next; free(q);Dp

5、= p next next; q = p next; free(q);二、填空题7在一个长度为 n 的顺序表中删除第 i 个元素,需要向前移动 n i 个元素8在顺序表中插入或删除一个元素,需要平均移动表长的一半 个元素,具体移动的元素个数与插入或删除的位置有关9顺序表中逻辑上相邻的元素在物理存储位置上一定相邻,链表结构中逻辑上相邻的元素在物理位置上不一定相邻10已知顺序表中一个元素的存储位置是 x,每个元素占 c 个字节,求其后继元素位置计算公式为 x c,而已知单链表中某一结点由 p 指向,求此后继结点存储地址的操作为 p next11在用 p 指针访问单链表时,判断不是访问结束的条件是

6、p ! NULL;在访问单循环链表时,判断不是访问表结束的条件是 p ! head12已知 p 指向双向链表的中间某个结点,从给定的操作语句中选择合适的填空(1 )在 p 结点后插入 s 结点的语句序列是 I、G 、A、D(2 )在 p 结点前插入 s 结点的语句序列是 C、N、H 、B(3 )删除 p 结点的直接后继结点的语句序列是 J、Q、E、M(4 )删除 p 结点的直接前趋结点的语句序列是 K、P、F、M (5 )删除 p 结点的语句序列是 O、R、LAp next s Bp prior s Cs next pDs prior p Ep next p next next Fp prio

7、r p prior priorGp next prior s Hp prior next s Is next p nextJq p next Kq p prior Lfree(p)M free(q) Ns prior p prior Op prior next p nextPp prior prior next p Qp next next prior p Rp next prior p prior13下面是一个在带头结点的单链表 head 中删除所有数据域值为 x 的结点的算法,但不完善,请在相应的地方填上适当的语句,使之成为完整的算法void DeleX(LinkList head, Da

8、taType x)LinkNode *p, *q, *s;P head;q p next;while (q != NULL)if (q data x)s q;q q next;free(s);p next q;elsep q;q q next;三、算法设计题14设有两个顺序表 A 和 B,且都递增有序。试写一算法,从 A 中删除与 B 中相同的那些元素(即计算 A B) SeqList Subtraction(SeqList A, SeqList B)int i, j, k 0;/令匹配位置为 0for (i 0; i next;if (q ! NULL)/判断所指结点是否是最后一个结点if

9、(p head)/判断所指结点是否是头结点head head next;/头结点指针域所指结点变成新的头结点s head next;/记录第 2 个结点head next p;/新的头结点指针域指向原头结点p next s;/原头结点变成第 1 个结点后指针域指向第 2 个结点else r head;while (r next ! p)r r next;/查找 p 指向结点直接前趋r next q;/p 指向结点直接前趋指针域指向 p 指向结点直接后继p next q next;/p 指向结点指针域指向 p 指向结点直接后继的直接后继q next p;/p 指向结点直接后继指针域指向 pels

10、e printf(“p 指向的结点无后继节点!”)16已知两条单链表 A 和 B 分别表示两个集合,其元素值递增有序。试写一算法,求 A 和 B 的交集C,要求 C 同样以元素值递增的单链表形式存储LinkList Intersection(LinkList A, LinkList B)LinkNode *p, *q, *r, *s;LinkList C (LinkNode *) malloc(SizeOf(LinkNode);r C; p A; s B;while (p ! null & q ! null)if (p data data) p p next;else if (p data q

11、 data) q q next;else s (LinkNode *) malloc(SizeOf(LinkNode);s data p data; s next NULL; r next s;r s; p p next; q q next;17设有一个带头结点的双向循环链表,head 为链表的头指针。试写一算法,实现在值为 x 的结点之前插入一个值为 y 的结点void Insert(DlinkList head, DataType x, DataType y)DlistNode *p, *s;s (DlistNode *) malloc(SizeOf(DlistNode);s data y

12、;p head next;while (p ! head & p data ! x)p p next;/查找结点值为 x 的结点if (p head)printf(“没有值为 x 的结点!”);elses next p;s prior p prior;p prior next s;p prior s;第 3 章 栈和队列练习题一、单项选择题1栈的操作原则是(C)A顺序进出 B后进后出 C后进先出 D先进先出2进栈序列为 a,b ,c ,则通过入出栈操作可能得到的 a,b,c 的不同排列个数为(B )A4 B5 C6 D73按字母 a, b,c ,d,e 顺序入栈,则出栈的输出序列不可能是(B

13、)Adecba Bdceab Cabcde Dedcba4判断一个顺序栈 st(最多元素为 StackSize)为栈满的条件表达式是(D)Ast.top ! StackSize Bst.top ! 0 Cst.top ! 1 Dst.top StackSize 15在向顺序栈中压入元素时(C)A先存入元素,后移动栈顶指针 B谁先谁后无关紧要C先移动栈顶指针,后压入元素 D同时进行6一个队列的入队序列是 1,3,5 ,7,9,则出队的输出序列只能是(B )A9 ,7 ,5,3,1 B1,3 , 5,7,9C 1,5,9,3,7 D9 ,5,1,7,37判断一个顺序队列 sq(最多元素为 Queu

14、eSize)为空队列的条件表达式为(A)Asq.rear sq.front Bsq.rear 0C sq.front QueueSize Dsq.rear QueueSize 18判断一个循环队列 cq(最多元素为 QueueSize)为满队列的条件表达式为(C)Acq.rear cq.front Bcq.rear QueueSizeC (cq.rear 1) % QueueSize cq.front Dcq.rear % QueueSize 1 cq.front二、填空题9假设以 S 和 X 分别表示进栈和退栈操作,则对输入序列 a,b,c,d,e 进行一系列栈操作SSXSXSSXXX 之后,得到的输出序列为 b、c 、e、d 、a10假设 S.datamaxsize为一个顺序存储的栈,变量 top 指示栈顶元素的位置。能做进栈操作的条件是 S.top 0)S2.datatop2 x;else S1.datatop2 x;Da

展开阅读全文
相关资源
相关搜索

当前位置:首页 > 行业资料 > 其它行业文档

电脑版 |金锄头文库版权所有
经营许可证:蜀ICP备13022795号 | 川公网安备 51140202000112号