数据结构复习题

数据结构复习题

一、填空题

1.数据结构是一门研究非数值计算的程序设计问题中计算机的操作对象以及它们之间

的关系和运算等的学科。

2.数据结构被形式地定义为(D,R),其中D是数据元素的有限集合,R是D上的_去

系—有限集合。

3.数据结构包括数据的逻辑结沟、数据的存储结构和数据的运算这三个方面的

内容。

4.数据结构按逻辑结构可分为两大类，它们分别是一线性结构和非线性结构°

5.线性结构中元素之间存在一对一关系,树形结构中元素之间存在二M多关系，图形结构中

元素之间存在剑型关系。

6.在线性结构中，第一个结点没有前驱结点,其余每个结点有且只有1个前驱结点；

最后一个结点没有后续结点,其余每个结点有且只有1个后续结点。

7.在树形结构中，树根结点没有前驱结点,其余每个结点有且只有个前驱结点：

叶子结点没有后续结点,其余每个结点的后续结点数可以任意多个。

8.在图形结构中，每个结点的前驱结点数和后续结点数可以任意多个。

9.数据的存储结构可用四种基本的存储方法表示，它们分别是顺序、链式、索引和散

列。

10.数据的运算最常用的有5种，它们分别是插入、删除、修改、查找、排序。

11.一个算法的效率可分为时间效率和空间效率c

12.在顺序表中插入或删除一个元素，需要平均移动表中一半元素,具体移动的元素个数与

表长和该元素在表中的位置有关。

13.线性表中结点的集合是芭腥—的，结点间的关系是一一对一的。

14.向一个长度为n的向量的第i个元素(lWiWn+1)之前插入一个元素时，需向后移动n-i+1

个元素。

15.向一个长度为n的向量中删除第i个元素（iWiWn）时，需向前移动」个元素。

16.在顺序表中访问任意一结点的时间复杂度均为Q£D,因此，顺序表也称为随机存取

的数据结构。

17.顺序表中逻辑上相邻的元素的物理位置」江定相邻。单链表中逻辑上相邻的元素的物理位

置一不一定相邻。

18.在单链表中，除了首元结点外，任一结点的存储位置由其直接前驱结点的链域的值指

示。

19.在n个结点的单链表中要删除已知结点*p,需找到它的前驱结点的地址,其时间复杂度

为0（n）；还有一种时间复杂度为0（1）的巧妙删除方法，即把p的后继结点中数据拷贝到

p结点中，然后删除p的后继结点，删除语句应该是a=p->ncxt;D->ncxt=q->ncxt;frce（q〕：。

20.向量、栈和队列都是线性结构,可以在向最的任何位置.插入和删除元素;

对于栈只能在栈顶插入和删除元素:对于队列只能在队尾插入和队首

删除元素。

21.栈是一种特殊的线性表，允许插入和删除运算的一端称为栈顶。不允许插入和删

除运算的一端称为栈底。

22.队列是被限定为只能在表的一端进行插入运算,在表的另一端进行删除运算的线

性表。

23.不包含任何字符（K咬为D）的串称为空串:由一个或多个空格（仅由空格符）

组成的串称为空白串。

24.子串的定位运算称为串的模式匹配；被匹配的主串称为目标串,子串称为模

式。

25.假设有二维数组A6X8,每个元素用相邻的6个字节存储，存储器按字节编址。已知A的

起始存储位置（基地址）为1C00,则数组A的体积（存储量）为288B；末尾元素

A57的第一个字节地址为1282:若按行存储时，元素AM的第一个字节地址为（8+4）

X6+1000=1072；若按列存储时，元素Am的第一个字节地址为（6X7+4）X6+1000）

=1276

26.由3个结点所构成的二叉树有—J种形态。

27.一棵深度为6的满二叉树有叫+地=0+吨=攻-1=31个分支结点和=32个叶子。

解：满二叉树没有度为1的结点，所以分支结点数就是二度结点数。

28.一棵具有257个结点的完全二叉树，它的深度为9。

解：用Llog2(n)J+l=L8.xx」+1=9

29.设一棵完全二叉树有700个结点，则共有350个叶子结点。

解：最快方法：最后一个叶子编号为700,其父节点编号为［n⑵=350,且其父节点为最

后一个非叶子结点。

30.设一棵完全二叉树具有1(X)0个结点，则此完全二叉树有心个叶子结点，有499

个度为2的结点，有1个结点只有非空左子树,有Q个结点只有非空右子树。

解：方法同上：最后一个非叶子编号为［n⑵=500,所以叶子结点数n()=500,n2=n()“=499。

另外，最后一个结点为2i属于左叶子，右叶子是空的，所以有1个非空左子树。完全二叉树

的特点决定不可能有左空右不空的情况，所以非空右子树数=().也可根据编号为50()的左右

儿子结点应该为100()和1001,而显然1001不存在。

31.在数据的存放无规律而言的线性表中进行检索的最佳方法是.顺序查找(线性查找)。

32.线性有序表(apa2,a3,a256)是从小到大排列的，对一个给定的值k,用二分法检索

表中与k相等的元素，在查找不成功的情况下，最多需要检索」次。设有100个结点，

用二分法查找时，最大比较次数是」o

33.假设在有序线性表a［20］上进行折半查找，则比较一次查找成功的结点数为1；比较两次

查找成功的结点数为，;比较四次查找成功的结点数为：平均查找长度为

3.7o

解：显然，平均查找长度=0(logzn)<5次(2)。但具体是多少次，则不应当按照公式

ASL="l1°g2(〃+l)来计算(即(21Xlog221)/20=4.6次并不正确！)。因为这是在假设门=

n

2m-1的情况下推导出来的公式。应当用穷举法罗列：

全部元素的查找次数为=(1+2X2+4X3+8X4+5X5)=74：ASL=74/20=3.7!!!

34.折半查找有序表(4,6,12,20,28,38,50,70,88,100),若查找表中元素20,它

将依次与表中元素28,6,12,20比较大小。

35.在各种查找方法中，平均查找长度与结点个数n无关的查找方法是一散列查找。

36.散列法存储的基本思想是由关键字的值决定数据的存储地址。

37.数据的逻辑结构可分为集合结构、线性结构、树形结构和图形结构等4种。

38.从长度为n的采用顺序存储结构的线性表中删除第i个元素(IWiWn),需要移动

n-i个元素,在第i个元素前面插入一个元素，需要移动n-i+l个元素。

39.顺序存储的栈，做入栈运算时，应先判断栈是否为满，做出栈运算时，应先判断栈是

否为空。

40.己知一个栈的进栈先后次序为abed,判断下面两个序列能否是其出栈序列：

(Ddbea不能(2)cbda显(注：填“能”或者“不能”)

41.长度为0的字符串称为一纯。设正文串长度为n,模式串长度为m,则简单模式匹配算

法的时间复杂度为O(n*ni)。

42.设广义表1尸(()，()),则GetHead(L)是()；GetT设1(L)是(())；L的长度是2；

L的深度是一2。

43.由带权为3,9,6,2,5的5个叶子结点构成一棵哈夫曼树，则带权路径长度为反。

44.完全二叉树的第7层有8个结点，则此完全二叉树的叶子结点数为工。768个结点的

完全二叉树有避纹个叶子结点？19个结点的哈夫曼树有」L个叶子结点？

45.n个顶点的无向连通图，用邻接矩阵存储时，该矩阵至少有2r1-2个非零元素。

46.希尔排序的增量序列有多种选择，但不管哪种选择，最后一个增量必须为]。

47.假设以S和X分别表示入栈和出栈操作，则对输入序列a,b,c,d,e进行一系列栈操

作SSXSXSSXXX之后，得到的输出序列为bceda。

48.组成串的数据元素只能是字符。

49.n个结点的完全二叉树，编号鼓大的非叶结点是W21号结点，编号最小的叶结点是

[n/2]+l号结点。

50.已知二叉树有50个叶子结点，则该二叉树的总结点数至少是一99。

51.在一棵■"叉树中,度为0的结点个数为NO,则度为2的节点个数为巫L。

52.叶子权值（5,6,17,8,19）所构造的哈夫曼树带权路径长度为一

53.深度为k的完全二叉树至少有上个结点，至多有2卜-1个结点。

54.在n个元素的线性表中顺序查找，若查找成功，则关键字的比较次数最多为」1_次；使用

监视哨时，若查找失败，则关键字的比较次数为」1±1次。

55.折半搜索只适合用于—有序的顺序存储表_°

56.结点关键字转换为该结点存储单元地址的函数H称为一哈希函数—或叫.散列函数一。

57.在一棵k叉树中，度为i（0〈=i〈=k）的结点的个数为Ni,则有NO=£M*（f-l）+lo

解：所有结点数记为n,结合树中分支数比结点数少一个，以及每一个分支被计入顶点的度1

次，则有

n=NO+N1+…+Nk

n-l=1*N1+2*N2+…k*Nk〃所有结点度数的和

两式相减即得。

58.设一棵完全二叉树叶子结点数为k,最后一层结点数为偶数时，则该二叉树的高度

为;最后一层结点数为奇数时，则该二叉树的高度为o

解：根据完全二叉树性质，结点数为n的完全二叉树，其深度为「log2（n+l）］［或者

Llog2（n）J+l］,所以只要推算出二叉树结点即可。

对完全二叉树从根（编号1）开始，逐层递增编号，最后一个结点编号为n,则n的父结

点为最后一个非叶子结点，其编号为［n/2］,也就是说，完全二叉树中非叶子结点个数为［n/2］,

比如n=4或5的完全二又树，其飞叶子结点数均为2；从而可以看出叶子结点数比非叶子结

点数，要么相等，要么多1个，因为完全二叉树除去除去最后一层，上面的为满二叉树（其

结点数为奇数），所以当最后一层结点数为偶数时，说明完全二叉树总结点数为奇数，因为叶

子结点数为k,则非叶子结点数为k-l,总结点数为2k-1,树深度为「bg2（2k）［=「bg^kl+l。

当最后一层结点数为奇数时，说明总结点数为偶数，此时叶子结点与非叶子结点数相等,

所以总结点数为2k,则树深度为「logQk+l）］。

59.有5种不同形态的一叉树可以按照中序遍历得到相同的abc序列。

解：根据二叉树5种基本形态，中根遍历为abc,

当根为a时，be在其右子树，有如图2种情况，

当根为b时，a在其左子树，c在其右子树，有如图1种情况，

当根为c时，ab在其左子树，有如图2种情况，

ab

\/\

ca।

/

cb

60.已知二叉树先序为ABDEGCF,中序为DBGEACF,则后序一定是DGEBFCA。

解：先画出二叉树，然后写出后根序列。

61.深度为k的完全二叉树至少有2卜1个结点,至多有2卜个结点。

解：结点数最少时，第k层仅1个结点，加上上面kT层满二叉树结点数。

结点数最多时，即为k层的满二叉树。

62.具有10个叶子的哈夫曼树，其最大高度为，最小高度为。

解：哈夫曼树只有度为0和2的结点，且有N0=N2+1,所以哈夫曼树结点数共有19个,

最小高度时为完全二叉树，即为［log2（19）］+l=5;

最大高度时;从根到倒数第二层均只有一个非叶子结点，所以高度为10,形状如下

63.设F是一个森林，B是由F转换得到的二叉树，F中有n个非终端结点，则B中右指针

域为空的结点有n+1个。

解：举例子推理，即可发现规律。

先对一棵一般树转换，可发现空的右指针数总比非叶子结点数多1个，那么2棵一

般树转换成2棵对应二叉树时，空的右指针数比非叶子结点数多2个，但是在转换为森

林时，后一棵二叉树接到前一棵二叉树的根右边，从而又会减少一个空的右指针，用以

最终空的右指针数总比非叶子结点数多1个。

64.在线性表(5,12,19,21,37,55,65,75,80,88,92)中,用折半查找法查找关键字为85的记

录，关键字的比较次数为次，所比较的元素依次为o

答案：3568088

65.假定对长度n=100的线性表进行分块查找，并假定每块的长度均为10,每个记录的查

找概率相等。若索引表和块内都采用顺序查找，则平均查找长度为;若

索引表采用折半查找，块内采用顺序查找，则平均查找长度约为。

答案：119

66.已知二叉排序树的左右子树均不为空，贝k左壬虬上所有结点的值均小于它的根结点值，

上所有结点的值均大于它的根结点的值。

67.二叉排序树的查找效率与树的形态有关。当二叉排序树退化成成单支树时，查找算法退

化为查找，其平均查找长度上升为。当二叉排序树是一棵平衡二叉

树时，其平均查找长度为。

答案：顺序(n+l)/2O(log2n)

68.希尔排序的增量序列有多种选择，但不管哪种选择，最后一个增量必须为。

答案：1

69.排序算法所花费的时间，通常用在数据的比较和生k两人操作上。

二、单项选择题

1.程序段for(i=n-l；i>=0；i—)

for(j=l：j<=n；j++)

ifAU]>A[j+l]

A|j]与A[j+1]对换；

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

A.O(n)R.O(n2)C.O(n3)D.O(nlog2n)

2.线性表中在链式存储中各结点之间的地址()。

A.必须连续B.部分地址必须连续C.不能连续D.连续与否无所谓

3.将两个各有n个元素的有序线性表归并成一个有序线性表，最少的比较次数是(：。

A.nB.2n-lC.2nD.n-1

4.在有n个结点的单链表中查找值为x的结点，在查找成功情况下，需平均比较()个结点。

A.nB.n/2C.(n-l)/2D.(n+l)/2

5.若希望从链表中快速确定一个结点的前驱，则链表最好采用()方式。

A.单链表B.循环单链表C.双向链表D.任意

6.带头结点的单链表head为空的判定条件是()。

A.head==NULLB.head->next==NULLC.head->ncxt==headD.hcad!=NULL

7.在循环双链表的p所指结点之后插入s所指结点的操作是()。

A.p->next=s;s->prior=p;p->next->prior=s;s->ncxt=p->next;

B.p->next=s：p->next->prior=s：s->prior=p：s->next=p->next：

C.s->prior=p;s->next=p->next;p->next=s;p->next->prior=s;

D.s->prior=p;s->next=p->next;p->next->prior=s;p->next=s;

8.设有一顺序栈S,元素sl,s2,s3,s4,s5,s6依次进栈，如果6个元素出栈的顺序是

s2,s4,s3,s6,s5,si,则栈的容量至少应该是。

A.3B.4C.5D.6

9.在一个栈顶指针为top的链栈中，将一个s指针所指的结点入栈，执行o

A.top->next=s：B.s->next=top->next;top->next=s;

C.s->next=top;top=s；D.s->next=top;top=top->next;

10.链栈和顺序栈相比，有一个比较明显的优点，即O

A.插入操作更加方便B.通常不会出现栈满的情况

C.不会出现栈空的情况D.删除操作更加方便

11.循环队列A[m]存放其元素，用front和rear分别表示队头及队尾，则循环队列满的条

件是_________。

A.(Q->rear+1)%m==Q->frontB.Q->rear==Q->front+1

C.Q->rear+l-Q->frontD.Q->rear==Q->front

12.若一个栈的输入序列为1,2,3,…,n,输出序列的第一个元素是n,则第i个输出元素是

()o

A.n-i-1B.n-iC.n-i+1D.不确定

13.设abcdef以所给的次序进栈，若在进栈操作时.，允许出栈操作，则下面得不到的序列为

()o

A.fedcbaB.bcafedC.dcefbaD.Ccibdef

14.中缀表达式A-(B+C/D)*E的后缀形式是()<>

A.AB-C+D/E*B.ABC+D/E*C.ABCD/E*+-D.ABCD/+E*-

15.领设以数组存放循环队列的元素,其头尾指针分别为front和rear,则当前队列中的

元素个数为(L

A.(rear-front+m)%mB.rear-front+1

C.(front-rear+m)%mD.(rear-front)%m

16.循环队列存储在数组A[0..m]中，则入队时队尾的操作为()。

A.rear=rear+1B.rear=(rear+1)%(m-1)

C.rear=(rear+l)%mD.rear=(rear+1)%(m+1)

17.下面关于串的叙述中，哪一个是不正确的？________

A.串是字符的有限序列B.空串是由空格构成的串

C.模式匹配是串的一种重要运算D.串既可以采用顺序存储，也可以采用链式存储

18.已知串S=naaab"，其next数组值为。

A.0,1,2,3B.1,1,2,3C.1,2,3,1D.1,2,1,1

19.一维数组A采用顺序存储结构，每个元素占用6个字节，第6个元素的起始地址为100,

则该数组的首地址是。

A.64B.28C.70D.90

20.稀疏矩阵采用压缩存储的目的主要是。

A.表达变得简单B.对矩阵元素的存取变得简单

C.去掉矩阵中的多余元素D.减少不必要的存储空间的开销

21.若对n阶对称矩阵A以行序为主序方式将其下三角形的元素(包括主对角线上所有元索)

依次存放于一维数组B[L.(n(n+l))/2]中，则在B中确定此仪)的位置k的关系为______。

A.i*(i+l)/2+jB.j*(j+l)/2+iC.i*(i+l)/2+MD.j*(j+l)/2+i+l

22.已知广义表LS=((a,b,c),(d,e,f)),运用GetHead和GetTail运算取出LS中的元素e

的运算是o

A.GetHead(GetTai1(LS))B.GetHead(GetTai1(GetTail(GetHead(LS))))

C.GetTai1(GetHead(LS))D.GetHead(GetTai1(GetHead(GetTai1(LS))))

23.设广义表L=((a,b,c)),则L的长度和深度分别为。

A.1和1B.1和3C.1和2D.2和3

24.一个100*90的稀疏矩阵，非0元素有10个整型数，设每个整型数占2字节，则用三元

组表示该矩阵时，所需的字节数是。

A.60B.66C.18000D.33

25.设二维数组A[L.m,1..n](即m行n歹lj)按行存储在数组B[L.m*n]中，则二维数组

元素A[i][j]在一•维数组B中的下标为()。

A.(i-l)*n+JB.C.D.

26.一棵三义树中，已知度为3的结点数等于度为2的结点数，且树中叶结点的数目为13,

则度为2的结点数目为o

A.4B.2C.3D.5

27.设n、m为一棵二叉树上的两个结点，在中序遍历时，n在m之前的条件是。

A.n在m右方B.n是m祖先C.n在m左方D.n是田子孙

28.对一个满二叉树，m个树枝，n个结点，深度为h,则。

A.n=h+mB.h+m=2nC.m=h-lD.n=2h-l

29.以二叉链表作为二叉树的存诸结构,在有n个结点的二叉链表中(n〉0),链表中空链域的

个数为o

A.2n-lB.n-lC.n+1D.2n+l

30.在一棵二叉树结点的先序序列、中序序列、后序序列中，所有叶子结点的先后顺序

A,都不相同B.先序和中序相同，而与后序不同

C.完全相同D.中序和后序相同，而与先序不同

31.如果将给定的一组数据作为叶子数值，所构造出的二叉树的带权路径长度最小，则该树

称为。

A.哈夫曼树B.平衡二叉树C.二叉树D.完全二叉树

32.树的先根序列和其对应的二叉树的是一样的，树的后根序列和其对应的二叉梃的

是一样的。

A.先序序列B.中序序列C.后序序列D.按层次遍历序列

33.若一个具有N个顶点，K条边的无向图是一个森林(N〉K),则该森林中必有棵树。

A.KB.NC.N-KD.1

34.如果T?是由树T转换而来的二叉树，那么对T中结点的后序遍历就是对Tz中结点的

（）遍历。

A.先序B.中序C.后序D.层次序

35.设树T的度为4,其中度为1,2,3和4的结点个数分别为4,2,1,1则T中的叶子

数为（）。

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

36.由4个结点可以构造出多少种不同的二叉树？（）

A.10B.12C.14D.16

37.二叉树在线索后，仍不能有效求解的问题是（）。

A.先序线索二叉树中求先序后继B.中序线索二叉梃中求中序后继

C.中序线索二叉树中求中序前驱D.后序线索二叉枕中求后序后继

38.一棵二叉树具有10个度为2的结点，5个度为1的结点，则度为0的结点个数是（）。

A.9B.11C.15D.不确定

39.设高度为h的二叉树上只有度为0和度为2的结点，则比类二叉树中所包含的结点数至

少为（）个。

A.2hB.2h-lC.2h+lD.h+1

40.设给定权值的叶子总数有n个，其哈夫曼树的结点总数为（）。

A.不确定B.2nC.2n+lD.2n-l

41.某二叉树的先序遍历序列和后序遍历序列正好相反，则此二叉树一定是（）。

A.空或只有一个结点B.完全二叉树C.单支树D.高度等于结点数

42.在二叉树结点的先序序列，中序序列和后序序列中，所有叶子结点的先后顺序（）。

A.都不相同B.完全相同

C.先序和中序相同，而与后序不同D.中序和后序相同，而与先序不同

43.根据使用频率，为5个字符设计的哈夫曼编码不可能是（）。

A.111,110,10,01,00B.000,001,010,011,1

C.100,11,10,1,0D.001,000,01,11,10

44.具有7个顶点的有向图至少应有条边才能确保一个强连通图。

A.6B.7C.8D.9

45.设无向图的顶点个数为n,则该图最多有条边。

A.n-1B.n（n-l）/2C.n（n+l）/2D.0E.n2

46.下列哪一种图的邻接矩阵是时称矩阵？

A.有向图B.无向图C.A0V网D.A0E网

47.在有向图的邻接表存储结构中，顶点v在链表结点中出现的次数是。

A.顶点v的度B.顶点v的出度C.顶点v的入度D.依附于顶点v的边数

48.采用邻接表存储图的深度优先遍历算法类似于树的。

A.中根遍历B.先根遍历C.后根遍历D.层次遍历

49.关键路径是指AOE（ActivityOnEdge）网中。

A.最长的回路B.最短的回路C.从源点到汇点（结束顶点）的最长路径

D.从源点到汇点（结束顶点）的最短路径

50.强连通分量是的极大连通子图。

A.无向图B.有向图C.树D.图

51.一个n个顶点的连通无向图，其边的个数至少为（）。

A.n-1B.nC.n+1D.nlog2n

52.图的广度优先搜索类似于树的（）遍历。

A.先序B.中序C.后序D.层次

53.下面（）方法可以判断出一个有向图是否有环（回路）。

A.深度优先遍历B.拓扑排序C.求最短路径D.求关键路径

54.在有向图G的拓扑序列中，若顶点Vi在顶点Vj之前，则下列情形不可能出现的是

（）o

A.G中有弧<Vi,Vj>B.G中有一条从Vi到Yj的路径

C.G中没有弧<Vi,Vj>D.G中有一条从Vj到Vi的路径

55.若查找每个元素的概率相等,则在长度为n的顺序表上查找到表中任一元素的平均查找

长度为_____________

A.nB.n+1C.(n-l)/2D.(n+l)/2

56.折半查找的时间复杂度。

A.O（n*n）B.O（n）C.O（nlog2n）D.O（log2n）

57.采用分块查找时，数据的组织方式为o

A.把数据分成若干块，每块内数据有序

B.把数据分成若干块，块内数据不必有序，但块间必须有序，每块内最大（或最小）的数

据组成索引表

C.把数据分成若干块，每块内数据有序，每块内最大（或最小）的数据组成索引表

D.把数据分成若干块，每块（除最后一块外）中的数据个数相等

58.二叉排序树的查找效率与二叉排序树的（1）有关,当（2）时,查找效率最低,

其查找长度为ru

（1）A.高度B.结点的个数C.形状D.结点的位置

（2）A.结点太多B.完全二叉树C.呈单叉树D.结点的结构太复杂

59.在一棵AVL树（平衡二叉树）中，每个结点的平衡因子的取值范围是o

A.T〜1B.-2〜2C.1-2D.0〜1

60.在平衡二叉树中插入一个结点后造成了不平衡，设最低的不平衡结点为A,并已知A的左

孩子的平衡因子为0,右孩子的平衡因子为1,则应作（）型调整以使其平衡。

A.LLB.LRC.RLD.RR

61.下面关于折半查找的叙述正确的是（）。

A.表必须有序，表可以顺严方式存储，也用以链表方式存储

B.表必须有序且表中数据必须是整型，实型或字符型

C.表必须有序，而且只能从小到大排列

D.表必须有序，旦表只能以顺序方式存储

62.从空二叉排序树开始，用下列序列中的（），构造的二叉排序树的高度最小。

A.45,25,55,15,35,95,30B.35,25,15,30,55,45,95

C15.25,30,35.45,55,95D.30.25,15,35,45,95.55

63.下面关于哈希查找的说法正确的是()。

A.哈希函数构造的越复杂越好，因为这样随机性好，冲突小

B.除留余数法是所有哈希函数中最好的

C.不存在特别好与坏的哈希函数，要视情况而定

D.若需在哈希表中删去一个元素，不管用何种方法解决冲突都只要简单的将该元素删去

即可

64.将10个元素哈希到100000个单元的哈希表中，则()产生冲突。

A.一定会B.一定不会C.仍可能会

65.下列排序算法中，算法是不稳定的。

A.起泡排序B.直接插入排序C.归并排序D.快速排序

66.在下列排序算法中，占用附辅助空间最多的是。

A.归并排序B.快速排序C.堆排序D.希尔排序

67.高度为h(h>0)的满二叉树有个结点。

A.2h-lB.2h+1C.2h-,+lD.2h+,-l

68.设无向连通图的顶点个数为n,则该图最少有()条边。

A.n-1B.n(n-l)/2C.n(n+l)/2D.0

69.下列说法正确的是________

A.链表在物理存储空间上一定是离散的。

B.顺序表在物理存储空间上一定是连续的。

C.堆栈的物理存储空间结构一定是离散的。

D.队列的物理存储空间结构一定是连续的。

70.下列排序算法中，其中()是稳定的。

A.堆排序，冒泡排序B.快速排序，堆排序

C.简单选择排序,归并排序D.归并排序.冒泡排序

71.对n个元素进行快速排序，如果初始数据已经有序，则时间复杂度为()。

2

A.0(1)B.0(n)C.0(n)D.0(log2n)

72.以下时间复杂度不是0(nlog2n)的排序方法是()。

A.堆排序B.直接插入排序C.二路归并排序D.快速排序

73.若需在OSlogzn)的时间内完成对数组的排序，且要求排序是稳定的，则可选择的排序方

法是()。

A.快速排序B.堆排序C.直接插入排序D.归并排序

74.一组记录的关键字为字6,79,56,38,40,84},则利用快速排序方法，以第一个记录为轴,

得到的一次划分结果为()。

A.{38,40,46,56,79,84}B.{40,38,46,79,56,84}

C.{40,38,46,56,79,84)D.{40,38,46,84,56,79}

75.一组记录的关键字为{45,80,55,40,42,85},则利用堆排序方法建立的初始大根堆为

()o

A.{80,45,50,40,42,85}B.{85,80,55,40,42,45}

C.{85,80,55,45,42,40}D.(85,55,80,42,45,40}

76.在待排序的元素序列基本有序的前提下，效率最高的排序方法是()。

A.直接插入排序B.快速排序C.简单选择排序D.归并排序

77.就排序算法所用的辅助空间而言，堆排序、快速排序、归并排序的关系是()。

A.堆排序＜快速排序＜归并排序B.堆排序〈归并排序〈快速排序

C.堆排序》归并排序〉快速排序D.堆排序》快速排序》归并排序

78.一个序列有10000个元素，若只想得到其中前10个最小元素，最好采用()方法。

A.二路归并排序B.直接选择排序C.Shell排序D.堆排序

三、解答题

1.进栈的先后顺序为A,B,C.D,E,F,试判断下列两种出栈顺序是否有可能。

(1)B,A,D,E,C,F(2)B,C,F,D.A,E

2.进栈顺序为A,B,C,D,且进栈过程中可以出栈，写出所有可能的出栈顺序。

3.设稀疏矩阵

-0-31000

00100-I

000000

A二

002000

000040

000000

(1)画出其三元组表形成的压缩存储表。

(2)画出其十字链表形成的压缩存储表。

4.用的邻接表如图所示：

vertexfirstedge

图邻接表

(1)写出从顶点V0出发进行深度优先搜索的遍历序列。

(2)写出从顶点V0出发进行广度优先搜索的遍历序列。

答案：VO-*V1-*V2-*V3,VO-*V1-＞V3-*V2

5.写出下图所示的四个拓扑序列。

答案：VMV5V2V6V3%,V5VlVoV6ViV3V.1,VMV5V2V3V6V4。

6.时于下图所示的连通图,请用Prim算法构造其最小生成树。

解：

(1)Prim算法的基本思想：从某个顶点集(初始时只有一个顶点)开始，通过加入与其中顶点

相关联的最小代价的边，来犷大顶点集合，直至将所有的顶点包含其中。其最小生成树的构

造过程如图所示(假设从顶点VI开始)。

(e)

利用Prim算法生成最小生成树过程

7.假定一个线性序列为(30,25,40,18,27,36,50,10,32,45),按此序列中的元素

顺序生成一棵二叉排序树，并求出在该二叉排序树上查找成功时的平均查找长度。

解：二叉树的建立过程是不断执行元素插入操作的过程，直到序列中的元素插完为止。该二

叉排序树建树过程如图8.3所示：

图&3二叉排序树的建树过程示意图

查找成功时的平均查找长度ASLu『(1+2*2+3*4+4*3)/10=29/10=2.9

8.已知二叉树左右子树都含有m个结点，当m=3时，试构造满足如下要求的所有二叉树。

(1)左右子树的先序与中序序列相同。

(2)左子树的中序与后序序列相同，右子树的先序与中序序列相同。

解：该题目山上题引申得到，主要考查二叉树的结构和遍历的性质，如图6.7所示。

9.没电文由6个字符A,B,C,D,E,F组成，它们在电文中出现的次数分别为：10,4,8,3,

2,7,试画出用于编码的哈夫蛀树，并列出每个字符的编码。

分析与解答：该题目主要考查哈夫亚树及应用。对应的哈夫蛀树如图6.18所示：

图6.18

对应的哈夫曼编码为A(10)：11B(4)：100C(8)：01

D(3)：1011E(2)：1010F(7)：00

10.设有一个关键字的输入序列{55,31,11,37,46,73,63,02,07},

(D从空树开始构造平衡二叉树，画出插入46之前的平衡二叉树。

(2)46插入之后哪一个结点平衡因子失效？属于4种调整方式中哪一种？

(3)画出插入46并调整之后的平衡二叉树。

解：⑴

11.已知一棵二叉树的中序序列和后序序列分别为BDCEAFHG和DECBHGFA,画出这棵二叉树。

并写出其先序遍历序列。

12.给定一组数列(15,8,10,21,6,19,3)分别代表字符48,(：,。,&玛6出现的频度,试画出哈

夫曼树，给出各字符的编码值。

13.设有关键字序列:35,27,55,70,67,20,26,28,写出用2-路归并排序法对该序列进行排

序每一趟后的结果。

分析与解答：考查归并排序的排序方法。首先，把初始序列看成8个长度为1有序子序列，

然后对其两两归并，得到4个长度为2的有序子序列，称为第一趟归并；再把4个长度为2

的有序子序列归并成2个长度为4的有序子序列，称为第二趟归并；再把这2个长度为4的

有序子序列归并成1个长度为8的有序序列，称为第三趟归并。

初始序列：[35][27][55][70][67][20][26][28]

第一趟归并：[2735][5570][2067][2628]

第一趟归并：[27355570][20262867]

第三趟归并：[2026272835556770]

14.给定关键字序列(26,25,20,33,21,24,45,204,42,38,29,31),要用哈希法进行存储,规

定负载因子a=0.6。

(1)请给出除余法的哈希函数。

(2)用开放地址线性探测法解决冲突，请画出插入所有的关雉字后得到的哈希表，并指出发

生冲突的次数。

15.设哈希函数为H(K)=KMOD11,解决冲突的方法为链地址法，试将下列关键字集合

{35,67,42,21,29,86,95,47,50,36,91}依次插入到哈希表中(画出哈希表的示意图)。并计

算平均查找长度ASLo

16.依次输入表(30,15,28,20,24,10,12,68,35,50,46,55)中的元素，生