《数据结构第1-4章选择题(有 答案).doc》由会员分享，可在线阅读，更多相关《数据结构第1-4章选择题(有 答案).doc（8页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、如有侵权，请联系网站删除，仅供学习与交流数据结构 第1-4章选择题(有 答案)【精品文档】第 8 页第1章 绪论5选择题（1）在数据结构中，从逻辑上可以把数据结构分成（ ）。A动态结构和静态结构 B紧凑结构和非紧凑结构C线性结构和非线性结构 D内部结构和外部结构（2）与数据元素本身的形式、内容、相对位置、个数无关的是数据的（ ）。A存储结构 B存储实现C逻辑结构 D运算实现（3）通常要求同一逻辑结构中的所有数据元素具有相同的特性，这意味着（ ）。 A数据具有同一特点B不仅数据元素所包含的数据项的个数要相同，而且对应数据项的类型要一致C每个数据元素都一样D数据元素所包含的数据项的个数要相等（4）
2、以下说法正确的是（ ）。A数据元素是数据的最小单位B数据项是数据的基本单位C数据结构是带有结构的各数据项的集合D一些表面上很不相同的数据可以有相同的逻辑结构说明：注意几个概念：数据项是数据的最小单位而不是基本单位，数据元素才是数据的基本单位，数据结构是带有结构的数据元素的集合而不是数据项的集合。（5）以下与数据的存储结构无关的术语是（ ）。A顺序队列 B. 链表 C. 有序表 D. 链栈说明：数据的存储结构只有数组（或称为顺序存储）和链表两种。顺序队列是用数组存储的队列，链表和链栈都是用链表。（6）以下数据结构中，（ ）是非线性数据结构A树 B字符串 C队 D栈第2章 线性表1选择题（1）一个
3、向量第一个元素的存储地址是100，每个元素的长度为2，则第5个元素的地址是（ ）。A110 B108 C100 D120说明：计算公式：A+(i-1)*L，A为起始地址，i是元素序号，L是元素长度。（2）在n个结点的顺序表中，算法的时间复杂度是O(1)的操作是（ ）。A访问第i个结点（1in）和求第i个结点的直接前驱（2in） B在第i个结点后插入一个新结点（1in）C删除第i个结点（1in）D将n个结点从小到大排序（3） 向一个有127个元素的顺序表中插入一个新元素并保持原来顺序不变，平均要移动的元素个数为（ ）。A8 B63.5 C63 D7说明：n个元素的顺序表共有n+1个插入位置（包括
4、一头一尾），在第i个位置插入元素需要移动n-i+1个元素，因此平均为(1+2+n)/(n+1)=n/2。（4）链接存储的存储结构所占存储空间（ ）。A分两部分，一部分存放结点值，另一部分存放表示结点间关系的指针B只有一部分，存放结点值C只有一部分，存储表示结点间关系的指针D分两部分，一部分存放结点值，另一部分存放结点所占单元数（5）线性表若采用链式存储结构时，要求内存中可用存储单元的地址（ ）。A必须是连续的 B部分地址必须是连续的C一定是不连续的 D连续或不连续都可以（6）线性表在（ ）情况下适用于使用链式结构实现。A需经常修改中的结点值 需不断对进行删除插入 C中含有大量的结点 中结点结构
5、复杂（7）单链表的存储密度（ ）。A大于1 B等于1 C小于1 D不能确定说明：存储密度的定义在课本p41表2.1的末尾，它是小于或等于1的一个实数。（8）将两个各有n个元素的有序表归并成一个有序表，其最少的比较次数是（ ）。An B2n-1 C2n Dn-1说明：合并两个有序表的算法见课本算法2.15和算法2.16。当两个表中的一个完全排在另一个表的前面时，比较的次数最少，此时只是后面表中的第一个元素与前面表中的元素逐一比较一次，然后就直接将两个表连接起来。（9）在一个长度为n的顺序表中，在第i个元素（1in+1）之前插入一个新元素时须向后移动（ ）个元素。An-i Bn-i+1 Cn-i-
6、1 Di(10) 线性表L=(a1，a2,an)，下列说法正确的是（ ）。A每个元素都有一个直接前驱和一个直接后继B线性表中至少有一个元素C表中诸元素的排列必须是由小到大或由大到小D除第一个和最后一个元素外，其余每个元素都有一个且仅有一个直接前驱和直接后继。(11) 若指定有n个元素的向量，则建立一个有序单链表的时间复杂性的量级是（ ）。AO(1) BO(n) CO(n2) DO(nlog2n)说明：这道题其实有些问题。若题目的意思是，有n个元素，事先我们不知道元素的大小次序，我们依此将这些元素一个个插入单链表中并且使得单链表有序。注意这是单链表，第8章的一些快速排序算法在这里用不上。因为是单
7、链表，每次插入一个元素，只能从表头开始逐一比较，寻找插入的位置。在最坏的情况下，需要比较n(n-1)/2次，时间复杂性为O(n2)。但平均却是O(n)。如果n个元素事先已存在单链表中，现在对其排序，则可采用类似“冒泡排序”或“简单选择排序”那样的算法，时间复杂性为O(n2)。(12) 以下说法错误的是（ ）。A求表长、定位这两种运算在采用顺序存储结构时实现的效率不比采用链式存储结构时实现的效率低B顺序存储的线性表可以随机存取C由于顺序存储要求连续的存储区域，所以在存储管理上不够灵活D线性表的链式存储结构优于顺序存储结构(13) 在单链表中，要将s所指结点插入到p所指结点之后，其语句应为（ ）。
8、As-next=p+1; p-next=s;B(*p).next=s; (*s).next=(*p).next;Cs-next=p-next; p-next=s-next;Ds-next=p-next; p-next=s; (14) 在双向链表存储结构中，删除p所指的结点时须修改指针（ ）。Ap-next-prior=p-prior; p-prior-next=p-next;Bp-next=p-next-next; p-next-prior=p;Cp-prior-next=p; p-prior=p-prior-prior;Dp-prior=p-next-next; p-next=p-prior
9、-prior;(15) 在双向循环链表中，在p指针所指的结点后插入q所指向的新结点，其修改指针的操作是（ ）。Ap-next=q; q-prior=p; p-next-prior=q; q-next=q;Bp-next=q; p-next-prior=q; q-prior=p; q-next=p-next;Cq-prior=p; q-next=p-next; p-next-prior=q; p-next=q;Dq-prior=p; q-next=p-next; p-next=q; p-next-prior=q;说明：对于（13）、（14）、（15）这类题，在草稿纸上画一画链表就明白了。要注意的
10、是，按语句次序，一旦修改了某根指针，就要删掉原来的指针。第3章 栈和队列1选择题（1）若让元素1，2，3，4，5依次进栈，则出栈次序不可能出现（ ）的情况。A5,4,3,2,1 B2,1,5,4,3 C4,3,1,2,5 D2,3,5,4,1（2）若已知一个栈的入栈序列是1，2，3，n，其输出序列为p1，p2，p3，pn，若p1=n，则pi为（ ）。 Ai Bn-i Cn-i+1 D不确定说明：p1=n表明全部元素入栈之后才出栈，因此出栈序列只能是n,n-1,2,1,第i个出栈的必为n-i+1。（3）数组用来表示一个循环队列，为当前队列头元素的前一位置，为队尾元素的位置，假定队列中元素的个数小
11、于，计算队列中元素个数的公式为（ ）。Ar-f B(n+f-r)%n Cn+r-f D（n+r-f)%n说明：当用数组表示循环队列时，f、r是数组元素的下脚标。由于是循环的，所以有可能rf，则r-f即为队列的元素个数；当rf时，(n+r-f)%n=(r-f)%n=r-f。（4）链式栈结点为：(data,link)，top指向栈顶.若想摘除栈顶结点，并将删除结点的值保存到x中,则应执行操作（ ）。Ax=top-data;top=top-link； Btop=top-link;x=top-link； Cx=top;top=top-link； Dx=top-link；说明：链栈是一个单链表，表头为栈
12、顶，见课本p47图3.3。（5）设有一个递归算法如下 int fact(int n) /n大于等于0 if(n=0) return 1; else return n*fact(n-1); 则计算fact(n)需要调用该函数的次数为（ ）。An+1 Bn-1 C n D n+2说明：可观察函数的参数，它将依次为n,n-1,1,0，共n+1个。（6）栈在（ ）中有所应用。A递归调用 B函数调用 C表达式求值 D前三个选项都有必须指出，递归调用使用的是系统堆栈，不是应用程序设计的栈。（7）为解决计算机主机与打印机间速度不匹配问题，通常设一个打印数据缓冲区。主机将要输出的数据依次写入该缓冲区，而打印机
13、则依次从该缓冲区中取出数据。该缓冲区的逻辑结构应该是（ ）。A队列 B栈 C 线性表 D有序表（8）设栈S和队列Q的初始状态为空，元素e1、e2、e3、e4、e5和e6依次进入栈S，一个元素出栈后即进入Q，若6个元素出队的序列是e2、e4、e3、e6、e5和e1，则栈S的容量至少应该是（）。A2 B3 C4 D 6说明：由于一个元素出栈后即进入队列，而队列是“先进先出”，所以出队的序列就是出栈的序列。（9）在一个具有n个单元的顺序栈中，假设以地址高端作为栈底，以top作为栈顶指针，则当作进栈处理时，top的变化为（）。 Atop不变 Btop=0 Ctop- Dtop+（10）设计一个判别表达
14、式中左，右括号是否配对出现的算法，采用（）数据结构最佳。A线性表的顺序存储结构 B队列 C. 线性表的链式存储结构 D. 栈（11）用链接方式存储的队列，在进行删除运算时（）。A. 仅修改头指针 B. 仅修改尾指针C. 头、尾指针都要修改 D. 头、尾指针可能都要修改说明：题目的意思是，用单链表实现队列，头指针指向第一个元素结点（首元结点），不使用头结点。不然的话，象课本p65图3.13的情形，删除操作只可能修改头结点中的指针，头指针永远不变。由于队列是“先进先出”的，所以删除的一定是队列第一个元素，当队列元素只剩一个时，删除后需同时修改头、尾指针。（12）循环队列存储在数组A0.m中，则入队
15、时的操作为（）。A. rear=rear+1 B. rear=(rear+1)%(m-1) C. rear=(rear+1)%m D. rear=(rear+1)%(m+1) 说明：数组长度是m+1而不是m。（13）最大容量为n的循环队列，队尾指针是rear，队头是front，则队空的条件是（）。 A. (rear+1)%n=front B. rear=front Crear+1=front D. (rear-l)%n=front说明：题目指的是课本p63图3.11所示的循环队列。（14）栈和队列的共同点是（）。A. 都是先进先出 B. 都是先进后出 C. 只允许在端点处插入和删除元素 D.
16、没有共同点说明：栈的“端点”是栈顶，队列的“端点”是队头。（15）一个递归算法必须包括（）。A. 递归部分 B. 终止条件和递归部分C. 迭代部分 D. 终止条件和迭代部分说明：“迭代”是循环的另一种说法。第4章 串、数组和广义表1选择题（1）串是一种特殊的线性表，其特殊性体现在（ ）。 A可以顺序存储 B数据元素是一个字符 C可以链式存储 D数据元素可以是多个字符 （2）下面关于串的的叙述中，（ ）是不正确的？ A串是字符的有限序列 B空串是由空格构成的串C模式匹配是串的一种重要运算 D串既可以采用顺序存储，也可以采用链式存储（3）串“ababaaababaa”的next数组为（ ）。A01
17、2345678999 B012121111212 C011234223456 D0123012322345（4）串“ababaabab”的nextval为（ ）。A010104101 B010102101 C010100011 D010101011 （5）串的长度是指（ ）。A串中所含不同字母的个数 B串中所含字符的个数C串中所含不同字符的个数 D串中所含非空格字符的个数（6）假设以行序为主序存储二维数组A=array1.100,1.100，设每个数据元素占2个存储单元，基地址为10，则LOC5,5=（ ）。A808 B818 C1010 D1020说明：按行序存储时，A5,5位于第5行第5列
18、，之前有4行，每行100个元素，所在第5行前面有4个元素，因此在A5,5前面一共有4*100+4=404个元素。从基地址10开始存放，每个元素两个单元，所以A5,5的存储地址是10+404*2=818。一般的计算公式是：loc(i,j)=BA+(i-1)*n+(j-1)*L，其中BA是基地址，n是数组列数，L是每个元素占用的单元数。注意按此公式计算时，i、j必须是从1数起的。（7）设有数组Ai,j，数组的每个元素长度为3字节，i的值为1到8，j的值为1到10，数组从内存首地址BA开始顺序存放，当用以列为主存放时，元素A5,8的存储首地址为（ ）。ABA+141 BBA+180 CBA+222
19、DBA+225说明：按列序存储，A5,8前面有7列，每列8个元素，所在的第8列上方有4个元素（因为在第5行），因此A58前面共有7*8+4=60个元素，每个元素3个字节，故存储地址为BA+60*3=BA+180。（8）设有一个10阶的对称矩阵A，采用压缩存储方式，以行序为主存储，a11为第一元素，其存储地址为1，每个元素占一个地址空间，则a85的地址为（ ）。A13 B32 C33 D40说明：这道题没有说明按上三角还是下三角存储。假设按下三角存储，则a85前面有7行，第1行只有一个元素，第2行有2个元素，依次类推，前7行共有1+2+7=28个元素，a85所在的第8行前面有4个元素，于是前面共
20、有28+4=32个元素，从地址1开始存储，每个元素一个字节，因此存储地址为1+32=33。若按上三角存储，则存储的是a85对称的元素a58，其存储地址为38。（9）若对n阶对称矩阵A以行序为主序方式将其下三角形的元素(包括主对角线上所有元素)依次存放于一维数组B1.(n(n+1)/2中，则在B中确定aij（ij）的位置k的关系为（ ）。Ai*(i-1)/2+j Bj*(j-1)/2+i Ci*(i+1)/2+j Dj*(j+1)/2+i说明：此题计算的是aij在数组B中的下标而不是存储地址，只要计算从数组第1个元素开始，到aij共有几个元素。aij前面共有i-1行，第1行在B中只存储一个元素，
21、第2行存储2个元素，依次类推，前i-1行共存储了1+2+(i-1)=i*(i-1)/2个元素，aij位于第i行第j列，这一行到aij为止存储了j个元素，因此B中到aij为止共有i*(i-1)/2+j个元素。（10）二维数组A的每个元素是由10个字符组成的串，其行下标i=0,1,8，列下标j=1,2,10。若A按行先存储，元素A8,5的起始地址与当A按列先存储时的元素（ ）的起始地址相同。设每个字符占一个字节。AA8,5 BA3,10 CA5,8 DA0,9说明：因为每个元素占用的单元数都相同，所以只要计算所存储的元素个数即可。当按行优先存储时，A8,5前面有8行（行号从0数起），每行10个元素
22、，所在的第8行前面有4个元素，因此存储到A8,5之前共有8*10+4=84个元素。按列优先存储时，若要存储在相同位置，则前面同样必须有84个元素，因为每列有9个元素，所以列号一定要大于84/9=9，由此即知只有选择项B符合要求。（11）设二维数组A1. m，1. n（即m行n列）按行存储在数组B1. m*n中，则二维数组元素Ai,j在一维数组B中的下标为（ ）。A(i-1)*n+j B(i-1)*n+j-1 Ci*(j-1) Dj*m+i-1说明：从第一行开始，在B中依次存储A中每个元素，存储到Ai,j共有多少个元素，下标就是多少。Ai,j前面有i-1行，每行n个元素，共有(i-1)*n个元素
23、；所在的第i行到Ai,j为止有j个元素，因此下标为(i-1)*n+j。（12）数组A0.4,-1.-3,5.7中含有元素的个数（ ）。A55 B45 C36 D16（13）广义表A=(a,b,(c,d),(e,(f,g)，则Head(Tail(Head(Tail(Tail(A)的值为（ ）。A(g) B(d) Cc Dd说明：Tail(A)= (b,(c,d),(e,(f,g) Tail(Tail(A)=Tail(b,(c,d),(e,(f,g)= (c,d),(e,(f,g) Head(Tail(Tail(A)=Head (c,d),(e,(f,g)=(c,d) Tail(Head(Tail(Tail(A)=Tail(c,d)=(d)Head(Tail(Head(Tail(Tail(A)=Head(d)=d（14）广义表(a,b,c,d)的表头是（ C ），表尾是（ B ）。Aa B( ) C(a,b,c,d) D(b,c,d)（15）设广义表L=(a,b,c)，则L的长度和深度分别为（ ）。A1和1 B1和3 C1和2 D2和3