浙江广播电视大学数据结构期末复习题.docx

浙江广播电视大学数据结构期末复习题.docx

《浙江广播电视大学数据结构期末复习题.docx》由会员分享，可在线阅读，更多相关《浙江广播电视大学数据结构期末复习题.docx（23页珍藏版）》请在冰点文库上搜索。

浙江广播电视大学数据结构期末复习题

浙江广播电视大学《数据结构》期末复习题

2005年12月

一、单选题

1．某程序的时间复杂度为（3n+nlog2n+n2+8）,其数量级表示为（）。

A．O（n）B．O（nlog2n）

C．O（n2）D．O（log2n）

2．队列的插入操作是在（）进行。

A．队首B．队尾

C．队前D．对后

3．二叉树上叶结点数等于（）。

A．分支结点数加1B．单分支结点数加1

C．双分支结点数加1D．双分支结点数减1

4．每次从无序表中取出一个元素，把它插入到有序表中的适当位置，此种排序方法叫做（）排序

A．插入B．交换

C．选择D．归并

5．在一个图中，所有顶点的度数之和等于所有边数的（）倍。

A．2B．1

C．3D．4

6．队列的删除操作是在（）进行。

A．队首B．队尾

C．队前D．对后

7．当利用大小为N的数组顺序存储一个栈时，假定用top==N表示栈空，则退栈时，用（）语句修改top指针。

A．top++;B．top=0;

C．top--;D．top=N;

8．由权值分别为3,6,7,2,5的叶子结点生成一棵哈夫曼树，它的带权路径长度为（）。

A．51B．23

C．53D．74

9．在一棵二叉树中，第4层上的结点数最多为（）。

A．31B．8

C．15D．16

10．向堆中插入一个元素的时间复杂度为（）。

A．O（log2n）B．O（n）

C．O

（1）D．16O（nlog2n）

11．在一个长度为n的顺序存储的线性表中，向第i个元素（1≤i≤n+1）之前插入一个新元素时，需要从后向前依次后移（）个元素。

A．n-iB．n-i+1

C．n-i-1D．i

12．在线性表的散列存储中，若用m表示散列表的长度，n表示待散列存储的元素的个数，则装填因子α等于（）。

A．n/mB．m/n

C．n/（n+m）D．m/（n+m）

13．从一棵B_树删除元素的过程中，若最终引起树根结点的合并，则新树高度是（）。

A．原树高度加1B．原树高度减1

C．原树高度D．不确定

14．在稀疏矩阵的带行指针向量的链接存储中，每个行单链表中的结点都具有相同的（）。

A．行号B．列号

C．元素值D．地址

15．在一个具有n个顶点的无向图中，要连通所有顶点则至少需要（）条边。

A．nB．2n

C．n-1D．n+1

16．某程序的时间复杂度为（10n+nlog2n+n2）,其数量级表示为（）。

A．O（n）B．O（nlog2n）

C．O（n2）D．O（log2n）

17．在一个长度为n的顺序存储的线性表中，向第i个元素（1≤i≤n+1）之前插入一个新元素时，需要从后向前依次后移（）个元素。

A．n-iB．n-i+1

C．n-i-1D．i

18．在一棵二叉搜索树中，每个分支结点的左子树上所有结点的值一定（）该结点的值。

A．小于B．大于

C．不小于D．大于等于

19．对于一棵具有n个结点的树，该树中所有结点的度数之和为（）。

A．n-1B．n

C．n+1D．2n

20．某程序的时间复杂度为（3n+100×log2n+nlog2n）,其数量级表示为（）。

A．O（n）B．O（nlog2n）

C．O（100）D．O（log2n）

21．在一个单链表中,若q所指结点是p所指结点的前驱结点,若在q与p之间插入一个s所指的结点,则执行（）。

A．s→link=p→link;p→link=s;B．p→link=s;s→link=q;

C．p→link=s→link;s→link=p;D．q→link=s;s→link=p;

22．根据n个元素建立一棵二叉搜索树时，其时间复杂度大致为（）。

A．O（n）B．O（log2n）

C．O（n2）D．O（nlog2n）

二、填空题

1．一个算法应具备的5个特性为、、、

、。

2．在采用独立结点构成的双向链表中，设p和q分别是具有Dnode*类型的指针变量。

若双向链表中p结点之后插入一个q结点，其操作步骤为：

；

；

；

；

3．表示图的三种存储结构为、和。

4．假定一棵二叉树广义表表示为a（b（c,d），e（,f）），则对它进行的先序遍历结果为____________，中序遍历结果为____________，后序遍历结果为____________，按层遍历结果为____________。

5．当从一个小根堆中删除一个元素时，需要把________元素填补到________位置，然后再按条件把它逐层________调整。

6．二叉搜索树的中序遍历得到的结点序列为________。

7．数据的存储结构被分为____________、___________、____________和____________四种。

8．若对一棵二叉树的结点编号从0开始顺序编码，按顺序存储，把编号为0的结点存储到a[0]中，其余类推，则a[i]元素的左孩子元素为________，右孩子元素为________，双亲元素（i>0）为________。

9．从一个栈删除元素时，首先取出，然后再前移一位。

10．后缀表达式“210+5*6–9/”的值为。

11．假定一棵树的广义表表示为A（B（C（D,E）,F,G（H,I,J））,K），则度为3、2、1、0的结点数分别为______、______、______和______个。

12．在一个具有n个顶点的无向完全图中，包含有________条边，在一个具有n个顶点的有向完全图中，包含有________条边。

13．在索引表中，若一个索引项对应主表中的一条记录，则称此索引为________索引，若对应主表中的若干条记录，则称此索引为________索引。

14．对于二分查找所对应的判定树，它既是一棵_____，又是一棵__________。

15．对于双目操作符，其重载函数带有__________个参数，其中至少有一个为____________的类型。

16．从一维数组a[n]中顺序查找出一个最大值元素的时间复杂度为________，输出一个二维数组b[m][n]中所有元素值的时间复杂度为________。

17．在归并排序中，进行每趟归并的时间复杂度为________，整个排序过程的时间复杂度为________，空间复杂度为________。

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

19．当从一个小根堆中删除一个元素时，需要把________元素填补到________位置，然后再按条件把它逐层________调整。

20．快速排序在平均情况下的时间复杂度为________，在最坏情况下的时间复杂度为________。

21．从一棵二叉搜索树中查找一个元素时，若元素的值等于根结点的值，则表明_______，若元素的值小于根结点的值，则继续向________查找，若元素的大于根结点的值，则继续向________查找。

22．在一个单链表HL中，若要向表头插入一个由指针p指向的结点，则应执行语句：

。

23．若对一棵二叉树的结点编号从0开始顺序编码，按顺序存储，把编号为0的结点存储到a[0]中，其余类推，则a[i]元素的左孩子元素为________，右孩子元素为________，双亲元素（i>0）为________。

24．在循环单链表中，最后一个结点的指针域指向________结点。

25．假定一棵树的广义表表示为A（B（C,D（E,F,G）,H（I,J））），则结点D的双亲结点为________，孩子结点为___________。

26．后缀表达式“216+5–6–9*”的值为。

27．在一棵高度为5的理想平衡树中，最多含有________个结点，最少含有________个结点。

28．二叉搜索树的中序遍历得到的结点序列为________。

29．在以HL为表头指针的带表头附加结点的单链表和循环单链表中，判断链表为空的条件分别为________________和____________________。

30．假定一个线性表为（”abcd”,”baabd”,”bcef”,”cfg”,”ahij”,”bkwte”,”ccdt”,”aayb”），若按照字符串的第一个字母进行划分，使得同一个字母被划分在一个子表中，则得到的a,b,c三个子表的长度分别为________、________和________。

三、运算题

1．已知一个中缀算术表达式为：

3+4*（25-（6/15））-8@，写出对应的后缀算术表达式。

2．对以下图，试给出一种拓扑序列，若在它的邻接表存储结构中，每个顶点邻接表中的边结点都是按照终点序号从大到小链接的，则按此给出唯一一种拓扑序列。

3.空堆开始依次向堆中插入线性表（64,52,12,48,45,26）中的每个元素，请以线性表的形式给出每插入一个元素后堆的状态。

（为小根堆）

４．在一份电文中共使用五种字符：

A，G，F，U，Y，Z，它们的出现频率依次为12,9,18,7,14，11，求出每个字符的哈夫曼编码。

5．假定一个待散列存储的线性表为（37,65,25,73,42,91,45,36,18,75），散列地址空间为HT[12]，若采用除留余数法构造散列函数和链接法处理冲突，试求出每一元素的散列地址，画出最后得到的散列表，求出平均查找长度。

6．对于下图，若按照克鲁斯卡尔算法产生最小生成树，写出得到的各条边的次序。

7．有七个带权结点，其权值分别为3,7,8,2,6,10,14，试以它们为叶子结点构造一棵哈夫曼树，并计算出带权路径长度WPL。

8。

已知一组记录的排序码为（46，79，56，38，40，80,95，24），写出对其进行快速排序的每一次划分结果。

9．已知一个中缀算术表达式为：

25-（6/15）+（15/8）@，写出对应的后缀算术表达式。

10．在一份电文中共使用五种字符：

A，G，F，U，Y，Z，它们的出现频率依次为4,9,8,17,14，11，求出每个字符的哈夫曼编码。

11．一个线性表为B=（12，23，45，57，20，03，78，31，15，36），设散列表为HT[0..12]，散列函数为H（key）=key%13并用线性探查法解决冲突，请画出散列表，并计算等概率情况下查找成功的平均查找长度。

四、阅读算法，回答问题

1．intAA（LNode*HL,ElemTypex）

{

intn=0;

LNode*p=HL;

while（p!

=NULL）

{

if（p->data==x）n++;

p=p->next;

}

returnn;

}

对于结点类型为LNode的单链表，以上算法的功能为：

2．intBB（ElemTypeA[],intn,KeyTypeK）

{

for（inti=0;i

if（A[i].key==K）break;

if（i

elsereturn–1;

}

该算法的功能是：

3．voidCC（Stack&S）

{

Pop（S）;

Push（S,50）;

Push（S,45）;

Peek（S）;

}

假定调用算法时栈S中已有2个元素（23，16）的栈，其中23时栈底，调用后得到的栈内容为（从栈底开始排列）：

4．voidDD（ElemTypeA[],intn）

{

ElemTypex;

inti,j,flag;

for（i=1;i

{

flag=0;

for（j=n-1;j>=i;j__）

if（A[j].stn

{

x=A[j];

A[j]=A[j-1];

A[j-1]=x;

flag=1;

}

if（flag==0）return;

}

}

该算法的功能是什么，一般称为什么算法？

5．voidEE（LNode*HL,constElemType&item）

{

LNode*newptr=newLnode;

newptr->data=item;

LNode*p=HL;

while（p->next!

=HL）

p=p->next;

newptr->next=HL;

p->next=newptr;

}

对于结点类型为LNode的单链表，以上算法的功能为：

6．voidFF（List&L）

{

inti=0;

while（i

{

intj=i+1;

while（j

{

if（L.list[j]==L.list）

{

for（intk=j+1;k

L.list[k-1]=L.list[k];

L.size--;

}

elsej++;

}

i++;

}

}

以上算法的功能为：

7．voidGG（BTreeNode*&BST）

{

ElemTypea[6]={45，23，78，35，77，25}；

BST=NULL；

for（inti=0,i<6;i++）

Insert（BST,a[i]）;

}

调用该算法后，生成的二叉搜索数的中序序列为：

8．voidHH（）

{

ElemTypeA[]={1,3,5,7,9,2,4,6,8,10},B[10];

TwoMerge（A,B,0,4,9）;

for（inti=0;i<10;i++）

cout<

cout<

}

调用该算法后，输出结果为：

9．voidII（LNode*&HL）

{

LNode*p=HL;

HL=NULL;

while（p!

=NULL）

{

LNode*q=p;

p=p->next;

q->next=HL;

HL=q;

}

}

对于结点类型为Lnode的单链表，以上算法的功能为：

10．voidJJ（List&La）

{

InitList（La）;

inta[]={78,26,56,27,34,42};

for（i=0;i<3;i++）

InsertFront（La,a[i]）;

for（i=3;i<6;i++）

InsertRear（La,a[i]）;

TraverseList（La）;

}

该算法执行后得到的线性表La为：

11．voidKK（BTreeNode*BT）

{

if（BT!

=NULL）

{

cout<data;

if（BT->left!

=NULL||BT->right!

=NULL）

{

cout<<’（’;

KK（BT->left）;

if（BT->right!

=NULL）

cout<<’,’;

KK（BT->right）;

cout<<’）’;

}

}

}

以上算法的功能为：

12．voidLL（GLNode*GL）

{

intmax=0;

while（GL!

=NULL）

{

if（GL->tag==true）

{

intdep=LL（GL->sublist）;

if（dep>max）max=dep;

}

GL=GL->next;

}

returnmax+1;

}

以上算法的功能为：

13．voidCC（Stack&S）

{

Pop（S）;

Push（S,50）;

Push（S,45）;

Peek（S）;

}

假定调用算法时栈S中已有2个元素（23，16）的栈，其中23时栈底，调用后得到的栈内容为（从栈底开始排列）：

14．写出以下函数的功能。

boolAA（BtreeNode*BST,ElemType&item）

{

if（BST==NULL）

returnfalse;

else{

if（item==BST→data）

{

item=BST→dta;

returntrue;

}

elseif（item

returnfind（BST→left,item）;

else

retrunfind（BST→right,item）;

}

}

五、编写算法

1．编写一个算法，返回搜索树中的关键字最小的元素值。

2．编写一个非递归算法，在稀疏有序索引表中二分查找出给定值K所对应的索引项，即索引值刚好大于等于K的索引项，返回该索引项的start域的值，若查找失败则返回-1。

3．编写对二叉树进行中序遍历的非递归算法。

4．编写从类型为List的线性表L中删除其值等于给定值x的第一个元素的算法，假定该线性表不为空。

要求若删除成功返回true，否则返回false。

boolDelete（List&L,ElemTypex）

{

5．写出向以BST为树根指针的二叉搜索树上插入值为item的结点的递归算法。

voidInsert（ABTListBST,constElemType&item）

{

参考答案

一、单选题

1．C2．B3．C4．A5．A

6．A7．A8．A9．B10．A

11．C12．A13．B14．A15．C

16．C17．C18．B19．A20．B

21．D22．D

二、填空题

1．有穷性、确定性、可行性、输入、输出

2．q->right=p->right;

if（p->right）p->right->left=q;

q->left=p;

p->right=q;

3．邻接距阵、邻接表、边集数组

4．abcdefcbdaefcdbfeaabecdf

5．堆尾、堆顶、向下

6．有序序列

7．顺序结构、链接结构、索引结构、散列结构

8．2i+1、2i+2、

9．栈顶元素、栈顶指针

10．6

11．2、2、0、7

12．n（n-1）/2、n（n-1）

13．稠密、稀疏

14．二叉搜索树、理想平衡树

15．2、用户定义

16．O（n）、O（m*n）

17．O（n）、O（nlog2n）、O（n）

18．

、m-1、

、m

19．堆尾、堆顶、向下

20．O（nlog2n）、O（n2）

21．查找成功、左子树、右子树

22．p->next=HL;HL=p;

23．2i+1、2i+2、

24．表头

25．B、EFG

26．63

27．31、16

28．有序序列

29．HL→next=NULL、HL=HL→next

30．3、3、2

三、运算题

1．后缀算术表达式：

3425615/－*＋8－@

2．拓扑序列为：

1402365789

3．（64）

（52，64）

（12，64，52）

（12，48，52，64）

（12，45，52，64，48）

（12，45，26，64，48，52）

4．A：

111G：

011F：

10

U：

010Y：

00Z：

110

（或0、1相反）

5．

0

1

2

3

4

5

6

7

8

9

10

11

∧

∧

∧

∧

∧

平均查找长度ASL=（7*1+2*2+3*1）/10=1.4

6．（3，4）5，（0，1）8，（4，5）9，（4，7）10，（2，4）14，（1，3）15，（4，6）31

7.带权路径长度WPL=131。

哈夫曼树为：

8．[382440]46[56809579]

24[3840]46[56809579]

24384046[56809579]

2438404656[809579]

243840465679[8095]

2438404656798095

9．后缀算术表达式：

25615/-158/+@

10．带权路径长度WPL=158。

哈夫曼树为：

A：

000G：

100F：

001U：

11Y：

01Z：

101（或0和1相反）

11．

78

15

03

57

45

20

31

23

36

12

查找成功的平均查找长度：

ASLSUCC=14/10=1.4

四、阅读算法，回答问题

1．统计单链表中结点的值等于给定值x的结点数。

2．在具有n个元素的顺序表A中，顺序查找关键字为K的元素。

3．栈内容为（从栈底开始排列）：

23，50，45。

4．对数组A中的n个元素进行排序，称为起泡算法。

5．向单链表的末尾添加一个元素。

6．删除线性表中所有重复的元素。

7．232535457778

8．12345678910

9．将一个单链表按逆序链接。

10．（56，26，78，27，34，42）

11．把二叉树以广义表形式输出。

12．计算广义表深度。

13．栈内容为（从栈底开始排列）：

23，50，45。

14．在二叉搜索树上查找等于给定值item的元素。

五、编写算法

1．

ElemTypeFindMax（BtreeNode*BST）

{

if（BST==NULL）

{

cerr<<”不能在空树上查找最小值！

”<

exit

（1）;

}

BtreeNode*t=BST;

while（t->left!

=NULL）

t=t->left;

returnt->data;

}

2．

intBinsch（IndexListB,intm,IndexKeyTypeK）

{

intlow=0,high=m-1;

while（low<=high）

{

intmid=（low+high）/2;

if（K==B[mid].index）

returnB[mid].start;

elseif（K

high=mid-1;

else

low=mid+1;

}

if（low

elsereturn–1;