数据结构C语言版期末考试试题（有答案）2017-1-1218.14.59
抢时间，抓基础，勤演练定有收获；树自信，誓拼搏，升大学回报父母。
"数据结构"期末考试试题
一、单选题(每小题2分
共12分)
1．在一个单链表HL中
若要向表头插入一个由指针p指向的结点
则执行( )
A． HL＝ps p一>next＝HL
B． p一>next＝HL；HL＝p3
C． p一>next＝Hl；p＝HL；
D． p一>next＝HL一>next;HL一>next＝p；
2．n个顶点的强连通图中至少含有( )
A.n-l条有向边
B.n条有向边
C.n(n-1)／2条有向边
D.n(n一1)条有向边
3.从一棵二叉搜索树中查一个元素时
其时间复杂度大致为( )
A.O(1)
B.O(n)
C.O(1Ogzn)
D.O(n2)
4．由权值分别为3
8
6
2
5的叶子结点生成一棵哈夫曼树
它的带权路径长度为( )
A．24 B．48
C． 72 D． 53
5．当一个作为实际传递的对象占用的存储空间较大并可能需要修改时
应最好把它说明为( )参数
以节省参数值的传输时间和存储参数的空间
A.整形
B.引用型
C.指针型
D.常值引用型·
6．向一个长度为n的顺序表中插人一个新元素的平均时间复杂度为( )
A．O(n) B．O(1)
C．O(n2) D．O(10g2n)
二、填空题(每空1分
共28分)
1．数据的存储结构被分为--、--、--和--四种
2．在广义表的存储结构中
单元素结点与表元素结点有一个域对应不同
各自分别为--域和--域
3．--中缀表达式 3十x*(2.4／5-6)所对应的后缀表达式为----
4．在一棵高度为h的3叉树中
最多含有--结点
5．假定一棵二叉树的结点数为18
则它的最小深度为--
最大深度为--·
6．在一棵二叉搜索树中
每个分支结点的左子树上所有结点的值一定--该结点的值
右子树上所有结点的值一定--该结点的值
7．当向一个小根堆插入一个具有最小值的元素时
该元素需要逐层--调整
直到被调整到--位置为止
8．表示图的三种存储结构为--、--和---
9．对用邻接矩阵表示的具有n个顶点和e条边的图进行任一种遍历时其时间复杂度为--
对用邻接表表示的图进行任一种遍历时
其时间复杂度为--
10．从有序表(12
18
30
43
56
78
82
95)中依次二分查43和56元素时
其查长度分别为--和--·
11．假定对长度n＝144的线性表进行索引顺序查
并假定每个子表的长度均为
则进行索引顺序查的平均查长度为--
时间复杂度为--·
12．一棵B-树中的所有叶子结点均处在--上
13．每次从无序表中顺序取出一个元素
把这插入到有序表中的适当位置
数据结构与算法题库
此种排序方法叫做--排序；每次从无序表中挑选出一个最小或最大元素把它交换到有序表的一端
此种排序方法叫做--排序
14．快速排序在乎均情况下的时间复杂度为--
最坏情况下的时间复杂度为--
三、运算题(每小题6分
共24分)
1．假定一棵二叉树广义表表示为a(b(c
d)
c(((
8)))
分别写出对它进行先序、中序、后序和后序遍历的结果
先序：
中序；
后序：
2．已知一个带权图的顶点集V和边集G分别为：
V＝{0
1
2
3
4
5}；
E={(0
1)8
(0
2)5
(0
3)2
(1
5)6
(2
3)25
(2
4)13
(3
5)9
(4
5)10}
则求出该图的最小生成树的权
最小生成树的权；
3．假定一组记录的排序码为(46
79
56
38
40
84
50
42)
则利用堆排序方法建立的初始堆为--
4．有7个带权结点
其权值分别为3
7
8
2
6
10
14
试以它们为叶子结点生成一棵哈夫曼树
求出该树的带权路径长度、高度、双分支结点数带权路径长度：-- 高度：-- 双分支结点数：--
四、阅读算法
回答问题(每小题8分
共16分)
1．VOldAC(List&L)
{
InitList(L)；
InsertRear(L;25)；
InsertFront(L
50)；
IntaL4]＝{5
8
12
15
36};
for(inti＝0; i<5; i++)

版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。