修改后的习题.doc

数据结构习题习题一一、选择题1、数据结构是一门研究非数值计算的程序设计问题中的操作对象以及它们之间的（）和运算的学科。 A结构 B关系 C运算 D算法2、在数据结构中，从逻辑上可以把数据结构分成（）。 A动态结构和静态结构 B紧凑结构和非紧凑结构 C线性结构和非线性结构 D逻辑结构和存储结构3、线性表的逻辑顺序和存储顺序总是一致的，这种说法（）。 A正确 B不正确 C无法确定 D以上答案都不对4、算法分析的目的是（）。 A找出算法的合理性 B研究算法的输人与输出关系 C分析算法的有效性以求改进 D分析算法的易懂性二、填空题1、_是信息的载体，是对客观事物的符号表示，它能够被计算机识别、存储、加工和处理，_是对能够有效的输人到计算机中并且能够被计算机处理的符号的总称。例如，数学中所用到的整数和实数，文本编辑所用到的字符串等。 2、数据元素是数据的_，有些情况下也称为元素、结点、顶点、记录等。3、_是数据不可分割的最小单元，是具有独立含义的最小标识单位。例如构成一个数据元素的字段、域、属性等都可称之为_。 4、简而言之，数据结构是数据之间的_，即数据的_。 5、数据的逻辑结构是指数据之间的_。逻辑结构是从_上描述数据，它与具体存储无关，是独立于计算机的。因此逻辑结构可以看作是从具体问题抽象出来的_。 6、数据的_指数据元素及其关系在计算机存储器内的表示。_是逻辑结构在计算机里的实现，也称之为映像。 7、_是指对数据施加的操作。它定义在数据的逻辑结构之上，每种逻辑结构都有一个_。常用的有：查找、排序、插人、删除、更新等操作。 8、数据逻辑结构可以分为四种基本的类型，_结构中的元素除了仅仅只是同属于一个_，不存在什么关系。 9、数据逻辑结构的四种基本类型中，_中的元素是一种一对一的关系，这种结构的特征是：若结构是非空集，则有且只有一个开始结点和一个终端结点，并且所有结点最多只能有一个直接前驱和一个直接后继。 10、数据逻辑结构的四种基本类型中，_中的元素是一种一对多的关系。 11、图型结构或图状结构是一种_的关系。在这种逻辑结构中，所有结点均可以有多个前驱和多个后继。 12、有时也可将树型结构、集合和图型结构称为_，这样数据的逻辑结构就可以分为_和_两大类。 13、_方式是指逻辑上相邻的结点被存储到物理上也相邻的存储单元中。这种存储结构只存储结点的数值，不存储结点之间的关系，结点之间的关系是通过存储单元的相邻关系隐含的表示出来的。 14、_方式是种存储方法，不要求逻辑上相邻的结点在物理上也相邻，即数据元素可以存储在任意的位置上。 15、索引存储方式又可以分为_和_。若每个结点在索引表中都有一个索引项，则该种索引存储方式称为_；若一组结点在索引表中只对应一个索引项，则索引存储方式称为_。在一中，索引项的地址指示结点所在的位置，而一中，索引项的地址指示一组结点的起始位置。 16、_方式是利用结点关键字的值直接计算出该结点存储单元地址，然后将结点按某种方式存人该地址的一种方法。 17、所谓算法（Algorithm）是对特定问题求解方法和步骤的一种描述，它是指令的一组_，其中每个指令表示一个或多个操作。18、算法的_性是指算法必须能够在执行有限个步骤之后结束，并且每个步骤都必须在有穷的时间内完成。 19、算法的_性是指算法中的每一个步骤必须是有明确定义的，不允许有模棱两可的解释，也不允许有多义性。并且，在任何条件下，算法只能有惟一的一条执行路径，即只要输人是相同的就只能得到_的输出结果。 20、算法的_性又称为算法的能行性，是指算法中描述的操作是可以通过已经实现的基本运算执行_次来实现，即算法的_应该能够被计算机执行。 21、判断一个算法的好坏主要以下几个标准：_、_、_、_。 22、算法分析是对一种算法所消耗的计算机资源的估算，其中包括计算机_的长短和_的大小。 23、空间复杂度（SPace ComPlexity）也是度量一个算法好坏的标准，它所描述的是算法在运行过程中所占用_的大小。三、判断题 1、顺序存储方式只能用于存储线性结构。（） 2、数据元素是数据的最小单位。（） 3、算法可以用不同的语言描述，如果用C语言或PASCAL语言等高级语言描述，则算法实际上就是程序了。（） 4、数据结构是带有结构的数据元素的集合。（）5、数据的逻辑结构是指各元素之间的逻辑关系，是用户根据需要而建立的。（） 6、数据结构、数据元素、数据项在计算机中的映像分别称为存储结构、结点、数据域。（） 7、数据的物理结构是指数据在计算机中实际的存储形式。（） 8、具有存取任一元素的时间相等这一特点的存储结构称为随机存取结构。（）四、综合题 1、用大O形式表示下面算法的时间复杂度： for（i=0；im；i十十） for（j=0；jn；j） Aij=i*j； 2、写出下面算法的时间复杂度： i0； s=0； while(sn） i+; s+=i; 3、写出以下算法的时间复杂度： for（i0; im; i）for（j0 ; jt; j） cij=0；for（i=0；im；i） for（j=o; jt; j+） for（k=0；kn；k） cijaik*bkj;4、写出下面算法的时间复杂度：i=1;while（in） i=i*3;5、求下面函数中各条语句的频度和算法的时间复杂度：prime（int n） int i2； while (ni）！=0isqrt(n) ) i+; if（isqrt(n) ) printf（”d is a prime number.n”，n）； else printf（”d is not a prime number.n”，n）；习题二一、选择题 1在一个长度为n的顺序表中删除第i个元素（0i=0）个数据元素的_。其中n为数据元素的个数，定义为线性表的_。当n为零时的表称为_。4所谓顺序表（Sequential LISt）是线性表的_，它是将线性表中的结点按其_依次存放在内存中一组连续的存储单元中，使线性表中相邻的结点存放在_的存储单元中。5单链表不要求逻辑上相邻的存储单元在物理上也一定要相邻。它是分配一些_的存储单元来存储线性表中的数据元素，这些存储单元可以分散在内存中的_的位置上，它们在物理上可以是一片连续的存储单元，也可以是_的。因此在表示线性表这种数据结构时，必须在存储线性表元素的同时，也存储线性表的。6线性表的链式存储结构的每一个结点（Node）需要包括两个部分：一部分用来存放元素的数据信息，称为结点的_；另一部分用来存放元素的指向直接后继元素的指针(即直接后继元素的地址信息)，称为_或_。7线性链表的逻辑关系是通过每个结点指针域中的指针来表示的。其逻辑顺序和物理存储顺序不再一致，而是一种_存储结构，又称为_。8如果将单链表最后一个结点的指针域改为存放链表中的头结点的地址值，这样就构成了_。9为了能够快速地查找到线性表元素的直接前驱，可在每一个元素的结点中再增加一个指向其前驱的指针域，这样就构成了_。10双向链表某结点的指针P，它所指向结点的后继的前驱与前驱的后继都是p_。11在单链表中，删除指针P所指结点的后继结点的语句是_。12在双循环链表中，删除指针P所指结点的语句序列是P-prior-nextp-next及_。13单链表是_的链接存储表示。14可以使用_表示树形结构。15向一个长度为n的向量的第i个元素(lin+1）之前插人一个元素时，需向后移动_个元素。16删除一个长度为n的向量的第i个元素（lin）时，需向前移动_个元素。17在单链表中，在指针P所指结点的后面插人一个结点S的语句序列是_。18在双循环链表中，在指针P所指结点前插人指针S所指的结点，需执行语句_。19取出广义表A（x，（a，b，c，d）中原子c的函数是_。20在一个具有n个结点的有序单链表中插人一个新结点并使之仍然有序的时间复杂度为_。21写出带头结点的双向循环链表L为空表的条件_。22线性表、栈和队列都是_结构。23向栈中插人元素的操作是先移动栈_针，再存人元素。三、判断题1线性表采用链表存储时，结点和结点内部的存储空间可以是不连续的。（）2在具有头结点的链式存储结构中，头指针指向链表中的第一个数据结点。( ) 3顺序存储的线性表不可以随机存取。（） 4单链表不是一种随机存储结构。（）5顺序存储结构线性表的插入和删除运算所移动元素的个数与该元素的位置无关。() 6顺序存储结构是动态存储结构，链式存储结构是静态存储结构。（）7线性表的长度是线性表所占用的存储空间的大小。（）8双循环链表中，任意一结点的后继指针均指向其逻辑后继。（）9线性表的惟一存储形式是链表。（）四、综合题1编写一个将带头结点单链表逆置的算法。2ha和hb分别是两个按升序排列的、带头结点的单链表的头指针，设计一个算法，把这两个单链表合并成一个按升序排列的单链表，并用hC指向它的头结点。3有一个带头结点的单链表，头指针为head，编写一个算法countlist（）计算所有数据域为X的结点的个数（不包括头结点）。4在一个带头结点的单链表中，头指针为head，它的数据域的类型为整型，而且按由小到大的顺序排列，编写一个算法insertxlist（），在该链表中插人值为x的元素，并使该链表仍然有序。5在一个带头结点的单链表中，head为其头指针，p指向链表中的某一个结点，编写算法swapinlist（），实现p所指向的结点和p的后继结点相互交换。6有一个带头结点的单链表，所有元素值以非递减有序排列，head为其头指针，编写算法deldylist（）将该链表中多余元素值相同的结点删除。7在带头结点的单链表中，设计算法dellistmaxmin，删除所有数据域大于min，而小于max的元素。8设计一个将双链表逆置的算法invertdblinklist（），其中头指针为head，结点数据域为data，两个指针域分别为prior和next。习题三一、选择题 l一个栈的序列是：a，b，c，d，e，则栈的不可能输出的序列是（）。Aa，b，c，d，e Bd，e，c，b，a Cd，c，e，a，b De，d，c，b，a 2若一个栈的输人序列是1，2，3，n，输出序列的第一个元素是n，则第k个输出元素是（ ）。 Ak Bn-k-1 Cn-k+1 D不确定3判定一个栈S（最多有n个元素）为空的条件是（ ）。 AS-top！0 BS-top= =0 CS-top!=n DS-top= =n4判定一个栈S（最多有n个元素）为满的条件是（ ）。 AS-top!=0 BS-top= =0 CS-top!=n DS-top= =n5向一个栈顶指针为top的链栈中插人一个*S结点的时候，应当执行语句（ ）。 Atop-next=S； BS-next=top；top=S； CS-nexttop-next；top-nextS；DS-nexttop；topS-next；6向一个带头结点、栈顶指针为top的链栈中插人一个*S结点的时候，应当执行语句（ ）。 Atop-next=S； BS-next=top；top=S； CS-next=top-next；top-next=S； DS-next=top；top=S-next；7判定一个队列Q（最多有n个元素）为空的条件是（ ）。 AQ-rear-Q-front= =n BQ-rear-Q-front+1= =n CQ-rear = = Q-front DQ-rear +1= = Q-front8判定一个队列Q（最多有n个元素）为满的条件是（）。 AQ-rear-Q-front= =n BQ-rear-Q-front+1= =n CQ-rear = = Q-front DQ-rear +1= = Q-front9判定一个循环队列Q（最多有n个元素）为空的条件是（ ）。 AQ-rear = = Q-front BQ-rear = = Q-frontl CQ-front= =(Q-rear +1)n DQ-front= =(Q-rear -1)n10判定一个循环队列Q（最多有n个元素）为满的条件是（ ）。 AQ-rear = = Q-front BQ-rear = = Q-frontl CQ-front= =(Q-rear +1)n DQ-front= =(Q-rear -1)n11在一个链队列中，假定front和rear分别为头指针和尾指针，则插入一个结点*S的操作是（ ）。 Afrontfront-next BS-next=rear；rear=S Crear-next=S；rear=S DS-next=front；frontS12在一个链队列中，假定front和rear分别为头指针和尾指针，删除一个结点的操作是（ ）。 Afront=front-next Brear=rear-next Crear-next=front Dfront-nextrear 13栈与队列都是（ ）。 A链式存储的线性结构 B链式存储的非线性结构 C限制存取点的线性结构 D限制存取点的非线性结构 14若进栈序列为l，2，3，4，则（ ）不可能是一个出栈序列。 A3，2，4，1 Bl，2，3，4 C4，2，3，1 D4，3，2，l 15在解决计算机主机与打印机之间速度不匹配问题时通常设置一个打印数据缓冲区，主机将要输出的数据依次写人该缓冲区，而打印机则从该缓冲区中取走数据打印。该缓冲区应该是一个（ ）结构。 A堆栈 B队列 C数组 D线性表二、填空回1栈（stack）是限定在_一端进行插人或删除操作的线性表。在栈中，允许插人和删除操作的一端称为_，而另一端称为_。不含元素的栈称为_。2在栈的运算中，栈的插人操作称为_或_，栈的删除操作称为_或_。3根据栈的定义，每一次进栈的元素都在原_之上，并成为新的_；每一次出栈的元素总是当前的_，因此最后进栈的元素总是_，所以栈也称为_线性表，简称为_表。4栈是一种操作受到限制的线性表，是一种特殊的线性表，因此栈也有_和_两种存储结构，分别称为_和_。5当栈满的时候，再进行人栈操作就会产生_，这种情况的溢出称为_；当栈空的时候，如果再进行出栈操作，也会_，这种情况下的溢出称为_。6栈的链式存储结构简称为_，是一种_。7人们日常计算用到的表达式都被称为_，这是由于这种算术表达式的运算符被置于两个操作数中间。8计算机中通常使用_，这是一种将运算符置于两个操作数后面的算术表达式。这种表达式是由波兰科学家谢维奇提出的，因此又称为_。9队列（Queue）也是一种_，但它与栈不同，队列中所有的插人均限定在表的一端进行，而所有的删除则限定在表的另一端进行。允许插人的一端称为_，允许删除的一端称为_。10队列的特点是_，因此队列又被称为_的线性表，或称为_表。11队列的_又称为_，是用一组地址连续的存储单元依次存放队列中的元素。12由于队列中的元素经常变化，对于队列的删除和插人分别在队头和队尾进行，因此需要设置两个指针分别指向_和_，这两个指针又称为_和_。13循环顺序队列（Circular Sequence Queue）经常简称为_，它是将存储顺序队列的存储区域看成是一个首尾相连的一个环，即将队首和队尾元素连接起来形成一个环形表。首尾相连的状态是通过数学上的_来实现的。14在算法或程序中，当一个函数直接调用自己或通过一系列语句间接调用自己的时候，则称这个函数为，也称为_。函数直接调用自己，则称为_；当一个函数通过另一个函数来调用自己则称为_。15在循环队列中规定：当Q-rear= =Q-front的时候循环队列为_， 当（Q-rear+1）MAXSIZEfront的时候循环队列为_。16用链表方式表示的队列称为_。17已知栈的输人序列为1，2，3，n，输出序列为a1，a2，an，符合a2= =n的输出序列共有_。18一个栈的输人序列是12345，则栈的输出序列为43512是_（填是否可能）。19一个栈的输人序列是12345，则栈的输出序列为12345是_（填是否可能）。20设sq1maxsize为一个顺序存储的栈，变量top指示栈顶元素的位置，则作入栈操作的条件是_。21设sq1maxsize为一个顺序存储的栈，变量top指示栈顶元素的位置，如果把栈顶元素弹出并送到X中，则需执行语句_。22栈的特性是_。23对栈进行退栈时的操作是先取出元素，后移动_。24设s1max为一个顺序存储的栈，变量top指示栈顶位置，栈为满的条件是_。25设链栈的栈顶指针为top，则栈非空的条件是_。26已知循环队列用数组data1.n存储元素值，用f，r分别作为头尾指针， 则当前元素个数为_。27在一个循环队列中，队首指针指向队首元素的_位置。（前一个或后一个）28队列中允许进行删除的一端称为_。29链队列实际上是一个同时带有头指针和尾指针的单链表（1n），尾指针指向该单链表的第_个元素。30设双向链表链列为lq，lq的头指针为lq.Front，尾指针为lq.Rear，则队列为空的条件是_。31从循环队列中删除一个元素，其操作是先取出一个元素，后移动_。32队列中允许进行插入的一端称为_。三、判断题1栈和队列都是限制存取点的线性结构。（ ）2不同的人栈和出栈组合可能得到相同输出序列。（ ）3消除递归一定要用栈。（ ）4循环队列是顺序存储结构。（ ）5循环队列不会产生溢出。（ ）6循环队列满的时候rear= =front。（ ）7在对链队列（带头结点）做出队操作时不会改变front指针的值。（）四、综合题1设有4个元素A、B、C和D进栈，给出它们所有可能的出栈秩序。2输入n个10以内的数，每输入k（0=k=9），就把它插人到第k号队列中。最后把10个队列中的非空队列按队列序号以从小到大的顺序串接成一条链，并输出该链中的所有元素。3假设用循环单链表实现循环队列，该队列只使用一个尾指针rear，其相应的存储结构和基本操作算法如下：(l) 初始化队列 initqueue (Q)：建立一个新的空队列 Q。(2) 人队列enqueue (Q，x)：将元素 x插人到队列 Q中。(3) 出队列delqueue (Q)：从队列Q中退出一个元素。(4) 取队首元素gethead (Q)：返回当前队首元素。(5) 判断队列是否为空：emptyqueue (Q)。(6) 显示队列中元素：dispqueue (Q)。4“回文”是指一个字符串从头读到尾和从尾读到头都一样。假设字符串是从输人设备一次一个字节的读人，并且读到字符“”的时候表示结束。请用栈和队列编写一个算法判断一个字符串是否回文。5假设表达式中有三种括号：圆括号“（）”、方括号“ ”和花括号“ ”用C语言编写程序判断读人的表达式中不同括号是否正确配对，假定读人的表达式以”#”结束。6用C语言编写背包问题的算法。背包问题的描述是：假设有n件质量分别为w1，w2，wn的物品和一个最多能装载总质量是T的背包，问能否从这n件物品中选择若干件物品装人背包，并且使被选物品的总质量