数据结构期末复习题

数据结构习题1

一、选择题

1、程序段如下：

sum=O；

for(i=l;i<=n;i++)

for(j=n;j>=l;j-)

sum++；

其中n为正整数，则最后一行的语句频度在最坏情况下是()。

A、O(n)B、O(nlog2n)

C、O(n3)D、O(n2)

2、二维数组A[8][8]按行优先顺序存储，若数组元素A[2]⑶的存储地址为1087,

A[4][5]的存储地址为1159,则数组元素A[6][7]的存储地址为()。

A、1223B、1227

C、1231D、1235

3、已知栈的最大容量为4o若进栈序列为1,2,3,4,5,6,且进栈和出栈可

以穿插进行，则不会出现的出栈序列为()。

A、4,3,2,1,5,6B、3,2,1,6,4,5

C、4,3,2,1,6,5D、3,2,1,6,5,4

4、已知广义表C=(a,(b,c),d),则:head(1就«/(0))为()

A>dB、c

C、bD、a

5、已知一棵完全二叉树有256个叶子结点，则该树可能达到的最大深度为()0

A.10B.11

C.8D.9

6、已知森林F={T1,T2,T3,T4,T5,T6},各棵树Ti（i=L2,3,4,5,6）中

所含结点的个数分别为18,2,3,4,5,6,将F按照左孩子右兄弟转化为二叉

树，则与F对应的二叉树的右子树的结点个数为（）o

A.19B.20

C.17D.18

7、对下图所示的无向图，从顶点1开始进行深度优先遍历，可得到顶点访问序

列（）。

A.1245637B.1243567

C.1243576D.1234576

A.16,72,31,23,94,53

B.94,23,31,72,16,53

C.16,53,23,94,31,72

D.16,23,53,31,94,72

9、对记录序列(314,508,298,123,486,145)依次按个位进行一趟基数排序之

后所得的结果为()o

A、298,123,508,486,145,314

B、508,314,123,145,486,298

C、123,314,145,486,298,508

D、123,314,145,486,508,298

10、已知关键字序列为(51,22,83,46,75,18,68,30),对其进行快速排序,

第一趟划分完成后的关键字序列是()o

A、(18,22,30,46,51,75,68,83)

B、(30,22,18,46,51,75,83,68)

C、(30,22,18,46,51,75,68,83)

D、(30,22,18,46,51,83,68,75)

二、填空题

1、使用一个30个元素的数组存储循环队列，如果采取少用一个元素空间的方法

来区别循环队列的队空和队满,约定队头指针front等于队尾指针rear时表示

队空。若为front=29,rear=0,则队列中的元素个数为。

2、一棵二叉树有30个叶子结点，仅有一个孩子的结点有20个，则该二叉树

共有个结点；若某棵完全二叉树共有100个结点，则该叶子结点数

为。

3、设某棵二叉树的中序遍历序列为ABCD,前序遍历序列为CABD,则后序遍历该

二叉树得到的线性序列为o

4、在有序表(22,34,46,58,70,82,94)中二分查找关键字22时所需进行

的关键字比较次数为o

5、将整数序列｛40,50,70,20,10,30｝中的数依次插入到一棵空的平衡二叉树中，画

出相应的平衡二叉树o

三、应用题

1、已知字符串'abaabababc',采用KMP算法，计算每个字符的next和nextval

函数的值。

2、假设某系统在通信联络中只可能出现5个字符(a,b,c,d,e),其概率分别为:

0.15,0.30,0.20,0.28,0.07,画出构造的Huffman树和Huffman编码。

3、设带权有向图如下所示:

求出源点V1到汇点V9之间的关键路径。

4、已知Hash函数为H(K)=Kmod9，哈希表长为9,用二次探测再散列

处理冲突,

给出关键字(23,34,56,24,75,12,49,52)在散列表中的分布，并求在等

概率情况下查找成功的平均查找长度。

5、已知3阶B-树如右图所示，画出将关键字18、110和120依次插入之后的B-

树。

OCDCDCD（6170、）（1001

四、程序阅读题

i、设有单链表类型定义如下：

voidf41(LinkListhead,intA,intB）

(

LinkListp=head;

while(p!=NULL)

(

if(p->data=>A&&p->data<=B)

printf(,,%d\nn,p->data);

p=p->next;

)

}

已知链表h如下图所示，给出执行f41(h,4,8）之后的输出结果;

h-------A|61+19〔十』||一|5|1A|

2、写出下面程序运行之后的结果。

voidf42(intn)//n为非负的十进制整数

int

SeqStackS;

InitStack(&S);〃堆栈初始化

do{

Push(&S,n%2);〃入栈

n=n/2;

Jwhile(n);

while(!StackEmpty(&S))//如果堆栈不空，循环

(

e=Pop(&S);〃出栈

printf(',%ld/,,e);

}

)

main()

{

f42(100);

)

3、假设以二叉链表作为二叉树的存储结构，其类型定义如下:

typedefstructnode{

chardata;

structnode*lchild,*rchild;//左右孩子指针

}BinTNode,*BinTree；

已知如图所示的二叉树以T为指向根结点

的指针，画出执行f43(T)

后的二叉树；

voidf43(BinTreeT){

BinTreetemp;

if(T){

f43(T->lchild);

if((T->Ichild)&&T->rchild)

temp=T->ichild->data;

T->lchild=T->rchild;

T->rchild=temp;

)

f43(T->rchild);

)

)

4、下面程序实现二分查找算法。

Typedefstruct{

KeyTypekey；

InfoTypeotherinfo；

}SeqList[N+l]；

intBinSearch(SeqListR,intn,KeyTypeK)

{intlow=l,high=n；

while((1)){

mid=(low+high)/2；

if((2))

returnmid；

if(R[mid].key>K)

high=mid-l；

else

⑶；

)

returnO；

}//BinSearch

请在空白处填写适当内容，使该程序功能完整