数据结构参考答案.doc

_数据结构模拟卷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. 20 B. 18 C. 25 D. 228. 在有向图中每个顶点的度等于该顶点的（ C ）。A. 入度 B. 出度C. 入度与出度之和D. 入度与出度之差9. 在基于排序码比较的排序算法中，（ C ）算法的最坏情况下的时间复杂度不高于O(nlog2n)。A. 起泡排序B. 希尔排序C. 归并排序D. 快速排序10. 当的值较小时，散列存储通常比其他存储方式具有（ B ）的查找速度。A. 较慢B. 较快C. 相同 D.不同二、填空题1. 二维数组是一种非线性结构，其中的每一个数组元素最多有_2_个直接前驱（或直接后继）。2. 将一个n阶三对角矩阵A的三条对角线上的元素按行压缩存放于一个一维数组B中，A00存放于B0中。对于任意给定数组元素BK，它应是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 (n0) 个顶点的无向图最多有_ n(n-1)/2_条边，最少有_0_条边。10. 在索引存储中，若一个索引项对应数据对象表中的一个表项（记录），则称此索引为_稠密_索引，若对应数据对象表中的若干个表项，则称此索引为_稀疏_索引。三、判断题1. 数组是一种复杂的数据结构，数组元素之间的关系既不是线性的也不是树形的(对)2. 链式存储在插入和删除时需要保持物理存储空间的顺序分配，不需要保持数据元素之间的逻辑顺序(错)3. 在用循环单链表表示的链式队列中，可以不设队头指针，仅在链尾设置队尾指针(对)4. 通常递归的算法简单、易懂、容易编写，而且执行的效率也高(错)5. 一个广义表的表尾总是一个广义表(对)6. 当从一个小根堆（最小堆）中删除一个元素时，需要把堆尾元素填补到堆顶位置，然后再按条件把它逐层向下调整，直到调整到合适位置为止(对)7. 对于一棵具有n个结点，其高度为h的二叉树，进行任一种次序遍历的时间复杂度为O(h)( 错)8. 存储图的邻接矩阵中，邻接矩阵的大小不但与图的顶点个数有关，而且与图的边数也有关(错)9. 直接选择排序是一种稳定的排序方法(错)10. 闭散列法通常比开散列法时间效率更高(错)四、运算题1. 设有一个1010的对称矩阵A，将其下三角部分按行存放在一个一维数组B中，A00存放于B0中，那么A85存放于B中什么位置。解：根据题意，矩阵A中当元素下标I与J满足IJ时，任意元素AIJ在一维数组B中的存放位置为I * (I + 1) / 2 + J，因此，A85在数组B中位置为8 * (8 + 1) / 2 + 5 = 41。2. 这是一个统计单链表中结点的值等于给定值x的结点数的算法，其中while循环有错，请重新编写出正确的while循环。int count ( ListNode * Ha, ElemType x ) / Ha为不带头结点的单链表的头指针int n = 0;while ( Ha-link != NULL ) Ha = Ha-link; if ( Ha-data = x ) n+;return n;解：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, G后序序列：解：后序序列：C, B, F, E, I, J, H, G, D, A4. 已知一个有序表 ( 15, 26, 34, 39, 45, 56, 58, 63, 74, 76, 83, 94 ) 顺序存储于一维数组a12中，根据折半搜索过程填写成功搜索下表中所给元素34, 56, 58, 63, 94时的比较次数。34 56 58 63 94 元素值 比较次数34 56 58 63 9402 1 3 4 4解：判断结果元素值 比较次数 5. 设散列表为HT17, 待插入关键码序列为 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)(2) 计算等概率下搜索成功的平均搜索长度；1/12 * (1 + 2 + 1 + 1 + 1 + 1 + 2 + 4 + 5 + 2 + 5 + 6) = 31 / 12五、算法设计题已知二叉树中的结点类型用BinTreeNode表示，被定义为:struct BTreeNode char data;BinTreeNode *leftChild, *rightChild; ;其中data为结点值域，leftChild和rightChild分别为指向左、右子女结点的指针域，根据下面函数声明编写出求一棵二叉树中结点总数的算法，该总数值由函数返回。假定参数BT初始指向这棵二叉树的根结点。 int BTreeCount ( BinTreeNode* BT );解：int BTreeCount ( BinTreeNode* BT ) if ( BT = NULL ) return 0; /2分else return BTreeCount ( BT-leftChild ) + BTreeCount ( BT-rightChild ) + 1; /4分数据结构模拟卷 B一、单项选择题1以下与数据的存储结构无关的术语是（ C ）。A循环队列 B. 链表 C. 哈希表 D. 栈2以下数据结构中，哪一个是线性结构（ D ）。A广义表 B. 二叉树 C. 稀疏矩阵 D. 串3以下那一个术语与数据的存储结构无关？（ B ）。A栈 B. 哈希表 C. 线索树 D. 双向链表4在下面的程序段中，对x的赋值语句的频度为（ C ）。FOR i:=1 TO n DO FOR j:=1 TO n DO x:=x+1;A O(2n) BO(n) CO(n2) DO(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. 堆积10. 下列排序算法中，其中（ D ）是稳定的。 A. 堆排序，冒泡排序 B. 快速排序，堆排序 C. 直接选择排序，归并排序 D. 归并排序，冒泡排序11.已知一算术表达式的中缀形式为 A+B*C-D/E，后缀形式为ABC*+DE/-，其前缀形式为( D )。A-A+B*C/DE B. -A+B*CD/E C-+*ABC/DE D. -+A*BC/DE12.算术表达式a+b*（c+d/e）转为后缀表达式后为（ B ）。Aab+cde/* Babcde/+*+ Cabcde/*+ Dabcde*/+EFDGAB/+*-C*二、填空题，在横线处填写合适内容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出发，对图G进行广度优先搜索的序列有_2_种。10. 每次直接或通过基准元素间接比较两个元素，若出现逆序排列就交换它们的位置，这种排序方法叫做_交换_排序。11. 快速排序在平均情况下的空间复杂度为_ O(log2n) _。12. 若对长度n=10000的线性表进行二级索引存储，每级索引表中的索引项是下一级20个表项的索引，则一级索引表的长度为_500_。三、判断题1.在顺序表中进行顺序搜索时，若各元素的搜索概率不等，则各元素应按照搜索概率的降序排列存放，则可得到最小的平均搜索长度（ 对 ）2. 在二叉搜索树中，若各结点的搜索概率不等，使得搜索概率越小的结点离树根越近，则得到的是最优二叉搜索树（错 ）3. 对于AOE网络，加速任一关键活动都能使整个工程提前完成（ 错 ）4. 直接选择排序是一种稳定的排序方法（错 ）5. 闭散列法通常比开散列法时间效率更高（ 错 ）6.数据的逻辑结构是指各数据元素之间的逻辑关系，是用户根据应用需要建立的（对 ）7.顺序表和一维数组一样，都可以按下标随机（或直接）访问（对 ）8.在一个顺序存储的循环队列中, 队头指针指向队头元素的后一个位置（ 错 ）9.用非递归方法实现递归算法时一定要使用递归工作栈（ 错 ）10.在一棵二叉树中，假定每个结点只有左子女，没有右子女，对它分别进行中序遍历和后序遍历，则具有相同的结果（ 对 ）四、运算题1. 设有一个二维数组A1020，按行存放于一个连续的存储空间中，A00的存储地址是200，每个数组元素占1个存储字，则A62的存储字地址是多少。 A62的存储字地址：322答案说明： 按行存储时，计算Aij地址的公式为 LOC(i,j)=LOC(0,0)+(i*n+j)*d 其中首地址LOC(0,0)=200, 每个数组元素的存储占用数d=1, 二维数组的列数n=20，根据题意，元素A62的存储地址为 LOC(6,2)=200+(6*20+2)*1=3222. 已知一棵二叉树的中序和后序序列如下，求该二叉树的高度（假定空树的高度为-1）和度为2、度为1及度为0的结点个数。 中序序列：c,b,d,e,a,g,i,h,j,f 后序序列：c,e,d,b,i,j,h,g,f,a求解一下问题：高度： 4 度为2的结点数：3度为1的结点数： 3 度为0的结点数：43. 假定一组记录为(36,75,83,54,12,67,60,40)，将按次序把每个结点插入到初始为空的一棵AVL树中，请回答在插入时需进行“左单旋转”、“右单旋转”、“先左后右双旋转”、“先右后左双旋转”，“不调整”的结点数各是多少？左单旋转结点个数： 1 右单旋转结点个数：0先左后右双旋转结点个数： 1 先右后左双旋转结点个数：0 不调整结点个数：64. 已知一个带权图的顶点集V和边集G分别为： 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, (4,5)6,(4,6)6,(5,6)12; 试根据迪克斯特拉(Dijkstra)算法求出从顶点0到其余各顶点的最短路径，在下面填写对应的路径长度。 顶点： 0 1 2 3 4 5 6 0161014252131 路径长度： 5. 已知一个数据表为36,25,25*,62,40,53，请写出在进行快速排序的过程中每次划分后数据表的变化。(0) 36 25 25* 62 40 53(1) 25* 25 36 62 40 53 (2) 25* 25 36 53 40 62 (3) 25* 25 36 40 53 62 五、算法设计题1设有一个表头为first的单链表。试设计一个算法，通过遍历一趟链表，将链表中所有结点按逆序链接。解答1 template void List : : Tnerse() if (first= NULL )return ;ListNode * p=firstlink ; , *pr =NULL ; While (p !=NULL ) Firstlink =pr ;Pr =first ;first =p ;p =plink;first -link =pr ;解答2 template void List : : Tnerse() ListNode * p , *head = new ListNode ( ) ;While (first ! = NULL ) P=first ;first = firstlink;plink =headlink ; headlink =p;first = headlink ; delete head ;数据结构模拟卷 C一、单项选择题1数据结构是（D）。A一种数据类型B数据的存储结构C一组性质相同的数据元素的集合D相互之间存在一种或多种特定关系的数据元素的集合2算法分析的目的是（B）。A辨别数据结构的合理性B评价算法的效率C研究算法中输入与输出的关系D鉴别算法的可读性3在线性表的下列运算中，不改变数据元素之间结构关系的运算是（D）。A插入B删除C排序D定位4若进栈序列为1，2，3，4，5，6，且进栈和出栈可以穿插进行，则可能出现的出栈序列为（B）。A3，2，6，1，4，5B3，4，2，1，6，5C1，2，5，3，4，6D5，6，4，2，3，15设串sl=Data Structures with Java,s2=it，则子串定位函数index(s1,s2)的值为（D）。A15B16C17D186二维数组A89按行优先顺序存储，若数组元素A23的存储地址为1087，A47的存储地址为1153，则数组元素A67的存储地址为（A）。A1207B1209C1211D12137在按层次遍历二叉树的算法中，需要借助的辅助数据结构是（A）。A队列B栈C线性表D有序表8在任意一棵二叉树的前序序列和后序序列中，各叶子之间的相对次序关系（B）。A不一定相同B都相同C都不相同D互为逆序9若采用孩子兄弟链表作为树的存储结构，则树的后序遍历应采用二叉树的（C）。A层次遍历算法B前序遍历算法C中序遍历算法D后序遍历算法10若用邻接矩阵表示一个有向图，则其中每一列包含的1的个数为（A）。A图中每个顶点的入度B图中每个顶点的出度C图中弧的条数D图中连通分量的数目11图的邻接矩阵表示法适用于表示（C）。A无向图B有向图C稠密图D稀疏图12在对n个关键字进行直接选择排序的过程中，每一趟都要从无序区选出最小关键字元素，则在进行第i趟排序之前，无序区中关键字元素的个数为（D）。AiBi+1Cn-iDn-i+1二、填空题1栈是_特殊_的线性表，其运算遵循_后进先出_的原则。2_栈_是限定仅在表尾进行插入或删除操作的线性表。3. 一个栈的输入序列是：1，2，3则不可能的栈输出序列是_3，1，2_。4二叉树由_根结点、 左子树、右子树_三个基本单元组成。5在二叉树中，指针p所指结点为叶子结点的条件是P-Lchild=NULL & P-Rchild=NULL _。6具有256个结点的完全二叉树的深度为_9_。7已知一棵度为3的树有2个度为1的结点，3个度为2的结点，4个度为3的结点，则该树有_12_个叶子结点。8若不考虑基数排序，则在排序过程中，主要进行的两种基本操作是关键字的_比较_和记录的_移动_。9.分别采用堆排序，快速排序，冒泡排序和归并排序，对初态为有序的表，则最省时间的是_冒泡排序_算法，最费时间的是_快速排序_算法。10不受待排序初始序列的影响，时间复杂度为O(N2)的排序算法是_选择排序_，在排序算法的最后一趟开始之前，所有元素都可能不在其最终位置上的排序算法是_归并排序_。 三、解答题1某广义表的表头和表尾均为（a,(b,c)），画出该广义表的图形表示。2已知二叉树的先序序列和中序序列分别为HDACBGFE和ADCBHFEG。（1）画出该二叉树；