数据结构习题集(含答案)(3)

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

百度搜索“77cn”或“免费范文网”即可找到本站免费阅读全部范文。收藏本站方便下次阅读，免费范文网，提供经典小说综合文库数据结构习题集(含答案)(3)在线全文阅读。