数据结构自测题(带答案)2013-11-28.doc

第一章 概论 一、填空题1. 数据结构是一门研究非数值计算的程序设计问题中计算机的 操作对象 以及它们之间的 关系 和运算等的学科。2. 数据结构被形式地定义为（D, R），其中D是 数据元素 的有限集合，R是D上的 关系 有限集合。3. 数据结构包括数据的 逻辑结构 、数据的 物理结构 和数据的 运算 这三个方面的内容。4. 数据结构按逻辑结构可分为两大类，它们分别是 线性结构 和 非线性结构 。5. 线性结构中元素之间存在 一对一 关系，树形结构中元素之间存在 一对多 关系，图形结构中元素之间存在 多对多 关系。6 在线性结构中，第一个结点 无 前驱结点，其余每个结点有且只有 1个前驱结点；最后一个结点 无 后续结点，其余每个结点有且只有1个后续结点。7. 在树形结构中，树根结点没有 前驱 结点，其余每个结点有且只有 1 个前驱结点；叶子结点没有 后继 结点，其余每个结点的后续结点数可以 有多个后继 。8. 在图形结构中，每个结点的前驱结点数和后续结点数可以 有多个 。9. 一个算法的效率可分为 时间 效率和 空间 效率。10数据之间的关系在计算机中有两种不同的表示方法，即 顺序映像 和 非顺序映像 。11算法的五个重要特性是 输入性 、 输出性、 有穷性 、 可行性 和 确定性 。12 数据项 是数据的不可分割的最小单位。13算法分析的两个主要方面是 时间复杂度 和 空间复杂度 。14 数据元素 是数据的基本单位，15对于给定的n个元素，可以构造的逻辑结构有 线性 ， 集合 ，树型， 图型 等种。16数据结构包括数据的 集合 、数据的 关系 和数据的 运算 这三个方面的内容。17数据结构按逻辑结构可分为两大类，它们分别是 线性结构 和 非线性结构。二、单项选择题（ B ）1. 非线性结构是数据元素之间存在一种：A）一对多关系 B）多对多关系 C）多对一关系 D）一对一关系（ C ）2. 数据结构中，与所使用的计算机无关的是数据的 结构；A) 存储 B) 物理 C) 逻辑 D) 物理和存储（ C ）3. 算法分析的目的是：A) 找出数据结构的合理性 B) 研究算法中的输入和输出的关系C) 分析算法的效率以求改进 D) 分析算法的易懂性和文档性（ A ）4. 算法分析的两个主要方面是：A) 空间复杂性和时间复杂性 B) 正确性和简明性C) 可读性和文档性 D) 数据复杂性和程序复杂性（ C ）5. 计算机算法指的是：A) 计算方法 B) 排序方法 C) 解决问题的有限运算序列 D) 调度方法（ B ）6. 计算机算法必须具备输入、输出和 等5个特性。A) 可行性、可移植性和可扩充性 B) 可行性、确定性和有穷性C) 确定性、有穷性和稳定性 D) 易读性、稳定性和安全性三、分析下面各程序段的时间复杂度1. for (i=0; in; i+)for (j=0; jm; j+)Aij=0; O（n*m）2. s=0; for (i=0; in; i+)for(j=0; jn; j+) s+=Bij;O(n*n)3. x=0;for(i=1; in; i+) for (j=1; j=n-i; j+)x+;O(n*n)4. i=1; while(i=n) i=i*3;O（log3n）5.求下列算法段的语句频度及时间复杂度。for(i=1; i=n; i+)for(j =1; j=i ; j+)x=x+1; O(n*n)6.分析下列算法段的时间频度及时间复杂度。for （i=1;i=n;i+） for (j=1;j=i;j+) for ( k=1;knext= NULL（C）head（D）head!= NULL19若希望从链表中快速确定一个结点的前驱，则链表最好采用（ C ）方式。A、单链表 B、循环单链表 C、双向链表 D、任意20线性表是具有n个（ C ）的有限序列。 A、表元素B、字符C、数据元素D、数据项21若希望从链表中快速确定一个结点的前驱，则链表最好采用（ C ）方式。A、单链表 B、循环单链表 C、双向链表 D、任意三、简答题1. 试比较顺序存储结构和链式存储结构的优缺点。在什么情况下用顺序表比链表好？答： 顺序存储时，相邻数据元素的存放地址也相邻（逻辑与物理统一）；要求内存中可用存储单元的地址必须是连续的。优点：存储密度大（1？），存储空间利用率高。缺点：插入或删除元素时不方便。链式存储时，相邻数据元素可随意存放，但所占存储空间分两部分，一部分存放结点值，另一部分存放表示结点间关系的指针优点：插入或删除元素时很方便，使用灵活。缺点：存储密度小（top0 ST-top=0 ST-topm0 ST-top=m0（ A ）4. 判定一个队列QU（最多元素为m0）为满队列的条件是 QU-rear QU-front = = m0 QU-rear QU-front 1= = m0 QU-front = = QU-rear QU-front = = QU-rear+1（ D ）5数组用来表示一个循环队列，为当前队列头元素的前一位置，为队尾元素的位置，假定队列中元素的个数小于，计算队列中元素的公式为（）rf; （）（nfr）% n; （）nrf; （）（nrf）% n5（ B ）判定一个栈ST（最多元素为m0）为空的条件是（A）ST-top0 （B）ST-top=0 （C）ST-topm0 （D）ST-top=m06若已知一个栈的入栈序列是1,2,3,n，其输出序列为p1,p2,p3,pn，若p1=1,则pi为( D )（A）i （B）n （C） n-i+1 （D）不确定7在一个具有个单元的顺序栈中，假定以地址高端（既下标为的单元）作为栈底，以TOP作为栈顶指针，向栈中压入一个元素时，TOP的变化（ C ）（A）TOP不变（B）TOP=N（C）TOP=TOP+1（D）TOP=TOP-18栈和队列的共同点是（ C ）。 A、都是先进后出 B、都是先进先出 C、只允许在一端进行插入和删除操作 D、没有共同点9将递归算法转换成对应的非递归算法时，通常需要使用（ A ）。 A、栈 B、队列 C、链表 D、树10循环队列用数组A0,m-1存放其元素值，已知其头尾指针分别是front和rear,则当前队列中的元素个数是（ C ）。 A、rear-front B、rear-front+1 C、(rear-front+m)%m D、rear-front-111设计一个判别表达式中左,右括号是否配对出现的算法,采用（ B ）数据结构最佳. A、线性表的顺序存储结构 B、栈 C、线性表的链式存储结构 D、队列12从一个栈顶指针为HS的链栈中删除一个结点时，假定用X保存被删除结点的值，则执行 D 。A、 X=HS； HS=HS-NEXT; B、 X=HS-DATA;C、 HS=HS-NEXT；X=HS-DATA; D、 X=HS-DATA；HS=HS-NEXT;13. 设有4个数据元素a1、a2、a3和a4，对他们分别进行栈操作或队操作。在进栈或进队操作时，按a1、a2、a3、a4次序每次进入一个元素。假设栈或队的初始状态都是空。现要进行的栈操作是进栈两次，出栈一次，再进栈两次，出栈一次；这时，第一次出栈得到的元素是 A ，第二次出栈得到的元素是 B ；类似地，考虑对这四个数据元素进行的队操作是进队两次，出队一次，再进队两次，出队一次；这时，第一次出队得到的元素是 C ，第二次出队得到的元素是 D 。经操作后，最后在栈中或队中的元素还有 E 个。供选择的答案： AD：a1 a2 a3 a4 E： 1 2 3 0答：A、B、C、D、E分别为 、 、 、 、 14. 栈是一种线性表，它的特点是 A 。设用一维数组A1,n来表示一个栈，An为栈底，用整型变量T指示当前栈顶位置，AT为栈顶元素。往栈中推入（PUSH）一个新元素时，变量T的值 B ；从栈中弹出（POP）一个元素时，变量T的值 C 。设栈空时，有输入序列a，b，c，经过PUSH，POP，PUSH，PUSH，POP操作后，从栈中弹出的元素的序列是 D ，变量T的值是 E 。供选择的答案：A： 先进先出 后进先出 进优于出 出优于进 随机进出B，C： 加1 减1 不变 清0 加2 减2D： a,b b,c c,a b,a c,b a,cE： n+1 n+2 n n-1 n-2答：A、B、C、D、E分别为 、 、 、 、 15. 在做进栈运算时，应先判别栈是否 A ；在做退栈运算时，应先判别栈是否 B 。当栈中元素为n个，做进栈运算时发生上溢，则说明该栈的最大容量为 C 。为了增加内存空间的利用率和减少溢出的可能性，由两个栈共享一片连续的内存空间时，应将两栈的 D 分别设在这片内存空间的两端，这样，只有当 E 时，才产生上溢。供选择的答案：A，B：空 满 上溢 下溢C： n-1 n n+1 n/2D： 长度 深度 栈顶 栈底E：两个栈的栈顶同时到达栈空间的中心点 其中一个栈的栈顶到达栈空间的中心点 两个栈的栈顶在达栈空间的某一位置相遇 两个栈均不空，且一个栈的栈顶到达另一个栈的栈底答：A、B、C、D、E分别为 、 、 、 、 三、简答题1. 设有编号为1，2，3，4的四辆列车，顺序进入一个栈式结构的车站，具体写出这四辆列车开出车站的所有可能的顺序。4321，3421，3241，3214，2431，2314，2341，2134，2143，1234，1342，1324，1432，1243， 全进之后再出情况，只有1种：4，3，2，1 进3个之后再出的情况，有3种，3,4,2,1 3,2,4,1 3,2,1,4 进2个之后再出的情况，有5种，2,4,3,1 2,3,4,1 2,1, 3,4 2,1,4,3 2,1,3,4 进1个之后再出的情况，有5种，1,4,3,2 1,3,2,4 1,3,4,2 1, 2,3,4 1,2,4,32. 顺序队列的“假溢出”是怎样产生的？如何知道循环队列是空还是满？答：一般的一维数组队列的尾指针已经到了数组的上界，不能再有入队操作，但其实数组中还有空位置，这就叫“假溢出”。采用循环队列是解决假溢出的途径。另外，解决队满队空的办法有三： 设置一个布尔变量以区别队满还是队空； 浪费一个元素的空间，用于区别队满还是队空。 使用一个计数器记录队列中元素个数（即队列长度）。我们常采用法，即队头指针、队尾指针中有一个指向实元素，而另一个指向空闲元素。判断循环队列队空标志是： f=rear 队满标志是：f=(r+1)%N3. 设循环队列的容量为40（序号从0到39），现经过一系列的入队和出队运算后，有 front=11，rear=19; front=19，rear=11；问在这两种情况下，循环队列中各有元素多少个？答：用队列长度计算公式： (Nrearfron)% N L=（401911）% 40=8 L=（401119）% 40=324 写出下列程序段的输出结果（栈的元素类型SElem Type为char）。Pop(S,x); Push(S,t); Push(S,x);Pop(S,x); Push(S,s);while(!StackEmpty(S) Pop(S,y);printf(y); ;Printf(x);void main( )Stack S;Char x,y;InitStack(S);x=c;y=k;Push(S,x); Push(S,a); Push(S,y);答：输出为“stack”5 写出下列程序段的输出结果（队列中的元素类型QElem Type为char）。void main( )Queue Q; Init Queue (Q);Char x=e; y=c;EnQueue (Q,h); EnQueue (Q,r); EnQueue (Q,y);DeQueue (Q,x); EnQueue (Q,x); DeQueue (Q,x); EnQueue (Q,a); while(!QueueEmpty(Q) DeQueue (Q,y);printf(y); ;Printf(x);答：char6 简述以下算法的功能（栈和队列的元素类型均为int）。void algo3(Queue &Q)Stack S; int d;InitStack(S);while(!QueueEmpty(Q) DeQueue (Q,d); Push(S,d);while(!StackEmpty(S) Pop(S,d); EnQueue (Q,d); 第5章 数组 一、填空题1. 假设有二维数组A68，每个元素用相邻的6个字节存储，存储器按字节编址。已知A的起始存储位置（基地址）为1000，则数组A的体积（存储量）为 288 ；末尾元素A57的第一个字节地址为 1282 ；若按行存储时，元素A14的第一个字节地址为 (8+4)6+1000=1072 ；若按列存储时，元素A47的第一个字节地址为 (674)61000）1276 。2. 设数组a6070的基地址为2048，每个元素占2个存储单元，若以列序为主序顺序存储，则元素a3258的存储地址为 9072 。3. 三元素组表中的每个结点对应于稀疏矩阵的一个非零元素，它包含有三个数据项，分别表示该元素的行号 、 列号 和 数值 。4.求下列广义表操作的结果：（1） GetHead(a,b),(c,d)= (a,b) ; （2） GetHeadGetTail(a,b),(c,d)= (c,d) ;（3） GetHeadGetTailGetHead(a,b),(c,d)= b ;（4） GetTailGetHeadGetTail(a,b),(c,d) = (d) ;5二维数组A0.200.10采用以行序为主方式存储，每个元素占4个存储单元,并且A00的存储地址是1016，则A98的存储地址是 1444 6假设线性表的每个元素占用L个存储单元，线性表中第i+1个数据元素的存储位置LOC(ai+1)和第i个元素的存储位置LOC(ai)之间满足的关系式为： 不确定 7稀疏矩阵常用的两种存储方法有 三元组表 和 十字链表 。二、单选题（ A ）1 假设有60行70列的二维数组a6070以列序为主序顺序存储，其基地址为10000，每个元素占2个存储单元，那么第32行第58列的元素a3258的存储地址为 。（无第0行第0列元素） 16902 16904 14454 答案A, B, C均不对( B ) 2. 设矩阵A是一个对称矩阵，为了节省存储，将其下三角部分（如右图所示）按行序存放在一维数组B 1, n(n-1)/2 中，对下三角部分中任一元素ai,j(ij), 在一维数组B中下标k的值是：i(i-1)/2+j-1 i(i-1)/2+j i(i+1)/2+j-1 i(i+1)/2+j3. 从供选择的答案中，选出应填入下面叙述 ？ 内的最确切的解答，把相应编号写在答卷的对应栏内。有一个二维数组A，行下标的范围是0到8，列下标的范围是1到5，每个数组元素用相邻的4个字节存储。存储器按字节编址。假设存储数组元素A0,1的第一个字节的地址是0。存储数组A的最后一个元素的第一个字节的地址是 A 。若按行存储，则A3,5和A5,3的第一个字节的地址分别是 B 和 C 。若按列存储，则A7,1和A2,4的第一个字节的地址分别是 D 和 E 。供选择的答案AE：28 44 76 92 108 116 132 176 184 188答案：A B C D E= 4. 从供选择的答案中，选出应填入下面叙述 ？ 内的最确切的解答，把相应编号写在答卷的对应栏内。有一个二维数组A，行下标的范围是1到6，列下标的范围是0到7，每个数组元素用相邻的6个字节存储，存储器按字节编址。那么，这个数组的体积是 A 个字节。假设存储数组元素A1,0的第一个字节的地址是0，则存储数组A的最后一个元素的第一个字节的地址是 B 。若按行存储，则A2,4的第一个字节的地址是 C 。若按列存储，则A5,7的第一个字节的地址是 D 。供选择的答案AD：12 66 72 96 114 120 156 234 276 282 （11）283 （12）288答案：A （12） B C D 5设有50行的二维数组A5060，其元素长度为2字节，按行优先顺序存储，基地址为200，则元素A1825的存储地址为（ D 2410 ）。A、1850 B、188 C、1950 D、24106广义表(a,b,(c,(d)的表尾是（ D ）。 A(d) B. (c,(d) C. b,(c,(d) D. (b,(c,(d) 三、简答题1. 已知二维数组Am,m采用按行优先顺序存放，每个元素占K个存储单元，并且第一个元素的存储地址为Loc(a11)，请写出求Loc(aij)的计算公式。如果采用列优先顺序存放呢？解：公式教材已给出，此处虽是方阵，但行列公式仍不相同；按行存储的元素地址公式是： Loc(aij)= Loc(a11) + (i-1)*m+(j-1) * K按列存储的元素地址公式是： Loc(aij)= Loc(a11) + (j-1)*m+(i-1) * K四、计算题1. 用三元组表表示下列稀疏矩阵： 解：参见填空题4. 三元素组表中的每个结点对应于稀疏矩阵的一个非零元素，它包含有三个数据项，分别表示该元素的 行下标 、 列下标 和 元素值 。所以（1）可列表为： （2）可列表为：8866416-225943565353233685467858122. 下列各三元组表分别表示一个稀疏矩阵，试写出它们的稀疏矩阵。 解：（1）为64矩阵，非零元素有6个。 （2）为45矩阵，非零元素有5个0 2 0 0 12 0 0 0 3 0 0 0 0 0 0 4 0 0 6 0 16 0 0 0 1 0 0 0 00 0 0 9 00 8 0 0 60 0 7 0 03试画出下列稀疏矩阵以行序为主序的三元组表。 答：4设一稀疏矩阵为6行5列，其三元组表中存储的非零元素依将为（-90，28，7，24，35，5，-98）,列号依次为1，4，5，2，5，1，4，行表cpot的值依次为0,0,2,2,3,5,5,请画出该稀疏矩阵。答案为：00000-900028000000000070240032500-9805设有一个二维数组Amn，假设A00存放位置在644（10），A22存放位置在676（10），每个元素占一个空间，问A33（10）存放在什么位置？脚注（10）表示用10进制表示。答案：设数组元素Aij存放在起始地址为Loc(i,j)的存储单元中。 因为：Loc(2,2)= Loc(0,0)+2*n+2=644+2*n+2=676 所以：n=(676-2-644)/2=15 所以：Loc(3,3)= Loc(0,0)+3*15+3=644+45+3=692 6数组A中，每个元素Ai,j的长度均为2个字节,行下标从1到9，列下标从1到11，从首地址S开始连续存