第3章 数据结构t

第3章 数据结构

3．1数据结构的基本概念

一、 课后部分习题答案 3-1 什么是算法？

解答：算法是在有限步骤内求解某一问题所使用的一组定义明确的规则。通俗点说，就是计算机解题的过程。在这个过程中，无论是形成解题思路还是编写程序，都是在实施某种算法。

二、 部分例题及解题思路 ? 选择题

1. 数据结构是指（ ）。

A.数据元素的组织形式 B.数据类型 C.数据存储结构 D.数据定义

2. 数据在计算机存储器内表示时，物理地址与逻辑地址不相同的，称之为（ ）。

A.存储结构 B.逻辑结构 C.链式存储结构 D.顺序存储结构 3. 树形结构是数据元素之间存在一种（ ）。

A.一对一关系 B.多对多关系 C.多对一关系 D.一对多关系

4. 设语句x++的时间是单位时间，则以下语句的时间复杂度为（ ）。

for(i=1; i<=n; i++) for(j=i; j<=n; j++) x++;

A.O(1)

B.O(n)

2 C.O(n)

D.O(n)

35. 算法分析的目的是（1），算法分析的两个主要方面是（2）。

（1） A.找出数据结构的合理性 B.研究算法中的输入和输出关系

C.分析算法的效率以求改进 D.分析算法的易懂性和文档性 （2） A.空间复杂度和时间复杂度 B.正确性和简明性

C.可读性和文档性 D.数据复杂性和程序复杂性 6. 计算机算法指的是（1），它具备输入，输出和（2）等五个特性。 （1） A.计算方法 B.排序方法

C.解决问题的有限运算序列 D.调度方法

（2） A.可行性，可移植性和可扩充性 B.可行性，确定性和有穷性

C.确定性，有穷性和稳定性 D.易读性，稳定性和安全性

7. 数据在计算机内有链式和顺序两种存储方式，在存储空间使用的灵活性上，链式存储比顺序存储要（ ）。

A.低 B.高 C.相同 D.不好说 8. 数据结构作为一门独立的课程出现是在（ ）年。

A.1946 B.1953 C.1964 D.1968

28

9. 数据结构只是研究数据的逻辑结构和物理结构，这种观点（ ）。

A.正确 B.错误

C.前半句对，后半句错 D.前半句错，后半句对 10. 计算机内部数据处理的基本单位是（ ）。

A.数据 B.数据元素 C.数据项 D.数据库

? 填空题

1. 数据结构按逻辑结构可分为两大类，分别是______________和_________________。 2. 数据的逻辑结构有四种基本形态，分别是________________、__________________、__________________和__________________。

3. 线性结构反映结点间的逻辑关系是__________________的，非线性结构反映结点间的逻辑关系是__________________的。

4. 一个算法的效率可分为__________________效率和__________________效率。

5. 在树型结构中，树根结点没有__________________结点，其余每个结点的有且只有__________________个前趋驱结点；叶子结点没有__________________结点；其余每个结点的后续结点可以__________________。

6. 在图型结构中，每个结点的前趋结点数和后续结点数可以__________________。 7. 线性结构中元素之间存在__________________关系；树型结构中元素之间存在__________________关系；图型结构中元素之间存在__________________关系。

8. 下面程序段的时间复杂度是__________________。

for(i=0;i

A[i][j]=0;

9. 下面程序段的时间复杂度是__________________。

i=s=0; while(s

10. 下面程序段的时间复杂度是__________________。

s=0;

for(i=0;i

11. 下面程序段的时间复杂度是__________________。

i=1; while(i<=n) i=i*3;

12. 衡量算法正确性的标准通常是____________________________________。

13. 算法时间复杂度的分析通常有两种方法，即___________和___________的方法，通常我们对算法求时间复杂度时，采用后一种方法。

? 求下列程序段的时间复杂度

29

1. x=0;

for(i=1;i

2. x=0;

for(i=1;i

3. int i,j,k;

for(i=0;i

for(k=0;k

c[i][j]=a[i][k]*b[k][j]

}

4. i=n-1;

while((i>=0)&&A[i]!=k)) j--; return (i);

5. fact(n)

{ if(n<=1)

return (1);

else

return (n*fact(n-1));

}

6．void prime(int n){

/* 判断n是否是素数 */

for (i=2; ((n%i)!=0)&&(i

if i>sqrt(n) printf(\ else printf(\

}/* prime */

7． float sum1(int n){

/* 计算1！+2！+…+n! */ p=1; sum1=0;

for (i=1; i<=n; ++i){

p=p*i; sum1=sum1+p } }/* sum1 */

8． float sum2(int n){

/* 计算1！+2！+…+n! */ sum2=0;

for (i=1; i<=n; ++i){

30

p=1;

for (j=1; j<=i; ++j) p=p*j; sum2=sum2+p; }

}/* sum2 */

9． void sort(int a[],int n){

/* 将数组a中的元素按自小到大的顺序排列 */ for (i=1; i<=n-1; ++i){ k=i;

for (j=i+1; j<=n; ++j) if (a[j]j) {x=a[i];a[i]=a[k];a[k]=x;} }

}/* sort */

10．void matrimult(a[m][n],b[n][l],c[m][l],int m,int n,int l){ /* a为m×n阶的矩阵，b为n×l阶的矩阵，c为m×l阶的矩阵 */ /* 计算c=a*b */ for (i=1; i<=m; ++i) for (j=1; j<=l; ++j) c[i,j]=0; for (i=1; i<=m; ++i) for (j=1; j<=l; ++j)

for (k=1; k<=n; ++k)

c[i,j]=c[i,j]+a[i,k]*b[k,i]; }/* matrimult */

? 参考答案 单项选择题

1. A 2. C 3. D 4. B 5. C、A 6. C、B 7. B 8. D 9. B 10. B

填空题

1. 线性结构，非线性结构 2. 集合，线性，树，图 3. 一对一，一对多或多对多 4. 时间，空间

5. 前趋，一，后继，多 6. 有多个

7. 一对一，一对多，多对多 8. O(n2) 9. O(n) 10. O(n2)

31

11. O(log3n)

12. 程序对于精心设计的典型合法数据输入能得出符合要求的结果。 13. 事后统计，事前估计

算法分析题

1. O(n) 2. O(n) 3. O(n) 4. O(n) 5. O(n) 6。最坏情况下O(sqrt(n)) 7. O(n) 8. O(n2) 9. O(n2) 10.O(n3)

2233．2线性数据结构

二、部分例题及解题思路

（ ）1. 链表的每个结点中都恰好包含一个指针。

答：错误。链表中的结点可含多个指针域，分别存放多个指针。例如，双向链表中的结点可以含有两个指针域，分别存放指向其直接前趋和直接后继结点的指针。

（ ）2. 链表的物理存储结构具有同链表一样的顺序。

答：错，链表的存储结构特点是无序，而链表的示意图有序。

（ ）3. 链表的删除算法很简单，因为当删除链中某个结点后，计算机会自动地将后续的各 个单元向前移动。

答：错，链表的结点不会移动，只是指针内容改变。

（ ）4. 线性表的每个结点只能是一个简单类型，而链表的每个结点可以是一个复杂类型。 答：错，混淆了逻辑结构与物理结构，链表也是线性表！且即使是顺序表，也能存放记录型数据。

（ ）5. 顺序表结构适宜于进行顺序存取，而链表适宜于进行随机存取。 答：错，正好说反了。顺序表才适合随机存取，链表恰恰适于“顺藤摸瓜”

（ ）6. 顺序存储方式的优点是存储密度大，且插入、删除运算效率高。

答：错，前一半正确，但后一半说法错误，那是链式存储的优点。顺序存储方式插入、删除运算效率较低，在表长为n的顺序表中，插入和删除一个数据元素，平均需移动表长一半个数的数据元素。

（ ）7. 线性表在物理存储空间中也一定是连续的。

答：错，线性表有两种存储方式，顺序存储和链式存储。后者不要求连续存放。

（ ）8. 线性表在顺序存储时，逻辑上相邻的元素未必在存储的物理位置次序上相邻。 答：错误。线性表有两种存储方式，在顺序存储时，逻辑上相邻的元素在存储的物理位置次序上也相邻。

32

（ ）9. 顺序存储方式只能用于存储线性结构。

答：错误。顺序存储方式不仅能用于存储线性结构，还可以用来存放非线性结构，例如完全二叉树是属于非线性结构，但其最佳存储方式是顺序存储方式。

（ ）10. 线性表的逻辑顺序与存储顺序总是一致的。 答：错，理由同7。链式存储就无需一致。

11．数据在计算机存储器内表示时，物理地址与逻辑地址相同并且是连续的，称之为（ ） A、存储结构 B、逻辑结构 C、顺序存储结构 D、链式存储结构 答案：C

12.一个向量第一个元素的存储地址是100，每个元素的长度为2，则第5个元素的地址是（ ） A、110 B、108 C、100 D、 120 答案：B

13. 在n个结点的顺序表中，算法的时间复杂度是O（1）的操作是 ( ) A、访问第i个结点（1≤i≤n）和求第i个结点的直接前驱（2≤i≤n） B、在第i个结点后插入一个新结点（1≤i≤n） C、删除第i个结点（1≤i≤n） D、将n个结点从小到大排序 答案：A

14. 向一个有127个元素的顺序表中插入一个新元素并保持原来顺序不变，平均要移动 ( )个元素

A、8 B、63.5 C、63 D、7 答案：B

15. 链接存储的存储结构所占存储空间( )）

A、分两部分，一部分存放结点值，另一部分存放表示结点间关系的指针 B、只有一部分，存放结点值

C、只有一部分，存储表示结点间关系的指针

D、分两部分，一部分存放结点值，另一部分存放结点所占单元数 答案：A

16. 链表是一种采用 ( )存储结构存储的线性表； A、顺序 B、链式 C、星式 D、网状 答案：B

17. 线性表若采用链式存储结构时，要求内存中可用存储单元的地址 ( ) A、必须是连续的 B、部分地址必须是连续的 C、一定是不连续的 D、连续或不连续都可以 答案：D

18． 线性表Ｌ在（ ）情况下适用于使用链式结构实现。

33

A、需经常修改Ｌ中的结点值 B、需不断对Ｌ进行删除插入 C、Ｌ中含有大量的结点 D、Ｌ中结点结构复杂 答案：B

19． 单链表的存储密度（ ）

A、大于1 B、等于1 C、小于1` D、不能确定 答案：C 20． 设a1、a2、a3为3个结点，整数P0，3，4代表地址，则如下的链式存储结构称为（ ）

A、循环链表 B、单链表 C、双向循环链表 D、双向链表 答案：B

21.栈中元素的进出原则是（ ）

A、先进先出 B、后进先出 C、栈空则进 D、栈满则出 答案：B

22.若已知一个栈的入栈序列是1，2，3，?，n，其输出序列为p1，p2，p3，?，pn，若p1=n，则pi为（ ）

A、i B、n=i C、n-i+1 D、不确定 答案：C

解释：当p1=n，即n是最先出栈的，根据栈的原理，n必定是最后入栈的（事实上题目已经表明了），那么输入顺序必定是1，2，3，?，n，则出栈的序列是n，?，3，2，1。

23.判定一个队列QU（最多元素为m0）为满队列的条件是（ ）

A、QU->rear － QU->front = = m0 B、QU->rear － QU->front －1= = m0 C、QU->front = = QU->rear D、QU->front = = QU->rear+1 答案：A

解：队满条件是元素个数为m0。由于约定满队时队首指针与队尾指针相差1，所以不必再减1了，应当选A。当然，更正确的答案应该取模，即：QU->front = = (QU->rear+1)% m0

24．数组Ｑ［ｎ］用来表示一个循环队列，ｆ为当前队列头元素的前一位置，ｒ为队尾元素 的位置，假定队列中元素的个数小于ｎ，计算队列中元素的公式为（ ） A、r－f; B、（n＋f－r）% n; C、n＋r－f; D、（n＋r－f）% n 答案：D

25. 从供选择的答案中，选出应填入下面叙述 ？ 内的最确切的解答，把相应编号写在答卷的对应栏内。

设有4个数据元素a1、a2、a3和a4，对他们分别进行栈操作或队操作。在进栈或进队操作时，按a1、a2、a3、a4次序每次进入一个元素。假设栈或队的初始状态都是空。

现要进行的栈操作是进栈两次，出栈一次，再进栈两次，出栈一次；这时，第一次出栈得到的元素是 1 ，第二次出栈得到的元素是 2 是；类似地，考虑对这四个数据

34

元素进行的队操作是进队两次，出队一次，再进队两次，出队一次；这时，第一次出队得到的元素是 3 ，第二次出队得到的元素是 4 。经操作后，最后在栈中或队中的元素还有 5 个。 供选择的答案：

1～D：A、a1 B、a2 C、 a3 D、a4 E： A、1 B、2 C、 3 C、 0 答案：12345＝B,D,A,B,B

26. 从供选择的答案中，选出应填入下面叙述 ？ 内的最确切的解答，把相应编号写在答卷的对应栏内。

栈是一种线性表，它的特点是 A 。设用一维数组A[1,…,n]来表示一个栈，A[n]为栈底，用整型变量T指示当前栈顶位置，A[T]为栈顶元素。往栈中推入（PUSH）一个新元素时，变量T的值 B ；从栈中弹出（POP）一个元素时，变量T的值 C 。设栈空时，有输入序列a，b，c，经过PUSH，POP，PUSH，PUSH，POP操作后，从栈中弹出的元素的序列是 D ，变量T的值是 E 。 供选择的答案：

A、 ① 先进先出 ②后进先出 ③进优于出 ④出优于进 ⑤ 随机进出 B，C： ① 加1 ②减1 ③不变 ④清0 ⑤ 加2 ⑥减2 D：① a,b ②b,c ③c,a ④b,a ⑤ c,b ⑥ a,c E：① n+1 ②n+2 ③ n ④ n-1 ⑤ n-2 答案：ABCDE=2, 2, 1, 6, 4

注意，向地址的高端生长，称为向上生成堆栈；向地址低端生长叫向下生成堆栈，本题中底部为n，向地址的低端递减生成，称为向下生成堆栈。

27. 从供选择的答案中，选出应填入下面叙述 ？ 内的最确切的解答，把相应编号写在答卷的对应栏内。

在做进栈运算时，应先判别栈是否 A ；在做退栈运算时，应先判别栈是否 B 。当栈中元素为n个，做进栈运算时发生上溢，则说明该栈的最大容量为 C 。 为了增加内存空间的利用率和减少溢出的可能性，由两个栈共享一片连续的内存空间时，应将两栈的 D 分别设在这片内存空间的两端，这样，只有当 E 时，才产生上溢。 供选择的答案：

A，B： ①空 ② 满 ③ 上溢 ④ 下溢 C： ①n-1 ② n ③ n+1 ④ n/2 D： ① 长度 ②深度 ③ 栈顶 ④ 栈底

E：①两个栈的栈顶同时到达栈空间的中心点 ②其中一个栈的栈顶到达栈空间的中心点 ③两个栈的栈顶在达栈空间的某一位置相遇 ④两个栈均不空，且一个栈的栈顶到达另一个栈的栈底

答案：ABCDE＝2, 1, 2, 4, 3

28.试比较顺序存储结构和链式存储结构的优缺点。在什么情况下用顺序表比链表好？

答：① 顺序存储时，相邻数据元素的存放地址也相邻（逻辑与物理统一）；要求内存中可用存储单元的地址必须是连续的。

优点：存储密度大，存储空间利用率高。缺点：插入或删除元素时不方便。

②链式存储时，相邻数据元素可随意存放，但所占存储空间分两部分，一部分存放结点

35

值，另一部分存放表示结点间关系的指针。

优点：插入或删除元素时很方便，使用灵活。缺点：存储密度小（<1），存储空间利用率低。

顺序表适宜于做查找这样的静态操作；链表宜于做插入、删除这样的动态操作。 若线性表的长度变化不大，且其主要操作是查找，则采用顺序表；

若线性表的长度变化较大，且其主要操作是插入、删除操作，则采用链表。

29 .描述以下三个概念的区别：头指针、头结点、首元结点（第一个元素结点）。在单链表中设置头结点的作用是什么？

答：首元结点是指链表中存储线性表中第一个数据元素a1的结点。为了操作方便，通常在链表的首元结点之前附设一个结点，称为头结点，该结点的数据域中不存储线性表的数据元素，其作用是为了对链表进行操作时，可以对空表、非空表的情况以及对首元结点进行统一处理。头指针是指向链表中第一个结点（或为头结点或为首元结点）的指针。若链表中附设头结点，则不管线性表是否为空表，头指针均不为空。否则表示空表的链表的头指针为空。这三个概念对单链表、双向链表和循环链表均适用。是否设置头结点，是不同的存储结构表示同一逻辑结构的问题。

头结点 ? head data link 头指针 首元结点

简而言之，

头指针是指向链表中第一个结点（或为头结点或为首元结点）的指针； 头结点是在链表的首元结点之前附设的一个结点；数据域内只放空表标志和表长等信息（内放头指针？那还得另配一个头指针！）

首元素结点是指链表中存储线性表中第一个数据元素a1的结点。 30．指出以下算法中的错误和低效（即费时）之处，并将它改写为一个既正确又高效的算法。

Status DeleteK(SqList&a, int i, int k){ //本过程从顺序存储结构的线性表a中删除第i个元素起的k个元素 i<1 || k<0 || i+k> a.length ) return INFEASIBLE; //参数不合法 if ( else{ for(count = 1; count =i+1; j--) a.elem[j-1] = a.elem[j]; a.length - -; } return OK; } // DeleteK 注：上题涉及的类型定义如下： # define LIST INIT SIZE 100 # define LISTINCREMENT 10 typedef struct { Elem Type *elem; //存储空间基址 36 Int length; //当前长度 Int listsize; //当前分配的存储容量 }SqList;

答：错误有两处：

参数不合法的判别条件不完整。例如表长为10，若从第一位置（i=1）删除10个元素（k=10）,要求合理但会被判为非法。

合法的入口参数条件为（0 a.length ) return INFEASIBLE 改为：if (！（（0=i+1; j--) a.elem[j-1] = a.elem[j];

改为for (j>=i+1; j = a.length; j++) a.elem[j-1] = a.elem[j];

31. 编写程序，将若干整数从键盘输入，以单链表形式存储起来，然后计算单链表中结点的个数（其中指针P指向该链表的第一个结点）。

解：编写C程序如下： 全局变量及函数提前说明： --------------------------------- #include #include

typedef struct liuyu{int data;struct liuyu*link;}test; liuyu *p,*q,*r,*head; int m=sizeof(test);

void main () /*第一步，从键盘输入整数，不断添加到链表*/ {int i;

head=(test*)malloc(m); /*m=sizeof(test);*/ p=head; i=0;

while (i!=-9999)

{ printf(\scanf(\

p->data=i; /* input data is saved */ p->link=(test*)malloc(m); /*m=sizeof(test));*/ q=p;

p=p->link; }

q->link=NULL; /*原先用p->link=NULL似乎太晚！*/

p=head; i=0; /*统计链表结点的个数并打印出来*/ while (p->link!=NULL)

37

{printf(\p=p->link; i++; }

printf(\ /*结点的个数不包括-9999*/ }

32． 请编写26个字母按特定字母值插入或删除的完整程序，可自行选用顺序存储或链表结构。 答：

#include /*全局变量及函数提前说明：*/ #include

typedef struct liuyu{char data;struct liuyu*link;}test; liuyu *p,*q,*r,*head;

int L; /*元素的个数*/ int m=sizeof(test);

void build(); /* 主函数中会被调用的函数应当预先说明 */ void display();

int insert_char(char,char); /*插入一个字母，在第字母Y之前，若无字母则加到末尾*/ int delet_char(char); /* 删除元素X，注意保存X的前趋元素指针！ */ /*---------------------------------------------------------*/

void build() /*字母链表的生成*/ {int i;

head=(test*)malloc(m); /*m=sizeof(test);*/ p=head;

for(i=1;i

{ p->data=i+'a'-1; /* 'a'也可用其ASCII码97来表示 */ p->link=(test*)malloc(m); /*m=sizeof(test));*/ p=p->link; } p->data=i+'a'-1; p->link=NULL; }

/*---------------------------------------------------------*/ void display() /*字母链表的输出*/ {p=head;

while (p->link!=NULL) { printf(\p=p->link; }

printf(\}

/*---------------------------------------------------------*/

int insert_char(char X,char Y) /*插入一个字母X在某个字母Y之前，若找不到Y字母则加到末尾*/ {p=head;

38

r=(test*)malloc(m); r->data=X;

if(head->data==Y) { head=r;

r->link=p; }

else{ while((p->data!=Y)&&(p->link!=NULL)) {q=p; p=p->link;} if(p->data==Y) { q->link=r; r->link=p; } else{p->link=r;r->link=NULL;} } L++; return(0); }

/*---------------------------------------------------------*/

int delet_char(char X) /* 删除元素X，注意保存X的前趋元素指针！{ p=head;

if(head->data==X){head=head->link;free(p);} else{ while((p->data!=X)&&(p->link!=NULL)) {q=p; p=p->link;} if(p->data==X)

{ q->link=p->link; free(p); } else return(-1); } L--;

return(0); }

/*---------------------------------------------------------*/ void main(void) /*字母线性表的生成和输出*/ { L=26; build(); display();

printf(\display();

printf(\display(); }

附：屏幕上显示的执行结果是：

a b c d e f g h i j k l m n o p q r s t u v w x y z insert return value=0

a b c d 9 e f g h i j k l m n o p q r s t u v w x y z L delete return value=0

a b c d e f g h i j k l m n o p q r s t u v w x y L

*/ 39

3．3数组

二、课后部分习题答案

3-9 假设按行优先存储整数数组A[9][8]时，第一个元素的字节地址是100，每个整数占4个字节。求下列元素的存储地址：（1）A00 (2)A11 (3)A35 (4)A87

解答:根据题目意思，一个以行优先存储的m*n二维数据的Aij元素地址按下述公式计算： Loc（Aij）=Loc（A00）+（i*n+j）*L，此处L=4 所以A00就是第一个元素，它的地址是100。

A11的地址根据公式有：Loc（A11）=Loc（A00）+（1*8+1）*4=100+9*4=136。 A35的地址根据公式有：Loc（A35）=Loc（A00）+（3*8+5）*4=100+29*4=216。 A87的地址根据公式有：Loc（A87）=Loc（A00）+（8*8+7）*4=100+71*4=384。

3-12 什么是稀疏矩阵？稀疏矩阵的存储方法有哪几种？

解答：设矩阵Amn中有s个非零元素，若s远远小于矩阵元素的总数(即s<

为了节省存储单元，可只存储非零元素。由于非零元素的分布一般是没有规律的，因此在存储非零元素的同时，还必须存储非零元素所在的行号、列号，才能迅速确定一个非零元素是矩阵中的哪一个元素。稀疏矩阵的压缩存储会失去随机存取功能。

其中每一个非零元素所在的行号、列号和值组成一个三元组(i，j，aij)，并由此三元组惟一确定。

稀疏矩阵进行压缩存储通常有两类方法：顺序存储和链式存储。

将表示稀疏矩阵的非零元素的三元组按行优先(或列优先)的顺序排列(跳过零元素)，并依次存放在向量中，这种稀疏矩阵的顺序存储结构称为三元组表。

三、部分例题及解题思路

1. 设二维数组A[0?m-1][0?n-1]按行优先顺序存储在内存中，第一个元素的地址为p，每个元素占k个字节，则元素aij的地址为（ ）。 A.p +[i*n+j-1]*k B.p+[(i-1)*n+j-1]*k

C.p+[(j-1)*n+i-1]*k D.p+[j*n+i-1]*k 解答：A

2. 已知二维数组A10×10中，元素a20的地址为560，每个元素占4个字节，则元素a10的地址为（ ）。 A.520 B.522 C.524 D.518

解答：A

3. 若数组A[0?m][0?n]按列优先顺序存储，则aij地址为（ ）。

A.LOC(a00)+[j*m+i] B. LOC(a00)+[j*n+i]

C.LOC(a00)+[(j-1)*n+i-1] D. LOC(a00)+[(j-1)*m+i-1] 解答：A

4. 假定在数组A中，每个元素的长度为3个字节，行下标i从1到8，列下标j从1到10，

40

从首地址SA开始连续存放在存储器内，存放该数组至少需要的单元数为（ ）。

A.80 B.100 C.240 D.270

解答：C

5. 数组A中，每个元素的长度为3个字节，行下标i从1到8，列下标j从1到10，从首地址SA开始连续存放在存储器内，该数组按行存放时，元素A[8][5]的起始地址为（ ）。 A.SA+141 B.SA+144 C.SA+222

解答：C

6. 稀疏矩阵一般的压缩存储方法有两种，即（ ）。

D.SA+225

A.二维数组和三维数组 B.三元组和散列

C.三元组和十字链表 D.散列和十字链表 解答:C

7. 若采用三元组压缩技术存储稀疏矩阵，只要把每个元素的行下标和列下标互换，就完成了对该矩阵的转置运算，这种观点（ ）。 A.正确 B.不正确

解答:B

8. 一个稀疏矩阵为 ? 2 0 ? ，则对应的三元组线性表为_____________。 0 0 ?3000? ?00?15???

?0000?解答：三元组表为：（（0，2，2），（1，0，3），（2，2，-1），（2，3，5））

??3．4树

二、部分例题及解题思路

1． 不含任何结点的空树（ ）

A、是一棵树 B、是一棵二叉树

C、是一棵树也是一棵二叉树 D、既不是树也不是二叉树 答案：C

2．二叉树是非线性数据结构，所以（ ）

A、它不能用顺序存储结构存储 B、它不能用链式存储结构存储

C、顺序存储结构和链式存储结构都能存储 D、顺序存储结构和链式存储结构都不能使用 答案：C

41

3. 具有n(n>0)个结点的完全二叉树的深度为（ ）

A、?log2(n)? B、? log2(n)? C、 ? log2(n) ?+1 D、 ?log2(n)+1? 答案：C

注1：?x ?表示不小于x的最小整数；? x?表示不大于x的最大整数，它们与[ ]含义不同！ 注2：选A是错误的。例如当n为2的整数幂时就会少算一层。似乎? log2(n) +1?是对的？

4．把一棵树转换为二叉树后，这棵二叉树的形态是（ ） A、唯一的 B、有多种

C、有多种，但根结点都没有左孩子 D、有多种，但根结点都没有右孩子 答案：A

5.从供选择的答案中，选出应填入下面叙述 ？ 内的最确切的解答，把相应编号写在答卷的对应栏内。

树是结点的有限集合，它__A__ 根结点，记为T。其余的结点分成为m（m≥0）个 B 的集合T1，T2，?，Tm，每个集合又都是树，此时结点T称为Ti的父结点，Ti称为T的子结点（1≤i≤m）。一个结点的子结点个数为该结点的 C 。 供选择的答案

A： ①有0个或1个 ②有0个或多个 ③有且只有1个 ④有1个或1个以上 B: ①互不相交 ② 允许相交 ③ 允许叶结点相交 ④ 允许树枝结点相交 C： ①权 ② 维数 ③ 次数（或度） ④ 序 答案：ABC＝1，1，3

6. 从供选择的答案中，选出应填入下面叙述 ？ 内的最确切的解答，把相应编号写在答卷的对应栏内。

二叉树 A 。在完全的二叉树中，若一个结点没有 B ，则它必定是叶结点。每棵树都能惟一地转换成与它对应的二叉树。由树转换成的二叉树里，一个结点N的左子女是N在原树里对应结点的 C ，而N的右子女是它在原树里对应结点的 D 。 供选择的答案

A： ①是特殊的树 ②不是树的特殊形式 ③是两棵树的总称 ④有是只有二个根结点的树形结构

B: ①左子结点 ② 右子结点 ③ 左子结点或者没有右子结点 ④ 兄弟 C～D： ①最左子结点 ② 最右子结点 ③ 最邻近的右兄弟

④ 最邻近的左兄弟 ⑤ 最左的兄弟 ⑥ 最右的兄弟

答案：ABCDE＝2，1，1，3

7．试写出如图所示的二叉树分别按先序、中序、后序遍历时得到的结点序列。

答案：DLR：A B D F J G K C E H I L M LDR: B F J D G K A C H E L I M LRD：J F K G D B H L M I E C A

8.把如图所示的树转化成二叉树。

42

如果按上面给出的划分算法，每次取当前无序区的第1个记录为基准，那么当文件的记录已按递增序(或递减序)排列时，每次划分所取的基准就是当前无序区中关键字最小(或最大)的记录，则快速排序所需的比较次数反而最多。冒泡排序算法最快。

27．当待排序的元素很大时，为了交换元素的位置，移动元素要占用较多的时间，这是影响时间复杂度的主要因素。（ ） 答：对。

28．内排序要求数据一定要以顺序方式存储。 （ ）

答：错。内排序是指在排序的整个过程中，数据全部存放在计算机的内存储器中，并且在内存储器中调整记录的相对位置，但并不要求以顺序方式存储。

29．排序算法中的比较次数与初始元素序列的排列无关。（ ） 答：错。

30．在执行某个排序算法过程中，出现了排序码朝着最终排序序列位置相反方向移动，则该算法是不稳定的。（ ） 答：错。例如冒泡排序是稳定排序，将4,3,2,1按冒泡排序排成升序序列，第一趟变成3,2,1,4，此时3就朝向最终位置的相反方向移动。

31．当待排序记录已经从小到大排序或者已经从大到小排序时，快速排序的执行时间最省。（ ）

答：错。当文件为正序时，直接插入、冒泡排序最快。

32．快速排序的速度在所有排序方法中为最快。（ ）

答：错。在平均情况下，快速排序最快；在最好的情况下，直接插入排序和冒泡排序最快；在最坏的情况下，对排序和归并排序最快。

33．归并排序辅助存储为O（1）。（ ） 答：错。归并排序辅助存储为O(n)。

34．在任何情况下，归并排序都比简单插入排序快。（ ） 答：错。原因同32。

35. 中序遍历平衡的二叉排序树，可得到最好排序的关键码序列。（ ） 答：对。

36. 当输入序列已经有序时，起泡排序需要的排序码比较次数比快速排序要少。（ ） 答：对。

37. 如果输入序列已经排好序，则快速排序算法无需移动任何数据对象就可以完成排序。（ ）

答：错。输入序列若是以逆序排列则需要移动数据对象来完成排序

68

38.在执行某种排序算法的过程中，出现了排序码朝着最终排序序列相反的方向移动，从而认为该排序算法是不稳定的。（ ） 答：错。排序的不稳定性是指排序的前两个排序码相同的元素的相对次序经过了排序后发生了变化，而题中未涉及到元素的相对次序（特别是相同排序码的元素）的改变，只有移动方向，所以这种说法不正确。

39. 大多数排序算法都有两个基本的操作： 比较（两个关键字的大小） 和 移动（记录或改变指向记录的指针） 。

40. 在插入和选择排序中，若初始数据基本正序，则选用 插入排序（到尾部） ；若初始数据基本反序，则选用 选择排序 。

41. 在堆排序、快速排序和归并排序中，若只从存储空间考虑，则应首先选取 堆排序 方法，其次选取 快速排序 方法，最后选取 归并排序 方法； 若只从排序结果的稳定性考虑，则应 选取归并排序方法； 若只从平均情况下最快考虑，则应选取快速排序方法；

若只从最坏情况下最快并且要节省内存考虑，则应选取堆排序方法。

42.每次从无序子表中取出一个元素，把它插入到有序子表中的适当位置，此中排序方法叫做插入排序。每次从无序表中挑选出一个最小或最大元素，把它交换到有序表的一端，此种方法叫做选择排序。

43.在对一组记录（54，38，96，23，15，72，60，45，83）进行直接插入排序时，当把第7个记录60插入到有序表时，为寻找插入位置至少需比较 3 次。(可约定为，从后向前比较)

44.每次直接直接或通过基准元素间接比较令个元素，若出现逆序排列时就交换它们的位置，此种方法叫做 快速 排列，每次使两个相邻的有序表合并成一个有序标的排序方法叫做 归并 排序。

45. 在直接选择排序中，数据对象移动次数的时间复杂度为O(___n_____)。

46. 每次使两个相邻的有序表合并成一个有序表，这种排序方法叫做 二路归并排序。

47. (1)当待排序的关键字序列的初始态分别为正序和反序时，为什么直接选择排序的时间基本相同?

(2)为什么数组的初态为正序时，冒泡和直接插入排序的执行时间最少? 答：

(1)由于在直接选择排序中，主要的操作是比较操作和移动操作。无论文件的初始状态如何，若文件有n个记录，则都要进行n-1趟直接选择排序，第i趟直接选择排序中都要做n-i次比较才能选出最小关键字的记录。所以总的比较次数都为O(n2)。至于记录的移动次数，初始文件为正序时，移动次数为0，当文件初始时为反序，总的移动次数为3(n-1)。因此当待排序的关键字序列的初始态分别为正序和反序时，直接选择排序的时间基本相同，为O(n2)。 (2)当冒泡排序是正序时，只需做一趟冒泡排序就可完成，共做n-1次比较，移动次数为0，

69

所以执行时间最少。而直接插入排序时，若初始为正序，则做了n-1趟直接插入排序，但每趟排序只做了一次比较，共做n-1次比较。移动次数为0。所以当数组初态为正序，直接插入排序时间也最少。

48.给出一组关键字（19，01，26，92，87，11，43，87，21），进行冒泡排序，试列出每一趟排序后关键字的排列次序，并统计每趟排序所进行的关键字比较次数。 答：初始关键字序列为（19，01，26，92，87，11，43，87，21） 第一趟排序比较8次，交换6次后成为

（01，19，26，87，11，43，87，21，92）

第二趟排序比较7次，交换3次后成为

（01，19，26，11，43， 87，21，87，92）

第三趟排序比较6次，交换2次后成为

（01，19， 11，26，43，21，87，87，92） 第四趟排序比较5次，交换2次后成为

（01， 11，19，26，21，43，87，87，92） 第五趟排序比较4次，交换1次后成为

（01， 11，19， 21，26，43，87，87，92） 第六趟排序比较3次，交换0次。排序完毕。

49.对题48给出的关键字序列进行选择排序，试列出每趟排序后的关键字序列，并统计所进行的关键字比较次数。

答：初始关键字序列为（19，01，26，92，87，11，43，87，21） 第一趟排序比较8次，将最小元01与19交换：

（01，19，26，92，87，11，43，87，21）

第二趟排序比较7次，将第二最小元11与19交换：

（01，11，26，92，87，19，43，87，21）

第三趟排序比较6次，将第3最小元19与26交换：

（01，11，19，92，87，26，43，87，21） 第四趟排序比较5次，将第4最小元21与92交换：

（01，11，19，21，87，26，43，87，92）

第五趟排序比较4次，将第5最小元26与87交换：

（01，11，19，21，26，87，43，87，92）

第六趟排序比较3次，将第6最小元43与87交换：

（01，11，19，21，26，43，87，87，92）

第七、八两趟排序各比较2次和1次，不进行交换。

50.什么是内部排序？什么是排序方法的稳定性和不稳定性？

答：假设给定含有n个记录（R1,R2,…,Rn）的文件，其相应的关键字为（K1,K2,…,Kn），则排序是确定一个排列P(1),P(2),…,P(n)，使得K P(1)≤K P(2) , ≤?≤K P(n)，从而得到有序文件（R P(1),R P(2),…,R P(n)）。整个排序过程都在内存进行的排序称为内部排序。

假设在待排序的文件中，存在两个或两个以上的记录具有相同的关键字，在用某种排序法排序后，若这些相同关键字的记录相对次序仍然保持不变，则这种排序方法是稳定的，否则称这种排序方法是不稳定的。

70

A．有向图 B．无向图 C．AOV网 D．AOE网 答案：B

18．设无向图的顶点个数为n，则该图最多有（ ）条边。

A．n-1 B．n(n-1)/2 C． n(n+1)/2 D．0 E．n2 答案:B

19．无向图G=(V,E),其中：V={a,b,c,d,e,f}, E={(a,b),(a,e),(a,c),(b,e),(c,f),(f,d), (e,d)}， 对该图进行深度优先遍历，得到的顶点序列正确的是（ ）。

A．a,b,e,c,d,f B．a,c,f,e,b,d C．a,e,b,c,f,d D．a,e,d,f,c,b 答案：D

20. 下列说法不正确的是（ ）。

A． 图的遍历是从给定的源点出发每一个顶点仅被访问一次 B． 图的深度遍历不适用于有向图 C． 遍历的基本算法有两种：深度遍历和广度遍历 D． 图的深度遍历是一个递归过程 答案：B

21．图中有关路径的定义是（ ）。

A．由顶点和相邻顶点序偶构成的边所形成的序列 B．由不同顶点所形成的序列 C．由不同边所形成的序列 D．上述定义都不是 答案： A

22．一个n个顶点的连通无向图，其边的个数至少为（ ）。

A．n-1 B．n C．n+1 D．nlogn 答案：A

23．要连通具有n个顶点的有向图，至少需要（ ）条边。

A．n-l B．n C．n+l D．2n 答案：B

24．n个结点的完全有向图含有边的数目（ ）。

A．n*n Ｂ．n（n＋１） C．n／2 D．n*（n－l） 答案：D

25．一个有n个结点的图，最少有（ ）个连通分量，最多有（ ）个连通分量。

A．0 B．1 C．n-1 D．n 答案：①B ②D

?010?

?A??101 ????010??可以看出，该图共有（①）个顶点；如果是有向图 26． 从邻接矩阵

该图共有（②） 条弧；如果是无向图，则共有（③）条边。

48

①．A．9 B．3 C．6 D．1 E．以上答案均不正确 ②．A．5 B．4 C．3 D．2 E．以上答案均不正确 ③．A．5 B．4 C．3 D．2 E．以上答案均不正确 答案：①:B ②:B ③:D

27．当一个有N个顶点的图用邻接矩阵A表示时，顶点Vi的度是（ ）。

A．

?A[i,j]i?1n B．

?A?i,j?j?1n C．

?A[j,i]i?1n D．

?A[i,j]?A?j,i?i?1nn+

j?1

答案：B

28. 下列说法不正确的是（ ）。

A．图的遍历是从给定的源点出发每一个顶点仅被访问一次 B．遍历的基本算法有两种：深度遍历和广度遍历 C．图的深度遍历不适用于有向图 D．图的深度遍历是一个递归过程 答案： C

29. 设图如下所示，在下面的5个序列中，符合深度优先遍历的序列有多少？（ ）

a e b d f c a c f d e b a e d f c b a e f d c b a e f d b c

A．5个 B．4个 C．3个 D．2个 答案：D a

bec

df

第29题图 第30题图

30.下图中给出由7个顶点组成的无向图。从顶点1出发，对它进行深度优先遍历得到的序

列是( ① )，而进行广度优先遍历得到的顶点序列是（ ② ）。 ①：A．1354267 B．1347652 C．1534276

D．1247653 E．以上答案均不正确

②：A．1534267 B．1726453 C．l354276

D．1247653 E．以上答案均不正确

答案：①：C ②: C

31.已知一个图如下所示。则由该图得到的一种拓扑序列为（ ）。

49

A．v1,v4,v6,v2,v5,v3 B．v1,v2,v3,v4,v5,v6 C．v1,v4,v2,v3,v6,v5 D．v1,v2,v4,v6,v3,v5 答案：A

解析：此题要求掌握拓扑排序的具体步骤：在有向图中选择一个没有前驱的顶点并输出,在有向图中删除该顶点以及从它出发的弧，重复以上步骤直至有向图变空。可得到A的序列。

2 6 4 1 1 V1 6 50 2 3 1

2 V2 3 43 5 6 4 11 3 V3 8 8 4 5 4 V4 5 5 V5 3 38 7 24 6 6 V6 5 1 7 12 8 20 7 V7 第31 题图 8 V8

第32题图

32.从供选择的答案中选出正确答案填入下面叙述的（）中。

如图是带权的有向图G的邻接表表示法。以结点V1出发深度遍历图G所得的结点序列为（ ① ）；广度遍历图G所得的结点序列是（ ② ）；G的一个拓扑序列是（③ ）；从结点V1到结点V8的最短路径是（ ④ ）；从结点V1到V8的关键路径是（⑤ ）。 ①-③: A.V1,V2,V3,V4,V5,V6,V7,V8 B. V1,V2,V4,V6,V5,V3,V7,V8

C. V1,V2,V4,V6,V3,V5,V7,V8

12 D. V1,V2,V4,V6, V7,V3,V5, V8 E. V1,V2,V3,V8,V4,V5,V6,V7 F. V1,V2,V3,V8,V4,V5,V7,V6 G. V1,V2,V3,V8,V5,V7,V4,V6 ④-⑤:A.(V1,V2,V4,V5,V3,V8)

B. (V1,V6,V5,V3,V8) C. (V1,V6,V7,V8) D. (V1,V2,V5,V7,V8) 答案: ①:G ②：C ③：B ④: D ⑤:B

解析：根据题中给出的邻接表，可以画出相应的图，如下图所示。

依该图的特点（只有一个入度为0的顶点），取v1

V3 43 为出发点，访问此结点，然后依次从v1的未被访问的邻V2 8 接点出发进行深度优先遍历，直至图中所有和v1有路径6 11 6 V5 38 1 相通的结点都被访问到。若此时图中尚有结点未访问到，V1 V8 V4 24 则另选图中一个未被访问过的结点做起始点，重复上述1 50 20 过程，直至图中所有几点都被访问为止。因此，图的深

12 V6 V7 度优先遍历为：v1,v2,v3,v8,v5,v7,v4,v6。通常深度优 先遍历的结果不是唯一的。但从供选择的答案中选取的

答案只有G才是深度优先遍历的结果。对于其它问题，只要依邻接表画出了相应有向图，问题就比较容易解答。

50

33.判定一个有向图是否存在回路，除了可以利用拓扑排序的方法外，还可以利用（ ）。

A.求关键路径的方法 B.求最短路径的方法 C.深度优先遍历法 D.广度优先遍历算法 答案：C。

解析：此题要求对以上各种方法了解。

34. 在n个结点的无向图中，若边数大于n-1,则该图必是连通图。（ ） 答：错。不一定是连通图，可能有若干连通分量。

35. 有向图的邻接矩阵是对称的。（ ）

答：错。只有有向完全图的邻接矩阵是对称的。

36. AOV网的含义是以边表示活动的网。（ ）

答：错。 AOV网是用顶点代表活动，弧表示活动间的优先关系的有向图,叫顶点表示活动的网。

37. 邻接矩阵适用于有向图和无向图的存储，但不能存储带权的有向图和无向图，而只能使用邻接表存储形式来存储它。（ ）

答：错。邻接矩阵中元素值可以存储权值。

38.树中的结点和图中的顶点就是指数据结构中的数据元素。( ) 答：对。

39. 有n个顶点的无向图, 采用邻接矩阵表示, 图中的边数等于邻接矩阵中非零元素之和的一半。（ ） 答：对。

40. 无向图的邻接矩阵一定是对称矩阵，有向图的邻接矩阵一定是非对称矩阵。（ ） 答：错。只有有向完全图的邻接矩阵是对称的

41. 用邻接矩阵存储一个图时，在不考虑压缩存储的情况下，所占用的存储空间大小与图中结点个数有关，而与图的边数无关。（ ） 答：对。

42.存储无向图的相邻矩阵是对称的，因此只要存储相邻矩阵的下（或上）三角部分就可以了。（ ） 答：对。

43. 一个有向图的邻接表和逆邻接表中结点的个数可能不等。（ ） 答：错。

44.有e条边的无向图，在邻接表中有e个结点。（ ）

答：错。若无向图中有n个顶点，e条边，则它的临接表需n个头结点和2e个表结点。

51

45. 有向图中顶点V的度等于其邻接矩阵中第V行中的1的个数。（ ） 答：错。

46. 连通分量指的是有向图中的极大连通子图。（ ） 答：错。无向图的极大连通子图称为连通分量。

47. 一个图的广度优先搜索树是唯一的。（ ） 答：错。

48.图的深度优先搜索序列和广度优先搜索序列不是唯一的。（ ） 答：对

49.有回路的图不能进行拓扑排序。（ ） 答：对

50.在一个图G的邻接表表示中，每个顶点的邻接表中所含的结点数，对于有向图而言等于该顶点的 出度数 ；而对于无向图而言等于该顶点的 度数 。

51.一个无向图有n个顶点和e条边，则所有顶点的度的和为 2e 。

52.若无向图G的顶点度数的最小值大于或等于 顶点个数n 时,G至少有一条回路。

53.在一个具有n个顶点的无向完全图中，包含有n(n-1)/2 条边；在一个具有n个顶点的有向完全图中，包含有n(n-1) 条边。

54.有向图的极大强连通子图称为 有向图的强连通分量 。

55. 根据图的存储结构进行某种次序的遍历，得到的顶点序列是 唯一 的。

3．6查找

二、课后部分习题答案 3-24

答：查找b的过程

0 1 2

b

3 e 4 f High=4 5 g mid=5 6 j 7 k 8 m 9 n High=9 52

a Low=1 c Low=1 mid=2 mid=Low=high=1

b>a 未找到。

查找k的过程

0 1

k>g k=k找到。

Low=6 mid=7

High=9

Low=1 mid=5 High=9 a 2 c 3 e 4 f 5 g 6 j 7 k 8 m 9 n 3-28

答：考虑每个字串的第一个字符，若取p=17则 H(key)=key(第一个字母的ASCII码mod 17)

H(Jan)=74 mod 17=6 H(Feb)=70 mod 17=2 H(Mar)=77 mod 17=9 H(Apr)=65 mod 17= 14 H(May)=77mod 17= 9 H(June)=74 mod 17= 6 H(July)=74 mod 17= 6 H(Aug)=65 mod 17= 14 H(Sep)=83 mod 17= 15 H(Oct)=79 mod 17= 11 H(Nov)=78 mod 17= 10 H(Dec)=68 mod 17= 0

用线性探测法处理冲突，建表如下图所示。 Hi=(Hash(key)+di) mod m (1≤i

用链地址法处理冲突，建表如下图所示。 0 1 2 3 4 5 6 7 8 9 11

Mar Nov Oct May Jan June July Feb Dec 10 12 13 14

Apr Sep Aug 53

15 16

三、部分例题及解题思路

1．在表长为ｎ的链表中进行线性查找，它的平均查找长度为（ ）

Ａ、ASL＝ｎ Ｂ、ASL＝（n＋1）/2 Ｃ、ASL＝n＋１ Ｄ、ASL≈log2（n＋1）－1 答案：B

2．折半查找有序表（4，6，10，12，20，30，50，70，88，100）。若查找表中元素58，则 它将依次与表中（ ）比较大小，查找结果是失败。

A、20，70，30，50 B、30，88，70，50 C、20，50 D、30，88，50 答案：A

3．对22个记录的有序表作折半查找，当查找失败时，至少需要比较（ ）次关键字。 A、3 B、4 C、5 D、6 答案：C

4. 链表适用于（ ）查找

A．顺序 B．二分法 C．顺序，也能二分法 D．随机 答案：A

5. 折半搜索与二叉搜索树的时间性能（ ）

A、 相同 B、完全不同 C、有时不相同 D、数量级都是O（log2n） 答案：C

6．从供选择的答案中，选出应填入下面叙述 ？ 内的最确切的解答，把相应编号写在答卷的对应栏内。

要进行线性查找，则线性表（ A ） ；要进行二分查找，则线性表（ B ） ；要进行散列查找，则线性表（ C ） 。

某顺序存储的表格，其中有90000个元素，已按关键项的值的上升顺序排列。现假定对各个元素进行查找的概率是相同的，并且各个元素的关键项的值皆不相同。当用顺序查找法查找时，平均比较次数约为（ D ） ，最大比较次数为 （ E ） 。 供选择的答案：

A~C：① 必须以顺序方式存储 ② 必须以链表方式存储 ③ 必须以散列方式存储 ④ 既可以以顺序方式，也可以以链表方式存储

⑤ 必须以顺序方式存储且数据元素已按值递增或递减的次序排好 ⑥ 必须以链表方式存储且数据元素已按值递增或递减的次序排好

D，E： ① 25000 ② 30000 ③ 45000 ④ 90000

答案： A= ④ B= ⑤ C= ③ D＝ ③ E＝ ④

7.从供选择的答案中，选出应填入下面叙述 ？ 内的最确切的解答，把相应编号写在答卷的对应栏内。

数据结构反映了数据元素之间的结构关系。链表是一种（ A ） ，它对于数据元素的

54

插入和删除 （ B ） 。通常查找线性表数据元素的方法有（ C ） 和（ D ）两种方法，其中（ C ） 是一种只适合于顺序存储结构但 （ E ） 的方法；而（ D ） 是一种对顺序和链式存储结构均适用的方法。 供选择的答案：

A：①顺序存储线性表 ②非顺序存储非线性表 ③顺序存储非线性表 ④非顺序存储线性表

B： ① 不需要移动结点，不需改变结点指针 ②不需要移动结点，只需改变结点指针 ③只需移动结点，不需改变结点指针 ④既需移动结点，又需改变结点指针 C：① 顺序查找 ②循环查找 ③条件查找 ④二分法查找 D：① 顺序查找 ②随机查找 ③二分法查找 ④分块查找 E：① 效率较低的线性查找 ②效率较低的非线性查找 ③ 效率较高的非线性查找 ④效率较高的线性查找

答案：A＝ ④ B＝ ② C＝ ④ D＝ ① E＝ ③

8. 从供选择的答案中，选出应填入下面叙述 ？ 内的最确切的解答，把相应编号写在答卷的对应栏内。

在二叉排序树中，每个结点的关键码值（ A ） ，（ B ）一棵二叉排序，即可得到排序序列。同一个结点集合，可用不同的二叉排序树表示，人们把平均检索长度最短的二叉排序树称作最佳二叉排序，最佳二叉排序树在结构上的特点是（ C ）。 供选择的答案

A： ①比左子树所有结点的关键码值大，比右子树所有结点的关键码值小 ②比左子树所有结点的关键码值小，比右子树所有结点的关键码值大 ③比左右子树的所有结点的关键码值都大

④与左子树所有结点的关键码值和右子树所有结点的关键码值无必然的大小关系 B: ①前序遍历 ② 中序（对称）遍历 ③ 后序遍历 ④ 层次遍历 C：① 除最下二层可以不满外，其余都是充满的 ②除最下一层可以不满外，其余都是充满的

③ 每个结点的左右子树的高度之差的绝对值不大于1 ④ 最下层的叶子必须在最左边

答案：A＝ ① B＝ ② C＝ ②

9. 从供选择的答案中，选出应填入下面叙述 ？ 内的最确切的解答，把相应编号写在答卷的对应栏内。

散列法存储的基本思想是根据（ A ）来决定 （ B ），碰撞（冲突）指的是（ C ），处理冲突的两类主要方法是（ D ）。 供选择的答案

A，B： ①存储地址 ② 元素的符号 ③ 元素个数 ④ 关键码值 ⑤ 非码属性 ⑥ 平均检索长度 ⑦ 负载因子 ⑧ 散列表空间 C: ①两个元素具有相同序号 ② 两个元素的关键码值不同，而非码属性相同 ③ 不同关键码值对应到相同的存储地址 ④ 负载因子过大 ⑤ 数据元素过多 D： ① 线性探查法和双散列函数法 ② 建溢出区法和不建溢出区法 ③ 除余法和折叠法 ④ 拉链法和开地址法

答案：A＝ ④ B＝ ① C＝ ③ D＝ ④

55

10.考虑具有如下性质的二叉树：除叶子结点外，每个结点的值都大于其左子树上的一切结点的值。并小于等于其右子树上的一切结点的值。

现把9个数1，2，3，?，8，9填入右图所示的二叉树的9个结点中，并使之具有上述性质。此时，n1的值是（ A ），n2的值是（ B ），n9的值是（ C ）。现欲把10放入此树并使该

树保持前述性质，增加的一个结点可以放在（D ）或（ E ）。 供选择的答案 A～C： ①1 ② 2 ③ 3 ④ 4 ⑤ 5 ⑥ 6 ⑦ 7 ⑧ 8 ⑨ 9

D～E： ① n7下面 ② n8下面 ③ n9下面 ④ n6下面

⑤ n1与n2之间 ⑥ n2与n4之间 ⑦ n6与n9之间 ⑧ n3与n6之间

答案：A＝ ⑦ B＝ ④ C＝ ⑥ D＝ ② E＝ ⑥

11.当在一个有序的顺序存储表上查找一个数据时，既可用折半查找，也可用顺序查找，但前者比后者的查找速度( )

A．必定快 B.不一定 C. 在大部分情况下要快 D. 取决于表递增还是递减 答案：C

12.顺序查找法适用于查找顺序存储或链式存储的线性表，平均比较次数为（（1））,二分法查找只适用于查找顺序存储的有序表，平均比较次数为（（2））。 在此假定N为线性表中结点数，且每次查找都是成功的。

A.N+1 B.2log2N C.logN D.N/2 E.Nlog2N F.N2 答案：（1）D （2）C

13. 下面关于二分查找的叙述正确的是 ( )

A. 表必须有序，表可以顺序方式存储，也可以链表方式存储 B. 表必须有序且表中数据必须是整型，实型或字符型 C. 表必须有序，而且只能从小到大排列 D. 表必须有序，且表只能以顺序方式存储 答案：D

14. 对线性表进行二分查找时，要求线性表必须（ ）

A. 以顺序方式存储 B.以顺序方式存储,且数据元素有序 C.以链接方式存储 D.以链接方式存储,且数据元素有序 答案：B

15．适用于折半查找的表的存储方式及元素排列要求为( )

A．链接方式存储，元素无序 B．链接方式存储，元素有序

C．顺序方式存储，元素无序 D．顺序方式存储，元素有序 答案：D

16. 用二分（对半）查找表的元素的速度比用顺序法( )

A． 必然快 B. 必然慢 C. 相等 D. 不能确定

答案：D

17. 具有12个关键字的有序表，折半查找的平均查找长度（ ） A. 3.1 B. 4 C. 2.5 D. 5 答案：A

56

18. 折半查找的时间复杂性为（ ）

A. O（n2） B. O（n） C. O（nlogn） D. O（logn） 答案：D

19．当采用分块查找时，数据的组织方式为 ( )

A．数据分成若干块，每块内数据有序

B．数据分成若干块，每块内数据不必有序，但块间必须有序，每块内最大（或最小）的数据组成索引块

C. 数据分成若干块，每块内数据有序，每块内最大（或最小）的数据组成索引块 D. 数据分成若干块，每块（除最后一块外）中数据个数需相同 答案：B

20. 二叉查找树的查找效率与二叉树的( （1）)有关, 在 (（2）)时其查找效率最低【武汉交通科技大学1996 一、2(4分)】

(1): A. 高度 B. 结点的多少 C. 树型 D. 结点的位置 (2): A. 结点太多 B. 完全二叉树 C. 呈单枝树 D. 结点太复杂。 答案：（1）C (2) C

21．如果要求一个线性表既能较快的查找，又能适应动态变化的要求，则可采用( )查找

法。

A. 分块查找 B. 顺序查找 C. 折半查找 D. 基于属性 答案：A

22. 设有一组记录的关键字为{19，14，23，1，68，20，84，27，55，11，10，79}，用链 地址法构造散列表，散列函数为H（key）=key MOD 13,散列地址为1的链中有（ ）个 记录。

A．1 B. 2 C. 3 D. 4 答案：D

23. 下面关于哈希(Hash，杂凑)查找的说法正确的是( )

A．哈希函数构造的越复杂越好，因为这样随机性好，冲突小 B．除留余数法是所有哈希函数中最好的

C．不存在特别好与坏的哈希函数，要视情况而定

D．若需在哈希表中删去一个元素，不管用何种方法解决冲突都只要简单的将该元素删去即可 答案： C

24. 若采用链地址法构造散列表，散列函数为H（key）=key MOD 17，则需 (（1）) 个链

表。这些链的链首指针构成一个指针数组，数组的下标范围为 (（2）) （1） A．17 B. 13 C. 16 D. 任意 （2） A．0至17 B. 1至17 C. 0至16 D. 1至16 答案：（1）A （2）C

25. 设哈希表长为14，哈希函数是H(key)=key,表中已有数据的关键字为15，38，61，

84共四个，现要将关键字为49的结点加到表中，用二次探测再散列法解决冲突，则放入的位置是( )

A．8 B．3 C．5 D．9 答案：D

26. 哈希查找中k个关键字具有同一哈希值，若用线性探测法将这k个关键字对应的记录存 入哈希表中，至少要进行( )次探测。

57

A． k B. k+1 C. k(k+1)/2 D.1+k(k+1)/2 答案：C

27. 散列表的地址区间为0-17,散列函数为H(K)=K mod 17。采用线性探测法处理冲突，并将

关键字序列26，25，72，38，8，18，59依次存储到散列表中。 （1）元素59存放在散列表中的地址是（ ）。

A． 8 B. 9 C. 10 D. 11 （2）存放元素59需要搜索的次数是（ ）。

A． 2 B. 3 C. 4 D. 5 答案：（1）D （2）C

28. 设哈希表长m＝14，哈希函数H（key）＝key％11。表中已有4个结点： addr(15)=4 addr(38)=5 addr(61)=6 addr(84)=7

其余地址为空，如果用二次探测再散列处理冲突，关键字为49的结点的地址是：（ ） A. 8 B .3 C. 5 D. 9 答案：D

29. 外排序是指：（ ）

A. 在外存上进行的排序方法 B .不需要使用内存的排序方法

C. 数据里很大，需要人工干预的排序方法

D. 排序前后数据在外存，排序时数据调入内存的排序方法 答案：D

30. 在内部排序中，排序不稳定的有：( )

A. 插入排序 B .冒泡排序 C. 快速排序 D. 归并排序 答案：C

31. 有一个长度为12的有序表，按二分查找法对该表进行查找，在表内各元素等概率情况下查找成功所需的平均比较次数为：( )

A. 35/12 B .37/12 C. 39/12 D. 43/12 答案：B

32. 有一个有序表为{1，3，9，12，32，41，45，62，75，77，82，95，100}，当二分查找值82为的结点时，几次比较后查找成功？

A. 1 B .2 C. 4 D. 8 答案：C

33. 采用顺序查找方法查找长度为n的线性表时，每个元素的平均查找长度为：( )

A. n B .n/2 C. (n+1)/2 D. (n-1)/2 答案：C

34.散列函数有一个共同性质，即函数值应当以（ ① ）取其值域的每个值。

设哈希地址空间为0～m-1,k为关键字，用p去除k，将所得的余数作为k的散列地址，即H(k)=k MOD p，为了减少发生冲突的频率，一般取p为（ ② ） ①：A.最大概率 B.最小概率 C.平均概率 D.同等概率

②：A.小于m的最大奇数 B.小于m的最大偶数 C.m D.小于m的最大素数

58

E.小于m的最大合数 F.大于m的最小素数。 答案：①：D ②：D

35.从供选择的答案中选出正确答案填入（）内。

散列存储的基本思想是根据（ ① ）来决定（ ②），冲突指的是（ ③ ），（ ④ ）越大，发生碰撞的可能性就越大。处理冲突的两类主要方法是（ ⑤ ）。

①②④：Ａ．存储地址 B.元素的序号 C.元素的个数 D.关键码值 E.非码属性 F.平均检索长度 G.负载因子 H.散列表空间

：A.两个元素具有相同序号 B.两个元素的关键码值不同，而非码属性相同。 C.不同关键码值对应相同的存储地址 D.负载因子过大 E.数据元素过多。 ：A.线性探测法和双散列函数法 B.建溢出区法和不建溢出区法 C.除余法和折叠法 D.拉链法和开地址法 答案：①：D ②:A ③: C ④: G ⑤:D

36．设哈希（Hash）表的地址范围为0～17，哈希函数为：H（K）＝K MOD 16。 K为关键字，用线性探测法再散列法处理冲突，输入关键字序列： （10，24，32，17，31，30，46，47，40，63，49） 造出Hash表，试回答下列问题： 画出哈希表的示意图；

若查找关键字63，需要依次与哪些关键字进行比较？ 若查找关键字60，需要依次与哪些关键字比较？

假定每个关键字的查找概率相等，求查找成功时的平均查找长度。

解答： （1）画表如下： 0 1 2 3 4 5 6 7 8 下标 T[0…10] 探测次数 9 10 0 1 11 2 12 3 13 4 14 5 6 15 7 16 8 17 9 10 33 1 1 1 13 12 34 38 27 22 1 3 4 1 7 8 32 17 63 49 24 40 10 30 31 46 47 （2） 查找63,首先要与H(63)=63=15号单元内容比较，即63 vs 31 ,no; 然后顺移，与46,47,32,17,63相比，一共比较了6次！

（3）查找60,首先要与H(60)=60=12号单元内容比较，但因为12号单元为空（应当有空标记），所以应当只比较这一次即可。 （4） “63”需要6次，“49”需要3次，“40”需要2次，“46”需要3次，“47”需要3次，

所以ASL=1/11（6＋2＋3×3）＝17/11=1.5454545454≈1.55

37. 设散列表长度为11，散列函数h(x)=x,给定的关键字序列为：1，13，13，34，38，33，27，试画出分别用拉链法和线性探测法解决冲突时所构造的散列表，并求出在等概率情况下，这两种方法查找成功和失败时的平均查找长度。请问装填因子的值是什么?

答：

(1)拉链法如下图： (2)线性探测法如下图：

59

T[0..10] 0 1 2 3 4 5 6 7 ∧ ∧ ∧ ∧ → 33 → 22 →∧ → 1 → 12 →34→ ∧ → 13 →∧

→ 38 → 27 →∧ 8 ∧

9 ∧

10 ∧

用拉链法的查找成功平均查找长度为：

ASLsucc=(1*4+2*3+3*1)/8=1.625 查找失败时平均查找长度为：

ASLunsucc=(2+3+1+0+0+0+2+0+0+0+0)/11=0.73 用线性探查法查找成功时平均查找长度为： ASLsucc=(1+1+1+3+4+1+7+8)/8=3.25 查找失败时平均查找长度为：

ASLunsucc=(9+8+7+6+5+4+3+2+1+1+1)/11=4.3

装填因子α拉链=4/11=0.36 α线性探查=8/11=0.73

38．选取散列函数H（key）=（3*key），用线性探测法处理冲突，对下列关键码序列构造一个散列地址空间为0～10，表长为11的散列表，{22，41，53，08，46，30，01，31，66}。

解答：由题意知，m=11(刚好为素数)

则(22*3)=6??0 链接指针 地址 值 (41*3)=11??2 0 22 1 (53*3)=14??5 1 66 (08*3)=2??2 2 41 3 (46*3)=12??6 3 08 4,7 (30*3)=8??2 4 30 (01*3)=0??3 5 53 (31*3)=8??5 6 46 (66*3)=9??0 7 01 8 31 9 10 22 0 66 1

41 2

8 3

30 4

53 5

46 6

1 7

31 8

9

10

60

1 3 4，7

39.假定有k个关键字互为同义词，若用线性探查法把这些同义词存入散列表中，至少要进行多少次探查?

答：至少要进行1+2+3...+k-1+k次探查。

也就是说，在散列表的一连串连续空间内，第一个关键字只需探查一次，第二个就要探查2次，如此这般，第k个关键字就要探查k次才能找到位置存放。所以至少要把它们全加起来才够。

40．在散列检索中，“比较”操作一般也是不可避免的。（ ） 答：对。

41．哈希函数的选取平方取中法最好。 （ ）

答：错。不能说哪种哈希函数的选取方法最好，各种选取方法有自己的适用范围。

42．负载因子 (装填因子)是散列表的一个重要参数，它反映散列表的装满程度。（ ） 答：对

43. 哈希表的结点中只包含数据元素自身的信息，不包含任何指针。（ ） 答：错。哈希表的结点中可以包括指针，指向其元素。

44．用向量和单链表表示的有序表均可使用折半查找方法来提高查找速度。（ ） 答：错。单链表不能使用折半查找方法。

45. 在索引顺序表中，实现分块查找，在等概率查找情况下，其平均查找长度不仅与表中元素个数有关，而且与每块中元素个数有关。（ ） 答：对。

46．在查找树（二叉树排序树）中插入一个新结点，总是插入到叶结点下面。 （ ） 答：错。按插入后中序遍历是递增序列的原则，若某结点只有右子树，而插入元素的关键字小于该结点的关键字，则会插入到该结点的左侧，成为其左孩子。这种插入就不是插入到叶子下面。

47．完全二叉树肯定是平衡二叉树。（ ）

答：错。从平衡因子定义看，完全二叉树任一结点的平衡因子的绝对值确实是小于等于1。但是，平衡二叉树本质上是二叉排序树，完全二叉树不一定是排序树。故不能说完全二叉树是平衡二叉树。

48．对一棵二叉排序树按前序方法遍历得出的结点序列是从小到大的序列。（ ） 答：错。按中序遍历得出的节点序列是从小到大的序列。

49．二叉树中除叶结点外, 任一结点X，其左子树根结点的值小于该结点（X）的值；其右子树根结点的值≥该结点（X）的值,则此二叉树一定是二叉排序树。（ ）

答：错。某结点的左子树根结点不一定是它的中序前驱，其右子树根结点也不一定是它的中序后继。

50．有n个数存放在一维数组A[1..n]中，在进行顺序查找时，这n个数的排列有序或无序其平均查找长度不同。 （ ） 答：错。在等概率下，查找成功时的平均查找长度相同，查找失败时的平均查找长度不相同。

51. 在任意一棵非空二叉排序树中，删除某结点后又将其插入，则所得二排序叉树与原二排

61

序叉树相同。（ ）

答：错。只有被删除结点是叶子结点时命题才正确

52.在各种查找法中，平均查找长度与结点个数n无关的查找方法是 哈希表查找法 。

53.二分查找的存储结构仅限于顺序存储结构而且是顺序的。

54.在哈希函数H(key)=key%p中，p应该取 素数。

55.若一个待哈希存储的线性表长度为n，用于哈希的哈希长度为m，则m应大于等于n，装填因子为 n/m 。

56.在哈希存储中，装填因子的值约达，存取元素时发生冲突的可能性就 越大，当装填因子的值越小，存取元素时发生冲突的可能性就 越小。

57.假定有K个关键字互为同义词，若用线性探测再哈希法把这K个关键字存入哈希表中，至少要进行k(k+1)/2次探测。

58.构造哈希函数的方法有 直接定址法、数字分析法、除留余数法等。

59. 设有序表为(a,b,c,e,f,g,i,j,k,p,q),请分别画出对给定值b,g和n进行折半查找的过程。 答：

(1)查找b的过程如下(其中方括号表示当前查找区间，圆括号表示当前比较的关键字)

下标： 1 2 3 4 5 6 7 8 9 10 11 12 13 第一次比较： [a b c d e f (g) h i j k p q] 第二次比较： [a b (c) d e f] g h i j k p q 第三次比较： [a (b)]c d e f g h i j k p q 经过三次比较，查找成功。

(2)g的查找过程如下：

[a b c d e f (g) h i j k p q] 一次比较成功。

(3)n的查找过程如下：

下标： 1 2 3 4 5 6 7 8 9 10 11 12 13 第一次比较： [a b c d e f (g) h i j k p q] 第二次比较： a b c d e f g [h i (j) k p q] 第三次比较： a b c d e f g h i j [k (p) q] 第四次比较： a b c d e f g h i j [k] p q] 经过四次比较，查找失败。

3．7排序

二、课后部分习题答案 3-30

62

本文来源：https://www.bwwdw.com/article/d8qd.html