第3部分 模拟试题及参考答案(2)

·6· 数据结构简明教程（C语言描述）

C) tail (head(head (tail(L)))) D) tail (tail (head (head (L))))

10．设有一个按元素值排好序的线性表且长度大于2，对给定的值k，分别用顺序查找法和二分查找法查找一个与k相等的元素，比较次数分别是s和b，在查找不成功的情况下，正确的s和b的数量关系是( )。

A) 总有 s=b B) 总有s>b C) 总有 s

二、填空题(20分)

l．已知完全二叉树有30个结点，则整个二叉树有___________个度为0的结点。

2．有数据WG={7,19,2,6,32,3,21,10}，则所建Huffman树的树高是___________，带权路径长度WPL为___________。

3．设有三对角矩阵如下图

将带状区中的元素ai,j(︱i﹣j︱≤1)放在一维数组B中，则B的大小为___________ ，元素ai,j在B中的位置是___________(下标从0开始)。

4．设关键字输入序列为(13,24,37,90,53)，则生成的平衡二叉树的根为___________，左子树中的数据是___________，右子树中的数据是___________。

5．下面程序段中带下划线的语句的执行次数的数量级是___________。

i=1;

while(i

6．无向图G=(V,E)，其中V(G)={1,2,3,4,5,6,7}，E(G)={(1,2),(1,3),(2,4),(2,5),(3,6),(3,7),(6,7),(5,1)}，对该图从顶点3开始进行遍历，去掉遍历中未走过的边，得一生成树G'=(V,E')，V(G')=V(G)，E(G')={(1,3),(3,6),(7,3),(1,2),(1,5),(2,4)}，则采用的遍历方法是___________。

三、判断题(10分)

1．存在这样的二叉树，对它采用任何次序的遍历，结果相同。( ) 2．队列和栈都是运算受限的线性表，只允许在表的两端进行运算。( ) 3．非空的广义表的表尾只能是一个子表而不可能是一个原子。( ) 4．有向图的邻接表和逆邻接表中的结点的个数可能不等。( ) 5．堆是一个完全二叉树，反之亦然。( )

6．链表是采用链式存储结构的线性表，进行插入、删除操作时，在链表中比在顺序存储结构中效率高。 ( )

7． 在图G的最小生成树中，可能会有某条边的权值超过未选边的权值。( )

8．二叉树中除叶结点外，任一结点x，其左子树根结点的值小于该结点x的值，其右子树根结点的值大于该结点x的值，则此二叉树一定是二叉排序树。( )

9．用二叉链表存储n个结点的二叉树，结点的2n个指针域中有n﹣1个空指针。( )

第3部分 模拟试题及参考答案 ·7·

10．给定一棵树，可以找到唯一的一棵二叉树与之对应。( ) 四、应用题(20分)

1．对下图所示二叉树分别按先序、中序、后序遍历，给出相应的结点序列，同时给二叉树加上后序后继线索。

2．给出下图所示AOE网的中的关键路径。

a3=3

a1=5

a4=6 a2=7

a5=3

a6=4 a9=2 a10=5 a7=4 a8=4

a11=5 a13=2

a12=4

3．对下图所示有向图，列出4种可能的拓扑有序序列。

A C B D F E 4．设一组数据为(1,14,27,29,55,68,10,11,23)，现采用的哈希函数是H(key)=key ，冲突用链地址法解决，设哈希表的大小为13(0..12)，试画出插入上述数据后的哈希表。

5．已知2-3树如图所示，当插入一个数85后，画出调整后的2-3树。

45 24 30 53 90 3 12 26 37 50 61 70 100 6．对给定文件(28,07,39,10,65,14,61,17,50,21)，选择第一个元素28进行划分，写出其快速排序第一趟的排序过程。

五、算法设计题(30分)

1．请设计一个算法，要求该算法把二叉树的叶子结点按从左到右的顺序连成一个单链表，表头指针为head。 二叉树按二叉链表方式存储，链接时用叶子结点的右指针域来存放单链表指针(10分)。

·8· 数据结构简明教程（C语言描述）

2．一个无向连通图的存储结构以邻接表的形式给定，删除该图中的一条边(i,j)。叙述思路并编写算法(10分)。

3．线性表(a1，a2，a3，…，an)中元素递增有序，且按顺序存于计算机内(10分)。要求设计一算法完成：

(1) 用最少的时间在表中查找数值为x的元素。

(2) 若找不到将其插入表中并使表中元素仍递增有序。

模拟试题4

一、选择题(20分)

1．在平衡二叉树中插入一个结点后造成了不平衡，最低的不平衡结点为A，并已知A的左孩子的平衡因子为1，则应作( )型调整以使其平衡。

A) LL B) LR C) RL D) RR 2．线性表( a1，a2，···，an)以链式方式存储时，访问第k个元素的时间复杂度为( )。 A) O(k) B) O(1) C) O(n) D) O(k﹣1) 3．以下数据结构中，是非线性数据结构( )。 A) 树 B) 字符串 C) 队 D) 栈 4．算术表达式A+B*(C+D/E)转为后缀表达式为( )。

A) AB+CDE/* B) ABCDE/+*+ C) ABCDE/*++ D) ABCDE*/++

5．循环队列存储在数组A[0..m]中，则入队时的队尾指针的操作为( )。 A) rear=rear+1 B) rear=(rear+1)%(m﹣1)

C) rear=(rear+1)% m D) rear=(rear+1)%(m+1)

6．下列排序方法中，( )不能保证每趟排序至少能将一个元素放到其最终位置上。 A) 快速排序 B) SHELL排序 C) 堆排序 D) 冒泡排序

7．一个栈的输入序列为1234..N，若输出序列的第一个元素是N，则输出序列的第i(1≤i≤N)个元素是( )。

A) 不确定 B) N﹣i+1 C) i D) N﹣i

8．将二叉树的概念推广到三叉树，则一棵有244个结点的完全三叉树的高度为( )。

A) 4 B) 5 C) 6 D) 7 9．下面关于求关键路径的说法不正确的是( )。

A) 一个事件的最迟开始时间为以该事件为尾的弧的活动最迟开始时间与该活动的持续时间的差 B) 一个事件的最早开始时间与以该事件为尾的弧的活动最早开始时间相同 C) 求关键路径是以拓扑排序为基础的 D) 关键活动一定位于关键路径上

10．在有向图G的拓扑序列中，若顶点vi在顶点vj之前，则下列情形不可能出现的是( )。 A) G中有弧

B) G中有一条从vi到vj的路径 C) G中没有弧

D) G中有一条从vj到vi的路径

第3部分 模拟试题及参考答案 ·9·

二、填空题(20分)

1．如果含n个顶点的图形成一个环，则它有___________棵生成树。 2．空格串是指______________________，其长度等于_____________。 3．广义表(a,(a,b),d,e,((i,j),k))的长度是___________，深度是___________。

4．假定有k个关键字互为同义词，若用线性探测再散列法把这k个关键字存入表中，至少要进行___________次探测。

5．设栈Ｓ和队列Ｑ初始均为空，若6个元素入栈的顺序为(a1,a2,a3,a4,a5,a6)。一个元素出栈之后立即入队列Ｑ，若6个元素出队的顺序为(a2,a4,a3,a6,a5,a1)，则栈的容量至少为___________。

6．设无向连通图G的顶点数与边数和一立方体相同 …… 此处隐藏：3355字，全部文档内容请下载后查看。喜欢就下载吧 ……