22.在具有n个单元、且采用顺序存储的循环队列中，队满时共有___________个元素。
23．假设为循环队列分配的向量空间为Q[20]，若队列的长度和队头指针值分别为13和17，则当前尾指针的值为______。
24.空串的长度是________；空格串的长度是________。
25.对于顺序存储结构的二维数组，通常采用___________两种存放方式存储数据元素。 26．若用一个大小为6的数组来实现循环队列，且当前rear和front的值分别为0和3，当从队列中删除一个元素，再加入两个元素后，rear和front的值分别为__________。
27．假设按行优先顺序将一个20阶的三对角矩阵A压缩存储在一维数组Q中，其中Q[0]存放矩阵的第1个元素a1,1，那么矩阵元素a3,4在Q中的存储位置k=_______。
28. 设栈S和队列Q的初始状态为空，元素e1，e2，e3，e4,e5和e6依次通过栈S，一个元素出栈后即进队列Q，若6个元素出队的序列是e2，e4，e3,e6,e5,e1则栈S的容量至少应该是____________。
29．设一棵二叉树中度为2的结点数为10，则该树的叶子数为________________。
30.在一棵度为3的树中，度为2的结点个数是1，度为0的结点个数是6，则度为3的结点个数是________。
31.对于一棵具有n个结点的二叉树，当进行链接存储时，其二叉链表中的指针域的总数为2n个，其中________个用于链接孩子结点。
32. 已知完全二叉树T的第5层只有7个结点，则该树共有____________个叶子结点。 33．在含100个结点的完全二叉树中，叶子结点的个数为___________。 34．在含有n个顶点的连通图中，任意两个不同顶点之间的简单路径的最大长度为_______。 35．一个具有10个顶点的完全无向图中有_______条边。 36．含n个顶点的无向连通图中至少含有______条边。 37.有向图G用邻接矩阵A［1··n，1··n］存储，其第i列的所有元素之和等于顶点Vi的________。
38.对于n个顶点的生成树，其边的个数为__________ 。
39．顶点数为n、边数为n(n-1)/2的无向图称为_____________。
40．用_______排序方法对关键字序列（20，25，12，47，15，83，30，76）进行排序时，前三趟排序的结果为：
20，12，25，15，47，30，76，83 12，20，15，25，30，47，76，83 12，15，20，25，30，47，76，83
41.快速排序最好情况下的时间复杂度为________，最坏情况下的时间复杂度为________。 42.利用筛选法将关键字序列(37，66，48，29，31，75)建成的大根堆为(________)。 43．在待排序的n个记录中任取一个记录，以该记录的键值作为标准，将所有记录分为两组，使得第一组中各记录的键值均小于或等于该键值，第二组中的各记录的键值均大于该键值；然后将该记录排在两组中间。再对所分成的两组分别使用上述方法，直到所有记录都排在适当位置为止。这种排序方法称为________________。
44．哈希表常用的两类解决冲突的方法是_______和_______。 45．一棵平衡二叉树中任一结点的平衡因子只可能是_______。
46.对二叉排序树进行________遍历，可得到排好序的递增结点序列。 47．5阶B树的根结点至少含有_________个关键字。
48. 产生冲突现象的两个关键字称为该散列函数的____________。
49．长度为L的顺序表，采用设置岗哨方式顺序查找，若查找不成功，其查找长度为________________。
50．若序列中关键字相同的记录在排序前后的相对次序不变，则称该排序算法是________
的。
三、判断题
9
1．数据的逻辑结构是指各数据元素之间的逻辑关系，是用户根据应用需要建立的。 2．存储相同数据元素，顺序存储比链式存储少占空间。
3．线性链表存储空间不一定是连续，且前件元素一定存储在后件元素的前面。 4．顺序表和一维数组一样，都可以按下标随机(或直接)访问。 5．二维数组可以视为数组元素为一维数组的一维数组。
6．在一个顺序存储的循环队列中，队头指针指向队头元素的后一个位置。 7．在用单链表表示的链式队列中．队头在链表的链尾位置。 8．用非递归方法实现递归算法时一定要使用递归工作钱。 9．凡是递归定义的数据结构都可以用递归算法来实现它的操作。
10．在一棵二叉树中，假定每个结点只有左子女，没有右子女，对它分别进行中序遍历和后序遍历，则具有相同的结果。
11．在二叉搜索树中，若各结点的搜索概率不等，使得搜索概率越小的结点离树根越近，则得到的是最优二叉搜索树。
12.用邻接矩阵法存储一个图时，在不考虑压缩存储的情况下，所占用的存储空间大小只与图中结点个数有关，而与图的边数无关。
13.邻接表法只能用于有向图的存储，而相临矩阵法对于有向图和无向图的存储都适用。(错) 14.任何有向网络(AOV-网络)拓扑排序的结果是唯一的。 15．对于AOE网络，加速任一关键活动都能使整个工程提前完成。 16．直接选择排序是一种稳定的排序方法。
17．当向一个小根堆(最小堆)中插入一个具有最小值的元素时，该元素需要逐层向上调整，直到微调整到堆顶位置为止。 18．进行折半查找的表必须是顺序存储的有序表。
19．一棵m阶B树中每个结点最多有m个关健码，最少有2个关键码。
20．在散列法中采取开散列(链地址)法来解决冲突时，其装载因子的取值一定在(0，1)之间。
四、应用题
1. 假设以数组seqn［m］存放循环队列的元素，设变量rear和quelen分别指示循环队列中队尾元素的位置和元素的个数。
(1)写出队满的条件表达式； (2)写出队空的条件表达式；
(3)设m=40,rear=13,quelen=19,求队头元素的位置； (4)写出一般情况下队头元素位置的表达式。 2．某广义表的表头和表尾均为（a,(b,c)），画出该广义表的图形表示。 3.已知某二叉树的顺序存储结构如图所示，试画出该二叉树。 A B C D E F G 4．已知二叉树的先序序列和中序序列分别为HDACBGFE和ADCBHFEG。 （1）画出该二叉树；
（2）画出该二叉树的中序线索链表的存储表示。 （3）画出与（1）求得的二叉树对应的森林。
5．某二叉树的先根遍历序列为ABIJCDFGHE，中根遍历序列为IJBADGFHCE，试画出该二叉树，并写出它的后序遍历序列。
6．已知树如右图所示，
（1）写出该树的后序序列； （2）画出由该树转换得到的二叉树。
10
7.假设通信电文使用的字符集为{a,b,c,d,e,f,g}，字符的哈夫曼编码依次为：0110，10，110，111，00，0111和010。
(1)请根据哈夫曼编码画出此哈夫曼树，并在叶子结点中标注相应字符；
(2)若这些字符在电文中出现的频度分别为：3，35，13，15，20，5和9，求该哈夫曼树的带权路径长度。
8．已知带权图的邻接表如下所示，其中边表结点的结构为：
依此邻接表从顶点C出发进行深度优先遍历。 （1）画出由此得到的深度优先生成树；
（2）写出遍历过程中得到的从顶点C到其它各顶点的带权路径及其长度。
9.假设用迪杰斯特拉(Dijkstra)算法求下列图中从顶点a到其余各顶点的最短路径，按求解过程依次写出各条最短路径及其长度。
10.试给出下图的邻接矩阵和邻接表表示。
11.已知如图所示，用普里姆（prim）算法从顶点A开始求最小生成树。在算法执行之初，顶点的集合U={A，B}，边的集合TE={（A，B）}。试按照最小生成树的生成过程，分步给出加入顶点和边以后的集合U和TE的值。
12．用二分查找法对一个长度为10的有序表进行查找，填写查找每一元素需要的比较次数。（8分）
11
元素下标 比较次数
1 2 3 4 5 6 7 8 9 10
13．从空树起，依次插入关键字37，50，42，18，48，12，56，30，23，构造一棵二叉排序树。
（1）画出该二叉排序树；
（2）画出从（1）所得树中删除关键字为37的结点之后的二叉排序树。 14.已知某二叉排序树10个结点的值依次为1~10，其结构如图所示，试标出该二叉树各结点所对应的具体值。
15．上图所示二叉树是否为平衡二叉树？若是，说明理由；若不是，将其转换为平衡二叉树。
16．对下列关键字序列（33，25，48，59，36，72，46，07，65，20）构造表长为19的散列表。假设散列函数为h(key)=key,用开放地址法解决冲突，探查序列为d=h(key),d+12,d-12，d+2 2,d-2 2,d+32，d-32，?，等等。 （1）画出该散列表；
（2）计算该散列表的装填因子α；
（3）求出等概率情况下查找成功的平均查找长度ASL。
17.已知散列函数为H(key)=key%7，散列表长度为7(散列地址空间为0..6)，待散列序列为：(25，48，32，50，68)。要求：
(1)根据以上条件构造一散列表，并用线性探测法解决有关地址冲突； (2)若要用该散列表查找元素68，给出所需的比较次数。
18.已知一组键值序列（22，24，26，25，27，29，21，28），试给出采用直接插入排序法对该组序列作升序排序的每一趟结果。
19.已知一组键值序列为(38，64，73，52，40，37，56，43)，试采用快速排序法对该组序列 作升序排序，并给出每一趟的排序结果。
20.已知一组键值序列(26，21，32，56，78，89，90)，试采用二路归并排序法对该组序列 作升序排序，并给出每一趟的排序结果。
21.画出对应于序列{10，20，7，75，41，67，3，9，30，45}的初始堆（堆顶元素取最小值）。
22．L为一个带头结点的循环链表。函数f30的功能是删除L中数据域data的值大于c的所有结点，并由这些结点组建成一个新的带头结点的循环链表，其头指针作为函数的返回值。请在空缺处填入合适的内容，使其成为一个完整的算法。 LinkList f30(LinkList L, int c) {
LinkList Lc,p,pre; pre=L;
12
相关推荐：
loading