《数据结构期末考试题.pdf》由会员分享，可在线阅读，更多相关《数据结构期末考试题.pdf（46页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、/一、单 选 题(每 题 2 分，共 20分)1.1.对一个算法的评价，不包括如下(B)方面的内容。A.健壮性和可读性 B.并行性 C.正确性 D.时空复杂度2.2.在带有头结点的单链表H L中，要向表头插入一个由指针p 指向的结点，则执行(A),A.p-next=HL-next;HL-next=p;B.p-next=HL;HL=p;C.p-next=HL;p=HL;D.HL=p;p-next=HL;3.3.对线性表，在下列哪种情况下应当采用链表表示？(B)A.经常需要随机地存取元素 B.经常需要进行插入和删除操作C.表中元素需要占据一片连续的存储空间 D.表中元素的个数不变4.4.一个栈的输
2、入序列为1 2 3,则下列序列中不可能是栈的输出序列的是(C)A.23 1 B.32 1C.3 1 2 D.1 235.5.AOV 网是一种(D)。A.有向图 B.无向图 C.无向无环图 D.有向无环图6.6.采用开放定址法处理散列表的冲突时，其平均查找长度(B)。A.低于链接法处理冲突 B.高于链接法处理冲突C.与链接法处理冲突相同 D.高于二分查找7.7.若需要利用形参直接访问实参时，应将形参变量说明为(D)参数。A.值 B.函数 C.指针 D.引用8.8.在稀疏矩阵的带行指针向量的链接存储中，每个单链表中的结点都具有相同的(A)。A.行号 B.列号 C.元素值 D.非零元素个数9.9.快
3、速排序在最坏情况下的时间复杂度为(D)oA.O(log2n)B.O(nlog2n)C.0(n)D.0(n2)10.1 0.从二叉搜索树中查找一个元素时，其时间复杂度大致为(C)。A.O(n)B.O(l)C.O(log2n)D.O(n2)二、二、运 算 题(每 题 6 分，共 24分)1.1.数据结构是指数据及其相互之间的联系 o 当结点之间存在M 对N(M：N)的联系时，称这种结构为 图,2.2.队列的插入操作是在队列的 尾 进行，删 除 操 作 是 在 队 列 的 一 首_ _ _ _ _ _ 进行。3.3.当用长度为N 的数组顺序存储一 个 栈时，假定用to p=N 表示栈空，则表示栈满的
4、条件是_ _ _ top=0_(要超出才为满)o4.4.对于一个长度为n 的单链存储的线性表，在表头插入元素的时间复杂度为 O(1),在表尾插入元素的时间复杂度为_ O(n)。5.5.设 W 为一个二维数组，其每个数据元素占用4 个字节，行下标i 从。到 7,列下标j 从。到 3,则二维数组W 的数据元素共占用_ 1 2 8 个字节。W 中第6 行的元素和第4 列的元素共占用 44 个字节。若按行顺序存放二维数组W,其起始地址为1 0 0,则二维数组元素W6,3的起始地址为_ 108。6.6.广 义 表 A=(a,(a,b),(a,b),c),则 它 的 深 度 为 3,它的长度为3_。7.1
5、.一 二叉树是指度为2 的 有序 树。一棵结点数为N 的二叉树，其所有结点的度的总和是_n-l。8.8.对一棵二叉搜索树进行中序遍历时、得到的结点序列是一个 有序序列。对一棵由算术表达式组成的二叉语法树进行后序遍历得到的结点序列是该算术表达式的 后缀表达式 o9.9.对 于 一 棵 具 有 n 个 结 点 的 二 叉 树，用二叉链 表 存 储 时，其指针总数为2n 个,其中 n-1 个 用 于 指 向 孩 子,n+1个指针是空闲的。10.1 0.若对一棵完全二叉树从0 开始进行结点的编号，并按此编号把它顺序存储到一维数组A 中，即编号为0 的结点存储到A0中。其余类推，则 A i 元素的左孩子
6、元素为_2i+l，右孩子元素为_ 2i+2，双亲元素为(_i-l)/2。11.11.在 线 性 表 的 散 列 存 储 中，处 理 冲 突 的 常 用 方 法 有 开 放 定 址 法和 链接法 两种。12.1 2.当待排序的记录数较大，排序码较随机且对稳定性不作要求时，宜采用 快速排序；当待排序的记录数较大，存储空间允许且要求排序是稳定时，宜采用归并 排序。三、三、运 算 题(每 题 6 分，共 24分)1.1.已知一个6x5稀疏矩阵如下所示，0 0 0 0 10 0 0 0 00-1 0 0 00 0 0 0-25 0 0 0 00 0 7 0 0试：(1)(1)写出它的三元组线性表；(2)
7、(2)给出三元组线性表的顺序存储表示。2.2.设有一个输入数据的序列是 46,25,78,62,12,80 ,试画出从空树起，逐个输入各个数据而生成的二叉搜索树。3.3.对于图6 所示的有向图若存储它采用邻接表，并且每个顶点邻接表中的边结点都是按照终点序号从小到大的次序链接的，试写出：(1)从顶点出发进行深度优先搜索所得到的深度优先生成树；(2)从顶点出发进行广度优先搜索所得到的广度优先生成树；4.4.已知一个图的顶点集V和边集E分别为：V=1,2,3,4,5,6,7;E=,;若存储它采用邻接表，并且每个顶点邻接表中的边结点都是按照终点序号从小到大的次序链接的，按主教材中介绍的拓朴排序算法进行
8、排序，试给出得到的拓朴排序的序列。四、四、阅读算法(每题7 分，共 14分)1.1.int Prime(int n)(int i=l;int x=(int)sqrt(n);while(+i=x)if(n%i=0)break;if(ix)return 1;else return 0;)(1)(1)指出该算法的功能；判断n 是否是素数(或质数)(2)(2)该算法的时间复杂度是多少？2.2.写出下述算法的功能：从初始点片出发广度优先搜索由邻接表GL所表示的图。void AJ(adjlist GL,int i,int n)Queue Q;InitQueue(Q);couti*;visitedi=tru
9、e;QInsert(Q,i);while(!QueueEmpty(Q)int k=QDelete(Q);edgenode*p=GLk;while(p!=NULL)int j=p-adjvex;if(!visitedj)|coutnext;五、五、算 法填空(共8 分)如下为二分查找的非递归算法，试将其填写完整。Int Binsch(ElemType A,int n,KeyType K)(int low=0;int high=n-l;while(low=high)-int mi d=(l ow+hi gh)/2；if(K=Amid.key)return mid;/查找成功，返回元素的下标else
10、 if(Knext;ElemType temp=p-data;delete p;return temp;一、一、单 选 题(每 题 2 分，共 20分)1.1.栈和队列的共同特点是(A)。A.只允许在端点处插入和删除元素B.都是先进后出C.都是先进先出D.没有共同点2.2.用链接方式存储的队列，在进行插入运算时(D).A.仅修改头指针 B.头、尾指针都要修改C.仅修改尾指针 D.头、尾指针可能都要修改3.3.以下数据结构中哪一个是非线性结构？(D)A.队列 B.栈 C.线性表 D.二叉树4.4.设 有 一 个 二 维 数 组 网，假 设 A00存放位置在644(I0),A22存放位置在 676
11、(1 0),每个元素占一个空间，问 A33(存放在什么位置？脚注(表示用10进制表示。CA.688 B.678 C.692 D.6965.5.树最适合用来表示(C)。A.有序数据元素 B.无序数据元素C.元素之间具有分支层次关系的数据 D.元素之间无联系的数据6.6.二叉树的第k 层的结点数最多为(D).A.2k-l B.2K+1 C.2K-1 D.2k-17.7.若 有 18个元素的有序表存放在一维数组A19中，第一个元素放Al中，现进行二分查找，则查找A 3 的比较序列的下标依次为(D)A.1,2,3 B.9,5,2,3C.9,5,3 D.9,4,2,38.8.对 n 个记录的文件进行快速
12、排序，所需要的辅助存储空间大致为CA.0(1)B.O(n)C.O(log2n)D.O(n2)9.9.对于线性表(7,34,55,25,64,46,20,1 0)进行散列存储时，若 选 用 H(K)=K%9作为散列函数，则散列地址为1 的元素有(D)个，A.1 B.2 C.3 D.410.1 0.设有6 个结点的无向图，该 图 至 少 应 有(A)条边才能确保是一个连通图。A.5 B.6 C.7 D.8二、二、填 空 题(每空1 分，共 26分)1.1.通常从四个方面评价算法的质量：正确性、_ 易读性、一强壮性_ _ _ _ _ _ _和高效率_ _ _ _ _ _ _2.2.一个算法的时间复杂
13、度为(/+210g2”+14“)/2,其数量级表示为_ 0 (n)。3.3.假定一棵树的广义表表示为A(C,D(E,F,G),H(I,J),则树中所含的结点数为_ 9 个，树的深度为 3,树的度为 3。4.4.后缀算式9 2 3+-10 2/-的值为。中缀算式(3+4X)-2Y/3对应的后缀算式为5.5.若用链表存储一棵二叉树时I 每个结点除数据域外，还有指向左孩子和右孩子的两个指针。在这种存储结构中，n 个结点的二叉树共有 2n 个指针域，其中有 n-1 个指针域是存放了地址，有 n+1 个指针是空指针。6.6.对于一个具有n 个顶点和e 条边的有向图和无向图，在其对应的邻接表中，所含边结点
14、分别有_e_个和_ 2e_个。7.7.AOV府是一种 有向无回路 的图。8.8.在一个具有n 个顶点的无向完全图中，包含有_n(n-l)/2 条边，在一个具有 n 个顶点的有向完全图中，包含有_ n(n-l)条边。9.9.假定一个线性表为(12,23,74,55,63,4 0),若按Key%4 条件进行划分，使得同一余数 的 元 素 成 为 一 个 子 表，则 得 到 的 四 个 子 表 分 别 为(12,40)、_()、(74)_ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _和_ _ _ _ _ (23,55,63)_(10.1 0.向一棵B_树插刀蒜的过程中,若最终引起树根结
15、点的分裂,则新树比原树的高度 增 加 1。11.1 1.在堆排序的过程中，对任一分支结点进行筛运算的时间复杂度为_ O (bg2 n),整个堆排序过程的时间复杂度为O(nlog2 n)。12.1 2.在快速排序、堆排序、归并排序中，一归并 排序是稳定的。3.3.已知一个图的顶点集V 和边集E 分别为：V=1,2,3,4,5,6,7;E=(1,2)3,(1,3)5,(1,4)8,(2,5)10,(2,3)6,(3,4)15,(3,5)12,(3,6)9,(4,6)4,(4,7)20,(5,6)18,(6,7)25;用克鲁斯卡尔算法得到最小生成树，试写出在最小生成树中依次得到的各条边。4.4.画出
16、向小根堆中加入数据4,2,5,8,3 时,每加入一个数据后堆的变化。四、四、阅读算法(每题7分，共14分)1.1.LinkList mynote(LinkList L)/L是不带头结点的单链表的头指针if(L&L-next)q=L；L=L-next；p=L；SI：while(p-next)p=pnext；S2：pnext=q；qnext=NULL；return L；)请回答下列问题：(l)说明语句s i 的功能；(2)说明语句组S 2的功能；(3)设链表表示的线性表为31血，,a”)，写出算法执行后的返回值所表示的线性表。2.2.void ABC(BTNode*BT)(if BT(ABC(BT
17、-left);ABC(BT-right);coutBT-data*;该算法的功能是:五、五、算法填空(共8分)二叉搜索树的查找递归算法：bool Find(BTreeNode*BST,ElemType&item)if(BST=NULL)return fhlse;查找失败else if(item=BST-data)item=BST-data;查找成功return _t rue;else if(itemdata)return F i n d(_ B S T-l e f t,i t e m);else return Find(_ B S T-r i g h t,i t e m);/if六、六、编 写
18、算法(共8 分)统计出单链表H L中结点的值等于给定值X 的结点数。int CountX(LNode*HL,ElemType x)、l.A二、2.D3.D 4.C123456789123456789-、正确性O(n)9-12nen-12e10.10.单选题5.C 6.D 7.D填空题参考答案（每题2 分,8.C 9.D（每 空 1 分,易 读 性 强 壮 性 高 效 率334X*+2 Y*3/-n+1有向无回路n(n-l)/2(12,40)增 加 1共 20分)10.A共 26分)n(n-l)()(74)(23,55,63)311.11.O(log2n)O(nlog2n)12.1 2.归并三、
19、三、运算题(每题6 分，共 24分)1.1.线性表为：(78,50,40,60,34,90)0 1 1 1 01 0 1 0 11 1 0 1 11 0 1 0 12.2.邻接矩阵：0 1 1 1 0邻接表如图11所示：图1 13.3.用克鲁斯卡尔算法得到的最小生成树为：(1,2)3,(4,6)4,(1,3)5,(1,4)8,(2,5)1 0,(4,7)204.4.见 图12四、四、阅读算法(每题7分，共1 4分)1.L(1)查询链表的尾结点(2)将第一个结点链接到链表的尾部，作为新的尾结占(3)返回的线性表为 2月3,“,即?)2.2.递归地后序遍历链式存储的二叉树。五、五、算法填空(每空2
20、分，共8分)t ru e B ST-l eft B ST-right八、，:、编写算法(8分)int C ou nt X(LNode*HL,E l emType x)int i=0;LNode*p=HL;/i 为计数器w hil e(p!=NU LL)if(P-dat a=x)i-H-;p=p-nex t;/w hil e,出循环时i中的值即为x结点个数ret u rn i;/C ou nt X一、一、单选题(每小题2分，共8分)1、1、呷 二b长度为L的顺序线性表中顺序查找值为x的元素时，查找成功时的平均查找长 度(即x与元素的平均比较次数，假定查找每个元素的概率都相等)为A n B n/2
21、 C (n+l)/2 D(n-l)/22、2 公普梨，若口所指结点是P所指结点的前驱结点，若在q与p之间插入-个s所指的结点，则执行(D)。A s-*l ink=p-l ink;p-l ink=s;C p l ink=s f l ink;s fink=p;B p-l ink=s;s-*l ink=q;D q fl ink=s;s-*l ink=p;3、3、栈的插入和删除操作在(A)进行。A栈顶 B栈底 C 任意位置 D指定位置4、4、由权值分别为11,8,6,2,5 的叶子结点生成一棵哈夫曼树，它的带权路径长 度 为(B)A 24 B 71 C 48 D 53二、二、填 空 题(每 空 1分，
22、共 32分)1、1、数据的逻辑结构被分为集合、线性、树 和 图四种。2、2、种抽象数据类型包括 数据描述 和_操作声明 两个部分。3、3、在下面的数组a 中链接存储着一个线性表，表头指针为ao.next,则该线性表为_(38,56,25,60,42,74)a 0 1 2 3 4 5 6 7 860564238742543762014、4、在以 HL为表头指针的带表头附加结点的单链表和循环单链表中，判断链表为空的条件 分 别 为 _H L-n e x t=N U L L 和_ HL=HL-next_ 5、M而具有n 个元素的一维数组存储一个循环队列,则其队首指针总是指向队首元素的前一个位置，该循
23、环队列的最大长度为_n-l。6、6、当堆栈采用顺序存储结构时，栈顶元素的值可用一S.stackS.top-表示；当堆栈采用链接存储结构时，栈顶元素的值可用 HS-data 表示。7、7、一棵高度为5 的二叉树中最少含有 5 个结点，最多含有 31 个结点；一雇高度为5 的理想平衡树中，最少含有 个结点，最多含有 个好点。8、8在图的邻接表中，每个结点被称为一边结点_ _ _ _ _ _ _ _ _ _ _,通常它包含三个域：一是一邻接点域_ _ _ _ _ _ _ _ _ _ _ _;二是一权域_ _ _ _ _ _ _ _ _ _;三是一链域_ _ _ _ _ _ _ _ _ _ _。9、9
24、、在一个索引文件的索引表中，每个索引项包含对应记录的索引值域 和开始位置域 两项数据。10、10、假定一棵树的广义表表示为A(B(C,D(E,F,G),H(I,J),则树中所含的结点数为_ 1 0 个,树的深度为 3，树的度为 3,结点H 的双亲结点为_B_，孩子结点为_ _ _ _ I 和 J_。11、11、在 痴 E 序的过程中，对任一分支结点进行筛运算的时间复杂度为_O(log2 n)，整个堆排序过程的时间复杂度为 O(nlog2 n)。12、12、在对m 阶的B_树插入元素的过程中，每向一个结点插入一个索引项(叶子结点中的索引项为关锤争和空指针)后，若该结点的索引项数等于_ m 个，则
25、必须把它分裂为_ m-l 个结点。三、运算题(每小题6 分，共 24分)1、1、已知一组记录的排序码为(46,79,56,38,40,80,95,2 4),写出对其进行快速排序的每次划分结果。2、2、一个线性表为 B=(12,23,45,57,20,03,78,31,15,3 6),设散列表为HT0.12,散列函数为H(key)=key%13并用线性探查法解决冲突，请画出散列表，并计算等概率情况下查找成功的平均查找长度。3、3、已知一棵二叉树的前序遍历的结果序列是ABECKFGHIJ,中序遍历的结果是EBCDAFHIGJ,试写出这棵二叉树的后序遍历结果。4、4、已知一个图的顶点集V 各边集G
26、如下：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)当它用邻接矩阵表示和邻接表表示时，分别写出从顶点V。出发按深度优先搜索遍历得到的顶点序列和按广度优先搜索遍历等到的顶点序列。假定每个顶点邻接表中的结点是按顶点序号从大到小的次序链接的。图深度优先序列广度优先序列邻接矩阵表示时邻接表表示时四、四、阅读算法，回答问题(每小题8 分，共 16分)1、假定从键盘上输入一批整数，依次为：78 63 45 30 91 34-1,请写出输出结果.#inc
27、lude#include consst int stackmaxsize=30;typcdcf int elemtypc;struct stack elemtype stack stackmaxsize;int top;)；#include stack.hVoid main()stack a;initstack(a);int x;cin x;while(x!=-l)push(a,x);cin x;)while(Istackempty(a)cout pop(a);cout endl;该算法的输出结果为：1、34 91 30 45 63 782、阅读以下二叉树操作算法，指出该算法的功能。Templ
28、ate void BinTree ：unknown(BinTreeNode*t)BinTreeNode*p=t,*temp;if(p!=NULL)temp=p-*leftchild;p-*leftchild=prightchild;p-*rightchild=temp;unknown(p-leftchild);undnown(p-*rightchild);）该 算 法 的 功 能 是：交 换 二 叉 树 的 左 右 子 树 的 递 归 算 法。五、五、算法填空，在画有横线的地方填写合适的内容（10分）对顺序存储的有序表进行二分查找的递归算法。int Binsch(ElemType A,int
29、low,int high,KeyType K)(if(low=high)int mid=1if(K=A mid.key)return mid;else if(K 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;第 一 部分选择题(30分)一、项选择题(本大题共15小题，每小题2 分，共 3 0 分)在每小
30、题列出的四个选项中只有一个选项是符合题目要求的，请将正确选项前的字母填在题后的括号内。1.算法指的是(D)A.计算机程序 B.解决问题的计算方法C.排序算法 D.解决问题的有限运算序列2.线性表采用链式存储时，结点的存储地址(B)A.必须是不连续的B.连续与否均可C.必须是连续的D.和头结点的存储地址相连续3.将长度为n 的单链表链接在长度为m 的单链表之后的算法的时间复杂度为(C)A.0 (1)B.O(n)C.O(m)D.O(m+n)4.由两个栈共享一个向量空间的好处是：(B)A.B.C.D.减少存取时间,节省存储空间,减少存取时间,节省存储空间,降低下溢发生的机率降低上溢发生的机率降低上溢
31、发生的机率降低下溢发生的机率5.设数组datam作为循环队列SQ 的存储空间，什。田为队头指针，rear为队尾指针，则执行出队操作后其头指针fiont值为6.A.front=front+1C.front=(front-l)%m如下陈述中正确的是(AA.串是一种特殊的线性表C.串中元素只能是字母(DB.D.B.D.)front=(front+l)%(m-l)front=(front+l)%m串的长度必须大于零空串就是空白串)7.若目标串的长度为n,模式串的长度为n/3,则执行模式匹配算法时，在最坏情况下的时间复杂度是(C)nA.0(3)B.0 (n)8.一个非空广义表的表头(DA.不可能是子表C
32、.只能是原子C.0 (n2)D.0 (n3)B.只能是子表D.可以是子表或原子9.假於以来行表刁三产叫表表示稀疏矩阵,则和下列行表0 2|3|3|5对应的稀疏矩阵是(A)-0-8 0 6-0-8 0 6-7 0 0 07 0 0 0A.0 0 0 0B.-5 0 4 0-5 0 4 00 0 0 00 0 0 00 3 0 00-8 0 60-8060 0 0 00 0 0 0C.0 2 0 0D.7 0 0 0-5 0 4 0-5 0 4 00 0 0 00 3 0 01 0 .在一棵度为3的树中，度为3的结点个数为2,度为2的结点个数为1,则度为0的结点个数为（C ）A.4 B.5 C.6
33、 D.71 1 .在含n个顶点和e 条边的无向图的邻接矩阵中，零元素的个数为（D ）A.e B.2 e C.n2_e D.n22 e1 2 .假 设 个 有 n个顶点和e条弧的有向图用邻接表表示，则删除与某个顶点环相关的所有弧的时间复杂度是（C ）A.O（n）B.0（e）C.O（n+e）D.O（n*e）1 3 .用某种排序方法对关键字序列（2 5,8 4,2 1,4 7,1 5,2 7,6 8,3 5,2 0）进行排序时;序列的变化情况如下：2 0,1 5,2 1,2 5,4 7,2 7,6 8,3 5,8 41 5,2 0,2 1,2 5,3 5,2 7,4 7,6 8,8 41 5,2 0
34、,2 1,2 5,2 7,3 5,4 7,6 8,8 4则所采用的排序方法是（D ）A.选择排序 B.希尔排序 C.归并排序 D.快速排序1 4 .适于对动态查找及进行高效率查找的组织结构是（C）A.有序表 B.分块有序表 C.三 叉 排 序 树 D.线性链表1 5 .不定长文件是指（B）A.文件的长度不固定 B.记录的长度不固定C.字段的长度不固定 D.关键字项的长度不固定第二部分 非选择题（共 7 0 分）二、填 空 题（本大题共1 0 小题，每小题2分，若有两个空格，每个空格1 分，共 2 0 分）不写解答过程，将正确的答案写在每小题的空格内。错填或不填均无分。1 6 .数据的逻辑结构是
35、从逻辑关系上描述数据，它与数据的存储 无关，是独立于计算机的。1 7 .在一个带头结点的单循环链表中，p 指向尾结点的直接前驱，则指向头结点的指针h e ad可用 p 表示为 h e ad=r）-next-next。1 8 .栈 顶 的 位 置 是 随 着 进栈和退栈 操作而变化的。1 9 .在串S=s t r u c t u r e”中，以 t 为首字符的子串有1 2 个。2 0 .假设一个9阶的上三角矩阵A按列优先顺序压缩存储在一维数组B 中，其中B 0 存储矩阵中第1 个元素a”则 B 3 1 中存放的元素是如_ _ _ _ _ _ _。2 1 .已知一棵完全二叉树中共有7 6 8 结点
36、，则 该 树 中 共 有 3 8 4 个叶子结点。2 2 .已知一个图的广度优先生成树如右图所示，则与此相应的广度优先遍历序列为。23.在 单 链 表 上 难 以 实 现 的 排 序 方 法 有 快 速 排 序 堆 排 序 和希尔排序24.在有序表(12,24,36,48,60,72,8 4)中二分查找关键字72时所需进行的关键字比较次数为 _ _ _ _ _ _ _ _ _ _。25.多重表文件和倒排文件都归属于多关键字 文件。三、解答题(本大题共4 小题，每小题5 分，共 20分)26.画出下列广义表的共享结构图形表示P=(z),(x,y),(x,y),x),)27.请画出与下列二叉树对应
37、的森林。28.已知一个无向图的顶点集为 a,b,c,d,e，其邻接矩阵如下所示abcd0 1 0 0 11 0 0 1 00 0 0 1 10 1 1 0 11 0 1 1 0(1)画出该图的图形；(2)根据邻接矩阵从顶点a 出发进行深度优先遍历和广度优先遍历，写出相应的遍历序列。29.已知二个散刎表号下用所示：|35|20|33|48|丁0 1 23456789 10 11 12其散列函数为h(key户key%13,处理冲突的方法为双重散列法，探查序列为：hj=(h(key)+i*hl(key)%m i=0,1,，m 1其中h 1 (key)=key%11+1回答下列问题：(1)对表中关键字
38、35,20,33和 48进行查找时，所需进行的比较次数各为多少？(2)该散列表在等概率查找时查找成功的平均查找长度为多少？四、算法阅读题(本大题共4 小题，每小题5 分，共 20分)30.下列算法的功能是比较两个链串的大小，其返回值为：comstr(S|,S2)=-101当 S s2请在空白处填入适当的内容。int comstr(LinkString si,LinkString s2)/si和 s2 为两个链串的头指针while(sl&s2)if(sl datedate)retum _ 1：ifisl dates2date)retuml；if(s2 )retum 1 ；iff si(4)ket
39、urnl：return 0 ；31.阅读下面的算法LinkList mynote(LinkList L)/L是不带头结点的单链表的头指针SI：S2：if(L&L-next)q=L；L=L-next；p=L；while(p-next)p=p-next；p-next=q；qnext=NULL；return L；)请回答下列问题：(1)说明语句S I 的功能；查询链衣的尾结点(2)说明语句组S2的功能；将第一个结点链接到链表的尾部，作为新的尾结点(3)设 链 表 表 示 的 线 性 表 为-,an)，写出算法执行后的返回值所表示的线性表。返回的线性表为(22声 3,即 肉)Queue2；3 2.假设
40、两个队列共享一个循环向量空间(参见右下图),其类型Queue2定义如下：typedef struct DateType datafMaxSize；int front2,rear2；对于i=0或 1,fronti reari分别为第i 个队列的头指针和尾指针。请对以下算法填空,实现第i 个队列的入队操作。int EnQueue(Queue2*Q,int i,DateType x)若第i 个队列不满，则元素x 入队列，并返回1；否则返回0if(il)retum 0；if(Q-rearri1=O-frontr(i+l)%2(1)IretumO；Qdata Qreari =x；Qreari1=(Q-r
41、eari1+l)%Maxsize();return 1；3 3.已知二叉树的存储结构为二叉链表，阅读下面算法。typedcf struct node DateType data；Struct node*next；JListNode；typedef ListNode*LinkList；LinkList Leafhead=NULL；Void Inorder(BinTree T)LinkList s；If(T)Inorder(Tlchild)；If(!T-lchild)&(!T-rchild)s=(ListNode*)malloc(sizeof(ListNode)；s-data=Tdata；s-ne
42、xt=Leafhead；Leafhead=s；Inorder(Trchild)；对于如下所示的二叉树D)L UCG(H（1）画出执行上述算法后所建立的结构;（2）说明该算法的功能。五、算法设计题（本题共10分）3 4.阅读下列函数arrange。int arrange(int a,int l,int h,int x)/l和 h 分别为数据区的下界和上界int i,j,t；i=l;j=h；while(ij)while(i=x)j；while(i=x)i+；t=aj；aj=ai；ai=t；if(ainext next19.1220.a4,8 21.38422.abefcdg23.快速排序、堆排序、
43、希尔排序24.2三、解答题(本大题共4 小题，每小题5 分,26.25.多关键字Zyz图 1图 227.2 8.该图的图形为:深度优先遍历序列为：abdce广度优先遍历序列为：abedc29.(1)对关键字35、20、33和 48进行查找的比较次数为3、2、1、1；ASL-3+2+1 +1+2-9(2 )平均查找长度 5 5四、算法阅读题(本大题共4 小题，每小题5 分，共 20分)30.S 1=S1 next s2=s2nexts2(或 s2!=NULL 或 s2&!sl)si(或 sl!=NULL 或 sl&!s2)return 031.(1)查询链表的尾结点(2)将第一个结点链接到链表的
44、尾部，作为新的尾结点(3)返回的线性表为(a2,a3,an,a1)3 2.(i+l)%2(或 l-i)Q-rcari(Qreari+)%Maxsize33.()Leafhead 逝 I e(2)中序遍历二叉树，按遍历序列中叶子结点数据域的值构建一个以Leafhead为头指针的逆序单链表(或按二叉树中叶子结点数据自右至左链接成一个链表)。五、算法设计题(本题共10分)34.(1)该函数的功能是：调整整数数组a中的元素并返回分界值i,使所有 x 的元素均落在a l.i,使所有x 的元素均落在ai+l.h(2)int f(int b,int n)或 int f(int b,int n)int p,q
45、；int p,q：p=arrangc(b,0,n 1,0)；p=arrange(b,0,n 1,1)；q=arrange(b,p+l,n-1,1)；q=arrange(b,0,p,0)；return q-p；return p-q；一、选 择 题(20分)1.组成数据的基本单位是(C)。(A)数据项(B)数据类型(C)数据元素(D)数据变量2.设数据结构 A=(D,R),其中 D=1,2,3,4,R=r,r=,则数据结构A 是(C)。(A)线性结构(B)树型结构(C)图型结构(D)集合3.数组的逻辑结构不同于下列(D)的逻辑结构。(A)线性表(B)栈(C)队列(D)树4.二叉树中第i(iNl)层
46、上的结点数最多有(C)个。(A)2i(B)2(C)2(D)2i-l5.设指针变量p 指向单链表结点A,则删除结点A 的后继结点B 需要的操作为(A)o(A)p-next=p-next-next(B)p=p-next(C)p=p-next-next(D)p-next=p6.设 栈 S 和队列Q 的初始状态为空，元素E l、E2、E3、E4、E 5和 E 6依次通过栈S,个元素出栈后即进入队列Q,若 6 个元素出列的顺序为E2、E4、E3、E6、E5和 E 1,贝 U 栈S 的容量至少应该是(C)o(A)6(B)4(C)3(D)27.将 10阶对称矩阵压缩存储到一维数组A 中，则数组A 的长度最少
47、为(C)。(A)100(B)40(C)55(D)808.设结点A 有 3 个兄弟结点且结点B 为结点A 的双亲结点，则结点B 的度数数为(B)。(A)3(B)4(C)5(D)l9.根据二叉树的定义可知二叉树共有(B)种不同的形态。(A)4(B)5(C)6(D)710.1 0.设有以下四种排序方法，则(B)的空间复杂度最大。(A)冒泡排序(B)快速排序(C)堆排序(D)希尔排序二、填空题(30分)1.1.设顺序循环队列Q。m-1 的队头指针和队尾指针分别为F 和 R,其中队头指针F 指向当前队头元素的前一个位置，队尾指针R 指向当前队尾元素所在的位置，则出队列的语句为F=_(F+l)%m;。2.
48、2.设线性表中有n 个数据元素，则在顺序存储结构上实现顺序查找的平均时间复杂度 为 O(n),在 链 式 存 储 结 构 上 实 现 顺 序 查 找 的 平 均 时 间 复 杂 度 为_O(n)_。3.设 二 攵 树 中 有 n 个结点，则当用二叉链表作为其存储结构时，该二叉链表中共有2n个指针域，n+1 个空指针域。4.4.设指针变量p 指向单链表中结点A,指针变量s 指向被插入的结点B,则在结点A 的后面插入结点 B 的操作序列为_s-next=p-next;p-next=s_。5.5.设无向图G 中有n 个顶点和e 条边，则其对应的邻接表中有 n 个表头结点和 2e 个表结点。6.6.设
49、无向图G 中 有 n 个 顶 点 e 条边，所有顶点的度数之和为m,则 e 和 m 有_m=2e_关系。7.彼二棵二叉树的前序遍历序列和中序遍历序列 均 为 A B C,则该二叉树的后序遍历序列为 CBA。8.8.设一棵完全二叉树中有21个结点，如果按照从上到下、从左到右的顺序从1 开始顺序编号，则编号为8 的双亲结点的编号是 4,编号为8 的左孩子结点的编号是 169.9.下列程序段的功能实现子串t 在主串s 中位置的算法，要求在下划线处填上正确语句。int index(char s,char t)i=j=O;while(istrlen(s)&jnext=p-next;s-next=s5.5
50、.n,2e6.6.m=2e7.7.CBA8.8.4,169.9.i-j+1,010.10.n-1三、应用题1.1.链式存储结构略，前序A BD EC,中序DBEAC,后序DEBCA。2.2.哈夫曼树略，WPL=783.3.(18,5,16,19,21,23),(5,16,21,19,18,23)4 8力 2砥-10/?4-2 5-3 20 1 2 3 4 5 6 7 也一 684.4,线性探测：A 8 A 10 25 32 27 68 链地址法：h l 2 75.5.深度：125364,广度：123456,最小生成树T 的边集为 E=(1,4),(1,3),(3,5),(5,6),(5,6)四