数据结构复习题.docx

1、数据结构复习题考试时间： 2014年 1月10日(星期五)14时30分16时30分考试教室安排： B413考试方式：闭卷笔试考试成绩卷面(60)平时作业(40)考试题型(参考）：1、选择(20分)2、填空(20分)3、综合应用(60分)4、算法设计(30分)题型1 单选题 （10题，2分/题，20分）2 填空题 （5题，4分/题，20分）3 应用题 （6题，10分/题，60分）4 附加题 （2题，15分/题，30分）（写C函数）题型1 单选题 （10题，2分/题，20分）如：存取数据采用先进先出原则的是（ ）。A、线性表 B、字符串 C、栈 D、队列2 填空题 （5题，4分/题，20分）如：循

2、环队列，head,tail分别指向队头，队尾，最大长度n，判队满的条件为 。3 应用题 （6题，10分/题，60分）如：假设对一段电文“abcdcbcacab”进行Huffman编码。画出对应的Huffman树，并写出每个字符的Huffman编码。4 附加题 （2题，15分/题，30分） （写C函数）如：哈希表用拉链法解决冲突，结构如下：#define LEN 32struct node int data; struct node *next; ;struct node *HashTab LEN ;写哈希函数int hash( int key )。（5分）写函数struct node *src

3、h( int key)，查找key。若找到，返回其结点指针；否则将其插入表中再返回其结点指针。(10分)一、线性结构（包括：表、栈、队、串、数组、广义表）1. 假设有二维数组A79，每个元素用相邻的6个字节存储，存储器按字节编址。已知A的起始存储位置（基地址）为1000，末尾元素A68的第一个字节地址为多少？若按列存储时，元素A47的第一个字节地址为多少？答： 末尾元素A68的第一个字节地址1000（7行9列1）6B1000626=1372 按列存储时，元素A47的第一个字节地址1000（7列7行4）6B1000536=1318 2. 在KMP算法中，已知模式串为LIUYULIUWENYU ，

4、请写出模式串的nextj函数值，并分析nextj函数值的大小与KMP算法的比较次数多少（或时间）有何关系，简单解释你的理由。答： nextj函数值=0111112341111 nextj函数值越大，比较次数越多； 反之，函数值越小，则比较次数越少，时间越快。2、非线性结构（包括：二叉树、树、图）1. 已知一棵二叉树的前序序列和中序序列分别为： ABDGCEFH和DGBAECHF，则该二叉树的后序序列是什么？ 答：既可先画树而得后序序列，也可直接推出后序序列，结果为：GDBEHFCA 总结二叉树的常见题有：1. 先序/中序/后序遍历的递归算法2. 如何判定一棵二叉树是二叉排序树?2. 假设字符a

5、,b,c,d,e,f的使用频度分别是0.07, 0.09, 0.16, 0.18, 0.23, 0.27，写出a,b,c,d,e,f的Huffman编码并计算其平均码长WPL。 (10分) 3. 设AH 8个字符出现的概率为: w=0.10, 0.16, 0.01, 0.02, 0.29, 0.10, 0.07, 0.25, 设计最优二进制码并计算平均码长。 (10分) 答：最优二进制码构造同上，WPL=2.59 解：（1）根据给定的n个权值构成n颗二叉树的集合F（2）在F中选取两颗根结点的权值最小的数作为左右子树构造一棵新的二叉树，且置新的二叉树的根结点的权值为其左、右子树上根结点的权值较小

6、者（3）在F中删除这两棵树，同时将新得到的二叉树加入F中（4）重复（2）和（3），直到F只含一棵树为止图1. 某无向图G的邻接表如下图所示。要求： 请画出该图G的逻辑结构图； 根据邻接表写出其深度优先遍历序列和广度优先遍历序列(设访问起点为v3)； 根据遍历结果，画出图G的深度优先和广度优先生成树。2. 下图为某无向图的邻接表，按教材算法分别写出深度优先搜索和广度优先搜索的结果，并画出逻辑结构图。3、查找和排序查找算法包括：顺序、折半、二叉排序树、散列排序算法包括：插入、交换、选择、基数1. 假设一有序表中有23个元素，现进行折半查找，则平均查找长度是多少？提示：现在n=23比较小，应当用穷举

7、法罗列：全部元素的查找次数为(122438485)89 ASL89/23=3.87 2. 已知一组关键字为（10，24，32，17，31，30，46，47，40，63，49），设哈希函数H（key）key MOD 7。 请解答：（1） 写出用链地址法处理冲突构造所得的哈希表；（2） 若查找关键字17，需要依次与哪些关键字进行比较？（3） 若查找关键字60，需要依次与哪些关键字比较？（4） 假定每个关键字的查找概率相等，求查找成功时的平均查找长度。 （10分）答： ASL 1. 82 3. 已知一组关键字为（10， 24， 32， 17， 31， 30， 46， 47， 40， 63， 49），

8、设哈希函数H（key）key MOD 13。请写出用线性探测法处理冲突构造所得的哈希表。 （10分）4. 欲将无序序列（23, 78, 12, 35, 69, 95, 11, 09, 35*, 48, 99, 26）中的关键码按升序重新排列，请写出快速排序第一趟排序的结果序列。另外请画出堆排序（小根堆）的初始堆。提示1：快速排序注意要按振荡式逼近算法来实现 ；第一趟排序的结果为：09， 11， 12， 23， 69， 95, 35, 78, 35*, 48, 99, 26 提示2：堆排序要从排无序堆开始，从最后一个非终端结点开始，自下而上调整,而且要排成小根堆。初始堆序列为： 09，23，11

9、， 35 ，48，26，12， 78 ，35*, 69, 99, 95 5. 采用一个辅助空间的堆排序算法对关键字序列46，37，65，96，75，11，25，48排序，如果排序结果为逆序，请给出初始堆。 答：最终逆序则意味着要建小根堆：11 37 25 48 75 65 46 966. 快速排序在什么情况下最快？什么样情况下最慢？在最慢的情况下请提出一种提高效率的解决办法。 答：快速排序在无序状态下最快，在基本有序（或逆序）下最慢。 提高效率的解决办法为，选中间位置的元素a 下标mid为中枢7. 设有1000个无序的元素，需排出前10个最大（小）的元素，你认为采用哪种排序方法最快？为什么？答

10、：堆排序第2章 线性表 线性表具有两种存储方式，即顺序方式和链接方式。现有一个具有五个元素的线性表L=23，17，47，05，31，若它以链接方式存储在下列100119号地址空间中，每个结点由数据（占2个字节）和指针（占2个字节）组成，如下图所示。其中指针X，Y，Z的值分别为多少？该线性表的首结点起始地址为多少？末结点的起始地址为多少？1、填空题1、向一个长度为n的顺序表中的第i个元素（0in-1）之前插入一个元素时，需向后移动 _个元素。2、在单链表中，要删除某一指定的结点，必须找到该结点的 _结点。3、访问单链表中的结点，必须沿着 _一次进行。4、在一个单链表中p所指结点之后插入一个s所指

11、结点时，应执行_和_的操作。二、选择题1、链表不具备的特点是 。 可随机访问任一节点 插入删除不须要移动元素 不必事先估计存储空间 所需空间与其长度成正比2、带头结点的单链表head为空的判定条件是 。 head=NULL head-next=NULL head-next=head head!=NULL3、如果最常用的操作是取第i个结点及其前驱，则采用 存储方式最节省时间。 单链表 双链表 单循环链表 顺序表第3章 栈与队列和栈类似，队列中亦有上溢和下溢现象。此外，顺序队列中还存在“假上溢”现象。因为在入队和出队的操作中，头尾指针只增加不减小，致使被删除元素的空间永远无法重新利用。因此，尽管队

12、列中实际的元素个数远远小于向量空间的规模，但也可能由于尾指针巳超出向量空间的上界而不能做入队操作。该现象称为假上溢。为充分利用向量空间。克服上述假上溢现象的方法是将向量空间想象为一个首尾相接的圆环，并称这种向量为循环向量，存储在其中的队列称为循环队列（Circular Queue)。 空队列的特征？ 约定：front=rear 队列会满吗？极易装满！因为数组通常有长度限制，而其前端空间无法释放。问：什么叫“假溢出” ？如何解决？答：在顺序队中，当尾指针已经到了数组的上界，不能再有入队操作，但其实数组中还有空位置，这就叫“假溢出”。解决假溢出的途径采用循环队列在循环队列中又出现了一个新问题：如何

13、判定队满和队空？ 由于入队时尾指针向前追赶头指针，出队时头指针向前追赶尾指针，故队空和队满时头尾指针均相等。因此，我们无法通过front=rear来判断队列“空”还是“满”。 解决此问题的方法至少有三种： 其一是另设一个布尔变量以区别队列的空和满；其二是少用一个元素的空间，约定入队前，测试尾指针在循环意义下加1后是否等于头指针，若相等则认为队满（注意：rear所指的单元始终为空）；其三是使用一个计数器记录队列中元素的总数（实际上是队列长度）2、顺序循环队列的队空和队满判断问题新问题：在循环队列中，空队特征是front=rear；队满时也会有front=rear；判决条件将出现二义性！解决方案有

14、三：使用一个计数器记录队列中元素个数（即队列长度）；判队满：count0 & rear=front 判队空：count=0加设标志位，出队时置,入队时置,则可识别当前front=rear属于何种情况判队满：tag=1 & rear=front 判队空：tag=0 & rear=front 少用一个存储单元判队满： front=(rear+1)%MaxQueueSize 判队空： rear=front1、单项选择题1、栈的特点是 B ，队列的特点是 A 。（A）先进先出 （B）先进后出2、栈和队列的共同特点是 C 。（A）都是先进后出 （B）都是先进先出（C）只允许在端点处插入和删除元素 （D）

15、没有共同点3、一个栈的进栈序列是a，b，c，d，e，则栈的不可能的输出序列是 C 。（A）edcba （B）decba （C）dceab （D）abcde4、若已知一个栈的进栈序列是p1，p2，p3， ，pn 。其输出序列为1，2，3，n ，若p3=1，则p1为 C 。（A）可能是2（B）一定是2（C）不可能是2 （D）不可能是35、设有一个空栈，栈顶指针为1000H（十六进制，下同），现有输入序列为1、2、3、4、5，经过PUSH，PUSH，POP，PUSH，POP，PUSH，PUSH后，输出序列是 3 ，栈顶指针是 8 。5、4、3、2、1 2、1 2、3 3、4 1002H 1004H

16、1005H 1003H6、一个队列的入对序列是若1，2，3，4，则队列的输出序列是 B 。（A）4，3，2，1 （B）1，2，3，4（C）1，4，3，2 （D）3，2，4，17、若用一个大小为6的一维数组来实现循环队列，且当前rear和front的值分别为0和3。当从队列中删除一个元素，再加入两个元素后，rear和front的值分别是 B 。（A）1和5 （B）2和4 （C）4和2 （D）5和1第4章 串一、选择题1、空串与空白串是相同的，这种说法 B 。 （A）正确 （B）不正确2、串是一种特殊的线性表，其特殊性体现在 D 。（A）可以顺序存储 （B）数据元素是一个字符（C）可以链接存储 （

17、D）数据元素可以是多个字符3、D 是C语言中”abcd321ABCD”的子串。（A）abcd （B）321AB（C）”abcABC” (D)”21AB”二、填空题1、两个串相等的充分必要条件是 。两个串的长度相等且对应位置的字符相同 2、空串是零个字符的串 ，其长度等于零 。3、空白串是由一个或多个空格字符组成的串 其长度等于其包含的空格个数 。4、模式串t=abaabcac”的next函数值序列为 -1 0 0 1 1 2 0 1 ，nextval函数值序列为 -1，0，-1，1，0，2，-1，1 。第5章 数组与广义表广义表L=（a，（b, c），进行GetTail(L）操作后的结果为（

18、）A、c B、b, c C、(b, c) D、(b, c) 第6章 树1、单项选择题1、由于二叉树中每个结点的度最大为2，所以二叉树是一种特殊的树，这种说法 B 。 （A）正确 （B）错误2、某二叉树的先序遍历序列和后序遍历序列正好相反，则该二叉树一定是 D 。 （A）空或只有一个结点 （B） 完全二叉树 （C）二叉排序树 （D） 高度等于其节点数3、深度为5的二叉树至多有 C 个结点。（A）16 （B）32 （C）31 （D）104、根据使用频率为5个字符设计的哈夫曼编码不可能是 D（A）111，110，10，01，00（B）000，001，010，011，1（C）100，11，10，1，0

19、 （D）001，000，01，11，10二、填空题1、树和二叉树的主要差别是(1. 树中结点的最大度数没有限制，而二叉树结点的最大度数为2；) (2. 树的结点无左、右之分，而二叉树的结点有左、右之分。) 2、深度为k的完全二叉树至少有 _(2的K-1次方)_ 个结点，至多有（2的k次方）-1 个结点，若按自上而下，从左到右次序给结点编号（从1开始），则编号最小的叶子结点的编号是（2的k-2次方）+1 _。 3、一棵二叉树的第i(i1)层最多有 (2的i-1次方) 个结点；一棵有n（n0）个结点的满二叉树共有(2的logn次方) 个叶子结点和 （2的logn次方）-1 个非叶子结点。1、已知二

20、叉树的先序、中序和后序序列分别如下，其中有一些看不清的字母用*表示，请构造出一棵符合条件的二叉树并画出该二叉树。先序序列是：*BC*FG中序序列是：CB*EAG*后序序列是：*EDB*FA2、将右图所示的树转化为二叉树，并写出先序遍历，中序遍历和后序遍历的结果。课后习题:1、假设对一段电文“abcdcbcacab”进行Huffman编码。画出对应的Huffman树，并写出每个字符的Huffman编码。2、假设字符a,b,c,d,e,f的使用频度分别是0.2, 0.4, 0.02, 0.1, 0.15, 0.13, 构造Huffman树，写出各字符的Huffman编码。3、树用孩子兄弟链接法存储

21、，结点结构为struct Node char data，struct Node *child，*brother；写C函数void PreOrder( struct Node *root )，先根遍历树。root是指向树根的指针。第7章 图 作业一、单项选择题1、一个n个顶点的无向图最多有 C 条边。 （A）n （B）n(n-1) （C）n(n-1)/2 （D） 2n2、在一个有向图中，所有顶点的入度之和等于所有顶点的出度之和的 B 倍。 （A）1/2 （B）1 （C）2 （D）43、关键路径是事件结点网络中 A 。 （A）从源点到汇点的最长路径 （B）最长的回路4、下面不正确的说法是 B 。A

22、、关键活动不按期完成就会影响整个工程的完成时间B、任何一个关键活动提前完成，将使整个工程提前完成C、所有关键活动都提前，则整个工程提前完成D、某些关键活动若提前完成，将使整个工程提前完成。二、填空题1、一个图的邻接矩阵表示法 表示法是惟一的，而邻接表 表示法是不惟一的。2、在有n个顶点的有向图中，每个顶点的度最大可 达 2（n-1） 。1、设有向图G如下图所示，试给出：（1）该图的邻接矩阵；（2）该图的邻接表；（3）从V1出发的“深度优先”遍历序列；（4）从V1出发的“广度优先”遍历序列。2、对下图的AOE网，求出：（1）每个事件的最早发生时间和最迟发生时间；（2）每个活动的最早开始时间和最迟

23、开始时间；（3）画出关键活动组成的图。对哪些活动提速，可使整个工期提前。课后习题:1、有向网N=V,E，V=0,1,2,3,4，E=， ，E中每个元组的第三个元素表示权。 (1)、画出该网。 (2)、写出该网的邻接矩阵。 (3)、求关键路径，写出计算过程。 （4）用迪杰斯特拉（Dijkstra）算法求最短路径，写出顶点0到其它各顶点的最短路径长度、路径及产生过程。 2、(1)、自定义无向图的邻接表存储结构Graph。 (2)、基于上述图结果，写函数void Kruskal(Graph g)，用克鲁斯卡尔算法求最小生成树，并输出树的生长过程。期末考试题型：1、算法编程题（35分）2、算法编程题（

24、35分）3、算法编程题（30分）共100分4、附加题：算法编程题（30分）期末考试是上机机考：题型跟我们平时的实验题型描述，输入、输出一致。分为必做题共3题和附加题1题。题目难度2题较易，1题相对适中。附加题较难。题目内容都是13个实验及所做的练习题中的相关内容！题型：1、问题描述 2、算法描述 3、输入描述4、输入样本 5、输出描述 6、输出样本1、问题描述 给出初始数据采用冒泡排序（或简单选择排序或直接插入排序，将数据从小到大排成有序序列2、算法 通过一趟排序，将待排序记录分割成独立的两部分，其中一部分记录的关键字均比另一部分记录的关键字小，则可分别对这两部分记录进行排序，以达到整个序列有

25、序3、输入每个样本分1行：第一行：第一个数字m表示样本数目，其后跟m个样本4、输入样本8 12 21 1 2 3 4 5 65、输出每一趟快速排序的结果（为一行，包括原始序列）6、输出样本12 21 1 2 3 4 5 66 5 1 2 3 4 12 21 1 2 3 4 5 6 12 21本学期必做的13个实验1 顺序表实验 （易）2 单链表实验 （易）3 堆栈应用括号匹配实验 4 串应用KMP算法实验 5 Huffman编码的设计与应用实验 （难） 6 图的深度优先搜索实验 （较难） 7 最短路径实验 （较难）8 顺序查找实验 （易）9 折半查找实验 （易）10 二叉排序树实验 （难）11 哈希查找实验 （难） 12 快速排序实验 （易）13 希尔排序实验 （易）