下载文档原格式
数据结构自考试题和答案一、单项选择题（每题2分，共20分）1. 在数据结构中，算法的时间复杂度是指（）。
A. 执行算法所需要的时间B. 执行算法所需要的指令条数C. 算法执行过程中所需要的基本操作次数D. 算法执行过程中所需要的存储空间答案：C2. 线性表的顺序存储结构和链式存储结构相比，其优点是（）。
A. 存储密度高B. 存储密度低C. 插入和删除操作快D. 存储空间可以动态分配答案：A3. 在二叉树的遍历过程中，若某结点的左孩子为空，则其右孩子（）。
A. 一定为空B. 一定为非空C. 可能为空，也可能为非空D. 以上说法都不对答案：C4. 哈希表的构造方式是（）。
A. 数组B. 树C. 链表D. 数组和链表5. 一个长度为n的线性表，若采用顺序存储结构，则其在表中第i个位置的元素（1≤i≤n）的存储地址为（）。
A. 100+iB. 100+(i-1)×2C. 100+(i-1)×3D. 100+(i-1)×4答案：B6. 在二叉排序树中，若某结点的左子树非空，则其左子树中任一结点的值（）。
A. 都小于该结点的值B. 都大于该结点的值C. 都等于该结点的值D. 都大于等于该结点的值7. 对于图的遍历，以下说法正确的是（）。
A. 深度优先搜索只能使用递归实现B. 广度优先搜索只能使用队列实现C. 深度优先搜索和广度优先搜索都可以使用递归和非递归方式实现D. 深度优先搜索和广度优先搜索都必须使用栈实现答案：C8. 在一个具有n个顶点的无向图中，若该图是连通图，则其边数最少为（）。
A. n-1B. nC. n+1D. 2n9. 一个栈的入栈序列为1, 2, 3, 4, 5，则可能的出栈序列为（）。
A. 1, 3, 5, 2, 4B. 4, 5, 3, 2, 1C. 5, 4, 3, 2, 1D. 2, 4, 1, 3, 5答案：C10. 在一个有向图中，若存在从顶点v到顶点w的有向路径，则称v可达w，若存在从顶点v到图中每一个顶点的路径，则称v是（）。
2006.101.若结点的存储地址与其关键字之间存在某种映射关系，则称这种存储结构为( )A.顺序存储结构B.链式存储结构C.索引存储结构D.散列存储结构2.在长度为n的顺序表的第i(1≤i≤n+1)个位置上插入一个元素，元素的移动次数为( )A.n-i+1B.n-iC.iD.i-13.对于只在表的首、尾两端进行插入操作的线性表，宜采用的存储结构为( )A.顺序表B.用头指针表示的单循环链表C.用尾指针表示的单循环链表D.单链表4.若进栈序列为a,b,c，则通过入出栈操作可能得到的a,b,c的不同排列个数为( )A.4B.5C.6D.75．一棵有16结点的完全二叉树，对它按层编号，则对编号为7的结点X，它的双亲结点及右孩子结点的编号分别为（）A．2，14 B．2，15C．3，14 D．3，156．设有一5阶上三角矩阵A［1..5，1..5］，现将其上三角中的元素按列优先顺序存放在一堆数组B［1..15］中。
已知B［1］的地址为100，每个元素占用2个存储单元，则A［3，4］的地址为（）A．116 B．118C．120 D．1227．一个带权的无向连通图的最小生成树（）A．有一棵或多棵 B．只有一棵C．一定有多棵 D．可能不存在8．下列有关图遍历的说法中不正确的是（）A．连通图的深度优先搜索是一个递归过程B．图的广度优先搜索中邻接点的寻找具有“先进先出”的特征C．非连通图不能用深度优先搜索法D．图的遍历要求每一顶点仅被访问一次9．某算法的空间花费s(n)=2n+n100+nlog2n+n101，则其空间复杂度为（）。
A． O(nlog2n) B. O(n100) C. O(n101) D. O(2n)10. 单链表中的存储密度一定（）。
A．小于0.5 B. 等于1 C. 大于0.1 D. 小于1 11．在顺序栈中删除一个元素，至少要移动（）元素。
A． 0 B. 1 C. n/2 D. n 12．空串是（）。
东北林业大学 2005－2006学年第二学期考试试题 学院：信息学院 教研室（学科）主任：第3 页共 3 页 考试科目： 数据结构（A ）考试时间：120分钟 试卷总分 100分 题号 一 二 三 四 五 总分 得分 评卷 教师 一、单项选择题（在每个小题四个备选答案中选出一个正确答案，填在题末的括号中）（本大题共10小题，每小题1.5分，总计15分） 1、从逻辑上可以把数据结构分为（ ）两大类。
A ．动态结构、静态结构 B ．顺序结构、链式结构 C ．线性结构、非线性结构 D ．初等结构、构造型结构 答案（ ） 2、若某线性表最常用的操作是存取任一指定序号的元素和在最后进行插入和删除运算，则利用（ ）存储方式最节省时间。
A ．顺序表 B ．双链表 C ．带头结点的双循环链表 D ．单循环链表 答案（ ） 3、循环队列A[0..m-1]存放其元素值，用front 和rear 分别表示队头和队尾，则当前队列中的元素数是( )。
A.(rear-front+m)%m B. rear-front+1 C. rear-front-1 D. rear-front 答案（ ） 4、串的长度是指（ ）。
A ．串中所含不同字母的个数 B ．串中所含字符的个数 C ．串中所含不同字符的个数 D ．串中所含非空格字符的个数 答案（ ） 5、设广义表L=（（a,b,c ）），则L 的长度和深度分别为（ ）。
A. 1和1 B. 1和3 C. 1和2 D. 2和3 答案（ ） 6、二叉树的先序遍历和中序遍历如下： 先序遍历：EFHIGJK ；中序遍历: HFIEJKG 。
该二叉树根的右子树的根是：( )A. EB. FC. GD. H答案（ ）7、深度为h 的满m 叉树的第k 层有（ ）个结点。
(1=<k=<h)A ．m k-1B ．m k -1C ．m h-1D ．m h -1答案（ ）8、关键路径是事件结点网络中（ ）。
全国2004年10月卷答案一、单项选择题DABAC CCBDA ABABD// 5.可以简单的计算，空域为3->7，总共5个，对长则为21 - 5 = 167.c//BDBABDABDABBDA123失败，比较3次BDBABDABDABBDA1失败，比较1次BDBABDABDABBDA12失败，比较2次BDBABDABDABBDA1失败，比较1次BDBABDABDABBDA123成功，比较3次共计10次10.dA/B/ | \C D F|E二、填空题16.（一组）运算17. 直接前驱18. SXSSXXSSXSSXXX19. 模式匹配20. 5n - 6N+2N-2+2N-4=5N-6// n阶5对角阵// 1 1 1 0 0 ............// 1 1 1 1 0 ............// 1 1 1 1 1 0 ..........// 0 1 1 1 1 1 0.........// 0 0 1 1 1 1 1 0 ......// ....0 1 1 1 1 1 0 ....// ......................// ......................21. 50// 63 < 100 < 127, 最下一层叶子数:100 - 63 = 37// 倒数第2层叶子数:32 - [ 37 / 2 ] = 13 []向上取整22. 径？23. 待排关键字（记录）？24. 有序的？25. ?// 一些概念题，因为没书，很久没接触了，可能不准确。
三、解答题略28划分后左边:(55) (28) (73) (91) (37) 右边:（64），（19），（82），（46）第一次Merge之后:(28,55)(73) (91) (37) 右边:（64），（19），（82），（46)第二次Merge之后:(28,55)(73,91) (37) 右边:（64），（19），（82），（46)第三次Merge之后:(28,55,73,91)(37) 右边:（64），（19），（82），（46)第四次Merge之后:(28,37,55,73,91) 右边:（64），（19），（82），（46)第五次Merge之后:(28,37,55,73,91) 右边:（19,64），（82), (46)所以.....28，37，55，73，91，19，64，82，46四、算法阅读题30.1) p = pre->next; 或 p = L->next; // p指向第一个结点2) p->next = Lc->next; // 数据大于c的p结点插入Lc链表表头3) p = pre->next; 或 p = p->next; // 下一个结点31.此题有误，... if ((i=!t)!=0) ... 应该是 ... if( ( i = !i ) != 0 ) ...1) 1,3,5,7,6,4,22) 堆栈S中的元素依次出栈，奇数次序的入栈T,偶数次序的入队Q32.图G的邻接矩阵不对称，因此，是有向图1) 52) 计算有向图G中的端点i（第i+1个端点)的度，包括出度和入度3) O(n)33. 此题明显有错误if( low > high )应为if( low < high )因为if(){...}里有while( low < high )1) -8, -3, -2, -1, 4, 2, 5, 7：-8 -3 2 -1 -2 4 5 72) 将数组R中的前n个数调整为所有负数在前，所有整数在后五、算法设计题34. 看原型，应该是要使用递归了,题目很傻地把解法都告诉我们了。
数据结构自考试题及答案一、单项选择题（每题1分，共10分）1. 在数据结构中，从逻辑上可以把数据结构分为（）。
A. 动态结构和静态结构B. 线性结构和非线性结构C. 顺序结构和链式结构D. 内部结构和外部结构答案：B2. 线性表的顺序存储结构和链式存储结构相比，它的优点是（）。
A. 存储密度大B. 存储密度小C. 插入和删除操作快D. 可以进行随机访问答案：D3. 下列关于栈的描述中，错误的是（）。
A. 栈是先进后出（LIFO）的线性表B. 栈允许在一端进行插入和删除操作C. 栈是具有记忆功能的线性表D. 栈的插入和删除操作必须在栈顶进行答案：C4. 在二叉树的遍历过程中，若某结点的左子树为空，则该结点的左孩子直接与（）相连。
A. 右孩子B. 右兄弟C. 父节点D. 子节点答案：C5. 哈希表的构造方式是（）。
A. 数组B. 树C. 链表D. 图答案：A6. 在图的遍历过程中，深度优先搜索（DFS）和广度优先搜索（BFS）的主要区别在于（）。
A. 遍历顺序B. 是否使用栈C. 是否使用队列D. 是否使用递归答案：C7. 快速排序算法的时间复杂度在最坏情况下是（）。
A. O(n)B. O(nlogn)C. O(n^2)D. O(2^n)答案：C8. 以下排序算法中，时间复杂度为O(nlogn)的是（）。
A. 冒泡排序B. 选择排序C. 快速排序D. 插入排序答案：C9. 在数据库管理系统中，索引的作用是（）。
A. 存储数据B. 提高查询效率C. 维护数据完整性D. 实现数据加密答案：B10. 以下不属于查找算法的是（）。
A. 顺序查找B. 二分查找C. 哈希查找D. 归并排序答案：D二、填空题（每题2分，共20分）11. 在数据结构中，线性表的顺序存储结构通常使用___________来实现。
答案：数组12. 一个长度为n的顺序表，若在第i个位置插入一个元素（1≤i≤n+1），需要向后移动___________个元素。
自考数据结构试题及答案一、选择题（每题2分，共10分）1. 在数据结构中，线性表的顺序存储结构通常使用什么数据类型来存储元素？A. 数组B. 链表C. 栈D. 队列答案：A2. 下列关于栈的描述中，错误的是：A. 栈是一种后进先出（LIFO）的数据结构B. 栈顶元素可以被访问和修改C. 栈底元素可以被访问和修改D. 栈可以进行插入和删除操作答案：C3. 在二叉树的遍历算法中，先访问根节点，然后访问左子树，最后访问右子树的遍历方式是：A. 前序遍历B. 中序遍历C. 后序遍历D. 层序遍历答案：A4. 哈希表的冲突解决方法中，链地址法的基本思想是：A. 将冲突的元素存储在同一个数组位置B. 将冲突的元素存储在不同的数组位置C. 将冲突的元素存储在链表中D. 将冲突的元素存储在树中答案：C5. 下列算法中，不属于排序算法的是：A. 冒泡排序B. 快速排序C. 深度优先搜索D. 归并排序答案：C二、填空题（每题2分，共10分）1. 在数据结构中，_________是指元素之间存在一对一关系的线性结构。
答案：线性表2. 递归算法的基本思想是将问题分解为若干个规模更小的相同问题，然后_________。
答案：递归求解3. 在图的遍历算法中，广度优先搜索（BFS）通常使用_________数据结构来实现。
答案：队列4. 一个长度为n的有序数组，使用二分查找算法查找一个元素的时间复杂度为_________。
答案：O(log n)5. 哈夫曼编码是一种用于数据压缩的编码方法，它是一种_________编码。
答案：可变长三、简答题（每题5分，共20分）1. 请简述链表和数组在存储结构上的主要区别。
答案：链表的存储结构是动态的，每个元素包含数据和指向下一个元素的指针，而数组的存储结构是静态的，元素在内存中连续存储。
2. 什么是图的深度优先搜索（DFS）算法？请简述其基本步骤。
答案：深度优先搜索（DFS）算法是一种遍历图的算法，它从一个顶点开始，尽可能深地搜索图的分支。
更多优质自考资料尽在百度贴吧自考乐园俱乐部（/club/5346389）欢迎❤加入...欢迎❤交流...止不住的惊喜等着你.........2004年下半年全国自考数据结构真题一、单项选择题（本大题共15小题，每小题2分，共30分）在每小题列出的四个备选项中只有一个是符合题目要求的，请将其代码填写在题后的括号内。
错选、多选或未选均无分。
1.A. AB. BC. CD. D答案：D2.若要在单链表中的结点*p之后插入一个结点*s，则应执行的语句是（）A.s->next=p->next;p->next=s;B.p->next=s;s->next=p->next;C.p->next=s->next;s->next=p;D.s->next=p;p->next=s->next;答案：A3.若要在O（1）的时间复杂度上实现两个循环链表头尾相接，则应对两个循环链表各设置一个指针，分别指向（）A.各自的头结点B.各自的尾结点C.各自的第一个元素结点D.一个表的头结点，另一个表的尾结点答案：B4.栈的两种常用存储结构分别为（）A.顺序存储结构和链式存储结构B.顺序存储结构和散列存储结构C.链式存储结构和索引存储结构D.链式存储结构和散列存储结构答案：A5.已知循环队列的存储空间为数组data［21］，且当前队列的头指针和尾指针的值分别为8和3，则该队列的当前长度为（）A. 5B. 6C.16D.17答案：C6.已知在如下定义的链串结点中，每个字符占1个字节，指针占4个字节，则该链串的存储密度为typedef struct node {char data［8］;struct node *next;} LinkStrNode;（）A.1/4B.1/2C.2/3D.3/4答案：C7.应用简单的匹配算法对主串s=″BDBABDABDAB″与子串t=″BDA″进行模式匹配，在匹配成功时，进行的字符比较总次数为（）A.7B.9C.10D.12答案：C8.二维数组A［20］［10］采用列优先的存储方法，若每个元素占2个存储单元，且第1个元素的首地址为200，则元素A［8］［9］的存储地址为（）A.574B.576C.578D.580答案：B9.对广义表L=((a,b),c,d)进行操作tail(head(L))的结果是（）A.（c,d）B.(d)C. bD.(b)答案：D10.已知一棵树的前序序列为ABCDEF，后序序列为CEDFBA，则对该树进行层次遍历得到的序列为（）A.ABCDEFB.ABCEFDC.ABFCDED.ABCDFE答案：D11.一个含n个顶点和e条弧的有向图以邻接矩阵表示法为存储结构，则计算该有向图中某个顶点出度的时间复杂度为（）A. AB. BC. CD. D答案：A12.在关键字序列(12，23，34，45，56，67，78，89，91)中二分查找关键字为45、89和12的结点时，所需进行的比较次数分别为（）A.4，4，3B.4，3，3C.3，4，4D.3，3，4答案：B13.下列排序方法中，最好与最坏时间复杂度不相同的排序方法是（）A.冒泡排序B.直接选择排序C.堆排序D.归并排序答案：A14.已知含10个结点的二叉排序树是一棵完全二叉树，则该二叉排序树在等概率情况下查找成功的平均查找长度等于（）A. 1.0B. 2.9C. 3.4D. 5.5答案：B15.在下列各种文件中，不能进行顺序查找的文件是（）A.顺序文件B.索引文件C.散列文件D.多重表文件答案：C二、填空题（本大题共10小题，每小题2分，共20分）请在每小题的空格中填上正确答案。
数据结构自考试题及答案一、单项选择题（每题1分，共10分）1. 在数据结构中，最基本的数据结构是（）。
A. 线性结构B. 非线性结构C. 顺序结构D. 链式结构答案：A2. 线性表的顺序存储结构和链式存储结构相比，其主要优点是（）。
A. 存储密度高B. 存储密度低C. 存储空间少D. 插入和删除操作快答案：A3. 在一个长度为n的顺序表中，删除第i个元素（1≤i≤n）时，需要移动的元素个数为（）。
A. i-1B. n-iC. n-i+1D. n-1答案：C4. 栈的基本运算中，不包括（）。
A. 入栈B. 出栈C. 读栈顶元素D. 判断栈空答案：D5. 队列的特点是（）。
A. 先进先出B. 先进后出C. 后进先出D. 后进后出答案：A6. 树的深度为5，其中度为3的结点最多有（）个。
A. 3B. 7C. 9D. 15答案：D7. 在二叉树的前序遍历序列、中序遍历序列、后序遍历序列中，唯一与树的形态一一对应的序列是（）。
A. 前序遍历序列B. 中序遍历序列C. 后序遍历序列D. 无法确定答案：A8. 在图的遍历过程中，若某结点的入度为0，则该结点（）。
A. 一定为起点B. 一定为终点C. 可以为起点或终点D. 既不是起点也不是终点答案：C9. 哈夫曼编码是一种（）。
A. 定长编码B. 变长编码C. 唯一编码D. 非唯一编码答案：B10. 用邻接矩阵表示图时，若该图是无向图，则其邻接矩阵一定是（）。
A. 对称矩阵B. 非对称矩阵C. 稀疏矩阵D. 密集矩阵答案：A二、填空题（每题2分，共20分）1. 在数据结构中，算法的时间复杂度是指算法执行过程中所需要的基本运算次数与输入数据量之间的关系。
算法的时间复杂度通常用大O符号表示，例如，O(n)表示时间复杂度与输入数据量成______关系。
答案：线性2. 线性表的两种存储结构分别是顺序存储结构和______存储结构。
答案：链式3. 在栈中，栈顶元素是最后被插入的元素，遵循______原则。
自考数据结构试题及答案一、选择题1. 在数据结构中，算法的复杂性主要包括时间复杂性和空间复杂性。
以下哪个选项不属于算法复杂性的一部分？A. 时间复杂性B. 空间复杂性C. 逻辑复杂性D. 性能复杂性答案：C2. 假设有一个栈，其元素从上到下依次是A、B、C、D。
如果现在要弹出所有的元素，那么弹出的顺序是什么？A. D、C、B、AB. A、B、C、DC. B、C、D、AD. C、B、D、A答案：A3. 在二叉树的遍历中，前序遍历的顺序是什么？A. 先根，后左，后右B. 先左，后根，后右C. 先右，后根，后左D. 先根，后右，后左答案：A4. 哈希表的冲突可以通过多种方式解决，其中不是解决冲突的方法是：A. 开放寻址法B. 链地址法C. 线性探测法D. 建立公共溢出区答案：C5. 以下哪个排序算法是稳定的？A. 快速排序B. 归并排序C. 堆排序D. 选择排序答案：B二、填空题6. 在单链表中，删除节点的操作需要提供________和________两个参数。
答案：前驱节点；节点数据7. 一个长度为n的数组，如果采用二分查找法，查找元素的时间复杂度是________。
答案：O(log n)8. 假设有一个图，其顶点数为V，边数为E，如果不使用任何优化手段，该图的邻接矩阵存储方式所需的空间复杂度是________。
答案：O(V^2)9. 一个具有n个节点的完全二叉树的最小高度是________。
答案：log2(n+1)10. 动态存储管理中，可利用的最基本的两种分配策略是________和________。
答案：首次适应；最佳适应三、简答题11. 什么是平衡二叉树？请简述其特点。
答：平衡二叉树是一种特殊的二叉搜索树，其中任何两个兄弟节点的深度之差的绝对值不超过1。
其特点包括：- 所有节点的两个子树的高度差不超过1。
- 保持了二叉搜索树的性质，即左子树上所有节点的键值小于它，右子树上所有节点的键值大于它。
全国2004年1月高等教育自学考试数据结构试题课程代码：02331一、单项选择题（本大题共15小题，每小题2分，共30分）在每小题列出的四个备选项中只有一个是符合题目要求的，请将其代码填写在题后的括号内。
错选、多选或未选均无分。
1．在数据结构中，数据的逻辑结构可以分成（）A．内部结构和外部结构B．线性结构和非线性结构C．紧凑结构和非紧揍结构D．动态结构和静态结构2．在以单链表为存储结构的线性表中，数据元素之间的逻辑关系用（）A．数据元素的相邻地址表示B．数据元素在表中的序号表示C．指向后继元素的指针表示D．数据元素的值表示3．设p指向单链表中的一个结点，s指向待插入的结点，则下述程序段的功能是（）s -> next = p -> next; p -> next = s;t = p -> data; p -> data = s -> data; s ->data = t;A．结点*p与结点*s的数据域互换B．在p所指结点的元素之前插入元素C．在p所指结点的元素之后插入元素D．在结点*p之前插入结点*s4．栈和队列都是（）A．限制存取位置的线性结构B．顺序存储的线性结构C．链式存储的线性结构D．限制存取位置的非线性结构5．若数组s[0..n-1]为两个栈s1和s2的共用存储空间，且仅当s[0..n-1]全满时，各栈才不能进行进栈操作，则为这两个栈分配空间的最佳方案是：s1和s2的栈顶指针的初值分别为（）A．1和n+1 B．1和n/2C．－1和n D．－1和n+16．执行下列程序段后，串X的值为（）S=〞abcdefgh〞; T=〞xyzw〞;substr (X,S,2,strlen(T));substr (Y,S, stelen(T),2);strcat (X,Y);A．〞cdefgh〞B．〞cdxyzw〞C．〞cdefxy〞D．〞cdefef〞7．多维数组之所以有行优先顺序和列优先顺序两种存储方式是因为（）浙02331# 数据结构试题第 1 页(共8 页)A．数组的元素处在行和列两个关系中B．数组的元素必须从左到右顺序排列C．数组的元素之间存在次序关系D．数组是多维结构，内存是一维结构8．从广义表LS＝（(p, q), r, s）中分解出原子q的运算是（）A．tail (head (LS)) B．head (tail (head (LS)))C．head (tail (LS)) D．tail (tail (head (LS)))9．在具有n个叶子结点的严格二叉树中，结点总数为（）A．2n+1 B．2nC．2n-1 D．2n-210．若<v i, v j>是有向图的一条边，则称（）A．v i邻接于v j B．v j邻接于v iC．v i和v j相互邻接D．v i与v j不相邻接11．在一个带权连通图G中，权值最小的边一定包含在G的（）A．最小生成树中B．深度优先生成树中C．广度优先生成树中D．深度优先生成森林中12．当在二叉排序树中插入一个新结点时，若树中不存在与待插入结点的关键字相同的结点，且新结点的关键字小于根结点的关键字，则新结点将成为（）A．左子树的叶子结点B．左子树的分支结点C．右子树的叶子结点D．右子树的分支结点13．希尔排序的增量序列必须是（）A．递增的B．随机的C．递减的D．非递减的14．如果在排序过程中，每次均将一个待排序的记录按关键字大小加入到前面已经有序的子表中的适当位置，则该排序方法称为（）A．插入排序B．归并排序C．冒泡排序D．堆排序15．设置溢出区的文件是（）A．索引非顺序文件B．ISAM文件C．VSAM文件D．顺序文件二、填空题（本大题共10小题，每小题2分，共20分）请在每小题的空格中填上正确答案。
错填、不填均无分。
16．下列程序段的时间复杂度为________________。
product = 1;for (i = n;i>0; i--)for (j = i+1; j<n; j++)product *=j;17．已知指针p指向单链表中某个结点，则语句p -> next =p -> next -> next的作用是浙02331# 数据结构试题第 2 页(共8 页)浙02331# 数据结构试题 第 3 页(共 8 页)________________。
18．假设元素只能按a,b,c,d 的顺序依次进栈，且得到的出栈序列中的第一个元素为c ，则可能得到的出栈序列为________________，不可能得到的出栈序列为________________。
19．若链串结点中的指针占4个字节，每个字符占1个字节，则结点大小为2的链串的存储密度为________________。
20．右图表示的广义表为________________。
21．若一棵满三叉树中含有121个结点，则该树的深度为________________。
22．若以邻接矩阵表示有向图，则邻接矩阵上第i 行中非零元素的个数即为顶点v i 的________________。
23．若希望只进行8趟排序便能在4800个元素中找出其中值最小的8个元素，并且要求排序过程中所进行的关键字比较次数尽可能少，则应该选用________________排序方法。
24．在含20个关键字的3阶B 树（2－3树）上查找一个关键字，至多需要访问___________次外存。
25．文件上的两类主要操作为________________和________________。
三、解答题（本大题共4小题，每小题5分，共20分）26．设栈S1的入栈序列为1 2 3 4（每个数字为13个元素），则不可能得到出栈序列3142。
但可通过增设栈S2来实现。
例如，按下图中的箭头指示，依次经过栈S1和S2，便可得到序列3 1 4 2。
如果用H1和H2分别表示栈S1和S2的进栈操作，用P1和P2分别表示两个栈的出栈操作，则得到3 1 4 2的一个操作步骤为H1，H1，H1，P1，H2，P2，P1，H2，P1，H2，P2，H1，P1，H2，P2，P2 请仿照上例写出利用两个栈从1 2 3 4得到4 1 3 2的操作步骤。
浙02331# 数据结构试题 第 4 页(共 8 页) 27．已知树如右图所示，（1）写出该树的后序序列；（2）画出由该树转换得到的二叉树。
28．为关键字（17，33，31，40，48）构造一个长度为7的散列表，设散列函数为h(key)=key%7,用开放定址法解决冲突的探查序列是hi = (h(key) + i(key%5+1))%7 0≤i ≤6（1）画出构造所得的散列表；（2）求出在等概率情况下查找成功时的平均查找长度。
29．已知R ［1..8］中的元素依次为（12，5，9，20，6，31，24，27），写出按算法MergeSortDC 对R 进行自顶向下的二路归并排序过程中，前5次调用函数Merge(R, low, mid, high)时参数 low, mid 和high 的值。
void MergeSortDC (int R[], int low, int mid, int high ){int mid;if (low<high){mid = (low +high)/2;MergeSortDC (R, low, mid);MergeSortDC (R, mid+1, high);Merge (R, low, mid, high);}} // MergeSortDC（1）第一次调用时的参数值；（2）第二次调用时的参数值；（3）第三次调用时的参数值；（4）第四次调用时的参数值；（5）第五次调用时的参数值；四、算法阅读题（本大题共4小题，每小题5分，共20分）30．下列函数的功能是，对以带头结点的单链表作为存储结构的两个递增有序表（表中不存在值相同的数据元素）进行如下操作：将所有在Lb 表中存在而La表中不存在的结点插入到La中，其中La和Lb分别为两个链表的头指针。
请在空缺处填入合适内容，使其成为一个完整的算法。
void union (LinkList La, LinkList Lb){//本算法的功能是将所有Lb表中存在而La表中不存在的结点插入到La表中LinkList pre = La, q;LinkList pa = La -> next;LinkList pb = Lb -> next;free (Lb);while (pa && pd){if (pa -> data <pb -> data){ pre = pa; pa = pa -> next;}else if (pa -> data > pb ->data){(1) ;pre = pb;pb = pb -> next;(2) ;}else{q = pb; pb = pb -> next; free (q);}}if (pb)(3) ;}(1)(2)(3)31．已知串的存储结构为动态存储分配的顺序串。
阅读下列算法，并回答问题：（1）写出执行函数调用strc (s, r)的返回结果，其中s=〃aba〃, r=〃abababa〃; （2）简述函数strc的功能。
int strc (HString * sub, HString * str){浙02331# 数据结构试题第 5 页(共8 页)int i=0, j, k, count =0;while (i < str -> length – sub -> length +1){j=i; k=0;while (k <sub -> length && str -> ch[j] = =sub -> ch[k] ){j++; k++;}if (k = = sub -> length){count ++; i=j-sub -> length +1;}else i++;}return count;}(1)(2)32．下列函数MDFSForest的功能是，对一个采用邻接矩阵作存储结构的图进行深度优先搜索遍历，输出所得深度优先生成森林中各条边。
请在空缺处填入合适内容，使其成为一个完整的算法。
#define MaxMun 20 //图的最大顶点数typedef struct {char vexs [MaxNum]; //字符类型的顶点表int edges [MaxNum][MaxNum]; //邻接矩阵int n, e; //图的顶点数和边数}MGraph; //图的邻接矩阵结构描述typedef enum {FALSE, TRUE} Boolean;Boolean visited [MaxNum];void MDFSTree (MGraph *G, int i);void MDFSForest (MGraph *G){int i, k;for (i=0; i <G -> n; i++)visited [i] = (1) ;for (k = 0; k<G -> n; k++)if (!visited [k]) MDFSTree (G,k);浙02331# 数据结构试题第 6 页(共8 页)}void MDFSTree (MGraph *G, int i){int j;visited [i]=TRUE;for (j=0; j<G -> n; j++){if ( (2) ){printf (〃<%c, %c>〃G -> vexs [i], G -> vexs [j]);(3) ;}}｝（1）（2）（3）33．已知整形数组L［1..8］中的元素依次为（9，8，5，7，6，3，2，1），阅读下列函数，并写出执行函数调用sort(L, 8)时，对L进行的头两趟（pass分别为0和1）处理结果。
