《东南大学十套大数据的结构试的题目及问题解释》由会员分享，可在线阅读，更多相关《东南大学十套大数据的结构试的题目及问题解释（24页珍藏版）》请在金锄头文库上搜索。
1、实用标准文案数据结构试卷（一）三、计算题（每题6分，共24 分）1. 在如下数组A 中链接存储了一个线性表，表头指针为A 0.next，试写出该线性表。A01234567data605078903440next35720412. 请画出下图的邻接矩阵和邻接表。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;用克鲁斯卡尔算法得到最小生成树，试写出在最小生成树中依次得到的各条边。
2、4.画出向小根堆中加入数据4, 2, 5, 8, 3时，每加入一个数据后堆的变化。四、阅读算法（每题7 分，共 14 分）1.LinkList mynote(LinkList L)/L是不带头结点的单链表的头指针if(L&L-next)q=L； L=L next ； p=L；S1：while(p next) p=p next ；S2：pnext=q ； q next=NULL；return L；请回答下列问题：（ 1）说明语句 S1 的功能；（ 2）说明语句组 S2 的功能；（ 3）设链表表示的线性表为（ a1,a 2,a n）, 写出算法执行后的返回值所表示的线性表。2.void ABC(B
3、TNode * BT)if BT ABC (BT-left);ABC (BT-right);coutdatadata)item=BST-data;/查找成功return _;else if(itemdata)return Find(_,item);else return Find(_,item);/if六、编写算法（共8 分）统计出单链表HL 中结点的值等于给定值X 的结点数。int CountX(LNode* HL,ElemType x)精彩文档实用标准文案数据结构试卷（二）三、应用题 (36 分 )1 设一组初始记录关键字序列为(45 ，80， 48， 40， 22，78) ，则分别给出第
4、4 趟简单选择排序和第4 趟直接插入排序后的结果。2 设指针变量p 指向双向链表中结点A，指针变量q 指向被插入结点B，要求给出在结点A的后面插入结点B的操作序列（设双向链表中结点的两个指针域分别为llink和 rlink）。3 设一组有序的记录关键字序列为(13 ，18， 24， 35， 47，50， 62， 83，90) ，查找方法用二分查找，要求计算出查找关键字62 时的比较次数并计算出查找成功时的平均查找长度。4 设一棵树T 中边的集合为(A ， B) ，(A ， C)， (A ，D)， (B， E) ，(C， F)， (C， G) ，要求用孩子兄弟表示法（二叉链表）表示出该树的存储结
5、构并将该树转化成对应的二叉树。5 设有无向图G，要求给出用普里姆算法构造最小生成树所走过的边的集合。6 设有一组初始记录关键字为(45 ， 80， 48，40，22，78) ，要求构造一棵二叉排序树并给出构造过程。四、算法设计题(16 分 )1 设有一组初始记录关键字序列（K1，K2， ， Kn），要求设计一个算法能够在O(n) 的时间复杂度内将线性表划分成两部分，其中左半部分的每个关键字均小于Ki ，右半部分的每个关键字均大于等于Ki 。2 设有两个集合A 和集合 B，要求设计生成集合C=A B 的算法，其中集合A、B 和 C用链式存储结构表示。精彩文档实用标准文案数据结构试卷（三）二填空题
6、1. 下列算法实现在顺序散列表中查找值为 x 的关键字，请在下划线处填上正确的语句。 struct recordint key; int others;int hashsqsearch(struct record hashtable ,int k)int i,j; j=i=k % p;while(hashtablej.key!=k&hashtablej.flag!=0)j=(_)%m; if(i=j)return(-1);if (_ ) return(j); else return(-1);2.下列算法实现在二叉排序树上查找关键值k，请在下划线处填上正确的语句。typedefstructnod
7、eintkey;structnode *lchild;structnode *rchild;bitree;bitree *bstsearch(bitree *t, int k)if (t=0 ) return(0);else while (t!=0)if(t-key=k)_;elseif(t-keyk)t=t-lchild;else_;三、计算题 ( 每题 10 分，共 30 分 )1. 已知二叉树的前序遍历序列是AEFBGCDHIKJ，中序遍历序列是EFAGBCHKIJD，画出此二叉树，并画出它的后序线索二叉树。2已知待散列的线性表为（ 36，15，40，63，22），散列用的一维地址空间为
8、 0 . 6 ，假定选用的散列函数是 H（ K） = K mod 7 ，若发生冲突采用线性探查法处理，试：（ 1）计算出每一个元素的散列地址并在下图中填写出散列表：0123456（ 2）求出在查找每一个元素概率相等情况下的平均查找长度。3已知序列（ 10，18， 4， 3， 6，12，1，9，18，8）请用快速排序写出每一趟排序的结果。四、算法设计题( 每题 15 分，共 30 分 )1 设计在单链表中删除值相同的多余结点的算法。2 设计一个求结点x 在二叉树中的双亲结点算法。精彩文档实用标准文案数据结构试卷（四）1 设一组初始记录关键字序列为(20 ， 18， 22， 16， 30， 19)
9、 ，则以 20 为中轴的一趟快速排序结果为 _ 。2 设一组初始记录关键字序列为(20 ，18，22，16，30，19) ，则根据这些初始关键字序列建成的初始堆为_ 。3 设某无向图G 中有 n 个顶点，用邻接矩阵A 作为该图的存储结构，则顶点i和顶点 j互为邻接点的条件是_ 。4 设无向图对应的邻接矩阵为A，则 A 中第 i 上非 0 元素的个数 _第 i 列上非 0元素的个数（填等于，大于或小于）。5 设前序遍历某二叉树的序列为ABCD，中序遍历该二叉树的序列为BADC，则后序遍历该二叉树的序列为_ 。6 设散列函数H(k)=k mod p ，解决冲突的方法为链地址法。要求在下列算法划线处
10、填上正确的语句完成在散列表hashtalbe中查找关键字值等于k 的结点，成功时返回指向关键字的指针，不成功时返回标志0。typedef struct node int key; struct node *next; lklist;void createlkhash(lklist *hashtable )int i,k; lklist *s;for(i=0;im;i+)_;for(i=0;ikey=ai;k=ai % p; s-next=hashtablek;_;三、计算题 ( 每题 10 分，共 30 分 )1、画出广义表LS=( ) , (e) , (a , (b , c , d )的头尾链表存储结构。2、下图所示的森林：(1) 求树（ a）的先根序列和后根序列；(2) 求森林先序序列和中序序列；（ 3）将此森林转换为相应的二叉树；AGBCHDEFIJK(a)(b)3、设散列表的地址范围是 0.9 ，散列函数为 H（ key ） = （ key2 +2） MOD 9,并采用链表处理冲突，请画出元素
