选择题
1、若入栈序列的元素顺序为A、B、C、D、E，判断下列哪一个出栈序列是不可能的。（ ）
A．A、B、C、D、E B. B、C、D、E、A C．E、A、B、C、D D. D、C、B、A、E
2、某程序的时间复杂度为（3n+nlog2n+n2+8）, 其数量级表示为（ ）。
A．O（n） B．O（nlog2n） C．O（n2） D．O（log2n）
3、一个循环队列的队首和队尾指针分别是front和rear,则判别队空的条件是（ ）
A．front+1==rear
C．front==0
B．front==rear+1 D．front==rear
4、一个非空广义表的表头（ ）
A．不可能是子表 B．只能是子表 C．只能是原子 D.可以是子表或原子 5、一个有顺序表有255个对象，采用顺序搜索法查表，平均搜索长度为（ ）
A 128 B 127 C 126 D 255
6、设有一个含200个表项的散列表，用线性探查法解决冲突，按关键码查询时找到一个表项的平均探查次数不超过1.5，则散列存储空间应能够至少容纳（ ）个表项。（搜索成功的平均搜索长度为Snl=(1+1/(1-a))/2,其中a为装填因子
A 400 B 526 C 624 D 676
7、在一棵度为3的树中，度为3的结点个数为2，度为2的结点个数为1，则度为0的结点个数为 ( )。
A. 4 B. 5 C. 6 D. 7 8．以下哪个数据结构不是多型数据类型（ ）
A．栈 B．广义表 C．有向图 D．字符串 9．以下数据结构中，（ ）是非线性数据结构
A．树 B．字符串 C．队 D．栈 10. 下列数据中，（ ）是非线性数据结构。
A．栈 B. 队列 C. 完全二叉树 D. 堆 11．连续存储设计时，存储单元的地址（ ）。
A．一定连续 B．一定不连续 C．不一定连续 D．部分连续，部分不连续 12．对稀疏矩阵进行压缩存储目的是（ ）。
A．便于进行矩阵运算 B．便于输入和输出 C．节省存储空间 D．降低运算的时间复杂度 13．以下属于逻辑结构的是（ ）。
A．顺序表 B. 哈希表 C.有序表 D. 单链表
14．从一棵B_树删除元素的过程中，若最终引起树根结点的合并，则新树高度是（ ）。
A．原树高度加1 B．原树高度减1 C．原树高度 D．不确定
15．在一个具有n个顶点的无向图中，要连通所有顶点则至少需要（ ）条边。
A．n B．2n C．n-1 D．n+1
16．在某线性表中最常用的操作是在最后一个元素之后插入一个元素和删除第一个元素，则
采用( )存储方式最节省运算时间。
A 单链表 B、仅有头指针的单循环链表C、双链表 D、仅有尾指针的单循环链表 17．下列4种排序方法中，不稳定的方法是（ ）。
A．直接插入排序 B．冒泡排序 C．归并排序 D．直接选择排序 18．串是一种特殊的线性表，其特殊性体现在（ ）
A.可以顺序存储 B.数据元素是一个字符 C.可以链接存储 D.数据元素可以是多个字符 19．在一个图中，所有顶点的度数之和等于所有边数的（ ）倍。
A.1/2 B.1 C.2 D.4
20．有一个有序表为{1，3，9，12，32，41，45，62，75，77，82，95，100}，当二分查找
值为82的结点时，（ ）次比较后查找成功。
A.1 B.2 C.4 D.8 21．一棵左右子树不空的二叉树在先序线索化后，其空指针域数为（ ）。
A.0 B.1 C.2 D.不确定
22．在下列排序算法中，在待排序的数据表已经为有序时，花费时间反而最多的是（ ）。
A.快速排序 B.希尔排序 C.冒泡排序 D.堆排序 23．向顺序栈中压入新元素时，应当（ ）。
A．先移动栈顶指针，再存入元素 B．先存入元素，再移动栈顶指针 C．先后次序无关紧要 D．同时进行 24．在线索二叉树中，下面说法不正确的是( )
A. 在中序线索树中，若某结点有右孩子，则其后继结点是它的右子树的左支末端结点。 B.线索二叉树是利用二叉树的n+1 个空指针来存放结点前驱和后继信息的。 C.每个结点通过线索都可以直接找到它的前驱和后继
D.在中序线索树中，若某结点有左孩子，则其前驱结点是它的左子树的右支末端结点。 25．广义表A=(a,b,(c,d),(e,(f,g))),则下面式子的值为（ ）。Head(Tail(Head(Tail(Tail(A)))))
A. (g) B. (d) C. c D. d
26．有三个数字1,2,3,将它们构成二叉树，中序遍历序列为1,2,3的不同二叉树有( )种。
A. 5 B. 6 C. 7 D.8 27．一个算法应该是（ ）。
A．程序 B．问题求解步骤的描述 C．要满足五个基本特性 D．A和C. 28. 下面关于算法说法错误的是（ ）
A．算法最终必须由计算机程序实现
B.为解决某问题的算法同为该问题编写的程序含义是相同的 C. 算法的可行性是指指令不能有二义性 D. 以上几个都是错误的 29. 下面说法错误的是（ ）
(1）算法原地工作的含义是指不需要任何额外的辅助空间
（2）在相同的规模n下，复杂度O(n)的算法在时间上总是优于复杂度O(2n)的算法 （3）所谓时间复杂度是指最坏情况下，估算算法执行时间的一个上界 （4）同一个算法，实现语言的级别越高，执行效率就越低
A．(1) B.(1),(2) C.(1),(4) D.(3)
30．从逻辑上可以把数据结构分为（ ）两大类。
A．动态结构、静态结构 B．顺序结构、链式结构 C．线性结构、非线性结构 D．初等结构、构造型结构 31．以下与数据的存储结构无关的术语是（ ）。
A．循环队列 B. 链表 C. 哈希表 D. 栈 32．以下数据结构中，哪一个是线性结构（ ）？
A．广义表 B. 二叉树 C. 稀疏矩阵 D. 串 33．以下那一个术语与数据的存储结构无关？（ ）
A．栈 B. 哈希表 C. 线索树 D. 双向链表 34．一棵左右子树不空的二叉树在先序线索化后，其空指针域数为（ ）。
A .0 B. 1 C. 2 D 不确定 35．在一棵二叉树中，第4层上的结点数最多为（ ）。
A．31 B．8 C．15 D．16 36．向堆中插入一个元素的时间复杂度为（ ）。
A．O(log2n) B．O(n) C．O(1) D．O(nlog2n)
37．广义表L=（a，（b，c）），进行Tail（L）操作后的结果为（ ）。
A. c B. b，c C.（b，c） D.（（b，c）） 38．一棵完全二叉树上有1001个结点，其中叶子结点的个数是（ ）
A．250 B、500 C．254
D、501
39．计算机算法必具备输入、输出和( ) 等五个特性
A. 可行性、可移植性和可扩充性 B. 可行性、确定性和有穷性 C. 确定性、有穷性和稳定性 D.易读性、稳定性和安全性
40. 下面的叙述不正确的是（ ）
A．线性表在链式存储时，查找第i个元素的时间同i的值成正比 B. 线性表在链式存储时，查找第i个元素的时间同i的值无关 C. 线性表在顺序存储时，查找第i个元素的时间同i 的值成正比 D. 线性表在顺序存储时，查找第i个元素的时间同i的值无关
41．在长度为n的顺序表的第i(1≤i≤n+1)个位置上插入一个元素，元素的移动次数为( ) A n-i+1 B.n-i C.i D.i-1
42．对于只在表的首、尾两端进行插入操作的线性表，宜采用的存储结构为( )
A. 顺序表 B.用头指针表示的单循环链表 C.用尾指针表示的单循环链表 D.单链表
43．若一个具有N个顶点，K条边的无向图是一个森林(N>K)，则该森林中必有( )棵树。 A. K B. N C .N-K D.1
44．若已知一个栈的入栈序列是1，2，3，....，n，其输出序列为p1,p2,p3,?pn,若p1是n，则pi是 ( )
A. i B. n-i C. n-i+1 D. 不确定 45．表达式a*(b+c)-d的后缀表达式是( )
A.abcd*+- B.abc+*d- C .abc*+d- D.-+*abcd 46．在倒排文件中，通常包含有 ( ) 倒排表。
A. 一个 B.多个 C.两个 D.一个或两个
47．二维数组M[i,j]的元素占三个字节，行下标i的范围从0到4，列下标j的范围从0到5，M按行存储时元素M[3，5]的起始地址与M按列存储时元素( ) 的起始地址相同。
A、 M[2,4] B、M[3,4] C、M[3,5] D、M[4,4]
48．在一个单链表HL中，若要在指针q所指结点的后面插入一个由指针p所指向的结点，则执行（ ）。
A. q->next=p->next;p->next=q; B. p->next=q->next;q=p; C. q->next=p->next;p->next=q; D. p->next=q->next;q->next=p; 49．非空的循环链表head的尾结点*p满足（ ）
A. p->next =NULL B. p=NULL C. p->next=head D. p=head
50．若要尽可能快地完成对实数数组的排序，且要求排序是稳定的，则应选（ ）
A 快速排序 B 堆排序 C 归并排序 D 基数排序。 51．二叉树在线索化后，仍不能有效求解的问题是（ ）。
A.先序线索二叉树中求先序后继 B. 中序线索二叉树中求中序后继 C.中序线索二叉树中求中序前驱 D. 后序线索二叉树中求后序后继
52．在平衡二叉树中插入一个结点后造成了不平衡，设最低的不平衡点为A，并已知A的
左孩子的平衡因子为-1，右孩子的平衡因子为0，则做（ ）型调整以使其平衡。
A.LL B.LR C.RL D.RR
53．对有18个元素的有序表做折半查找，则查找A[3]的比较序列的下标依次（ ）。
A.1-2-3 B.9-5-2-3 C.9-5-3 D. 9-4-2-3 54．计算机算法指的是（ ）
A．计算方法 B．.排序方法 C．解决问题的有限运算序列 D．调度方法
55．设森林F中有三棵树，第一，第二，第三棵树的结点个数分别为M1，M2和M3。与森林F对应的二叉树根结点的右子树上的结点个数是（ ）。
A．M1 B．M1+M2 C．M3 D．M2+M3 56．以下叙述正确的是（ ）
A． 线性表的线性存储结构优于链表存储结构 B． 二维数组是其数据元素为线性表的线性表 C． 栈的操作方式是先进先出 D． 队列的操作方式是先进后出
57．一个顺序存储的线性表的第一个元素的存储地址是100，每个元素的长度是2，则第5个元素的地址是（ ）
A． 100 B． 108 C． 110 D． 120 58．判定一个栈ST（最多元素为m）为空的条件是（ ）
A． ST->top <> 0 B．ST->top = 0 C． ST->top <> m D． ST->top = m 59．静态链表中指针表示的是（ ）.
A． 内存地址 B．数组下标 C．下一元素地址 D．左、右孩子地址 60．.已知某二叉树的后序遍历序列是dabec，中序遍历序列是debac，它的前序遍历序列是（ ）
A．acbed B．decab C．deabc D．cedba 61．有n个叶子的哈夫曼树的结点总数为（ ）。
A．不确定 B．2n C．2n+1 D．2n-1 62．在一非空二叉树的中序遍历序列中，根结点的右边（ ）
A．只有右子树上的所有结点 B．只有右子树上的部分结点 C．只有左子树上的部分结点 D．只有左子树上的所有结点
63．对于一个具有n个顶点的无向图，若采用邻接矩阵表示，则该矩阵的大小是（ ）
A．n B．（n－1）2 C．n－1 D．n2 64.下面的叙述中，不正确的是( )
A．关键活动不按期完成就会影响整个工程的完成时间 B．任何一个关键活动提前完成，将使整个工程提前完成 C．所有关键活动若提前完成，则整个工程将提前完成 D．某些关键活动若提前完成，将使整个工程提前完成 65.二叉树上叶结点数等于（ ）。
A．分支结点数加1 B．单分支结点数加1 C．双分支结点数加1 D．双分支结点数减1
66．若二叉树采用二叉链表存储结构，要交换其所有分支结点左、右子树的位置，利用( )遍历方法最合适。
A．前序 B．中序 C．后序 D．按层次
67.每次从无序表中取出一个元素，把它插入到有序表中的适当位置，此种排序方法叫做（ ）排序
A．插入 B．交换 C．选择 D．归并
68.设循环队列中数组的下标范围是1~n，其头尾指针分别为f和r，则其元素个数为（ ）。
A．r-f B．r-f+1 C．(r-f) mod n +1 D．(r-f+n) mod n 69.二叉树在线索化后，仍不能有效求解的问题是（ ）。
A．先序线索二叉树中求先序后继 B． 中序线索二叉树中求中序后继 C．中序线索二叉树中求中序前驱 D． 后序线索二叉树中求后序后继 70下面说法正确的为（ ）
（1）二叉树按某种方式线索化后，任一结点均有指向前驱和后继的线索 （2）二叉树的前序遍列序列中，任意一个结点均处在子孙结点前 （3）二叉排序树中任一结点的值大于其左孩子的值，小于右孩子的值 A．（1）（2）（3） B．（1）（2）
C．（1）（3） D．前面的可选答案都不对 71下面的说法中正确的是（ ）
(1) 任何一棵二叉树的叶结点在三种遍历中的相对次序不变; (2) 按二叉树定义,具有三个结点的二叉树共有6种;
A．(1),(2) B．(1) C．(2) D．(1),(2)都错
72.一棵二叉树高度为h,所有结点的度或为0,或为2,则这棵二叉树最少有（ ）个结点 A． 2h B．2h-1 C．2h+1 D．h+1
73．下列排序算法中，在待排序数据已有序时，花费时间反而最多的是（ ）排序
A．冒泡 B．希尔 C．快速 D．堆 74．与链表不相适宜的叙述是（ ）
A、动态存储分配 B、可表示任何类型的数据结构
C、插入和删除操作灵活 D、查找速度快
75．设i为n个结点的二叉树结点编号，i=1,2,?,n；若i<=(n-1)/2时，结点i的右子女为（ ）
A、2i B、2i+1 C、2i-1 D、i+1 76．队列的插入操作是在（ ）进行。
A、队首 B、队尾 C、队前 D、对后 77、下面关于二分查找的叙述正确的是 ( )
A. 表必须有序，表可以顺序方式存储，也可以链表方式存储 B. 表必须有序，而且只能从小到大排列
C. 表必须有序且表中数据必须是整型，实型或字符型 D. 表必须有序，且表只能以顺序方式存储
78．在一个单链表HL中，若要在指针q所指结点的后面插入一个由指针p所指向的结点，则执行（ ）。
A、 q->next=p->next;p->next=q; B、 p->next=q->next;q=p; C、 q->next=p->next;p->next=q; D、 p->next=q->next;q->next=p; 79．S=‘software’，其子串的数目是（ ）
A、8 B、37 C、36 D、9
80．下面的说法中正确的是（ ）.
（1）任何一棵二叉树的叶子结点在三种遍历中的相对次序不变； （2）按二叉树定义，具有三个结点的二叉树共有6种。
A．(1)(2) B．(1) C．(2) D．(1)、(2)都错
81．二维数组M[i,j]的元素占三个字节，行下标i的范围从0到4，列下标j的范围从0到5，M按行存储时元素M[3，5]的起始地址与M按列存储时元素( )的起始地址相同。 A、 M[2,4] B、M[3,4] C、M[3,5] D、M[4,4] 82．下列几种排序方法中，平均查找长度最小的是( )
A、插入排序 B、选择排序 C、快速排序 D、归并排序
83．采用顺序查找方法查找长度为n的线性表时，每个元素的平均查找长度为（ ）
A、n B、n/2 C、（n＋1）/2 D、（n－1）/2 84．下述几种排序方法中，要求内存量最大的是（ ）
A、插入排序 B、选择排序 C、快速排序 D、归并排序
85．数据结构是一门研究非数值计算的程序设计问题中计算机的（ ），以及它们之间的（ ） 和运算等的学科。
A、操作对象 关系 B、计算方法 结构 C、逻辑存储 运算 D、数据映象 算法 86．下述哪一条是顺序存储结构的优点？（ ）
A．存储密度大 B．插入运算方便
C．删除运算方便 D．可方便地用于各种逻辑结构的存储表示 87．计算机算法必须具备输入、输出、（ ）等五个特性。
A、 可行性、可移植性和可扩充性 B、 C、 确定性、有穷性和稳定性 D、 88．栈和队列的共同点是（ ）
A、 都是先进后出 B、 都是先进先出 C、 只允许在端点处插入和删除元素 D、 没有共同点 89．在一个单链表中，若删除p所指结点的后续结点，则执行（ ）
A、p -> next = p ->next->next; B、p = p->next; p->next = p->next->next C、p->next = p->next; D、p = p->next->next; 90．深度为5的二叉树至多有（ ）个结点
A、16 B、32 C、31 D、10
91．设循环队列中数组的下标范围是1~n，其头尾指针分别为f和r，则其元素个数为（ ）。
A、r-f B、r-f+1 C、(r-f) mod n +1 D、(r-f+n) mod n
92．递归过程或函数调用时，处理参数及返回地址，要用一种称为（ ）的数据结构。
A．队列 B．多维数组 C．栈 D. 线性表 93．对一棵二叉排序树进行（ ）遍历得到的结点序列是一个有序序列。
A、前序 B、中序 C、后序 D、层序 94．任何一个无向连通图的最小生成树（ ）。
A、有一棵或多棵 B、只有一棵 C、一定有多棵 D、可能不存在
95．数组A[1..5,1..6]的每个元素占5个单元，将其按行优先顺序存储在起始地址为1000的连续的内存单元中，则元素A[5,5]的地址为（ ）。 A. 1140 B. 1145 C. 1120 D 1125
96．下列排序算法中，某一趟结束后未必能选出一个元素放在其最终位置上的是（ ）。
A.堆排序 B.冒泡排序 C.快速排序 D.直接插入排序
97．设栈S和队列Q的初始状态为空，元素e1，e2，e3，e4,e5和e6依次通过栈S，一个元素出栈后即进队列Q，若6个元素出队的序列是e2，e4，e3,e6,e5,e1则栈S的容量至少应该是( )。
A． 6 B. 4 C. 3 D. 2
100．一棵非空的二叉树的先序遍历序列与后序遍历序列正好相反，则该二叉树一定满足（ ）
A．所有的结点均无左孩子B．所有的结点均无右孩子 C．只有一个叶子结点D．是任意一棵二叉树
101．在二叉树结点的先序序列，中序序列和后序序列中，所有叶子结点的先后顺序（ ）
可行性、确定性和有穷性 易读性、稳定性和安全性
A．都不相同 B．完全相同
C．先序和中序相同，而与后序不同 D．中序和后序相同，而与先序不同 102．某二叉树的前序序列和后序序列正好相反，则该二叉树一定是（）的二叉树。
A．空或只有一个结点 B．任一结点无左子树 C．高度等于其结点数 D．任一结点无右子树
103．若线性表最常用的操作是存取第i个元素及其前驱的值，则采用 （ ） 存储方式节省时间。
A. 单向链表 B.双向链表 C.单循环链表 D.顺序表
104．对二叉树的结点从1开始进行连续编号，要求每个结点的编号大于其左、右孩子的编号，同一双亲的左、右孩子中，左孩子的编号小于右孩子的编号，则可采用（ ） 顺序实现编号。
A. 前序遍历 B.中序遍历 C.后序遍历 D.层序遍历 105．设连通图G的顶点数n，则G的生成树的边数为 （ ） 。
A.n B.n-1 C.2n D，2n-1
106．若长度为n的线性表采用顺序存储结构，删除一元素需要移动元素的平均个数为（ ）
A (n-1)/2 B n C n-1 D n/2
107．设A是n*n的对称矩阵，将A的对角线及对角线上方的元素以列为主的次序存放在一维数组B[1..n(n+1)/2]中，对上述任一元素aij(1≤i，j≤n，且i≤j)在B中的位置为( )。
A. i(i-l)/2+j B. j(j-l)/2+i C. j(j-l)/2+i-1 D. i(i-l)/2+j-1 108．设栈的输入序列为（1，2，3，4），则不可能的出栈序列为（ ）
A 1234 B 2134 C 1432 D 4312
109．从一棵深度为h的二叉排序树中查找一个元素时，其时间复杂度为 ( )。
A．O(h) B．O(h2) C．O(log2h) D．O(n*log2h)
110．一个循环队列的队首和队尾指针分别是front和rear,则判别队空的条件是（ ） A.front+1==rear C.front==0
B.front==rear+1 D.front==rear
111．由两个栈共享一个向量空间的好处是（ ）
A、减少存取时间，降低下溢发生的机率 B、节省存取空间，降低上溢发生的机率 C、减少存取时间，降低上溢发生的机率 D、节省存取空间，降低下溢发生的机率 112．如下陈述中正确的是（ ）
A、串是一种特殊的线性表 B、串的长度必须大于零 C、串中元素只能是字母 D、空串就是空白串
113． 引入二叉线索树的目的是（ ）
A．加快查找结点的前驱或后继的速度 B．为了能在二叉树中方便的进行插入与删除 C．为了能方便的找到双亲 D．使二叉树的遍历结果唯一 114．线索二叉树是一种（ ）结构。
A． 逻辑 B． 逻辑和存储 C． 物理 D．线性 115．n个结点的线索二叉树上含有的线索数为（ ）
A．2n B．n－l C．n＋l D．n 116．二叉树在线索后，仍不能有效求解的问题是（ ）。
A．前（先）序线索二叉树中求前（先）序后继 B．中序线索二叉树中求中序后继 C．中序线索二叉树中求中序前驱 D．后序线索二叉树中求后序后继
117． 设F是一个森林，B是由F变换得的二叉树。若F中有n个非终端结点，则B中右指针域为空的结点有（ ）个。
A． n-1 B．n C． n+1 D． n+2
118．如果T2是由有序树T转换而来的二叉树，那么T中结点的后序就是T2中结点的（ ）。
A．先序 B．中序 C．后序 D．层次序
119、无向图G=（V，E），其中：V={ a,b,c,d,e,f} ,E={(a,b),(a,e),(a,c),(b,e),(c,f),(f,d),(e,d)} 对该图进行深度优先遍历，得到的顶点序列正确的是（ ） A.a,b,e,c,d,f B.a,c,f,e,b,d
C.a,e,b,c,f,d D.a,e,d,f,c,b
120．对序列{15，9，7，8，20，-1，4}进行排序，进行一趟后数据的排列变为{4，9，-1，8，20，7，15}；则采用的是（ ）排序。
A. 选择 B. 快速 C. 希尔 D. 冒泡
121．设哈希表长为14，哈希函数是H(key)=key,表中已有数据的关键字为15,38,61,84共四个，现要将关键字为49的结点加到表中，用二次探测再散列法解决冲突，则放入的位置是（ ）
A. 8 B.3 C.5 D.9
122． 用数组 r 存储静态链表, 结点的 next 域指向后继, 工作指针 j 指向链中结点,使 j 沿链移动的操作为（ ）
A. j=r[j].next B. j=j+1 C. j=j->next D. j=r[j]->next
123．判定一个有图是否存在回路，除了可以利用拓扑排序的方法外，还可以利用( )。 A.求关键路径的方法 B.求最短路径的Dijkstra方法
C.深度优先遍历算法 D.广度优先遍历算法
124．为查找某一特定单词在文本中出现的位置，可应用的串运算是( )
A.插入 B.删除 C.串联接 D.子串定位
125．设单循环链表中结点的结构为（data，next），且rear是指向非空的带头结点的单循环链表的尾结点的指针。若要删除链表的第一个结点，则应执行下列哪一个操作？( )
A. s=rear; rear=rear->next; free(s); B. rear=rear->next; free(s); C. rear=rear->next->next; free(s);
D s=rear->next->next; rear->next->next=s->next; free(s);
126．下列排序算法中，在每一趟都能选出一个元素放到其最终位置上，并且其时间性能受数据初始特性影响的是：（ ）。
A. 直接插入排序 B. 快速排序 C. 直接选择排序 D. 堆排序 127．在一棵二叉树上，第4层上的结点数最多为( )
A.31 B.8 C.15 D.16
128． 快速排序方法在( )情况下，最不利于发挥其长处 A.要排序的数据量太大 B.要排序的数据含有多个相同值 C.要排序的数据已基本有序 D.要排序的数据个数为奇数 129． 对于无向图的生成树，下列说法不正确的是( )
A.生成树是遍历的产物
B.从同一顶点出发所得的生成树相同 C.生成树是图的极小连通子图 D.不同遍历方法所得到的生成树不同 130．算法分析的目的是( )
A.找出数据结构的合理性 B.研究算法中的输入和输出的关系 C.分析算法的效率以求改进 D.分析算法的易懂性和文档性 131．下列陈述中正确的是( )
A.二叉树是度为2的有序树 B.二叉树中结点只有一个孩子时无左右之分 C.二叉树中必有度为2的结点 D.二叉树中最多只有两棵子树，并且有左右之分 132．判断有向图是否有回路，除了可以用深度优先遍历算法外，还可以用( ) A. 求关键路径的方法 B. 广度优先遍历算法
C. 求最短路径的方法 D. 拓扑排序
133．有一个有序表为{5,8,10,15,32,41,45,62,75,77,82,95,100},当二分查找值为82的数据时( ) 次比较成功。
A.1 B.4 C.2 D.8
134．下列关于AOE网的叙述中，不正确的是（ ）。
A．关键活动不按期完成就会影响整个工程的完成时间 B．任何一个关键活动提前完成，那么整个工程将会提前完成
C．所有的关键活动提前完成，那么整个工程将会提前完成 D．某些关键活动提前完成，那么整个工程将会提前完成
135．采用顺序查找方法查找长度为n的线性表，平均查找长度为 ( )。 A.n B.n/2 C.(n+1)/2 D.(n-1)/2 136．下列哪一种图的邻接矩阵是对称矩阵？（ ）
A．有向图 B．无向图 C．AOV网 D．AOE网 137．对线性表采用折半查找法，该线性表必须 ( )。
A. 采用顺序存储结构 B.采用链式存储结构 C.采用顺序存储结构，且元素按值有序 D.采用链式存储结构，且元素按值有序
138．已知二叉树的前序序列为ABDCEFG，中序序列为DBCAFEG，则后序序列为 ( )。 A.DCBAFGE B.DCBFGEA C.DCBFEGA D.DCBGFEA
139．当利用大小为N 的数组顺序存储一个栈时，假定用top = = N表示栈空，则退栈时，用（ ）语句修改top指针。
A．top++; B．top=0; C．top--; D．top=N;
140．数据序列（2，1，4，9，8，10，6，20）只能是下列排序算法中的( )的两趟排序后的结果。
A. 快速排序 B. 冒泡排序 C. 选择排序 D. 插入排序 141．从一棵B_树删除元素的过程中，若最终引起树根结点的合并，则新树高度是（ ）。
A．原树高度加1 B．原树高度减1 C．原树高度 D．不确定 142．在倒排文件中，通常包含有 倒排表。
A.一个 B.多个 C.两个 D.一个或两个
143．若用冒泡排序方法对序列{10,14,26,29,41,52}从大到小排序，需进行 （ ）次比较。
A. 3 B. 10 C. 15 D. 25
144．循环队列A[0..m-1]存放其元素值，用front和rear分别表示队头及队尾，则当前队列中的元素数是
A.(rear - front + m)%m B.rear - front + 1 C. rear - front - 1 D.rear-front 145．下列说法不正确的是（ ）。
A．图的遍历是从给定的源点出发每一个顶点仅被访问一次
B．图的深度遍历不适用于有向图
C．遍历的基本算法有两种：深度遍历和广度遍历 D．图的深度遍历是一个递归过程
146. 一个队列的入队序列是1、2、3、4，则队列的输出序列是（ ）
A. 4、3、2、1 B.1、2、3、4 C.1、4、3、2 D.3、2、4、1
147.在一个单链表中，已知q所指结点是p所指结点的前驱结点，若在q和p之间插入s结点，则执行（ ）
A. s -> next = p -> next; p->next = s;B.p->next = s->next; s->next = p; C.q->next = s; s->next = p; D.p->next = s; s->next = q;
148．下列排序算法中( )不能保证每趟排序至少能将一个元素放到其最终的位置上。
A.快速排序 B. shell排序 C. 堆排序 D.冒泡排序 149．具有n个顶点的有向图最多有（ ）条边。
A．n B.n(n-1) C.n(n+1) D.n*n
150．在数据结构中，逻辑上数据结构可分为（ ）。
A．动态结构和静态结构 B．线性结构和非线性结构 C．紧凑结构和非紧凑结构 D．内部结构和外部结构 151．在下面的排序方法中，辅助空间为O（n）的是( ) 。
A．希尔排序 B. 堆排序 C. 选择排序 D. 归并排序 152．不便于插入和删除操作的是（ ）。
A．单链表 B．双链表 C．顺序表 D．循环链表
153．在有向图G的拓扑序列中，若顶点Vi在顶点Vj之前，则下列情形不可能出现的是（ ）。
A．G中有弧
B．一个事件的最早开始时间同以该事件为尾的弧的活动最早开始时间相同
C．一个事件的最迟开始时间为以该事件为尾的弧的活动最迟开始时间与该活动的持续时间的差
D．关键活动一定位于关键路径上 155．树最适合用来表示（ ）
A.有序数据元素 B.无序数据元素 C.元素之间具有分支层次关系的数据 D.元素之间无联系的数据 156．具有4个顶点的无向完全图至多有（ ）条边。
A.6 B.12 C.16 D.20
157．具有6个顶点的无向图至少应有（ ）条边才能确保是一个连通图。
A.5 B.6 C.7 D.8
158．假定有k个关键字互为同义词，若用线性探测法把这k个关键字存入散列表中，至少要进行多少次探测？( )
A．k-1次 B. k次 C. k+1次 D. k（k+1）/2次
159．设哈希表长为14，哈希函数是H(key)=key,表中已有数据的关键字为15，38，61，
84共四个，现要将关键字为49的结点加到表中，用二次探测再散列法解决冲突，则放入的位置是( ) A．8 B．3 C．5 D．9
160．设有一组记录的关键字为{19，14，23，1，68，20，84，27，55，11，10，79}，用链
地址法构造散列表，散列函数为H（key）=key MOD 13,散列地址为1的链中有（ ）个记录。 A．1 B. 2 C. 3 D. 4
填空题
二、填空题
1 栈的特点是( )，队列的特点是( )。
2 设二维数组A[-20..30,-30..20], 每个元素占有4 个存储单元, 存储起始地址为200.如按行优先顺序存储,则元素 A[25,18]的存储地址为( )；如按列优先顺序存储,则元素A[-18,-25]的存储地址为( )。
3 一个图的( 邻接矩阵 )表示法是唯一的，而(邻接表 )表示法是不唯一的。 4 二叉树由( )，( )，( )三个基本单元组成。 5树在计算机内的表示方式有( )，( )，( )。 6在二叉树中，指针p所指结点为叶子结点的条件是( )。
7中缀式a+b*3+4*（c-d）对应的前缀式为( )，若a=1，b=2，c=3，d=4，则后缀式db/cc*a-b*+的运算结果为( )。
8二叉树中某一结点左子树的深度减去右子树的深度称为该结点的( )。 9具有256个结点的完全二叉树的深度为( )。
10已知一棵度为3的树有2个度为1的结点，3个度为2的结点，4个度为3的结点，则该树有( )个叶子结点。
11在顺序表（8,11,15,19,25,26,30,33,42,48,50）中，用二分（折半）法查找关键码值20，需做的关键码比较次数为( )。
12深度为H 的完全二叉树至少有( )个结点；至多有( )个结点；H和结点总数N之间的关系是 ( )。
13高度为4的3阶b-树中，最多有( )个关键字。
14在完全二叉树中，编号为i和j的两个结点处于同一层的条件是( )。 15具有n个结点的满二叉树，其叶子结点的个数为( ).
16已知广义表A=(9,7,( 8,10,(99)),12)，试用求表头和表尾的操作Head( )和Tail( )将原子元素99从A中取出来( )。
17已知广义表L=（（x,y,z）,a,(u,t,w)）, 则head(tail(tail(L)))= ( )。 18设有二维数组A[0..9,0..19],其每个元素占两个字节，第一个元素的存储地址为100，若按列优先顺序存储，则元素A[6,6]存储地址为( )。
19．一棵有n个结点的满二叉树有( 0 )个度为1的结点、有( (n-1)/2 )个分支 （非 终端）结点和( (n+1)/2)个叶子，该满二叉树的深度为( )。
20．假设根结点的层数为１，具有ｎ个结点的二叉树的最大高度是( n )。
21．在一棵二叉树中，度为零的结点的个数为N0,度为2的结点的个数为N2,则有N0 =( )。 22设只含根结点的二叉树的高度为0，则高度为k的二叉树的最大结点数为( ),最小结点数为( )。
23．设有N个结点的完全二叉树顺序存放在向量A[1:N]中，其下标值最大的分支结点为
( )。
24．假定有k个关键字互为同义词，若用线性探测再散列法把这k个关键字存入散列表中，至少要进行( )次探测。
25．高度为8的完全二叉树至少有( )个叶子结点。
26．已知二叉树有50个叶子结点，则该二叉树的总结点数至少是( )。 27．一个有2001个结点的完全二叉树的高度为( )。
28．设F是由T1,T2,T3三棵树组成的森林,与F对应的二叉树为B,已知T1,T2,T3的结点数分别为n1,n2和n3则二叉树B的左子树中有( )个结点，右子树中有( )个结点。 29．一个深度为k的，具有最少结点数的完全二叉树按层次，（同层次从左到右）用自然数依此对结点编号，则编号最小的叶子的序号是( )；编号是i的结点所在的层次号是( )（根所在的层次号规定为1层）。
30．如某二叉树有20个叶子结点，有30个结点仅有一个孩子，则该二叉树的总结点数为( )。
31．如果结点A有 3个兄弟，而且B是A的双亲，则B的度是( )。 32有n个结点并且其高度为n的二叉树的数目是( )。
33将下三角矩阵A[1..8,1..8]的下三角部分逐行地存储到起始地址为1000的内存单元中，已知每个元素占4个单元，则A[7,5]的地址是( )。
34已知二维数组A[1..10，0..9]中每个元素占4个单元，在按行优先方式将其存储到起始地址为1000的连续存储区域时，A[5，9]的地址是( )。
35按13、24、37、90、53的次序形成二叉平衡树，则该二叉平衡树的高度是( )，其根为( )，左子树中的数据是( )，右子树中的数据是( )。 36假定一棵三叉树的结点个数为50，则它的最小深度为( )。 37在操作序列
Qinsert(1),Qinsert(2),Qdelete,Qinsert(3),Qinsert(4),Qdelete,
Qinsert(5).之后，队头元素和队尾元素分别是什么？( ) 、( ) Qinsert(k)表示整数k入队列,Qdelete表示元素出队列。 38带头结点的双循环链表L为空表的条件是：( )。
39在操作序列 push(1),push(2),pop,push(3),push(4),pop ,push(5)之后,栈顶、栈底元素分别是什么？( )、( ) 。
push(k)表示整数k入栈，pop表示栈顶元素出栈。
40设数组A[0..8,1..10],数组中任一元素A[i,j]均占内存48个二进制位，从首地址2000开始连续存放在主内存里，主内存字长为16位，那么 （l） 存放该数组至少需要的单元数是( );
（2） 存放数组的第8列的所有元素至少需要的单元数是( ); （3） 数组按列存储时，元素A[5,8]的起始地址是( )。 41高度为8的平衡二叉树的结点数至少有( )个。
42．完全二叉树中，结点个数为n，则编号最大的分支结点的编号为( )。
43．设一棵完全二叉树叶子结点数为k,最后一层结点数>2，则该二叉树的高度为( )。 44．对于一个具有n个结点的二元树，当它为一棵( )二元树时具有最小高度，当它为一棵( )时，具有最大高度。
45．具有N个结点的二叉树，采用二叉链表存储，共有( )个空链域。
46 8层完全二叉树至少有( )个结点，拥有100个结点的完全二叉树的最大层数为( )。 47．含4个度为2的结点和5个叶子结点的二叉树，可有______个度为1的结点。 48．一棵树T中，包括一个度为1的结点，两个度为2的结点，三个度为3的结点，四个度为4的结点和若干叶子结点，则T的叶结点数为( )。
49． n（n大于1）个结点的各棵树中，其深度最小的那棵树的深度是( )。它共有( )个叶子结点和( )个非叶子结点，其中深度最大的那棵树的深度是( )，它共有( )个叶子结点和( )个非叶子结点。
50． 每一棵树都能唯一的转换为它所对应的二叉树。若已知一棵二叉树的前序序列是BEFCGDH，对称序列是FEBGCHD，则它的后序序列是( )。设上述二叉树是由某棵树转换而成，则该树的先根次序序列是( )。
51．先根次序周游树林正好等同于按( )周游对应的二叉树，后根次序周游树林正好等同于按( )周游对应的二叉树。
52．二叉树结点的对称序序列为A,B,C,D,E,F,G,后序序列为B,D,C,A,F,G,E,则该二叉树结点的前序序列为( ),则该二叉树对应的树林包括( )棵树。 53．二叉树的先序序列和中序序列相同的条件是( )。
54．已知一棵二叉树的前序序列为abdecfhg,中序序列为dbeahfcg，则该二叉树的根为( )，左子树中有( )， 右子树中有( )。
55．设二叉树中每个结点均用一个字母表示，若一个结点的左子树或右子树为空，用 ．表示，现前序遍历二叉树，访问的结点的序列为ABD.G...CE.H..F．．，则中序遍历二叉树时，访问的结点序列为( );后序遍历二叉树时，访问的结点序列为( )。 56．已知二叉树前序为ABDEGCF，中序为DBGEACF，则后序一定是( )。
57．现有按中序遍历二叉树的结果为abc，问有( )种不同的二叉树可以得到这一遍历结果，这些二叉树分别是( )。
58．一个无序序列可以通过构造一棵( )树而变成一个有序序列，构造树的过程即为对无序序列进行排序的过程。
59．利用树的孩子兄弟表示法存储，可以将一棵树转换为( )。
60．若一个二叉树的叶子结点是某子树的中序遍历序列中的最后一个结点，则它必是该子树的( )序列中的最后一个结点。
61．先根次序周游树林正好等同于按( )周游对应的二叉树；后根次序周游树林正好等同于( )周游对应的二叉树。
62. 在一棵存储结构为三叉链表的二叉树中，若有一个结点是它的双亲的左子女，且它的双亲有右子女，则这个结点在后序遍历中的后继结点是( )。
63．一棵左子树为空的二叉树在先序线索化后，其中的空链域的个数为：( )。 64．具有n个结点的满二叉树，其叶结点的个数是( )。
65．设一棵后序线索树的高是50，结点x是树中的一个结点，其双亲是结点y,y的右子树高度是31，x是y的左孩子。则确定x的后继最多需经过( )中间结点（不含后继及x本身）
66．线索二元树的左线索指向其( )，右线索指向其( )。
67二叉树的前序遍历的操作步骤：若二叉树非空：（1） ( )； （2） ( ) ；（3）( ) 。
68己知三对角矩阵A【1..9,1..9】的每个元素占2个单元，现将其三条对角线上的元素逐行存储在起始地址为1000的连续的内存单元中，则元素A[7,8]的地址为( )。 69数据结构包括( )、( )、( ) 、( )四种结构。 70表达式23+((12*3-2)/4+34*5/7)+108/9的后缀表达式是( )。
71假设一个15阶的上三角矩阵A按行优先顺序压缩存储在一维数组B中，则非零元素A9,9在B中的存储位置k=( )。（注：矩阵元素下标从1开始） 72．哈夫曼树是( )。
73．若以{4，5，6，7，8}作为叶子结点的权值构造哈夫曼树，则其带权路径长度是( )。 74．有数据WG={7，19，2，6，32，3，21，10}，则所建Huffman树的树高是( )，带权路径长度WPL为( )。
75．有一份电文中共使用 6个字符:a,b,c,d,e,f,它们的出现频率依次为2,3,4,7,8,9，试构造一棵哈夫曼树，则其加权路径长度WPL为( )，字符c的编码是( )。 76．设n0为哈夫曼树的叶子结点数目，则该哈夫曼树共有( )个结点。
77设HEAD（P）为求广义表P的表头函数，TAIL（P）为求广义表P的表尾函数，给出下列广义表的运算结果：HEAD（a,b,c）=( )，head((a),(b))= ( )，tail(head((a.b),(c,d)))= ( )。
78设循环队列存放在向量sq.data[0:M]中，则队头指针sq.front在循环意义下的出队操作可表示为( )，若用牺牲一个单元的办法来区分队满和队空（设队尾指针sq.rear）,则队满的条件为( )。
79深度为5的二叉数至多有( )个节点。
80对于一个具有n个结点的单链表，在已知的结点*p后插入一个新结点的时间复杂度为( ),在给定值为x的结点后插入一个新结点的时间复杂度为( )。 81多个栈共存时，最好用( )作为存储结构。
82在一棵7阶B树中，一个结点中最多有( )个关键字，最少有( )个关键字。 83在双向循环链表中,向p所指的结点之后插入指针f所指的结点，其操作是( )、( )、( )、( )。
84在一棵二叉树中有n0个叶结点，有n2个度为2的结点，则n0=( )。 85 G是一个非连通无向图，共有28条边，则该图至少有( )个顶点。
86顺序存储结构是通过( )表示元素之间的关系的;链式存储结构是通过( )表示元素之间的关系的。
87循环队列的引入，目的是为了克服( )。
88不带头结点的单链表HEAD为空的判断条件是( )，带头结点的单链表HEAD为空的判断条件是( )。
89某二叉树有10个叶子结点，20个结点仅有一个孩子，该二叉树的总的结点数 是 ( )。
90广义表A((( ),(a,(b),c)))，head(tail(head(tail(head(A))))等于( )。 91带头结点的双循环链表L中只有一个元素结点的条件是：( )。
92给定一组数据{6，2，7，10，3，12}以它构造一棵哈夫曼树，则树高为( )，带权路径长度WPL的值为( )。
93当两个栈共享一存储区时，栈利用一维数组stack(1,n)表示，两栈顶指针为top[1]与top[2]，则当栈1空时，top[1]为( )，栈2空时 ，top[2]为( )，栈满时为( )。 94判断一个无向图是一棵树的条件是( )。 95有向图G的强连通分量是指( )。 96一个连通图的( )是一个极小连通子图。 97具有10个顶点的无向图，边的总数最多为( )。
98若用n表示图中顶点数目，则有( )条边的无向图成为完全图。
99 设无向图 G 有n 个顶点和e 条边，每个顶点Vi 的度为di（1<=i<=n〉，则e=( ) 100 G是一个非连通无向图，共有28条边，则该图至少有( )个顶点。
101 在有n个顶点的有向图中，若要使任意两点间可以互相到达，则至少需要( )条弧。 102在有n个顶点的有向图中，每个顶点的度最大可达( )。 103设G为具有N个顶点的无向连通图，则G中至少有( )条边。
104顺序查找n个元素的顺序表，若查找成功，则比较关键字的次数最多为( )次；当使用监视哨时，若查找失败，则比较关键字的次数为( )。 105．如果含n个顶点的图形形成一个环，则它( )棵生成树。
106.在双向链表中，每个结点有两个指针域，一个指向其( )结点，另一个指向其 ( ) 结点。
107广义表简称表，是由零个或多个原子或子表组成的有限序列，原子与表的差别仅在于 ( )。为了区分原子和表，一般用( )表示表，用( )表示原子。一个表的长度是指 ( )，而表的深度是指( )。
108、已知一棵完全二叉树的第八层有8个结点（根结点在第0层），则该完全二叉树的叶结点数是( )。
109在作进栈运算时应先判别栈是否( );在作退栈运算时应先判别栈是否( )；当栈中元素为n个，作进栈运算时发生上溢，则说明该栈的最大容量为( )。 110 上面的图去掉有向弧看成无向图则对应的最小生成树的边权之和为( )。 111．设有向图有n个顶点和e条边，进行拓扑排序时，总的计算时间为( )。 112．AOV网中,结点表示( ),边表示( )；AOE网中,结点表示( ),边表示( )。 113．若不考虑基数排序，则在排序过程中，主要进行的两种基本操作是关键字的( )和记录的( )。
114 属于不稳定排序的有( )。
115分别采用堆排序，快速排序，冒泡排序和归并排序，对初态为有序的表，则最省时间的是( )算法，最费时间的是( )算法。
116设表中元素的初始状态是按健值递增的，分别用堆排序，快速排序，冒泡排序和归并排序方法对其进行排序（按递增顺序）， ( )排序最省时间，( )排序最费时间。 117不受待排序初始序列的影响，时间复杂度为O(N)的排序算法是( )，在排序算法的最后一趟开始之前，所有元素都可能不在其最终位置上的排序算法是( )。 118直接插入排序用监视哨的作用是( )。
119对n个记录的表r[1..n]进行简单选择排序，所需进行的关键字间的比较次数为( )。 120在AOE网中，从源点到汇点路径上各活动时间总和最长的路径称为( )。
121在一棵m阶B-树中,若在某结点中插入一个新关键字而引起该结点分裂,则此结点中原有的关键字的个数是( );若在某结点中删除一个关键字而导致结点合并,则该结点中原有的关键字的个数是( )。
122 当一个AOV网用邻接表表示时，可按下列方法进行拓扑排序。 （1）．查邻接表中入度为( )的顶点，并进栈；
（2）．若栈不空，则①输出栈顶元素Vj，并退栈；②查Vj的直接后继Vk，对Vk入度处理，处理方法是( )；
（3）．若栈空时，输出顶点数小于图的顶点数，说明有( )，否则拓扑排序完成。 123算法的五个重要特性是( )、( )、( )、( )、( )。
124线性表L=（a1,a2,?,an）用数组表示，假定删除表中任一元素的概率相同，则删除一个
2
元素平均需要移动元素的个数是( )。
应用题
1 设数据集合d= {1，12，5，8，3，10，7，13，9}，完成下列各题：
1) 依次取d中各数据，构造一棵二叉排序树bt。 2) 如何依据此二叉树bt得到d的一个有序序列？ 3) 画出在二叉树bt中删除“12”后的树结构
2 已知一棵二叉数的前序遍历为ABDECFG中序遍历为DBEAFGC，画出该二叉树，并写出它的后序序列。
3 关键码集为{36,18,22,11,48,59,19,14,70},哈希表表长为11，hash(key)=key,用线性探测法处理冲突，并求出查找成功时的平均查找长度(给出步骤)
4 设一数组中原有数据如下：15，13，20，18，12，60。下面是一组由不同排序方法进行一遍排序后的结果。
（ ）排序的结果为：12，13，15，18，20，60 （ ）排序的结果为：13，15，18，12，20，60 （ ）排序的结果为：13，15，20，18，12，60 （ ）排序的结果为：12，13，20，18，15，60 5 有如图所示的带权有向图G，试回答以下的问题。(给出步骤)
1) 给出从顶点1出发的深度优先遍历序列和广度优先遍历序列。 2) 给出下图的一个拓扑序列。 3) 给出从顶点1到顶点8的关键路径。
6 4 4 5 1 3 3 6 4 7 4 9 6 2 5 8 2 5 4 2 12 7 3 3 6 给出一组关键字T={12，2，16，30，8，28，4，10，20，6，18}，写出用下列算法从小到大排序时第一趟结束时的序列
1） 希尔排序（第一趟排序的增量为5） 2） 快速排序（选第一个记录为枢轴）
7 已知一棵二叉树的先序遍历序列为：AEFBGCDHIKJ，中序遍历序列为：EFAGBCHKIJD。试写出此二叉树的后序遍历序列，并用图画出它的后序线索二叉树。
8 现有如下的稀疏矩阵A如图所示，要求用三元组表示A和它的转置矩阵。
?150?013??00??00030022?0?? ?6??0?9 对给定的有7个顶点的有向图的邻接矩阵如下：
(1)画出该有向图； (2)画出邻接表；
(3)若将图看成AOE－网，列出其关键活动及相应的有向边，关键路径长度是多少？
??????????????????2??????52?????3?1??????35????75?3???????????? 7??5????10设用于通讯的电文由8个字母A、B、C、D、E、F、G、H组成，字母在电文中出现的频率分别为：7、19、2、6、32、3、21、10。试为这8个字母设计哈夫曼编码。
11设有一组关键字{9,01,23,14,55,20,84,27}，采用哈希函数：H（key）=key mod 7 ，表长为10，用开放地址法的二次探测再散列方法Hi=(H(key)+di) mod 10(di=1,2,3,?,)解决冲突。要求：对该关键字序列构造哈希表，并计算查找成功的平均查找长度。 12一棵非空的二叉树其先序序列和后序序列正好相反，画出这棵二叉树的形状。
13有关键字集合K={15，22，50，13，20，36，28，48，35，31，41，18}采用散列存取，散列表长为15，设散列函数H（K）=K MOD 13，解决冲突采用开放地址法中的二次探测再散列的方法，试将K值填入表中，并计算查找成功时的平均查找长度。
14假设一棵二叉树的层次次序（按层次递增顺序排列，同一层次自左向右）为ABECFGDHI,中序序列为BCDAFEHIG。请画出该二叉树，并将其转换为对应的森林。
15有一随机数组(25,84,21,46,13,27,68,35,20),现采用某种方法对它们进行排序,其每趟排序结果如下, 则该排序方法是什么?
初 始:25,84,21,46,13,27,68,35,20 第一趟:20,13,21,25,46,27,68,35,84 第二趟:13,20,21,25,35,27,46,68,84 第三趟:13,20,21,25,27,35,46,68,84 16 判断序列（12，70，33，65，24，56，48，92，86，33）是否为堆，如果不是，则把它调整为小堆。
17设一棵二叉树的先序、中序遍历序列分别为；先序遍历序列： A B D F C E G H 中序
2
2
2
遍历序列： B F D A G E H C
（1）画出这棵二叉树。
（2）画出这棵二叉树的后序线索树。 （3）将这棵二叉树转换成对应的树（或森林）。
18 已知含有8个结点的一棵二叉树，按先序、中序、后序进行遍历后，有些结点序号不清楚如下图示。要求构造出一棵符合条件的二叉树。 先根序遍历 _ 2 3 _ 5 _ 7 8 中根序遍历 3 _ 4 1 _ 7 8 6 后根序遍历 _ 4 2 _ _ 6 5 1
19 对给定文件（28，07，39，10，65，14，61，17，50，21）选择第一个元素28进行划分，写出其快速排序第一遍的排序过程。
20 有向图 G=
(1) 画出插入(18)的3阶B-树。
(2) 画出在插入(18)后的3阶B-树中删除(78) 后的3阶B-树
22设有下列带权无向图： (1) 请画出该图的邻接表。
(2) 列出深度优先遍历该图所得到的一个顶点序列。 (3) 请画出该图的一棵最小生成树。
23已知二叉树T的先序遍历序列为ABCDEFGHIJKL，中序遍历序列为CBEFDJIKLHGA。请画出T的后序线索树。
24判断下列序列是否是堆（可以是小堆，也可以是大堆，若不是堆，请将它们调整为堆）。 （1）100，85，98，77，80，60，82，40，20，10，66 （2）100，98，85，82，80，77，66，60，40，20，10 （3）100，85，40，77，80，60，66，98，82，10，20
（4）10，20，40，60，66，77，80， 82，85，98，100
25一个深度为L的满K叉树有以下性质：第L层上的结点都是叶子结点，其余各层上每个结点都有K棵非空子树，如果按层次顺序从1开始对全部结点进行编号，求： 1）各层的结点的数目是多少？
2）编号为n的结点的双亲结点（若存在）的编号是多少？ 3）编号为n的结点的第i 个孩子结点（若存在）的编号是多少？
4）编号为n的结点有右兄弟的条件是什么？如果有，其右兄弟的编号是多少？
26给出一组关键字T=(12,2,16,30,8,28,4,10,20,6,18),写出用下列算法从小到大排序时第一趟结束时的序列；
(1) 希尔排序（第一趟排序的增量为5） (2) 快速排序（选第一个记录为枢轴（分隔）
算法设计
1一个单链表（不同结点的数据域值可能相同），其头指针为head，编写一个函数计算数据域为x 的结点个数。
2设计算法，求二叉树的深度。 3计一个算法判断一个字符串是否对称
4有一棵二叉树BT以二叉链表为存储结构，请按照要求写出如下算法。 求BT中所有叶子结点数目。
5设计算法，按从根结点到叶子结点，从左子结点到右子结点的次序输出二叉树的所有结点。 6 写出先序遍历二叉树的非递归算法
7设计算法，在无头结点链表L的第i个元素之前插入元素 8设计一算法判别表达式中小括号是否匹配
9设计一算法，求二叉树中以值为x的结点为根的子树深度
10试编写在带头结点的单链表中删除（一个）最小值结点的（高效）算法
11设L为单链表的头结点地址，其数据结点的数据都是正整数且无相同的，试设计利用直接插入的原则把该链表整理成数据递增的有序单链表的算法。
12设有一个带头结点的单向链表，数据项递减有序。写一算法，重新排列链表，使数据项递增有序，要求算法时间复杂度为O（n）
13有一个单链表L（至少有1个结点），其头结点指针为head，编写一个过程将L逆置，即最后一个结点变成第一个结点，原来倒数第二个结点变成第二个结点，如此等等。 14假设以带头结点的循环链表表示队列，并且只设一个指针指向队尾结点，但不设头指针，请写出相应的入队列和出队列算法。
15设一棵二叉树以二叉链表为存贮结构，结点结构为(lchild, data,rchild)，设计一个算法将二叉树中所有结点的左，右子树相互交换。
16一棵二叉树以二叉链表来表示，求其指定的某一层k(k>1)上的叶子结点的个数。