内容发布更新时间 : 2024/11/20 2:21:52星期一 下面是文章的全部内容请认真阅读。

抢时间，抓基础，勤演练定有收获；树自信，誓拼搏，升大学回报父母。 \数据结构\期末考试试题 一、单选题(每小题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．数据的存储结构被分为--、--、--和--四种

word文档 可自由复制编辑

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．每次从无序表中顺序取出一个元素 把这插入到有序表中的适当位置

word文档 可自由复制编辑

此种排序方法叫做--排序；每次从无序表中挑选出一个最小或最大元素 把它交换到有序表的一端 此种排序方法叫做--排序

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}

则求出该图的最小生成树的权

word文档 可自由复制编辑