数据结构专升本模拟题及参考答案 下载本文

算法的易懂性和文档性

5. 下面程序段的时间复杂性的量极为( )。 Int fun(int n) { int i=1,s=1; While(s

C.O(n) D.O( ) 6. 线性表是( )。

A.一个有限序列,可以为空 B.一个有限序列,不能为空

C.一个无限序列,可以为空 D.一个无限序列,不能为空

7. 带头结点的单链表L为空的判定条件是( )。

A.L= =NULL B.L-〉next= =NULL

C.L-〉next= =L D.L! =NULL

8. 在一个长度为n的线性表中,删除值为x的元素时需要比较元素和移动元素的总次数为( )。

O(n/2)

A.(n+1)/2 B.n/2 C.n D.n+1 9. 一个顺序存储线性表的第一个元素的存储地址是90,每个元素的长度是2,则第6个元素的存储地址是( )。

A.98 B.100 C.102 D.106 10. 如果某链表中最常用的操作是取第i个结点及其前驱,则采用( )存储方式最节省时间。

A.单链表 B.双向链表

C.单循环链表 D.顺序表

二、填空题

1. 高度为2的二叉树的结点数至少有________个,高度为3的二叉树的结点数至少有________个。 2. 在顺序表(8,11,15,19,25,26,30,33,42,48,50)中,用折半查找关键字值20,需做的关键字比较次数为________。

3.在有n个顶点的无向图中,每个顶点的度最大可达________。

4.已知广义表A=((a,b,c),(d,e,f)),则广义表运算head(tail(tail(A)))= 。

5、数组(Array)是n(n≥1)个 的有序组合,数组中的数据是按顺序存储在一块 的存储单元中。

6. 采用顺序存储结构表示三元组表(Triple Table),来实现对稀疏矩阵的一种压缩存储形式,就称为 ,简称 表。

7. 运算是矩阵运算中最基本的一项,它是将一个m x n的矩阵变成另外一个n x m的矩阵,同时使原来矩阵中元素的行和列的位置互换而值保持不变。 三、应用题

1、对于下图所示的二叉树,画出二叉链表存储结构图。

2、请画出下图所示的树所对应的二叉树。

3. 已知一个无向图如下图所示,要求分别用Prim和

B A C D E

Kruskal算法生成最小树(假设以①为起点,试画出构造过程)。

4. 已知完全二叉树的第8层有8个结点,则其叶子结点是多少?

5. 画出如图所示中树的二叉树的表示形式。

作业题(四)

一、单项选择题

1. 将两个各有n个元素的有序表归并成一个有序表,其最少得比较次数是( )。 A

n