数据结构测试题1.doc

数据结构测试题 一（期末试卷题型：选择题10个，共20分；填空10个，共10分；应用题6个，共60分；算法题1个，共10分。）一、单项选择题(本大题共10小题，每小题2分，共20分)1.如果在数据结构中每个数据元素只可能有一个直接前驱，但可以有多个直接后继，则该结构是（ ）。A. 栈B. 队列C. 树D. 图2.下面程序段的时间复杂度为（ ）。for (i=0; in; i+)for (j=0; jnext= =headB. p-next-next= =headC. p-next= =NULLD. p= =head4.若以S和X分别表示进栈和退栈操作，则对初始状态为空的栈可以进行的栈操作系列是（ ）。A. SXSSXXXXB. SXXSXSSXC. SXSXXSSXD. SSSXXSXX5.假设以数组Am存放循环队列的元素。已知队列的长度为length，指针rear指向队尾元素的下一个存储位置，则队头元素所在的存储位置为( )。A.(rear-length+m+1)mB.(rear-length+m)mC.(rear-length+m-1)mD.(rear-length)m6.两个字符串相等的条件是（ ）。A. 串的长度相等B. 含有相同的字符集C. 都是非空串D. 串的长度相等且对应的字符相同7.已知一棵含50个结点的二叉树中度为1的结点个数为（ ）。A. 0B. 1C. 48D. 498.已知一棵完全二叉树有64个叶子结点，则该树可能达到的最大深度是（）。A7B8C9D109.如图所示的有向无环图可以得到的拓扑序列的个数是（ ）。 A. 3B. 4C. 5D. 610.二维数组A89按行优先顺序存储，若数组元素A23的存储地址为1087，A47的存储地址为1153，则数组元素A67的存储地址为（ ）。A1207B1209C1211D1213二、填空题(每空2分，共10分)11. 在一个长度为n的单链表L中，删除链表中*p的前驱结点的时间复杂度为_ _。12.已知循环队列的存储空间大小为m，队头指针front指向队头元素，队尾指针rear指向队尾元素的下一个位置，则队空的条件是 _ _，队满的条件是_ _。13.在字符串“sgabacbadfgbac” 中匹配t串“bad”，匹配成功次数是_ _次。14.一棵含999个结点的完全二叉树的深度为_ _。15.在一个长度为100的顺序表中删除第10个元素时，需移动_ _个元素。三、应用题(共60分)1.已知二叉树的先序序列和中序序列分别为ABDEHCFI和DBHEACIF，(1) 画出该二叉树;(2) 写出该二叉树的后序序列。( 10). 后序遍历：D H E B I F C A2.画出与如图所示森林对应的二叉树。( 10) 3. 假设通信电文使用的字符集为a,b,c,d,e,f,g，这些字符在电文中出现的频度分别为：3，35，13，15，20，5和9，求该哈夫曼树及哈夫曼编码。(15)4. 已知带权图G如图所示，写出使用普里姆算法从顶点A开始构造图G最小生成树的过程。( 15) 5. (1)画出对表长为13的有序顺序表进行二分查找的判定树；(2)已知关键字序列为（12，14，16，21，24，28，35，43，52，67，71，84，99），写出在该序列中二分查