数据结构期末考试试题.pdf

“数据结构”期末考试试题一、单选题(每小题2 分，共 12分)1.在一个单链表H L 中，若要向表头插入一个由指针p指向的结点，则 执 行()。A.H L=p s pn ex t=H LB.pn ex t=H L；H L=p 3C.p-n ex t =H l；p=H L；D.p 一 n ex t=H L n ex t ;H L n ex t =p；2.n个 顶 点 的 强 连 通 图 中 至 少 含 有()。A.n l 条有向边 B.n 条有向边C.n(n-1)/2 条有向边 D.n(n l)条有向边3.从一棵二叉搜索树中查找一个元素时，其 时 间 复 杂 度 大 致 为()0A.0(1)B.0(n)C.0(10 g zn)D.0(n 2)4.由权值分别为3,8,6,2,5 的叶子结点生成一棵哈夫曼树，它的带权路径长度为()。A.24 B.48C.72 D.535.当一个作为实际传递的对象占用的存储空间较大并可能需要修改时，应最好把它说明为()参数，以节省参数值的传输时间和存储参数的空间。A.整形 B.引用型C.指针型 D.常值引用型6.向一个长度为n的顺序表中插人一个新元素的平均时间复杂度为()。A.0(n)B.0(1)C.0(n 2)I).0(10 g 2n)二、填空题(每空1 分，共 28分)1.数据的存储结构被分为、和四种。2.在广义表的存储结构中，单元素结点与表元素结点有一个域对应不同，各自分别为域和域。3.中 缀 表 达 式 3 十 x*(2.4/56)所对应的后缀表达式为-。4.在一棵高度为h的 3 叉树中，最多含有结点。5.假定一棵二叉树的结点数为18,则它的最小深度为，最大深度为-6.在一棵二叉搜索树中，每个分支结点的左子树上所有结点的值一定该结点的值,右子树上所有结点的值一定该结点的值。7.当向一个小根堆插入一个具有最小值的元素时，该元素需要逐层调整，直到被调整到位置为止。8.表示图的三种存储结构为、和-。9.对用邻接矩阵表示的具有n个顶点和e 条边的图进行任一种遍历时，其时间复杂度为,对用邻接表表示的图进行任一种遍历时，其时间复杂度为o10 .从有序表(12,18,30,43,56,78,82,95)中依次二分查找43和 56元素时，其查找长度分别为和-11.假定对长度n =144的线性表进行索引顺序查找，并假定每个子表的长度均为，则进行索引顺序查找的平均查找长度为，时间复杂度为-12.一棵B一树中的所有叶子结点均处在上。13.每次从无序表中顺序取出一个元素，把这插入到有序表中的适当位置，此种排序方法叫做排序；每次从无序表中挑选出一个最小或最大元素，把它交换到有序表的一端，此种排序方法叫做排序。14.快速排序在乎均情况下的时间复杂度为，最坏情况下的时间复杂度为。三、运算题(每小题6 分，共 24分)1.假定一棵二叉树广义表表示为a(b(c,d),c(,8),分别写出对它进行先序、1中序、后序和后序遍历的结果。先序：中序；后序：2.已知一个带权图的顶点集V和边集G分别为：V=0,1,2,3,4,5；E=(0,1)8,(0,2)5,(0,3)2,(1,5)6,(2,3)25,(2,4)13,(3,5)9,(4,5)10,则求出该图的最小生成树的权。最小生成树的权；3.假定一组记录的排序码为(46,7 9,5 6,38,40,8 4,5 0,42),则利用堆排序方法建立的初始堆为。4.有 7个带权结点，其权值分别为3,7,8,2,6,10,14,试以它们为叶子结点生成一棵哈夫曼树，求出该树的带权路径长度、高度、双分支结点数。带权路径长度：高度：双分支结点数：。四、阅读算法，回答问题(每小题8分，共 16 分)1.V 01d A C(L i st&L)(I ni tL i st(L)；I nse rtR e a r(L;25)；I nse rtF ront(L,5 0)；I nta L 4 =5,8,12,15,36;f or(i nti=0;i 5;i+)i f (a i%2=0)I nse rtF ront(L,a i )；e l se l nse rtR e a r(L,a i )；)该算法被调用执行后，得到的线性表L为：2.voi d A G(Q ue ue&Q)(I ni tQ ue ue(Q)；i nta 5 6,12,5,15,8；f or(i nt i=0;i 5;i+)Q l nse rt(Q,a i )；Q I nse rt(Q,Q De l e te (Q)；Q I nse rt(Q,20)；Q I nse rt(Q,Q De l e te(Q)十 16)；wh i l e(!Q ue ue E m pty(Q)c out Q De l e te (Q)”；)该算法被调用后得到的输出结果为：五、算法填空，在画有横线的地方填写合适的内容(每小题6分，共 12分)1.从一维数组A n)中二分查找关键字为K的元素的递归算法，若查找成功则返回对应元素的下标，否则返回一 1。I ntB i nsc h(E l e m T ype A ,I ntl ow,i nt h i g h,K e yT ype K)(i f (l ow d a ta=X)re turn 1;/根结点的层号为 1/向子树中查找x 结点e l se i nt c l=Nod e L e ve l (B T l e f t,X)；i f(c l =l)re turn c l+1;i nt c 2=；i f-;/若树中不存在X结点则返回。e l se re turn 0；)六、编写算法(8 分)按所给函数声明编写一个算法，从表头指针为H L 的单链表中查找出具有最大值的结点,该最大值由函数返回，若单链表为空则中止运行。E l e m T ype M a xV a l ue(L N0d e*H L);“数据结构”期末考试试题答案一、单选题(每小题2 分，共 12分)评分标准；选对者得2 分，否则不得分。1.B 2.B 3.C 4.D 5.B 6.A二、填空题(每空1 分，共 28 分)1 .顺序结构 链接结构 索引结构 散列结构(次序无先后)2 .值(或d a t a)子表指针(或s u b l i s t)3 .3 x 2.4 5/6 一*十4 .一 1)/25 .5 1 86 .小于 大于(或大于等于)7 .向 上 堆顶8 .邻接矩阵 邻接表 边集数组(次序无先后)9.0(n2)0(e)1 0 .1 31 1 .1 3 0()1 2 .同一层1 3 .插人 选择1 4 .0(n l o g 2 n)0(n2)三、运算题(每小题6 分，共 2 4 分)1 .先序：a,b,c,d,e,f,e /2 分中序：c,b,d,a,f,8,e /2 分后序：c,d,b,e,f,e,a /2 分2 .最小生成树的权：3 1 /6分33.(84,79,56,42,40,46,50,38)/6 分4.带权路径长度：131/3 分高度：5/2 分双分支结点数：6/1 分四、阅读算法，回答问题(每小题8 分，共 16分)评分标准：每小题正确得8 分，出现一处错误扣4 分，两处及以上错误不得分。1.(36,12,8,50,25,5,15)2.5 15 8 6 20 28五、算法填空，在画有横线的地方填写合适的内容(每小题6 分，共 12分)1.feturn mid/2 分returnBinsch(A,low,mid-1,K)/2 分returnBmsch(A,mid+1,high,K)/2 分2.NodeLevel(BT right,X)/3 分(c2=l)returnc2 十 1/3 分六、编写算法(8分)评分标准：请参考语句后的注释，或根据情况酌情给分。ElemType MaxValue(LNodeO*HL。)(if(HL=NU1L)/2 分cerr data；/3 分LN0de*p=HI next；/4 分while(P!：NULL)/7 分i f(maxdata)max=p-data；p=p-next；)returnmax；/8 分一、单项选择题（本大题共15小题，第小题2分，共30分）在每小题列出的四个选项中只有一个符合题目要求，请将其代码填在题后的括号内。错选或未选均无分。1 .算 法 必 须 具 备 输 入、输 出 和 C A.计算方法 B.排序方法C.解决问题的有限运算步骤 D.程序设计方法2 .有n个 节 点 的 顺 序 表 中，算 法 的 时 间 复 杂 度 是0（1）的 操 作 是 A A.访问第i个 节 点（i W i W n）B.在第i个节点后插入一个新节点（i W i W n）C.删除第i个 节 点（I W i W n）D,将n个节点从小到大排序43单链表的存储密度ICA.大 于 1B.等 于 1C.小 于 1D.不能确定4.设将整数1,2,3,4,5依次进栈，最后都出栈，出栈可以在任何时刻(只要栈不空)进行,则出栈序列不可能是A.23415B.54132C.23145D.154325.循环队列SQ 的存储空间是数组d m,队头、队尾指针分别是front和 re a r,则执行出队后其头指针front值是D A.front=front+lB.front=(front+l)%(m-l)C.front=(front-1 )%mD.front=(front+l)%m6.在一个具有n 个结点的有序单链表中插入一个新结点并仍然保持有序的时间复杂度是B1A.O(l)B.0(n)C.0(n2)D.O(nlogn)7.设二维数组按行优先顺序存储，则 元 素 的 地 址 为B5A.L OC(A 0 0 )+(i*m+j)B.L O C(A 0 0)+(i*n+j)8.D9 A1 0.I D1 1 .C1 2.C1 3 .C.L O C(A 0 0)+(i-1 )*n+j-l D.L O C(A 0 0)+(i-1 )*m+j-l 一 个 非1空 广 义 表 的 表 头JA.一定是子表B.定是原子C.不能是子表D.可以是原子，也可以是子表具 有 n 个 节点的完全二叉树的深度为1A.F l o g 2(n+1)1-1B.I o g 2 n+1C.l o g2nD.L l o g2n J若 要惟一地确定一棵二叉树，只 需 知 道该二叉 树 的A.前序序列B.中序序列C.前序和后序序列D.中序和后序序列在 一 个 无 向 图 中，所 有 顶 点 的 度 数 之 和 等 于 图 的 边 数 的 倍A.1/2B.1C.2D.4拓 扑 排1序 运 算 只 能 用 于1A.带权有向图B.连通无向图C.有向无环图D.无向图在 所 有 排 序 方 法 中，关 键 字 比 较 的 次 数 与 记 录 的 初 始 排 列 次 序 无 关 的 是DA.希尔排序B.冒泡排序6C.插入排序 D.选择排序1 4.下 列 排 序 算 法 中 时 间 复 杂 度 不 受 数 据 初 始 状 态 影 响，恒 为0(一)的是CA.堆排序C.直接选择排序15二 分A A.有序、顺序存储C.无序、顺序存储B.冒泡排序D.快速排序查 找 要 求 节 点B.有序、链接存储D.无序、链接存储二、填空题(本大题共10小题，每小题2分，共20分)不写解答过程，将正确的答案写在每小题的空格内。错填或不填均无分。16.数据的逻辑结构分为两大类，匕们是线性结构和 非线性结构 o17.在单链表中(假设结点指针域名称为n e x t),删除指针P所指结点的后继结点的语句是D-n e x t=p-n e x t-n e x t。18.已知循环队列用数组datan存储元素值，用front,rear分别作为头尾指针，则当前元素个数为(r e a r-f r o n t+n)%n。19.若n为主串长，m为子串长，则串的朴素匹配算法最坏的情况下需要比较字符的总次数为(n-m+1)X m。20.广义表(a),(b),j,(d)的表尾是(b).i,(d)_。21.已知二叉树有61个叶子节点，且仅有一个孩子的节点数为4 5,则总节点数为 16672 2.解决计算机与打印机之间速度不匹配问题，须要设置一个数据缓冲区，应 是 一 个 队列 结 构。23.n 个顶点e 条边的图采历 算 法 的 时 间 复 杂 度 为021414-6207252433184115用邻接表存储，深度优先遍O(n+e)2 4.对 于 n 个关键字的集合进行冒泡排序，在最坏情况下所需要的时间为 0 （r?）25.在一个长度为n 的顺序表中的第i 个 元 素（IWiWn）之前插入一个元素时，需向后移 n-i+1 个元素。三、解 答 题（本大题共4 小题，共 25分）26.对于下面的稀疏矩阵，画出其三元组法存储表示（假设下标从。开始）。（5 分）0 0 140 0 07 0 00 0 0I 0 15 00 0 00-6 00 0 2418 0 00 0 0答案:行号 列号012345值27.已知一棵二叉树的中序序列和后序序列分别如卜，请画出该二叉树。（5 分）中序序列：DI GJ LKBAECHF后序序列：I LKJ GDBEHFCA答案：GH2 8.设有一个关键码的输入序列 5 5,3 1,1 1,3 7,4 6,7 3,6 3,0 2,0 7 ,（7分）（1）从空树开始构造平衡二叉搜索树，画出每加入一个新结点时二叉树的形态。若发生不平衡，指明需做的平衡旋转的类型及平衡旋转的结果。（3分）（2）计算该平衡二叉搜索树在等概率下的搜索成功的平均搜索长度和搜索不成功的平均搜索长度。（4分）【解答】（1）构造平衡二又搜索树的过程（2）计算在等概率下的搜索成功的平均搜索长度和搜索不成功的平均搜索卜度.ASLx =（1/9）*（1 +2 *2 +3 *4 +4 *2）=2 5/9ASLg =（1/1）*（3*6 十 4/4）=1 7/5 2 9.已知个图的邻接表如下所示。（8分）（1）画出该图的图形；（4分）（2）根据邻接表分别画出从顶点a出发进行深度优先和广度优先遍历所生成的生成树。（4分）A9四、算法阅读题(本大题共3小题，每小题5分，共15分)30.设 线 性 表 的 n 个 结 点 定 义 为 在 顺 序 表 上 实 现 的 插 入 和 删 除 算 法 如 下,请在空白处填入适当内容。(顺序表的最大可容纳项数为MaxSize)Template int SeqList:Insert(Type&x,int i)If(ilast+l II last=)return 0;Else Last+;For(int j=last;ji;j-)d a t a j =(2);(3)_;Return 1;)Template class Typo int seqList:Remove(Type&x)int i=Find(x);if(i=0)last-;for(int j=(4)return 1;jtop!=StackSize-1)s-data+s-top=x;)DataType Pop(SeqStack*s)10if(s-top!=-l)return s-datas-top-;)void main()(DataType i;SeqStack s;s.top=-l;scanfC%d,&i);while(i!=-l)(push(&s,i);scanf(cT,&i);)while(s-top!=-l)(i=Pop(&s);printf(“%6d”,i);答案：(1)程序的功能是把输入的审整 数(用 做 结 束 标 记)，按照与输入相反的次序输出。用栈实现这一功能。(2)输 出 结 果 8765432 lo3 2.已知二叉树的存储结构为二叉链表，阅读下面算法。说明该算法的功能。Templateint BinaryTree:height(BinTreeNode*t)if(t=NULL)return-1;int hl=height(t-leftChild);int hr=height(t-rightChild);return l+(hlhr?hl:hr);)答案：该算法的功能是统计二叉树的高度。五、算法设计题(本题 共10分)3 3.设一棵二叉树以二叉链表表示，试以成员函数形式编写有关二叉树的递归算法。(1)统计二叉树中度为1 的结点个数；(5 分)(2)统计二叉树中度为2 的结点个数。(5 分)(提示：递归算法如32题所示)解答：(1)统计二叉树中度为1 的结点个数。Tempi ateInt BinaryTree:Degree 1 (BinTreeNode*t)constIf(t=NULL)return 0;1 1If(t-leftchild!=NULL&t-rightchild=NULL&t-rightchild!=NULL)Return 1 +Degree 1 (t-leftchild)+Degree l(t-rightchild);Return Degree 1 (t-leftchild)+Degreel(t-rightchild);t-leftchild=NULL(2)统计二叉树中度为2的结点个数。TemplateInt BinaryTree:Degree2(BinTreeNode*t)constIf(t=NULL)return 0;If(t-leftchild!=NULL&t-rightchild!=NULL)Return 1 +Degree2(t-leftchild)+Degree2(t-rightchild);Return Degree2(t-leftchild)+Degree2(t-rightchild);)“数据结构”期末考试试题一、单选题(每小题2 分，共 1 2 分)1 .在一个单链表H L 中，若要向表头插入一个由指针p 指向的结点，则执行()。A.H L=ps p 一 ne xt=H LB.p ne xt=H L；H L=p3C.p ne xt=H l；p=H L；D.p 一 ne xt=H L ne xt;H L 一 ne xt=p；2 .n 个 顶 点 的 强 连 通 图 中 至 少 含 有(),A.n1 条有向边 B.n 条有向边C.n(n1)/2 条有向边 D.n(n-T)条有向边3.从一棵二叉搜索树中查找一个元素时，其时间复杂度大致为()。A.0(1)B.0(n)C.0(1 0 g z n)D.0(n 2)4.由权值分别为3,8,6,2,5 的叶子结点生成一棵哈夫曼树，它的带权路径长度为()。A.24 B.48C.7 2 D.535.当一个作为实际传递的对象占用的存储空间较大并可能需要修改时，应最好把它说明为()参数，以节省参数值的传输时间和存储参数的空间。A.整形 B.引用型C.指针型 D.常值引用型6 .向一个长度为n的顺序表中插人一个新元素的平均时间复杂度为()oA.0(n)B.0(1)C.0(n 2)D.0(1 0 g 2n)二、填空题(每空1 分，共 28 分)1 .数据的存储结构被分为、和四种。2.在广义表的存储结构中，单元素结点与表元素结点有一个域对应不同，各自分别为-域和-域。3.中 缀 表 达 式 3 十 x*(2.4/56)所对应的后缀表达式为-。4.在一棵高度为h的 3 叉树中，最多含有结点。5.假定一棵二叉树的结点数为1 8,则它的最小深度为，最大深度为-6 .在一棵二叉搜索树中，每个分支结点的左子树上所有结点的值一定该结点的值,右子树上所有结点的值一-定该结点的值。7 .当向一个小根堆插入一个具有最小值的元素时，该元素需要逐层调整，直到被调 整 到，位置为止。128 .表示图的三种存储结构为、和-。9 .对用邻接矩阵表示的具有n个顶点和e条边的图进行任一种遍历时，其时间复杂度为，对用邻接表表示的图进行任一种遍历时，其时间复杂度为。1 0 .从有序表(1 2,1 8,30,43,56,7 8,8 2,9 5)中依次二分查找43和 56 元素时，其查找长度分别为和-1 1 .假定对长度n=1 44的线性表进行索引顺序查找，并假定每个子表的长度均为，则进行索引顺序查找的平均查找长度为，时间复杂度为-1 2.一棵B 一树中的所有叶子结点均处在上。1 3.每次从无序表中顺序取出一个元素，把这插入到有序表中的适当位置，此种排序方法叫做排序；每次从无序表中挑选出一个最小或最大元素，把它交换到有序表的一端，此种排序方法叫做排序。1 4.快速排序在乎均情况下的时间复杂度为，最坏情况下的时间复杂度为。三、运算题(每小题6 分，共 24分)1 .假定一棵二叉树广义表表示为a(b(c,d),c(,8),分别写出对它进行先序、中序、后序和后序遍历的结果。先序:中序；后序：2.已知一个带权图的顶点集V和边集G分别为：V=0,1,2,3,4,5；E=(0,1)8,(0,2)5,(0,3)2,(1,5)6,(2,3)25,(2,4)1 3,(3,5)9,(4,5)1 0 ,则求出该图的最小生成树的权。最小生成树的权；3.假定一组记录的排序码为(46,7 9,56,38,40,8 4,50,42),则利用堆排序方法建立的初始堆为。4.有 7个带权结点，其权值分别为3,7,8,2,6,1 0,1 4,试以它们为叶子结点生成 棵 哈 夫 曼 树，求出该树的带权路径长度、高度、双分支结点数。带权路径长度：高度：双分支结点数：。四、阅读算法，回答问题(每小题8 分，共 1 6分)1.V01 dAC(L i s t&L)(I n i t L i s t(L)；I n s e r t R e ar(L;25)；I n s e r t F r o n t(L,50)；I n t aL 4=5,8,1 2,1 5,36);f o r(i n t i=0;i 5;i+)i f (ai%2 0 )I n s e r t F r o n t (L,ai)；e l s e l n s e r t R e ar(L,ai)；)该算法被调用执行后，得到的线性表L为：2.v o i d AG(Q u e u e&Q)(I n i t Q u e u e(Q)；i n t a5=6,1 2,5,1 5,8；f o r (i n t i=0;i 5;i+)Q I n s e r t (Q,ai)；Q I n s e r t(Q,Q De l e t e(Q)；Q I n s e r t(Q,20)；Q I n s e r t(Q,Q De l e t e(Q)十 1 6)；w h i l e(!Q u e u e Em p t y(Q)co u t Q De l e t e(Q)”；13该算法被调用后得到的输出结果为：五、算法填空，在画有横线的地方填写合适的内容(每小题6 分，共 1 2分)1.从 维数组An)中二分查找关键字为K的元素的递归算法，若查找成功则返回对应元素的下标，否则返回一 1。I n t Bi n s ch(El e m Tv p e A,I n t l o w,i n t h i g h,K e y Tv p e K)(i f (l o w=h i g h)(i n t m i d=(l o w+h i g h)/2；i f (K=Am i d.k e y)-；e l s e i f (K dat a=X)r e t u r n 1;/根结点的层号为 1/向子树中查找x结点e l s e i n t cl=N o de L e v e l (BT-l e f t,X)；i f(cl =l)r e t u r n cl+1;i n t c2=；i f;/若树中不存在X 结点则返回。e l s e r e t u r n 0；)六、编写算法(8分)按所给函数声明编写一个算法，从表头指针为H L 的单链表中查找出具有最大值的结点,该最大值由函数返回，若单链表为空则中止运行。El e m Ty p e M ax Val u e(L N 0de*H L);“数据结构”期末考试试题答案一、单选题(每小题2 分，共 1 2分)评分标准；选对者得2 分，否则不得分。1.B 2.B 3.C 4.D 5.B 6.A二、填空题(每空1 分，共 28分)1.顺序结构 链接结构 索引结构 散列结构(次序无先后)2.值(或dat a)子表指针(或s u bl i s t)3.3 x 2.4 5/6*十4.(3h 1)/25.5 1 8146.小 于 大于（或大于等于）7.向上 堆顶8.邻接矩阵 邻接表 边集数组（次序无先后）9.0（n2）0（e）1 0.1 31 1 .1 3 0()1 2.同一层1 3.插人 选择1 4.0(n l o g2n)0(n2)三、运算题（每小题6 分，共 24分）1.先序：a,b,c,d,e,中序：c,b,d,a,f,8,后序：c,d,b,e,f,e,f,ee/2 分/2 分a/2 分2.最小生成树的权：31 /6 分3.（84,79,56,42,40,46,50,38）/6 分4.带权路径长度：1 31 /3 分高度：5/2 分双分支结点数：6/1 分四、阅读算法，回答问题（每小题8 分，共 1 6分）评分标准：每小题正确得8 分，出现一处错误扣4 分，两处及以上错误不得分。1.(36,12,8,50,25,5,15)2.5 15 8 6 20 28五、算法填空，在画有横线的地方填写合适的内容(每小题6 分，共 12分)1.feturn mid /2 分returnBinsc h(A,low,mid -1,K)/2 分returnBmsc h(A,mid+1,high,K)/2 分2.Nod eLev el(BT right,X)/3 分(c 2=l)returnc 2 十 1/3 分六、编写算法(8分)评分标准：请参考语句后的注释，或根据情况酌情给分。ElemT ype Ma xV a lue(LNod eO*HL。)(if(HL=NU 1L)/2 分c errz，Linked list is empty!end l；exit(1)；)ElemT ypema x：HL-d a ta；/3 分LN0 d e*p=HI next；/4 分while(P!：NU LL)/7 分if(ma xd a ta)ma x=p d a ta；p=p-next；)returnma x；/8 分)数据结构与算法复习题四、应用简答题。151.有下列几种用二元组表示的数据结构，画出它们分别对应的逻辑图形表示，并指出它们分别属于何种结构。(1)A =D,R ,其中：D=a,b,c,d,e,f,g,h,R=r,r=.,(2)B=D,R ,其中：D=a,b,c,d,e,f,g,h,R=r,r=,(3)C=D,R ,其中：D=1,2,3,4,5,6,R=r,r=(1,2),(2,3),(2,4),(3,4),(3,5),(3,6),(4,5),(4,6)2.简述顺序表和链表存储方式的特点。答：顺序表的优点是可以随机访问数据元素，缺点是大小固定，不利于增减结点(增减结点操作需要移动元素)。链表的优点是采用指针方式增减结点，非常方便(只需改变指针指向，不移动结点)。其缺点是不能进行随机访问，只能顺序访问。另外，每个结点上增加指针域,造出额外存储空间增大。3.对链表设置头结点的作用是什么？(至少说出两条好处)答：其好处有：(1)对带头结点的链表，在表的任何结点之前插入结点或删除表中任何结点，所要做的都是修改前一个结点的指针域，因为任何元素结点都有前驱结点(若链表没有头结点，则首元素结点没有前驱结点，在其前插入结点和删除该结点时操作复杂些)。(2)对带头结点的链表，表头指针是指向头结点的非空指针，因此空表与非空表的处理是一样的。4.对于一个栈，给出输入项A,B,C o如果输入项序列由A,B,C组成，试给出全部可能的输出序列。5.设有4个元素1、2、3、4依次进栈，而栈的操作可随时进行(进出栈可任意交错进行，但要保证进栈次序不破坏1、2、3、4的相对次序)，请写出所有不可能的出栈次序和所有可能的出栈次序.6.现有稀疏矩阵A如图所示，要求画出三元组表示法和十字链表表示法：1500220-150133000000-600000000910000000280007.设4维数组的4个下标的范围分别为l-l.0J,1,2,11,3J,1-2,-1,请分别按行序和列序列出各元素。8.有一份电文中共使用5个字符：a,b,c,d,e,它们出现的频率依次为4,7,5,2,9,试画出对应的哈夫曼树(请按左子树根结点的权小于等于右子树根结点的权的次序构造)，并求出每个字符的哈夫曼编码。169.有如图所示的二叉树，回答如下问题。(1)(2)(3)(4)(5)(6)写出该树的中序遍历序列;写出该树的先序遍历序列;写出该树的后序遍历序列:画出该二叉树的中序线索二叉树;画出该二叉树的后序线索二叉树;画出该二叉树对应的森林；10 已 知 棵 树 边 的 集 合 为,，画 出这棵树。11.假设二叉树采用顺序存储结构，如图所示。(1)画出二叉树表示；(2)写出先序遍历、中序遍历和后序遍历的结果；(3)写出结点值c 的双亲结点，其左、右孩子；(4)画出把此二叉树还原成森林的图。1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20e a f d g c j h i b12.已知一棵二叉树的中序序列为cbedahgijf,后序序列为cedbhjigfa,画出该二叉树的先序线索二叉树。13.某二叉树的先序遍历序列是abdgcefh,中序遍历序列是dgbaechf,给出其后序遍历序列。14.将下图所示森林转换成为二叉树，并写出转化后二叉树中序遍历结果。E FN O171 5 .有一份电文中共使用8个字符：a、b、c、d、e、f、o、i,它们的出现频率依次为1 0,20,1 5,3 2,4 0,6 0,26,1 8。试画出对应的哈夫曼树(请按左子树根结点的权小于等于右子树根结点的权的次序构造)，并求出每个字符的哈夫曼编码。1 6 .已知某系统在通信联络中只可能出现A,B,C,D,E,F,Q H 八种字符，其频率为0.0 5,0.29,0.0 7,0.0 8,0.1 4,0.23,0.0 3,0 1 1 试设计哈夫曼编码。1 7 .对有五个顶点 v l,v 2,v 3,v 4,v 5 的图的邻接矩阵如图所示，解答下列问题：(1)画出逻辑图。(2)画出该逻辑结构的邻接表。(3)基于邻接矩阵写出图的深度、广度优先遍历序列。01003000100000000000060020000010000000000005001 8 .如图所示，解答如下问题：(1)写出从定点A出发，深度和广度优先遍历方法遍历该图的顶点序列。(2)根据普里姆算法和克鲁斯卡尔算法，分别求它的最小生成树，要求给出构造过程。1 9 .给出如图所示的无向图G 的邻接矩阵和邻接表两种存储结构。并在给定的邻接表的基础上，指出从顶点1 H l 发的深度优先遍历和广度优先遍历序列。1820.使用普里姆算法构造出如图所示的图G 的一棵最小生成树。21.使用克鲁斯卡尔算法构造出如图所示的图G 的 棵最小生成树。22.设有一棵二叉树，它的中序和后序遍历结果如下，请画出该二叉树。中序：1 4 3 5 6 2后序：4 6 5 3 2 123.设一棵顺序二叉树具有10个结点，请计算其中叶子结点的数目。24.设如图所示二叉树是由某棵树转化而来，请画出其对应的原树。1912 5.设有如图所示的一棵树，请将其转化为二叉树。10 1112 13 92 6.下表给出了某工程各工序之间的优先关系和各工序所需时间。解答下列问题:(1)画出相应的AOE图；(2)给出各事件的最早发生时间和最晚发生时间；(3)找出关键路径，并指明完成该工程所需最短时间；(4)若把AOE网视为AOV网，给出其一个拓扑序列的例子。工 序代号ABCDEFGHIJKLMM时间151050815409015806015302040先 驱工作A,BBC,DBEGIEIF.IH,J,K LG2 7.某不带权有向图如下所示。给出其邻接矩阵和邻接表表示。202 8.求如下A O E图的关键路径，要求给出求解过程。2 9.有一组数据，内容如下：8,1 5,3 8,5 7,6 8,8 8,9 8,1 0 8,1 2 9,2 3 4,2 5 6试用二分查找法查找6 8 和 2 2 2,要求先画出二叉折半检索树，然后写出查找过程。3 0 .已知有序表为 1 2,1 8,2 4,3 5,4 7,5 0,6 2,8 3,9 0,1 1 5,1 3 4 ,请画出采用折半查找法对应的判断树。3 1 .设数据集合d=1,1 2,5,8,3,1 0,7,1 3,9),试完成下列各题：(1)依次取d中各数据，构造一棵二叉排序树b t。(2)如何依据此二叉树b t得到d的一个有序序列。(3)画出在二叉树b t中删除“1 2”后的树结构。3 2 .对给定的数列R=7,1 6,4,8,2 0,9,6,1 8,5 ,构造一棵二叉排序树，并且(1)给出按中序遍历得到的数列Rl(1)给出按后序遍历得到的数列R2。3 3 .已知序列 1 7,1 8,6 0,4 0,7,3 2,7 3,6 5,8 5 ,请给出采用冒泡排序法对该序列作升序排序时每一趟的结果。213 4.已知序列 5 0 3,8 7,5 1 2,6 1,9 0 8,1 7 0,8 9 7,2 7 5,6 5 3,4 6 2 ,请给出采用快速排序法对该序列作升序排序时每一趟的结果。3 5.已知序列 5 0 3,8 7,5 1 2,6 1,9 0 8,对该序列作升序排序时每一趟的结果。1 7 0,8 9 7,2 7 5,6 5 3,4 6 2 ,请给出采用堆排序法3 6.已知序列 5 0 3,8 7,5 1 2,6 1,9 0 8,1 7 0,法对该序列作升序排序时每一趟的结果。8 9 7,2 7 5,6 5 3,4 6 2 ,请给出采用希尔排序3 7.已知序列 1 7,1 8,6 0,4 0,7,3 2,7 3,6 5,8 5 ,请给出采用直接插入排序法对该序列作升序排序时每一趟的结果。3 8.设散列表的长度m=1 3 (0,1,2,1 2),散列函数为H (k)=k m o d m,给定的关键字序列为 1 9,1 4,2 3,1 0,6 8,2 0,8 4,2 7,5 5,1 1 。试画出用线性探测法解决冲突时所构造的散列表。五、算法设计题。1 .已知一个顺序表L,其中的元素按值非递减有序排列，设计一个算法插入一个元素x 后保持该顺序表仍按非递减有序排列。2 .设计一个算法从顺序表L中删除所有值为x 的元素。3 .已知线性表元素递增有序，并以带头结点的单链表作存储结构，设计一个高效算法，删除表中所有值大于m in k 且小于m a xk 的元素(若表中存在这样的元素)。并分析所写算法的时间复杂度。4 .设计一个在带头结点的单链表中删除一个最小值结点的高效算法。5 .有一个不带头结点的单链表L (至少有一个结点)，其头指针为he a d。设计一个算法将L逆置，即最后一个结点变成第一个结点，原来倒数第二个结点变成第二个结点，如此等等。6 .假设二叉树采用链式存储方式存储，编写个二叉树前序遍历的非递归算法。7 .假设二叉树采用链式存储方式存储，编写个二叉树后序遍历的非递归算法。8 .假设二叉树采用链式存储方式存储，编写一个二叉树中序遍历的非递归算法。9 .编写一个C+函数。实现线性表就地逆置。即在原表的存储空间内将线性表(a l,a 2,a n)逆 置 为(a n,.,a 2,a l)o1 0 .编 写 个单链走倒链程序，即将单链表中每个结点的前驱与后继关系颠倒。1 1 .在数组a 0n-1 中存放有n个不同的整数，请编写一个函数，将 a 中的n个数按从小到大的顺序排列。1 2 .有一个不带头结点的单链表L (至少有一个结点)，其头指针为h e ad。设计一个算法将L逆置，即最后一个结点变成第一个结点，原来倒数第二个结点变成第二个结点，如此等等。1 3 .已知非空线性链表的第一个结点的指针为h e ad