一、选择题
1. 组成数据的基本单位是( )。
(A) 数据项 (B)数据类型 (C)数据元素 (D)数据变量 2. 线性表的链接实现有利于( )运算。
(A) 插入 (B)读表元 (C)查找 (D)定位 3. 串的逻辑结构与( )的逻辑结构不同。
(A) 线性表 (B)栈 (C)队列 (D)树 4. 二叉树第i（i≥1）层最多有( )个结点。
(A) 2 (B)2i (C) 2 (D) 2-1 5. 设单链表中指针p指向结点A，若要删除A后结点（若存在），则需要修改指针的操 作为( )
(A) p->next = p->next->next (B)p=p->next
(C)p=p->next->next (D)p->next=p
6. 设一数列的输入顺序为1,2,3,4,5,6，通过栈操作不可能排成的输出序列为( ) (A) 3,2,5,6,4,1 (B) 1,5,4,6,2,3
(C) 2,4,3,5,1,6 (D) 4,5,3,6,2,1
7. 设字符串S1=’ABCDEFG’，S2=’PQRST’，则运算S=CONCAT(SUB(S1,2,LENGTH(S2))，SUB(S1,LENGTH(S2),2))的结果为( )
(A) ‘BCQR’ (B) ‘BCDEF’ (C) ’BCDEFG’ (D) ‘BCDEFEF’
8. 有一个10阶的对称矩阵A,采用压缩存储方式，以行序为主存储，a11为第一元素，其存储地址为1，每个元素占1个地址空间，则a85地址为( )
(A)13 (B) 33 (C) 18 (D) 40 9. 如果结点A有3个兄弟，而且B为A的双亲，则B的度为( ) (A) 3 (B) 4 (C) 5 (D) 1 10. 线索化二叉树中某结点D没有左孩子的必要条件是( ) (A) D->Lchild=Null (B) D->ltag=1 (C) D->Rchild=Null (D) D->ltag=0 10. 数据结构是研究数据的( )以及它们之间的相互关系。 (A) 理想结构、物理结构 (B) 理想结构、抽象结构 (C) 物理结构、逻辑结构 (D) 抽象结构、逻辑结构 11. 线性表采用链式存储时，其地址( )。
(A) 必须是连续的 (B) 部分地址必须是连续的
(C) 一定是不连续的 (D) 连续与否均可以
12. 设循环队列Q[1...N-1]的头尾指针为F，R，当插入元素时尾指针R加1，头指针F总是指向队列中第一个元素的前一个位置，则队列中元素计数为( )。
(A) R-F (B) N-(R-F) (C) (R-F+N)%N (D) (F-R+N)%N 13. 完成堆排序的全过程需要( )个记录大小的辅助空间。
i
i-1
i
(A) 1 (B) n (C) nlog2n (D) n2
14. 若给定关键字集合为{20,15,14,18,21,36,40,10}，一趟快速排序结束时，键值的排列为( )
(A) 10,15,14,18,20,36,40,21 (B) 10,15,14,18,20,40,36,21 (C) 10,15,14,20,18,40,36,21 (D) 15,10,14,18,20,36,40,21 15. 有一棵二叉树如图1所示，该树是( )。
5020103095557085图1
(A) 二叉平衡树 (B) 二叉排序树 (C) 堆的形状 (D) 以上都不是
16. 对于含有n个顶点e条边的无向连通图，利用Prim算法生成最小代价生成树其时间复杂度为( ),利用Kruskal的时间复杂度为( )。
(A) O(log2n) (B) O(n) (C) O(ne) (D) O(elog2e) 17. 具有n个顶点的完全有向图的边数为( )。
(A) n(n-1)/2 (B) n(n-1) (C) n (D) n-1
18. 设有100个元素，用二分法查找时，最大比较次数是( )，最小比较次数是( )。 (A) 25 (B) 7 (C) 10 (D) 1 19. 在内部排序中，排序时不稳定的有( )。
(A) 插入排序 (B) 冒泡排序 (C) 快速排序 (D) 归并排序
20. 中序遍历一棵二叉排序树所得的结点访问序列是键值的( )序列。 (A) 递增或递减 (B) 递减 (C) 递增 (D) 无序 21. Substr(‘DATA STRUCTURE’,5,9) = ( )。 (A) ‘STRUCTURE’ (B) ‘DATA’ (C) ‘ASTRUCTUR’ (D) ‘DATA STRUCTURE’ 22. 下列哪种形态不是树( )。
A2
2
2
A
￠
a
BBCD （A） （B） （C） （D） 23. 下列哪种排序需要的附加存储开销最大( )。
(A) 快速排序 (B) 堆排序 (C) 归并排序 (D) 插入排序 24. 对任何一棵树T，设n0,n1,n2,…,nm分别是0,1,2,…,m的结点，则n0=( )。 (A) n1+n2+…+nm
(B) 1+n2+2n3+…+（m-1）nm
(C) n2+2n3+3n4+…+（m-1）nm (D) 2n1+3n2+…+（m+1）nm
V1V2V4 图 1
V3 25. 在图1中，V4的度为( )。
(A) 1 (B) 2 (C) 3 (D) 4 26. n个顶点的无向图的邻接表中结点总数最多有( )个。
(A) 2n (B) n (C) n/2 (D) n(n-1) 27. 设连通图G的顶点数为n，则G的生成树的边数为( )。
(A) n (B) n-1 (C) 2n (D) 2n-1 28. 下列哪种排序需要的附加存储开销最小( )。
(A) 快速排序 (B) 堆排序 (C) 归并排序 (D) 计数排序
29. 若按 ( )列出二叉搜索树中所存储的元素，则恰好是集合中所有元素从小到大的排序。
(A) 先序 (B) 中序 (C) 后序 (D) 按层次 30. 在图1所示的4棵树中，哪一棵是完全二叉树( )。
10405030253515201040355030251520403550101525201035405030251520 30
图1
（A） （B） （C） （D） 31. 下面程序段的时间复杂度为( )。 s=s0;
for(i =1 ;i<=n;i++) {
for(j =n;j>=n-1;j--) { s = s+1;
} }
(A) O(n) (B) O(nlog2n) (C) O(n2) (D) O(n3/2) 32. 采用链结构存储线性表时，其地址( )。
(A) 必须是连续的 （B）连续不连续都可以
（C）部分地址必须是连续的 (D) 必须是不连续的 33. 具有2000个结点的二叉树，其高度至少为( )。
(A) 9 (B) 10 (C) 11 (D) 12 34. 下列程序的时间复杂度为( )。 for(i=0;i for(i=0;i 36. 在一个具有n个结点的单链表中查找其值等于x的结点，在查找成功的情况下，需平均比较( )个元素结点。 (A) n/2 (B) n (C) (n+1)/2 (D) (n-1)/2 37. 串的长度是( )。 (A) 串中不同字符的个数 (B) 串中不同字母的个数 (C) 串中所含字符的个数n(n>0) (D) 串中所含字符的个数n(n≥0) 38. 若有一个栈的输入序列是1,2,3,…,n，输出序列的第一个元素是n，则第i个输出元素是( ) (A) n-i (B) n-i-1 (C) n-i+1 (D) 不确定 39. 设有一个栈，元素的进栈次序A，B，C，D，E，下列( )是不可能的出栈序列。(A) A,B,C,D,E （B）B,C,D,E,A (C) E,A,B,C,D （D）E,D,C,B,A 40. 在一棵度为3的树中，度为3的结点数为2个，度为2的结点数为1个，度为1的结点数为2个，那么度为0的结点数有( )个。 (A) 4 (B) 5 (C) 6 (D) 7 41. 在一个具有n个结点的无向完全图中，包含有( )条边。 (A) n(n-1)/2 (B) n(n-1) (C) n(n+1)/2 (D) n 42. 采用顺序检索的方法检索长度为n的线性表，则检索每个元素的平均比较次数为( )。 (A) n (B) n/2 (C) (n+1)/2 (D) (n-1)/2 2 for(j=0;j 43. 已知一个有序表为（13,18,24,35,47,50,62,83,90,115,134），当二分检索值为90的元素时，需要( )次比较可检索成功。 44. 已知8个元素（34,76,45,18,26,54,92,65），按照依次插入结点的方法生成一棵二叉排序树，该树的深度为( )。 (A) 4 (B) 5 (C) 6 (D) 7 45、如某数据结构的数据元素的集合为S={A,B,C,D,E,F,G},数据元素之间的关系为R={ (A)4 (B)5 (C)6 (D)20 47、在具有N个单元的顺序存储的循环队列中，假定front和rear分别为队头指针和队尾指针，则判断队空的条件为 。 (A)front==rear (B)（rear+1）%MAXSIZE==front (C)front-rear==1 (D)rear%MAXSIZE==front 48、一个5×5的对称矩阵采用压缩存储，需要存储 个元素。 (A)5 (B)10 (C)15 (D)20 49、一个无向连通图有5个顶点、8条边，则其生成树将要去掉 条边。 (A)3 (B)4 (C)5 (D)6 50、设一颗二叉树共有50个叶子结点（终端结点），则共有 个度为2的结点。 (A)25 (B)49 (C)50 (D)51 51、设一棵二叉树共有20个度为2的结点，则叶子结点共有 个。 (A)4 0 (B)19 (C)20 (D)21 52、一个元素进入队列的时间复杂度是 。 (A)O(1) (B) O(n) (C) O(n) (D) O(log2n) 53、设一颗完全二叉树中根结点的编号为1，而且23号结点有左孩子但没有右孩子，则完全二叉树总共有 个结点。 (A)24 (B)45 (C)46 (D)47 54、二叉树的第3层最少有 个结点。 (A)0 (B)1 (C)2 (D)3 55、已知某算法的执行时间为（n+n2）+log2(n+2)，n代表问题规模，则该算法的时间复杂 是 。 (A)O(n) (B)O(n2) (C)O(log2n) (D)O(nlog2n) 56、如果一棵树有10个叶子结点，则该树至少有 个结点。 (A)10 (B)11 (C)19 (D)21 57、设有一个10阶的对称矩阵a，采用压缩存储方式，以行序为主存储，a[0][0]的存储地址 为100，每元素占1个地址空间，则a[3][2]的地址为 。 (A)102 (B)105 (C)106 (D)108 58、总共3层的完全二叉树，其结点数至少有___________个。 (A)3 (B)4 (C)7 (D)8 59、队列操作的原则是_________。 (A)先进先出 (C)只能进行插入 (B)后进先出 (D)只能进行删除 2 60、在有n个结点的二叉链表中，值为非空的链域的个数为_________. (A)n-1 (B)2n-1 (C)n+1 (D)2n+1 61、在具有n个结点且为完全二叉树的二叉排序树中查找一个关键值，其平均比较次数的数 量级为_________。 （A）O(n) (B)O(log2n) (C)O(nlog2n) (D)O(n) 62、下列排序算法中，时间复杂度不受数据初始状态影响，恒为O（log2n）的是_________。 (A)堆排序 (B)冒泡排序 (C)简单选择排序 (D)快速排序 63．快速排序的记录移动次数（ ）比较次数，其总执行时间为O(nlog2n)。 ① 大于 ②大于等于 ③小于等于 ④小于 64．栈操作的原则是（ ） ① 先进先出 ②后进先出 ③栈顶插入 ④栈顶删除 65．设矩阵A是一对称矩阵(aij=aji,1<=i,j<=8)，若每个矩阵元素占3个单元，将其上三角部分（包括对角线）按行序为主序存放在数组B中，B的首地址为1000，则矩阵元素a67的地址为（ ） ① 1031 ②1093 ③1096 ④1032 66、设数组Data[0..m]作为循环队列SQ的存储空间，front为队头指针，rear为队尾指针，则执行出队操作的语句为（ ） ①front=front+1 ②front=(front+1)% m ③rear=(rear+1)%m ④front=(front+1)%(m+1) 67、深度为6（根的层次为1）的二叉树至多有（ ）结点。 i. 64 ②32 ③31 ④63 68、将含100个结点的完全二叉树从根这一层开始，每层上从左到右依次对结点编号，根结点的编号为1。编号为49的结点X的双亲编号为（ ） ①24 ②25 ③23 ④无法确定 69、堆是一个键值序列{k1,k2,…, kn},对i=1,2,…,|_n/2_|,满足( ) ①ki≤k2i≤k2i+1 ②ki 70、线性表采用链式存储时，结点的存储地址 （ ） A.必须是不连续的 B.连续与否均可 C.必须是连续的 D.和头结点的存储地址相连续 71、一个非空广义表的表头 （ ） A．不可能是子表 B. 只能是子表 C.只能是原子 D.可以是子表或原子 72、算法分析的目的是( A )。 A 找出数据结构的合理性 B 研究算法中输入和输出的关系 C 分析算法的效率以求改进 D 分析算法的易懂性和文档性 73、若结点的存储地址与其关键字之间存在的某种映射关系，则称这种存储结构为（ ） A.顺序存储结构 B.链式存储结构 C.索引存储结构 D.散列存储结构 74、 若进栈序列为a，b，c，则通过入出栈操作可能得到的a，b，c的不同排列个数为（ ） A.4 B.5 C.6 D.7 75、.若要在单链表中的结点*p之后插入一个结点*s，则应执行的语句是（ ） A.s-＞next=p-＞next; p-＞next=s; B.p-＞next=s; s-＞next=p-＞next 2 C.p-＞next=s-＞next; s-＞next=p; D.s-＞next=p;p-＞next=s-＞next; 76、.对广义表L=((a,b),c,d)进行操作tail (head (L))的结果是（ ） A.(c,d ) B.(d ) C.b D.(b) 77、在关键字序列（12，23，34，45，56，67，78，89，91）中二分查找关键字为45，89和12的结点时，所需进行的比较次数分别为（ ） A.4，4，3 B.4， 3， 3 C.3，4，4 D.3，3，4 （ ） 78、已给下图，哪一项是该图的拓扑排序？ （ ） 1 2 3 5 4 A．1，2，3，4，5 B．1，3，2，4，5 C．1，2，4，3，5 D．1，2，3，5，4 79、在一个单链表中，已知*q结点是*p结点的前趋结点，若在*q和*p之间插入*s结点，则需执行（ ）。 A．s->next=p->next; p->next=s; B．q->next=s; s->next=p; C．p->next=s->next; s->next=p; D．p->next=s; s->next=q; 80、一棵深度为k的满二叉树有（ ）个结点。 A．2k -1 B．2k-1 C．2k D．2 81、在一个单链表HL中，若要向表头插入一个由指针p指向的结点，则执行 。 A、HL = p; p->next = HL; B、p->next = HL; HL = p; C、p->next = HL; p = HL; D、p->next = HL->next; HL->next = p; 82、在一个单链表HL中，若要删除由指针q所指向结点的后继结点，则执行 。 A、p = q->next ; p->next = q->next; B、p = q->next ; q->next = p; C、p = q->next ; q->next = p->next; D、q->next = q->next->next; q->next = q; 83、栈的插入与删除操作在 进行。 A、栈顶 B、栈底 C、任意位置 D、指定位置 84、在一个循环顺序队列中，队首指针指向队首元素的 位置。 A、前一个 B、后一个 C、当前 D、后面 85、由权值分别为3,8,6,2,5的叶子结点生成一棵哈夫曼树，它的带权路径长度为________。 A、 24 B、 48 C、 72 D、 53 86、当利用大小为N的一维数组顺序存储一个栈时，假定用top=－1表示栈空，则向这个栈插入一个元素时，首先应执行 语句修改top指针。 A．top++； B．top--； C．top=NULL ； D．top； 87、线性表采用链式存储时，其地址 。 A．必须是连续的 B．部分地址必须是连续的 C．一定是不连续的 D．连续与否均可以 88、设有一个广义表为A(a)，其表尾为（ ）。 k A: a B: (( )) C: （） D: (a) 89、与邻接矩阵相比，邻接表更适合于存储 ( )。 A: 无向图 B: 连通图 C: 稀疏图 D: 稠密图 90、带头结点的单链表first为空的判定条件是： 91、在一棵树中，（ ）没有前驱结点。 A. 分支结点 B. 叶结点 C. 树根结点 D. 空结点 92、在有向图中每个顶点的度等于该顶点的（ ）。 A. 入度 B. 出度 C. 入度与出度之和 93、已知一个图如下所示，从顶点a出发进行广度优先遍历可能得到的序列为（） A a c e f b d B a c b d f e C a c b d e f D a c d b f e D. 入度与出度之差 A. first == NULL; B. first->link == NULL; C. first->link == first; D. first != NULL; 94、已知一组关键字为{25，48，36，72，79，82，23，40，16，35}，其中每相邻两个为有序子序列。对这些子序列进行一躺两两归并的结果是（） A {25，36，48，72，23，40，79，82，16，35} B {25，36，48，72，16，23，40，79，82，35} C {25，36，48，72，16，23，35，40，79，82} D {16，23，25，35，36，40，48，72，79，82} 第 1 页（共 5 页） 95、折半查找的时间复杂性为（ ） 2 A. O（n） B. O（n） C. O（nlog n） D. O（log n） 96、按照二叉树的定义，具有3个结点的二叉树有( )种。 A．3 B．4 C．5 D．6 . 97、一个队列的入列序列是１，２，３，４，则队列的输出序列是（ ） A、4,3,2,1 B、1,2,3,4 C、1,4,3,2 D、3,2,1,4 98、按照二叉树的定义，具有3个结点的二叉树有（ ）种 A、3 B、4 C、5 D、6 99.如图所示的有向无环图可以得到的不同拓扑序列的个数为（ ） A.1 B.2 C.3 D.4 100.下列排序方法中，稳定的排序方法为（ ） A.希尔排序 B.堆排序 C.快速排序 D.直接插入排序 101、算法设计中，在生成当前结点的孩子结点时，通过一些限界条件即限界函数，帮助避免生成不包含答案结点子树的状态空间的检索方法是（ ） A、分枝界限法 B、回溯法 C、穷举法 D、递归 102、算法设计中，将问题的候选解按某种顺序逐一枚举和检验，直到候选解满足所有要求的检索方法是（ ） A、分枝界限法 B、回溯法 C、穷举法 D、递归法 103、算法设计中，不重复，不遗漏地比较所有元素，直到找到需要元素为止，该方法称为( ) A、分枝界限法 C、穷举法 B、回溯法 D、递归法 二、填空题 1. 对于一个以顺序实现的循环队列Q[0..m_1]，队头、队尾指针分别为f,r,其判空的条件是 ，判满的条件是 。 2. 循环链表的主要优点是 。 3. 一个n*n的对称矩阵，如果以行或列为主序存入内存，则其容量为 。 4. 具有64个结点的完全二叉树的深度为 。 5. 设有一个空栈，现输入序列为1,2,3,4,5,经过Push,Push,Pop,Push,Pop,Push,Pop,Push后，输出序列为 。 6. 一个具有n个顶点的有向完全图的弧数为 。 7. 设一棵二叉树共用50个叶结点（终端结点），则共有 个度为2的结点 。 8. 高度为h（h0）的二叉树，最少有 个结点，最多有 个结点。 9、已知某算法的执行时间为（n+n）/2+log2(2n+1)，n代表问题规模，则该算法的时间复杂度是 。 10、数据结构有线性结构、树结构、 、 等几种逻辑结构。 11、一个无向连通图有6个顶点7条边，则其生成树有 条边。 12、在一个长度为n的顺序表中插入一个元素，最少需要移动 个元素，最多需要移动 个元素。 13、如果指针p指向一棵二叉树的一个结点，则判断p没有左孩子的逻辑表达式为 。 14、一个5×5的对称矩阵采用压缩存储，需要存储_________个元素。 15、设单链表中指针P指向结点A，若要删除A之后的结点（假设存在），则需要修改指针的操作为____________________。 16、已知二叉树中叶子数为50，仅有一个孩子的结点数为30，则总结点数____________________。 17、图1中v3的入度和出度分别为____________________。 18．在带有头结点的单链表L中，若要删除第一个结点，则需执行下列三条语句：＿＿＿＿＿＿＿＿；L->next=U->next；free(U)； 19．深度为8（根的层次号为1）的满二叉树有＿＿＿＿＿＿个叶子结点。 20．将一棵有100个结点的完全二叉树按层编号，则编号为49的结点X，其双亲PARENT（X）的编号为＿＿＿＿＿＿＿。 21．设有一个链队，结点结构为data|next，front为队头指针，rear为队尾指针，当执行入队操作时需执行下列语句： malloc(p)；p->data=x; p->next=NULL； ＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿； ＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿； 22、设r指向单链表的最后一个结点，要在最后一个结点之后插入s所指的结点，需执行的三条语句是___________；r=s; r->next=null;。 23、已知一棵度为3的树有2个度为1的结点，3个度为2的结点，4个度为3的结点，则该树中有____________ 个叶子的结点。 24、树有三种常用的存储结构，即孩子链表法、孩子兄弟链表法和_________________ . 25．在一个带头结点的单向循环链表中，p指向尾结点的直接前驱，则指向头结点的指针head可用p表示为head＝ 。 26．在有序表（12，24，36，48，60，72，84）中二分查找关键字72时所需进行的关键字比较次数为 。 27. 若一个算法中的语句频度之和为T(n)=3720n+4nlogn，则算法的时间复杂度为 。 28. 假设以S和X分别表示进栈和退栈操作，则对输入序列a,b,c,d,e进行一系列栈操作SSXSXSSXXX之后，得到的输出序列为 。 29. 串S=“I am a worker”的长度是 。 30.在含100个结点的完全二叉树中，叶子结点的个数为 。 31.如果排序过程不改变 之间的相对次序，则称该排序方法是稳定的。 32．算法有五个特征它们是 、 、可行性、输入和输出。 33．栈是限定仅在 进行插入和删除的线性表。 V4V3V1V22 ?134．具有64个结点的完全二叉树的深度为 。 35．数据结构讲述的三大关系是 、 、 。 36．已知二叉树中的叶子树为50，仅有一个孩子的结点数为30，则总结点数为 。 37．队列的原则是 。 38．已知某算法的执行时间为n+n2,n代表问题规模，则该算法的时间复杂度是 。 39．数据结构有线性结构、树结构、 、 等几种逻辑结构。 40．栈的原则是 。 41．顺序存储的队列如果不采用循环方式，则会出现 问题。 42．设一颗完全二叉树共有50个叶子结点，则它共有________个度为2的结点。 43．对于一个顺序栈作进栈运算时，应先判断栈是否为 ，判断的条件是 ，作出栈运算时，应先判断栈是否为 ，判断的条件是 。 44．在一棵二叉树上第5层的结点数最多为 。 45.将指向单链表中的某个结点的指针p移动到该结点的后继结点表示为 。 46. 总共三层的完全二叉树，其结点数至少有 个，至多有 个。 47. 二叉树的遍历方法有 、 、 。 48、链表对于数据元素的插入和删除不需移动结点，只需改变相关结点的________域的值。 49、一棵树的广义表表示为a (b (c, d (e, f), g (h) ), i (j, k (x, y) ) )，结点f的层数为______。假定根结点的层数为0。 50、n (n﹥0) 个顶点的无向图最多有________条边，最少有________条边。 51、在队列中，允许进行插入操作的一端称为 ，允许进行删除操作的一端称为 。 52、设Ｓ１＝”good”,S2=”book”,则Ｓ１，Ｓ２和Ｓ３依次联接后的结果是 。 53、若按层次顺序将一棵有n个结点的完全二叉树的所有结点从1到n编号，那么当2i>n,则结点i无 ；若2i+1>n，则结点i无 。 54、在有序表（12，24，36，48，60，72，84）中二分查找关键字72时所需进行的关键字比较次数为 。 55． 在单链表中设置头结点的作用是_________________________________。 56．设广义表L=（（（a））），则该广义表的长度是 ，深度是 。 57．若一个二叉树含有n个结点，则它的二叉链表中必有 个空的链域。 58、在双链表中，存储一个结点有三个域，一个是数据域；另两个是指针域，分别指向 ___________和_________。 59、在循环列队中，设队头指针front指向队头元素前一个空闲元素，队尾指针指向队尾元素，那么，队空标志为_______________，队满标志为_____________________。 60、设广义表C=( (x,(a,b) ),y ) ), 则C的长度为_____,深度为________ 61、在一棵具有n个结点的完全二叉树中，从树跟起，自上而下、自左而右地给所有结点编号。设跟结点编号为1。若编号为i的结点，有右孩子，那么其右孩子的编号为__________；若编号为i的结点，有父结点，那么其父结点的编号为___________。 62、有一稠密图G，则G采用________存储较省空间。设有一稀疏图G，则采用__________存储较省空间。 63、数据结构的存储结构包括顺序、________、索引和散列等四种。 64、在链表中进行插入和 操作的效率比在顺序存储结构中进行相同操作的效率高。 65、对于队列，只能在＿＿＿插入元素，在＿＿＿删除元素。 66、当线性表很少做插入删除操作时，应采用＿＿＿＿存储结构为好。 67．在二叉树第h层上最多有＿＿＿＿个结点。 68．关键路径的长度是完成整个工程所需要的最______时间。 69、下面树的先序、中序、后续遍历的结果依次为______________、_______________、_________________ 70、 a e 将左边的森林转换为二叉树为 b c f ______________ b a c d e f 71、线性结构中元素之间存在 ______ 关系，树形结构中元素之间存在______关系，图形结构中元素之间存在______关系。 72．带有一个头结点的单链表head为空的条件是 73．不带头结点的单链表head为空的判定条件是 74、设有50行的二维数组A[50][60]，其元素长度为4字节，按行优先顺序存储，基地址为200，则元素A[18][25]的存储地址为 。 75、在算法设计方法中，____________是一种将大问题分解成一些较小问题，然后由小问题的解方便的构造大问题的解的类似于递归思想的算法。在算法设计方法中，____________是一种不断用新值取代旧值，或者由旧值递推出新值的过程的算法 三、应用题 1、假定一个待散列存储的线性表为（32，75，63，48，94，25，36，18，70），散列地址空间为[0,1,…,10],若采用除留余数法构造散列函数和线性探查法处理冲突,试给出它们对应的散列表( H(key)=key MOD 11). 2、有一份电文中共使用五种字符：a,b,c,d,e,它们的出现频率依次为4，7，5，2，9，请画出对应的编码赫夫曼树（请按照左子树根结点的权小于等于右子树根结点的权的次序构造），求出每个字符的赫夫曼编码，并求出该树的带权路径长度 3、对于下图，（1）写出按深度优先搜索结果 （2）写出按广度优先搜索结果 4、对于下图， V2 a4=1 a1=3 V5 V1 a2=5 a5=6 a7=3 V3 a8=3 V6 V7 a3=2 V4 a6=4 （1） 写出关键路径 （2） 写出活动a5的最早开始时间，最晚开始时间 （3） 写出活动a6的最早开始时间，最晚开始时间 V5 V3 V4 V7 V2 v1 V6 5、根据所给有向图，写出一个拓扑序列。 3 2 5 7 6、求出从v0到其它顶点的最短路径 80 V2 120 V3 V0 30 10 20 V1 20 V4 1 4 6 7、将给定的图简化为最小的生成树，要求从顶点1出发。 1 5 8 3 3 15 2 10 12 6 6 9 4 2 7 7 5 8、已知有五个待排序的记录，其关键字分别为：256，301，751，129，937,863，742，694，076，438请用以下排序的方法将它们从小到大排列 （1）快速排序； （2）堆排序。 9、依次读入给定的整数序列{7，16，4，8，20，9，6，18，5}，构造一棵二叉排序树。 10、对于下图，请画出相应的邻接矩阵和邻接表，并求出最小生成树（用prim算法和kruskal算法中的任一种）。画出从A 到其它顶点的最短路径并给出相应的路径长度。 D20123EC81510FB511G1图3A 四、算法设计题 1、单链表的操作（增加、删除、查找等） 2、二叉树的操作（建立、求高度、求结点个数、求叶子结点个数、输出等） 因篇幅问题不能全部显示，请点此查看更多更全内容