《[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
