第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．解决问题的计算方法C．解决问题的有限运算序列D．排序算法二、填空题6．数据结构一般包括逻辑结构、存储结构和数据运算三个方面的内容．7．数据的逻辑结构可分为线性结构、非线性结构两大类．8．数据的存储结构（物理结构）一般可以用顺序存储结构、链式存储结构、索引存储结构及散列存储结构等四种存储方法表示．9．在选用求解一个问题的算法时，除了首先考虑算法是“正确的”之外，还主要考虑执行算法所需要的时间、执行算法所需要的存储空间及算法应易于理解、易于编程、易于调试等三点。
10．设有一批数据元素，为了最快地存取某元素，宜用顺序结构存储，为了方便的插入一个元素，宜用链式结构存储．三、应用题设n为正整数，利用大“O”记号，写出下列各程序段的时间复杂度．11．for (i = 1; i <= n; i++){y = y + 1;for (j = 1; j <= 2 * n; j++)x = x + 1;}分析：语句“y = y + 1;”执行n次，语句“x = x + 1;”各执行22n次，故该程序段的时间复杂度为O(2n)．12．s = 0;while (n >= (s + 1) * (s + 1))s = s + 1;分析：语句“s = s + 1;”执行．13．x = 1;sum = 0;for (i = 0; i <= n; i++){x = x * i;sum = sum + x;}分析：语句“x = x * i”和“sum = sum + x;”各执行n次，故该程序段的时间复杂度为O(n)．14．for (i = 1; i <= n; i++)if (3 * i <=n)for (j = 3 * i; j <= n; j++){x++;y = 3 * x + 2;}分析：语句“x++”和“y = 3 * x + 2;”各执行1(1)n n-次，故该程序段的时间复杂度为O(2n)．615．for (i = 1; i <= n; i++)for (j = 1; j <= i; j++){x = x + 1;}分析：语句“x = x + 1;”执行1(1)n n+次，故该程序段的时间复杂度为O(2n)．216．sum = 0; i = 0;while (i <= 100){sum = sum + i;i++;}分析：语句“sum = sum + i;”和“i++;”各执行100次，故该程序段的时间复杂度为O(1)．17．x = 1;s = 0;for (i = 1; i <= n; i++){++x;s += x;}for (j = 1; j <= n; j++)for (k = 1; k <= n; k++){x++;s = s + x;}分析：语句“++x;”执行n次，语句“x++;”和“s = s + x;”各执行2n次，故该程序段的时间复杂度为O(2n)．第2章线性表练习题一、单项选择题1．在长度为n的顺序表的第i(11)≤≤+个位置上插入一个元素，元素的移动次数为（A）i nA．1i-n i-+B．n i-C．i D．1 2．若一个顺序表中第一个元素的存储地址为1000，每个元素占4个地址单元，那么，第6个元素的存储地址应是（A）A．1020 B．1010 C．1016 D．1024 3．带头结点的单链表（以head为头指针）为空的判断条件是（C）A．head != NULL B．head -> next == headC．head -> next == NULL D．head == NULL4．在单循环链表中，p指向表任一结点，判断表不是访问结束的条件是（B）A．p != NULL B．p != head C．p -> next != head D．p -> next != NULL 5．在一个单链表中，已知q指向p所指向结点的前趋结点，若在p、q所指结点之间插入一个s所指向的新结点，则执行的操作是（A）A．q -> next = s; s -> next = p B．p -> next = s; s -> next = qC．s -> next = p -> next; p -> next = s D．p -> next = s -> next; s -> next = p 6．在一个单链表中，若删除p指向结点的后继结点，则执行的操作是（A）A．q = p -> next; p -> next = p -> next -> next; free(q);B．p = p -> next; q = p -> next; p = q -> next; free(q);C．q = p -> next -> next; p = p -> next; free(q);D．p = p -> next -> next; q = p -> next; free(q);二、填空题7．在一个长度为n的顺序表中删除第i个元素，需要向前移动n- i个元素．8．在顺序表中插入或删除一个元素，需要平均移动表长的一半个元素，具体移动的元素个数与插入或删除的位置有关．9．顺序表中逻辑上相邻的元素在物理存储位置上一定相邻，链表结构中逻辑上相邻的元素在物理位置上不一定相邻．10．已知顺序表中一个元素的存储位置是x，每个元素占c个字节，求其后继元素位置计算公式为x+ c，而已知单链表中某一结点由p指向，求此后继结点存储地址的操作为p -> next．11．在用p指针访问单链表时，判断不是访问结束的条件是p != NULL；在访问单循环链表时，判断不是访问表结束的条件是p != head．12．已知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、L．A．p -> next = s B．p -> prior = s C．s -> next = pD．s -> prior = p E．p -> next = p -> next -> next F．p -> prior = p -> prior -> priorG．p -> next -> prior = s H．p -> prior -> next = s I．s -> next = p -> nextJ．q = p -> next K．q = p -> prior L．free(p)M．free(q) N．s -> prior = p -> prior O．p -> prior -> next = p -> next P．p -> prior -> prior -> next = p Q．p -> next -> next -> prior = p R．p -> next -> prior = p -> prior 13．下面是一个在带头结点的单链表head中删除所有数据域值为x的结点的算法，但不完善，请在相应的地方填上适当的语句，使之成为完整的算法．void DeleX(LinkList head, DataType 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;}else{p = 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 < A.Length; i++) {for (j = k; j < B.Length; j++)//从比较匹配的位置开始查起if (A.Data[i] == B.Data[j]){k = j; //记录比较到的位置for (j = i; j < A.Length - 1; j++)A.Data[j] = A.Data[j + 1];//删除相同的元素A.Length--;break;}}return A;}15．已知head是指向一个带头结点的单链表的头指针，p指向该链表的任一结点。
试写一算法，将p 所指向的结点与其后继结点交换位置．void Exchange(LinkList head, LinkNode *p){LinkNode *q, *s, *r;q = p -> next;if (q != NULL)//判断所指结点是否是最后一个结点{if (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指向结点直接后继指针域指向p}}else printf(“p指向的结点无后继节点!”)}16．已知两条单链表A和B分别表示两个集合，其元素值递增有序。