搜索
2目录习题一.....................................................................................................................................................................3习题二.....................................................................................................................................................................5习题三.....................................................................................................................................................................7习题四.....................................................................................................................................................................9习题五..................................................................................................................................................................11习题六..................................................................................................................................................................14习题七..................................................................................................................................................................18习题八..................................................................................................................................................................20习题九..................................................................................................................................................................223习题一一、选择题1．下列有关说法不正确的是（D）。A．数据元素是数据的基本单位B．数据项是数据中不可分割的最小可标识单位C．数据可由若干个数据元素构成D．数据项可由若干个数据元素组成2．计算机所处理的数据一般具备某种内在联系，这是指（B）。A．数据和数据之间存在某种关系B．元素和元素之间存在某种关系C．元素内部存在某种关系D．数据项和数据项之间存在某种关系3．从逻辑上可以把数据结构分为（C）两大类。A．动态结构和静态结构B．顺序结构和链式结构C．线性结构和非线性结构D．初等结构和构造型结构4．下面关于算法的说法正确的是（D）。A．算法最终必须由计算机程序执行B．算法就是为解决某一问题而编写的程序C．算法的可行性是指不能有二义性指令D．以上几个都是错误的5．算法的时间复杂度取决于（C）。A．问题的规模B．待处理数据的初态C．A和BD．以上都不是4二、填空题1．数据项是数据元素中不可分割的最小标识单位，通常不具备完整、确定的实际意义，只是反映数据元素某一方面的属性。2．数据的逻辑结构通常分为集合、线性结构、树形结构和图状（或网状）结构。3．数据的存储结构通常分为顺序存储结构、链式存储结构、索引存储结构和哈希（或散列）存储结构。4．一个算法有5个特性，即有穷性、确定性、可行性、输入和输出。5．在对算法的空间复杂度进行分析时，只需考虑临时变量所占用的存储空间而不用考虑形参占用的存储空间。三、编程题（略）5习题二一、选择题1．顺序表比链表的存储密度更大，是因为（B）。A．顺序表的存储空间是预先分配的B．顺序表不需要增加指针来表示元素之间的逻辑关系C．链表的所有结点是连续的D．顺序表的存储空间是不连续的2．假定顺序表中第一个数据元素的存储地址为第1000个存储单元，若每个数据元素占用3个存储单元，则第五个元素的地址是第（C）个存储单元。A．1015B．1005C．1012D．10103．若将某一数组A中的元素，通过头插法插入至单链表B中（单链表初始为空），则插入完毕后，B中结点的顺序（A）。A．与数组中元素的顺序相反B．与数组中元素的顺序相同C．与数组中元素的顺序无关D．与数组中元素的顺序部分相同、部分相反4．与单链表相比，双链表（B）。A．可随机访问表中结点B．访问前后结点更为便捷C．执行插入、删除操作更为简单D．存储密度等于15．在一个含有n个结点的有序循环双链表中插入一个结点后，仍保持循环双链表的有序，其算法的时间复杂度为（A）。A．O(n)6B．O(1)C．O(log2n)D．O(n2)二、填空题1．我们将以顺序存储结构实现的线性表称为顺序表。2．我们将以链式存储结构实现的线性表称为链表。3．在单链表中，我们若想在头结点之前插入一个新结点nNode可通过执行nNode.next=self.head.next和self.head.next=nNode两条语句实现。注意：此处“在头结点之前插入一个新结点nNode”是指将新结点nNode插入至头结点后的第一个位置。4．在某一双链表中，假定cNode已经指向了当前待删除的结点，若想成功将该结点删除，需要执行的操作对应的代码为pNode=cNode.prev、qNode=cNode.next、pNode.next=qNode、qNode.prev=pNode、delcNode。5．循环单链表是在单链表的基础上将其自身的第一个结点的地址存入表中最后一个结点的指针域中，循环双链表是在双链表的基础上将双链表中最后一个结点的后继指针指向双链表的头结点，并将其头结点的先驱指针指向表中最后一个结点。三、编程题（略）7习题三一、选择题1．对于一个顺序栈，栈中能存储的元素个数最多不超过正整数MaxStackSize（栈顶指针top的初值为-1），对于栈满条件的判断应该为（C）。A．top!=MaxStackSize-1B．top!=MaxStackSizeC．topMaxStackSize-1D．topMaxStackSize2．让元素a、b、c、d、e依次进入一个链式栈中，则出栈的顺序不可能是（C）。A．e、d、c、b、aB．b、a、e、d、cC．d、c、a、b、eD．b、c、e、d、a3．设栈S和队列Q的初始状态均为空，元素a、b、c、d、e、f、g依次进入栈S。若每个元素出栈后立即进入队列Q，且7个元素出队的顺序是b、d、c、f、e、a、g，则栈S的容量至少是（C）。A．1B．2C．3D．44．带头结点的链式队列，其队头指针指向实际队头元素所在结点的前一个结点，其队尾指针指向队尾结点，则在进行出队操作时（D）。A．修改队头指针B．修改队尾指针C．队头和队尾指针都要修改8D．队头和队尾指针可能都要修改5．设有一个递归算法如下。deffact(self,n):ifn=0：return1else:returnself.fact(n-1)*n计算fact(n)需要调用该函数的次数为（A）。A．n+1B．n-1C．nD．n+2二、填空题1．一个栈的进栈序列为1,2,3,…,n，对应的出栈序列为S1,S2,S3,…,Sn。若S2=3，则S3可能取值的个数为n-1。2．引入循环队列的目的是提高存储空间的利用率。3．利用长度为n的列表存储循环队列的元素，队头指针front指向实际队头元素所在位置的前一个位置，队尾指针rear指向实际队尾元素，则入队时的操作为rear=(rear+1)%n，出队时的操作为front=(front+1)%n。4．栈和队列的共同点是都是操作受限的线性表。5．一个递归算法必须包括终止条件和递归部分。三、编程题（略）9习题四一、选择题1．现有两个串分别为S1=“abdcefg”，S2=“MLHWP”，对其执行以下操作(S1.SubString(0,S2.GetStringLentgh())).StringConcat(S1.SubString(S2.GetStringLentgh()-1,2))后的结果为（B）。A．bcdefB．bdcefgC．bcMLHWPD．bcdefef2．若串S=“software”，则其子串和真子串数目分别为（B）。A．8，7B．37，36C．36，35D．9，83．模式串T=“ABABAABAB”的ListNextValue值为（A）。A．(0,1,0,1,0,4,1,0,1)B．(0,1,0,1,0,2,1,0,1)C．(0,1,0,1,0,0,0,1,1)D．(0,1,0,1,0,1,0,1,1)注意：教材中介绍时是以“-1”代表没有位置可以移动,而这里分别是以“0”表示没有位置移动，下标从“1”开始。4．设矩阵A是一个对称矩阵，为了节省存储空间，将其下三角部分按照行优先存放在一个一维数组B[0,…,n(n+1)/2-1]中，对于下三角部分中任意一元素a[i][j]（i≥j），在一维数组B中的下标k的值为（B）。A．i(i-1)/2+j-1B．i(i+1)/2+j10C．i(i+1)/2+j-1D．i(i-1)/2+j5．广义表((a,b,c,d))的表头和表尾分别为（D）。A．a，(b,c,d)B．a，((b,c,d))C．(a,b,c,d)，表尾为空D．(a,b,c,d)，()二、填空题1．两个串相等的充分必要条件为两个串的长度相等且对应位置的字符依次相同。2．模式串T=“ababaab”的ListNext和ListNextValue函数值分别为0,1,1,2,3,4,2;0,1,0,1,0,4,1。注意：教材中介绍时是以“-1”代表没有位置可以移动,而这里分别是以“0”表示没有位置移动，下标从“1”开始。3．设有二维数组A[30][50]，其元素长度为4字节，按行优先顺序存储，基地址为100，则元素A[23][42]的存储地址为4868。4．稀疏矩阵常用的压缩存储方式为三元组顺序表。5．广义表(a,(a,b),d,e,(i,j),k)的长度为6，其表头和表尾分别为a;((a,b),d,e,(i,j),k)。三、编程题(略)11习题五一、选择题1．深度为h的满m叉树的第k层有（A）个结点。（1≤k≤h）A．mk-1B．mk-1C．mh-1D．mh-12．一棵具有1028个结点的二叉树的深度h为（C）。A．11B．10C．11～1028D．10～10273．关于二叉树的说法正确的是（B）。A．所有二叉树的度均为2B．一棵二叉树的度可以小于2C．一棵二叉树中至少有