数据结构期末复习题

第一次作业——绪论

1.数据结构被形式地定义为(D,R),其中D是（ B ）的有限集。

A.算法

B.数据元素

C.数据操作

D.逻辑结构

2.数据结构是一门研究非数值计算的程序设计问题中计算机的（ A ）以及它们之间的关系和运算等的学科。

A.数据元素

B.计算方法

C.逻辑存储

D.数据映象

3.下列几种算法时间复杂度中，最大的是（C ）

A.O(nlog2n)

B.O(n)

C.O(n2)

D.O(1)

4.下面程序段的时间复杂度是_______。

for (i=0;i<n;i++)

for (j=0;j<m;j++)

A[i][j]=0;

答案：

(1) O(m*n)

5.下面程序段的时间复杂度是_______。

i=s=0

While(s<n)

{

i++; /* i=i+1 */

s+=i; /* s=s+i */

}

答案：

6.下面程序段的时间复杂度是_______。

s=0;

for (i=0;i<n;i++)

for (j=0;j<n;j++)

s+=B[i][j];

sum=s;

答案：

7.下面程序段的时间复杂度是_______。

i=1;

While (i<=n)

i=i*3;

答案：

8.根据数据元素之间关系的不同特性，通常将数据结构划分为集合、线性结构、（）和图结构四类基本结构。

答案： 树型结构

9.下列关于数据的逻辑结构的叙述中，哪一个是正确的 A 。

A. 数据的逻辑结构是数据间关系的描述

B. 数据的逻辑结构反映了数据在计算机中的存储方式

C. 数据的逻辑结构分为顺序结构和链式结构

D. 数据的逻辑结构分为静态结构和动态结构

10.在数据结构中，从逻辑上可以把数据结构分为 D 。

A. 动态结构和静态结构

B. 紧凑结构和非紧凑结构

C. 内部结构和外部结构

D. 线性结构和非线性结构

11.数据类型是值的（）和定义在这个值集上的一组操作的总称。

答案:集合

12. 算法分析的主要内容是 C 。

A. 正确性

B. 可读性和稳定性

C. 空间复杂性和时间复杂性

D. 简单性

13.求一个n阶二维数组的所有元素之和，用C/C++语言描述该算法，并给出算法的时间复杂度。

答案：

int sumOfArray(int arr[][3], int n) {int sum = 0;for (int i = 0; i < n; i++) {for (int j = 0; j < n; j++) {sum += arr[i][j];}}return sum;}时间复杂度是O(n²)

14. 对于输入的任意n个整数输出其中的最大和最小元素，用C/C++语言描述该算法，并给出算法的时间复杂度。

void findMaxMin(int arr[], int n) {int maxVal = arr[0];int minVal = arr[0];for (int i = 1; i < n; i++) {if (arr[i] > maxVal) {maxVal = arr[i];}if (arr[i] < minVal) {minVal = arr[i];}}cout << "最大元素是：" << maxVal << endl;cout << "最小元素是：" << minVal << endl;}时间复杂度是O(n)

第二次作业——线性表，链表

1.线性表是( A ) 。

A. 一个有限序列，可以为空

B. 一个有限序列，不能为空

C. 一个无限序列，可以为空

D. 一个无序序列，不能为空

2.对顺序存储的线性表，设其长度为n，在任何位置上插入或删除操作都是等概率的。插入一个元素时平均要移动表中的（ A ）个元素。

A. n/2

B. (n+1)/2

C. (n –1)/2

D. n

3.线性表采用链式存储时，其地址( D ) 。

A. 必须是连续的

B. 部分地址必须是连续的

C. 一定是不连续的

D. 连续与否均可以

4.用链表表示线性表的优点是（ C ）。

A. 便于随机存取

B. 花费的存储空间较顺序存储少

C. 便于插入和删除

D. 数据元素的物理顺序与逻辑顺序相同

5.某链表中最常用的操作是在最后一个元素之后插入一个元素和删除最后一个元素，则采用( D )存储方式最节省运算时间。

A. 单链表

B. 双链表

C. 单循环链表

D. 带头结点的双循环链表

6.循环链表的主要优点是( ) 。

A.不再需要头指针了

B.已知某个结点的位置后，能够容易找到他的直接前趋

C.在进行插入、删除运算时，能更好的保证链表不断开

D.从表中的任意结点出发都能扫描到整个链表

7.若某线性表中最常用的操作是在最后一个元素之后插入一个元素和删除第一个元素，则采用（D ）存储方式最节省运算时间。

A. 单链表

B. 仅有头指针的单循环链表

C. 双链表

D.仅有尾指针的单循环链表

8.一个向量(一种顺序表)第一个元素的存储地址是100，每个元素的长度为2，则第5个元素的地址是____B___。

A. 110

B. 108

C. 100

D. 120

9.不带头结点的单链表head为空的判定条件是___A___。

A.head = = NULL;

B.head->next = = NULL;

C.head->next = = head;

D.head! = NULL;

10.在循环双链表的p所指结点之后插入s所指结点的操作是____D_。

A.p->right=s; s->left=p; p->right->left=s; s=->right=p->right;

B.p->right=s; p->right->left=s; s->left=p; s->right=p->right;

C.s->left=p; s->right= p->right; p->right=s; p->right->left=s;

D.s->left=p; s->right=p->right; p->right->left=s; p->right=s;

插4删2// 保存p的前驱结点和后继结点指针struct Node *prev = p->left;struct Node *next = p->right;// 修改前驱结点的后继指针指向p的后继结点prev->right = next;// 修改后继结点的前驱指针指向p的前驱结点next->left = prev;

11.在一个长度为n的向量中的第i个元素(1≤i≤n)之前插入一个元素时，需向后移动_____个元素。

答案：n-i+1

12.在一个长度为n的向量中删除第i个元素(1≤i≤n)时，需向前移动_____个元素。

答案：n-i

13.有一个单链表（不同结点的数据域值可能相同），其头指针为head，编写一个函数计算数据域为x的结点个数。

答案：

#include <stdio.h>#include <stdlib.h>// 定义链表节点结构体typedef struct ListNode {int data;struct ListNode *next;} ListNode;// 创建新节点的辅助函数ListNode* createNode(int val) {ListNode* newNode = (ListNode*)malloc(sizeof(ListNode));newNode->data = val;newNode->next = NULL;return newNode;}// 计算数据域为 x 的结点个数int countOccurrences(ListNode* head, int x) {int count = 0;ListNode* current = head;while (current != NULL) {if (current->data == x) {count++;}current = current->next;}return count;}// 打印链表的辅助函数void printList(ListNode* head) {ListNode* current = head;while (current != NULL) {printf("%d ", current->data);current = current->next;}printf("\n");}// 释放链表内存的辅助函数void freeList(ListNode* head) {ListNode* current = head;while (current != NULL) {ListNode* next = current->next;free(current);current = next;}}int main() {// 创建一个单链表示例ListNode* head = createNode(1);head->next = createNode(2);head->next->next = createNode(3);head->next->next->next = createNode(2);head->next->next->next->next = createNode(5);head->next->next->next->next->next = createNode(2);int x = 2;int count = countOccurrences(head, x);// 输出结果printf("链表：");printList(head);printf("数据域为 %d 的结点个数: %d\n", x, count);// 释放链表内存freeList(head);return 0;}

14.有一个有序单链表（从小到大排序），表头指针为head，编写一个函数向该单链表中插入一个元素为x的结点，使插入后该链表仍然有序。

答案：

#include <stdio.h>#include <stdlib.h>// 定义链表节点结构体typedef struct ListNode {int data;struct ListNode *next;} ListNode;// 创建新节点的辅助函数ListNode* createNode(int val) {ListNode* newNode = (ListNode*)malloc(sizeof(ListNode));newNode->data = val;newNode->next = NULL;return newNode;}// 将元素 x 插入到有序链表中ListNode* insertSorted(ListNode* head, int x) {ListNode* newNode = createNode(x);if (head == NULL || x <= head->data) {newNode->next = head;return newNode;}ListNode* current = head;while (current->next != NULL && current->next->data < x) {current = current->next;}newNode->next = current->next;current->next = newNode;return head;}// 打印链表的辅助函数void printList(ListNode* head) {ListNode* current = head;while (current != NULL) {printf("%d ", current->data);current = current->next;}printf("\n");}// 释放链表内存的辅助函数void freeList(ListNode* head) {ListNode* current = head;while (current != NULL) {ListNode* next = current->next;free(current);current = next;}}int main() {// 创建一个有序单链表示例ListNode* head = createNode(1);head->next = createNode(3);head->next->next = createNode(4);head->next->next->next = createNode(7);int x = 5;head = insertSorted(head, x);// 输出链表printf("链表：");printList(head);// 释放链表内存freeList(head);return 0;}

15.编写一个函数将一个头指针为a的单链表A分解成两个单链表A和B，其头指针分别为a和b，使得A链表中含有原链表A中序号为奇数的元素，而B链表中含有原链表A中序号为偶数的元素，且保持原来的相对顺序。

答案：

#include <stdio.h>#include <stdlib.h>// 定义链表节点结构体typedef struct ListNode {int data;struct ListNode *next;} ListNode;// 创建新节点的辅助函数ListNode* createNode(int val) {ListNode* newNode = (ListNode*)malloc(sizeof(ListNode));newNode->data = val;newNode->next = NULL;return newNode;}// 将一个链表分解成两个链表void splitList(ListNode* a, ListNode** b) {if (a == NULL) {*b = NULL;return;}ListNode* odd = a;  // 奇数链表的头节点ListNode* even = a->next;  // 偶数链表的头节点*b = even;  // 将偶数链表的头节点赋值给 b// 遍历链表，将奇数和偶数节点分开while (even != NULL && even->next != NULL) {odd->next = even->next;  // 连接奇数节点odd = odd->next;even->next = odd->next;  // 连接偶数节点even = even->next;}odd->next = NULL;  // 结束奇数链表}// 打印链表的辅助函数void printList(ListNode* head) {ListNode* current = head;while (current != NULL) {printf("%d ", current->data);current = current->next;}printf("\n");}// 释放链表内存的辅助函数void freeList(ListNode* head) {ListNode* current = head;while (current != NULL) {ListNode* next = current->next;free(current);current = next;}}int main() {// 创建一个单链表示例ListNode* a = createNode(1);a->next = createNode(2);a->next->next = createNode(3);a->next->next->next = createNode(4);a->next->next->next->next = createNode(5);ListNode* b = NULL;splitList(a, &b);// 输出 A 链表printf("A 链表：");printList(a);// 输出 B 链表printf("B 链表：");printList(b);// 释放链表内存freeList(a);freeList(b);return 0;}

16.已知两个顺序表A和B分别表示两个集合，其元素递增排列，编写一个函数求出A和B的交集C，要求C同样以元素递增的顺序表形式存储。

答案：

#include <stdio.h>#include <stdlib.h>// 函数原型声明int* intersect(int A[], int sizeA, int B[], int sizeB, int *returnSize);int main() {int A[] = {1, 2, 3, 4, 5};int B[] = {3, 4, 5, 6, 7};int sizeA = sizeof(A) / sizeof(A[0]);int sizeB = sizeof(B) / sizeof(B[0]);int returnSize;int *C = intersect(A, sizeA, B, sizeB, &returnSize);// 打印交集printf("Intersection: ");for (int i = 0; i < returnSize; i++) {printf("%d ", C[i]);}printf("\n");// 释放分配的内存free(C);return 0;}int* intersect(int A[], int sizeA, int B[], int sizeB, int *returnSize) {int *C = (int *)malloc((sizeA < sizeB ? sizeA : sizeB) * sizeof(int));int i = 0, j = 0, k = 0;while (i < sizeA && j < sizeB) {if (A[i] < B[j]) {i++;} else if (B[j] < A[i]) {j++;} else {if (k == 0 || C[k-1] != A[i]) {  // 避免添加重复的元素C[k++] = A[i];}i++;j++;}}*returnSize = k;return C;}

第三次作业——栈和队列

1.若已知一个栈的入栈序列是1，2，3，…，n，其输出序列为p1，p2，p3，…，pn，若p1=n，则pi为( C )。

A. i

B. n=i

C. n-i+1

D.不确定

2.栈和队列的共同点是( C )。

A. 都是先进后出

B. 都是先进先出

C. 只允许在端点处插入和删除元素

D.没有共同点

3.若依次输入数据元素序列{a，b，c，d，e，f，g}进栈，出栈操作可以和入栈操作间隔进行，则下列哪个元素序列可以由出栈序列得到？( A )

A. {d，e，c，f，b，g，a}

B.{ f，e，g，d，a，c，b}

C. {e，f，d，g，b，c，a}

D. { c，d，b，e，g，a，f}

4.一个栈的入栈序列是1,2,3,4,5，则下列序列中不可能的出栈序列是( B )

A.2,3,4,1,5

B.5,4,1,3,2

C.2,3,1,4,5

D.1,5,4,3,2

5.队列操作的原则是( A )

A. 先进先出

B. 后进先出

C. 只能进行插入

D. 只能进行删除

6.判断一个循环队列QU ( m0为最大队列长度(以元素为单位)，front和rear分别为队列的队头指针和队尾指针 ) 为空队列的条件是( A )。

A.QU->front == QU->rear

B.QU->front != QU-> rear

C.QU->front == (QU->rear+1) % m0

D.QU->front != (QU->rear+1) % m0

7.判断一个循环队列QU ( m0为最大队列长度(以元素为单位)，front和rear分别为队列的队头指针和队尾指针 )为满队列的条件是( C )。

A. QU->front==QU->rear

B. QU->front!=QU-> rear

C. QU->front==(QU->rear+1) % m0

D.QU->front!=(QU->rear+1) % m0

8.在少用一个元素空间的循环队列QU ( m0为最大队列长度(以元素为单位)，front和rear分别为队列的队头指针和队尾指针 ) 中，当队列非满时，若删除一个数据元素，则其队头指针front的变化是( D )。

A. QU->front==(QU->rear+1) % m0

B. QU->front==(QU->front+1)

C. QU->front==(QU->rear+1)

D.QU->front==(QU->front+1) % m0

9.在少用一个元素空间的循环队列QU ( m0为最大队列长度(以元素为单位)，front和rear分别为队列的队头指针和队尾指针 ) 中，当队列非空时，若插入一个新的数据元素，则其队尾指针rear的变化是( B)。

A.QU->rear==(QU->front+1) % m0

B.QU->rear==(QU->rear+1) % m0

C.QU->rear==(QU->front+1)

D.QU->rear==(QU->rear+1)

10.假设顺序栈的定义为：

typedef struct {

selemtype *base; /* 栈底指针*/

selemtype *top; /* 栈顶指针*/

int stacksize; /* 当前已分配的存储空间,以元素为单位*/

}sqstack;

变量st为sqstack型，则栈st为空的判断条件为（ D ）。

A. st.base == NULL

B. st.top == st.stacksize

C. st.top-st.base>= st.stacksize

D. st.top == st.base

二. 填空题（共4题，20分）

11.线性表、栈、队列都是线性结构，可以在线性表的_________位置插入和删除元素，对于栈只能在_________位置插入和删除元素，对于队只能在________位置插入和只能在_________位置删除元素。

答案：(1) 任何

(2) 栈顶

(3) 队尾

(4) 队头

12.用S表示入栈操作，X表示出栈操作，若元素入栈顺序为1,2,3,4, 为了得到1,3,4,2出栈顺序相应的S和X操作串为______________________。

答案：SXSSXSXX

13.设栈S和队列Q的初始状态皆为空，元素a1，a2，a3，a4，a5和a6依次通过一个栈，一个元素出栈后即进入队列Q，若6个元素出队列的顺序是a3，a5，a4，a6，a2，a1则栈S至少应该容纳个元素。

答案： 4

三. 判断题（共4题，20分）

15.栈和队列都是限制存取点的线性结构（ A ）

A. 对

B. 错

16.栈和队列是两种重要的线性结构（ A ）

A. 对

B. 错

17.不带头结点的单链表形式的队列，头指针F指向队列的队首结点，尾指针R指向队列的最后一个结点（ A ）

A. 对

B. 错

18.在对不带头结点的链队列作出队操作时，不会改变头指针的值。（ B ）

A. 对

B. 错

四. 简答题（共2题，10分）

19.假设以带头结点的循环链表表示队列，并且只设一个指针指向队尾元素结点(注意不设头指针)，试编写相应的队列初始化、入队列和出队列的算法。

20.利用两个栈s1，s2模拟一个队列时，如何用栈的运算来实现该队列的运算：

enqueue:插入一个元素；

dequeue:删除一个元素；

queue_empty:判定队列为空。

第四次作业——数组、二叉树

1.二维数组A[10..20,5..10]采用行序为主序方式存储，每个元素占用4个存储单元，且A[10，5]的存储地址是1000，则A[18，9]的存储地址是（ A ）

A. 1208

B. 1212

C. 1368

D. 1364

2.若对n阶对称矩阵A[1..n,1..n]以行序为主序方式将其下三角形的元素（包括主对角线上所有元素）依次存放于一维数组中，则在B中确定aij (i<j)的位置k的关系为（B　）。

3.下列有关二叉树的说法正确的是( B )。

A. 二叉树的度为2
B. 一棵二叉树度可以小于2
C. 二叉树中至少有一个结点的度为2
D. 二叉树中任一个结点的度都为2

4.假定在一棵二叉树中，双分支结点数为15，单分支结点数为30个，则叶子结点数为( B )

A. 15
B. 16
C. 17
D. 47

5.设a、b为一棵二叉树上的两个结点。在中序遍历时，a在b前面的条件是( B )。

A. a在b的右方
B. a在b的左方
C. a是b的祖先
D. a是b的子孙

6.以下说法正确的是( C )

A.若一个树叶是某二叉树前序遍历序列中的最后一个结点，则它必是该子树后序遍历序列中的最后一个结点。
B.若一个树叶是某二叉树前序遍历序列中的最后一个结点，则它必是该子树中序遍历序列中的最后一个结点。
C.在二叉树中，具有两个子女的父结点，在中序遍历序列中，它的后继结点最多只能有一个子女结点。
D.在二叉树中，具有一个子女的父结点，在中序遍历序列中，它没有后继子女结点。

7.树的基本遍历策略可分为先根遍历和后根遍历，二叉树的基本遍历策略可分为先序遍历、中序遍历和后序遍历。这里，我们把由树转化得到的二叉树叫做这棵树对应的二叉树。结论( A )是正确的。

A. 树的先根遍历序列与其对应的二叉树先序遍历序列相同。

B. 树的后序遍历序列与其对应的二叉树后序遍历序列相同。

C. 树的先根遍历序列与其对应的二叉树中序遍历序列相同。

D.以上都不对

8.深度为k的二叉树，结点个数最多为（ B）

9.具有10个叶子结点的哈夫曼树中，总共结点个数为( A )

A. 19

B. 20

C. 18

D. 10

2*10-1

10. 以下说法错误的是( B )。

A. 存在这样的二叉树，对它采用任何次序遍历其结点访问序列均相同。

B. 二叉树是树的特殊情形。

C. 在二叉树只有一棵子树的情况下也要明确指出该子树是左子树还是右子树

D. 由树转换成二叉树，其根结点的右子树总是空的。

11. 以下说法正确的是( C )。

A.若一个树叶是某二叉树前序遍历序列中的最后一个结点，则它必是该子树后序遍历序列中的最后一个结点。

B.若一个树叶是某二叉树前序遍历序列中的最后一个结点，则它必是该子树中序遍历序列中的最后一个结点。

C.在二叉树中，具有两个子女的父结点，在中序遍历序列中，它的后继结点最多只能有一个子女结点。

D.在二叉树中，具有一个子女的父结点，在中序遍历序列中，它没有后继子女结点。

12.用顺序存储的方法将完全二叉树中的所有结点逐层存放在数组R[1..n]中，结点R[i]若有左子女，则左子女是结点( B )。

A. R[2i+1]

B. R[2i]

C. R[i/2]

D. R[2i-1]

13.具有n个结点的二叉树，采用二叉链表存储，共有个空链域。

答案：n+1

14.对于一棵具有n个结点的二叉树，当进行链接存储时，其二叉链表中指针域总数为个，其中个用于链接孩子结点，

个空闲着。

答案：

(1) 2n

(2) n-1

(3) n+1

15.二叉树的线索化实质是将二叉链表中的_______改为_________。

答案：

(1) 空指针

(2) 线索

16.8层完全二叉树至少有个结点，拥有100个结点的完全二叉树的最大层数为。

答案：

(1) 128

(2) 7

17.二叉树通常有存储结构和存储结构。

答案：

(1) 顺序

(2) 链式

18.遍历一棵二叉树包括访问根结点、遍历左子树和遍历三个方面。

答案：

(1) 右子树

19.对于一个具有n个结点的二叉树，当它为一棵二叉树时具有最小高度

答案：完全

20. (简答题)含有60个叶子结点的二叉树的最小高度是多少？

21.已知一棵二叉树的中序序列为CBEDAHGIJF、后序序列为CEDBHJIGFA，给出该二叉树的树形表示。和各个字符的哈夫曼树编码。

23.假设二叉树中的每个结点值为单个字符，采用二叉链表存储结构存储。设计一个算法，求二叉树中最小值的结点值。

第五次作业——图

1.在一个图中，所有顶点的度数之和等于所有边数的0.5倍，在一个有向图中，所有顶点的入度之和等于所有顶点出度之和的( B )倍。

A. 0.5

B. 1

C. 2

D. 3

2.具有n个顶点的有向图最多有( B )条边。

3.在一个无向图中，若两个顶点之间的路径长度为k，则该路径上的顶点数为( B )。

A. k

B. k+1

C. k+2

D. 2k

4.采用邻接表存储的图的深度优先遍历类似于二叉树的( B )。

A. 中序遍历

B. 先序遍历

C. 后序遍历

D. 按层次遍历

5.一个图中包含k个连通分量，若按深度优先(DFS)搜索方法访问所有结点，则必须调用( B )次深度优先遍历算法。

A. 1

B. k

C. k-1

D. k+1

填空题

一个连通图的是一个极小连通子图。

答案：生成树

7.在无向图G的邻接矩阵A中，若A[i][j]等于1，则A[j][i]等于。

答案： 1

8.遍历图的基本方法有深度优先搜索和广度优先搜索，其中是一个递归过程。答案：深度优先搜索

9.具有n个顶点的无向连通图至少需要条边。

答案：n-1

10. 若无向图中任意两个不同的顶点间都有路径，则称该图为_______。答案：连通图

11.有向图G如下图所示，它的两个拓扑排序序列分别为______和______。

答案：(1) V1,V2,V3,V6,V5,V4

(2) V1,V3,V2,V6,V5,V4

三判断题：

12.在n个结点的无向图中，若边数 > n-1，则该图必是连通图。

A. 对

B. 错

13.邻接表法只能用于有向图的存储，而邻接矩阵法对于有向图和无向图的存储都适用。

A. 对

B. 错

14.图的深度优先搜索序列和广度优先搜索序列不一定是唯一的。

A. 对

B. 错

15.图的邻接矩阵中矩阵元素的行数只与顶点个数有关。

A. 对

B. 错

16.图的邻接矩阵中矩阵中非零元素个数与边数有关。

A. 对

B. 错

17.若一个图的邻接矩阵为对称矩阵，则该图必为无向图。

A. 对

B. 错

18.给出下列递归过程的执行结果。

void unknown(int w) {

if (w) {

unknown(w-1);

for (int i=1;i<=w;i++) cout<<w;

cout<<endl;

}

调用语句：unknown(4);

答案：

333

4444

19.假设图G采用邻接表存储，试设计一个算法，判断无向图G 是否为一棵树。若为树，返回真；否则返回假。

20.假设图G采用邻接表存储，设计一个算法输出图G中从顶点uð v的一条简单路径（假设图G中从顶点uð v至少有一条简单路径）。

第六次作业——查找与排序

1.顺序查找法适合于存储结构为（B ）的线性表。

A.散列存储

B.顺序存储或链接存储

C.压缩存储

D.索引存储

2.采用折半查找方法查找长度为n的线性表时，每个元素的平均查找长度为（ D）。

A.O(n2)

B.O(nlog2n)

C.O(n)

D.O(log2n)

3.采用顺序查找方法查找长度为n的线性表时，每个元素的平均查找长度为（ C）。

A.n

B.n/2

C.(n+1)/2

D.(n-1)/2

4.10个元素的有序表，等概率条件下折半查找成功的平均查找长度是（ A）。

A.2.9

B.3

C.4.5

D.5.0

5.在所有排序方法中，关键字比较次数与记录的初始排列次序无关的是（D ）。

A 希尔排序

B 起泡排序

C 插入排序

D 选择排序

6.一组记录的排序码为(46,79,56,38,40,84)，则利用堆排序的方法建立的初始堆为（ B）。

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

7.下列算法中（D ）中算法占用的辅助空间最多。

A 堆排序

B SHELL排序

C 快速排序

D 归并排序

8.下列排序算法中，稳定的是（ B）。

A 直接选择排序

B 直接插入排序

C 快速排序

D 堆排序

9.设有序顺序表中的元素依次为017，094，154，170，275，503，509，512，553，612，677，765，897，908。试画出对其进行折半查找时做性能分析用的判定树，并计算等概率条件下查找成功时的平均查找长度和查找不成功时的平均查找长度。

10.已知待排序记录的关键字序列如下：（19，7，25，14，33，18）。请写出用快速排序时

每一趟的排序结果。

答案：

(1)[18 7 14]19[33 25]

(2)[14 7]18 19[33 25]

(3)7 14 18 19[33 25]

(4)7 14 18 19 25 33

11.给出一组关键字序列：12，8，9，15，7，16，13，4，10，20，11，14，请给出用快速排序、堆排序、希尔排序（渐减增量序列d=6,3,2,1）各自的第一趟、第二趟排序结果。

答案：1)快速排序[11 8 9 10 7 4]12[13 16 20 15 14]

[4 8 9 10 7]11 12[13 16 20 15 14]

2)堆排序(大根堆)

[16 15 14 12 11 9 13 4 10 7 8 20]

[15 12 14 10 11 9 13 4 8 7 16 20 3]

3)希尔排序

[12 4 9 15 7 14 13 8 10 20 11 16]

[12 4 9 13 7 10 15 8 14 20 11 16]

12.设散列函数为H (key)=key ％ 11，散列地址空间为0～10，对关键字序列(27，13，55，32，18，49，24，38，43)用线性探测再散列解决冲突，构建散列表。现已有前4个关键字构建的散列表如下所示，请将剩余5个关键字填入表中相应的位置。