2000数据结构b
- 格式：doc
- 大小：46.00 KB
- 文档页数：3
…………密…………封…………线…………内…………请…………不…………要…………答…………题…………
一、单项选择题（从下列各题四个备选答案中选出一个正确答案，每小题2分，共20分）
1.算法分析的两个主要方面是（）
A.空间复杂性和时间复杂性
B.正确性和简明性
C.可读性和文档性
D.数据复杂性和程序复杂性
2．在以下的叙述种正确的是 ( )
A.线性表的顺序存储结构优于链式存储结构
B.二维数组是其数据元素为线性表的线性表
C.栈的操作方式是先进先出
D.队列的操作方式是后进先出
3. 循环队列用数组A[0,m-1]存放其元素值，已知其头尾指针分别是 front和 rear,则当前队列中的元素个数是（）
A. ( rear-front+m)%m
B. rear-front+1
C. rear-front-1
D. rear-front
4. 带头结点的单链表head为空的判定条件是 ( )
A. head==NULL
B.head->next==NULL
C. head->next==head
D.head!=NULL
5.在双循环链表的p指针所指结点之后插入s指针所指结点的操作是（）。
A.p->next=s; s->priou=p; p->next->priou=s; s->next=p->next
B.p->next=s; p->next->priou=s; s->priou=p; s->next=p->next
C.s->priou=p;s->next=p->next;p->next=s; p->next->priou=s;
D.s->priou=p;s->next=p->next;p->next->priou=s; p->next=s;
6.稀疏矩阵一般的压缩存储方法有两种，即（）
A. 二维数组和三维数组表
B. 三元组和散列
C. 三元组表和十字链表
D.散列和十字链表
7.广义表A=（a,b,(c,d),(e,(f,g))）,则下面式子的值为（）；
Head(Tail(Head(Tail(Tail(A)))))
A．（g） B.(d) C.c D.d
…………密…………封…………线…………内…………请…………不…………要…………答…………题…………
8.有分别带权为9，2，5，7的四个叶子结点构造一棵哈夫曼树，该树的带权路径长度为（）
A. 23
B.37
C.44
D.46
9.有拓扑序列的图一定是（）。
A.有环图
B.无向图
C.强连通图
D.有向无环图
10.利用逐点插入法建立序列(50，72，43，85，75，20，35，45，65，30)对应的二叉排序树以后，查找元素35要进行( )元素间的比较。
A．4次 B．5次 C. 7次 D．10次
二、填空（每空1分，共20分）
1．长度为n的顺序表，插入和删除元素的时间复杂性为__________;顺序存储的栈和队列，插入和删除元素的时间复杂性为__________。
2.非空单循环链表L中,指针p所指结点是尾结点的条件是__________________。
3.在一个单链表中p所指结点之后插入一个由指针s所指结点，应执行s->next=________;和p->next=_____________的操作。
4．有n个结点的树，则该树中所有结点的度之和为____________。
5.设有二维数组A[0..9,0..19]，其每个元素占两个字节，第一个元素的存储地址为100，若按行优先顺序存储，则元素A[4,6]的存储地址为________ ，按列优顺序存储，元素A[4,6]的存储地址为__________ 。
6.试找出满足下面条件的所有二叉树：前序序列和中序序列相同____________________；中序序列和后序序列相同_________________。
7．二叉树以二叉链表为存储结构，在有n(n>0)个结点的二叉树中，空链域的个数为_____________。
8．假定一棵二叉树的结点数为18，则它的最小高度为_______，最大高度为__________。
9.一个连通图的生成树是一个_______连通子图，n个顶点的生成树有_______条边。
10．具有n个顶点的无向完全图，边的总数为_______条；而在n个顶点的有向完全图中，边的总数为_______条。
11.设s=’IAMASTUDENT’,t=’GOOD’,q=’WORKER’; 函数SubString(s,5,7)的值为____________;函数Index(s,t) 的值为________;函数Replace(s,’STUDENT’,q)的值为______________。
三、回答下列问题（1—4题每题5分，5题10分，共30分）
1．已知一棵二叉树的前序遍历的结果是ABECDFGHIJ, 中序遍历的结果是EBCDAFHIGJ, 试画出这棵二叉树。
2．假设字符a,b,c,d,e,f的使用频度分别是0.07,0.09,0.12,0.22,0.23,0.27，构造哈夫曼树，并求a,b,c,d,e,f的Huffman（哈夫曼）编码。
…………密…………封…………线…………内…………请…………不…………要…………答…………题…………
3．对如图1，用prim 算法构造一棵最小生成树，写出构造过程。
4．设哈希函数为H(k)=k MOD 13 ,用线性探测法解决冲突，请画出在
0—12
的哈希空间中，对于关键字序列
32,17,10,73,45,89,92,36,80,27,19,58构造哈希表，并计算在等概率情况下的平均查找长度。
5．试对右图所示的AOE 网络，解答下列问题。
(1) 这个工程最早可能在什么时间结束。
(2) 求每个事件的最早开始时间Ve （i ）和最迟开始
时间Vl(i)。
(3) 求每个活动的最早开始时间e( )和最迟开始时间l( )。
(4) 确定哪些活动是关键活动。
画出由所有关键活动构成的图，指出哪些活动加速可使整个工程提前完成。
四、算法设计题（共30分）
1．设有一个由正整数组成的无序（向后）单链表，编写算法完成如下功能： 找出最小值结点，且打印该数值。
2.设二叉树采用二叉链表表示，各结点结构为：
编写递归算法，求二叉树中元素值为x 的结点在先序序列中的位置（假定二叉树中有惟一的值为x 的元素）。
3将二分查找算法改写为递归算法。
