绵阳数据结构

一、单项选择题（本大题共20小题，每小题1分，共20分）请将正确选项前的字母填在题后的括号内。1.在顺序存储的线性表(a1,a2,...,an)中,删除任意一个结点时所需移动结点的平均次数为（）。A、nB、n/2C、(n-1)/2D、(n+1)/22.下列算法suanfa2的时间复杂度为____。intsuanfa2(intn){intt=1；while(t=n)t=t*2；returnt；}A.O(log2n)B.O(n)C.O(n2)D.O(2n)3.____又称为FIFO表。A.队列B.栈C.散列表D.哈希表4.若6行8列的数组以列序为主序顺序存储,基地址为1000,每个元素占2个存储单元,则第5行第3列的元素(假定无第0行第0列)的地址是____。A.1086B.1068C.1032D.答案A,B,C都不对5.广义表(a,((b,()),c),(d,(e)))的深度是____。A.2B.3C.4D.56.若待排序列已基本有序，要使它们完全有序，从关键码比较次数和移动次数考虑，应当使用的排序方法是（）。A、归并排序B、快速排序C、直接选择排序D、直接插入排序7.与中缀表达式a+b*c-d等价的前缀表达式是____。A.+a-*bcdB.*+-abcdC.-+a*bcdD.abcd+*-8.折半查找有序表(6,15,30,37,65,68,70,72,89,99),若查找元素37,需依次与表中元素____进行比较,。A.65,15,37B.68,30,37C.65,15,30D.65,15,30,379.对长度为10的表作选择(简单选择)排序,共需比较____次关键字。A.45B.55C.90D.11010.对n个元素的表作快速排序,在最坏情况下,算法的时间复杂度为____。A.O(log2n)B.O(nlog2n)C.O(n2)D.O(2n)11.一组记录的关键字经一趟二路归并排序后得到含有5个长度为2的有序表如下：[25，48]，[16，35]，[79，82]，[23，40]，[36，72]，在此基础上按二路归并排序方法再对该序列进行一趟归并后的结果为（）。A、16，25，35，48，79，82，23，36，40，72B、16，25，35，48，23，40，79，82，36，72C、16，25，48，35，79，82，23，36，40，72D、16，25，35，48，79，23，36，40，72，8212.将线性表的数据元素以____结构存放,查找一个数据元素所需的时间不依赖于表的长度。A.循环双链表B单链表C.哈希(Hash)表C.一维数组13.设依次进入一个栈的元素序列为c,a,b,d,不可得到出栈的元素序列有____。A.a.b,c,dB.a,d,b,cC.b,a,d,cD.c,d,a,b14.___又是一棵满二叉树。A.深度为5有31个结点的二叉树B.有15个结点的完全二叉树C.哈夫曼(Huffman)树D.二叉排序树15.查找哈希(Hash)表,解决冲突的的方法有__B__。A.除留余数法B.线性探测再散列法C.直接地址法D.链地址法16.算法指的是（c）A．计算机程序B．解决问题的计算方法C．解决问题的有限运算序列D．排序算法17.由__D__组成的集合是一个数据对象。A.不同类型的数据项B.不同类型的数据元素C.相同类型的数据项D.相同类型的数据元素18、在一个单链表HL中，若要向q所指结点之后插入一个由指针p指向的结点，则执行（D）A、HL=p;p-next=HLB、p-next=HL;HL=pC、P-next=q-next;q-next=pD、p-next=q-next;q=pnext19、由权值分别为3，8，10，2，6的叶子结点生成一棵哈夫曼树，该树中双分支结点数为A、2B、3C、4D、520．设sub(s,i,j)的功能是返回串s从第i个字符开始长度为j的子串，scopy(s,t)的功能是复制串t到s，若字符串s=`SCIENCESTUDY’，则调用scopy(p,sub(s,1,7))后得到(A)A、p=`SCIENCE’B、p=`STUDY’C、s=`SCIENCE’D、s=`STUDY17.下图是一个AOV网，（B）是它的拓扑序列。A.ABCDEB.ACDBEC.ADBCED.CADBE18.对一个算法的评价，不包括如下（D）方面的内容。A.可读性B.正确性C.时间复杂度D.并行性19.递归算法必须使用（A）。A.线性表B.图C.栈D.队列ABACAADE20.当稀疏矩阵采用十字链表的链式存储时，它的包括元素的行号、列号、元素本身的信息和（D）的指针域。A.指向同一行中下一个有效节点的指针B.指向同一列中下一个有效节点的指针C.分别指向所在行和列的的下一个有效节点的指针D.指向头节点的指针二、填空题（本大题共10小题，每小题2分，共12分）不写解答过程，将正确的答案写在每小题的空格内。1.在串S=“structure”中，以t为首字符的子串有2个。2.查找表分为静态查找表和动态查找表两种，二叉排序树属于动态树表。3..第i趟在n-i+l(i=1，2，…，n-l)个记录中选取键值最小的记录作为有序序列的第i个记录。这样的排序方法称为选择排序。4.对某非空二叉树进行前序、中序遍历时，所得的结果完全相同（即结点序列一致），则这棵二叉树必定是完全二叉树5.一个数据结构在计算机中的表示(映象)称为数据的物理结构6..线性表中__元素的个数称为表的长度。7.从二叉排序树种查找一个元素的时间复杂度是O（log2N）_。8.如果一个数据结构的元素个数为n，n=0，则该数据结构不可能是_空表____。9.一个二叉树可以还原为一棵树的条件是该二叉树__中序上将左右子树分开。10.有一个5维矩阵的元素k，则k最多有_____24______个后继。1.当线性表经常需要查找表中的数据时，应该采用__顺序_________存储结构。2.一个栈的输入顺序为123，则栈的可能输出序列有_____321_________________。3.队列的插入是在____队尾部__，在__队头__删除，因此队列又称为_先进后出____。4.一棵二叉树有30个节点，其中叶节点有10个，则度为2的节点有_____9______个，度为1的节点有_____6______个。5.一棵二叉树有n个节点，则有_____ｎ＋1______指针域被浪费了，所以我们通常用这些没有使用的指针域指向该节点的前驱或者后继，称之为____线索二叉_______树。6.如果串采用动态的顺序存储，我们称为___堆存储________。在循环队列中，为了正确判定队满和队空，常常留一个空间不存储数据，则队满的条件是____（Q.rear+1）%MAXQSIZE=Q.front_______，队空的条件是___Q.front=Q.rear________。7.在线性表的散列存储中，处理冲突的常用方法有_____线性探测再散列、二次探测再散列______和___________两种。8.有一个8阶上三角矩阵（行列序号从0开始编号），采用行优先顺序存储为一个顺序表，如果第一个元素的起始地址为L(0)，每个元素需要4个字节，则任意数组元素a[i,j]的存储开始地址是___________。11.对某非空二叉树进行前序、中序遍历时，所得的结果完全相同（即结点序列一致），则这棵二叉树必定是____完全二叉树________12.一个数据结构在计算机中的表示(映象)称为____数据的物理结构____________。队列是一种先进先出的数据结构，具有出队和入队两种基本操作，如果采用顺序存储，循环队列的出队操作是__p-front=(p-front+1)%MAXLEN13._______（队头：front，队列的最大元素个数为m）。14.和队列相反，栈是一种具有___先进后出________特点的数据结构。15.已知单链表每个节点的结构为：structnode{intdata;node*next;}，想在p节点后插入e元素的操作为：structnodeq;q=(structnode*)malloc(sizeof(structnode));q-data=e;q-next=___q-data________;p-next=____q-next_______;16.堆存储是指_____动态分配的空间都在堆上_______________________________________。17.广义表的表头可以是广义表或者独立元素，表尾则一定是第一个元素去掉剩余的部分____。18.排序是指排序是计算机内经常进行的一种操作，其目的是将一组“无序”的记录序列调整为“有序”的记录序列。分内部排序和外部排序。抽象数据类型定义包括三部分：数据对象、数据关系和基本操作19.字符串是指_由数字、字母、下划线组成的一串字符，模式匹配是指________数据结构中字符串的一种基本运算，给定一个子串，要求在某个字符串中找出与该子串相同的所有子串_________________________。1.广义表A=((a)，((),()))的表尾是__(a)，((),())___，深度是_3______________。2.有一个顺序表，数据元素的定义为：structdata{charname[10];intnum;}data;如果第一个元素的起始地址为L(0)，每个元素需要____________个字节的存储空间，则任意第i个元素的存储首地址是___________。3.数据的物理存储结构主要包括顺序和_链式存储__两种情况。4.设查找表中有100个元素，如果用二分法查找方法查找数据元素X，则最多需要比较____7____次就可以断定数据元素X是否在查找表中。已知P节点是某双向量表的中间节点，在P节点后插入S节点的语句序列是：______________s-next=p-next;p-next=s;5._________________三、判断下列叙述是否正确(本大题共5小题，每小题1分，共5分)1．字符串的长度是指串中不同字符的个数。对2．存在这样的二叉树，对它采用任何次序遍历结果都相同。对3．在堆排序中，一个堆的堆根元素一定是一个最小数或最大数对4．完全二叉树中，若某个结点没有左孩子，则该结点一定是叶子结点。对5．线性表的逻辑顺序与存储顺序总是一致的。错四、试画出下列存储结构图(每小题5分,共15分)1.数组A[1..2,0..2]的以列序为主序的顺序存储结构。2.依次将元素A,C,D,B插入一个初始状态为空的链式栈中,试画出所有插入完成之后的链式栈。3.二叉树的顺序存储结构:1.广义表L=（a,b,(c)）的链式存储。3、如下稀疏矩阵的三元组存储结构。1.画出数组A[0..2,0..2]的以列序为主序的顺序存储结构图，起始地址为loc，每个元素占有4个字节。2.依次将元素A,C,D,B插入一个初始状态为空的链式栈中,试画出所有插入完成之后的链式栈，指明栈顶和栈底。4.已知图G中的边为a,b,a,f,c,d,e,a,b,c，画出该图五、解答题(每小题6分,共24分)1.设电文中出现字字母A、B、C、D、E、F、G、H每个字母在电文中出现的次数分别是5，25，4，7，9，12，30，8，请画出哈夫曼树，求A,B,C,D的哈夫曼编码及哈夫曼树的WPL。2.试按表(10,8,9,12,20,5,6,15,19,25)中元素的排列次序,将所有元素插入一棵初始为空的二叉排序树中,使之仍是一棵二叉排序树。(1)试画出插入完成之后的二叉排序树；(2)假设每个元素的查找概率相等,试计算该树的平均查找长度ASL。3.1(3)对该树进行中序遍历,试写出中序遍历序列。中：5,6,8,9,10,12,15,19,20,253.试将森林F={T1,T2,T3,T4}转换为一棵二叉树。T1T2T3T44.已知一棵二叉树的前序遍历序列和中序遍历序列分别是：I