装订线（答题不得超过此线）
学号：
姓名：
4、设一个散列表包含13个表项,.其下标从0到12,采用线性探查法解决冲突（p（K，i）＝i），请按以下要求,将下列关键码按从左到右的顺序散列到表中。
10，100，32，45，58，126，3，29，200，400，0
散列函数采用除留余数法,用%SIZE（对表长取余运算）将各关键码映像到表中.，请指出每一个产生冲突的关键码可能产生多少次冲突？
5、一棵前序序列为1，2，3，4的二叉树，其中序序列可能是4，1，2，3吗，为什么？
设一棵二叉树的前序序列为1，2，3，4，5，6，7，8，9，其中序序列为2，3，1，5，4，7，8，6，9，试画出该二叉树。
6、假设用于通信的电文由字符集{a,b,c,d,e,f,g}中的字母构成。
它们在电文中出现的幅度分别为{0.31,0.16,0.10,0.08,0.11,0.20,0.04},为这7个字母统计哈夫曼编码，并计算其平均编码长度。
7、插入排序是否为稳定的排序算法？
为什么？
插入排序在最佳情况和最坏情况下，比较次数和移动数据次数分别为多少？
（假设共有n个元素）
四、算法设计。
（35分）
1．设某带头结点的单链表L，,结点中的元素为整型数据，试编写算法，判断该单链表L中的元素，是否成等差关系，即各元素植依次为a1,a2,a3,a4,……an判断ai+1-ai=ai-ai－1是否成立，其中i满足1<=i<=n-1
2．设一棵二叉树，结点结构为|lchild|data|rchild其中 data域中存放一个字符，设计一个算法按前叙遍历顺序，仅打印出data域为数字的字符（即‘0’<=data<=’9’）
3．某百货公司仓库中电视机的价格和数量信息，按其价格从低到高存储在一个带头结点的循环链表中，链表中的结点由价格、数量和链指针三个域组成：
|cost|num|next|，现新到m台价格为c的电视机需入库，试为此编写修改循环链表中存储的电视机信息的算法。
数据结构试题答案
一、填空题（每空2分，共20分）
1、q->link=s;s->link=p;（两个先后没有关系;link写成next也可以）
2、1
3、后进先出（或LIFO、先进后出）
4、10
5、2n-1
6、插入排序
7、（nlogn）（或nlogn））
8、按关键码的值大小有序
9、n
10、n（n－1）/2
二、程序填空题（10分）
1、--cnt[（a[j]/m）%r]（3分）
2、a[j]=b[j]（4分）
3、m*r（3分）
三、应用题（每小题5分，共35分）
1、使用一个数组来存储两个栈，每个栈从各自的端点向中间延伸，从而减少空间的浪费。
（3分），当两个栈顶指针相遇时（|top2－top1|＝1），栈满（1分）；当栈顶指针为－1或n时，栈空（1分）。
（数组下标从0到n－1）
2、
二叉查找树如下：
（4分）
平均查找长度＝（1×1＋2×2＋3×3＋4×2＋5×2）/10＝3.2（1分）
3、
广度优先搜索生成树（1为起点）（2.5分）
深度优先搜索生成树（2为起点）（2.5分）
4、
下标
0
1
2
3
4
5
6
7
8
9
10
11
12
散列表
0
3
29
200
32
45
58
100
10
126
400
冲突
次数
1
1
2
2
2
散列表（3分），冲突次数（2分）
5、
（1）不可能。
（1分）
反证法证明：
假设存在这棵二叉树，则从前序序列可知，1为二叉树的根节点。
同时，从中序序列可知，节点4位于该二叉树的左子树，节点2、3位于右子树。
对于这样一棵二叉树，按照前序遍历的规则，在其前序遍历序列中，节点4应该位于节点2、3之前，这与已知相矛盾。
因此，这棵二叉树不存在。
（2分）
（2）（2分）
6、（参考）哈夫曼树如下：
（2分）
哈夫曼编码分别为：
（2分）
a
b
c
d
e
f
g
11
101
011
1001
011
00
1000
平均编码长度＝2×0.31＋3×0.16＋3×0.10＋4×0.08＋3×0.11＋2×0.20＋4×0.04＝2.61（1分）
7、
插入排序是稳定的排序算法（1分），因为排序过程是建立在相邻元素比较的基础之上的（2分）。
最佳情况下，需要进行n－1次比较，移动0次元素（1分）；最差情况下，需要比较n×（n－1）/2次，移动元素n×（n－1）/2次（1分）。
四、算法设计（共35分）
1、（10分）
typedefstructListNode
{
intdata;
StructListNode*next;
}ListNode;
BOOLCheckList（ListNode*L）
{
ListNode*a,*pa,*qa;
qa=L->next->next;
a=L->next;
pa=L;
if（（pa==NULL）||（a==NULL）||（qa==NULL））
returnfalse;
while（qa!
=NULL）
{
if（（qa->data+pa->data）!
=（2*a->data））
returnfalse;
qa=qa->next;
a=a->next;
pa=pa->next;
}
2、（10分）
typedefstructTreeNode
{
chardata;
StructTreeNode*lchild;
StructTreeNode*rchild;
}ListNode;
BOOLPreOrderChar（TreeNode*T）
{
if（T!
=NULL）
{
if（（T->data>=’0’）&&（T->data<=’9’））
cout<data<<’’;
PreOrderChar（T->lchild）;
PreOrderChar（T->rchild）;
}
}
3、（15分）
typedefstructListNode
{
doublecost;
intnum;
StructListNode*next;
}ListNode;
BOOLAddTV（intm,doublec,ListNode*L）
{
ListNode*a,*p,*q;
a=newListNode;
a->cost=c;
a->num=m;
if（L->next==NULL）
{
a->next=L;
L->next=a;
}
else
{
p=L;
q=L->next;
while（（q->next!
=L）&&（c>=q->cost））
{
p=p->next;
q=q->next;
}
if（q->next==L）
{
q->next=a;
a->next=L;
}
else
{
p->next=a;
a->next=q;
}
}
}
课程名称：
数据结构-引言，算法分析，线性表
课程考试试卷
题
号
一
二
三
四
五
六
七
八
总分
阅卷
教师
得
分
……………………………………………………………………………………………………
得
分
一、单选题（每小题2分，共10分，本题所给四个答案中只有一个是正确的）
1．下面程序段的时间复杂度是。
sum=0;
for（i=0;i（A）O（n/2）（B）O（n）（C）O（log2n）（D）O（n2）
2．下面程序段的时间复杂度是。
sum=0;
for（i=0;i（A）O（n/2）（B）O（n）（C）O（log2n）（D）O（n2）
3．在有n个元素组成的顺序表中，删除第i个元素（1≤i≤n）后，需要向前移动位置的元素个数为。
（A）n－i－1（B）n－i（C）n－i＋1（D）i
4．在有n个元素组成的链表中，删除第i个元素（1≤i≤n）后，需要向前移动位置的元素个数为。
（A）0（B）1（C）i（D）n－i－1
5．已知单链表中指针q所指结点是指针p所指结点的直接前驱，若在*q与*p之间插入*s，则应执行操作？
（A）s->link=p->link;p->link=s;（B）q->link=s;s->link=p;
（C）p->link=s->link;s->link=p;（D）p->link=s;s->link=q;
得
分
二、填空题（每空1分，共5分）
1.从逻辑结构上讲，数据结构主要分为三大类：
线性结构结构和网状结构。
2.算法有效性的评价指标包括空间复杂度和。
3.堆栈的特点是_____，队列的特点是_________。
4.在顺序表示的线性表中，插入一个新的记录的时间复杂度为________。
得
分
三、判断题（若正确，在括号内打“”，否则打“×”；每题1分，共5分）
1．线性表中的所有元素都有一个前驱和一个后继。
（）
2．线性表是一种抽象数据类型。
（）
3．算法的时间复杂度等于算法运行的时间。
（）
4．由于顺序表中的记录是连续存储的，所以适合数据经常增加或删除的应用。
（）
5．队列是一种操作受限的线性表。
（）
得
分
四、解析题（每题10分，共50分）
1．简述下列概念：
数据、数据元素、数据类型、数据结构、逻辑结构、存储结构、线性结构、非线性结构。
2．设n为正整数，利用大"O"记号，将下列程序段的执行时间表示为n的函数。
i=1;k=0;
while（i {k=k+10*i;i++;
}
3．设n个人围坐在一个圆桌周围，现在从第s个人开始报数，数到第m个人，让他出局；然后从出局的下一个人重新开始报数，数到第m个人，再让他出局，……，如此反复直到所有的人全部出局为止。
下面要解决的Josephus问题是：
对于任意给定的n,s和m，求出这n个人的出局序列。
请以n=9,s=1,m=5为例，人工模拟Josephus的求解过程以求得问题的解。
4．顺序表的插入和删除要求仍然保持各个元素原来的次序。
设在等概率情形下,对有127个元素的顺序表进行插入,平均需要移动多少个元素?
删除一个元素,又平均需要移动多少个元素?
5．铁路进行列车调度时,常把站台设计成栈式结构的站台，如右图所示。
试问：
（1）设有编号为1,2,3,4,5,6的六辆列车,顺序开入栈式结构的站台,则可能的出栈序列有多少种?
（2）若进站的六辆列车顺序如上所述,那么是否能够得到435612,325641,154623和135426的出站序列,如果不能,说明为什么不能;如果能,说明如何得到（即写出"进栈"或"出栈"的序列）。
得
分
五、算法设计题（每题10分，共30分）
1．已知数组存储了n个整数。
下面给出了顺序查找算法，如果数组中存在某个整数等于K，返回K在数组的下标位置；否则返回－1表示数组中没有整数K。
请在算法的空缺处填入适当内容，使之能够正常工作。
//值K如果在数组array中返回存储的下标位置，否则返回-1表示没有查找到。
intbinary（intR[],intn,intK）{
inti;
①;
while（②）
{
if（K==R[i]）③;//在数组中
④;
}
⑤;//不在数组中
}
2．假设线性表中存储了一些整数，试编写算法找到最大值。
3．设计一个算法，实现一个单链表的就地逆置（不另外增加多余的辅助空间）
课程名称：
数据结构-树、排序
课程考试试卷
题
号
一
二
三
四
五
六
七
八
总分
阅卷
教师
得
分
……………………………………………………………………………………………………
得
分
一、单选题（每小题2分，共10分，本题所给四个答案中只有一个是正确的）
1．将含有100个结点的完全二叉树从根结点开始顺序编号，根结点为第0号，其他结点自上而下，同一层从左向右连续编号，则编号最小的叶子结点的编号为。
（A）47（B）48（C）49（D）50
2．对一颗二叉排序树进行得到的结点序列是一个有序序列。
（A）前序周游（B）中序周游（C）后序周游（D）层次周游
3．设只含根结点的二叉树的高度为1，则高度为10的二叉树,至少有_________个结点。
（A）10（B）20（C）30（D）40
4．如果待排序序列中两个数据元素具有相同的值，在排序前后它们的相互位置发生颠倒，则称该排序算法是不稳定的。
下列四种排序方法中是稳定的排序方法。
（A）shell排序（B）快速排序
（C）归并排序（D）简单选择排序
5．若表R在排序前已按键值递增顺序排列，则算法的比较次数最少。
（A）直接插入排序 （B）快速排序
（C）归并排序 （D）选择排序
得
分
二、填空题（每空1分，共5分）
5.已知完全二叉树的第5层有8个结点（根结点在第1层）,则其叶结点数是____________。
6.在有n个叶结点的Huffman树中,共有_____个结点。
7.采用________结构来存储和表示完全二叉树是最有效的。
8.当记录个数比较少且基本有序时，_____是最有效的排序方法。
9.内部排序问题的时间复杂度的下限是_。
得
分
三、判断题（若正确，在括号内打“”，否则打“×”；每题1分，共5分）
1．没有一个结点的二叉树称为空树。
（）
2．一棵二叉树不能存储在一维数组中。
（）
3．归并排序即适合内排序，也适合外排序。
（）
4．快速排序在最差情况下的时间复杂度是O（n2），此时它的性能并不比冒泡排序更好。
（）
5．删除二叉排序树中的一个结点,再重新插入进去,一定能得到原来的二叉排序树。
（）
得
分
四、解析题（每题10分，共50分）
2．根据下面的字母/频率表构造一棵Huffman树,并给出各字母的Huffman编码。
A
B
C
D
E
1
4
9
16
25
3．已知一棵二叉树如下，请分别写出按前序、中序、后序和层次遍历时得到的结点序列。
3．请证明非空满二叉树的叶结点数等于其分支结点数加1。
4．请画出把如下的完全二叉树构建成最大值堆的过程。
5．采用直接插入排序算法,对关键字序列（49,38,65,97,76,13,27）按从小到大的次序进行排序,写出每趟排序的结果。
得
分
五、算法设计题（每题10分，共30分）
1．下面给出了冒泡排序的算法，请在算法的空缺处填入适当内容，使之能够正常工作，得到一个递增的序列。
Voidbubsort（ElemA[],intn）{//数组R中有n个记录
inti,j;Elemt；
for（i=0;①;i++）{
for（intj=n-1;②;j--）
{
if（A[j]③;
④;
⑤;
}
}
}
2．试设计一个前序周游二叉树的函数。
3．编写求二叉树的结点数目的算法。
课程名称：
数据结构-查找、图
课程考试试卷
题
号
一
二
三
四
五
六
七
八
总分
阅卷
教师
得
分
……………………………………………………………………………………………………
得
分
一、单选题（每小题2分，共10分，本题所给四个答案中只有一个是正确的）
1．如果具有n个顶点的图是一个环,则它有________________棵生成树。
（A）n/2（B）n－1（C）n（D）2n
2．具有n个顶点的无向完全图有条边。
（A）n（n－1）/2（B）n（n－1）（C）n（n＋1）/2（D）n2
3．对线性表进行二分搜索时，要求线性表必须。
（A）以数组方式存储（B）以数组方式存储且结点按关键码有序排列
（C）以链接方式存储（D）以链接方式存储且结点按关键码有序排列
4．在有n个结点的二叉检索树中查找一个值,最差情况下的时间代价为________。
（A）O（n）（B）O（logn）（C）O（nlogn）（D）O（n2）
5．具有n个顶点的连通图至少有________条边。
（A）1（B）n-1（C）n （D）n（n-1）
得
分
二、填空题（每空1分，共5分）
10.具有n个顶点的无向图最多有_________条边。
11.n个顶点的连通图的生成树具有___条边。
12.不存在拓扑排序序列的有向图是___。
13.在理想情况下，散列表中查找元素所需的比较次数为__。
14.二分查找的时间复杂度为__。
得
分
三、判断题（若正确，在括号内打“”，否则打“×”；每题1分，共5分）
1．邻接表适合存储稀疏图。
（）
2．用相邻矩阵法存储一个图所需的存储单元数目与图的边数有关。
（）
3．存储无向图的邻接矩阵是对称的，因此只要存储邻接矩阵的下（上）三角部分就可以了。
（）
4．二叉排序树查找的性能一定比顺序查找好。
（）
5．任何一个带权的无向连通图的最小生成树（MST）是唯一的。
（）
得
分
四、解析题（每题8分，共40分）
1．设散列函数为h（K）=Kmod7,散列表的地址空间为0,…,6,开始时散列表为空,用线性探查法解决冲突,请画出依次插入键值23,14,9,6,30,12,18后的散列表。
2．给出的图：
（1）画出这个图的相邻矩阵表示。
（2）画出这个图的邻接表表示。
3．给出的图：
（1）写出从顶点J1出发的深度优先搜索遍历序列。
（2）写出从顶点J1出发的广度优先搜索遍历序列。
（3）写出拓扑排序序列。
4．给出从顶点4出发，使用Dijkstra最短路径算法产生的最短路径长度。
5．对第4小题给出的图，给出从顶点3开始使用Prim的MST算法时各个边的访问顺序，并给出最终的MST。
得
分
五、算法设计题（每题10分，共30分）
1．已知数组元素按照从小到大的顺序存储。
下面给出了二分查找算法，请在算法的空缺处填入适当内容，使之能够正常工作。
//值K如果在数组array中返回存储的下标位置，否则返回-1表示没有查找到。
intbinary（intR[n+1],intK）{
intlow=1;
inthigh=n;
while（①）{//当low,high相遇时结束查找
intmid=②;//取数组中间位置
if（K>array[mid]）low=mid+1;
if（K==array[mid]）③;
if（K}
⑤;//不在数组中
}
2．试设计一个图的深度优先搜索算法。
3．试设计一个图的广度优先搜索算法。
升级会员 