数据结构 第1-4章选择题(有 答案)

5．选择题

（1）在数据结构中，从逻辑上可以把数据结构分成（ ）。

A．动态结构和静态结构 ．紧凑结构和非紧凑结构

C．线性结构和非线性结构 ．内部结构和外部结构

（2）与数据元素本身的形式、内容、相对位置、个数无关的是数据的（ ）。

A．存储结构 ．存储实现

C．逻辑结构 ．运算实现

（3）通常要求同一逻辑结构中的所有数据元素具有相同的特性，这意味着（ ）。

 ．数据具有同一特点

B．不仅数据元素所包含的数据项的个数要相同，而且对应数据项的类型要一致

C．每个数据元素都一样

D．数据元素所包含的数据项的个数要相等

（4）以下说法正确的是（ ）。

A．数据元素是数据的最小单位

B．数据项是数据的基本单位

C．数据结构是带有结构的各数据项的集合

D．一些表面上很不相同的数据可以有相同的逻辑结构

说明：注意几个概念：数据项是数据的最小单位而不是基本单位，数据元素才是数据的基本单位，数据结构是带有结构的数据元素的集合而不是数据项的集合。

（5）以下与数据的存储结构无关的术语是（   ）。

A．顺序队列       B. 链表        C. 有序表          D.  链栈

说明：数据的存储结构只有数组（或称为顺序存储）和链表两种。顺序队列是用数组存储的队列，链表和链栈都是用链表。

（6）以下数据结构中，（  ）是非线性数据结构

A．树        B．字符串       C．队           D．栈

第2章  线性表

1．选择题

（1）一个向量第一个元素的存储地址是100，每个元素的长度为2，则第5个元素的地址是（ ）。

A．1B．108 C．1D．120

说明：计算公式：A+(i-1)*L，A为起始地址，i是元素序号，L是元素长度。

（2）在n个结点的顺序表中，算法的时间复杂度是O(1)的操作是（ ）。

A．访问第i个结点（1≤i≤n）和求第i个结点的直接前驱（2≤i≤n） 

B．在第i个结点后插入一个新结点（1≤i≤n）

C．删除第i个结点（1≤i≤n）

D．将n个结点从小到大排序

（3） 向一个有127个元素的顺序表中插入一个新元素并保持原来顺序不变，平均要移动的元素个数为（ ）。

A．8B．63.5 C．6D．7

说明：n个元素的顺序表共有n+1个插入位置（包括一头一尾），在第i个位置插入元素需要移动n-i+1个元素，因此平均为(1+2+…+n)/(n+1)=n/2。

（4）链接存储的存储结构所占存储空间（ ）。

A．分两部分，一部分存放结点值，另一部分存放表示结点间关系的指针

B．只有一部分，存放结点值

C．只有一部分，存储表示结点间关系的指针

D．分两部分，一部分存放结点值，另一部分存放结点所占单元数

（5）线性表若采用链式存储结构时，要求内存中可用存储单元的地址（ ）。

A．必须是连续的 ．部分地址必须是连续的

C．一定是不连续的 D．连续或不连续都可以

（6）线性表Ｌ在（ ）情况下适用于使用链式结构实现。

A．需经常修改Ｌ中的结点值 Ｂ．需不断对Ｌ进行删除插入 

C．Ｌ中含有大量的结点 Ｄ．Ｌ中结点结构复杂

（7）单链表的存储密度（ ）。

A．大于1  B．等于1 C．小于1 D．不能确定

说明：存储密度的定义在课本p41表2.1的末尾，它是小于或等于1的一个实数。

（8）将两个各有n个元素的有序表归并成一个有序表，其最少的比较次数是（ ）。

A．n  ．2n-1   C．2n   D．n-1

说明：合并两个有序表的算法见课本算法2.15和算法2.16。当两个表中的一个完全排在另一个表的前面时，比较的次数最少，此时只是后面表中的第一个元素与前面表中的元素逐一比较一次，然后就直接将两个表连接起来。

（9）在一个长度为n的顺序表中，在第i个元素（1≤i≤n+1）之前插入一个新元素时须向后移动（ ）个元素。

A．n-i    B．n-i+1     ．n-i-1    D．i

(10) 线性表L=(a1，a2,……an)，下列说法正确的是（ ）。

A．每个元素都有一个直接前驱和一个直接后继

B．线性表中至少有一个元素

C．表中诸元素的排列必须是由小到大或由大到小

D．除第一个和最后一个元素外，其余每个元素都有一个且仅有一个直接前驱和直接后继。

(11) 若指定有n个元素的向量，则建立一个有序单链表的时间复杂性的量级是（ ）。

A．O(1)   B．O C．O(n2)   D．O(nlog2n)

说明：这道题其实有些问题。若题目的意思是，有n个元素，事先我们不知道元素的大小次序，我们依此将这些元素一个个插入单链表中并且使得单链表有序。注意这是单链表，第8章的一些快速排序算法在这里用不上。因为是单链表，每次插入一个元素，只能从表头开始逐一比较，寻找插入的位置。在最坏的情况下，需要比较n(n-1)/2次，时间复杂性为O(n2)。但平均却是O(n)。

如果n个元素事先已存在单链表中，现在对其排序，则可采用类似“冒泡排序”或“简单选择排序”那样的算法，时间复杂性为O(n2)。

(12) 以下说法错误的是（ ）。

A．求表长、定位这两种运算在采用顺序存储结构时实现的效率不比采用链式存储结构时实现的效率低

B．顺序存储的线性表可以随机存取

C．由于顺序存储要求连续的存储区域，所以在存储管理上不够灵活

D．线性表的链式存储结构优于顺序存储结构

(13) 在单链表中，要将s所指结点插入到p所指结点之后，其语句应为（ ）。

A．s->next=p+1; p->next=s;

B．(*p).next=s; (*s).next=(*p).next;

C．s->next=p->next; p->next=s->next;

D．s->next=p->next; p->next=s;

 (14) 在双向链表存储结构中，删除p所指的结点时须修改指针（ ）。

A．p->next->prior=p->prior; p->prior->next=p->next;

B．p->next=p->next->next; p->next->prior=p;

C．p->prior->next=p; p->prior=p->prior->prior;

D．p->prior=p->next->next; p->next=p->prior->prior;

(15) 在双向循环链表中，在p指针所指的结点后插入q所指向的新结点，其修改指针的操作是（ ）。

A．p->next=q; q->prior=p; p->next->prior=q; q->next=q;

B．p->next=q; p->next->prior=q; q->prior=p; q->next=p->next;

C．q->prior=p; q->next=p->next; p->next->prior=q; p->next=q;

D．q->prior=p; q->next=p->next; p->next=q; p->next->prior=q;

说明：对于（13）、（14）、（15）这类题，在草稿纸上画一画链表就明白了。要注意的是，按语句次序，一旦修改了某根指针，就要删掉原来的指针。

第3章  栈和队列

1．选择题

（1）若让元素1，2，3，4，5依次进栈，则出栈次序不可能出现（  ）的情况。

A．5,4,3,2,1   B．2,1,5,4,3    C．4,3,1,2,5    D．2,3,5,4,1

（2）若已知一个栈的入栈序列是1，2，3，…，n，其输出序列为p1，p2，p3，…，pn，若p1=n，则pi为（  ）。

    A．i               B．n-i               C．n-i+1            D．不确定

说明：p1=n表明全部元素入栈之后才出栈，因此出栈序列只能是n,n-1,…,2,1,第i个出栈的必为n-i+1。

（3）数组Ｑ［ｎ］用来表示一个循环队列，ｆ为当前队列头元素的前一位置，ｒ为队尾元素的位置，假定队列中元素的个数小于ｎ，计算队列中元素个数的公式为（  ）。

A．r-f             B．(n+f-r)%n       C．n+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中,则应执行操作（  ）。

A．x=top->data;top=top->link； B．top=top->link;x=top->link；

C．x=top;top=top->link；    D．x=top->link；

说明：链栈是一个单链表，表头为栈顶，见课本p47图3.3。

（5）设有一个递归算法如下

        int fact(int n) {  //n大于等于0

             if(n<=0) return 1;

             else return n*fact(n-1);        }

则计算fact(n)需要调用该函数的次数为（  ）。 

A． n+1              B． n-1              C． n                  D． n+2

说明：可观察函数的参数，它将依次为n,n-1,…,1,0，共n+1个。

（6）栈在 （  ）中有所应用。

A．递归调用       B．函数调用      C．表达式求值        D．前三个选项都有

必须指出，递归调用使用的是系统堆栈，不是应用程序设计的栈。

（7）为解决计算机主机与打印机间速度不匹配问题，通常设一个打印数据缓冲区。主机将要输出的数据依次写入该缓冲区，而打印机则依次从该缓冲区中取出数据。该缓冲区的逻辑结构应该是（  ）。

A．队列      B．栈   C． 线性表     D．有序表

（8）设栈S和队列Q的初始状态为空，元素e1、e2、e3、e4、e5和e6依次进入栈S，一个元素出栈后即进入Q，若6个元素出队的序列是e2、e4、e3、e6、e5和e1，则栈S的容量至少应该是（　）。

A．2              B．3              C．4                D． 6

说明：由于一个元素出栈后即进入队列，而队列是“先进先出”，所以出队的序列就是出栈的序列。

（9）在一个具有n个单元的顺序栈中，假设以地址高端作为栈底，以top作为栈顶指针，则当作进栈处理时，top的变化为（　）。 

A．top不变 B．top=0C．top--   D．top++

（10）设计一个判别表达式中左，右括号是否配对出现的算法，采用（　）数据结构最佳。

A．线性表的顺序存储结构              B．队列     

C. 线性表的链式存储结构              D. 栈

（11）用链接方式存储的队列，在进行删除运算时（　）。

A. 仅修改头指针                      B. 仅修改尾指针

C. 头、尾指针都要修改                D. 头、尾指针可能都要修改

说明：题目的意思是，用单链表实现队列，头指针指向第一个元素结点（首元结点），不使用头结点。不然的话，象课本p65图3.13的情形，删除操作只可能修改头结点中的指针，头指针永远不变。

由于队列是“先进先出”的，所以删除的一定是队列第一个元素，当队列元素只剩一个时，删除后需同时修改头、尾指针。

（12）循环队列存储在数组A[0..m]中，则入队时的操作为（　）。

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                                                          

C．rear+1==front                      D. (rear-l)%n==front

说明：题目指的是课本p63图3.11所示的循环队列。

（14）栈和队列的共同点是（　）。

A. 都是先进先出                       B. 都是先进后出   

C. 只允许在端点处插入和删除元素       D. 没有共同点

说明：栈的“端点”是栈顶，队列的“端点”是队头。

（15）一个递归算法必须包括（　）。

A. 递归部分                           B. 终止条件和递归部分

C. 迭代部分                           D. 终止条件和迭代部分

说明：“迭代”是循环的另一种说法。

第4章  串、数组和广义表

1．选择题

（1）串是一种特殊的线性表，其特殊性体现在（  ）。

  A．可以顺序存储               B．数据元素是一个字符      

C．可以链式存储               D．数据元素可以是多个字符 

（2）下面关于串的的叙述中，（  ）是不正确的？ 

A．串是字符的有限序列

B．空串是由空格构成的串

C．模式匹配是串的一种重要运算  

D．串既可以采用顺序存储，也可以采用链式存储

（3）串“ababaaababaa”的next数组为（  ）。

A．0．0C．011234223456 ．0123012322345

（4）串“ababaabab”的nextval为（  ）。

A．010104101      B．010102101  C．0．010101011 

（5）串的长度是指（  ）。

A．串中所含不同字母的个数   B．串中所含字符的个数

C．串中所含不同字符的个数   D．串中所含非空格字符的个数

（6）假设以行序为主序存储二维数组A=array[1..100,1..100]，设每个数据元素占2个存储单元，基地址为10，则LOC[5,5]=（  ）。

A．8 B．818  ．1．1020

说明：按行序存储时，A[5,5]位于第5行第5列，之前有4行，每行100个元素，所在第5行前面有4个元素，因此在A[5,5]前面一共有4*100+4=404个元素。从基地址10开始存放，每个元素两个单元，所以A[5,5]的存储地址是10+404*2=818。

一般的计算公式是：loc(i,j)=BA+[(i-1)*n+(j-1)]*L，其中BA是基地址，n是数组列数，L是每个元素占用的单元数。注意按此公式计算时，i、j必须是从1数起的。

（7）设有数组A[i,j]，数组的每个元素长度为3字节，i的值为1到8，j的值为1到10，数组从内存首地址BA开始顺序存放，当用以列为主存放时，元素A[5,8]的存储首地址为（  ）。

A．BA+141    B．BA+180    C．B．BA+225

说明：按列序存储，A[5,8]前面有7列，每列8个元素，所在的第8列上方有4个元素（因为在第5行），因此A[58]前面共有7*8+4=60个元素，每个元素3个字节，故存储地址为BA+60*3=BA+180。

（8）设有一个10阶的对称矩阵A，采用压缩存储方式，以行序为主存储，a11为第一元素，其存储地址为1，每个元素占一个地址空间，则a85的地址为（  ）。

A．1   B．32    C．33 ．40

说明：这道题没有说明按上三角还是下三角存储。假设按下三角存储，则a85前面有7行，第1行只有一个元素，第2行有2个元素，依次类推，前7行共有1+2+…+7=28个元素，a85所在的第8行前面有4个元素，于是前面共有28+4=32个元素，从地址1开始存储，每个元素一个字节，因此存储地址为1+32=33。

若按上三角存储，则存储的是a85对称的元素a58，其存储地址为38。

（9）若对n阶对称矩阵A以行序为主序方式将其下三角形的元素(包括主对角线上所有元素)依次存放于一维数组B[1..(n(n+1))/2]中，则在B中确定aij（iA．i   B．j*(j-1)/2+i   C．i*(i+1)/2+j    D．j*(j+1)/2+i

说明：此题计算的是aij在数组B中的下标而不是存储地址，只要计算从数组第1个元素开始，到aij共有几个元素。

aij前面共有i-1行，第1行在B中只存储一个元素，第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按行先存储，元素A[8,5]的起始地址与当A按列先存储时的元素（ ）的起始地址相同。设每个字符占一个字节。

A．A[8,5]       B．A[3,10]   C．A[5,8]    D．A[0,9]

说明：因为每个元素占用的单元数都相同，所以只要计算所存储的元素个数即可。

当按行优先存储时，A[8,5]前面有8行（行号从0数起），每行10个元素，所在的第8行前面有4个元素，因此存储到A[8,5]之前共有8*10+4=84个元素。

按列优先存储时，若要存储在相同位置，则前面同样必须有84个元素，因为每列有9个元素，所以列号一定要大于[84/9]=9，由此即知只有选择项B符合要求。

（11）设二维数组A[1.. m，1.. n]（即m行n列）按行存储在数组B[1.. m*n]中，则二维数组元素A[i,j]在一维数组B中的下标为（  ）。

A．(i-1)*n+j    B．(i-1)*n+j-  C．i*(j-1)   D．j*m+i-1

说明：从第一行开始，在B中依次存储A中每个元素，存储到A[i,j]共有多少个元素，下标就是多少。A[i,j]前面有i-1行，每行n个元素，共有(i-1)*n个元素；所在的第i行到A[i,j]为止有j个元素，因此下标为(i-1)*n+j。

（12）数组A[0..4,-1..-3,5..7]中含有元素的个数（  ）。

A．5   B．45         C．3   D．16

（13）广义表A=(a,b,(c,d),(e,(f,g)))，则Head(Tail(Head(Tail(Tail(A)))))的值为（  ）。

A．(．(．c D．d

说明：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 ）。

A．a  ．( ) ．(a,b,c,d)      D．(b,c,d)

（15）设广义表L=((a,b,c))，则L的长度和深度分别为（  ）。

A．1和1  ．1和3   C．1和2       ．2和3