1.线性链表不具有的特点是()

1、1 .线性链表不具有的特点是（第3题图第4题图A .随机访问B.不必事先估计所需存储空间大小C.插入与删除时不必移动元素D .所需空间与线性表长度成正比4.写出右上图中的一个拓扑有序序列2 .设一个栈的输入序列为1 , 2, 3, 4,则输出序列不可能是（）。A . 1,2, 3, 43.下列排序算法中， 位置上。 A .归并B . 4, 3, 2, 1C . 1,3, 2, 4D . 4,1,2,3）排序在每趟结束后不一定能选出一个元素放到其排好序的最终B .冒泡C.选择D .堆5. 对于顺序存储的线性表，访问结点和删除结点的时间复杂度分别为6. 平衡二叉树上所有结点的平衡因子只可能是 4.

2、下列序列中，（）是执行第一趟快速排序后得到的序列（排序的关键字类型是字符串）。A. da, ax, eb, de, bb ff ha, gcB . cd, eb, ax, da ff ha, gc, bb7.假定对线性表 R1.60进行分块查找，共分为10块，每块长度等于6。若假定查找索引表和块均用顺序查找的方法，则查找每一个元素的平均查找长度为&将一棵有100个结点的完全二叉树从根这一层开始，每一层上从左到右依次对结点进行编 号，根结点的编号为1，则编号为37的双亲结点编号为C . gc, ax, eb, cd, bb ff da, ha5.设有一个10阶的对称矩阵 A1010 存入

3、一维数组 B中，A00存入B0中，则D . ax, bb, cd, da ff eb, gc, ha，采用压缩存储方式按行将矩阵中下三角部分的元素A85在 B中（ ）位置。6.A. 32B . 33F面哪一种图的邻接矩阵肯定是对称矩阵A.有向图B.无向图C .)。AOV41D. 65D. AOE 网具有2008个结点的二叉树，其深度至少为A . 9B . 10C .9.设有一个字符串 s='scienee'，其非空子串的数目是 _10 .有n个顶点的强连通有向图 G至少有条弧。1 . 一棵二叉树的先序序列和中序序列分别如下，先序序列：ABCDEFGHIJ中序序列：CBDEAGI

4、HJF画出该二叉树。（3分） 写出其后序序列。（3分）(11D. 12（1）（2）2.给出用Kruskal算法构造下列带权图的最小生成树的过程。关键路径是边表示活动的网（ AOE网）中的（A .从源点到汇点的最长路径B .从源点到汇点的最短路径C .最长的回路D .最短的回路一个广义表为（a, （a,b）, d, e, （i,j） ,k），则该广义表的长度为（）。A.不确定B . 8C . 5D . 610 .设循环队列中数组的下标范围是0n -，其头尾指针分别为f和r，则其元素个数为（A . r -fB . r -f + 1 C . （ r -f ） mod n + 1 D . （ r -f

5、 + n ） mod n1. 算法具有的五个重要特性是：有穷性，确定性， ，输入和输出。2. 一组记录的关键字为（45,80,55,40,42,85 ），则利用堆排序的方法建立的初始堆为3.对如下无向图G,从结点V1出发，写出一个按深度优先遍历图的结点序列:3.已知一个长度为 12 的表（6，8，4，12，2，10，7，3，9，1，11，5）。（1）将表中的元素依次插入到一个初始为空的二叉排序树中，画出该二叉排序树并求其在等 概率下的平均查找长度。（3分）（2）若先对表中的记录排序，构成有序表后再对其进行折半查找，画出判定树并求其在等概 率下的平均查找长度。（3分）4.已知哈希表地址空间为0.

6、10，哈希函数为 H（key） = key MOD 11，采用链地址法处理冲突,将下面数据序列依次插入该哈希表中，并求出在等概率下查找成功时的平均查找长度。12， 24， 1， 34， 38， 44， 27， 22。5.假定用于通信的电文仅由8个字母a，b，c，d，e，d，f，g，h组成，各个字母在电文中出现的频率分别为5，23，3，6，10，11，36，4。要求：11/ 6'.(1 )以这些频率作为叶子结点的权值构造Huffman树。(2分)9.在有n个叶子结点的哈夫曼树中，其结点总数为A.不确定B.2 n-1C.2nD.2 n+1(2)试为这8个字母设计不等长 Huffman编码。

7、(2分)10.与单链表相比，双向链表的优点之一是A .插入、删除更简单B.可以进行随机访问C .可以省略表头指针或表尾指针D.访问前后相邻结点更方便fAbdhceg(3)计算出电文总长度。(2分)1. 有两个不带头结点的单循环链表，链表头指针分别为 链表a之后，链接后的链表仍保持循环链表形式。2. 试编写一个计算二叉树的叶子结点数的算法。要求二叉树采用链式存储结构。3. 请写出监视哨设在高下标端的插入排序算法。06 21. Prim算法适合求 的网的最小生成树，而Kruskal算法适用于求的最小生成树。2.循环单链表L为空的条件是 。3.在对队列中，新插入的网a和b。编写一个过程将链表b链到的

8、元素只能插入到4 .平衡二叉树上所有结点 的平衡因子只可能是。5.个有序表1 , 3, 9, 12, 32, 41, 45, 62, 75, 77, 82, 95, 99, 当采用折半查找法查找关键字为82的元素时，次比较后查找成功。6设二维数组A610,每个数组元素占4个存储单元，若按行优先顺序存放数组元素，A00的存储地址是860,则A35的存储地址是1.具有n(n>0)个结点的完全二叉树的深度为7可以进行拓扑排序的- 定是A. log2nB. log2nC. log2n +1D. log2n+12. 一个栈的进栈序列是a, b, c, d, e,则栈的不可能的输出序列是&求

9、单链表长度算法的时间复杂度是A.abcdeB.edcbaC.decbaD.dceab3.数据在计算机存储器内表示时，物理地址与逻辑地址相同且连续，称之为A.存储结构B.逻辑结构9.在直接插入排序、希尔排序、直接选择排序、快速排序、堆排序和归并排序中，平均比较次 数最少的排序方法是1.已知一个二叉树的中序遍历序列为DGBAECF,后序遍历序列为 GDBEFCA,请给出:C.顺序存储结构D.链式存储结构4.对二叉排序树的左子树中所有结点与右子树中所有结点的关键字大小关系是A.小于B.大于(3) 画出该二叉树。(3分)(4) 写出其后序序列。(3分).对关键字序列11,78,10,1,3,2,4,2

10、1构造哈希表，取散列地址为 HT0.10，散列函数为 H(K) =K % 11,试用线性探查法冲突，画出相应的哈希表，并分别求查找成功和不成功时的平均查 找长度。C.等于D.不小于5.按照二叉树的定义，具有3个节点的二叉树3.已知关键字序列503 , 87, 512, 61, 908, 170, 897, 275, 653, 462，采用快速排序A.2B.3C.4D. 5算法对该序列作升序排序时的每一趟的结果。6.广义表(a)的表尾是A . a7 .设有两个串P和q，求在B. (a)C.()q在p中首次出现的位置的运算称为D.(a)A.模式匹配B.连接C.求子串D.求串长8.引入二叉线索树的目

11、的是4.从一棵空树开始，逐个读入并插入下列关键字:40 , 28, 6, 72, 100,3, 54, 1, 80, 91, 38请首先建立二叉排序树，然后删除节点72,并给出删除节点 72后的二叉树。A 加快查找结点的前驱或后继的速度B.为了能在二叉树中方便的进行插入与删除C .为了能方便的找到双亲D .使二叉树的遍历结果唯一5.给定权集 W=2,3,4,7,8,9,试构造关于W的一棵哈夫曼树，并求带权路径长度WPL。1. 有一个有序单链表（从小到大排序），表头指针为L,设计一个算法向该单链表中插入一个 元素为x的结点，并使插入后链表仍然有序。2. 二叉树采用链式存储结构，3.二叉树采用链式

12、存储结构，试编写算法求二叉树的深度。试设计一个按层次顺序（同层自左向右）遍历二叉树的算法。答案一、选择题（每小题1.A2.D3.A2分,共4.A20分)5.C6.B7.C8.A9.C10.D20分)（1分）3. （1） 二叉排序树为:1/、5 712(1 分)911等概率下平均查找长度ASL = (1+2*2+3*4+4*3+5*2 ) /12 = 13/4 = 3.25(2)排序后进行折半查找的判定树为：6、98 10 12ASL = (1+2*2+3*4+4*5 ) /12 = 37/12 3.08第1页洪3页)xKK V25等概率下平均查找长度（2 分）（1分）(2 分)(1 分)2分，

13、共2. (85,80,55,40,42,45)二、填空题（每小题1.可行性4. 1,2, 3, 5, 6, 4 （答案不惟一）7. 98. 189.263 . V1, V2, V3, V5 ,V4,V6, V7, V8 (答案不惟一) 5.0(1)和 0( n)10. n6. -, 0, 14.哈希函数值为：（1分）H（12）=1H（24）=2H（1）=1哈希表为：（3分）H(34)=1H(38)=5H(44)=0H(27)=5H(22)=0三、解答下列各题 （每小题6分，共30分）1 .该二叉树为（3分）：/ A、B ；,FC/D后序序列:CEDBIJHGFAE AI J(3分)2. V1V

14、23V6V1V2V2(2 分)V4(2 分)V5V6V4V65. (1) Huffman 树为：(2 分)V2VV6V4 2 V5(1 分)V1 3VVV6V4 2 V52 V5(1 分)98172223363/ 10 11 11/、3456（2）其huffman编码为 （2分）注：此题答案不唯一，只要满足哈夫曼编码的要求都可。abcdEfgH1001(2 分)先令指针P指向链表a的第一个结点找到链表a的最后一个结点/将链表b链到a的最后一个结点之后第2页(共3页)令指针P指向链表b的第一个结点找到链表b的最后一个结点令链表b的最后一个结点指向合并后的链表的表头(2) Typedef stru

15、ct BiTNodeTelemT ype data;Struct BiTNode *lchild, *rchild;BiTNode, *BiTree;void leaf(BiTree T) /采用二叉链表存贮二叉树，n为全局变量，用于累加二叉树的叶子结点的个数。本算法在先序遍历二叉树的过程中，统计叶子结点的个数第一 次被调用时，n=0if(T) /若二叉树为空，结束返回/若二叉树不为空，在先序遍历二叉树的过程中，统计叶子结点的个数if(T->lchild=null &&T->rchild=null) n=n+1;leaf(T->lchild);leaf(T-&

16、gt;rchild);/if/leaf一、选择题(每小题1分，1-5C D CBD6-10 C A ADD二、填空题(每空1. 边稠密，边稀疏2. L-> next=L;3. 队尾4. -1, 0, 15. 46. 10007. 无环图8. 0( n)9. 快速排序2分，共三、解答题(每小题1.(1) 二叉树是：6分，共 10 分)共30分)20分)(3)电文总码数为 4*5+2*23+4*3+4*6+3*10+3*11+2*36+4*4=253四、算法设计(每小题10分，共30分) 说明：每小题中：1. 思路正确2. 算法正确3. 算法完整(1) typedef struct LNod

17、e ElemT ype data; struct LNode *n ext; LNode, *L in kList;void Connect( Lin kList a, Lin kList b ) 将循环链表b链在循环链表a之后的算法，链表 a和b均不带头结点 Lin kList p;p=a;while( p->n ext<>a) p = p->n ext;p->n ext=b;P=b;while( p->n ext<>b) p = p->n ext;p->n ext=a;(3)typedef struct KeyT ype key;

18、InfoType otheri nfo;RedTy pe;typ edef struct RedTy pe rMAXSIZE+1;int len gth;SqList;void Insert_Sort1(SqList &L)/监视哨设在高下标端的插入排序算法 k=L .len gth;for(i=k-1;i;-i) /从后向前逐个插入排序if(L.ri.key>L.ri+1.key)L.rk+1.key=L.ri.key; / 监视哨for(j=i+1;L.rk+1.key>L.rj.key;+j)L.rj-1=L.rj; / 前移L.rj-1=L.rk+1; / 插入/l

19、n sert_Sort1(2)后序序列为:28384054721008091（4 分）（4分）GDBEFCA （2 分）删除72后:40282.解：首先求出散列地址，据此得到哈希表见下图。54381001178132421 1100123689104578091（2 分）查找成功的平均比较次数为：ASL = (1 + 1+ 2 + 1 + 3+2+ 8 + I) / 8= 2.375查找不成功的平均查找长度为：5.构造的哈夫曼树为:33ASLunsucc = （8 + 7+ 6+ 5+ 4 + 3+ 2+ 1 + 1 + 1 + 9） /11 4.27318153.每趟快速排序的结果如下:4628727561170 503 8971708727561 46261871702756187908653512512653897908653排序后：61 87 170 275 462 503 512 653 897 9085124.二叉排序树:加权路径长度WP