数据结构参考答案

1《数据结构》模拟卷A一、选择题1.在一个长度为n的顺序表的任一位置插入一个新元素的渐进时间复杂度为（A）。A.O(n)B.O(n/2)C.O(1)D.O(n2)2.带头结点的单链表first为空的判定条件是：（B）。A.first==NULL;B.first-link==NULL;C.first-link==first;D.first!=NULL;3.从逻辑上可以把数据结构分为（C）两大类。A．动态结构、静态结构B．顺序结构、链式结构C．线性结构、非线性结构D．初等结构、构造型结构4.在系统实现递归调用时需利用递归工作记录保存实际参数的值。在传值参数情形，需为对应形式参数分配空间，以存放实际参数的副本；在引用参数情形，需保存实际参数的（D），在被调用程序中可直接操纵实际参数。A.空间B.副本C.返回地址D.地址5.以下数据结构中，哪一个是线性结构（D）。A．广义表B.二叉树C.稀疏矩阵D.串6.以下属于逻辑结构的是（C）。A．顺序表B.哈希表C.有序表D.单链表7.对于长度为9的有序顺序表，若采用折半搜索，在等概率情况下搜索成功的平均搜索长度为（C）的值除以9。A.20B.18C.25D.228.在有向图中每个顶点的度等于该顶点的（C）。A.入度B.出度C.入度与出度之和D.入度与出度之差9.在基于排序码比较的排序算法中，（C）算法的最坏情况下的时间复杂度不高于O(nlog2n)。A.起泡排序B.希尔排序C.归并排序D.快速排序10.当α的值较小时，散列存储通常比其他存储方式具有（B）的查找速度。2A.较慢B.较快C.相同D.不同二、填空题1.二维数组是一种非线性结构，其中的每一个数组元素最多有______2___个直接前驱（或直接后继）。2.将一个n阶三对角矩阵A的三条对角线上的元素按行压缩存放于一个一维数组B中，A[0][0]存放于B[0]中。对于任意给定数组元素B[K]，它应是A中第_(K+1)/3_行的元素。3.链表对于数据元素的插入和删除不需移动结点，只需改变相关结点的__指针__域的值。4.在一个链式栈中，若栈顶指针等于NULL则为__空栈_。5.主程序第一次调用递归函数被称为外部调用，递归函数自己调用自己被称为内部调用，它们都需要利用栈保存调用后的__返回_地址。6.在一棵树中，__叶子_结点没有后继结点。7.一棵树的广义表表示为a(b(c,d(e,f),g(h)),i(j,k(x,y)))，结点f的层数为___3___。假定根结点的层数为0。8.在一棵AVL树（高度平衡的二叉搜索树）中，每个结点的左子树高度与右子树高度之差的绝对值不超过_____1___。9.n(n﹥0)个顶点的无向图最多有__n(n-1)/2_条边，最少有___0_____条边。10.在索引存储中，若一个索引项对应数据对象表中的一个表项（记录），则称此索引为_稠密__索引，若对应数据对象表中的若干个表项，则称此索引为_稀疏___索引。三、判断题1.数组是一种复杂的数据结构，数组元素之间的关系既不是线性的也不是树形的(对)2.链式存储在插入和删除时需要保持物理存储空间的顺序分配，不需要保持数据元素之间的逻辑顺序(错)3.在用循环单链表表示的链式队列中，可以不设队头指针，仅在链尾设置队尾指针(对)4.通常递归的算法简单、易懂、容易编写，而且执行的效率也高(错)5.一个广义表的表尾总是一个广义表(对)6.当从一个小根堆（最小堆）中删除一个元素时，需要把堆尾元素填补到堆顶位置，然后再按条件把它逐层向下调整，直到调整到合适位置为止(对)7.对于一棵具有n个结点，其高度为h的二叉树，进行任一种次序遍历的时间复杂度为O(h)(错)38.存储图的邻接矩阵中，邻接矩阵的大小不但与图的顶点个数有关，而且与图的边数也有关(错)9.直接选择排序是一种稳定的排序方法(错)10.闭散列法通常比开散列法时间效率更高(错)四、运算题1.设有一个1010的对称矩阵A，将其下三角部分按行存放在一个一维数组B中，A[0][0]存放于B[0]中，那么A[8][5]存放于B中什么位置。解：根据题意，矩阵A中当元素下标I与J满足I≥J时，任意元素A[I][J]在一维数组B中的存放位置为I*(I+1)/2+J，因此，A[8][5]在数组B中位置为8*(8+1)/2+5=41。2.这是一个统计单链表中结点的值等于给定值x的结点数的算法，其中while循环有错，请重新编写出正确的while循环。intcount(ListNode*Ha,ElemTypex){//Ha为不带头结点的单链表的头指针intn=0;while(Ha-link!=NULL){Ha=Ha-link;if(Ha-data==x)n++;}returnn;}解：while(Ha!=NULL){if(Ha-data==x)n++;Ha=Ha-link;}3.已知一棵二叉树的前序和中序序列，求该二叉树的后序序列。前序序列：A,B,C,D,E,F,G,H,I,J中序序列：C,B,A,E,F,D,I,H,J,G4后序序列：解：后序序列：C,B,F,E,I,J,H,G,D,A4.已知一个有序表(15,26,34,39,45,56,58,63,74,76,83,94)顺序存储于一维数组a[12]中，根据折半搜索过程填写成功搜索下表中所给元素34,56,58,63,94时的比较次数。元素值比较次数解：判断结果元素值比较次数5.设散列表为HT[17],待插入关键码序列为{Jan,Feb,Mar,Apr,May,June,July,Aug,Sep,Oct,Nov,Dec}，散列函数为H(key)=i2，其中，i是关键码第一个字母在字母表中的序号。现采用线性探查法解决冲突。字母ABCDEFGHIJKLM序号12345678910111213字母NOPQRSTUVWXYZ序号14151617181920212223242526(1)试画出相应的散列表；H(Jan)=102=5，成功.H(Feb)=62=3，成功.H(Mar)=132=6，成功.H(Apr)=12=0，成功.H(May)=132=6，=7，成功，H(June)=102=5，=6，=7，=8，成功.H(July)=102=5，=6，=7，=8，=9，成功.H(Aug)=12=0，=1，成功.H(Sep)=192=9，=10，成功.H(Oct)=152=7，=8，=9，=10，=11，成功.H(Nov)=142=7，=8，=9，=10，=11，=12，成功.H(Dec)=42=2，成功.(1)相应的散列表：012345678910111213AprAugDecFebJanMarMayJuneJulySepOctNov(1)(2)(1)(1)(1)(1)(2)(4)(5)(2)(5)(6)345658639434565863940213445(2)计算等概率下搜索成功的平均搜索长度；1/12*(1+2+1+1+1+1+2+4+5+2+5+6)=31/12五、算法设计题已知二叉树中的结点类型用BinTreeNode表示，被定义为:structBTreeNode{chardata;BinTreeNode*leftChild,*rightChild;};其中data为结点值域，leftChild和rightChild分别为指向左、右子女结点的指针域，根据下面函数声明编写出求一棵二叉树中结点总数的算法，该总数值由函数返回。假定参数BT初始指向这棵二叉树的根结点。intBTreeCount(BinTreeNode*BT);解：intBTreeCount(BinTreeNode*BT){if(BT==NULL)return0;//2分elsereturnBTreeCount(BT-leftChild)+BTreeCount(BT-rightChild)+1;//4分}6《数据结构》模拟卷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;A．O(2n)B．O(n)C．O(n2)D．O(log2n)5.下面关于线性表的叙述中，错误的是哪一个（B）。A．线性表采用顺序存储，必须占用一片连续的存储单元。B．线性表采用顺序存储，便于进行插入和删除操作。C．线性表采用链接存储，不必占用一片连续的存储单元。D．线性表采用链接存储，便于插入和删除操作。6．线性表是具有n个（C）的有限序列（n0）。A．表元素B．字符C．数据元素D．数据项E．信息项7.若某线性表最常用的操作是存取任一指定序号的元素和在最后进行插入和删除运算，则利用（A）存储方式最节省时间。A．顺序表B．双链表C．带头结点的双循环链表D．单循环链表8.某线性表中最常用的操作是在最后一个元素之后插入一个元素和删除第一个元素，则采用（D）存储方式最节省运算时间。A．单链表B．仅有头指针的单循环链表C．双链表D．仅有尾指针的单循环链表9.下面给出的四种排序法中(D)排序法是不稳定性排序法。A.插入B.冒泡C.二路归并D.堆积7EFDGAB/++*-C*10.下列排序算法中，其中（D）是稳定的。A.堆排序，冒泡排序B.快速排序，堆排序C.直接选择排序，归并排序D.归并排序，冒泡排序11.已知一算术表达式的中缀形式为A+B*C-D/E，后缀形式为ABC*+DE/-，其前缀形式为(D)。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*/++二、填空题，在横线处填写合适内容1.数据结构的存储结构包括顺序、_链接___、索引和散列等四种。2.在程序运行过程中可以扩充的数组是_动态__分配的数组。这种数组在声明它时需要使用数组指针。3.在链表中进行插入和删除操作的效率比在顺序存储结构中进行相同操作的效率高。4.栈是一种限定在表的一端进行插入和删除的线性表，又被称为_后出先进__表。5.如果一个对象部分地包含自己，或自己定义自己，则称这个对象是__递归___的对象。6.一棵树的广义表表示为a(b(c,d(e,f),g(h)),i(j,k(x,y)))，结点f的层数为___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.每次直接或通过基准元素间接比较两个元素，若出现逆序排列就交换它们的位置，这种排序方法叫做___交换_______排序。811.快速排序在平均情况下的空间复杂度为__O(log2n)___。12.若对长度n=10000的线性表进行二级索引存储，每级索引表中的索引项是下一级20个表项的索引，则一级索引表的长度为___500_____。三、判断题1.在顺序表中进行顺序搜索时，若各元素的搜索概率不等，则各元素应按照搜索概率的降序排列存放，则可得到最小的平均搜索长度（对）2.在二叉搜索树中，若各结点的搜索概率不等，使得搜索概率越小的结点离树根越近，则得到的是最优二叉搜索树（错）3.对于AOE网络，加速任一关键活动都能使整个工程提前完成（错）4.直接选择排序是一种稳定的排序方法（