if（j==strlen（t））return（i-strlen（t））;elsereturn（-1）;
}
10.设一个连通图G中有n个顶点e条边，则其最小生成树上有________条边。
三、应用题
1．设完全二叉树的顺序存储结构中存储数据ABCDE，要求给出该二叉树的链式存储结构并给出该二叉树的前序、中序和后序遍历序列。
2．设给定一个权值集合W=（3，5，7，9，11），要求根据给定的权值集合构造一棵哈夫曼树并计算哈夫曼树的带权路径长度WPL。
3．设一组初始记录关键字序列为（19，21，16，5，18，23），要求给出以19为基准的一趟快速排序结果以及第2趟直接选择排序后的结果。
4．设一组初始记录关键字集合为（25，10，8，27，32，68），散列表的长度为7，散列函数H（k）=kmod7，要求用线性探测法作为解决冲突的方法设计哈希表。
5．设无向图G（所右图所示），要求给出该图的深度优先和广度优先遍历的序列,并画给相应的生成树
（一）参考答案
二、填空题
1.（F+1）%m
2.O（n），O（n）
3.2n，n+1
4.s->next=p->next;s->next=s
5.n,2e
6.m=2e
7.CBA
8.4，16
9.i-j+1，0
10.n-1
三、应用题
1.链式存储结构略，前序ABDEC，中序DBEAC，后序DEBCA。
2.哈夫曼树略，WPL=78
3.（18,5,16,19,21,23），（5，16，21，19，18，23）
4.线性探测：
数据结构
（二）
一、选择题
1．下面关于线性表的叙述错误的是（）。
（A）线性表采用顺序存储必须占用一片连续的存储空间
（B）线性表采用链式存储不必占用一片连续的存储空间
（C）线性表采用链式存储便于插入和删除操作的实现
（D）线性表采用顺序存储便于插入和删除操作的实现
2．设哈夫曼树中的叶子结点总数为m，若用二叉链表作为存储结构，则该哈夫曼树中总共有（）个空指针域。
（A）2m-1（B）2m（C）2m+1（D）4m
3．设顺序循环队列Q[0：
M-1]的头指针和尾指针分别为F和R，头指针F总是指向队头元素的前一位置，尾指针R总是指向队尾元素的当前位置，则该循环队列中的元素个数为（）。
（A）R-F（B）F-R（C）（R-F+M）％M（D）（F-R+M）％M
4．设某棵二叉树的中序遍历序列为ABCD，前序遍历序列为CABD，则后序遍历该二叉树得到序列为（）。
（A）BADC（B）BCDA（C）CDAB（D）CBDA
5．设某完全无向图中有n个顶点，则该完全无向图中有（）条边。
（A）n（n-1）/2（B）n（n-1）（C）n2（D）n2-1
6．设某棵二叉树中有2000个结点，则该二叉树的最小高度为（）。
（A）9（B）10（C）11（D）12
7．设某有向图中有n个顶点，则该有向图对应的邻接表中有（）个表头结点。
（A）n-1（B）n（C）n+1（D）2n-1
8．设一组初始记录关键字序列（5，2，6，3，8），以第一个记录关键字5为基准进行一趟快速排序的结果为（）。
（A）2，3，5，8，6（B）3，2，5，8，6
（C）3，2，5，6，8（D）2，3，6，5，8
二、填空题
1.为了能有效地应用HASH查找技术，必须解决的两个问题是____________________和__________________________。
2.下面程序段的功能实现数据x进栈，要求在下划线处填上正确的语句。
typedefstruct{ints[100];inttop;}sqstack;
voidpush（sqstack&stack,intx）
{
if（stack.top==m-1）printf（“overflow”）;
else{____________________;_________________;}
}
3.中序遍历二叉排序树所得到的序列是___________序列（填有序或无序）。
4.快速排序的最坏时间复杂度为___________，平均时间复杂度为__________。
5.设某棵二叉树中度数为0的结点数为N0，度数为1的结点数为N1，则该二叉树中度数为2的结点数为_________；若采用二叉链表作为该二叉树的存储结构，则该二叉树中共有_______个空指针域。
6.设某无向图中顶点数和边数分别为n和e，所有顶点的度数之和为d，则e=_______。
7.设一组初始记录关键字序列为（55，63，44，38，75，80，31，56），则利用筛选法建立的初始堆为___________________________。
8.设某无向图G的邻接表为
，则从顶点V1开始的深度优先遍历序列为___________；广度优先遍历序列为____________。
三、应用题
1．设一组初始记录关键字序列为（45，80，47，40，20，78），则分别给出第4趟简单选择排序和第4趟直接插入排序后的结果。
2．设指针变量p指向双向链表中结点A，指针变量q指向被插入结点B，要求给出在结点A的后面插入结点B的操作序列（设双向链表中结点的两个指针域分别为llink和rlink）。
3．
设一组有序的记录关键字序列为（13，18，24，35，47，50，62，83，90），查找方法用二分查找，要求计算出查找关键字62时的比较次数并计算出查找成功时的平均查找长度。
4．设一棵树T中边的集合为{（A，B），（A，C），（A，D），（B，E），（C，F），（C，G）}，要求用孩子兄弟表示法（二叉链表）表示出该树的存储结构并将该树转化成对应的二叉树。
5．设有无向图G（如右图所示），要求给出用普里姆算法构造最小生成树所走过的边的集合。
6．设有一组初始记录关键字为（45，80，48，40，22，78），要求构造一棵二叉排序树并给出构造过程。
7、给出如图所示的无向图G的邻接矩阵和邻接表两种存储结构。
8、简单选择排序、快速排序和堆排序是不稳定的排序方法,试举例说明。
9、给出下图邻接矩阵和邻接表两种存储结构；写出图的拓扑序列。
（二）参考答案
一、选择题
1.D2.B3.C4.A5.A6.C7.B8.C
二、填空题
1.构造一个好的HASH函数，确定解决冲突的方法
2.stack.top++，stack.s[stack.top]=x
3.有序
4.O（n2），O（nlog2n）
5.N0-1，2N0+N1
6.d/2
7.（31，38，54，56，75，80，55，63）
8.（1，3，4，2），（1，3，2，4）
三、应用题
1.（20，40，45，47，80，78），（40，45，47，80，20，78）
2.q->llink=p;q->rlink=p->rlink;p->rlink->llink=q;p->rlink=q;
3.2,ASL=91*1+2*2+3*4+4*2）=25/9
4.树的链式存储结构略，二叉树略
5.E={（1，3），（1，2），（3，5），（5，6），（6，4）}
6.略
8、简单选择排序、快速排序和堆排序是不稳定的排序方法,试举例说明。
【解答】
（2）简单选择排序{275275*512061}i=1
{061275*512275}i=2
{061275*512275}i=3
{061275*275512}
（3）快速排序{512275275*}
{275*275512}
（4）堆排序{275275*061170}已经是最大堆，交换275与170
{170275*061275}对前3个调整
{275*170061275}前3个最大堆，交换275*与061
{061170275*275}对前2个调整
{170061275*275}前2个最大堆，交换170与061
{061170275*275}
数据结构（三）
一、选择题
1．设某无向图有n个顶点，则该无向图的邻接表中有（）个表头结点。
（A）2n（B）n（C）n/2（D）n（n-1）
2．设无向图G中有n个顶点，则该无向图的最小生成树上有（）条边。
（A）n（B）n-1（C）2n（D）2n-1
3．设一组初始记录关键字序列为（60，80，55，40，42，85），则以第一个关键字45为基准而得到的一趟快速排序结果是（）。
（A）40，42，60，55，80，85（B）42，45，55，60，85，80
（C）42，40，55，60，80，85（D）42，40，60，85，55，80
4．（）二叉排序树可以得到一个从小到大的有序序列。
（A）先序遍历（B）中序遍历（C）后序遍历（D）层次遍历
5．设按照从上到下、从左到右的顺序从1开始对完全二叉树进行顺序编号，则编号为i结点的左孩子结点的编号为（）。
（A）2i+1（B）2i（C）i/2（D）2i-1
6．程序段s=i=0；do{i=i+1；s=s+i；}while（i<=n）；的时间复杂度为（）。
（A）O（n）（B）O（nlog2n）（C）O（n2）（D）O（n3/2）
7．设带有头结点的单向循环链表的头指针变量为head，则其判空条件是（）。
（A）head==0（B）head->next==0
（C）head->next==head（D）head!
=0
8．设某棵二叉树的高度为10，则该二叉树上叶子结点最多有（）。
（A）20（B）256（C）512（D）1024
9．设一组初始记录关键字序列为（13，18，24，35，47，50，62，83，90，115，134）,则利用二分法查找关键字90需要比较的关键字个数为（）。
（A）1（B）2（C）3（D）4
10.设指针变量top指向当前链式栈的栈顶，则删除栈顶元素的操作序列为（）。
（A）top=top+1;（B）top=top-1;
（C）top->next=top;（D）top=top->next;
二、判断题
1、数据的最小单位是数据项。
………………………….（√）
2、多重表文件中主索引为非稠密索引，次索引为稠密索引。
……….（√）
3、通常数据结构在计算机中有四种不同的表示方法分为顺序存储结构、链式存储结构、索引存储、文件存储。
……….…….（×）
4、算法具有输入、输出、可行性、稳定性、有穷性五个特性。
……………….（×）
5、数据的基本单位是数据项。
………………………….（×）
6、算法的复杂度分为时间复杂度和效率复杂度。
………….（×）
7、性质相同的数据元素的集合成为数据对象。
…………….（√）
8、所有结点按1对1的邻接关系构成的整体就是集合结构。
……….（×）
9、散列文件不能顺序存取、只能按关键字随机存取。
…………….（√）
10、数据的基本单位是数据元素。
………………………….（√）
11．不论是入队列操作还是入栈操作，在顺序存储结构上都需要考虑“溢出”情况。
（√）
12．当向二叉排序树中插入一个结点，则该结点一定成为叶子结点。
（√）
13．由树转化成二叉树，该二叉树的右子树不一定为空。
（×）
14．线性表中的所有元素都有一个前驱元素和后继元素。
（×）
15.带权无向图的最小生成树是唯一的。
（×）
16.具有12个结点的完全二叉树有5个度为2的结点。
（ ）
17.关键路径是事件结点网络中的从源点到汇点的最短路径。
（ ）
18.由树转化成二叉树，该二叉树的右子树不一定为空。
（）
19.堆排序是不稳定的排序方法。
（√ ）
20.查找表是由同一类型的数据元素（或记录）构成的集合（√）
三、填空题
1.设指针变量p指向双向链表中的结点A，指针变量s指向被插入的结点X，则在结点A的后面插入结点X的操作序列为_________=p；s->right=p->right；__________=s；p->right->left=s；（设结点中的两个指针域分别为left和right）。
2.设完全有向图中有n个顶点，则该完全有向图中共有________条有向条；设完全无向图中有n个顶点，则该完全无向图中共有________条无向边。
3.设关键字序列为（Kl，K2，…，Kn），则用筛选法建初始堆必须从第______个元素开始进行筛选。
4.解决散列表冲突的两种方法是________________和__________________。
5.设一棵三叉树中有50个度数为0的结点，21个度数为2的结点，则该二叉树中度数为3的结点数有______个。
6.高度为h的完全二叉树中最少有________个结点，最多有________个结点。
7.设有一组初始关键字序列为（24，35，12，27，18，26），则第3趟直接插入排序结束后的结果的是__________________________________。
8.设有一组初始关键字序列为（24，35，12，27，18，26），则第3趟简单选择排序结束后的结果的是__________________________________。
9.设一棵二叉树的前序序列为ABC，则有______________种不同的二叉树可以得到这种序列。
10.下面程序段的功能是实现一趟快速排序，请在下划线处填上正确的语句。
structrecord{intkey;datatypeothers;};
voidquickpass（structrecordr[],ints,intt,int&i）
{
intj=t;structrecordx=r[s];i=s;
while（i{
while（ix.key）j=j-1;if（iwhile（____________________）i=i+1;if（i}
_________________;
}
数据结构（三）
一、选择题
1．B2．B3．C4．B5．B
6．A7．C8．C9．B10．D
三、填空题
1.s->left=p，p->right
2.n（n-1），n（n-1）/2
3.n/2
4.开放定址法，链地址法
5.14
6.2h-1，2h-1
7.（12，24，35，27，18，26）
8.（12，18，24，27，35，26）
9.5
10.i
数据结构（四）
一、选择题
1．设输入序列是1、2、3、……、n，经过栈的作用后输出序列的第一个元素是n，则输出序列中第i个输出元素是（c）。
（A）n-i（B）n-1-i（C）n+1-i（D）不能确定
2.为查找某一特定单词在文本中出现的位置，可应用的串运算是（ ）
A.插入 B.删除 C.串联接 D.子串定位
3．设有序表中有1000个元素，则用二分查找查找元素X最多需要比较（）次。
（A）25（B）10（C）7（D
升级会员 