A、必定快 B、不一定 C、在大部分情况下要快 D、取决于表递增还是递减 4、具有12个关键字的有序表，折半查找的平均查找长度为（ A） A、3.1 B、4 C、2.5 D、5
5、当采用分块查找时，数据的组织方式为（ ） A、数据分成若干块，每块内数据有序
B、数据分成若干块，每块内数据不必有序，但块间必须有序
C、数据分成若干块，每块内数据有序，每块内最大（或最小）的数据组成索引块 D、数据分成若干块，每块（除最后一块外）中数据个数需相同 6、既希望查找速度快又便于线性表动态变化的查找方法有（C） A、顺序查找 B、折半查找 C、索引顺序查找 D、哈希法查找
7、分别以下序列构造二叉排序树，与用其他三个序列所构造的结果不同的是（ D ） A、（100，80，90，60，120，110，130） B、（100，120，110，130，80，60，90） C、（100，60，80，90，120，110，130） D、（100，80，60，90，120，130，110）
二、简答题
1、 什么叫动态查找？什么叫静态查找？什么样的存储结构适宜于进行静态查找？什么样
的存储结构适宜于进行动态查找？
2、 什么叫平均查找长度？写出平均查找长度的定义
三、设计题
1、
已知一个个数为12的数据元素序列为｛Dec,Feb,Nov,Oct,June,Sept,Aug,Apr,May,July,Jan,Mar｝，要求（注意字母的大小是指字母的ASCII码数值大小）：
（1） 按各数据元素的顺序构造一棵二叉排序树
（2） 设各数据元素的查找概率相等，给出该二叉排序树的平均查找长度。 2、
设有数据元素序列｛11，23，35，47，51，60，75，88，90，102，113，126｝，用除留余数法构造哈希表，要求： （1） 设计哈希表的长度取值为m;
（2） 画出用开放定址法的线性探查法解决哈希冲突的哈希表结构； （3） 画出用链表法解决哈希冲突的哈希表结构。
习
一、选择题
1、设有1000个无序的元素，希望用最快的速度挑出其中前10个最大的元素，最好（ ）排序法。
A、起泡排序 B、选择排序 C、堆排序 D、希尔排序
2、在待排序的元素序列基本有序的前提下，效率最高的排序方法是（ ） A、插入排序 B、选择排序 C、快速排序 D、希尔排序 3、一组记录排序码为（46，79，56，38，40，84），则利用堆排序的方法建立的初始堆为（ ）
10
题9
A、79，46，56，38，40，80 B、84，79，56，38，40，46
C、84，79，56，46，40，38 D、84，56，79，40，46，38
4、排序方法中，从未排序序列中依次取出元素与已排序序列（初始时为空）中的元素进行比较，将其放入已排序序列的正确位置上的方法，称为（ ） A、希尔排序 B、起泡排序 C、插入排序 D、选择排序 5、下述几种排序方法中，要求内存量最大的是（ ）
A、插入排序 B、选择排序 C、快速排序 D、归并排序
6、下列四种排序方法中，不稳定的方法是（ ）
A、直接插入排序 B、冒泡排序 C、归并排序 D、直接选择排序
二、设计题
1、对给定的j（1<=j<=n），要求在无序的记录区R［1…n］中找到按关键字自小到大排在第j个位置上的记录（即在无序集合中找到第j个最小元），试利用快速排序的划分思想编写算法实现上述的查找操作。
2、以单链表为存储结构，写一个直接选择排序算法。
3、改写快速排序算法，要求采用三者取中的方式选择划分的基准记录；若当前被排序的区间长度小于等于3时，无须划分而是直接采用直接插入方式对其排序。
基础篇参考答案
习题1参考答案
一、选择题
1. B 2. D 3. D 4. A 5. C 6. B 7. D 8. C 9. A 二、简答题
1. 答：数据的逻辑结构通常有四种，即集合、线性结构、树形结构和图状结构。存储结构主要有顺序存储结构和链式存储结构。
2. 答：比如一分通讯录，记录了相关人员的电话号码，将其按姓名一人占一行构成表，这个表就是一个数据结构。每一行是一个记录，对于整个表来说，只有一个开始结点和一个终端结点，其它结点也只有一个前驱和一个后继。这几个关系就确定了表的逻辑结构。 3. 答：算法是对特定问题求解步骤的一种描述，是指令的有限序列，其中每一条指令表示一个或多个操作。算法具有有穷性、确定性、可行性、输入和输出5个特性。 4.答：
(1) A对应的逻辑图形如下图左，它是一种线性结构。
f
(2) B对应的逻辑图形如上图右所示，它是一种树型结构。 (3) C对应的逻辑图形如下图所示，它是一种图型结构。
11
d a b c d b c e g h a h g f e
3
1
2
4
5
6
三、计算题
1/2
解： (1) O(n) ； (2) O(n) ； (3) O(n)。
习题2参考答案
一、选择题
1. A 2. B 3. B 4. D A5. A 6. C 7. B 8. A 9. C 二、简答题
1. 答：线性表是具有n个数据元素的一个有限序列。线性表的特点是：数据元素之间是一对一的关系。除第一个元素外，每个元素有且只有一个直接前驱；除最后一个元素外，每个元素有且只有一个直接后继。
2. 答：头指针是链表的一个标识，它用来指向带头结点的链表中的头结点。头结点是在链表的第一个数据元素之前附加的一个结点，它的作用是使对第一个结点的操作和其它结点一致，表空与非空时处理一致，不需要特殊处理，简化了操作。
3. 答：顺序表的特点是逻辑位置相邻的数据元素其物理位置也相邻，因此可以进行随机存储， 是一种随机存储结构。其插入和删除操作的时间复杂度均为O(n)。链表中的数据元素使用一组任意的存储单元存储，不要求逻辑位置相邻的数据元素物理位置也相邻，而是采用附加的指针表示元素之间的逻辑关系。链表的插入和删除结点均不需要移动其他结点，但是，其查找运算必须从头指针开始顺序查找，其时间复杂度为O(n)。 4. 答：算法如下
void Convert(SqList &L){ int i,j,temp; j=L.length-1;
i=0;
while(i temp=L.elem[i]; L.elem[i]=L.elem[j]; L.elem[j]=temp; i++; j--; } } 5. 答：算法如下 void Delete(SqList &La,SqList Lb){ int i,j,k; i=0;j=0; while(i 12 if(La.elem[i] else if(La.elem[i]>Lb.elem[j]) j++; else ListDelete_Sq(La, i+1, k); } } 6. 答：算法如下 void InvertList(LinkList &L){ LinkList p,q,r; p = L->next; q = p->next; p->next=NULL; while(q!=NULL){ r=q->next; q->next=p; p=q; q=r; } L->next=p; } 7. 答：算法如下 void MergeOrder(LinkList La,LinkList Lb){ LinkList pa,pb,Lc,pc; pa=La->next; pb=Lb->next; Lc=pc=La; while (pa&&pb){ if(pa->data <=pb->data ){ } pc->next=pa; pc=pa; pa=pa->next; }else{ pc->next=pb; } pc=pb; pb=pb->next; if (!pa) pc->next=pb; else pc->next=pa; } 8. 答：算法如下 int Length(LinkList L){ int i=0; LinkList p; p=L->next; 13 } while(p){ p=p->next; i++; } return i; 习题3参考答案 一、选择题 1. C 2. B 3. A 4. D 5. B 6. C7. C 8. A 9. B 10. B 二、简答题 1. 答：栈是限定在表的一端进行插入和删除操作的线性表。队列是只允许在表的一端进行插入，而在另一端进行删除元素的线性表。栈的操作是按照后进先出原则进行的，因此又称作后进先出的线性表。队列的操作是按照先进先出原则进行的，因此又称作先进先出的线性表。 2. 答：当front?0，rear=M时，再有元素入队发生溢出，称之为“假溢出”，存储空间还有剩余。为了改进这种状况，可以将顺序队列想象为一个首尾相接的环状空间，称之为循环队列。 3. 答： (1) 相应入队列操作 Status EnQueue_L (LinkQueue &Q, ElemType e) { p = (QLink) malloc (sizeof (QNode)); p->data = e; p->next=Q->next; Q->next = p; Q = p; return OK; } (2) 相应出队列的操作 Status DeQueue_L (LinkQueue &Q, ElemType &e) { if (Q->next == Q) return ERROR; p = Q.next->next; e = p->data; Q->next->next = p->next; free(p); return OK; } 4.答：算法如下 void Print(int n){ int i; if (n==0) return; for (i=1;i<=n;i++) printf(\printf(\ 14