数据结构 复习题

数据结构复习题

一、填空题

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

2. 数据结构被形式地定义为（D, R），其中D是 数据元素 的有限集合，R是D上的 关系 有限集合。

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

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

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

6． 在线性结构中，第一个结点 没有 前驱结点，其余每个结点有且只有 1个前驱结点；最后一个结点 没有 后续结点，其余每个结点有且只有1个后续结点。

7. 在树形结构中，树根结点没有 前驱 结点，其余每个结点有且只有 1 个前驱结点；叶子结点没有 后续 结点，其余每个结点的后续结点数可以任意多个 。

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

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

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

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

12. 在顺序表中插入或删除一个元素，需要平均移动 表中一半元素，具体移动的元素个数与 表长和该元素在表中的位置 有关。

13. 线性表中结点的集合是 有限 的，结点间的关系是 一对一 的。

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

15. 向一个长度为n的向量中删除第i个元素(1≤i≤n)时，需向前移动 n-i 个元素。

16. 在顺序表中访问任意一结点的时间复杂度均为 O(1) ，因此，顺序表也称为 随机存取 的数据结构。

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

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

19． 在n个结点的单链表中要删除已知结点*p，需找到它的前驱结点的地址，其时间复杂度为O（n）；还有一种时间复杂度为O(1)的巧妙删除方法，即把p的后继结点中数据拷贝到p结点中，然后删除p的后继结点，删除语句应该是q=p->next; p->next=q->next;free(q);。

20. 向量、栈和队列都是 线性 结构，可以在向量的 任何 位置插入和删除元素；对于栈只能在 栈顶 插入和删除元素；对于队列只能在 队尾 插入和 队首 删除元素。

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

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

23. 不包含任何字符（长度为0）的串 称为空串； 由一个或多个空格（仅由空格符）组成的串 称为空白串。

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

25. 假设有二维数组A6×8，每个元素用相邻的6个字节存储，存储器按字节编址。已知A的起始存储位置（基地址）为1000，则数组A的体积（存储量）为 288 B ；末尾元素A57的第一个字节地址为 1282 ；若按行存储时，元素A14的第一个字节地址为 (8+4)×6+1000=1072 ；若按列存储时，元素A47的第一个字节地址为 (6×7＋4)×6＋1000）＝1276 。

26． 由３个结点所构成的二叉树有 5 种形态。

27. 一棵深度为6的满二叉树有 n1+n2=0+ n2= n0-1=31 个分支结点和 26-1 =32 个叶子。 解：满二叉树没有度为1的结点，所以分支结点数就是二度结点数。

28． 一棵具有２５７个结点的完全二叉树，它的深度为 9 。 解：用? log2(n) ?+1= ? 8.xx ?+1=9

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

解：最快方法：最后一个叶子编号为700，其父节点编号为[n/2]＝350，且其父节点为最后一个非叶子结点。

30． 设一棵完全二叉树具有1000个结点，则此完全二叉树有 500 个叶子结点，有 499 个度为2的结点，有 1 个结点只有非空左子树，有 0 个结点只有非空右子树。 解：方法同上：最后一个非叶子编号为[n/2]＝500，所以叶子结点数n0=500, n2=n0-1=499。 另外，最后一个结点为2i属于左叶子，右叶子是空的，所以有1个非空左子树。完全二叉树的特点决定不可能有左空右不空的情况，所以非空右子树数＝0. 也可根据编号为500的左右儿子结点应该为1000和1001，而显然1001不存在。

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

32. 线性有序表（a1，a2，a3，?，a256)是从小到大排列的，对一个给定的值k，用二分法检索表中与k相等的元素，在查找不成功的情况下，最多需要检索 8 次。设有100个结点，用二分法查找时，最大比较次数是 7 。

33. 假设在有序线性表a[20]上进行折半查找，则比较一次查找成功的结点数为1；比较两次查找成功的结点数为 2 ；比较四次查找成功的结点数为 8 ；平均查找长度为 3.7 。

解：显然，平均查找长度＝O（log2n）<5次（2）。但具体是多少次，则不应当按照公式

ASL?n?1）。因为这是在假设n＝log2(n?1)来计算（即（21×log221）/20＝4.6次并不正确！

nm

5

2-1的情况下推导出来的公式。应当用穷举法罗列： 全部元素的查找次数为＝（1＋2×2＋4×3＋8×4＋5×5）＝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个元素(1≤i≤n),需要移动 n-i 个元素, 在第i个元素前面插入一个元素，需要移动 n-i+1 个元素。

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

40．已知一个栈的进栈先后次序为abcd，判断下面两个序列能否是其出栈序列：

(1)dbca 不能 (2)cbda 能 (注：填“能”或者“不能”)

41．长度为0的字符串称为_空串_。设正文串长度为n，模式串长度为m，则简单模式匹配算法的时间复杂度为__O(n*m)_。

42．设广义表L=(()，()) ，则GetHead(L)是 () ；GetTail(L)是 (()) ；L的长度是 2 ；L的深度是 2 。

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

44．完全二叉树的第7层有8个结点，则此完全二叉树的叶子结点数为_36_。768个结点的完全二叉树有_384_个叶子结点？19个结点的哈夫曼树有_10_个叶子结点？

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

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

47．假设以S和X分别表示入栈和出栈操作，则对输入序列a，b，c，d，e进行一系列栈操作SSXSXSSXXX之后，得到的输出序列为_bceda_。

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

49．n个结点的完全二叉树，编号最大的非叶结点是_[n/2]_号结点，编号最小的叶结点是_[n/2]+1_号结点。

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

51. 在一棵二叉树中，度为0的结点个数为N0,则度为2的节点个数为 N0-1 。

52. 叶子权值(5，6，17，8，19)所构造的哈夫曼树带权路径长度为 121 。

k-1k

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

54.在n个元素的线性表中顺序查找，若查找成功，则关键字的比较次数最多为 n_次；使用监视哨时，若查找失败，则关键字的比较次数为 n+1 次。

55.折半搜索只适合用于__有序的顺序存储表__。

56.结点关键字转换为该结点存储单元地址的函数H称为_哈希函数_或叫_散列函数_。 57.在一棵k叉树中，度为i(0<=i<=k)的结点的个数为Ni,则有N0 =

?Ni*(i?1)?1。

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

n =N0+N1+?+Nk

n-1= 1*N1+2*N2+?k*Nk //所有结点度数的和 两式相减即得。

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

为 ；最后一层结点数为奇数时，则该二叉树的高度为 。 解：根据完全二叉树性质，结点数为n的完全二叉树，其深度为?log2(n?1)?【或者，所以只要推算出二叉树结点即可。 ?log2(n)?+1】

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

点为最后一个非叶子结点，其编号为[n/2],也就是说，完全二叉树中非叶子结点个数为[n/2],比如n=4或5的完全二叉树，其飞叶子结点数均为2；从而可以看出叶子结点数比非叶子结点数，要么相等，要么多1个，因为完全二叉树除去除去最后一层，上面的为满二叉树（其结点数为奇数），所以当最后一层结点数为偶数时，说明完全二叉树总结点数为奇数，因为叶子结点数为k，则非叶子结点数为k-1,总结点数为2k-1，树深度为?log2(2k)?=?log2k??1。

当最后一层结点数为奇数时，说明总结点数为偶数，此时叶子结点与非叶子结点数相等，所以总结点数为2k，则树深度为?log2(2k?1)?。

59. 有 5 种不同形态的二叉树可以按照中序遍历得到相同的abc序列。 解：根据二叉树5种基本形态，中根遍历为abc，

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

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

60. 已知二叉树先序为ABDEGCF，中序为DBGEACF，则后序一定是 DGEBFCA 。 解：先画出二叉树，然后写出后根序列。

k-1k

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

解：结点数最少时，第k层仅1个结点，加上上面k-1层满二叉树结点数。 结点数最多时，即为k层的满二叉树。

62. 具有10个叶子的哈夫曼树，其最大高度为 ,最小高度为 。 解：哈夫曼树只有度为0和2的结点，且有N0=N2+1，所以哈夫曼树结点数共有19个， 最小高度时为完全二叉树，即为[log2(19)]+1=5;

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

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

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

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

先对一棵一般树转换，可发现空的右指针数总比非叶子结点数多1个，那么2棵一般树转换成2棵对应二叉树时，空的右指针数比非叶子结点数多2个，但是在转换为森林时，后一棵二叉树接到前一棵二叉树的根右边，从而又会减少一个空的右指针，所以

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

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

录，关键字的比较次数为 次，所比较的元素依次为 。 答案：3 56 80 88

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

找概率相等。若索引表和块内都采用顺序查找，则平均查找长度为 ；若索引表采用折半查找，块内采用顺序查找，则平均查找长度约为 。 答案：11 9

66．已知二叉排序树的左右子树均不为空，则_左子树_上所有结点的值均小于它的根结点值，___右子树_上所有结点的值均大于它的根结点的值。

67．二叉排序树的查找效率与树的形态有关。当二叉排序树退化成成单支树时，查找算法退化为__________查找，其平均查找长度上升为_________。当二叉排序树是一棵平衡二叉树时，其平均查找长度为_________ 。 答案：顺序 (n+1)/2 O(log2n)

68．希尔排序的增量序列有多种选择，但不管哪种选择，最后一个增量必须为_________。 答案：1

69. 排序算法所花费的时间，通常用在数据的比较和_移动_两大操作上。

二、单项选择题

1．程序段 for(i=n-1；i>=0；i--)

for(j=1；j<=n；j++) if A[j]>A[j+1]

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

其中n为正整数，则最后一行的语句频度在最坏情况下是（ ）。 A. O（n） B. O(n2) C. O(n3) D. O(nlog2n) 2．线性表中在链式存储中各结点之间的地址（ ）。

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

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

A．n B．2n-1 C．2n D．n-1 4．在有n个结点的单链表中查找值为x的结点，在查找成功情况下，需平均比较( )个结点。

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

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

A. 单链表 B. 循环单链表 C. 双向链表 D. 任意 6．带头结点的单链表head为空的判定条件是( )。

A. head==NULL B. head->next==NULL C. head->next==head D. head!=NULL

7．在循环双链表的p所指结点之后插入s所指结点的操作是( )。 A. p->next=s; s->prior=p; p->next->prior=s; s->next=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，元素s1,s2,s3,s4,s5,s6依次进栈，如果6个元素出栈的顺序是s2,s4,s3,s6,s5,s1，则栈的容量至少应该是____________。 A．3 B．4 C．5 D．6

9．在—个栈顶指针为top的链栈中，将一个s指针所指的结点入栈，执行____________。 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．链栈和顺序栈相比，有一个比较明显的优点，即____________。 A．插入操作更加方便 B．通常不会出现栈满的情况 C．不会出现栈空的情况 D．删除操作更加方便

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

A．(Q->rear+1)%m==Q->front B．Q->rear==Q->front+1 C．Q->rear+1==Q->front D．Q->rear==Q->front

12．若一个栈的输入序列为1,2,3,?,n，输出序列的第一个元素是n，则第i个输出元素是( )。

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

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

A．fedcba B. bcafed C. dcefba D. cabdef 14.中缀表达式A-（B+C/D）*E的后缀形式是（ ）。

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

15.假设以数组A[m]存放循环队列的元素,其头尾指针分别为front和rear，则当前队列中的元素个数为( )。

A．(rear-front+m)%m B．rear-front+1 C．(front-rear+m)%m D．(rear-front)%m

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

A. rear=rear+1 B. rear=(rear+1)%(m-1) C. rear=(rear+1) % m D. rear=(rear+1)%(m+1) 17．下面关于串的叙述中，哪一个是不正确的？_________

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

C．模式匹配是串的一种重要运算 D．串既可以采用顺序存储，也可以采用链式存储 18．已知串S=＂aaab＂,其next数组值为_________。

A．0，1，2，3 B．1，1，2，3 C．1，2，3，1 D．1，2，1，1 19． 一维数组A采用顺序存储结构，每个元素占用6个字节，第6个元素的起始地址为100，则该数组的首地址是 。

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

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

A．表达变得简单 B．对矩阵元素的存取变得简单 C．去掉矩阵中的多余元素 D．减少不必要的存储空间的开销

21．若对n阶对称矩阵A以行序为主序方式将其下三角形的元素(包括主对角线上所有元素)依次存放于一维数组B［1..(n(n+1))/2］中，则在B中确定aij(i

A. i*(i+1)/2+j B. j*(j+1)/2+i C. i*(i+1)/2+j+1 D. j*(j+1)/2+i+1

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

A．GetHead(GetTail(LS)) B．GetHead(GetTail(GetTail (GetHead (LS)))) C．GetTail (GetHead (LS)) D．GetHead(GetTail(GetHead(GetTail(LS)))) 23. 设广义表L=((a,b,c))，则L的长度和深度分别为 。 A. 1和1 B. 1和3 C. 1和2 D. 2和3

24. 一个100*90的稀疏矩阵，非0元素有10个整型数，设每个整型数占2字节，则用三元组表示该矩阵时，所需的字节数是_____________。

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

25．设二维数组A[1.. m，1.. n](即m行n列)按行存储在数组B[1.. m*n]中，则二维数组元素A[i][j]在一维数组B中的下标为( )。

A.(i-1)*n+j B.(i-1)*n+j-1 C. i*(j-1) D. j*m+i-1

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

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

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

A．n在m右方 B．n是m祖先 C．n在m左方 D．n是m子孙 28．对一个满二叉树，m个树枝，n个结点，深度为h，则____________。

h

A．n=h+m B．h+m=2n C．m=h-1 D．n=2-1

29．以二叉链表作为二叉树的存储结构，在有n个结点的二叉链表中(n>0)，链表中空链域的个数为____________。

A．2n-1 B．n-1 C．n+1 D．2n+1

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

A．都不相同 B．先序和中序相同，而与后序不同 C．完全相同 D．中序和后序相同，而与先序不同

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

A．哈夫曼树 B．平衡二叉树 C．二叉树 D．完全二叉树 32．树的先根序列和其对应的二叉树的 是一样的，树的后根序列和其对应的二叉树的 是一样的。

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

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

A．K B．N C．N-K D．1

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

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

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

A．5 B．6 C．7 D．8 36. 由4个结点可以构造出多少种不同的二叉树？( )

A．10 B．12 C．14 D．16 37. 二叉树在线索后，仍不能有效求解的问题是( )。

A．先序线索二叉树中求先序后继 B．中序线索二叉树中求中序后继 C．中序线索二叉树中求中序前驱 D．后序线索二叉树中求后序后继 38. 一棵二叉树具有10个度为2的结点，5个度为1的结点，则度为0的结点个数是( )。

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

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

A． 2h B．2h-1 C． 2h+1 D． h+1

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

A．不确定 B．2n C．2n+1 D．2n-1

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

A．空或只有一个结点 B．完全二叉树 C．单支树 D．高度等于结点数 42. 在二叉树结点的先序序列，中序序列和后序序列中，所有叶子结点的先后顺序( )。

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

C．先序和中序相同，而与后序不同 D．中序和后序相同，而与先序不同 43. 根据使用频率，为５个字符设计的哈夫曼编码不可能是( )。

A．111,110,10,01,00 B．000,001,010,011,1 C．100,11,10,1,0 D．001,000,01,11,10

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

A. 6 B. 7 C. 8 D. 9 45．设无向图的顶点个数为n，则该图最多有____________条边。

2

A．n-1 B．n(n-1)/2 C． n(n+1)/2 D．0 E．n 46．下列哪一种图的邻接矩阵是对称矩阵？____________

A．有向图 B．无向图 C．AOV网 D．AOE网

47．在有向图的邻接表存储结构中，顶点v在链表结点中出现的次数是_____________。 A．顶点v的度 B．顶点v的出度 C．顶点v的入度 D．依附于顶点v的边数 48．采用邻接表存储图的深度优先遍历算法类似于树的_____________。 A．中根遍历 B．先根遍历 C．后根遍历 D．层次遍历 49. 关键路径是指AOE(Activity On Edge)网中_____________。

A． 最长的回路 B． 最短的回路 C． 从源点到汇点(结束顶点)的最长路径

D． 从源点到汇点(结束顶点)的最短路径

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

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

51．一个n个顶点的连通无向图，其边的个数至少为( )。

A. n-1 B. n C. n+1 D. nlog2n 52． 图的广度优先搜索类似于树的( )遍历。

A. 先序 B. 中序 C. 后序 D. 层次 53． 下面( )方法可以判断出一个有向图是否有环(回路)。

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

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

A. G中有弧 B. G中有一条从Vi到Vj的路径 C. G中没有弧 D. G中有一条从Vj到Vi的路径

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

A. n B. n+1 C. (n-1)/2 D. (n+1)/2 56．折半查找的时间复杂度_____________。

A.Ｏ(n*n) B.Ｏ(n) C. Ｏ(nlog2n) D. Ｏ(log2n) 57．采用分块查找时，数据的组织方式为_____________。 Ａ. 把数据分成若干块，每块内数据有序 Ｂ. 把数据分成若干块，块内数据不必有序，但块间必须有序，每块内最大(或最小)的数据组成索引表

Ｃ. 把数据分成若干块，每块内数据有序，每块内最大(或最小)的数据组成索引表 Ｄ. 把数据分成若干块，每块(除最后一块外)中的数据个数相等

58．二叉排序树的查找效率与二叉排序树的 (1) 有关，当 (2) 时，查找效率最低，其查找长度为n。

(1) Ａ.高度 Ｂ.结点的个数 Ｃ.形状 Ｄ.结点的位置

(2) Ａ.结点太多 Ｂ.完全二叉树 Ｃ.呈单叉树 Ｄ.结点的结构太复杂

59．在一棵AVL树(平衡二叉树)中，每个结点的平衡因子的取值范围是_____________。 A. -1～1 B. -2～2 C. 1～2 D. 0～1

60．在平衡二叉树中插入一个结点后造成了不平衡，设最低的不平衡结点为A,并已知A的左孩子的平衡因子为0,右孩子的平衡因子为1,则应作( ) 型调整以使其平衡。

A. LL B. LR C. RL D. RR 61．下面关于折半查找的叙述正确的是( ) 。

A. 表必须有序，表可以顺序方式存储，也可以链表方式存储 B. 表必须有序且表中数据必须是整型，实型或字符型 C. 表必须有序，而且只能从小到大排列 D. 表必须有序，且表只能以顺序方式存储

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

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

C. 15，25，30，35，45，55，95 D. 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. 2-1 B. 2+1 C. 2+1 D.2-1

68. 设无向连通图的顶点个数为n，则该图最少有( )条边。 A．n-1 B．n(n-1)/2 C． n(n+1)/2 D．0 69.下列说法正确的是_________

A.链表在物理存储空间上一定是离散的。 B.顺序表在物理存储空间上一定是连续的。 C.堆栈的物理存储空间结构一定是离散的。 D.队列的物理存储空间结构一定是连续的。 70. 下列排序算法中，其中( )是稳定的。

A. 堆排序，冒泡排序 B. 快速排序，堆排序 C. 简单选择排序，归并排序 D. 归并排序，冒泡排序

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

2

A．O(1) B．O(n) C．O(n) D．O(log2n)

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

A．堆排序 B．直接插入排序 C．二路归并排序 D．快速排序 73. 若需在O(nlog2n)的时间内完成对数组的排序，且要求排序是稳定的，则可选择的排序方法是( )。

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

74. 一组记录的关键字为{46,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}，则利用堆排序方法建立的初始大根堆为( )。

h

h

h-1

h+1

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?0??0A???0?0??0-3000001102000000000000400?-1??0?? 0?0??0?(1)画出其三元组表形成的压缩存储表。 (2)画出其十字链表形成的压缩存储表。 4．图的邻接表如图所示：

vertex firstedge 1 3 ∧ V0

V1 0 2 3 ∧ V2 1

V3 0 1 ∧ 图 邻接表

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

(2)写出从顶点V0出发进行广度优先搜索的遍历序列。 答案：V0→V1→V2→V3，V0→V1→V3→V2 5．写出下图所示的四个拓扑序列。

V0 V3

v1 V5 V2 V6 V4

答案：V0V1V5V2V6V3V4，V5V1V0V6V2V3V4，V0V1V5V2V3V6V4。

6．对于下图所示的连通图，请用Prim算法构造其最小生成树。

16

① ② 5 21

19 9 ⑥ 14 ③

⑤

26

11 18

6 ④ 解：

(1) Prim算法的基本思想：从某个顶点集(初始时只有一个顶点)开始，通过加入与其中顶点相关联的最小代价的边，来扩大顶点集合，直至将所有的顶点包含其中。其最小生成树的构造过程如图所示(假设从顶点V1开始)。

①

14

① 14

16

② ① 14

16

② 5

③

⑤

(a)

16

⑤

(b)

⑤ ① 5

14

(c) 16

① 14

② ② 5

③

6 ⑥ 11

6 ③

④ ⑤

(d)

④ ⑤

(e)

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

7．假定一个线性序列为 (30，25，40，18，27，36，50，10，32，45 )，按此序列中的元素顺序生成一棵二叉排序树，并求出在该二叉排序树上查找成功时的平均查找长度。

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

30 25 30 25 30 40 18 30 25 30 40 25 18 30 40 25 27 30 18 30 40 27 36 18 30 25 18 10 27 32 36 25 30 40 27 36 50 25 18 10 27 36 40 50 10 18 25 27 32 36 40 50 40 50 45

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

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

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

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

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

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

(1) (2)

图6.7

9．设电文由6个字符A，B，C，D，E，F组成，它们在电文中出现的次数分别为：10,4,8,3，2,7。试画出用于编码的哈夫曼树，并列出每个字符的编码。

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

34 ○ 19 15 ○○ 10 ○9 8 7 ○○○

5 4 ○○

2 ○

图6.18

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

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

10．设有一个关键字的输入序列 { 55, 31, 11, 37, 46, 73, 63, 02, 07 }, (1) 从空树开始构造平衡二叉树, 画出插入46之前的平衡二叉树。 (2) 46插入之后哪一个结点平衡因子失效？属于4种调整方式中哪一种？ (3) 画出插入46并调整之后的平衡二叉树。 解：（1）

55 31 11 31 11 37 46 46 31 11 37 63 55 55 LR 11 37 31 46 55 11 37 31 46 55 73 55 31 55 31 31 55 11 37 46 55 LL 11 RR 11 31 37 55 73 RL 31 73 11 46 63 73 02 07 11 31 46 63 46 LR 73 02 07 11 31 63 73 37 55 37 55 37 55

11. 已知一棵二叉树的中序序列和后序序列分别为BDCEAFHG和DECBHGFA，画出这棵二叉树。并写出其先序遍历序列。 12. 给定一组数列(15,8,10,21,6,19,3)分别代表字符A,B,C,D,E,F,G出现的频度，试画出哈 夫曼树，给出各字符的编码值。

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] 第一趟归并： [27 35] [55 70] [20 67] [26 28]

第二趟归并： [27 35 55 70] [20 26 28 67] 第三趟归并： [20 26 27 28 35 55 67 70]

14．给定关键字序列(26,25,20,33,21,24,45,204,42,38,29,31)，要用哈希法进行存储，规定负载因子α=0.6。 (1)请给出除余法的哈希函数。

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

15．设哈希函数为H(K)=K MOD 11，解决冲突的方法为链地址法，试将下列关键字集合{35,67,42,21,29,86,95,47,50,36,91}依次插入到哈希表中(画出哈希表的示意图)。并计算平均查找长度ASL。

16．依次输入表(30,15,28,20,24,10,12,68,35,50,46,55)中的元素，生成一棵二叉排序树。 (1) 试画出生成之后的二叉排序树;

(2) 对该二叉排序树作中序遍历，试写出遍历序列;

(3) 假定每个元素的查找概率相等，试计算该二叉排序树的平均查找长度。

17．设有关键字序列：5,2,15,7,6,3,12,8，写出直接插入排序算法进行排序的每一趟结果。 解：初始序列： [5],2,15,7,6,3,12,8

第一趟插入： [2,5],15,7,6,3,12,8 第二趟插入： [2,5,15],7,6,3,12,8 第三趟插入： [2,5,7,15],6,3,12,8 第四趟插入： [2,5,6,7,15],3,12,8 第五趟插入： [2,3,5,6,7,15],12,8 第六趟插入： [2,3,5,6,7,12,15],8 第七趟插入： [2,3,5,6,7,8,12,15] 四、程序设计题。

1．根据如下定义的数据类型，写一个创建单链表的函数，其原型为Node * CreateList( )，该函数完成的功能为：从键盘终端读入用户输入的一序列整数（碰到0就结束），建立一个单向链表，并返回单项链表的附加头结点。 typedef struct node {

int num;

struct node *next ; }Node;

2．有一个带附加头结点的单链表head，已知单链表结点递增有序，写一个插入函数，其原型为void insert(plist s)，将s节点插入到此单链表中，并维持单链表递增特性。 节点类型定义如下： typedef struct node {

int data;

struct node *next; }*plist; plist head;

3．链式存储的栈，写出进栈函数int push(Stack S, Snode *t)。 有关数据类型如下： typedef struct node {

Datatype data; struct node *next; }Snode;

typedef struct stack {

Snode *top; }Stack;

注：进栈成功函数返回1，否则返回0。

4．顺序存储的循环队列，写出其进队列函数int enQue(Que Q，Datatype x)。 有关数据类型如下： typedef struct node {

Datatype elem[MAX]; int front,rear; }Que;

注：进队列成功函数返回1，否则返回0。

5．写出字符串的比较函数int strcmp(char *s1, char *s2); 注：函数返回两字符串首个不同字符的ASCII码差值。

6．试用递归方法写一个在二叉排序树中插入结点的算法，且要求没有重复结点。假设其根结点的指针为root，插入结点的指针为s。

分析：若root为空，则s作为根结点插入，算法结束。

若s->data等于root->data，为避免重复则对s无需插入，算法结束。 若s->data小于root->data，则递归插入到左子树； 若s->data大于root->data，则递归插入到右子树； 递归算法如下:

void InsertBST(pTree &root, pTree s) { if (root==NULL)

{ root=s; }

else if(s->datadata) InsertBST(root->left,s); else if(s->data>root->data) InsertBST(root->right,s); }

7．写一个函数int count(pTree root)统计以root为根的二叉树中结点总数。 二叉树中节点类型定义如下： typedef struct node {

int data;

struct node *left,*right; }*pTree；

8．将题5中统计结点总数改为统计叶子结点总数。 9．将题5中统计结点总数改为统计度为1的结点总数。

10．假设一个图的邻接矩阵为adj[][]，写出函数deep(int v)，它从顶点v开始进行深度优先遍历。【注：输出依次遍历的顶点即可】

11．写出冒泡排序函数，void bubble（int a[ ], int n），对数组元素a[1]~a[n]排成递增有序。 12．写出归并排序函数，void merge（int a[ ], int from, int to），对数组元素a[from]~a[to]排成递增有序。

本文来源：https://www.bwwdw.com/article/3j7r.html