数据结构b

装订线装订线装订线装订线注：装订线内禁止答题，装订线外禁止有姓名和其他标记。第1页共2页姓名:专业:年级层次:学号:东北农业大学网络教育学院2012秋在职高升专第3学期期末考试题签23207016数据结构(B卷)一、填空题(每题2分，共10题)1.一个算法的时间复杂度为(3n2+2nlog2n+4n-7)/(5n)，其数量级表示为（）。2.在单链表p结点之后插入s结点的操作是：（）。3.设有一个空栈，栈顶指针为1000H(十六进制)，现有输入序列为1，2，3，4，5，经过PUSH,PUSH,POP,PUSH,POP,PUSH,PUSH之后，输出序列是（），而栈顶指针值是（）H。设栈为顺序栈，每个元素占4个字节。4.设S=’Iamateacher’，则其长度为（）。5.10行20列矩阵若用行优先顺序表来表示，则矩阵中第8行第7列元素是顺序表中的第（）个元素。6.高度为8的完全二叉树至少有（）个叶子结点。7.高度为h的完全二叉树中至少有（）个结点，至多有（）个结点。8.右图中的强连通分量的个数为（）个9.将有序表（k1，k2，…，k99）中的关键字依次插人到一棵原来为空的二叉排序树中，这棵二叉排序树的高度是（）。10.为长度为5的顺序表建初始堆，元素的移动次数至多是（）次。二、单项选择题(每题2分，共10题)1.以下属于逻辑结构的是（）。A、顺序表B.哈希表C、有序表D、单链表2.已知指针p和q分别指向某单链表中第一个结点和最后一个结点。假设指针s指向另一个单链表中某个结点，则在s所指结点之后插入上述链表应执行的语句为（）。A、q-next=s-next；s-next=p；B、s-next=p；q-next=s-next；C、p-next=s-next；s-next=q；D、s-next=q；p-next=s-next；3.设n个元素的进栈序列是1，2，3，…，n，出栈序列是p1，p2，…，pn。若p1=n，则pi（l≦i＜n）的值（）。A、是iB、是n-iC、是n-i+1D、有多种可能4.设有两个串p和q，其中q是p的子串，求q在p中首次出现的位置的算法称为（）。A、求子串B、联接C、匹配D、求串长5.二维数组A的每个元素是由6个字符组成的串，其行下标i=0,1,…,8,列下标j=1,2,…,10。若A按行先存储，元素A[8,5]的起始地址与当A按列先存储时的元素（）的起始地址相同。设每个字符占一个字节。A、A[8,5]B、A[3,10]C、A[5,8]D、A[0,9]6.若某棵二叉树结点的后序序列和层次序序列正好相反，则该二叉树（）。A、每个结点都没有右孩子B、不存在度为2的结点C、每个结点都没有左孩子D、不存在7.要连通具有n个顶点的有向图，至少需要（）条边。A、n-lB、nC、n+lD、2n8.下面哪一方法可以判断出一个有向图是否有环（回路）：（）。A、深度优先遍历B、拓扑排序C、求最短路径D、求关键路径9.若查找每个记录的概率均等，则在具有n个记录的连续顺序文件中采用顺序查找法查找一个记录，其平均查找长度ASL为（）。装订线装订线装订线装订线注：装订线内禁止答题，装订线外禁止有姓名和其他标记。第2页共2页姓名:专业:年级层次:学号:A、(n-1)/2B、n/2C、(n+1)/2D、n10.假设排序过程中线性表的变化情况如下：21，25，49，25，16，8（初始状态）21，25，49，25，16，821，25，49，25，16，821，25，25，49，16，816，21，25，25，49，88，16，21，25，25，49（最终状态）可以断定，所采用的排序方法是（）排序。A、归并B、起泡C、简单选择D、直接插入三、判断题(每题1分，共10题)1.数据元素是数据的最小单位。()2.集合与线性表的区别在于是否按关键字排序。()3.若用s[1]~s[m]表示顺序栈的存储空间，则对栈的插人、删除操作最多只推进行m次。（）4.KMP算法的特点是在模式匹配时指示主串的指针不会变小（）。5.设模式串的长度为m,目标串的长度为n，当n≈m且处理只匹配一次的模式时，朴素的匹配（即子串定位函数）算法所花的时间代价可能会更为节省（）。6.在按行优先顺序存储的三元组线性表中，各元素的排列顺序只与每个元素的行下标有关，与每个元素的列下标无关。（）7.在树形结构中，处于同一层上的各结点之间都存在兄弟关系。（）8.当改变网上某一关键路径上任一关键活动后，必将产生不同的关键路径。（）9.在平衡二叉排序树中，每个结点的平衡因子值是相等的。（）10.对n个元素执行简单选择排序，排序码的比较次数总是n(n-1)/2次。（）四、应用题(每题10分，共2题)1.设双向循环链表中结点的数据域、前驱和后继指针域分别为data,pre和next,试写出在指针p所指结点之前插入一s结点的C语言描述语句。2.三维数组A[1..10，-2..6，2..8]的每个元素的长度为4个字节，试问该数组要占多少个字节的存储空间？如果数组元素以行优先的顺序存贮，设第一个元素的首地址是100，试求元素A[5,0,7]的存贮首地址。五、综合题(每题15分，共2题)1.设从键盘输入一整数的序列：a1,a2,a3，…，an,试编写算法实现：用栈结构存储输入的整数，当ai≠-1时，将ai进栈；当ai=-1时，输出栈顶整数并出栈。算法应对异常情况（入栈满等）给出相应的信息。2.借助于快速排序的算法思想，在一组无序的记录中查找给定关键字值等于key的记录。设此组记录存放于数组r[l..h]中。若查找成功，则输出该记录在r数组中的位置及其值，否则显示“notfind”信息。请编写出算法并简要说明算法思想。