数据结构习题1

A、必定快 B、不一定 C、在大部分情况下要快 D、取决于表递增还是递减 4、具有12个关键字的有序表，折半查找的平均查找长度为（ ） A、3.1 B、4 C、2.5 D、5

5、当采用分块查找时，数据的组织方式为（ ） A、数据分成若干块，每块内数据有序

B、数据分成若干块，每块内数据不必有序，但块间必须有序

C、数据分成若干块，每块内数据有序，每块内最大（或最小）的数据组成索引块 D、数据分成若干块，每块（除最后一块外）中数据个数需相同 6、既希望查找速度快又便于线性表动态变化的查找方法有（） A、顺序查找 B、折半查找 C、索引顺序查找 D、哈希法查找

7、分别以下序列构造二叉排序树，与用其他三个序列所构造的结果不同的是（ ） 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），则利用堆排序的方法建立的初始堆为（ ）

12

题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时，无须划分而是直接采用直接插入方式对其排序。

基础篇参考答案

习题2参考答案

一、选择题

习题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;

13

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(\Print(n-1);

}

5.答：算法如下

ElemType Bottom(Stack S){ ElemType x,y; Stack T; }

InitStack(T);

while (!StackEmpty(S)){ }

pop(S,x); push(T,x);

while (!StackEmpty(T)){ pop(T,y); }

push(S,y);

return x;

习题4参考答案

一、选择题 1. B 2. D 3. B 4. D 二、简答题

1. 答：长度为零的串称为空串，记作\。空格也是串的字符集合中的一个元素，由一个或多个空格组成的串称为空格串。例如\ \，其长度为串中空格的个数。

2. 答：虽然串是由字符组成的，但串和字符是两个不同的概念。串是长度不确定的字符序

14

列，而字符只是一个字符。即使是长度为1的串也与字符不同。例如，串\和字符'a'就是两个不同的概念，因为在存储时串的结尾通常加上串结束标志'\\0'。

3. 答：在串的顺序存储结构是用一维数组存放串中的字符。一种方法是用静态内存分配的方法定义的数组，数组元素的个数是在编译时确定的，在运行时是不可改变的，称之为静态顺序存储。另一种方法是用动态内存分配的方法定义的数组，数组元素的个数是在程序运行时用户申请确定的，称之为动态顺序存储。 4. 答：Status StrDelete (String &S,int i,int j){

int len; len=j-i+1;

if (i<1 || i>S[0]|| j>S[0])

// 非法情况的处理

return ERROR;

S[pos..S[0]-len]=S[pos+len..S[0]]; // 将S中从下标从pos+len开始的元素前移len位 S[0]=S[0]-len; return OK;

// 串长的处理

}

5. 答：Status SubString(String S1,String S2){

}

int i,j,k,flag=0; i=1;

while(i

j=1;

if(S1[i]==S2[j]){

k=i+1;j++;

while(S1[k]==S2[j]){ k++;j++; }

if (j==s2[0]) flag=1; else i++;

}

else i++;

return flag;

习题5参考答案

一、选择题

1. D 2. B 3. A 4. D 5. B 6. B 二、简答题

1. 答：所谓行序优先存储，其基本思想为：从第1行的元素开始按顺序存储，第1行元素存储完成后，再按顺序存储第2行的元素，然后依次存储第3行，??直到最后一行的所有元素存储完毕为止。而列序优先存储即为：依次按顺序存储第1列，第2列，??直到最后一列的所有元素存储完毕为止。

2. 答：我们把相同的元素或零元素在矩阵中的分布有一定的规律的称为特殊矩阵。压缩存储的原则是：对多个值相同的元素只存储一次，对零元素甚至不分配存储空间。

3. 答：矩阵中非零元素的个数远远小于矩阵元素的总数，这样的矩阵称为稀疏矩阵。稀疏

15