大数据结构与算法复习题

数据结构与算法复习题

一、 写出以下各词语对应的中文（英）

sequential storge structure 顺序存储结构 Abstract Data Type (ADT) 抽象数据类型 二叉排序树 Binary sort tree

queue 队列 storge structure 存储结构 time complexity 时间复杂度

线性表 Linear List 二叉树 Binary Tree Depth_First Search 深度优先搜索 singly linked lists 单链表

二、 单项选择题

1、数据结构是一门研究非数值计算的程序设计问题中数据元素的 、数据信息在计算机中的存储结构以及一组相关的运算等的课程。

A: 操作对象 Ｂ: 计算方法 Ｃ: 逻辑结构 Ｄ: 数据映象

2、某线性表最常用的运算是插入和删除,插入运算是指在表尾插入一个新元素,删除运算是指删除表头第一个元素,那么采用 存储方式最节省运算时间.。

A: 仅有头指针的单向循环链表 B: 仅有尾指针的单向循环链表 C: 单向链表 D:双向链表

3、一个栈的入栈序列是a，b，c，d，e，则栈的不可能的输出序列是____。 A: abcde B: decba C: edcba D: dceab 4、将一个递归算法改为对应的非递归算法时，通常需要使用_____。 A: 栈 B: 队列 C: 循环队列 D: 优先队列 5、关于空串，下列说法中正确的有____。

A: 空串就是空格串 B: 空串的长度可能不为零

C: 空串是零个字符的串 D: 空串的长度就是其包含的空格个数

6、二维数组A中，每个元素的长度为3个字节，行下标i从0到7，列下标j从0到9，从首地址SA开始连续存放在存储器内，该数组按行存放时，数组元素A[7][4]的起始地址为 。

A: SA+141 B: SA+144 C: SA+222 D: SA+225

实用文档

7、某二叉树的前序和后序序列正好相反，则该二叉树一定是 的二叉树。

8、下述４棵二叉树中，是完全二叉树的是： 。

Ａ: Ｂ: Ｃ: Ｄ:

9、深度为5的二叉树至多有____个结点。

A: 16 B: 32 C: 31 D: 10

10、在一个无向图中，所有顶点的度数之和等于所有边数的 倍。

A: 1/2 B: 1 C: 2 D: 4

11、采用顺序查找方法查找长度为n的线性表时，每个元素的平均查找长度为____.。

A: (n+1)/2 B: n/2 C: (n-1)/2 D: n 12、对线性表进行折半搜索时，要求线性表必须______。

A: 以数组方式存储且结点按关键码有序排列 B: 以数组方式存储

C: 以链接方式存储且结点按关键码有序排列 D: 以链接方式存储 13、下述几种排序方法中，要求内存量最大的是____。

A: 插入排序 B: 选择排序 C: 快速排序 D: 归并排序

14、采用二分查找方法查找长度为n的线性表时，每个元素的平均查找长度为____。

2

A: O（n） B: O(nlog2n) C: O(n) D: O(log2n) 15、在一个单链表中，若删除p所指结点的后续结点，则执行____。

A: p=p->next;p->next=p->next->next; B: p->next=p->next->next; C: p->next=p->next; D: p=p->next->next 16、非线性结构中，每个结点______。

A:无直接前趋 B:只有一个直接前驱和后继 C:只有一个直接前趋和个数不受的直接后继 D:有个数不受的直接前趋和后继

A: 空或只有一个结点 B: 高度等于其结点数 C: 任一结点无左孩子 D: 任一结点无右孩子

1017、设稀疏矩阵A0000020000500060按列优先顺序存储于三元组表，则结点(3，2，-5)

7000000是三元组表中的第__________项。

A:2 B:3 C:4 D:1

18、对于任何一棵二叉树T，如果其终端结点数为n0，度为2的结点数为n2，则______。

实用文档

A:n0=n2+1 B:n2=n0+1 C:n0=2n2+1 D:n2=2n0+1 19、下面程序段的时间复杂度是________。

s=0；

for(i=0；i23

A:O(1) B:O(n) C:Ｏ(n) D:O(n) 20、以下阐述不正确的是______。

A: 计算机内的数值运算依靠方程式，而非数值运算（如表、树等）则要依靠数据结构 B：数据结构是研究非数值计算的程序设计问题中计算机的操作对象以及它们之间的关系和操作等的学科

C: 数据的逻辑结构和数据的物理结构有时可以不加区分

D：同样的数据对象，用不同的数据结构来表示，运算效率可能有明显的差异 21、计算机算法指的是，它必须具备输入、输出和____。

A: 计算方法 B: 排序方法 C: 解决问题的有限运算步骤 D: 程序设计方法 22、数组与一般线性表的区别主要在____。 A: 存储方面 B: 元素类型一致 C: 逻辑结构方面 D: 不能进行插入、删除运算

23、在解决计算机主机与打印机之间速度不匹配问题时通常设置一个打印缓冲区， 该缓冲区应该是一个_____结构。

A: 栈 B: 队列 C: 数组 D: 树

24、在所有排序方法中，关键字比较的次数与记录的初始排列次序无关的是____。 A: 希尔排序 B: 起泡排序 C: 插入排序 D: 选择排序 25、二叉排序树中，键值最小的结点____。 A: 左指针一定为空 B: 右指针一定为空 C: 左、右指针均为空 D: 左、右指针均不为空

三、 在一个C语言程序中，有结构类型STUDENT的定义和结构数组allstudents的声明

如下： struct STUDENT {

char name[10]; int number; }

STUDENT allstudents[10][50];

allstudents是一个二维数组，它的每个元素都是包含name和number的结构类型。已知在C语言中，二维数组使用以行序为主序的存储结构，char类型占用1字节，int类型占用4字节。

实用文档

假定allstudents在内存中的起始存储位置是2000，请写出计算allstudents[i][j]的存储位置的算式，并计算allstudents[5][3]的存储位置。

答: (1) allstudents[i][j]的存储位置=2000+(i*50+j)*14 (2) allstudents[5][3]的存储位置=2000(5*50+3)*14=52

四、写出下列程序段的输出结果（栈的元素类型SelemType为char）

输出结果是：

五、 构造Huffman树，并求出带权路径的长度及给出Huffman编码

假设用于通信的电文由字符集{A，B，C，D，E}中的字母构成，这些字母在电文中出现的概率分别为{27，43，19，3，12}，要求：

1、 构造一棵Huffman树（左结点的权不大于右结点的权）

2、 求出带权路径的长度（2分）

3、 给出Huffman编码（左分支为\"0\"，右分支为\"1\"） 答：

实用文档

1、对应的Huffman树

043027015031121041611341192、带权路径的长度

（27*2+43*1+19*3+3*4+12*4）=214

3、Huffman编码

字符 Huffman编码 A 10 B 0 C 111 D 1100 E 1101

六、 图的应用

1、应用Prim（普里姆）算法求解下列连通图的最小生成树

要求按如下格式给出在构造最小生成树过程中顺序选出的各条边 ，并画出最小生成树 。

始顶点号 答:

终顶点号 权值

实用文档

始顶点号 0 3 5 3 1

终顶点号 3 5 2 1 4 权值 1 4 2 5 3

2、图G＝(V，E)，其中V={1,2,3,4,5,6}，Ｅ＝{<1,2>,<1,3>,<1,4>,<2,5>,<3,2>,<3,5>, <3,6>,<4,6>,<5,6>}，请画出图G，并写出其邻接矩阵和邻接表表示。

答：图G如下所示，图G的邻接矩阵和邻接表表示分别如图(b)和(c)所示。 对于这类问题，只要掌握了图的概念和存储结构就可以做出正确的答案。通常情况下．对图的顶点排列顺序和各顶点的邻接点排列顺序并没有特定要求，因此，在写出邻接矩阵和邻接表表示时，只要按照某种排列顺序画出相应的结构图就可以了。但应该注意的是，对于邻接矩阵表示，如果顶点结点的顺序不同，那么邻接矩阵就不相同；对于邻接表表示，如果顶点结点的顺序或者邻接点的顺序不同，那么邻接表就不相同。

0 1 1 1 0 0

1 0 0 0 0 1 0 0 1 0 0 1 1 2 4 0 0 0 0 0 1 3 0 0 0 0 0 1

0 0 0 0 0 0 6 5

(a) (b)

1 3 2 4 ∧

2 3 4 5 6 ∧ 5 ∧ 2 6 ∧ 6 ∧ 5 6 ∧ (c)

图 图及其存储结构

实用文档

七、根据二叉树的已知遍历，恢复该二叉树并进行其他遍历操作

已知一棵二叉树的先序遍历为：acbrsedfmlk，中序遍历为：rbsceafdlkm ，试画出该二叉树 ，并写出它的后序遍历 。

答:(1) 画出该二叉树:

(2)后序遍历:rsbecfklmda

八、 构造哈希表并求其成功查找时的ASL

设有一组关键字（19，01，23，14，55，20，84，27，68，11，10，77），采用哈希函数：H（key）= key % 13，若用开放定址法的线性探测法解决冲突，试在0～13的哈希地址空间中对该关键字序列构造哈希表并求其成功查找时的ASL。

1、填写对应的哈希表

哈希地址 关键字 0 1 2 3 4 5 6 7 8 9 10 11 12 13 比较次数

2、求其成功查找时的ASL

答：依题意，m=13，线性探测法的下一个地址计算公式为： di = H（key）

di+1 = （di+1）% m ；i=1，2，… 1、哈希表如下：（3分）

哈希地址 关键字 0 1 1 1 2 14 2 3 55 1 4 27 4 5 68 3 6 19 1 7 20 1 8 84 3 9 10 23 1 11 11 1 12 10 3 13 77 2 比较次数

2、共有12个关键字，等概率查找，则成功查找时（2分） ASL=（1+2+1+4+3+1+1+3+1+1+3+2）/12=23/12≈1.9

实用文档

九、建立二叉排序树并作插入和删除操作

已知一组关键字为{28,9,32,40,34,22,25,33,7,15},要求： 1、建立一棵二叉排序树

2、画出插入结点20后的二叉排序树 3、画出再删除结点32后的二叉排序树 答：

232232715222534407152225344033 2033 建二叉排序树 插入结点20后的二叉排序树

2823394071522253440或 715222534332020 删除结点32后的二叉排序树

十、排序算法操作

1、用希尔排序法，对8个数值（4，19，28，29，11，21，74，87）进行排序，增量序列为:5、3、1，并输出前2趟的结果。

答：第1趟排序结果： 4，19，28，29，11，21，74，87

第2趟排序结果： 4，11，21，29，19，28，74，87

2、用快速排序法，对8个数值（46，6，98，19，32，40，60，40）进行排序，并输出

前2趟的结果。

答：第1趟排序结果： 40，6，40，19，32，46，60，98

第2趟排序结果： 32，6，40，19，40，46，60，98

3、用冒泡排序法，对 10个数值（46,74,53,14,26,38,86,65, 27,34）进行排序，并输出前2趟的结果。

答：第1趟排序结果： 46 , 53, 14,26,38,74,65,27,34,86 第2趟排序结果： 46,14 ,26,38, 53,65,27,34,74,86

实用文档

十一、 阅读理解算法并回答问题和填充

1、已知二叉树的存储结构为二叉链表，结合下图阅读下列算法。 typedef struct node { TElemType data; struct node *next; }ListNode;

typedef ListNode *LinkList; LinkList Leafhead=NULL; void Inorder(BTree T) { LinkList s; if(T)

{ Inorder(T->lchild);

if(!T->lchild) && (!T->rchild)) { s=(ListNode*)malloc(sizeof(ListNode)); s->data=T->data; s->next=Leafheak; Lerfhead=s;

}

Inorder(T-> rchild); } }

对于上图所示的二叉树：

（1）画出执行上述算法后所建立的结构 （2）说明该算法的功能

答：（1）执行上述算法后建立的结构为如下所示的链表

（2）该算法的功能是用中序遍历递归算法对二叉树进行遍历，将二叉树中叶结点数据域的值作为单链表结点的值，并用头插法建立一个以Leafhead为头指针的逆序单链表（即按二叉树中叶结点数据从右至左链接成一个链表。

2、下列算法以二叉链表为存储结构，交换二叉树各结点的左右子树。请在有横线的地方填写合适的内容。

typedef char DataType;

实用文档

typedef struct node { DataType data;

struct node *lchild, *rchild; } BinTNode;

typedef BinTNode *BinTree; BinTree swap(BinTree T) {

BinTree t,t1,t2;

if (T==NULL) t=__________________(1); else {

t=(BinTree)malloc(sizeof(BinTNode)); t->data=____________(2); t1=swap(T->lchild); t2=swap(T->rchild); t->lchild=____________(3); t->rchild=____________(4); }

return(_____________(5)); } 答：

(1) NULL ; (2) T->data; (3) t2 ; (4) t1 ; (5) __ t___; 3、下列算法的功能是什么？ void abct(SqList &L) {

for ( i=2; i<=L.length; ++i )

if ( LT(L.r[i].key,L.r[i-1].key) )

{ L.r[0] = L.r[i]; L.r[i] = L.r[i-1];

for( j=i-2; LT(L.r[0].key,L.r[j].key);--j )

实用文档

L.r[ j+1] = L.r[ j]; L.r[ j+1] = L.r[0]; } } // InsertSort

答：直接插入排序

十二、 算法设计

1. 在单链表上实现线性表的求表长ListLength(L)运算。 答：由于在单链表中只给出一个头指针，所以只能用遍历的方法来数单链表中的结点个数了。算法描述如下：

int ListLength ( LinkList *L ) { //求带头结点的单链表的表长 int len=0; ListList *p; p=L;

while ( p->next!=NULL ) { p=p->next; len++; }

return (len); }

2、写一算法用头插法建立无头结点的单链表，结果返回单链表的头指针 typedef char DataType; typedef struct node { DataType data; struct node *next; }ListNode;

typedef ListNode *LinkList; 答：

实用文档

3、已知线性表的元素是无序的，且以带头结点的单链表作为存储结构；设计一个删除表中所有值小于max但大于min的元素的算法。

算法描述如下： delete(LinkList *head, int max, int min) { } 答：

delete(LinkList *head, int max, int min)

{ LinkList *p,*q; q=head; p=head->next; while (p!=NULL) if((p->data<=min) || (p->data>=max)) { q=p; p=p->next; } else

实用文档

{ q->next=p->next; free(p); p=q->next; } }

4、 试写一个算法,实现单链表的就地逆置,即利用原表的存储空间将线性表

(a1,a2,….an)逆置为 (an,an-1,……,a2, a1)

单链表结点的类型定义如下:

typedef struct node { /*结点类型定义*/ Datatype data; /*结点的数据域*/ struct node *next; /**结点的指针域*/ } ListNode; 答:

void InverseList (LinkList &head) { ListNode *p, *t, *h;

h=head->next; p=h->next; h->next=NULL; while(p!=NULL)

{ t=p->next; p->next=h; h=p; p=t; } head->next=h; }