硕士研究生入学考试大纲851数据结构Word文档下载推荐.docx

资源描述

硕士研究生入学考试大纲851数据结构Word文档下载推荐.docx

《硕士研究生入学考试大纲851数据结构Word文档下载推荐.docx》由会员分享，可在线阅读，更多相关《硕士研究生入学考试大纲851数据结构Word文档下载推荐.docx（21页珍藏版）》请在冰点文库上搜索。

硕士研究生入学考试大纲851数据结构Word文档下载推荐.docx

3.3栈和队列的链式存储结构

3.4栈和队列的应用

4串、数组和广义表

4.1字符串的定义、存储结构和操作，模式匹配算法

4.2数组的定义和顺序存储结构，特殊矩阵和稀疏矩阵的压缩存储

4.3广义表的定义和存储结构

5.树和森林

5.1树的定义和术语，树的表示形式和基本操作

5.2二叉树的定义、性质和基本操作

5.3二叉树的顺序存储结构和链式存储结构

5.4二叉树的遍历

5.5线索二叉树

5.6哈夫曼树和哈夫曼编码

5.7树的存储结构，树、森林和二叉树的转换，树和森林的遍历

5.8等价类及其表示

6图

6.1图的定义、术语和基本操作

6.2图的存储结构（邻接矩阵、邻接表）

6.3图的深度优先遍历、广度优先遍历和连通分量

6.4最小生成树、最短路径、拓扑排序和关键路径

7查找

7.1查找的基本概念

7.2顺序查找法、折半查找法和索引顺序表上的查找

7.3二叉排序树的定义，二叉排序树上的查找、插入和删除，二叉排序树查找的性能分析

7.4平衡二叉树的定义，平衡旋转，平衡二叉树的插入和删除

7.5散列表的基本概念、构造和分析

8内部排序

8.1排序的基本概念

8.2交换排序（冒泡排序，快速排序）

8.3插入排序（直接插入排序，折半插入排序，希尔排序）

8.4选择排序（直接选择排序，锦标赛排序，堆排序）

8.5两路归并排序

8.6基数排序

8.7各种内部排序算法的比较和应用

IV.题型示例及参考答案

一、单项选择题（每小题1分,共10分）

1.设有数组A[i,j],数组的每个元素长度为3字节,i的值为1到8,j的值为1到10,数组从内

存首地址SA开始顺序存放，当以列为主存放时，元素A[5,8]的存储首地址为（）。

（A）SA+180（B）SA+141（C）SA+222（D）SA+225

2.在双向链表指针p的结点前插入一个指针q的结点操作是（）。

（A）p->

Llink=q;

q->

Rlink=p;

p->

Llink->

Rlink=q;

Llink=q；

（B）q->

Llink=p->

Llink;

（C）p->

（D）q->

3.一棵二叉树高度为h,所有结点的度或为0,或为2,则这棵二叉树最少有（）结点。

（A）2h（B）2h+1（C）2h-1（D）h+1

4.当在一个有序的顺序存储表上查找一个数据时，既可用折半查找，也可用顺序查找，但前

者比后者的查找速度（）。

（A）取决于表递增还是递减（B）必定快（C）不一定（D）在大部分情况下要快

5.串的长度是指（）。

（A）串中所含不同字母的个数（B）串中所含非空格字符的个数

（C）串中所含不同字符的个数（D）串中所含字符的个数

6.下面说法错误的是（）。

（A）算法原地工作的含义是指不需要任何额外的辅助空间

（B）在相同的规模n下,复杂度O（n）的算法在时间上总是优于复杂度O（2n）的算法

（C）所谓时间复杂度是指最坏情况下，估算算法执行时间的一个上界

（D）同一个算法，实现语言的级别越高，执行效率就越低

7.以下错误的是（）

（i）静态链表既有顺序存储的优点，又有动态链表的优点。

所以，它存取表中第i个元素

的时间与i无关。

（ii）静态链表中能容纳的元素个数的最大数在表定义时就确定了，以后不能增加。

（iii）静态链表与动态链表在元素的插入、删除上类似，不需做元素的移动。

（A）（i）,（ii）（B）（i）（C）（i）,（ii）,（iii）（D）（ii）

8.已知广义表LS=（（a,b,c）,（d,e,f））,运用head和tail函数取出LS中原子e的运算是

（）。

（A）head（tail（head（tail（LS）））（B）tail（head（LS））

（C）head（tail（LS））（D）head（tail（tail（head（LS））））

9.对于顺序存储的线性表，访问结点和增加结点的时间复杂度为（）。

（A）O（n）O（n）（B）O（n）0

（1）（C）0

（1）O（n）（D）0

（1）0

（1）

10.若栈采用顺序存储方式存储，现两个栈共享空间V[1..m],top[j]表示第j个栈（j=1,2）栈顶指

针，栈1的底设在V[1],栈2的底设在V[m],则栈满的条件是（）。

（A）top[2]-top[1]==m（B）top[2]-top[1]==1

（C）top[2]-top[1]==0（D）top[2]+top[1]==m

二、填空题（每空1分，共10分）

1.循环队列用下标范围是0到m的数组V存放其元素值，已知其头、尾指针分别是f和r,f

是队首元素的前一个位置,r是队尾元素位置，若用牺牲一个单元的办法来区分队满和队

空，则队满的条件为。

2.有一个100>

200的元素值为整型的稀疏矩阵，非零元素有20个，设每个整型数占2字节,

则用三元组顺序表表示该矩阵时，所需的字节总数是。

3.如果按关键码值递增的顺序依次将99个关键码值插入到二叉排序树中，则对这样的二叉

排序树检索时，在等概率而且查找成功的情况下的平均查找长度ASL为。

4.下面程序段中带下划线的语句的执行次数的数量级是。

i=1;

while（i<

n）{for（j=1;

=n;

j++）x=x+1;

i=i*2;

}

5.对于长度为54的表，若索引表和各块内均用顺序查找，且每块长度为6,则在等概率情况

下查找成功的平均查找长度为。

6.将有关二叉树的概念推广到三叉树,则一棵有244个结点的完全三叉树的高

度。

7.两个字符串相等的充分必要条件是。

8.构造n个结点的强连通图，至少有条弧。

9.表达式a*（b+c）-d的后缀表达式是。

10.一棵完全二叉树上有1000个结点，其中叶子结点的个数是。

三、应用题洪80分）

1.（12分）假设一棵二叉树的中序序列为GLDHBEIACJFK,后序序列为LGHDIEBJKFCA。

要

求：

（1）画出该二叉树。

（2）画出该二叉树所对应的森林。

（3）画出该二叉树的中序全线索二叉树。

（4）画出该二叉树所对应的森林中第一棵树的带双亲域的孩子链表。

2.（8分）给定一组数据（15,8,10,21,6,19,3）分别代表字符A,B,C,D,E,F,G出现的频度要求：

（1）画出构造哈夫曼树的过程以及最后的哈夫曼树。

（2）在哈夫曼树上对各字符进行编码，并给出各字符的编码值。

（3）计算哈夫曼树的带权路径长度WPL。

3.（20分）设G=（V,E）为有向网，其中V（G）={V1,V2,V3,V4,V5,V6}。

现用三元组<

x,y,z>

表示弧

x,y>

以及弧上的权值z,则E（G）为E（G）={<

V6,V5,100>

V6,V4,30>

V4,V5,60>

V4,V3,20>

V3,V5,15>

V2,V6,10>

V2,V3,50>

V1,V2,5>

}。

要求：

（1）画出该有向网。

（2）画出该有向网的邻接矩阵。

（3）求基于你的邻接矩阵的从顶点V1出发的DFS序列以及DFS生成树。

（4）给出该有向网的所有拓扑有序序列。

（5）用dijkstra算法，求从源点V1出发到其它各终点的最短路径以及长度，请给出执行算

法过程中各步的状态，可用下面给出的表格形式表示。

4.（12分）有一结点的关键字序列F={26,36,41,38,44,15,68,12,06,51,25},

散列函数为：

H（K）=K%11,其中K为关键字，散列地址空间为0〜10。

（1）画出相应的闭散列表。

发生冲突时，以线性探测法解决。

（2）该散列表的装填因子a是多少？

（3）在等概率情况下查找成功时的平均查找长度ASL是多少？

（4）用线性探测法解决冲突时，如何处理被删除的结点？

为什么？

5.（8分）已知长度为10的表{16,3,7,12,9,28,25,18,14,20},按表中元素顺序依次插入一棵初始时

为空的平衡二叉排序树中，画出每一步插入后平衡二叉排序树的形态。

若做了某种旋转，说

明旋转的类型。

6.（20分）已知关键字序列F={22,12,26,40,18,38,14,20,30,16,28}。

（1）将该序列调整为小顶”堆，并给出调整过程。

请从时间和空间两方面对简单选择排

序、树形选择排序和堆排序作一比较。

（2）若采用链式基数排序方法排序,请写出第一趟“分配”之后各队列的状态和第一趟“收

集”之后的关键字序列。

并请简要说出基数排序方法和其他排序方法有什么区别？

（3）要求最后排序结果是按关键字从小到大的次序排列,请给出冒泡排序的前3趟排序结

果。

四、简答题（共30分）

1.（6分）线性表的顺序存储结构和链式存储结构各有哪些优缺点？

2.（8分）画出对长度n为10的递增有序表{A[1]、A[2]、……、A[10]}进行折半查找的判定

树。

当实现插入排序过程时,可以用折半查找来确定第i个元素在前i-1个元素中的可能插

入位置,这样做能否改善插入排序的时间复杂度？

3.（8分）快速排序的平均时间复杂度是多少？

快速排序在所有同数量级的排序方法中,其平

均性能好。

但在什么情况下快速排序将蜕化为起泡排序,此时的时间复杂度又是多少？

为改进之,通常可以怎么做？

4.（8分）请简要叙述求最小生成树的Prim算法的思想（或步骤）。

并指出对具有n个顶点和e

条边的连通网而言，Prim算法和Kruskal算法各自适合于什么情况下的连通网？

其时间复杂度又各为多少？

五、算法设计题（共20分）

1.（10分）给定（已生成）一个带表头结点的单链表，设head为头指针，结点的结构为（data，next），data为整型元素，next为指针，试写出算法：

按递减次序输出单链表中各结点的数据元素，并释放结点所占的存储空间。

（要求：

不允许使用数组作辅助空间）

2.（10分）以二叉链表作为二叉树的存储结构，试编写递归算法，求二叉树中以元素值为item的

结点为根的子树的深度（假设树中一定存在值为item的结点）。

（1）可用（类）Pascal语言或（类）C语言或C++语言描述你的算法；

（2）请简要描述你的算法思想；

（3）若你的算法是（类）Pascal或（类）C语言编写,则请给出相应的存储结构描述；

（4）若你的算法是用C++语言描述，则可参考使用以下给出的相关存储结构的类定义，算

法中可以使用类中已列出的成员函数。

若在你的算法中使用了未列出的成员函数，则要写出

该成员函数的完整算法描述

//单链表的类定义

template<

classtype>

classlinklist;

//单链表前视声明

classnode{//单链表结点类

friendclasslinklist<

type>

;

//定义单链表类linklist<

为结点类的友元private:

node<

*next;

//链指针域

public:

typedata;

//数据域

node（node<

*pnext=NULL）{next=pnext;

}//构造函数，用于构造头结点

};

classlinklist{//单链表类定义private:

*head;

//指向头结点的头指针

linklist（）{head=newnode<

（）;

head->

next=NULL;

}//构造函数

~linklist（）;

//析构函数

//二叉链表的类定义：

classType>

classBinaryTree;

//二叉链表类前视声明,以便使用友元template<

classBinTreeNode{//结点类friendclassBinaryTree<

Type>

private:

BinTreeNode<

*leftChild,*rightChild;

//结点的左、右孩子指针域

Typedata;

//结点的数据域

BinTreeNode（）:

leftChild（NULL）,rightChild（NULL）{}//构造函数,构造一个空结点

BinTreeNode（Typed,BinTreeNode<

*lp=NULL,BinTreeNode<

*rp=NULL）:

data（d）,leftChild（lp）,rightChild（rp）{}

//构造函数,构造一个数据域的值为d的结点

classBinaryTree{//二叉链表类

BinTreeNode<

*root;

//二叉树根结点指针

BinaryTree（）:

root（NULL）{}//构造函数

~BinaryTree（）{destroy（root）;

}//析构函数

参考答案

一、单项选择题

1.A；

2.B；

3.C；

4.D；

5.D；

6.C；

7.B；

8.A；

9.C；

10.B；

二、填空题

1.（r-f+m+1）%（m+1）

2.20*3*2+6=126

3.（99+1）/2=50

4.O（nlog2n）

5.（9+1）/2+（6+1）/2=17/2=8.5

6.Iog3（244+1）的上取整或Iog3244下取整+1

7.长度相等,对应位置的字符相同

8.n

9.abc+*d-

10.500（n2=499,n0=n2+1=499+1=500）

三、应用题

（1）二叉树

（2）森林

（4）双亲孩子链表

⑴

码f13}

潞叩I

2笑

⑵

⑶

WPL=（3+6）*4+（8+10+15）*3+（19+21）*2=36+99+80=215

100

0丿

DFS序列：

V1,V2,V3,V5,V6,V4

DFS生成树：

⑷拓扑序列：

V1,V2,V6,V4,V3,V5

（5）

（1）

（2）

（3）

（4）

（V1,V2）

（V1,V2,V3）

（V1,V2,V6,V4）

（V1,V2,V6,V5）

115

（V1,V2,V6,V4,V5）

105

（V1,V2,V3,V5）

（V1,V2,V6）

（u,v）

长度

关键字

HASH函数值

比较次数

H（k）=k%11,数组范围：

0~10

下标

关键字「

冲突关键字

=n/m=11/11=1

1123ASL（）c（17213281）=n1111⑷

不能真正地物理”删除,只能做删除标记”否则将截断在它之后填入散列表的同义词结点的查找路径。

{16,3,7,12,9,28,25,18,14,20}

平衡

3亠

（1）

/（>

命沪/席石//V

（a）魏虫豺呷彳1渝t0t主』金t/t彷T/军乍肚瘫

（0-*_2口22fQff4T■匹ff#7环

链式基数排序和其他排序方法的最大区别是各关键字之间没有发生比较。

初始

四、简答题

顺序存储结构

链式存储结构

优

占

八、、

存取第i个兀素方便（随机存取）,0

（1）

（1）插入、删除不需移动兀素，只修改指针，修

改指针的时间复杂度为0

（1）；

（2）不需要预先分配空间，可根据需要动态申请空间；

（3）表容量只受可用内存空间的限制。

缺

（1）在作插入或删除操作时，需移动大量

元素；

（2）由于难以估计，必须预先分配较大的空间，往往使存储空间不能得到充分利用；

（3）表的容量难以扩充。

（1）存取第i个兀素不方便，是0（n）

长度n为10的递增有序表折半查找的判定树如左所示。

（2）不能改善插入排序的时间复杂度

（3）原因：

插入排序中，用折半查找确定待插入元素位置，比直接插入排序减少了比较次数，但数据移动次数没有改变，排序的时间复杂度也未改变。

快速排序的平均时间复杂度为O（nlogn）。

在关键字有序或基本有序的情况下，快速排序将蜕化为起泡排序。

此时的时间复杂度是O（n2）。

为改进之，通常可以采用三者取中法”取三者中其关键字为中间值的记录为枢轴，只要将该

记录和待排序表的第一个关键字互换即可，算法不变。

4•算法思想：

设N=（V,{E}）是连通网,TE是N上最小生成树中边的集合

（1）初始令U={uO},（uOV）,TE=G

⑵在所有u.U,v・V-U的边（u,v）•E中,找一条代价最小的边（uO,vO）

⑶将（u0,v0）并入集合TE,同时v0并入U.即TE=TE+{（uO,vO）},U=U+{vO}

⑷重复上述

（2）,（3）操作直至U=V为止，则T=（V,{TE}）为N的最小生成树对具有n个顶点和e条边的连通网而言：

Prim算法适合于边稠密的连通网，其时间复杂度为0（n2）,与顶点数有关

Kruskal算法适合于边稀疏的连通网，其时间复杂度为O（elog2e）,与边的条数有关

五、算法设计题

算法思想：

对链表进行遍历，在每趟遍历中查找出整个链表的最大值元素，输出并释放结点所

占空间；

再查次最大值元素，输出并释放空间，如此下去，直至链表为空，最后释放头结点所占存储空间。

voidMiniDelete（linklisthead）

//head是带头结点的单链表的头指针，本算法按递增顺序输出单链表中各结点的数据元素，并

释放结点所占的存储空间。

{

while（head-〉next!

=null）//循环到仅剩头结点。

{pre=head;

展开阅读全文