福建师范大学数学与计算机学院计算机科学与技术
《数据结构与算法》期末练习
一 选择题
1．算法的计算量的大小称为计算的（ B ）。
A．效率 B. 复杂性 C. 现实性 D. 难度 2．下面说法错误的是（ C ）
(1）算法原地工作的含义是指不需要任何额外的辅助空间
（2）在相同的规模n下，复杂度O(n)的算法在时间上总是优于复杂度O(2)的算法 （3）所谓时间复杂度是指最坏情况下，估算算法执行时间的一个上界 （4）同一个算法，实现语言的级别越高，执行效率就越低
A．(1) B.(1),(2) C.(1),(4) D.(3) 3. 连续存储设计时，存储单元的地址（ A ）。
A．一定连续 B．一定不连续 C．不一定连续 D．部分连续，部分不连续 4. 下述哪一条是顺序存储结构的优点？（A ）
A．存储密度大 B．插入运算方便 C．删除运算方便 D．可方便地用于各种逻辑结构的存储表示 5．若某线性表最常用的操作是存取任一指定序号的元素和在最后进行插入和删除运算，则利用（ A ）存储方式最节省时间。
A．顺序表 B．双链表 C．带头结点的双循环链表 D．单循环链表 6．下面的叙述不正确的是（ BC ）
A．线性表在链式存储时，查找第i个元素的时间同i的值成正比 B. 线性表在链式存储时，查找第i个元素的时间同i的值无关
C. 线性表在顺序存储时，查找第i个元素的时间同i 的值成正比 D. 线性表在顺序存储时，查找第i个元素的时间同i的值无关
7．若长度为n的线性表采用顺序存储结构，在其第i个位置插入一个新元素的算法的时间复杂度为（ C ）(1<=i<=n+1)。
A. O(0) B. O(1) C. O(n) D. O(n)
8．双向链表中有两个指针域，llink和rlink，分别指回前驱及后继，设p指向链表中的一个结点，q指向一待插入结点，现要求在p前插入q，则正确的插入为（D ）
A. p＾.llink:=q; q＾.rlink:=p; p＾.llink＾.rlink:=q; q^.llink:=p^.llink; B. q＾.llink:=p^.llink; p＾.llink^.rlink:=q; q＾.rlink:=p; p^.llink:=q^.rlink; C. q^.rlink:=p; p^.rlink:=q; p^.llink^.rlink:=q; q^.rlink:=p; D. p^.llink^.rlink:=q; q^.rlink:=p; q^.llink:=p^.llink; p^.llink:=q; 9．下列排序算法中，其中（ D ）是稳定的。
A) 堆排序，冒泡排序 B) 快速排序，堆排序 C) 直接选择排序，希尔排序 D) 归并排序，冒泡排序
10．对一组数据（84，47，25，15，21）排序，数据的排列次序在排序的过程中的变化为 （1） 84 47 25 15 21 （2） 15 47 25 84 21 （3） 15 21 25 84 47 (4） 15 21 25 47 84 则采用的排序是 ( A )。
A) 选择 B) 冒泡 C) 快速 D) 插入
11．双向链表中有两个指针域，llink和rlink分别指向前趋及后继，设p指向链表中的一个结点，现要求删去p所指结点，则正确的删除是（ D）（链中结点数大于2，p不是第一个结点）
2
n
A．p^.llink^.rlink:=p^.llink; p^.llink^.rlink:=p^.rlink; dispose(p); B．dispose(p); p^.llink^.rlink:=p^.llink; p^.llink^,rlink:=p^.rlink; C．p^.llink^.rlink:=p^.llink; dispose(p); p^.llink^.rlink:=p^.rlink; D．以上A，B，C都不对。
12.一棵二叉树的前序遍历序列为ABCDEFG，它的中序遍历序列可能是（ B ）
A)CABDEFG B) BCDAEFG C) DACEFBG D) ADBCFEG
13. 设一个栈的输入序列是 1，2，3，4，5,则下列序列中，是栈的合法输出序列的是（ D ）。
A) 5 1 2 3 4 B) 4 5 1 3 2 C) 4 3 1 2 5 D) 3 2 1 5 4
14. 若一个栈的输入序列为1,2,3,?,n，输出序列的第一个元素是i，则第j个输出元素是（ D ）。
A. i-j-1 B. i-j C. j-i+1 D. 不确定的 15. 一个递归算法必须包括（ B ）。
A. 递归部分 B. 终止条件和递归部分 C. 迭代部分 D.终止条件和迭代部分
16. 若需在O(nlog2n)的时间内完成对数组的排序，且要求排序是稳定的，则可选择的排序方法是（ C ）。 A) 快速排序 B) 堆排序 C) 归并排序 D) 直接插入排序 17．下面关于串的的叙述中，哪一个是不正确的？（ B ）
A．串是字符的有限序列 B．空串是由空格构成的串
C．模式匹配是串的一种重要运算 D．串既可以采用顺序存储，也可以采用链式存储 18．稳定的排序方法是（ B ）
A)直接插入排序和快速排序 B)折半插入排序和起泡排序 C)简单选择排序和四路归并排序 D)树形选择排序和shell排序 19．已知串S=‘aaab’,其Next数组值为（ A ）。
A．0123 B．1123 C．1231 D．1211 20．串的长度是指（ B ）
A．串中所含不同字母的个数 B．串中所含字符的个数 C．串中所含不同字符的个数 D．串中所含非空格字符的个数
21. 某堆栈的输入序列为a, b，c ，d,下面的四个序列中，不可能是它的输出序列的是（ D ）。 A) a，c，b，d B) b, c，d，a C) c, d，b, a D) d, c，a，b
22．数组A[0..5,0..6]的每个元素占五个字节，将其按列优先次序存储在起始地址为1000的内存单元中，则元素A[5，5]的地址是( A )。
A. 1175 B. 1180 C. 1205 D. 1210
23．A[N，N]是对称矩阵，将下面三角（包括对角线）以行序存储到一维数组T[N（N+1）/2]中，则对任一上三角元素a[i][j]对应T[k]的下标k是（ B ）。
A. i（i-1）/2+j B. j（j-1）/2+i C. i（j-i）/2+1 D. j（i-1）/2+1
24. 已知广义表LS＝((a,b,c),(d,e,f)),运用head和tail函数取出LS中原子e的运算是( C )。 A. head(tail(LS)) B. tail(head(LS))
C. head(tail(head(tail(LS))) D. head(tail(tail(head(LS)))) 25．下面说法不正确的是( A )。
A. 广义表的表头总是一个广义表 B. 广义表的表尾总是一个广义表 C. 广义表难以用顺序存储结构 D. 广义表可以是一个多层次的结构
26．一组记录的关键码为（46，79，56，38，40，84），则利用快速排序的方法，以第一个记录为基准得到的一次划分结果为（ C ）。
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)
27. 已知一算术表达式的中缀形式为 A+B*C-D/E，后缀形式为ABC*+DE/-，其前缀形式为( D )
A．-A+B*C/DE B. -A+B*CD/E C．-+*ABC/DE D. -+A*BC/DE 28. 若一棵二叉树具有10个度为2的结点，5个度为1的结点，则度为0的结点个数是（ B）
A．9 B．11 C．15 D．不确定
29. 若二叉树采用二叉链表存储结构，要交换其所有分支结点左、右子树的位置，利用(C)遍历方法最合适。
A．前序 B．中序 C．后序 D．按层次
30. 将一个长度为n的向量的第i 个元素删除时，需要前移( B )个元素。
A) i B) n-i C) n+1 D) n-i+1
31. 某二叉树T有n个结点，设按某种顺序对T中的每个结点进行编号，编号为1，2，? ，n，且有如下性质：T中任一结点V，其编号等于左子树上的最小编号减1，而V的右子树的结点中，其最小编号等于V左子树上结点的最大编号加1。这时是按( B )编号的。
A.中序遍历序列 B.前序遍历序列 C.后序遍历序列 D.层次顺序 32. 线索二叉树是一种（ C ）结构。
A． 逻辑 B． 逻辑和存储 C． 物理 D．线性 33. 非空循环链表head 的尾结点 *p 满足下列( C )条件
A)head->next==p; B)head==p; C)p->next==head; D)p->next==0 34. 一个栈的输入序列是a,b,c,d,e ，则可能的出栈序列是( D )。
A) ecdab
35. 设栈s的类型为sqstack ，判定栈空的条件是( C )。
A) s==NULL B)s->top==0 C)s.top==0 D) s.top==NULL 36. 深度为5 的二叉树至多有个( B )结点。
A) 12
B) 31
C) 14
D) 15
37. 已知二叉树的后、中根序列分别是bedfca 和 badecf，则该二叉树的前根遍历序列是( C )。 A)defbca B)fedbca
C) abcdef D)fedcba
38. 一个有n个顶点的有向图最多有( B )弧 。
A) n(n+1) B) n(n-1) C) n(n+1)/2 D) n(n-1)/2
39. 具有n个顶点的无向图至少要有( B )条边才有可能是一个连通图。
A) n(n+1) B) n-1 C) n+1 D) n(n-1) 40. 图中有关路径的定义是（ A ）。
A．由顶点和相邻顶点序偶构成的边所形成的序列 B．由不同顶点所形成的序列 C．由不同边所形成的序列 D．上述定义都不是
41. 一个向量的第一个元素的地址是100，每个元素的长度是2 ，则第五个元素的地址是( C )
A) 102 B) 110 C) 108 D) 120
42. 一个循环顺序队列 ,队头、尾指针的值分别为front,rear，则队列中元素个数为( A )。（maxlen为循环顺序表的长度）
A) (rear-front+maxlen) % maxlen B) (rear-front) % maxlen C) rear-front+1 D) front-rear+1
43. 一个有n个顶点的图最少有( D )条边。
A) n(n+1) B) n(n-1) C) n(n+1)/2 D) 0
44. 具有5个顶点的无向图至少要有( A )条边才能确保是一个连通图。
A) 4 B) 5 C) 6 D) 7
B)cebda C)daecb D)abcde
45. 设栈s的类型为sqstack ，最多可容纳maxlen个元素，则判定栈满的条件是( B )。
A) s==maxlen-1 B) s.top==maxlen-1 C) s->top==maxlen-1 D) s.top==0
46. 一个顺序队列q的类型为sqqueue,队头、尾指针分别为front,rear，最多可容纳maxlen个元素，则队空的条件是( C )。
A) front==rear B) rear==0 C) q.front==q.rear D) rear==maxlen-1
47. 下面是求连通网的最小生成树的prim算法：集合VT，ET分别放顶点和边，初始为（ 1 ），下面步骤重复n-1次: a：（ 2 ）；b：（ 3 ）；最后：（ 4 ）。
（1）．A．VT，ET为空 B．VT为所有顶点，ET为空 C．VT为网中任意一点，ET为空 D．VT为空，ET为网中所有边
（2）．A. 选i属于VT，j不属于VT，且（i，j）上的权最小 B．选i属于VT，j不属于VT，且（i，j）上的权最大 C．选i不属于VT，j不属于VT，且（i，j）上的权最小 D．选i不属于VT，j不属于VT，且（i，j）上的权最大
（3）．A．顶点i加入VT，（i,j）加入ET B. 顶点j加入VT，（i,j）加入ET C. 顶点j加入VT，（i,j）从ET中删去 D．顶点i,j加入VT，（i,j）加入ET
（4）．A．ET 中为最小生成树 B．不在ET中的边构成最小生成树 C．ET中有n-1条边时为生成树，否则无解 D．ET中无回路时，为生成树，否则无解
CABA
48. 链栈与顺序栈相比，比较明显的优点是( D )
A)插入操作更加方便 B)删除操作更加方便 C)不会出现下溢的情况 D)不会出现上溢的情况
49. 下面关于二分查找的叙述正确的是 ( D )
A. 表必须有序，表可以顺序方式存储，也可以链表方式存储 C. 表必须有序，而且只能从小到大排列
B. 表必须有序且表中数据必须是整型，实型或字符型 D. 表必须有序，且表只能以顺序方式存储
50. 二叉查找树的查找效率与二叉树的( （1）)有关, 在 (（2）)时其查找效率最低 (1): A. 高度 B. 结点的多少 C. 树型 D. 结点的位置 (2): A. 结点太多 B. 完全二叉树 C. 呈单枝树 D. 结点太复杂。
CC
51. 如果求一个连通图中以某个顶点为根的高度最小的生成树，应采用（ B ）
A)深度优先搜索算法
B)广度优先搜索算法 D)拓扑排序算法
C)求最小生成树的prim算法
52. 既希望较快的查找又便于线性表动态变化的查找方法是 ( C ) A．顺序查找 B. 折半查找 C. 索引顺序查找 D. 哈希法查找
53. 对表长为n的顺序表进行顺序查找，在查找概率相等的情况下，查找成功的平均查找长度为( C )
A) (n-1)/2 B) n/2 C) (n+1)/2 D) n
54. 对于哈希函数H(key)=key,被称为同义词的关键字是( D )
A)35和41 B)23和39 C)15和44 D)25和51 55. 某内排序方法的稳定性是指( D)。
A．该排序算法不允许有相同的关键字记录 B．该排序算法允许有相同的关键字记录 C．平均时间为0（n log n）的排序方法 D．以上都不对
56. 下列内部排序算法中：
A．快速排序 B.直接插入排序 C. 二路归并排序 D. 简单选择排序 E. 起泡排序 F. 堆排序 （1） 其比较次数与序列初态无关的算法是（ ） （2）不稳定的排序算法是（ ）
（3）在初始序列已基本有序（除去n个元素中的某k个元素后即呈有序，k< （4）排序的平均时间复杂度为O(n?logn)的算法是（ ）为O(n?n)的算法是（ ） 1 DC 2 ADF 3 B 4 ACF BDE 57. 下列排序算法中(C )排序在一趟结束后不一定能选出一个元素放在其最终位置上。 A. 选择 B. 冒泡 C. 归并 D. 堆 58. 栈和队列都是（ A ） A)限制存取位置的线性结构 C)顺序存储的线性结构 B)链式存储的非线性结构 D)限制存取位置的非线性结构 59. 对关键码序列28，16，32，12，60，2，5，72快速排序，从小到大一次划分结果为（ B ）。 A. (2,5,12,16)26(60,32,72) B. (5,16,2,12)28(60,32,72) C. (2,16,12,5)28(60,32,72) D. (5,16,2,12)28(32,60,72) 60. 一棵含有n个节点的k叉树，可能达到的最小深度为多少？（ C ） A) n-k B) n-k+1 C) |logkn|+1 D) |logkn| 其中|k|表示下取整 61. 下列序列中( B )不是堆。 A) 12 36 53 68 48 60 75 B) 12 48 53 68 36 60 75 C) 12 48 36 60 75 68 53 D) 12 36 60 53 48 68 75 62. 在下列内排序方法中，( C )的平均时间复杂性是O(nlogn)。 A) 直接插入排序 B) 简单选择排序 C) 快速排序 D) 希尔排序 63. 设顺序栈s非空，则语句段( C )可实现栈s的出栈操作，其中s.top为栈顶指针，s.elem为栈空间，出栈的元素存放在x中。 A) s.top:=s.top+1; B) x:=s.elem[s.top]; x:=s.elem[s.top]; s.top:=s.top+1; C) s.top:=s.top-1; D) x:=s.elem[s.top]; x:=s.elem[s.top]; s.top:=s.top-1; 64. 有一组数据（15，9，7，8，20，-1，7，4），用堆排序的筛选方法建立的初始堆为 （ C ） A．-1，4，8，9，20，7，15，7 B．-1，7，15，7，4，8，20，9 C．-1，4，7，8，20，15，7，9 D．A，B，C均不对。 65. 下述二叉树中,哪一种满足性质:从任一结点出发到根的路径上所经过的结点序列按其关键字有序（ D ）。 A)二叉排序树 B)哈夫曼树 C)AVL树 D)堆 66. 下面给出的四种排序法中( D )排序法是不稳定性排序法。 A) 插入 B) 冒泡 C) 二路归并 D) 快速排序 67. 算法的时间复杂度取决于（ A ） A．问题的规模 B. 待处理数据的初态 C. A和B D. 计算机cpu 68. 有关静态链表的叙述：(1) 静态链表既有顺序存储的优点，又有动态链表的优点。所以，它存取表中第i个元素的时间与i无关。(2) 静态链表中能容纳的元素个数的最大数在表定义时就确定了，以后不能增加。(3) 静态链表与动态链表在元素的插入、删除上类似，不需做元素的移动。以上错误的是（ B ） A．（1），（2） B．（1） C．（1），（2）,(3) D.（2） 69．一个栈的输入序列为123?n，若输出序列的第一个元素是n，输出第i（1<=i<=n）个元素是（ B ）。 A. 不确定 B. n-i+1 C. i D. n-i 70．下面关于串的的叙述中，哪一个是不正确的？（ B ） A．串是字符的有限序列 B．空串是由空格构成的串 C．模式匹配是串的一种重要运算 D．串既可以采用顺序存储，也可以采用链式存储 71. 关于二叉树的叙述：①只有一个结点的二叉树的度为0; ②二叉树的度为2； ③二叉树的左右子树可任意交换;④深度为K的完全二叉树的结点个数小于或等于深度相同的满二叉树。正确的是（ D ） A．①②③ B．②③④ C．②④ D．①④ 72．用DFS遍历一个无环有向图，并在DFS算法退栈返回时打印相应的顶点，则输出的顶点序列是( A )。 A．逆拓扑有序 B．拓扑有序 C．无序的 73. 对n个关键字的序列进行快速排序，平均情况下的空间复杂度为( B ) A.O(1) B.O(logn) C.O(n) D.O(n logn) 二 填空题 1、在单链表L中，指针p所指结点有后继结点的条件是： p->next!=null 2、n（n大于1）个结点的各棵树中，其深度最小的那棵树的深度是_(1)__。它共有_(2)__个叶子结点和_(3)__个非叶子结点，其中深度最大的那棵树的深度是_(4)__，它共有_(5)__个叶子结点和_(6)__个非叶子结点。 (1)2 (2) n-1 (3) 1 (4) n (5) 1 (6) n-1 3、深度为9的完全二叉树最多有 个结点 256 4、二叉树由_(1)__，__(2)_，_(3)__三个基本单元组成。 .(1)根结点(2)左子树(3)右子树 5、先根遍历树林正好等同于按__ _遍历对应的二叉树. 先序 6、设只含根结点的二叉树的高度为0，则高度为k的二叉树的最大结点数为______,最小结点数为______。 (1) 2-1 (2) k+1 7、在有序表A[1..12]中，采用二分查找算法查等于A[12]的元素，所比较的元素下标依次为 6,9,11,12 8、设y指向二叉线索树的一叶子，x指向一待插入结点，现x作为y的左孩子插入，树中标志域为ltag和rtag，并规定标志为1是线索，则下面的一段算法将x插入并修改相应的线索，试补充完整：(lchild,rchild分别代表左，右孩子) x^.ltag:= (1)___; x^.lchild:= (2)___; y^.ltag:= (3)___; y^.lchild:= (4)___; x^.rtag:= (5)___; x^.rchild:= (6)___; IF (x^.lchild<>NIL) AND (x^lchild^.rtag=1) THEN x^.lchild^.rchild:= (7)___; (1)1 (2)y^.lchild (3)0 (4)x (5)1 (6) y (7)x(本题按中序线索化) 9、有N个顶点的有向图，至少需要量_______条弧才能保证是连通的。 N-1 10、在顺序表（8,11,15,19,25,26,30,33,42,48,50）中，用二分（折半）法查找关键码值11，需做的关 键码比较次数为 4 11、①二叉树用来表示表达式，因为需要保存各子树的值，修改二叉树的结点结构为(Lchild,Data,Val,Rchild)。其中Lchild,Rchild的意义同前，Val用来存放以该结点为根的子树的值，值的类型依具体情况而定。为了简便起见，算法假定所考虑的表达式只有+，-，*，/ 四种二目运算，且已表示成相应的二叉树。算法所计算的表达式值放在根结点的Val域中。 PROC Postorder-eval(t:ptrType) BEGIN IF (t!=NULL) K+1 BEGIN (1)_______; (2)_______; CASE t^.data: ‘+’: t^.Val:=t^. Lchild^. Val + t^. Rchild ^. Val; BREAK; ‘-’: t^.Val:=t^. Lchild^. Val - t^. Rchild ^. Val; BREAK; ‘*’: t^.Val:=t^. Lchild^. Val * t^. Rchild ^. Val; BREAK; ‘/’: t^.Val:=t^. Lchild^. Val / t^. Rchild ^. Val; BREAK; otherwise: (3)___; BREAK; ENDCASE END END; ②PROC Delete(x:datatype,A:tree) BEGIN tempA:= (4)___; WHILE (tempA^.Item!=x) AND (tempA!=NULL) DO IF (x ELSE BEGIN r:=tempA;tempA:=tempA^.Rchild;END;//tempA为要删结点，r为tempA的父亲 IF (6)___ return(x); IF (tempA^.Lchild!=NULL) AND (tempA^.rchild!=NULL) BEGIN t:=tempA; q:=tempA^.Rchild; WHILE (q^.Lchild!=NULL) DO BEGIN t:=q; q:=q^.Lchild; END; t^.Lchild:= (7)___; //删去q q^.Lchild :=tempA^.Lchild; q^.Rchild:=tempA^.Rchild; IF (tempA^.item< r^.item) r^.Lchild := (8)_ ELSE r^.Rchild:=q //用q代替 tempA END; ELSE IF(tempA^.Lchild!=NULL) IF(tempA^.item ELSE IF(tempA^.Rchild!=NULL) IF(tempA^.item ELSE r^.Lchild:=tempA^.Rchild ELSE //tempA为树叶 IF(10)_ r^.Lchild:=NULL ELSE r^.Rchild:=NULL END; 本题①是表达式求值，②是在二叉排序树中删除值为x的结点。首先查找x，若没有x，则结束。否则分成四种情况讨论：x结点有左右子树；只有左子树；只有右子树和本身是叶子。 (1)Postoder_eval(t^.Lchild) (2) Postorder_eval(t^.Rchild) (3)ERROR(无此运算符)(4)A (5)tempA^.Lchild (6)tempA=NULL (7)q^.Rchild (8)q (9)tempA^.Rchild (10)tempA^.Item 12、利用树的孩子兄弟表示法存储，可以将一棵树转换为______。 二叉树 13、n个结点的完全有向图含有边的数目__(7) n*（n－l） 14、当问题的规模n趋向无穷大时，算法执行时间T(n)的数量级被称为算法的________。 时间复杂度 15、假设S和X分别表示进栈和出栈操作，由输入序列“ABC”得到输出序列“BCA”的操作序列为SSXSXX，则由“a*b+c/d”得到“ab*cd/+”的操作序列为___________。 SXSSXXSSXSSXXX 16、在一棵度为3的树中，度为2的结点个数是1，度为0的结点个数是6，则度为3的结点个数是________。 2 17、设t是给定的一棵二叉树，下面的递归程序count(t)用于求得:二叉树t中具有非空的左,右两个儿子 的结点个数N2;只有非空左儿子的个数NL;只有非空右儿子的结点个数NR和叶子结点个数N0。N2、NL、NR、N0都是全局量，且在调用count(t)之前都置为0. typedef struct node {int data; struct node *lchild,*rchild;}node; int N2,NL,NR,N0; void count(node *t) {if (t->lchild!=NULL) if (1)___ N2++; else NL++; else if (2)___ NR++; else (3)__ ; if(t->lchild!=NULL)(4)____; if (t->rchild!=NULL) (5)____; } /*call form :if(t!=NULL) count(t);*/ (1)t->rchild!=null (2)t->rchild!=null (3)N0++ (4)count(t->lchild) (5)count(t->rchild) 18、利用筛选法将关键字序列(37，66，48，29，31，75)建成的大根堆为(____ ____)。 75, 66, 48, 29, 31, 37 19、对长度为20的有序表进行二分查找的判定树的高度为________。 5 20、阅读下列程序说明和程序，填充程序中的______ 【程序说明】本程序完成将二叉树中左、右孩子交换的操作。交换的结果如下所示（编者略）。 本程序采用非递归的方法，设立一个堆栈stack存放还没有转换过的结点，它的栈顶指针为tp。交换左、右子树的算法为： （1）把根结点放入堆栈。 （2）当堆栈不空时，取出栈顶元素，交换它的左、右子树，并把它的左、右子树分别入栈。 （3）重复（2）直到堆栈为空时为止。 typedef struct node *tree; struct node{int data; tree lchild,rchild;} exchange(tree t) {tree r,p; tree stack [500]; int tp=0; (1)_______ while (tp>=0) {(2)_______ if((3)_______) {r=p->lchild; p->lchild=p->rchild; p->rchild=r stack[(4)_______]=p->lchild; stack[++tp]=p->rchild; } }} (1)stack[tp]=t (2) p=stack[tp--] (3)p (4)++tp 21、排序(sorting)有哪几种方法_______________，_____________，____________，_____________，____________。 直接插入排序，冒泡排序，快速排序，希尔排序，归并排序，基数排序，堆排序等 22、下面程序段的时间复杂度为______________。（用O估计） FOR i:=1 TO n DO FOR j:=i TO n DO s=s+j; O（n*n） 23、非线性结构包括______________和_________________。 树，图 24、判断带头结点的双向循环链表L是否对称相等的算法如下所示，请在划线处填上正确的语句 FUNCTION equal(l:pointer) :boolean; VAR p,q:pointer; result: Boolean; BEGIN result =true ; p:= l^.link; q:=l^.pre ; WHILE (p<>q) AND ((1)_______)DO IF p^.data=q^.data THEN BEGIN (2)___; (3)____; END； ELSE result=false ; return(result); END; (1)result; (2)p:=p^.link; (3) q:=q^.pre （（２）（３）顺序可变） 25、用一维数组r[0. .m-1]表示顺序存储的循环队列，设队头和队尾指针分别是front 和rear，且队头指针所指的单元闲置，则队满的条件是______________________________，队空的条件是_____________________________。 Front=rear, rear+1=front 26、下面表达式树所对应的表达式的前缀表达式是_____________________________，后缀表达式是____________________________。 +*a-bc/de , abc-*de/+ 27、已知中序遍历bt所指二叉树算法如下，s为存储二叉树结点指针的工作栈，请在划线处填入一条所缺语句。 PROC inorder (bt:bitreptr); inistack(s); (1)_______; WHILE NOT empty(s) DO [WHILE gettop(s)<>NIL DO push(s,gettop(s)↑.lchild); (2)_______; IF NOT empty(s) THEN [visit (gettop(s)^); p:=pop(s); (3)_______ ] ] ENDP;{inorder} (1)push(s,bt) （2）pop(s) （3）push(s,p^.rchild) // p的右子树进栈 28．对有向图进行拓扑排序，若拓扑排序不成功，则说明该图_________________。下面有向图的一个拓扑有序序列是______________________________。 存在回路，123456798 29、由二叉树的前序遍历和中序遍历序列能确定唯一的一棵二叉树，下面程序的作用是实现由已知某二叉 树的前序遍历和中序遍历序列，生成一棵用二叉链表表示的二叉树并打印出后序遍历序列，请写出程序所缺的语句。 #define MAX 100 typedef struct Node {char info; struct Node *llink, *rlink; }TNODE; char pred[MAX],inod[MAX]; main(int argc,int **argv) { TNODE *root; if(argc<3) exit 0; strcpy(pred,argv[1]); strcpy(inod,argv[2]); root=restore(pred,inod,strlen(pred)); postorder(root); } TNODE *restore(char *ppos,char *ipos,int n) { TNODE *ptr； char *rpos; int k; if(n<=0) return NULL; ptr->info=(1)_______; for((2)_______ ; rpos ptr->llink=restore(ppos+1, (4)_______,k ); ptr->rlink=restore ((5)_______+k,rpos+1,n-1-k); return ptr; } postorder(TNODE*ptr) { if(ptr=NULL) return; postorder(ptr->llink); postorder(ptr->rlink); printf(“%c”,ptr->info); } (1)*ppos // 根结点 （2）rpos=ipos (3)rpos–ipos (4)ipos (5)ppos+1 三 简答题 1、名词解释：（1）抽象数据类型；（2）算法的时间复杂性； 2、堆与二元查找树的区别? 3、(判断题) 非空的二叉树一定满足：某结点若有左孩子，则其中序前驱一定没有右孩子. Yxm:正确 深度为k具有n个结点的完全二叉树，其编号最小的结点序号为 ?2?+1。Yxm:错误 在中序线索二叉树中，每一非空的线索均指向其祖先结点。Yxm:正确 当一棵具有n个叶子结点的二叉树的WPL值为最小时，称其树为Huffman树，且其二叉树的形状必是唯一的。Yxm：错误 用邻接矩阵存储一个图时，在不考虑压缩存储的情况下，所占用的存储空间大小与图中结点个数有关，而 k-2 （3）散列法(hashing)；（4）索引文件。 与图的边数无关。Yxm:正确 广度遍历生成树描述了从起点到各顶点的最短路径。Yxm：错误 连通图上各边权值均不相同，则该图的最小生成树是唯一的。Yxm:正确 一个有向图的邻接表和逆邻接表中结点的个数可能不等。Yxm：错误 4、如下所示的是一个带权无向图，带框的数字表示相应边的权，不带框的数字表示顶点号。用prime 算法求最小生成树时，如果已确定的边为(5,4),则，下一条边应在哪几条边中选取？选取哪一条？ 1 7 2 5 3 8 6 4 4 5 1 3 5 2 4 3 yxh：（4,6） 5、如何衡量hash函数的优劣？简要叙述hash表技术中的冲突概念，并指出三种解决冲突的方法。 评价哈希函数优劣的因素有：能否将关键字均匀影射到哈希空间上，有无好的解决冲突的方法，计算哈希函数是否简单高效。由于哈希函数是压缩映像，冲突难以避免。 散列表存储中解决碰撞的基本方法： ① 开放定址法 形成地址序列的公式是：Hi=（H（key）+di）% m，其中m是表长，di是增量。根据di取法不同，又分为三种： a．di =1，2，?，m-1 称为线性探测再散列，其特点是逐个探测表空间，只要散列表中有空闲空间，就可解决碰撞，缺点是容易造成“聚集”，即不是同义词的关键字争夺同一散列地址。 b．di =1，-1，2，-2，? ，?k（k≤m/2） 称为二次探测再散列，它减少了聚集，但不容易探测到全部表空间，只有当表长为形如4j+3（j为整数）的素数时才有可能。 c．di =伪随机数序列，称为随机探测再散列。 ② 再散列法 Hi=RHi（key） i=1，2，?，k，是不同的散列函数，即在同义词产生碰撞时，用另一散列函数计算散列地址，直到解决碰撞。该方法不易产生“聚集”，但增加了计算时间。 ③ 链地址法 将关键字为同义词的记录存储在同一链表中，散列表地址区间用H[0..m-1]表示，分量初始值为空指针。凡散列地址为i（0≤i≤m-1）的记录均插在以H[i]为头指针的链表中。这种解决方法中数据元素个数不受表长限制，插入和删除操作方便，但增加了指针的空间开销。这种散列表常称为开散列表，而①中的散列表称闭散列表，含义是元素个数受表长限制。 ④ 建立公共溢出区 设H[0..m-1]为基本表，凡关键字为同义词的记录，都填入溢出区 O[0..m-1]。 2 2 2 2 2 6、有一棵哈夫曼树共有5 个叶子结点其权值分别为0.1,0.25,0.08,0.21,0.9,试画出该哈夫曼树。假设该叶子分别表示a,b,c,d,e，分别给出五个叶子对应的哈夫曼编码。 yxh：a(1110),b(10),c(1111),d(110)，e(0) 7、采用哈希函数Ｈ（k）=3*k mod 13并用线性探测开放地址法处理冲突，在数列地址空间［0..12］中对关键字序列22,41,53,46,30,13,1,67,51 （1）构造哈希表（画示意图）；（2）装填因子；等概率下（3）成功的和（4）不成功的平均查找长度。 （1） 散列地址 关键字 比较次数 0 13 1 1 22 1 2 3 53 1 4 1 2 5 6 41 1 7 67 2 8 46 1 9 10 51 1 11 12 30 1 （2）装填因子=9/13=0.7 （3）ASLsucc =11/9 （4）ASLunsucc =29/13 8、已知一个图如下，试画出其逆邻接链表。 1 2 3 4 9、若一个栈的输入序列是1,2,3??，n, 其输出序列为p1,p2,??pn, 若 p1=n，则pi为多少？ yxh：i=n-i+1 10、非空的二叉树的中根遍历序列中，根的右子树的所有结点都在根结点的后边，这说法对吗？ 11、已知二叉树的中根遍历序列为abc，试画出该二叉树的所有可能的形态。 12、已知一个图如图所示，如从顶点a出发进行按深度优先遍历，可否得到序列acebdf ?为什么？若按广度优先遍历，能否得到序列abedfc?为什么？ a c b e f d 13、栈的存储方式有哪两种？ 14、对于单链表、单循环链表和双向链表，如果仅仅知道一个指向链表中某结点的指针p，能否将p所指结点的数据元素与其确实存在的直接前驱交换?请对每一种链表作出判断，若可以，写出程序段；否则说明理由。其中： 单链表和单循环链表的结点结构为 双向链表的结点结构为 15、假设通信电文使用的字符集为{a,b,c,d,e,f,g}，字符的哈夫曼编码依次为：0110，10，110，111，00，0111和010。 (1)请根据哈夫曼编码画出此哈夫曼树，并在叶子结点中标注相应字符； (2)若这些字符在电文中出现的频度分别为：3，35，13，15，20，5和9，求该哈夫曼树的带权路径长度。 16、试为下列关键字设计哈希表，要求所设计的表在查找成功时的平均查找长度不超过2.0。并请验证你造 设用线性探测再散列解决冲突，根据公式Snl≈（1+1/（1-α）） /2 。可求出负载因子为α=0.67。再根据数据个数和装载因子，可求出表长m=15/0.67，取m=23。设哈希函数H（key）=（关键字首尾字母在字母表中序号之和）MOD 23。 从上表求出查找成功时的平均查找长度为ASLsucc=19/15<2.0，满足要求。 17、用链表表示的数据的简单选择排序，结点的域为数据域data ，指针域 next ；链表首指针为head ，链表无头结点。 selectsort(head) p=head; while (p(1)_______) {q=p; r=(2)_______ while((3)______ ) {if ((4)_______ ) q=r; r=(5)_______ ; } tmp=q->data; q->data=p->data; p->data=tmp; p= (6)_______ ; } 题中p指向无序区第一个记录，q指向最小值结点，一趟排序结束，p和q所指结点值交换，同时向后移p指针。(1)!=null (2)p->next (3)r!=null (4)r->data 18、设某二叉树的前序遍历序列为：ABCDEFGHI，中序遍历序列为：BCAEDGHFI。（1）试画出该二叉树；（2）画出该二叉树后序线索化图。（3）试画出该二叉树对应的森林。 19、 一棵二叉排序树结构如下,各结点的值从小到大依次为1-9，请标出各结点的值。 的 哈 希 表 的 实 际 平 均 查 找 长 度 是 否 满 足 要 求 。 （CHA,CAI,LAN,WEN,LONG,ZHAO,WU,LIU,CHEN,LI,WANG,CAO,YUN,CHANG,YANG） date next prior date next 20、下面的排序算法的思想是：第一趟比较将最小的元素放在r[1]中，最大的元素放在r[n]中，第二趟比较将次小的放在r[2]中，将次大的放在r[n-1]中，?,依次下去，直到待排序列为递增序。（注：<-->）代表两个变量的数据交换）。 void sort(SqList &r,int n) { i=1; while((1)__) { min=max=1; for (j=i+1;(2)____ ;++j) {if((3)____) min=j; else if(r[j].key>r[max].key) max=j; } if((4)_____) r[min] < ---- >r[j]; if(max!=n-i+1){if ((5)___) r[min] < ---- > r[n-i+1]; else ((6)__); } i++; } }//sort (1)i 堆是一种有用的数据结构. 堆排序是一种_(1)_排序，堆实质上是一棵_(2)_结点的层次序列。对含有N个元素的序列进行排序时，堆排序的时间复杂度是_(3)_，所需的附加存储结点是_(4)_。关键码序列05，23，16，68，94，72，71，73是否满足堆的性质_(5)_。 (1) 选择 (2)完全二叉树 (3)O(Nlog2N) (4)O(1) (5)满足堆的性质 22、在堆排序、快速排序和合并排序中： (1)．若只从存储空间考虑，则应首先选取哪种排序方法，其次选取哪种排序方法，最后选取哪种排序方法？ (2)．若只从排序结果的稳定性考虑，则应选取哪种排序方法？ (3)．若只从平均情况下排序最快考虑，则应选取哪种排序方法？ (4)．若只从最坏情况下排序最快并且要节省内存考虑，则应选取哪种排序方法？ (1)堆排序，快速排序，归并排序 (2)归并排序 (3)快速排序 (4)堆排序 23、 算法模拟 设待排序的记录共7个，排序码分别为8，3，2，5，9，1，6。 (1) 用直接插入排序。试以排序码序列的变化描述形式说明排序全过程（动态过程）要求按递减顺序排序。 (2) 用直接选择排序。试以排序码序列的变化描述形式说明排序全过程（动态过程）要求按递减顺序排序。 (3) 直接插入排序算法和直接选择排序算法的稳定性如何？ (1)直接插入排序 第一趟 第四趟 第一趟 第四趟 四 算法阅读 (3)[8,3],2,5,9,1,6 第二趟 (2)[8,3,2],5,9,1,6 第三趟 (5)[8,5,3,2],9,1,6 (9)[9,8,5,3,2],1,6 第五趟 (1)[9,8,5,3,2,1],6 第六趟 (6)[9,8,6,5,3,2,1] (9)[9],3,2,5,8,1,6 第二趟 (8)[9,8],2,5,3,1,6 第三趟 (6)[9,8,6],5,3,1,2 (5)[9,8,6,5],3,1,2 第五趟 (3)[9,8,6,5,3],1,2 第六趟 (2)[9,8,6,5,3,2],1 (2)直接选择排序（第六趟后仅剩一个元素，是最小的，直接选择排序结束） (3)直接插入排序是稳定排序，直接选择排序是不稳定排序。 1、void AE(Stack& S){ InitStack(S); Push(S,3); Push(S,4); int x=Pop(S)+2*Pop(S); Push(S,x); int i,a[5]={1,5,8,12,15}; for(i=0;i<5;i++) Push(S,2*a[i]); while(!StackEmpty(S)) print(Pop(S)); } 该算法被调用后得到的输出结果为： 2、 void ABC (BTNode *BT,int &c1,int &c2) { if (BT !=NULL ) { ABC(BT->left,c1,c2); c1++; if (BT->left==NULL&&BT->right==NULL) c2++; ABC(BT->right,c1,c2); }//if } 该函数执行的功能是什么？ 3、在下面的每个程序段中，假定线性表La的类型为List，e的类型为ElemType,元素类型ElemType为int， 并假定每个程序段是连续执行的。试写出每个程序段执行后所得到的线性表La。 （1）InitList(La); Int a[]={100,26,57,34,79}; For (i=0;i<5;i++) ListInsert(La,1,a[i]); （2）ListDelete(La,1,e); ListInsert(La,ListLength(La)+1,e); （3）ClearList(La); For (i=0;i<5;i++) ListInsert(La,i+1,a[i]); 4、int Prime(int n) { int i=1; int x=(int) sqrt(n); while (++i<=x) if (n%i==0) break; if (i>x) return 1; else return 0; } (1)指出该算法的功能； (2)该算法的时间复杂度是多少？ 5. 写出下述算法A的功能： 其中BiTree定义如下: Typedef struct BiTNode{ TElemType data; struct BiTNode *LChild, *RChild; }BiTNode, *BiTree; Status A(BiTree T) { Queue Q; InitQueue(Q); ENQueue(Q,T); While(not QueueEmpty(Q)) { DeQueue(Q,e); If(e==NULL) break; Else { Print(e.data); ENQueue(Q,e.LChild); ENQueue(Q.e.RChild); } } } 6.阅读下列函数algo,并回答问题： (1)假设队列q中的元素为(2,4,5,7,8),其中“2”为队头元素。写出执行函数调用algo(&q)后的队列q； (2)简述算法algo的功能。 void algo(Queue *Q) { Stack S; InitStack(&S); while (!QueueEmpty(Q)) Push(&S, DeQueue(Q)); while (! StackEmpty(&S)) ＥnQueue(Q,Pop(&S)); } yxh：(1)q中的元素为(8,7,5,4,2); (2)把队列q中的元素倒序。 五 算法填空 1、下面是在带表头结点的循环链表表示的队列上，进行出队操作，并将出队元素的值保留在x中的函数，其中rear是指向队尾结点的指针。请在横线空白处填上适当的语句。 typedef struct node { int data; struct node *next; } lklist; void del( lklist rear, int &x); { lklist p,q; q=rear-> next; //q为头结点 if (__q->next==q ________) //rear-> next== rear printf( “it is empty!\\n” ); else { p=q->next; x=p->data; ___q->next=p->next______________ ; //删除首元结点 if (_q->next==q__________) rear=q; //空，或rear== p free(p) ; }; }; 2、堆分配存储方式下，串连接函数。 typedef struct { char * ch； int len； } HString； HString *s， t; Status StrCat(s， t) /* 将串t连接在串s的后面 */ { int i; char *temp; f if (temp==NULL) return(0); for (i=0; ;i++) temp［i］=s->ch［i］; for ( ;i fr s->ch=temp; return(1); } 3、向单链表的末尾添加一个元素的算法。 LNode是一个包含（data，Next）的结构体 Void InsertRear(LNode*& HL,const ElemType& item) { LNode* newptr; newptr=new LNode; If (______________________) { cerr<<\exit(1); } ________________________=item; newptr->next=NULL; if (HL==NULL) HL=__________________________; else{ LNode* P=HL; While (P->next!=NULL) ____________________; p->next=newptr; } } 4、L为一个带头结点的循环链表。函数f30的功能是删除L中数据域data的值大于c的所有结点，并由这些结点组建成一个新的带头结点的循环链表，其头指针作为函数的返回值。请在空缺处填入合适的内容，使其成为一个完整的算法。 LinkList f30(LinkList L, int c) { LinkList Lc,p,pre; pre=L; p= (1) ; p=L->next Lc=(LinkList) malloc(sizeof(ListNode)); Lc->next=Lc; while(p!=L) if(p->data>c) { pre->next=p->next; (2) ; p->next=Lc->next Lc->next=p; p=pre->next; } else { pre=p; (3) ; p=p->next } return Lc; } 5、已知图的邻接链表的顶点表结点结构为 边表结点EdgeNode的结构为 下列算法计算有向图G中顶点vi的入度。请在空缺处填入合适的内容，使其成为一个完整的算法。 int FindDegree(ALGraph *G,int i)//ALGraph为图的邻接表类型 { int dgree, j; EdgeNode *p; degree= (1) ; 0 for(j=0;j p=G->adjlist［j］. firstedge; while ( (2) ) p { if( (3) ) p->adjvex==i { degree++; break; } p=p->next; adjvex next vertex firstedge } } return degree; } 六 简单应用题 1、已知一个非空二叉树，其按中根和后根遍历的结果分别为： 中根：C G B A H E D J F I 后根：G B C H E J I F D A 试将这样二叉树构造出来;若已知先根和后根的遍历结果，能否构造这棵二叉树，为什么? (基本方法：先由后根序列确定根结点，再到中序序列中分割该二叉树) 2、对于下图，画出按Kruskal（克鲁斯卡尔）算法和Prim（普里姆）算法构造最小生成树的过程。 3、画出由下面的二叉树转换成的森林。 4、用Floyed（弗洛伊徳）算法求下图每一对顶点之间的最短路径及其长度，将计算过程的中间和最后结果填入下表： A 1 2 3 PATH 1 2 3 5、哈夫曼树在构造时，首先进行初始化存储空间，结果如左下图，当构造完成后，请填写最后状态表，如 A(0) 1 2 3 A(1) 1 2 3 A(2) 1 2 3 A(3) 1 2 3 PATH(0) 1 2 3 PATH(1) 1 2 3 PATH(2) 1 2 3 PATH(3) 1 2 3 右下图。 weight Parent 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 5 29 7 8 14 23 3 11 -- -- -- -- -- -- -- Lchild Rchild 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 weight Parent 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 Lchild Rchild 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 6、考虑右图： (1)从顶点A出发，求它的深度优先生成树(4分) (2)从顶点E出发，求它的广度优先生成树(4分) (3）根据普利姆(Prim) 算法，求它的最小生成树(请画出过程) (设该图用邻接表存储结构存储，顶点的邻接点按顶点编号升序排列)(6分) 答案如下： 七 编写算法题 1、设计函数，求一个单链表中值为x的结点个数。并将结果放在头结点的data 域中。 void count1(lklist head,int x) 2、假设以双亲表示法作树的存储结构，写出双亲表示的类型说明，并编写求给定的树的深度的算法。（注:已知树中结点数） 由于以双亲表示法作树的存储结构，找结点的双亲容易。因此我们可求出每一结点的层次，取其最大层次就是树有深度。对每一结点，找其双亲，双亲的双亲，直至（根）结点双亲为0为止。 int Depth(Ptree t) //求以双亲表示法为存储结构的树的深度，Ptree的定义参看教材 {int maxdepth=0; for(i=1;i<=t.n;i++) {temp=0; f=i; while(f>0) {temp++; f=t.nodes[f].parent; } // 深度加1,并取新的双亲 if(temp>maxdepth) maxdepth=temp; //最大深度更新 } return(maxdepth);//返回树的深度 } //结束Depth 3、设计建立有向图正邻接矩阵的函数（数据输入格式自定）。 Typedef struct { int data[ maxsize][maxsize]; int dem,e; }sqgraph; sqgraph crt (sqgraph g) { scanf(n,e);g.dem=n; for (i=1;i<=n;i++) for (j=1;j<=n;j++) g.data[i][j]=0; for (i=1;i<=e;i++) { scanf(beg,end); g.data[beg][end]=1; } return g; } 4、设计函数，将不带表头结点的单链表清除。 lklist clear ( lklist head) { while (head) { p=head ; head=head->next ; free(p); } return head; } 5、设计递归函数，求一棵非空的二叉树的深度。 int depth (bitreptr root) { if (!root) return 0; else { dl=depth(root->lc); dr=depth(root->rc); return 1+(dl>dr?dl:dr); } } 6、设线性表A=(a1,a2,a3,?,an)以带头结点的单链表作为存储结构。编写一个函数，删去A中序号为奇数的结点。 7、试编写一个算法，能由大到小遍历一棵二叉树。 void ShowTree ( TreeNode* current ) { if (current == NULL) { return; } ShowTree(current->right); cout << endl << current->data; ShowTree(current->left); } 8、对于二叉树的链接实现,完成非递归的中序遍历过程。 void InOrder(BiTree bt) {BiTree s[],p=bt; //s是元素为二叉树结点指针的栈，容量足够大 int top=0; while(p || top>0) {while(p) {s[++top]=p; bt=p->lchild;} //中序遍历左子树 if(top>0){p=s[top--]; printf(p->data); p=p->rchild;} //退栈，访问，转右子树 } } 9、利用直接插入排序的方法对一组记录按关键字从小到大的顺序排序。 10、给出一棵表示表达式的二叉树，其中运算符和运算对象都用一个字符表示，求该表达式的值。设二叉树用二叉链表表示，表达式中仅包含二元运算，函数operate(a, b, op)可求任何一种二元运算的值，其中参数op表示运算符，a和b分别表示左右两个运算对象。算法中允许直接引用函数operate (函数operate 不必定义)，如果需要还允许引用栈和队列的基本操作。 11、编写算法，将一单链表逆转。要求逆转在原链表上进行，不允许重新构造一个链表（可以申明临时变量、指针）。 该链表带头节点、头节点和数据节点的结构定义如下 typedef struct LNode { ElemType data; Struct LNode* next; }List, LNode; 函数定义：void invert(List & L) 12、编写算法计算给定二叉树中叶结点的个数。 其中树节点定义如下 typedef struct BiTNode{ DataType data; Struct BiTNode *LChild, * RChild; }BiTNode, *BiTree; 函数定义：CountLeaf (BiTree T, int & LeafNum) void CountLeaf (BiTree T, int & LeafNum) { if(T) { if(!T->lchild&&!T->rchild) LeafNum++; else { CountLeaf(T->lchild, LeafNum); CountLeaf(T->rchild, LeafNum); } } } 13、写出二叉树前根遍历的递归算法 已知二叉树结点定义为： struct node{ elemtp data; struct node *lc,*rc; ); Typedef struct node * bitreptr(指向根),*tpointer(指向一般结点); void preorder(bitreptr P) //P指向树根节点 void preorder(bitreptr P) { If(P!=0) { printf(P->data); preorder(P->lc); preorder(P->rc); } } 14、在邻接矩阵存储结构上实现图的基本操作： InsertVex(G,v)//插入顶点 Status Insert_Vex(MGraph &G, char v)//在邻接矩阵表示的图G上插入顶点v { if(G.vexnum+1)>MAX_VERTEX_NUM return INFEASIBLE; G.vexs[++G.vexnum]=v; return OK; }//Insert_Vex 15、已知某哈希表的装载因子小于1，哈希函数H（key）为关键字（标识符）的第一个字母在字母表中的序号，处理冲突的方法为线性探测开放定址法，请编写一个按第一个字母的顺序输出哈希表中所有关键字的算法。 void Print_Hash(HashTable H)//按第一个字母顺序输出Hash表中的所有关键字, void Print_Hash(HashTable H)//按第一个字母顺序输出Hash表中的所有关键字,其中处理冲突采用线性探测开放定址法 { for(i=1;i<=26;i++) for(j=i;H.elem[j].key;j=(j+1)%hashsize[sizeindex]) //线性探测 if(H(H.elem[j].key)==i) printf(\}//Print_Hash int H(char *s)//求Hash函数 { if(s) return s[0]-96; //求关键字第一个字母的字母序号(小写) else return 0; }//H 16、写出二叉树后根遍历的递归算法 已知二叉树结点定义为： struct node{ elemtp data; struct node *lc,*rc; ); Typedef struct node * bitreptr(指向根),*tpointer(指向一般结点); void aftorder(bitreptr P) { If(P!=0) { aftorder(P->lc); aftorder(P->rc); printf(P->data); } } 17、在邻接矩阵存储结构上实现图的基本操作：DeleteArc(G,v.w)//删除边（v,w） Status Delete_Arc(MGraph &G,char v,char w)//在邻接矩阵表示的图G上删除边(v,w) { if((i=LocateVex(G,v))<0) return ERROR; if((j=LocateVex(G,w))<0) return ERROR; if(G.arcs[i][j].adj) { G.arcs[i][j].adj=0; G.arcnum--; } return OK; }//Delete_Arc 18、编写一个函数或过程判定两棵二叉树是否相似，所谓两棵二叉树s和t相似，即是要么它们都 为空或都只有一个结点，要么它们的左右子树都相似。 [题目分析]两棵空二叉树或仅有根结点的二叉树相似；对非空二叉树，可判左右子树是否相似，采用递归算法。 int Similar(BiTree p,q) //判断二叉树p和q是否相似 {if(p==null && q==null) return (1); else if(!p && q || p && !q) return (0); else return(Similar(p->lchild,q->lchild) && Similar(p->rchild,q->rchild)) }//结束Similar 19、在邻接矩阵存储结构上实现图的基本操作：InsertArc(G,v,w)//插入边（v,w） Status Insert_Arc(MGraph &G,char v,char w)//在邻接矩阵表示的图G上插入边(v,w) { if((i=LocateVex(G,v))<0) return ERROR; if((j=LocateVex(G,w))<0) return ERROR; if(i==j) return ERROR; if(!G.arcs[i][j].adj) { } return OK; }//Insert_Arc 20、假设有一个1000*1000的稀疏矩阵，其中1%的元素为非零元素，现要求哈希表作存储结构。试设计一个哈希表并编写相应算法，对给定的行值和列值确定矩阵元素在哈希表上的位置。 Status Locate_Hash(HashTable H,int row,int col,KeyType key,int &k)//根据行列值在Hash表表示的稀疏矩阵中确定元素key的位置k { h=2*(100*(row/10)+col/10); //作者设计的Hash函数 while(H.elem[h].key&&!EQ(H.elem[h].key,key)) h=(h+1) 000; if(EQ(H.elem[h].key,key)) k=h; else k=NULL; }//Locate_Hash 分析:本算法所使用的Hash表长20000,装填因子为50%,Hash函数为行数前两位和列数前两位所组成的四位数再乘以二,用线性探测法处理冲突.当矩阵的元素是随机分布时,查找的时间复杂度为O(1). G.arcs[i][j].adj=1; G.arcnum++;