《数据结构期末试题及答案》由会员分享，可在线阅读，更多相关《数据结构期末试题及答案（8页珍藏版）》请在金锄头文库上搜索。
1、计算机科学与技术、网络工程本科数据构造期末考试试卷一、选择题(单选题,每题3分,共33分）1.已知某二叉树的中序、层序序列分别为BAFCE、FDBC,则该二叉树的后序序列为 。 A.BDAF B.BDEF C.DBACEF D.DEF2在11个元素的有序表111中进行折半查找（),查找元素11时，被比较的元素的下标依次是 。 A6,10，1 B.6，10,11 C.6,7，9,11 D6,8,9，11由元素序列(27,6,75,8，51）构造平衡二叉树，则初次浮现的最小不平衡子树的根(即离插入结点近来且平衡因子的绝对值为的结点）为 。 A7 B. .51 .4运用逐点插入法建立序列（50，7，
2、3，5,5,2，35,4，65,30)相应的二叉排序树后来,查找元素0要进行 次元素间的比较。 A B.5 C.6 D7循环链表的重要长处是 。 不再需要头指针了 B 已知某个结点的位置后,很容易找到它的直接前驱结点C在进行删除后，能保证链表不断开 D从表中任一结点出发都能遍历整个链表6.已知一种线性表(,25,74,6，2,），假定采用散列函数h（ky）=key%7计算散列地址,并散列存储在散列表A06中,若采用线性探测措施解决冲突，则在该散列表上进行等概率查找时查找成功的平均查找长度为 。 .15 B1.7 C.2 D237.由权值为9,2，,7的四个叶子结点构造一棵哈夫曼树，该树的带权途
3、径长度为 。 A2 B.37 4 D.468在最佳和最坏状况下的时间复杂度均为(ngn)且稳定的排序措施是 。 A基数排序 B.迅速排序 C.堆排序 归并排序无向图=(,E),其中=,b,c，d,f,=(a，b)，(，e)，（a，c),(b,e),(c，f)，(f,d),(e,d)。对该图进行深度优先遍历,下面不能得到的序列是 。 A.aebdc B.bdfc aedfcb Dafe10置换-选择排序的功能是 。 产生初始归并段 B.选出最大的元素 C产生有序文献 置换某个记录 11.IAM和SAM文献属于 。A索引顺序文献 B.索引非顺序文献 C.顺序文献 散列文献二、填空题(18每空2分，
4、91每空1分,共20分）1下面程序段的时间复杂度为 【】 。um=； For （i0; sumn; i+) sum+i；2.稀疏矩阵迅速转置算法(见第三题第1小题）的时间复杂度为 【2】 ，空间复杂度为 【3】 。3对广义表A(a，（b,c,d）)的运算hed（rail()的成果是 【】 。4将n个数据元素依次按a1，2，a的顺序压入栈中，共有【5】 种出栈序列。5具有4个结点的不相似的二叉树有 【6】 棵。6设有一种二维数组Amn,假设A0寄存位置在644(10)，22寄存位置在67(10),每个元素占一种空间，则A33（10)寄存的位置为 【】 。(脚注(1)表达用10进制表达)7 若某二
5、叉树有20个叶子结点,有3个结点仅有一种孩子,则该二叉树的总的结点数是 【8】 。8给定一组核心字49，38，6，7，76，3，7，,如下用了4种不同的排序措施分别得到了第一趟排序后的成果，请指出各自相应的排序措施。（每空1分） 第一趟排序后的成果排序措施2，3，4,7，9,5，【9】38，4，65，97,，7,27,49【0】49，76,65,4，3，3,27，【11】1,65，6,97，7，3，9,49【2】三、算法填空题(每空3分,共18分)1. 稀疏矩阵迅速转置算法/稀疏矩阵的三元组顺序表存储表达#define MAXSIZ 50 /非零元个数最大为500typeef truc i，j
6、; /行号，列号 EmType ; /非零元Triple;typede stu Trile dataMAXSIZE+1; /三元组表0号不用 it mu,nu,tu; /总行数,总列数，非零元总个数rix;efine AXCOL50tatus FatTransposeSMtrix(TSaiM,TSMrx &T)/采用三元组表存储表达,求稀疏矩阵M的转置矩阵T int nmMAC, cotCO, cl, t, ,q; TuM.n; T.nu=mu; .t.tu；if （T.t)or (o1； colM.u； +） mcl0; or （t=1; t=M.u; +) +m ； /求M中每一列含非零元
7、个数 cpo11; 求第col列中第一种非零元在T.t中的序号 r(col=2;corcild=) /右子树不存在或已被访问,访问之 ; 访问根结点Pop(S,p); /退栈p=t; /指向已被访问的结点elset=t-rchild; /指向右子树tag=0; /设立未被访问的标记whie( ); eturnOK;四、解答题（共20分）1(分)已知模式串p=cbcaaccb，求出的next数组值和neta数组值。j12341模式串bcaacbcNextetl2.（6分)已知一组核心字为，33,12，40,9,2,5，(1) 试依次插入核心字生成一棵3阶的树；(2) 在生成的3阶-树中依次删除4
8、0和1，画出每一步执行后-树的状态。3(8分）试对右图所示的OE网络,解答下列问题。 (1)求每个事件的最早开始时间Vei和最迟开始时间Vi。1 2 34 5 6 eVl （） 求每个活动的最早开始时间( )和最迟开始时间l( )。1,22, 43, nex; q=-ext; sqext； p-nex=NULL;试题答案及评分原则一、选择题(单选题,每题3分,共33分）12345679111BBDBDCDAA二、填空题(18每空分，912每空1分,共20分）【1】【2】【3】【】【5】【】O（)O(tnu）O()(b，c,）14【7】【8】【9】【10】【11】【12】6926迅速排序二路归并排序堆排序链式基数排序三、算法填空题(每空3分，共18分）1
