数据结构练习题1及答案

2012-3

一、单选题（每题 2 分，共20分） 1.以下数据结构中,( )是线性结构。

A.有向图 B.队列 C.线索二叉树 D.B树

2.在一个单链表HL中，若要在当前由指针p指向的结点后面插入一个由q指向的结点，则执行( )语句序列。

A.p=q；p->next=q； B.p->next=q； q->next=p； C.p->next=q->next； p=q； D.q->next=p->next； p->next=q； 3.( )不是队列的基本运算。

A.在队列第i个元素之后插入一个元素 B.从队头删除一个元素 C.判断一个队列是否为空 D.读取队头元素的值

4.字符A、B、C依次进入一个栈，按出栈的先后顺序组成不同的字符串，至多可以组成( )个不同的字符串。

A.14 B.5 C.6 D.8

5.由权值分别为3,8,6,2的叶子生成一棵哈夫曼树，它的带权路径长度为( )。

A． 11 B.35 C. 19 D. 53

6.下列二叉树的前序遍历序列为( )。

A.E,G,F,A,C,D,B B.E,A,G,C,F,B,D C.E,A,C,B,D,G,F D.E,G,A,C,D,F,B

二叉树

7.第6题二叉树的中序遍历序列为( )。

A.A,B,C,D,E,G,F B.E,A,G,C,F,B,D C.E,A,C,B,D,G,F D.B,D,C,A,F,G,E 8.第6题二叉树的层次遍历序列为( )。 A.E,G,F,A,C,D,B B.E,A,C,B,D,G,F

C.E,A,G,C,F,B,D D.E,G,A,C,D,F,B 9.下面关于图的存储的叙述中正确的是( )。

A.用邻接表法存储图,占用的存储空间大小只与图中边数有关，而与结点个数无关。

B.用邻接表法存储图,占用的存储空间大小与图中边数和结点个数都有关。 C.用邻接矩阵法存储图，占用的存储空间大小与图中结点个数和边数都有关。 D.用邻接矩阵法存储图,占用的存储空间大小只与图中边数有关，而与结点个数无关。

10.设有关键码序列(q,g,m,z,a,n,p,x,h)，下面( )序列是从该序列出发建成的

堆。

A.a,g,h,m,n,p,q,x,z B.a,g,m,h,q,n,p,x,z C.g,m,q,a,n,p,x,h,z D.h,g,m,p,a,n,q,x,z

二、填空题（每空1分，共26分）

1.数据的物理结构被分为______、______、______和_____四种。

2.对于一个长度为n的顺序存储的线性表，在表头插入元素的时间复杂度为______，在表尾插入元素的时间复杂度为_____。

3.向一个由HS指向的链栈中插入一个结点p时，需要执行的操作是____；删除一个结点时，需要执行的操作是____（假设栈不空而且无需回收被删除结点）。 4.对于一棵具有n个结点的二叉树，一个结点的编号为i(1≤i≤n)，若它有左孩子则左孩子结点的编号为___，若它有右孩子，则右孩子结点的编号为___，若它有双亲，则双亲结点的编号为___。

5.当向一个大根堆插入一个具有最大值的元素时，需要逐层___调整，直到被调整到____位置为止。

6.以二分查找方法从长度为10的有序表中查找一个元素时，平均查找长度为____。

7.表示图的三种常用的存储结构为_____、_____和____。

8.对于线性表（70，34，55，23，65，41，20）进行散列存储时，若选用H（K）=K %7作为散列函数，则散列地址为0的元素有_____个，散列地址为6的有____个。

9.在归并排序中，进行每趟归并的时间复杂度为___，整个排序过程的时间复杂度为_____，空间复杂度为_____。

10.在一棵m阶B_树上，每个非树根结点的关键字数目最少为____个，最多为____个，其子树数目最少为____，最多为____。

三、简答题（每题6分，共24分） 1.写出下列中缀表达式的后缀形式： （1）3X/(Y-2)+1 （2）2+X*(Y+3)

2.试对图2中的二叉树画出其：

(1)顺序存储表示的示意图； (2)二叉链表存储表示的示意图。

图2

(1){ 12, 70, 33, 65, 24, 56, 48, 92, 86, 33 }

(2){ 05, 23, 20, 28, 40, 38, 29, 61, 35, 76, 47, 100 }

3.判断以下序列是否是小根堆? 如果不是, 将它调整为小根堆。

4.已知一个图的顶点集V和边集E分别为： V={1,2,3,4,5,6,7};

E={(1,2)3,(1,3)5,(1,4)8,(2,5)10,(2,3)6,(3,4)15,(3,5)12, (3,6)9,(4,6)4,(4,7)20,(5,6)18,(6,7)25};

按照普里姆算法从顶点1出发得到最小生成树，试写出在最小生成树中依次得到的各条边。

四、阅读算法（每题7分，共14分） 1.void AE(Stack& S) {

InitStack(S)； Push(S,3)；

int x=Pop(S)+2*Pop(S)； Push(S,x)；

int i,a[5]={1,5,8,12,15}； for(i=0;i<5;i++) Push(S,2*a[i])； while(!StackEmpty(S)) cout<试指出算法被调用后得到的输出结果。 2.void ABC (BTNode *BT,int &c1,int &c2) { if (BT !=NULL )

Push(S,4)；

{ ABC(BT->left,c1,c2); c1++;

if(BT->left==NULL&&BT->right==NULL)c2++; ABC(BT->right,c1,c2); } }

试问该函数执行的功能是什么？

五、填空题（共8分）

向单链表的末尾添加一个元素的算法。

Void InsertRear(LNode*& HL,const ElemType& item) { LNode* newptr； newptr=new Lnode；

If ( _____________________ ) {

cerr<<\"Memory allocation failare!\"<_____________________=item； newptr->next=NULL； if (HL==NULL)

HL= __________________________ ； else {

LNode* P=HL；

while (P->next!=NULL) ___________________ ；

p->next=newptr； } }

六、编写算法（共8分）

编写从类型为List的线性表L中将第i个元素删除的算法，（假定不需要对i的值进行有效性检查,也不用判别L是否为空表。） void Delete(List& L, int i)

参

一、单选题（每题2分，共20分）

1.B 2.D 3.A 4.B 5.B 6.C 7.A 8.C 9.B 10.B

二、填空题（每空1分，共26分） 1. 顺序 链表 索引 散列 2. O(n) O(1)

3. p->next=HS;HS=p HS=HS->next 4. 2i 2i+1 i/2（或i/2） 5. 向上 根 6. 2.9

7. 邻接矩阵 邻接表 边集数组 8. 1 4

9. O(n) O(nlog2n) O(n)

10. m/2-1 m-1 m/2 m

三、简答题（每题6分，共24分）

1. (1) 3 X * Y 2 - / 1 +

(2) 2 X Y 3 + * + 2. （1）

0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 … 18 … 31 1 2 3 4 5 6 7 8 … 9 图3

（2）见图3所示：

3. (1)不是小根堆。调整为：{12,24,33,65,34,56,48,92,86,70} (2)是小根堆。

4. 普里姆算法从顶点1出发得到最小生成树为：

(1,2)3, (1,3)5, (1,4)8, (4,6)4, (2,5)10, (4,7)20

四、阅读算法（每题7分，共14分） 1.30 24 16 10 2 10

2.该函数的功能是：统计出BT所指向的二叉树的结点总数和叶子总数。

五、算法填空（共8分，每一空2分）

newptr==NULL newptr->=data newptr p=p->next

六、编写算法（8分）

void Delete(List& L, int i)

{ for(int j=i-1；jL.list[j]=L.list[j+1]； //第i个元素的下标为i-1

L.size--； }