2、2、在一个单链表中,若q所指结点是p所指结点的前驱结点,若在q与p之间插入一个s所指的结点,则执行()。B p→link=s;As-link=p-+link,p-link=s;s→link=q,D q -→link=s; s→link=p;C p→link=s-link;s→link=p;3、3、栈的插入和删除操作在（）进行。B栈底cA栈顶任意位置D指定位置4、4、由权值分别为11，8，6，2，5的叶子结点生成一棵哈夫曼树，它的带权路径长度为（）A 24B 71C48D 53二、填空题（每空1分，共32分）和1、1、数据的逻辑结构被分为四种。和2、2、一种抽象数据类型包括两个部分。3、3、在下面的数组a中链接存储着一个线性表，表头指针为a[o].next，则该线性表为213450678adata605642387425next37620414、4、在以HL为表头指针的带表头附加结点的单链表和循环单链表中，判和断链表为空的条件分别为5、5、用具有n个元素的一维数组存储一个循环队列，则其队首指针总是指向队首元素的，该循环队列的最大长度为表示；6、6、当堆栈采用顺序存储结构时，栈顶元素的值可用表示。当堆栈采用链接存储结构时，栈顶元素的值可用7、7、一棵高度为5的二叉树中最少含有个结点，最多含有个结点；个结点，最多含有一棵高度为5的理想平衡树中，最少含有个结点。8、8、在图的邻接表中，每个结点被称为，通常它包含三个域：一是二是；三是9、9、在一个索引文件的索引表中，每个索引项包含对应记录的和两项数据。10、10、假定一棵树的广义表表示为A（B（C，D（E，F，G)，H（I，J)))，则树中所含的结点数为个，树的深度为树的度为，孩子结点为结点H的双亲结点为
2、2、在一个单链表中,若 q 所指结点是 p 所指结点的前驱结点,若在 q 与 p 之间 插入一个 s 所指的结点,则执行( )。 A s→link=p→link; p→link=s; B p→link=s; s→link=q; C p→link=s→link; s→link=p; D q →link=s; s→link =p; 3、 3、 栈的插入和删除操作在（ ）进行。 A 栈顶 B 栈底 C 任意位置 D 指定位置 4、 4、 由权值分别为 11，8，6，2，5 的叶子结点生成一棵哈夫曼树，它的 带权路径长度为（ ） A 24 B 71 C 48 D 53 二、 二、 填空题（每空 1 分，共 32 分） 1、1、数据的逻辑结构被分为_、 _ 、_和 _四种。 2、2、一种抽象数据类型包括_和_两个部分。 3、3、在下面的数组 a 中链接存储着一个线性表，表头指针为 a[o].next，则 该线性表为_。 a 0 1 2 3 4 5 6 7 8 data next 4、4、在以 HL 为表头指针的带表头附加结点的单链表和循环单链表中，判 断链表为空的条件分别为_和_。 5、5、用具有 n 个元素的一维数组存储一个循环队列，则其队首指针总是指 向队首元素的_，该循环队列的最大长度为_。 6、6、当堆栈采用顺序存储结构时，栈顶元素的值可用———————表示； 当堆栈采用链接存储结构时，栈顶元素的值可用_表示。 7、7、一棵高度为 5 的二叉树中最少含有_个结点，最多含有 _个结点； 一棵高度为 5 的理想平衡树中，最少含有_个结点，最多含有 _个结点。 8、8、在图的邻接表中，每个结点被称为_，通常它包含三个域： 一是_；二是_；三是_。 9、9、在一个索引文件的索引表中，每个索引项包含对应记录的_ 和_两项数据。 10、 10、 假定一棵树的广义表表示为 A（B（C，D（E，F，G），H （I，J））），则树中所含的结点数为_个，树的深度为_, 树的度为 _, 结 点 H 的 双 亲 结 点 为 _, 孩 子 结 点 为 _ 。 60 56 42 38 74 25 4 3 7 6 2 0 1
11、 11、在堆排序的过程中，对任一分支结点进行筛运算的时间复杂度为整个堆排序过程的时间复杂度为12、12、在对m阶的B树插入元素的过程中，每向一个结点插入一个索引项（叶子结点中的索引项为关键字和空指针）后，若该结点的索引项数等于个，则必须把它分裂为个结点。三、三、运算题（每小题6分，共24分）1、1、已知一组记录的排序码为（46，79，56，38，40，80，95，24），写出对其进行快速排序的每一次划分结果。2、2、一个线性表为B=（12，23，45，57，20，03，78，31，15，36），设散列表为HT0.12]，散列函数为H（key）=key%13并用线性探查法解决冲突，请画出散列表，并计算等概率情况下查找成功的平均查找长度。3、3、已知一棵二叉树的前序遍历的结果序列是ABECKFGHIJ，中序遍历的结果是EBCDAFHIGJ，试写出这棵二叉树的后序遍历结果。4、4、已知一个图的顶点集V各边集G如下：V=(0,1,2,3,4,5,6,7,8,9);E=1(0,1)，(0，4)，(1，2)，(1,7),(2，8),(3,4),(3，8),(5，6),(5,8),(5,9),(6,7),(7,8)，(8,9)1当它用邻接矩阵表示和邻接表表示时，分别写出从顶点Vo出发按深度优先搜索遍历得到的顶点序列和按广度优先搜索遍历等到的顶点序列。假定每个顶点邻接表中的结点是按顶点序号从大到小的次序链接的。图深度优先序列广度优先序列邻接矩阵表示时邻接表表示时四、四、阅读算法，回答问题（每小题8分，共16分）1、假定从键盘上输入一批整数，依次为：7863345309134-1，请写出输出结果。#include<iostream.h>#include<stdlib.h>
11、 11、 在堆排序的过程中，对任一分支结点进行筛运算的时间复 杂度为_,整个堆排序过程的时间复杂度为_。 12、 12、 在对 m 阶的 B_树插入元素的过程中，每向一个结点插入一 个索引项（叶子结点中的索引项为关键字和空指针）后，若该结点的索 引项数等于_个，则必须把它分裂为_个结点。 三、 三、 运算题（每小题 6 分，共 24 分） 1、1、已知一组记录的排序码为（46，79，56，38，40，80, 95，24），写 出对其进行快速排序的每一次划分结果。 2、2、一个线性表为 B=（12，23，45，57，20，03，78，31，15，36），设 散列表为 HT[0.12]，散列函数为 H（key）= key % 13 并用线性探查法解 决冲突，请画出散列表，并计算等概率情况下查找成功的平均查找长度。 3、3、已知一棵二叉树的前序遍历的结果序列是 ABECKFGHIJ，中序遍历 的结果是 EBCDAFHIGJ，试写出这棵二叉树的后序遍历结果。 4、4、已知一个图的顶点集 V 各边集 G 如下： V = {0，1，2，3，4，5，6，7，8，9}； E = {（0，1），（0，4），（1，2），（1，7），（2，8），（3，4），（3 ，8），（5，6）， （5，8），（5，9），（6，7），（7，8），（8，9）} 当它用邻接矩阵表示和邻接表表示时，分别写出从顶点 V0 出发按深度优先 搜索遍历得到的顶点序列和按广度优先搜索遍历等到的顶点序列。 假定每个顶点邻接表中的结点是按顶点序号从大到小的次序链接的。 四、 四、 阅读算法，回答问题（每小题 8 分，共 16 分） 1、假定从键盘上输入一批整数，依次为：78 63 45 30 91 34 –1，请 写出输出结果。 # include < iostream.h> # include < stdlib.h > 图 深度优先序列 广度优先序列 邻接矩阵表示时 邻接表表示时
consstintstackmaxsize=30:typedef int elemtype;struct stackelemtype stack [stackmaxsize];int top;1:#include“stack.h”Void main()stack a,initstack(a);int x,cin>>x;,while (x! =-1) (push (a, x),cin>>x;1while (!stackempty (a)cout <<pop (a)<"cout <<endl;1该算法的输出结果为：2、阅读以下二叉树操作算法，指出该算法的功能。Template<calss type>void BinTree<Type> ::unknown (BinTreeNode<Type>*t) BinTreeNode< Type>*p=t,*temp,if (pl=NULL) (temp= p-leftchild;p→leftchild = p-rightchild;p-+rightchild = temp;unknown(p-leftchild);undnown(p--rightchild);1该算法的功能是：
consst int stackmaxsize = 30; typedef int elemtype; struct stack { elemtype stack [stackmaxsize]; int top; }; # include “stack.h” Void main ( ) { stack a; initstack(a); int x; cin >>x; while (x! = -1) { push (a, x ); cin >>x; } while (!stackempty (a)) cout <<pop (a) <<” ; cout <<end1; } 该算法的输出结果为： _. 2、阅读以下二叉树操作算法，指出该算法的功能。 Template <calss type > void BinTree <Type> ：： unknown (BinTreeNode<Type>*t) { BinTreeNode< Type> *p =t, *temp; if (p!=NULL) { temp = p→leftchild; p→leftchild = p→rightchild; p→rightchild = temp; unknown(p→leftchild); undnown(p→rightchild); } } 该算法的功能是：_
五、五、算法填空，在画有横线的地方填写合适的内容（10分）对顺序存储的有序表进行二分查找的递归算法。intBinsch(ElemTypeA/l,intlow,inthigh,KeyTypeK)if (low <= high)int mid = 1if(K==A[mid J.key)return mid;else if (K<A[mid].key)return 2elsereturn 31elsereturn4六、六、编写算法（10分）编写算法，将一个结点类型为Lnode的单链表按逆序链接，即若原单链表中存储元素的次序为ai，..an-，an，则逆序链接后变为，an，an-1，...al。Voidcontrary(Lnode*&HL)数据结构试题（答案）、单选题（每小题2分，共8分）题号2341答案CDAB二、填空题（每空1分，共32分）集合、线性、树、图；1:2:数据描述、操作声名；3:(38,56,25，60，42，74);4:HL--next =NULL:HL=HL-next:5:前一个位置；n-l;6:S.stack [S.top];HSdata;7:5318:边结点、邻接点域、权域、链域；9:索引值域、开始位置域；10:10、3、3、B、I和J;
五、 五、 算法填空，在画有横线的地方填写合适的内容（10 分） 对顺序存储的有序表进行二分查找的递归算法 。 int Binsch( ElemType A[ ],int low ,int high,KeyType K ) { if (low <= high) { int mid = 1 if ( K= = A[ mid ].key ) return mid; else if ( K < A[mid].key) return 2 else return 3 } else return 4 六、 六、 编写算法（10 分） 编写算法，将一个结点类型为 Lnode 的单链表按逆序链接，即若原单链表中 存储元素的次序为 a1，.an-1，an，则逆序链接后变为, an，an-1，.a1。 Void contrary (Lnode * & HL) 数据结构试题（答案） 一、单选题（每小题 2 分，共 8 分） 题 号 1 2 3 4 答 案 C D A B 二、填空题（每空 1 分，共 32 分） 1： 集合、线性、树、图； 2： 数据描述、操作声名； 3： （38，56，25，60，42，74）； 4： HL→next =NULL； HL=HL→next； 5： 前一个位置； n-1； 6： S.stack [S.top]; HS→data; 7： 5 31 8： 边结点、邻接点域、权域、链域； 9： 索引值域、开始位置域； 10： 10、3、3、B、I 和 J；
1l:0(log2n)、O(nlog2n)12:m、m-1三、运算题（每小题6分，共24分）1、划分次序划分结果第一次24[568095[3840] 4679]第二次809579]24[3840]46[56第三次24384046[56 809579]第四次249538404656[8079]79第五次2438404656[8095]第六次24384056798095462、234567891011120178150357203123361245查找成功的平均查找长度：ASLsUcc=14/10=1.43、此二叉树的后序遍历结果是：EDCBIHJGFA4、图深度优先序列广度优先序列邻接矩阵表示时0,1,2,8，3，4，5,6，7，90,1,4，2，7,3，8,6，5，9邻接表表示时0,4,3,8,9,5,6,7,1,20,4,1,3,7,2，8,6,9,5四、阅读算法，回答问题（每小题8分，共16分）1、1、该算法的输入结果是：34913045563782、2、该算法的功能是：交换二叉树的左右子树的递归算法。五、算法填空，在画有横线的地方填写合适的内容（10分）1、1是：（low+high）/2;2是：Binsch(A,low.mid -1,K)3 是:Binsch(A,mid+1,high,K);4是：-1;六、编写算法（10分）根据编程情况，酌情给分。Lnode *P=HL;HL-NULL:While (p!=null)Lnode*q-p;,P=p-next,q-*next-HL;HL=q,7
11： O（log2n）、O(nlog2n); 12： m 、 m - 1 三、运算题（每小题 6 分，共 24 分） 1、 划分次序 划分结果 第一次 [38 24 40] 46 [56 80 95 79] 第二次 24 [38 40] 46 [56 80 95 79] 第三次 24 38 40 46 [56 80 95 79] 第四次 24 38 40 46 56 [80 95 79] 第五次 24 38 40 46 56 79 [80 95] 第六次 24 38 40 46 56 79 80 95 2、 78 15 03 57 45 20 31 23 36 12 查找成功的平均查找长度：ASLSUCC=14/10= 1.4 3、此二叉树的后序遍历结果是：EDCBIHJGFA 4、 四、阅读算法，回答问题（每小题 8 分，共 16 分） 1、 1、 该算法的输入结果是：34 91 30 45 63 78 2、 2、 该算法的功能是：交换二叉树的左右子树的递归算法。 五、算法填空，在画有横线的地方填写合适的内容（10 分） 1、1 是：（low + high）/2; 2 是： Binsch(A,low,mid–1,K); 3 是： Binsch(A,mid+1,high,K); 4 是： -1； 六、编写算法（10 分） 根据编程情况，酌情给分。 { Lnode *P=HL; HL=NULL; While (p!=null) { Lnode*q=p; P=p→next; q→next=HL; HL=q; } } 图 深度优先序列 广度优先序列 邻接矩阵表示时 0，1，2，8，3，4，5，6，7，9 0，1，4，2，7，3，8，6，5，9 邻接表表示时 0，4，3，8，9，5，6，7，1，2 0，4，1，3，7，2，8，6，9，5 0 1 2 3 4 5 6 7 8 9 10 11 12