2.解：
(1) m的取值为13 (2)
地址 key
0 1 5 2 6 3 5 4 7 5 10 6 7 8 9 10 11 12 11 51 80 75 88 90 102 113 126 11 47 35 23 探测次数 6 习题9参考答案
一、选择题
1. B 2. D 3. B 4. C 5. D 6. C 二、设计题 1. 解：
int QuickSort(SeqList R,int j,int low,int high){ //对R[low..high]快速排序
int pivotpos; //划分后的基准记录的位置
if(low if (pivotpos==j) return r[j]; else if (pivotpos>j) return(R,j,low,pivotpos-1); else return quicksort(R,j,pivotpos+1,high); } //QuickSort 2. 解： void selectsort(linklist head){ RecNode *p,*q,*s; if(head->next)&&(head->next->next){ p=head->next;//p指向当前已排好序最大元素的前趋 while (p->next){ q=p->next;s=p; while(q){ if (q->key }//endwhile 交换s结点和p结点的数据; p=p->next; }//endwhile }//endif 20 }//endsort 3. 解： void QuickSort(SeqList R,int low ,int high){ //对R[low..high]快速排序 int pivotpos; if(high-low<=2){//若当前区内元素少于3个 //则进行直接插入排序 InsertSort(R,low,high); }else{ pivotpos=midPartion(R,low,high); QuickSort(R,low,pivotpos-1); QuickSort(R,pivotpos+1，high); } }//QuickSort int midPartion(SeqList R,int i, int j){ //三者取中规则定基准 } if(R[(i+j)/2].key>R[i].key){ 交换R[(i+j)/2]和R[i]; } if(R[i].key>R[j].key) { 交换R[i]和R[j];} if(R[i].key) 21 提 习 一、选择题： 高 题 篇 一 1、研究数据结构就是研究 。 A、数据的逻辑结构 B、数据的存储结构 C、数据的逻辑结构和存储结构 D、 数据的逻辑结构、存储结构及其数据在运算上的实现 2、以下属于逻辑结构的是 。 A、顺序表 B、哈希表 C、有序表 D、单链表 3、具有线性结构的数据结构是 。 A、图 B、树 C、广义表 D、栈 4、数据的 包括集合、栈、树和图结构４种基本类型 A、存储结构 B、逻辑结构 C、基本运算 D、算法描述 5、下面程序的时间复杂度为 。 for (I=0;I for (j=0;j A、O(m2) B、O(n2) C、O(m×n) D、O( m+n) 6、一个递归算法必须包括___ ___。 A、递归部分 B、终止条件和递归部分 C、迭代部分 D、终止条件和迭代部分 7、以下说法正确的是___ ___。 A、数据元素是数据的最小单位 B、数据项是数据的基本单位 C、数据结构是带有结构的各数据项的集合 D、一些表面上很不相同的数据可以有相同的逻辑结构 二、填空题 1、从一维数组a[n]中顺序查找出一个最大值元素的平均时间复杂性为 ，读取一个二维数组b[m,n]中任一元素的时间复杂性为 。 2、线性结构中元素之间存在 关系，树形结构中元素之间存在 关系，图形结构中元素存在 关系，而集合结构中元素之间不存在 关系。 3、数据结构是研究数据的 和 以及它们之间的相互关系，并对这种结构定义相应的 并设计出相应的 。 4、通常从___ __、__ ___、_ ____、__ ___等4个方面评价算法（包括程序）的质量。 5、数据的___ __结构与数据元素本身的内容和形式无关。 6、程序段“I=1;while(I<=n) I=I*2;”的时间复杂性为___ __。 参考答案： 一、选择题：1、D 2、C 3、D 4、B 5、C 6、B 7、D 二、填空题： 1、O(N) O(1) 2、一对一 一对多 多对多 逻辑 3、物理结构 逻辑结构 算法 算法 4、正确性 易读性 健壮性 高效性 5、逻辑 6、O(log2n) 22 习题二 一、选择题： 1、线性表是具有n个_____的有限序列。 A、表元素 B、字符 C、数据元素 D、数据项 E、信息项 2、若长度为n的线性表采用顺序存储结构，在其第Ｉ个位置插入一个新元素算法的时间复杂度为______。 A、O (log2n) B、O(1) C、O(n) D、O (n) 3、已知指针p单链表中某一结点，将新生成的由s所指结点加到p所指结点之后，其语句应为_____。 A、 s-> next=p+1; p->next=s; B、 (*p).next=s;(*s).next=(*p).next; C、 s->next=p->next;p->next=s->next; D、 s->next=p->next;p->next=s; 4、将两个各有n个元素的有序表归并成一个有序表，其最少的比较次数是_____。 A、n B、2n-1 C、2n D、n-1 5、线性表Ｌ＝(a1, a2,?, an)，下列说法正确的是_____。 A、每个元素都有一个直接前驱和一个直接后继 B、线性表中至少要有一个元素 C、表中诸元素的排列顺序必须是由小到大或由大到小 D、除第一个和最后一个元素外，其余每个元素都有一个且仅有一个直接前驱和直接后继 6、对单链表表示法，以下说法错误的是_____。 A、数据域用于存储线性表的一个数据元素 B、指针域（或链域）用于存放一个指向本结点所含数据元素的直接后继所在结点的指针 C、所有数据通过指针的链接而组织成单链表 D、NULL称为空指针，它不指向任何结点只起标志作用 7、若给定有n个元素的向量，则建立一个有序单向链表的时间复杂性的量级是 。 A、Ｏ(1) B、O(n) C、O (n2) D、O (log2n) 8、单链表的主要优点是_____。 A、便于随机查询 B、存储密度高 C、逻辑上相邻的元素在物理上也是相邻的 D、插入和删除比较方便 9、对一个具有n个元素的线性表，建立其单链表的时间复杂度为_____。 A、O (n) B、O (1) C、O(n2) D、O(nlog2n) 10、循环链表的主要优点是_____ A、不再需要头指针 B、已知某结点位置后能容易找到其直接前趋 C、在进行插入、删除运算时能保证链表不断开 D、从表中任一结点出发都能扫描整个链表 11、对顺序表的优缺点，以下说法错误的是_____。 A、无需为表示结点间的逻辑关系而增加额外的存储空间 B、可以方便地随机存取表中的任一结点 C、插入和删除运算较为方便 D、由于要求占用连续空间，所以存储分配只能预先进行（静态分配） 二、填空题 2 23 1、对于双向链表，在两个结点之间插入一个新结点时需修改的指针共有_____个，单链表为_____个。 2、对一个循环单链表中，表尾结点的指针域与表头指针值_____。 3、在线性表的顺序存储中，元素之间的逻辑关系是通过_____决定的；在线性表的链式存储中，元素之间的逻辑关系是通过_____决定的。 4、单链表表示法的基本思想是用_____表示结点间的逻辑关系。 5、头结点的next 域值是指示单链表的_____。 6、线性表的两种存储结构分别为_____和_____。 7、在线性表的单链表存储中，若一个元素所在结点地址为p，则其后继结点的地址为_____。 8、线性表的逻辑结构是_____结构，其所含结点的个数称为线性表的_____。 9、表长为０的线性表称为_____。 10、通常将链接方式存储的线性表称为_____，它不仅可用来表示线性表，而且可用来表示各种非线性的数据结构。 参考答案： 一、 选择题： 1、C 2、C 3、D 4、A 5、D 6、C 7、C 8、D 9、A 10、D 11、C 二、 填空题 1、4 2 2、相同 3、物理存储位置 链指针 4、指针 5、第一个数据结点存储地址 6、顺序 链接 7、p->next 8、线性 长度 9、空表 10 链表 三、算法设计 1、假设有两个按元素递增有序排列的线性表Ａ和Ｂ，均以单链表作存储结构。请编写算法，将表Ａ和表Ｂ归并成一个按元素值非递减有序（允许值相同）排列的线性表Ｃ，并要求利用原表（即表Ａ和表Ｂ）的结点空间存放表Ｃ。 Lklist connect(lklist *a,lklist *b) {lklist *p,*q,*r,*u,*c; p=a->next; q=b->next; C=a; r=a; while(p!=NULL)&&(q!=NULL) switch {case p->data>q->data: {u=q->next; r=q; q->next=p; q=u; } case p->data<=q->data; {r=p; p=p->next; }} if(q!=NULL) r>next=q; r->next=q; return(c);} 2、设有头结点的单链表Ｌ，编程对表中任一值只保留一个结点，删除其余值相同的结点。 DelElem(lklist *L); {pointer *p, *t,*pre; p=L->link; t=p; while(p!=NULL) {pre=t; t=t->link; do 24