数据结构参考答案解析

9》模拟卷A一、选择题1.在一个长度为n的顺序表的任一位置插入一个新元素的渐进时间复杂度为(A)。A.O(n)B.O(n/2)C.O(1)D.O(n2)A.first==NULL;B.first->link==NULL;C.first->link==first;D.first!=NULL;3.从逻辑上可以把数据结构分为(C)两大类。A．动态结构、静态结构B．顺序结构、链式结构C．线性结构、非线性结构D．初等结构、构造型结构为(D)，在被调用程序中可直接操纵实际参数。A.空间B.副本C.返回地址D.地址5.以下数据结构中，哪一个是线性结构(D)。A．广义表B.二叉树C.稀疏矩阵D.串6.以下属于逻辑结构的是(C)。A．顺序表B.哈希表C.有序表D.单链表度为(C)的值除以9。A.20B.18C.25D.228.在有向图中每个顶点的度等于该顶点的(C)。A.入度B.出度C.入度与出度之和D.入度与出度之差9.在基于排序码比较的排序算法中，(C)算法的最坏情况下的时间复杂度不高于O(nlogn)。2A.起泡排序B.希尔排序C.归并排序D.快速排序10.当α的值较小时，散列存储通常比其他存储方式具有(B)的查找速度。A.较慢B.较快C.相同D.不同二、填空题3.链表对于数据元素的插入和删除不需移动结点，只需改变相关结点的__指针__域的值。5.主程序第一次调用递归函数被称为外部调用，递归函数自己调用自己被称为内部调用，它们都需要利用栈保存调用后的__返回_地址。7.一棵树的广义表表示为a(b(c,d(e,f),g(h)),i(j,k(x,y)))，结点f为0。的绝对值不超过_____1___。10.在索引存储中，若一个索引项对应数据对象表中的一个表项(记录)，则称此索引为_稠密__索引，若对应数据对象表中的若干个表项，则称此索引为_稀疏___索引。1.数组是一种复杂的数据结构，数组元素之间的关系既不是线性的也不是树形的(对)2.链式存储在插入和删除时需要保持物理存储空间的顺序分配，不需要保持数据元素之间的逻辑顺序(错)4.通常递归的算法简单、易懂、容易编写，而且执行的效率也高(错)5.一个广义表的表尾总是一个广义表(对)6.当从一个小根堆(最小堆)中删除一个元素时，需要把堆尾元素填补到堆顶位置，然后再按条件把它逐层向下调整，直到调整到合适位置为止(对)O(h)(错)关(错)9.直接选择排序是一种稳定的排序方法(错)10.闭散列法通常比开散列法时间效率更高(错)存放于B[0]中，那么A[8][5]存放于B中什么位置。intcount(ListNode*Ha,ElemTypex)Ha的头指针intn=0;while(Ha->link!=NULL){Ha=Ha->link;if(Ha->data==x)n++;}returnn;}while(Ha!=NULL){}3.已知一棵二叉树的前序和中序序列，求该二叉树的后序序列。9JG4.已知一个有序表(15,26,34,39,45,56,58,63,74,76,83,94)顺序存储于元素值解：判断结果元素值34345658639434565863940213445.设散列表为HT[17],待插入关键码序列为{Jan,Feb,Mar,Apr,May,June,July,个字母在字母表中的序号。现采用线性探查法解决冲突。字母字母ABCDEFGHIJKLM序号12345678910111213字母NOPQRSTUVWXYZ序号14151617181920212223242526012345678910111213Apr(2)(4)(5)(2)(5)(6)五、算法设计题structBTreeNode{chardata;BinTreeNode*leftChild,*rightChild;};其中datad数声明编写出求一棵二叉树中结点总数的算法，该总数值由函数返回。假定参数BT初始指棵二叉树的根结点。intBTreeCount(BinTreeNode*BT);if(BT==NULL)return0;//2分4分}9《数据结构》模拟卷B一、单项选择题1．以下与数据的存储结构无关的术语是(C)。A．循环队列B.链表C.哈希表D.栈2．以下数据结构中，哪一个是线性结构(D)。A．广义表B.二叉树C.稀疏矩阵D.串3．以下那一个术语与数据的存储结构无关？(B)。A．栈B.哈希表C.线索树D.双向链表4．在下面的程序段中，对x的赋值语句的频度为(C)。FORi:=1TOnDOFORj:=1TOnDOx:=x+1;25.下面关于线性表的叙述中，错误的是哪一个(B)。A．线性表采用顺序存储，必须占用一片连续的存储单元。B．线性表采用顺序存储，便于进行插入和删除操作。C．线性表采用链接存储，不必占用一片连续的存储单元。D．线性表采用链接存储，便于插入和删除操作。6．线性表是具有n个(C)的有限序列(n>0)。A．表元素B．字符C．数据元素D．数据项E．信息项用(A)存储方式最节省时间。A．顺序表B．双链表C．带头结点的双循环链表D．单循环链表(D)存储方式最节省运算时间。A．单链表B．仅有头指针的单循环链表C．双链表D．仅有尾指针的单循环链表9.下面给出的四种排序法中(D)排序法是不稳定性排序法。A.插入B.冒泡C.二路归并D.堆积10.下列排序算法中，其中(D)是稳定的。A.堆排序，冒泡排序B.快速排序，堆排序C.直接选择排序，归并排序D.归并排序，冒泡排序11.已知一算术表达式的中缀形式为A+B*C-D/E，后缀形式为ABC*+DE/-，其前缀形式为A．-A+B*C/DEB.-A+B*CD/EC．-+*ABC/DED.-+A*BC/DE12.算术表达式a+b*(c+d/e)转为后缀表达式后为(B)。A．ab+cde/*B．abcde/+*+C．abcde/*++D．abcde*/++//+C*-DEFG*A+B二、填空题，在横线处填写合适内容2.在程序运行过程中可以扩充的数组是_动态__分配的数组。这种数组在声明它时需要使用3.在链表中进行插入和删除操作的效率比在顺序存储结构中进行相同操作的效率高。4.栈是一种限定在表的一端进行插入和删除的线性表，又被称为_后出先进__表。。___3______。假定树根结点的层数为0。7.一棵树按照左子女-右兄弟表示法转换成对应的二叉树，则该二叉树中树根结点肯定没有____右____子女。8.向一棵二叉搜索树中插入一个元素时，若元素的值小于根结点的值，则应把它插入到根结点的_左子树_上。9.设图G=(V,E)，V={1,2,3,4},E={<1,2>,<1,3>,<2,4>,<3,4>}，从顶点1出发，对图G进行广度优先搜索的序列有___2_____种。10.每次直接或通过基准元素间接比较两个元素，若出现逆序排列就交换它们的位置，这种排序方法叫做___交换_______排序。n2表项的索引，则一级索引表的长度为___500_____。三、判断题排列存放，则可得到最小的平均搜索长度(对)2.在二叉搜索树中，若各结点的搜索概率不等，使得搜索概率越小的结点离树根越近，则得到的是最优二叉搜索树(错)3.对于AOE网络，加速任一关键活动都能使整个工程提前完成(错)4.直接选择排序是一种稳定的排序方法(错)5.闭散列法通常比开散列法时间效率更高(错)6.数据的逻辑结构是指各数据元素之间的逻辑关系，是用户根据应用需要建立的(对)7.顺序表和一维数组一样，都可以按下标随机(或直接)访问(对)8.在一个顺序存储的循环队列中,队头指针指向队头元素的后一个位置(错)9.用非递归方法实现递归算法时一定要使用递归工作栈(错)10.在一棵二叉树中，假定每个结点只有左子女，没有右子女，对它分别进行中序遍历和后序遍历，则具有相同的结果(对)LOC(i,j)=LOC(0,0)+(i*n+j)*dLOCd=1,二维数组的列数n=20，据题意，元素A[6][2]的存储地址为LOC(6,2)=200+(6*20+2)*1=3222.已知一棵二叉树的中序和后序序列如下，求该二叉树的高度(假定空树的高度为-1)和中序序列：c,b,d,e,a,g,i,h,j,f3.假定一组记录为(36,75,83,54,12,67,60,40)，将按次序把每个结点插入到初始为空的一V={0,1,2,3,4,5,6};E={(0,1)19,(0,2)10,(0,3)14,(1,2)6,(1,5)5,(2,3)26,(2,4)15,(3,4)18,6)6,(5,6)12};345610142521315.已知一个数据表为{36,25,25*,62,40,53}，请写出在进行快速排序的过程中每次划分后*62)[25*25]36[62)25*2536[5340五、算法设计题4053]4053]40]6253621．设有一个表头为first的单链表。试设计一个算法，通过遍历一趟链表，将链表中所有if(first==NULL)return;LLWhile(p!=NULL){}first->link=pr;}While(first!=NULL){}}《数据结构》模拟卷C一、单项选择题1．数据结构是(D)。A．一种数据类型B．数据的存储结构C．一组性质相同的数据元素的集合D．相互之间存在一种或多种特定关系的数据元素的集合2．算法分析的目的是(B)。A．辨别数据结构的合理性B．评价算法的效率C．研究算法中输入与输出的关系D．鉴别算法的可读性．改变数据元素之间结构关系的运算是(．改变数据元素之间结构关系的运算是(D)。A．插入B．删除C．排序D．定位4．若进栈序列为1，2，3，4，5，6，且进栈和出栈可以穿插进行，则可能出现的出栈序列为(B)。5．设串sl=″DataStructureswithJava″,s2=″it″，则子串定位函数index(s1,s2)的值为(D)。A．15B．16C．17D．18AA的存储地址为1153，则数组元素A[6][7]的存储地址为(A)。A．1207B．1209C．1211D．12137．在按层次遍历二叉树的算法中，需要借助的辅助数据结构是(A)。9A．队列B．栈C．线性表D．有序表8．在任意一棵二叉树的前序序列和后序序列中，各叶子之间的相对次序关系(B)。A．不一定相同B．都相同C．都不相同D．互为逆序9．若采用孩子兄弟链表作为树的存储结构，则树的后序遍历应采用二叉树的(C)。A．层次遍历算法B．前序遍历算法C．中序遍历算法D．后序遍历算法10．若用邻接矩阵表示一个有向图，则其中每一列包含的″1″的个数为(A)。A．图中每个顶点的入度C．图中弧的条数B．图中每个顶点的出度D目11．图的邻接矩阵表示法适用于表示(C)。A．无向图B．有向图C．稠密图D．稀疏图则在进行第i趟排序之前，无序区中关键字元素的个数为(D)。A．iB．i+1C．n-iD．n-i+1二、填空题1．栈是__特殊_____的线性表，其运算遵循__后进先出_____的原则。2．___栈__是限定仅在表尾进行插入或删除操作的线性表。3.一个栈的输入序列是：1，2，3则不可能的栈输出序列是_3，1，2______。__。有__12_个叶子结点。8．若不考虑基数排序，则在排序过程中，主要进行的两种基本操作是关键字的_比较_____和记录的_移动____。9_冒泡排序____算法