大学专业试卷数据结构试卷下(B).doc

数据结构期末考试试卷（B）
一大题 单选题（每小题2分 ，共30分）
1．下列叙述中中正确的是（ ）
A．一个逻辑数据结构只能有一种存储结构
B．数据的逻辑结构属于线性结构，存储结构属于非线性结构
C．一个逻辑数据结构可以有多种存储结构，且各种存储结构影响数据处理的效率
D．一个逻辑数据结构可以有多种存储结构，且各种存储结构不影响数据处理的效率
2.某带头结点的单链表的头指针为head，判定该链表为非空的条件是( )
A.head==NULL B.head->next==NULL
C.head!=NULL D.head->next!=NULL
3.若进栈序列为1，2，3，4，5，6，且进栈和出栈可以穿插进行，则可能出现的出栈序列为（　　　）
A．3，2，6，1，4，5 B．3，4，2，1，6，5
C．1，2，5，3，4，6 D．5，6，4，2，3，1
4．设树T的度为4，其中度为1,2,3，和4的结点个数分别为4,2,1,1，则，T中的叶子数为（ ）
A．6 B.7 C.8 D.5
5. 栈和队列的共同点是（ ）
A. 都是先进先出 B.都是先进后出
C.只允许在端点处插入和删除元素 D.没有共同点
6.假设一棵完全二叉树按层次遍历的顺序依次存放在数组BT[m]中，其中根结点存放在BT[0]，若BT[i]中的结点有左孩子，则左孩子存放在( )
A.BT[i/2] B.BT[2*i-1]
C.BT[2*i] D.BT[2*i+1]
7..连通图是指图中任两个顶点之间( )
A.都连通的无向图 B.都不连通的无向图
C.都连通的有向图 D.都不连通的有向图
8. 二维数组A[8][9]按行优先顺序存储，若数组元素A[2][3]的存储地址为1087，A[4][7]的存储地址为1153，则数组元素A[6][7]的存储地址为（　　　）
A．1207 B．1209 C．1211 D．1213
9．若用邻接矩阵表示一个有向图，则其中每一列包含的″1″的个数为（　　　）
A．图中每个顶点的入度 B．图中每个顶点的出度
C．图中弧的条数 D．图中连通分量的数目
10. 如图所示的4棵二叉树中，（ ）不是完全二叉树。

A. B. C. D.
11. 在一是个具有n个顶点的有向图中，若具有e条边，则所有顶点的度数之和为（ ）
A. n B. e C. n+e D. 2e
12.以下数据结构中，（ ）是非线性数据结构
A．树 B．字符串 C．队 D．栈
13.在单链表指针为p的结点之后插入指针为s的结点，正确的操作是：（ ）。
A．p->next=s; s->next=p->next; B． s->next=p->next; p->next=s;
C．p->next=s； p->next=s->next; D． p->next=s->next; p->next=s;
14. 若串S=“software”,其子串的数目是（ ）。
A．8 B．37 C．36 D．9
15. 假定一棵三叉树的结点数为50，规定根结点的层次从0开始，则它的最小深度为（ ）。
A．3 B.4 C. 5 D.6

二大题 填空题（每空1分，共10分）
1.对于给定的n个元素,可以构造出的逻辑结构有 （1） ， （2） ， （3） 。
2. 在双向链表中，每个结点含有两个指针域，一个指向 （4） 结点，另一个指向 （5） 结点。
3. 队列是限制插入只能在表的一端，而删除在表的另一端进行的线性表，其特点是 （6） 。
4. 循环队列的引入，目的是为了克服 （7） 。
5.设一棵完全二叉树共有699个结点，则在该二叉树中的叶子节点数为　　（８）　　　，度为２的结点个数为　　　（９）　　　　。
6. 深度为k的完全二叉树至多有 （１０） 个结点。(注:空树的深度为-1)

三大题　应用题（每小题10分，共４0分）
1．已知二叉树的先序序列和中序序列分别为HDACBGFE和ADCBHFEG。
（1）画出该二叉树；（5分）
（2）写出该二叉树的后序遍历和层次遍历。（5分）
2．若字母A,B,C,D,E,F给定一组权值{5，9，11，2，7，16}，试设计相应的哈夫曼树和字母相应的哈夫编码。
3． 画出该图的邻接矩阵存储结构图,并按照邻接矩阵存储结构给出每个结点的邻接结点次序，给出该有向图的深度优先遍历的结点访问序列。
A
D
F
C
E
B
10

8
12
25
9
30
20
22
5

４．将下列由三棵树组成的森林转换为二叉树。（只要求给出转换结果）
N

P

G

H

J

M

O

L

I

K

E

D

F

B

A

C

四大题　程序设计题（每小题10分，共２０分）
１. 设头指针为head,并设带头结点的单链表中的数据元素递增有序，编写算法将 后数据元素X插入到带头结点单链表的合适位置上，要求插入后保持单链表数据元素的递增有序。
2. 在二叉树的链式存储结构下设计算法：求一棵二叉树的结点总数。

2