数据结构代码-软件03试卷

。担由此引。担由此引起的一切场纪律，并知道考专 班 学号 学生签名数据结构课 课程类别：必修课闭题—二三四五六七八九 分注意：除第一大题外其余各题答案必须填写在后面的答题一．选择填空题（1－5题每空2分，6－13题每空1分已知P结点是某双向链表的中间从下列提供的答案在P结点后插入S结点的语句序列 G_L_F C_在P结点前插入S结点的语句序列是_H_M_E_D 删除P结点的直接后继结点的语句序列是_OKAR删除P结点的直接前驱结点的语句序列是_ J_BR_删除P结点的语句序列 I_N_Q （A）p->next=p->next->next;(B)p->prior=p->prior-(C)p- (D)p- (E)s-(I)p->prior->next=p->next;(J)Q->prior-=p（L）p-（M）p->prior->prior（O）Q=（P）Q=p- (R)表长为13希表中已填有关键字为23，46，69,28的记录，用除留余数法构造哈希函数现有第5，6个记录，其关键字为35，39按二次探测再散列的方法处理，将它填入表中相应的位置。2题35在下标为11位置，39填在下标为73题4题根据上图判断下列拓扑序列不正确的 C1--C2--C3--C4--C5--C7--C9--C10--C11--C6--C12--C9--C10--C11--C6--C1--C12--C4--C2--C3--C5--C7--C1—C3—C2--C4--C5--C7--C9--C10--C11--C6--C12--C1—C4—C2—C3--C5--C7--C9--C10--C11--C6--C12--写出第4题图中所有的关键路径 在下图中那种序列是深度优先遍历序 5题 (B) (D)在顺序表上做插入运算，平均要移动表中一半元素。当表长n大时，算法的效率相当低。将一棵有99个结点的完全二叉树到右依次对结点进行根结点的号码为1，则编号为50的结点的左孩子编号为D.(A)98(B99(C)100(D8．n个顶点的完全有向图中含有边的条数 B (A) (B)n(n- (C) (D)栈和队列的共同特点 D (A)都是先进后 （B）都是先进先（C）没有共同点（D）许在端点处插入和删 即数据之间的相互关系和数据的 物理结构 即数据结构在计在循环链表中，可以根据任一结点的地址遍历整个链表，而单链表中需知道 表头结点 才能遍历整个链表。12．栈通常采用的两种结构 C 。（A）循环和链式结构（B）散列和索引结（C）链式和数组结构 （D）线性和非线性结构 二．简答题（60分在栈的操作中，进栈顺123456，问能否得到435612135426的出栈序列明为什么不能得到或如何能得（即写出以push（S，X）表示进栈和以pop（S，X）表示出栈的操作序列（6利用广义表的GetTail和GetHead操作写出函数表达式L3从下面的广义表中取L3（4分＝（（（，试分别画出具有三个结点的树和三个结点的二叉树的所同形态（7分已知一棵二叉树的先序系列为ABDGHJKECFIM,中序序列GDJHKBEACFMI,试画出此二（7分）分别对下图按普里姆算法（从A结点开始）和克鲁斯卡尔算法画出其最小生成树（8分）18题假设用于通信的电文由八个字母A,B,C,D,E,F,G,H组成，字母在电文中出现的频率分别为 0.19,0.02,0.06,0.32,0.21,0.10为这八个字母设计哈夫曼树且分别写出其哈夫曼编码，计算其带权路径长度WPL（8分）记录的关键字序列42，45，78，86,试构造一棵二叉排序树，并写出其构造过分21题利用迪杰斯特拉(Dijkstra)算法求上图中从顶点0到其他各顶点间的最短