数据结构 复习题

1、数据结构复习题一、填空题1. 数据结构是一门研究非数值计算的程序设计问题中计算机的 操作对象 以及它们之间的 关系 和运算等的学科。2. 数据结构被形式地定义为（D, R），其中D是 数据元素 的有限集合，R是D上的 关系 有限集合。3. 数据结构包括数据的 逻辑结构 、数据的 存储结构 和数据的 运算 这三个方面的内容。4. 数据结构按逻辑结构可分为两大类，它们分别是 线性结构 和 非线性结构 。5. 线性结构中元素之间存在一对一关系，树形结构中元素之间存在一对多关系，图形结构中元素之间存在多对多关系。6 在线性结构中，第一个结点 没有 前驱结点，其余每个结点有且只有 1个前驱结点；最后一个

2、结点 没有 后续结点，其余每个结点有且只有1个后续结点。7. 在树形结构中，树根结点没有 前驱 结点，其余每个结点有且只有 1 个前驱结点；叶子结点没有 后续 结点，其余每个结点的后续结点数可以任意多个 。8. 在图形结构中，每个结点的前驱结点数和后续结点数可以 任意多个 。9数据的存储结构可用四种基本的存储方法表示，它们分别是顺序 、 链式 、 索引 和 散列 。10. 数据的运算最常用的有5种，它们分别是插入 、 删除、修改、 查找 、排序。11. 一个算法的效率可分为 时间 效率和 空间 效率。12. 在顺序表中插入或删除一个元素，需要平均移动 表中一半元素，具体移动的元素个数与 表长和

3、该元素在表中的位置 有关。13. 线性表中结点的集合是 有限 的，结点间的关系是 一对一 的。14. 向一个长度为n的向量的第i个元素(1in+1)之前插入一个元素时，需向后移动 n-i+1 个元素。15. 向一个长度为n的向量中删除第i个元素(1in)时，需向前移动 n-i 个元素。16. 在顺序表中访问任意一结点的时间复杂度均为 O(1) ，因此，顺序表也称为 随机存取 的数据结构。17. 顺序表中逻辑上相邻的元素的物理位置 必定相邻。单链表中逻辑上相邻的元素的物理位置 不一定 相邻。18在单链表中，除了首元结点外，任一结点的存储位置由 其直接前驱结点的链域的值 指示。19 在n个结点的单

4、链表中要删除已知结点*p，需找到它的前驱结点的地址，其时间复杂度为O（n）；还有一种时间复杂度为O(1)的巧妙删除方法，即把p的后继结点中数据拷贝到p结点中，然后删除p的后继结点，删除语句应该是q=p->next; p->next=q->next;free(q);。20. 向量、栈和队列都是 线性 结构，可以在向量的 任何 位置插入和删除元素；对于栈只能在 栈顶 插入和删除元素；对于队列只能在 队尾 插入和 队首 删除元素。21. 栈是一种特殊的线性表，允许插入和删除运算的一端称为 栈顶 。不允许插入和删除运算的一端称为 栈底 。22. 队列 是被限定为只能在表的一端进行插入

5、运算，在表的另一端进行删除运算的线性表。23. 不包含任何字符（长度为0）的串 称为空串； 由一个或多个空格（仅由空格符）组成的串 称为空白串。24. 子串的定位运算称为串的模式匹配； 被匹配的主串 称为目标串， 子串 称为模式。25. 假设有二维数组A6×8，每个元素用相邻的6个字节存储，存储器按字节编址。已知A的起始存储位置（基地址）为1000，则数组A的体积（存储量）为 288 B ；末尾元素A57的第一个字节地址为 1282 ；若按行存储时，元素A14的第一个字节地址为 (8+4)×6+1000=1072 ；若按列存储时，元素A47的第一个字节地址为 (6×

6、;74)×61000）1276 。26 由个结点所构成的二叉树有 5 种形态。 27. 一棵深度为6的满二叉树有 n1+n2=0+ n2= n0-1=31 个分支结点和 26-1 =32 个叶子。解：满二叉树没有度为1的结点，所以分支结点数就是二度结点数。28 一棵具有个结点的完全二叉树，它的深度为 9 。 解：用ë log2(n) û+1= ë 8.xx û+1=929设一棵完全二叉树有700个结点，则共有 350 个叶子结点。解：最快方法：最后一个叶子编号为700，其父节点编号为n/2350，且其父节点为最后一个非叶子结点。30 设一棵完全

7、二叉树具有1000个结点，则此完全二叉树有 500 个叶子结点，有 499 个度为2的结点，有 1 个结点只有非空左子树，有 0 个结点只有非空右子树。解：方法同上：最后一个非叶子编号为n/2500，所以叶子结点数n0=500, n2=n0-1=499。 另外，最后一个结点为2i属于左叶子，右叶子是空的，所以有1个非空左子树。完全二叉树的特点决定不可能有左空右不空的情况，所以非空右子树数0. 也可根据编号为500的左右儿子结点应该为1000和1001，而显然1001不存在。31在数据的存放无规律而言的线性表中进行检索的最佳方法是 顺序查找（线性查找） 。32. 线性有序表（a1，a2，a3，a

8、256)是从小到大排列的，对一个给定的值k，用二分法检索表中与k相等的元素，在查找不成功的情况下，最多需要检索 8 次。设有100个结点，用二分法查找时，最大比较次数是 7 。33. 假设在有序线性表a20上进行折半查找，则比较一次查找成功的结点数为1；比较两次查找成功的结点数为 2 ；比较四次查找成功的结点数为 8 ；平均查找长度为 3.7 。解：显然，平均查找长度O（log2n）<5次（25）。但具体是多少次，则不应当按照公式来计算（即（21×log221）/204.6次并不正确！）。因为这是在假设n2m-1的情况下推导出来的公式。应当用穷举法罗列：全部元素的查找次数为（1

9、2×24×38×45×5）74； ASL74/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个元素(1in),需要移动 n-i 个元素, 在第i个元素前面插入一

10、个元素，需要移动 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个叶子结点构成一棵哈夫曼树，则带权路径长

11、度为_55_。44完全二叉树的第7层有8个结点，则此完全二叉树的叶子结点数为_36_。768个结点的完全二叉树有_384_个叶子结点？19个结点的哈夫曼树有_10_个叶子结点？45n个顶点的无向连通图，用邻接矩阵存储时，该矩阵至少有 2n-2 个非零元素。 46希尔排序的增量序列有多种选择，但不管哪种选择，最后一个增量必须为_1_。47假设以S和X分别表示入栈和出栈操作，则对输入序列a，b，c，d，e进行一系列栈操作SSXSXSSXXX之后，得到的输出序列为_bceda_。48. 组成串的数据元素只能是_字符_。49n个结点的完全二叉树，编号最大的非叶结点是_n/2_号结点，编号最小的叶结点是

12、_n/2+1_号结点。50已知二叉树有50个叶子结点，则该二叉树的总结点数至少是 99 。51. 在一棵二叉树中，度为0的结点个数为N0,则度为2的节点个数为 N0-1 。52. 叶子权值(5，6，17，8，19)所构造的哈夫曼树带权路径长度为 121 。53. 深度为k的完全二叉树至少有 2k-1 个结点，至多有 2k-1 个结点。54.在n个元素的线性表中顺序查找，若查找成功，则关键字的比较次数最多为 n_次；使用监视哨时，若查找失败，则关键字的比较次数为 n+1 次。55.折半搜索只适合用于_有序的顺序存储表_。56.结点关键字转换为该结点存储单元地址的函数H称为_哈希函数_或叫_散列函

13、数_。57.在一棵k叉树中，度为i(0<=i<=k)的结点的个数为Ni,则有N0 =。解：所有结点数记为n，结合树中分支数比结点数少一个，以及每一个分支被计入顶点的度1次，则有 n =N0+N1+Nk n-1= 1*N1+2*N2+k*Nk /所有结点度数的和 两式相减即得。58.设一棵完全二叉树叶子结点数为k,最后一层结点数为偶数时，则该二叉树的高度为 ；最后一层结点数为奇数时，则该二叉树的高度为 。解：根据完全二叉树性质，结点数为n的完全二叉树，其深度为【或者+1】，所以只要推算出二叉树结点即可。对完全二叉树从根（编号1）开始，逐层递增编号，最后一个结点编号为n，则n的父结点为

14、最后一个非叶子结点，其编号为n/2,也就是说，完全二叉树中非叶子结点个数为n/2,比如n=4或5的完全二叉树，其飞叶子结点数均为2；从而可以看出叶子结点数比非叶子结点数，要么相等，要么多1个，因为完全二叉树除去除去最后一层，上面的为满二叉树（其结点数为奇数），所以当最后一层结点数为偶数时，说明完全二叉树总结点数为奇数，因为叶子结点数为k，则非叶子结点数为k-1,总结点数为2k-1，树深度为=。当最后一层结点数为奇数时，说明总结点数为偶数，此时叶子结点与非叶子结点数相等，所以总结点数为2k，则树深度为。59. 有 5 种不同形态的二叉树可以按照中序遍历得到相同的abc序列。解：根据二叉树5种基本

15、形态，中根遍历为abc，当根为a时，bc在其右子树，有如图2种情况，当根为b时，a在其左子树，c在其右子树，有如图1种情况，当根为c时，ab在其左子树，有如图2种情况，60. 已知二叉树先序为ABDEGCF，中序为DBGEACF，则后序一定是 DGEBFCA 。 解：先画出二叉树，然后写出后根序列。61. 深度为k的完全二叉树至少有 2k-1 个结点，至多有 2k -1 个结点。 解：结点数最少时，第k层仅1个结点，加上上面k-1层满二叉树结点数。 结点数最多时，即为k层的满二叉树。62. 具有10个叶子的哈夫曼树，其最大高度为 ,最小高度为 。 解：哈夫曼树只有度为0和2的结点，且有N0=N

16、2+1，所以哈夫曼树结点数共有19个，最小高度时为完全二叉树，即为log2(19)+1=5;最大高度时，从根到倒数第二层均只有一个非叶子结点，所以高度为10，形状如下 63. 设是一个森林，是由转换得到的二叉树，中有n个非终端结点，则中右指针域为空的结点有 n+1 个。 解：举例子推理，即可发现规律。先对一棵一般树转换，可发现空的右指针数总比非叶子结点数多1个，那么2棵一般树转换成2棵对应二叉树时，空的右指针数比非叶子结点数多2个，但是在转换为森林时，后一棵二叉树接到前一棵二叉树的根右边，从而又会减少一个空的右指针，所以最终空的右指针数总比非叶子结点数多1个。64在线性表(5,12,19,21

17、,37,56,65,75,80,88,92)中，用折半查找法查找关键字为85的记录，关键字的比较次数为 次，所比较的元素依次为 。答案：3 56 80 8865假定对长度n = 100的线性表进行分块查找，并假定每块的长度均为10，每个记录的查找概率相等。若索引表和块内都采用顺序查找，则平均查找长度为 ；若索引表采用折半查找，块内采用顺序查找，则平均查找长度约为 。答案：11 966已知二叉排序树的左右子树均不为空，则_左子树_上所有结点的值均小于它的根结点值，_右子树_上所有结点的值均大于它的根结点的值。67二叉排序树的查找效率与树的形态有关。当二叉排序树退化成成单支树时，查找算法退化为_查

18、找，其平均查找长度上升为_。当二叉排序树是一棵平衡二叉树时，其平均查找长度为_ 。答案：顺序 (n+1)/2 O(log2n)68希尔排序的增量序列有多种选择，但不管哪种选择，最后一个增量必须为_。答案：169. 排序算法所花费的时间，通常用在数据的比较和_移动_两大操作上。二、单项选择题 1程序段 for(i=n-1；i>=0；i-) for(j=1；j<=n；j+) if Aj>Aj+1 Aj与Aj+1对换；其中n为正整数，则最后一行的语句频度在最坏情况下是（ ）。 A. O（n） B. O(n2) C. O(n3) D. O(nlog2n)2线性表中在链式存储中各结点之

19、间的地址（ ）。A. 必须连续 B. 部分地址必须连续 C. 不能连续 D. 连续与否无所谓3将两个各有n个元素的有序线性表归并成一个有序线性表，最少的比较次数是（ ）。An B2n-1 C2n Dn-14在有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

20、C. head->next=head D. head!=NULL7在循环双链表的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

21、. 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，则栈的容量至少应该是_。A3B4 C5 D69在个栈顶指针为top的链栈中，将一个s指针所指的结点入栈，执行_。Atop->nexts： Bs->next=top->next; top->next=s;Cs->next=top; tops； Ds->next=top; top=top

22、->next;10链栈和顺序栈相比，有一个比较明显的优点，即_。 A插入操作更加方便 B通常不会出现栈满的情况 C不会出现栈空的情况 D删除操作更加方便11循环队列Am存放其元素，用front和rear分别表示队头及队尾，则循环队列满的条件是_。A(Q->rear+1)%m=Q->front BQ->rear=Q->front+1CQ->rear+1=Q->front DQ->rear=Q->front12若一个栈的输入序列为1,2,3,n，输出序列的第一个元素是n，则第i个输出元素是( )。A. n-i-1 B. n-i C. n-i+1

23、 D. 不确定13. 设abcdef以所给的次序进栈，若在进栈操作时，允许出栈操作,则下面得不到的序列为( )。Afedcba B. bcafed C. dcefba D. cabdef14.中缀表达式A-（B+C/D）*E的后缀形式是（ ）。A. AB-C+D/E* B. ABC+D/E* C. ABCD/E*+- D.ABCD/+E*-15.假设以数组Am存放循环队列的元素,其头尾指针分别为front和rear，则当前队列中的元素个数为( )。A(rear-front+m)%m Brear-front+1 C(front-rear+m)%m D(rear-front)%m16. 循环队列存

24、储在数组A0.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数组值为_。A0，1，2，3 B1，1，2，3 C1，2，3，1 D1，2，1，119 一维数组A采用顺序存储结构，每个元素占用6个字节，第6个元素的起始地址为100，则该数组的首地址是 。A64

25、B28 C70 D9020稀疏矩阵采用压缩存储的目的主要是_ 。A表达变得简单 B对矩阵元素的存取变得简单 C去掉矩阵中的多余元素 D减少不必要的存储空间的开销21若对n阶对称矩阵A以行序为主序方式将其下三角形的元素(包括主对角线上所有元素)依次存放于一维数组B1.(n(n+1)/2中，则在B中确定aij(i<j)的位置k的关系为_。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+122已知广义表LS=(a,b,c), (d,e,f)，运用GetHead和GetTail运算取出LS中的元素e的运算是 。AGetH

26、ead(GetTail(LS) BGetHead(GetTail(GetTail (GetHead (LS)CGetTail (GetHead (LS) DGetHead(GetTail(GetHead(GetTail(LS)23. 设广义表L=(a,b,c)，则L的长度和深度分别为 。A. 1和1 B. 1和3 C. 1和2 D. 2和324. 一个100*90的稀疏矩阵，非0元素有10个整型数，设每个整型数占2字节，则用三元组表示该矩阵时，所需的字节数是_。A. 60 B. 66 C. 18000 D. 3325设二维数组A1. m，1. n(即m行n列)按行存储在数组B1. m*n中，则

27、二维数组元素Aij在一维数组B中的下标为( )。A.(i-1)*n+j B.(i-1)*n+j-1 C. i*(j-1) D. j*m+i-126.一棵三叉树中，已知度为3的结点数等于度为2的结点数，且树中叶结点的数目为13，则度为2的结点数目为_。A4B2C3D527设n、m为一棵二叉树上的两个结点，在中序遍历时，n在m之前的条件是_。 An在m右方 Bn是m祖先 Cn在m左方 Dn是m子孙28对一个满二叉树，m个树枝，n个结点，深度为h，则_。An=h+m Bh+m=2n Cm=h-1 Dn=2h-129以二叉链表作为二叉树的存储结构，在有n个结点的二叉链表中(n>0)，链表中空链域

28、的个数为_。A2n-1 Bn-1 Cn+1 D2n+130在一棵二叉树结点的先序序列、中序序列、后序序列中，所有叶子结点的先后顺序_。A都不相同 B先序和中序相同，而与后序不同C完全相同 D中序和后序相同，而与先序不同31如果将给定的一组数据作为叶子数值，所构造出的二叉树的带权路径长度最小，则该树称为_。A哈夫曼树 B平衡二叉树 C二叉树 D完全二叉树32树的先根序列和其对应的二叉树的 是一样的，树的后根序列和其对应的二叉树的 是一样的。A先序序列 B中序序列 C后序序列 D按层次遍历序列33若一个具有N个顶点，K条边的无向图是一个森林(N>K),则该森林中必有_棵树。AK BN CN-

29、K D134. 如果T2是由树T转换而来的二叉树，那么对T中结点的后序遍历就是对T2中结点的( )遍历。A先序 B中序 C后序 D层次序35. 设树T的度为4，其中度为1，2，3和4的结点个数分别为4，2，1，1 则T中的叶子数为( )。A5 B6 C7 D836. 由4个结点可以构造出多少种不同的二叉树？( )A10 B12 C14 D1637. 二叉树在线索后，仍不能有效求解的问题是( )。A先序线索二叉树中求先序后继 B中序线索二叉树中求中序后继C中序线索二叉树中求中序前驱 D后序线索二叉树中求后序后继 38. 一棵二叉树具有10个度为2的结点，5个度为1的结点，则度为0的结点个数是(

30、)。A9 B11 C15 D不确定39. 设高度为h的二叉树上只有度为0和度为2的结点，则此类二叉树中所包含的结点数至少为( )个。A 2h B2h-1 C 2h+1 D h+140. 设给定权值的叶子总数有n 个，其哈夫曼树的结点总数为( )。A不确定 B2n C2n+1 D2n-141. 某二叉树的先序遍历序列和后序遍历序列正好相反，则此二叉树一定是( )。A空或只有一个结点 B完全二叉树 C单支树 D高度等于结点数42. 在二叉树结点的先序序列，中序序列和后序序列中，所有叶子结点的先后顺序( )。A都不相同 B完全相同 C先序和中序相同，而与后序不同 D中序和后序相同，而与先序不同 43

31、. 根据使用频率，为个字符设计的哈夫曼编码不可能是( )。A111,110,10,01,00 B000,001,010,011,1 C100,11,10,1,0 D001,000,01,11,10 44具有7个顶点的有向图至少应有_条边才能确保一个强连通图。A. 6 B. 7 C. 8 D. 945设无向图的顶点个数为n，则该图最多有_条边。An-1 Bn(n-1)/2 C n(n+1)/2 D0 En246下列哪一种图的邻接矩阵是对称矩阵？_A有向图 B无向图 CAOV网 DAOE网47在有向图的邻接表存储结构中，顶点v在链表结点中出现的次数是_。A顶点v的度 B顶点v的出度 C顶点v的入度

32、 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. nlog2n52 图的广度优先搜索类似于树的( )遍历。A. 先序     B. 中序

33、     C. 后序      D. 层次53 下面( )方法可以判断出一个有向图是否有环(回路)。A. 深度优先遍历 B. 拓扑排序 C. 求最短路径 D. 求关键路径54 在有向图G的拓扑序列中，若顶点Vi在顶点Vj之前，则下列情形不可能出现的是( )。 A. G中有弧<Vi，Vj> B. G中有一条从Vi到Vj的路径 C. G中没有弧<Vi，Vj> D. G中有一条从Vj到Vi的路径55若查找每个元素的概率相等，则在长度为n的顺序表上查找到表中任一元素的平均查找长度为_。 A

34、. n B. n+1 C. (n-1)/2 D. (n+1)/256折半查找的时间复杂度_。A.(n*n) B.(n) C. (nlog2n) D. (log2n)57采用分块查找时，数据的组织方式为_。. 把数据分成若干块，每块内数据有序. 把数据分成若干块，块内数据不必有序，但块间必须有序，每块内最大(或最小)的数据组成索引表. 把数据分成若干块，每块内数据有序，每块内最大(或最小)的数据组成索引表. 把数据分成若干块，每块(除最后一块外)中的数据个数相等58二叉排序树的查找效率与二叉排序树的 (1) 有关，当 (2) 时，查找效率最低，其查找长度为n。(1).高度 .结点的个数.形状 .

35、结点的位置(2).结点太多.完全二叉树.呈单叉树 .结点的结构太复杂59在一棵AVL树(平衡二叉树)中，每个结点的平衡因子的取值范围是_。 A. -11 B. -22 C. 12 D. 0160在平衡二叉树中插入一个结点后造成了不平衡，设最低的不平衡结点为A,并已知A的左孩子的平衡因子为0,右孩子的平衡因子为1,则应作( ) 型调整以使其平衡。A. LL B. LR C. RL D. RR61下面关于折半查找的叙述正确的是( ) 。A. 表必须有序，表可以顺序方式存储，也可以链表方式存储 B. 表必须有序且表中数据必须是整型，实型或字符型C. 表必须有序，而且只能从小到大排列 D. 表必须有序

36、，且表只能以顺序方式存储62从空二叉排序树开始，用下列序列中的（ ），构造的二叉排序树的高度最小。A. 45，25，55，15，35，95，30B. 35，25，15，30，55，45，95C. 15，25，30，35，45，55，95D. 30，25，15，35，45，95，5563下面关于哈希查找的说法正确的是( ) 。A哈希函数构造的越复杂越好，因为这样随机性好，冲突小 B除留余数法是所有哈希函数中最好的 C不存在特别好与坏的哈希函数，要视情况而定D若需在哈希表中删去一个元素，不管用何种方法解决冲突都只要简单的将该元素删去即可64将10个元素哈希到100000个单元的哈希表中，则( )产

37、生冲突。A. 一定会 B. 一定不会 C. 仍可能会65下列排序算法中，_算法是不稳定的。A. 起泡排序 B. 直接插入排序 C. 归并排序D. 快速排序66在下列排序算法中，占用附辅助空间最多的是_。A.归并排序 B. 快速排序 C .堆排序 D.希尔排序67高度为h(h>0)的满二叉树有_个结点。A. 2h-1 B. 2h+1 C. 2h-1+1 D.2h+1-168. 设无向连通图的顶点个数为n，则该图最少有( )条边。 An-1 Bn(n-1)/2 C n(n+1)/2 D069.下列说法正确的是_A.链表在物理存储空间上一定是离散的。B.顺序表在物理存储空间上一定是连续的。C.

38、堆栈的物理存储空间结构一定是离散的。 D.队列的物理存储空间结构一定是连续的。70. 下列排序算法中，其中( )是稳定的。 A. 堆排序，冒泡排序 B. 快速排序，堆排序 C. 简单选择排序，归并排序 D. 归并排序，冒泡排序71. 对n个元素进行快速排序，如果初始数据已经有序，则时间复杂度为( )。AO(1)BO(n)CO(n2)DO(log2n)72. 以下时间复杂度不是O(nlog2n)的排序方法是( )。A堆排序 B直接插入排序C二路归并排序D快速排序73. 若需在O(nlog2n)的时间内完成对数组的排序，且要求排序是稳定的，则可选择的排序方法是( )。A快速排序B. 堆排序C. 直

39、接插入排序D. 归并排序74. 一组记录的关键字为46,79,56,38,40,84，则利用快速排序方法，以第一个记录为轴，得到的一次划分结果为( )。 A38,40,46,56,79,84 B. 40,38,46,79,56,84C40,38,46,56,79,84 D. 40,38,46,84,56,7975. 一组记录的关键字为45,80,55,40,42,85，则利用堆排序方法建立的初始大根堆为( )。A80,45,50,40,42,85 B. 85,80,55,40,42,45C85,80,55,45,42,40 D. 85,55,80,42,45,4076. 在待排序的元素序列基本

40、有序的前提下，效率最高的排序方法是( )。A. 直接插入排序B. 快速排序C. 简单选择排序D. 归并排序77. 就排序算法所用的辅助空间而言，堆排序、快速排序、归并排序的关系是( )。A. 堆排序<快速排序<归并排序 B. 堆排序<归并排序<快速排序C. 堆排序>归并排序>快速排序 D. 堆排序>快速排序>归并排序78. 一个序列有10000个元素，若只想得到其中前10个最小元素，最好采用( )方法。A二路归并排序B直接选择排序CShell排序D堆排序三、解答题1进栈的先后顺序为A,B,C,D,E,F，试判断下列两种出栈顺序是否有可能。（1）B

41、,A,D,E,C,F (2)B, C, F, D, A, E2进栈顺序为A，B，C，D，且进栈过程中可以出栈，写出所有可能的出栈顺序。3设稀疏矩阵(1)画出其三元组表形成的压缩存储表。(2)画出其十字链表形成的压缩存储表。4图的邻接表如图所示： vertex firstedgeV0 1 3 V1 0 2 3 V21 V3 0 1 图 邻接表 (1)写出从顶点V0出发进行深度优先搜索的遍历序列。(2)写出从顶点V0出发进行广度优先搜索的遍历序列。答案：V0V1V2V3，V0V1V3V25写出下图所示的四个拓扑序列。V0v1V5V2V6V3V41 答案：V0V1V5V2V6V3V4，V5V1V0V

42、6V2V3V4，V0V1V5V2V3V6V4。166对于下图所示的连通图，请用Prim算法构造其最小生成树。521919141126618 解： (1) Prim算法的基本思想：从某个顶点集(初始时只有一个顶点)开始，通过加入与其中顶点相关联的最小代价的边，来扩大顶点集合，直至将所有的顶点包含其中。其最小生成树的构造过程如图所示(假设从顶点V1开始)。(b)(c)(d)(e)14141614165161456(a)14111656利用Prim算法生成最小生成树过程7假定一个线性序列为 (30，25，40，18，27，36，50，10，32，45 )，按此序列中的元素顺序生成一棵二叉排序树，并求

43、出在该二叉排序树上查找成功时的平均查找长度。解：二叉树的建立过程是不断执行元素插入操作的过程，直到序列中的元素插完为止。该二叉排序树建树过程如图8.3所示：30254030253040302518403025182740302518273630251827364050302518273640501030251827364050103230251827364050103245图8.3 二叉排序树的建树过程示意图查找成功时的平均查找长度 ASLsucc=(1+2*2+3*4+4*3)/10=29/10=2.98已知二叉树左右子树都含有m个结点，当m=3时，试构造满足如下要求的所有二叉树。(1) 左

44、右子树的先序与中序序列相同。(2) 左子树的中序与后序序列相同，右子树的先序与中序序列相同。解：该题目由上题引申得到，主要考查二叉树的结构和遍历的性质，如图6.7所示。 (1) (2) 图6.79设电文由6个字符A，B，C，D，E，F组成，它们在电文中出现的次数分别为：10,4,8,3，2,7。试画出用于编码的哈夫曼树，并列出每个字符的编码。分析与解答：该题目主要考查哈夫曼树及应用。对应的哈夫曼树如图6.18所示： 图6.18对应的哈夫曼编码为 A(10)：11 B(4)：100 C(8)：01 D(3)：1011 E(2)：1010 F(7)：0010设有一个关键字的输入序列 55, 31,

45、 11, 37, 46, 73, 63, 02, 07 , (1) 从空树开始构造平衡二叉树, 画出插入46之前的平衡二叉树。(2) 46插入之后哪一个结点平衡因子失效？属于4种调整方式中哪一种？(3) 画出插入46并调整之后的平衡二叉树。解：（1）55553155311155311111315537 LL55371131465537113146553711314673 LR RR5537113146735537113146736355371131467363 RL113146630255377307113146630255377307 LR11. 已知一棵二叉树的中序序列和后序序列分别为BD

46、CEAFHG和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)