计算机科学与技术专业2011级《数据结构》期中考试

计算机科学与技术专业2011级《数据结构》期中考试

一、选择题（单号仅做单序号题目，双号仅做双序号题目；四个选项中只有一个是正确的，每小题3分，共30分）

1、数据在计算机内存中的表示是指（A）

A)数据的存储结构

B)数据结构

C)数据的逻辑结构

D)数据元素之间的关系

2、在数据结构中，与所使用的计算机无关的数据结构是（A）

A)逻辑结构

B)存储结构

C)逻辑和存储结构

D)物理结构

3、链表不具备的特点是（A）

A)可随机访问任意一个结点

B)插入和删除不需要移动任何元素

C)不必事先估计存储空间

D)所需空间与其长度成正比

4、对线性表，在下列情况下应当采用链表表示的是（B）

A)经常需要随机存取元素

B)经常需要进行插入和删除操作

C)表中元素需要占据一片连续的存储空间

D)表中的元素个数不变

5、若已知一个栈的进栈序列是1，2，3……n，其输出序列是p1，p2，p3，pn，若p1=n，则pi（1<i<n）为（C）

A)i

B)N-i

C)N-i+1

D)不确定

6、若已知一个栈的进栈序列是1，2，3……n，其输出序列是p1，p2，p3，pn，若p1=3，

则p2为（A）

A)可能是2

B)一定是2

C)可能是1

D)一定是1

7、不带头结点的单链表head为空的判定条件是（A）

A)head=NULL

B)head->next=NULL

C)head->next=head

D)head!=NULL

8、带头结点的单链表head为空的判定条件是（B）

A)head=NULL

B)head->next=NULL

C)head->next=head

D)head!=NULL

9、在一个链式队列中，假设f和r分别为队头和队尾指针，则插入s所指结点的运算是（B）

A)f->next=s;f=s;

B)r->next=s;r=s;

C)s->next=r;r=s;

D)s->next=f;f=s;

10、在一个链队列中，假设f和r分别为队头和队尾指针，则删除结点的运算是（C）

A)r=f->next;

B)r=r->next;

C)f=f->next;

D)f=r->next;

11、下列有关树的概念错误的是（B）

A)一棵树中只有一个无前驱的结点

B)一棵树的度为树中各个结点的度之和

C)一棵树中，每个结点的度数等于结点总数减一

D)一棵树中每个结点的度数之和与边的条数相等

12、下面关于二叉树的叙述正确的是（A）

A)一棵二叉树中叶子结点的个数等于度为2的结点个数加1

B)一棵二叉树中结点的个数大于0

C)二叉树中任何一个结点要么是叶，要么恰有两个孩子

D)二叉树中，任何一个结点的左子树和右子树的结点个数一定相等

13、已知某二叉树的后序遍历序列是DACBE,中序遍历序列是DEBAC，则它的前序遍历序列是（D）

A)ACBED

B)DEABC

C)DECAB

D)EDBCA

14、一棵二叉树的前序遍历序列为ABDGCFK，中序遍历为DGBAFCK，则结点的后序遍历序列是（B）

A)ACFKDBG

B)GDBFKCA

C)KCFAGDB

D)ABCDFKG

15、算法指的是（D）

A)计算机程序

B)解决问题的计算方法

C)排序算法

D)解决问题的有限运算序列

16、算法能正确地实现预定功能的特性称为算法的（A）

A)正确性

B)易读性

C)健壮性

D)高效性

17、执行下面程序段时，执行S语句的次数为（D）

for(inti=1;i<=n;i++)

for(intj=1;j<=i;j++)

S;

A)n2

B)n2/2D

C)n(n+1)

D)n(n+1)/2

18、下面程序段的时间复杂度是（D）

for(inti=0;i<n;i++)

for(intj=1;j<m;j++)

A[i][j]=0;

A)O(n)

B)O(m+n+1)

C)O(m+n)

D)O(m*n)

19、某线性表采用顺序存储结构，每个元素占4个存储单元，首地址为100，则第12个元素的存储地址为（A）

A)144

B)145

C)147

D)148

20、设线性表的顺序存储结构中，每个元素占用1个存储单元，表的第1个元素的存储地址为d，则第i个元素（1<=i<=n,n为表长）的存储地址为（A）

A)d+(i-1)*1

B)d+i*1

C)d+(i+1)*1

D)d+i*1-1

二、填空题（每小题4分，共32分）

1、在一个单链表中的p所指向结点之前插入一个s所指的结点时，可以执行如下操作：

（1）s->next=p->next;

（2）p->next=s;

（3）t=p->data;

（4）p->data=s->data;

（5）s->data=t;

2、设树T的度为4，其中度为1，2，3和4的结点的个数分别为4，2，1，1，则T中叶子结点的个数为（8）。

深度为k的完全二叉树至少有(2k-1)（2的k-1次方）个结点，至多有（2k-1）（2的k次方减1）个结点，若按自上而下，从左向右的次序编号（从1开始），则编号最小的叶子结点的编号是（2k-2+1）（2的k-2次方减1）

3、现有按中序遍历二叉树的结果为abc，问有（5）种不同形态的二叉树可以得到这一遍历结果。

4、对于一个长度为n的单链表，在表头插入元素的时间复杂度为（O(1)），在表尾插入元素的时间复杂度为（O(n)）。

5、用数组A[1…N]顺序存储完全二叉树的各结点，则当I<=(n-1)/2时，结点A[I]的右孩子是结点（A[2i+1]）。

6、若一棵二叉树中只有叶结点和左、右子树皆非空的结点，设叶结点的个数为K，则左、右子树皆非空的结点个数是（k-1）。

7、设F是由T1,T2和T3三棵树组成的森林，与F对应的二叉树为B，已知T1,T2和T3的结点个数分别是n1,n2,n3，则二叉树B的根结点的左子树和右子树中的结点个数分别是(n1-1、n2+n3)。

三、综合题（共38分）

1、设计一个算法，通过一趟遍历确定单链表中值最大的结点。（7分）

LinkListmaxnode(LinkListL)

{//在带头结点的单链表L中通过一趟遍历，查找值最大的结点并返回其地址

LinkListp=L->next,q=p;

while(p)

{if(p->data>q->data)

q=p;

p=p->next;

}

returnq;

}

2、编写算法对非递减有序的顺序表进行元素唯一化（即：使顺序表中重复的元素只保留一个），要求算法的时间复杂度为O(n)。（14分）

voidUnique(SqList&L)

{//对非递减有序的顺序表L进行元素唯一化

i=0;

for(j=1;j<L.length;j++)

if(L.elem[j]!=L.elem[i-1])

{if(j!=i)L.elem[i]=L.elem[j];

i++;

}

L.length=i;//更新表长

}

3、编写一个算法，输出一个二叉树的所有叶子结点。（7分）

voidfindLeaf(BinTreeT)

{

if(T)

{if(T->lchild==NULL&&T->rchild==NULL)

cout<<T->data;

else{findLeaf(T->lchild);

findLeaf(T->rchild);

}

}

}

4、以数据集{9,6,2,5,8,13,17}为权值构造一棵huffman树，并计算其带权路径长度。（10分）

WPL=（13+17）*2+（6+8+9）*3+（2+5）*4=157