南理工04级至07级数据结构课程期末考试试卷及答案.doc
《南理工04级至07级数据结构课程期末考试试卷及答案.doc》由会员分享，可在线阅读，更多相关《南理工04级至07级数据结构课程期末考试试卷及答案.doc（38页珍藏版）》请在冰点文库上搜索。
南京理工大学课程考试试卷（学生考试用）
课程名称：
数据结构学分：
3大纲编号062204
试卷编号：
考试方式：
闭卷满分分值：
100考试时间：
120分钟
组卷日期：
2006年5月18日组卷教师（签字）张宏审定人（签字）王树梅
学生班级：
计算机学院04级学生学号：
学生姓名：
一、选择题（1.5*20=30分）
1.若以{4，5，6，3，8}作为叶子结点的权值构造哈夫曼树，则带权路径长度是
A）55B）68C）59D）28
2.无向图G=（V，E），其中：
V={a,b,c,d,e,f},E={（a,b）,（a,e）,（a,c）,（b,e）,（c,f）,（f,d）,（e,d）},对该图进行广度优先遍历，得到的顶点序列正确的是
A）a,b,e,c,d,fB）a,c,f,e,b,dC）a,e,b,c,f,dD）a,e,d,f,c,b
3.对关键字码集合K={53，30，37，12，45，24，96}，从空二叉树出发建立与集合K对应的二叉排序树，若希望得到树的高度最小，应选择下列哪个输入序列。
A）45，24，53，12，37，96，30B）12，24，30，37，45，53，96
C）37，24，12，30，53，45，96D）30，24，12，37，45，96，53
4.已知一组数{20，8，6，2，30，1}的排序过程为：
（1）20，8，6，2，30，1
（2）1，8，6，2，30，20
（3）1，2，6，8，30，20
（4）1，2，6，8，20，30
问它是下面那一种排序：
A）快速排序B）直接插入排序C）起泡排序D）选择排序
5．计算机算法必须具备输入、输出和等五个特征。
A）可行性、可移植性和可扩充性B）可行性、确定性和有穷性
C）确定性、有穷性和稳定性D）易读性、稳定性和安全性
6．设哈希表长为14，哈希函数是H（key）=key%11,表中已有数据的关键字为15,38,61,84共四个，现要将关键字为26的结点加到表中，用二次探测再散列法解决冲突，则放入的位置是
A）8B）3C）2D）9
7．在一个单链表中，若要删除p所指结点的后继结点，则执行。
A）p=p->next;p->next=p->next->next
B）free（p->next）（C语言格式）或deletep->next（C++语言格式）
C）p=p->next->next;
D）p->next=p->next->next
8.数组A的每个元素需要4个字节存放，数组有8行10列，若数组以行为主顺序存放在内存SA开始的存储区中，则A中8行5列的元素的位置是
A）SA+74B）SA+292C）SA+296D）SA+300
9-10．在一棵7阶B树中，若在某结点中插入一个新关键字而引起该结点分裂，则此结点中原有
（1）个关键字；若在某结点中删去一个关键字而导致结点合并，则该结点中原有的关键字的个数是
（2）。
（1）A）6B）5C）4D）3
（2）A）4B）3C）2D）1
11．已知四个元素a,b,c,d依次进栈，进栈过程中可出栈，下面那一种出栈顺序是不正确的
A）a,d,c,bB）b,c,d,aC）c,a,d,bD）c,d,b,a
12．队列操作的原则是。
A）先进先出B）后进先出C）只能进行插入D）只能进行删除
13．在有n个结点的二叉链表中,值为空链域的个数为
A）n-1B）2n-1C）n+1D）2n+1
14．具有1080个结点的完全二叉树的深度为
A）12B）10C）11D）13
15．若已知一个栈的入栈序列是元素1，2，3，....，n，其输出序列为p1,p2,p3,…pn,若p1是n，则pi是（）
A）iB）n-iC）n-i+1D）不确定
16．对于一个具有n个顶点的无向图，若采用邻接矩阵表示，则该矩阵的大小是
A）nB）（n-1）2C）n-1D）n2
17．对线性表进行二分查找时，要求线性表必须
A）以顺序方式存储B）以链接方式存储
C）以顺序方式存储，且数据有序D）以链接方式存储，且数据有序
18．若用起泡排序对序列{14,26,29,41,52,5}从小到大排序,需要次比较
A）15B）28C）3D）21
19．有一个有序表为{1，3，9，12，32，41，45，62，70，77，82，95，100}，当二分查找值62的数据时要次比较成功。
A）1B）2C）4D）3
20．设双向循环链表中结点的结构为（data,pre,next）。
若在指针p所指结点之后插入结点s，则应执行下列操作
A）p->next=s;s->pre=p;p->next->pre=s;s->next=p->next;
B）p->next=s;p->next->pre=s;s->pre=p;s->next=p->next;
C）s->pre=p;s->next=p->next;p->next=s;p->next->pre=s;
D）s->pre=p;s->next=p->next;p->next->pre=s;p->next=s;
二、填空题（19分,其余每空1分）
1．已知h是无表头结点的单链表，且p结点既不是首元结点，亦不是尾元结点，试从下列提供答案中选择合适的语句序列（给出序号）：
a.在p结点后插入s结点的语句序列是
（1）；
b.在p结点前插入s结点的语句序列是
（2）；
c.在表首插入s结点的语句序列是（3）；
d.在表尾插入s结点的语句序列是（4）；
（1）p->next=s;
（2）p->next=p->next->next;
（3）p->next=s->next;
（4）h=s;
（5）p=h;
（6）s->next=NULL;
（7）q=p;
（8）while（p->next!
=NULL）p=p->next;
（9）while（p->next!
=q）p=p->next;
（10）p=q;
（11）p=h;s->next=h;
（12）h=p;
（13）s->next=p->next;
2．图的遍历分为（5）和（6）。
3．假设一棵二叉树的中序序列为DCBGEAHFIJK和后序序列为DCEGBFHKJIA，则先序序列为：
（7）。
4．深度为k的完全二叉树至少有（8）个结点；至多有（9）结点。
5．在一棵二叉树中，度为1的结点有40个，总的结点数为99，则二叉树中叶子结点数共有（10）。
6．在一棵m阶B-树中，若在某结点中插入一个新关键字而引起该结点分裂时，则左边结点有
（11） 个关键字；右边结点的关键字数是（12） 。
7.求图的最小生成树有两种算法，（13）算法适合于求稀疏图的最小生成树。
8．一个深度为k的，具有最少结点数的完全二叉树按层次，（同层次从左向右）用自然数依此对结点编号，则编号最小的叶子的序号是（14）；编号是i的结点所在的层次号是（15）（根所在的层次号规定为1层）。
三、简答题（35分）
1．已知有向图的带权矩阵为：
1）（3分）画出该有向图。
2）（3分）按Dijkstra算法,给出从顶点1（顶点标号从1计）到其余顶点的最短路径长度以及经过的中间点。
3）（3分）画出该图邻接表存储结构示意图。
4）（3分）画出对应无向图的最小生成树，给出生成树边权之和。
（如果去掉方向后,一对顶点之间有两条以上的边,只保留权值最小的边）
2．已知关键字的集合{56，8，15，80，10，22，28，50，60,40,90}
（1）（3分）试按给出的序列构造一棵平衡二叉树。
（2）（3分）试构造3阶B_树。
（3）（3分）写出依次删除关键字60,40后的B_树。
（4）（3分）按以上数据,用链地址法处理冲突（Hash函数H（key）=key%13），画出示意图（不要写算法）
3．（3分）已知三棵树的森林如下，试把它转化为二叉树
AGN
/\/|\/\
BCHIKOP
/|\/\/|\
DEFLMRST
4．（4分）按大顶堆将序列{56，8，15，80，10，22，28，50，60,40,90}调整为堆，写出最后的数据序列
5．（4分）给出拓扑排序算法描述（不用写C/C++算法）
四、算法设计（用类-C/类-C++描述）（16分）
1．（8分）完成一个二叉树左右子树交换的递归算法。
2．（8分）设在一个带头结点的双向链表中，所有结点的数据元素按值递增顺序排列，写一算法，删除表中所有大于min，小于max的元素（若存在）。
双链表的定义如下：
typedefstructDLnode{
intdata;
DLnode*pre,*next;
}DLnode;
南京理工大学课程考试试卷（学生考试用）
课程名称：
数据结构学分：
3大纲编号062204
试卷编号：
考试方式：
闭卷满分分值：
100考试时间：
120分钟
组卷日期：
2006年5月18日组卷教师（签字）张宏审定人（签字）王树梅
学生班级：
计算机学院04级学生学号：
学生姓名：
一、单项选择题（1.5*20=30分）
1、对于序列（12，13，11，18，60，15，7，18，25，100），用筛选法建堆，必须从值为________的数据开始建初始堆。
A）100B）12C）60D）15
2、若一棵二叉树具有10个度为2的结点，则该二叉树的度为0的结点个数是
A）9B）11C）12D）不确定
3、对某二叉树进行前序遍历的结果为ABDEFC，中序遍历的结果为DBFEAC，则后序遍历的结果为
A）DBFEACB）DFEBCAC）BDFECAD）BDEFAC
4、5阶B树中，每个结点最多有个关键字。
A）2B）3C）4D）5
5、设有一个二维数组a［m］［n］，假设a［0］［0］存放位置在644，a［2］［2］存放位置在676，每个元素占一个空间，则a［4］［5］在位置（数组元素以行为主存储）
Ａ）692 Ｂ）626Ｃ）709 Ｄ）724
6、一棵完全二叉树按顺序方式存储在一维数组chars[]={‘A’,’B’,’C’,’D’,’E’,
’F’,’G’,’H’,’I’,’J’}中，则结点E在二叉树的第层。
（注：
根所在的层为1层）
A）1B）2C）3D）4
7、下面说法不正确的是
A）循环链表从任何一个结点出发，都能访问到所有结点
B）一般树和二叉树的结点的孩子数都可以为0
C）在拓扑排序序列中，若Vi在Vj之前，则必定存在从Vi到Vj的路径
D）图（网）的最小代价生成树不是唯一的
8、下面说法不正确的说法有个
1）队列逻辑上是一个表头和表尾都能插入又能删除的线性表
2）有n个顶点的无向图G的最小生成树T就是由G中具有最小权值n-1条边所构造出来的G的子图。
3）在10万个随机排列的数据中，要选出5个最小的数，采用快速排序比采用Shell排序、堆排序及直接排序法都快。
4）哈希表查找无需进行关键字的比较。
A）1B）2C）3D）4
9、一个堆通常采用存储结构来存储
A）顺序B）链接C）索引D）哈希（散列）
10、长度为n的线性表中，_______都有一个直接前驱元素。
A）任意元素B）除第n/2个元素C）除第一个元素D）除最后一个元素
11、在由head所指的非空线性链表中删除由p指的链结点的下一个链结点的过程是依次执行
q=p->next;_______;deleteq;
A.）p->next=qB）q->next=pC）q->next=p->nextD）p->next=q->next
12、稀疏矩阵采用三元组方法进行压缩存储的原因是
A）0元素分布有规律B）非0元素分布有规律C）0元素多D）非0元素多
13、已知一个有向图的弧集合为{,,,,,},则由该图产生的一种可能的拓扑序列为_____
A）a,b,c,d,eB）a,c,d,e,bC）a,c,b,e,dD）a,c,d,b,e
14、对于一个数据序列，按照给定的次序建立一个二叉排序树，该二叉排序树的形状取决于
A）该序列的存储结构B）序列中的数据元素的取值范围
C）数据元素的输入次序D）使用的计算机的软、硬件条件
15、一组数据为（25,48,16,35,79,82,23,40,36,72）,现在用某种排序算法进行一趟后的结果如下：
16482535798223403672，则采用的是排序
A）选择B）快速C）Shell（希尔）D）直接插入
16、链表不具有的特点是____________.
A）可随机访问任一元素B）插入删除不需要移动元素
C）不必事先估计存储空间D）所需空间与线性表长度成正比
17、在有n个叶子的哈夫曼树中，其结点总数为______________。
A）不确定B）2nC）2n+1D）2n-1
18、任何一个无向带权连通图的最小生成树_____________。
A）只有一棵B）有一棵或多棵C）一定有多棵D）可能不存在
19、将一棵有100个结点的完全二叉树从根这一层开始，每一层上从左到右依次对结点进行编号，根结点的编号为1，则编号为49的结点的左孩子编号为__________。
A）98B）99C）50D）48
20、下面说法正确的是
1）二叉树的前序遍历序列中，任意一个结点均处于其子孙结点的前面
2）一棵树的先序遍历序列同它对应的转换后的二叉树的中序遍历序列相同
3）二叉线索树中每个结点都有指向前驱和后继的指针
A）1B）2C）1）和3）D）1）和2）
二、填空题（1*16=16分）
1、已知一有个链表表示的栈，栈顶指针为top,退栈后，对top的操作是
（1）（用C/C++语句描述，每个结点的两个域为值域data和指针域next）
2、若由3，6，8，12，10构成一棵哈夫曼树，则该树的高度是
（2），带权路径长度为（3）；
3、求从指定源点到其余各顶点的最短路径长度的算法中，弧上权须为正的原因是（4）；
4．图的（5）遍历是一种递归的算法，图的（6）遍历算法需要使用队列。
5．写出两个排序算法的名字,其平均排序时间为O（nlog2n）:
（7）。
6．有2049个结点的二叉树至少高（8）个结点；最大高度可达（9）。
7．在一棵二叉树中，度为1的结点有31个，总的结点数为50，则二叉树中叶子结点数共有（10）。
8．在一棵11阶B-树中，若在某结点中插入一个新关键字而引起该结点分裂时，则左边结点有
（11） 个关键字；右边结点的关键字数是（12） 。
9.快速排序在（13） 情况下效率最坏；此时，时间复杂度达到（14）
10．一个深度为k的，具有最少结点数的完全二叉树按层次，（同层次从左向右）用自然数依此对结点编号，则编号最小的叶子的序号是（15）；编号是i的结点所在的层次号是（16）（根所在的层次号规定为1层）。
三、简答题（40分）
2．已知有向图G有6个顶点（顶点号从1计），弧集E如下：
（其中弧后面冒号后数表示弧上的权）
E={<1，2>:
12，<1，4>:
15,<1,5>:
8,<2,3>:
13,<4,1>:
6,<4,3>:
25,<4,6>:
5,<5,4>:
5,
<5,6>:
20,<6,3>:
2,<6,5>:
7}
完成问题1）至4）
1）（3分）画出该有向图。
2）（3分）按Dijkstra算法,给出从顶点1（顶点标号从1计）到其余顶点的最短路径长度以及经过的中间点。
3）（3分）画出该图邻接表存储结构示意图。
4）（3分）上图去除弧上方向（去方向后，若两个顶点有两条边，去权值大的边），画出对应无向图的最小生成树，给出生成树边权之和。
2．已知关键字的集合{56，8，15，80，10，22，28，50，60,40,90}
（1）（4分）试按给出的序列构造一棵平衡二叉树。
（2）（4分）试构造3阶B_树。
（3）（4分）写出依次删除关键字56,90后的B_树。
（4）（4分）按以上数据,用链地址法处理冲突（Hash函数H（key）=key%13），画出示意图（不要写算法）
3．（4分）已知三棵树的森林如下，试把它转化为二叉树
AGN
/\/|\/\
BCHIKOP
/|\/\/|\
DEFLMRST
4．（4分）按大顶堆将序列{56，8，15，80，10，22，28，50，60,40,90}调整为堆，写出最后的数据序列
5．（4分）给出求最小生成树的Kruskal算法描述（不用写C/C++算法）
四、算法设计（用类-C/类-C++描述）（14分）
1．（7分）完成一个求二叉树叶子的递归算法treeleaf（p）。
（p为二叉树根）
2．（7分）有n个顶点的有向图用邻接表adj表示,写算法finddegree求出所有顶点的出度,结果放在数组outdegree[i]中（0≤i≤n）。
（outdegree[i]表示顶点i+1的出度,图的顶点号从1计）
南京理工大学课程考试试卷（学生考试用）
课程名称：
数据结构学分：
3大纲编号062204
试卷编号：
考试方式：
闭卷满分分值：
100考试时间：
120分钟
组卷日期：
2007年6月4日组卷教师（签字）张宏审定人（签字）王树梅
学生班级：
计算机学院05级
二、选择题（2*20=40分）
1.不是算法的基本特征
A）可行性B）长度有限C）在有限时间内完成D）确定性
2.某算法的时间复杂度为O（n2）,表明该算法的
A）问题规模是n2B）执行时间等于n2C）执行时间与n2成正比D）问题规模与n2成正比
3.设n个元素进栈序列是p1,p2,p3,…,pn，其输出序列是1,2,3,…,n,若p3=3,则p1的值为
A）可能是2B）一定是2C）不可能是1D）一定是1
4.链表不具备的特点是
A）可随机访问任一结点B）插入、删除不需要移动元素
C）不必事先估计存储空间D）所需空间与其长度成正比
5．最不合适用作链队的链表是。
A）只带队首指针的非循环单链表B）只带队首指针的循环双链表
C）只带队尾指针的循环双链表D）只带队尾指针的循环单链表
6．设二维数组A[6][10]，每个数组元素占用4个字节，若按行优先顺序存放时，数组元素A[3][5]的存储地址为1000，则A[0][0]的存储地址是
A）872B）860C）868D）864
7．以下不是堆的序列是。
A）100，85，98，77，80，60，82，40，20，10，66
B）100，98，85，82，80，77，66，60，40，20，10
C）10，20，40，60，66，77，80，82，85，98，100
D）100，85，40，77，80，60，66，98，82，10，20
8.一棵完全二叉树上有1001个结点，其中叶子结点的个数是
A）250B）500C）505D）501
9．无向图的邻接矩阵是一个矩阵。
A）对称B）零
升级会员 