数据结构自考题-13

(总分：90.00，做题时间：90分钟)

一、{{B}}单项选择题{{/B}}(总题数：15，分数：30.00)

1.数据结构是带有结构的数据元素的集合，一般包括三个方面的内容。以下选项中，哪个不是数据结构所包括的内容。

   

A.数据的存储结构 B.数据的运算 C.数据的逻辑结构 D.数据的来源

（分数：2.00） A. B. C. D. √

解析：[考点] 数据结构所包含的内容 [解析] 数据结构是带有结构的数据元素的集合，一般包括数据的存储结构、数据的运算、数据的逻辑结构。

2.以下选项中，哪一项不属于算法需要满足的准则。

   

A.输入和输出数据 B.可行性 C.无限性 D.确定性

（分数：2.00） A. B. C. √ D.

解析：[考点] 算法满足的准则 [解析] 任何算法都要满足有限性，也就是要在有限次执行后终止。 3.对于如下程序段，语句(4)的频度为______ (1)for(i=1; i＜=n; i++){ (2)x=x+1;

(3)for(j=1; j＜=2n; j++){ (4)y=y+1; } }

   

A.n+1 B.2*n*n C.n D.n*n

（分数：2.00） A. B. √ C. D.

解析：[考点] 算法中语句的频度求解 [解析] 语句的频度也就是语句执行的次数，所以语句(4)执行的次数为2*n*n，也就是其频度为2*n*n。

4.对于一个非空的线性表，以下关于其逻辑结构特征的描述，错误的是______

   

A.开始元素没有前趋 B.终端元素没有后继

C.内部元素有且仅有一个直接前趋和一个直接后继 D.所有数据元素都既有前趋和后继

（分数：2.00） A. B. C. D. √

解析：[考点] 非空线性表的逻辑结构特征 [解析] 非空线性表的逻辑结构特征是开始元素没有前趋，终端元素没有后继，内部元素有且仅有一个直接前趋和一个直接后继。

5.若一个线性表中，第一个元素的地址为200，第六个元素的地址为220，那么该数据表中的每个元素占______个地址单元。

   

A.3 B.4 C.5 D.以上都不对

（分数：2.00） A. B. √ C. D.

解析：[考点] 线性表的地址的求解 [解析] 根据公式220=200+(6-1)×4，可知该数据表中的每个元素占4个地址单元。

6.在用p访问循环链表(其中，head为头指针)时，判断不是访问表结束的条件是______

   

A.p! =head B.p-＞next! =NULL C.p!=NULL D.p-＞next!=head

（分数：2.00） A. √

B. C. D.

解析：[考点] 循环链表结束条件的判断 [解析] 在用p访问循环链表(其中，head为头指针)时，p-＞next!=NULL，p!=NULL或者p-＞next!=head是判断表结束的条件。 7.对于栈顶指针为top的顺序栈S，判断栈空的条件是______

   

A.S.top=0 B.S.top＜0

C.S.top=StackSize-1 D.S.top=StackSize

（分数：2.00） A. B. √ C. D.

解析：[考点] 判断栈空的条件 [解析] 对于栈顶指针为top的顺序栈S，判断栈空的条件是S.top＜0。 8.在栈和队列中，存取数据的原则分别是______

   

A.先进先出；先进先出 B.先进后出；先进先出 C.先进后出；先进后出 D.进出的先后无所谓

（分数：2.00） A. B. √ C. D.

解析：[考点] 栈和队列的操作原则 [解析] 栈的操作原则是先进后出，队列的操作原则是先进先出。 9.对于一个顺序队列Q，若其队头和队尾指针分别是front与rear，如果该顺序队列为空，那么______

   

A.Q.front==Q.rear B.Q.front==Q.rear==0 C.Q.front==Q.rear+1 D.Q.rear==Q.front+1

（分数：2.00） A. √ B. C. D.

解析：[考点] 顺序队列为空的条件 [解析] 顺序队列为空的条件是Q.front==Q.rear。 10.有一个序列按照A，B，C，D，E的顺序入队，那么其出队的序列为______

   

A.A，B，C，D，E B.A，C，E，B，D C.E，D，C，B，A D.以上都不对

（分数：2.00） A. √ B. C. D.

解析：[考点] 队列的应用 [解析] 根据队列先进先出的操作原则，按照A，B，C，D，E的顺序入队，那么其出队的序列为A，B，C，D，E。

11.对一个二维数组A(行下标i的取值范围是0～7，列下标j的取值范围是0～9)采用按行优先次序存储时，如果a[0][0]的存储地址是10，并且该数组的每个元素是5个字符(每个字符占用一个存储空间)，则a[5][6]对应的地址为______

   

A.280 B.290 C.300 D.275

（分数：2.00） A. B. √ C. D.

解析：[考点] 二维数组地址的计算 [解析] 根据二维数组的计算公式a[5][6]的计算地址为a[0][0]+(5×10+6)×5=290。

12.对于对称矩阵A，为了节省存储空间，将其上三角部分按行存放在一维数组a[n(n+1)/2]中，对任意的上三角元素aij(i≤j)的存储地址是______

   

A.LOC(a[0])=j*(j+1)/2+i B.LOC(a[0])+i*(i+1)/2+j C.j*(j+1)/2+i D.i*(i+1)/2+j

（分数：2.00） A. √ B. C. D.

解析：[考点] 对称矩阵的存储地址的计算

[解析] 对于对称矩阵A，为了节省存储空间，将其上三角部分按行存放在一维数组a[n(n+1)/2]中，对任意的上三角元素aij(i≤j)的存储地址是LOC(a[0]+j*(j+1)/2+i)。

13.三维数组A2×3×4按行优先顺序存储在内存中，每个数组元素占用4个存储单元，并且起始地址为100，那么数组元素a111的地址是______

   

A.168 B.68 C.100 D.117

（分数：2.00） A. √ B. C. D.

解析：[考点] 三维数组中元素的计算公式

[解析] 根据数组的计算公式，数组元素a111的地址是168。 14.对于一个非空的广义表，其表尾______

   

A.一定是原子 B.一定是子表 C.可能是原子 D.可能是子表

（分数：2.00） A. B. √ C. D.

解析：[考点] 广义表表尾的特征 [解析] 对于非空的广义表，其表尾一定是子表。 15.广义表()和(())的长度分别是______和(())的长度分别是______

   

A.0；1 B.1；1 C.0；0 D.1；0

（分数：2.00） A. √ B. C. D.

解析：[考点] 广义表的长度的计算 [解析] 根据广义表长度的计算公式，广义表()和(())的长度分别是0和1。

二、{{B}}填空题{{/B}}(总题数：10，分数：20.00)

16.数据结构是带有结构的数据元素的集合。其中的结构指的是______，即数据的组织形式。 （分数：2.00）

填空项1:__________________ （正确答案：数据元素之间的相互关系）

解析：[考点] 数据结构中结构的概念 [解析] 数据结构是带有结构的数据元素的集合。其中结构指的是数据元素之间的相互关系，即数据的组织形式。

17.通常情况下，把对算法所要求解问题的输入量称为______，并用一个正整数n来表示。 （分数：2.00）

填空项1:__________________ （正确答案：问题的规模）

解析：[考点] 问题的规模的概念 [解析] 通常情况下，把对算法所要求解问题的输入量称为问题的规模，并用一个正整数n来表示。

18.对于一个长度为n的顺序表，当在第i个位置上插入一个元素，元素的移动次数为______。(其中，1≤i≤n) （分数：2.00）

填空项1:__________________ （正确答案：n-i+1）

解析：[考点] 顺序表中插入元素时的移动次数 [解析] 对于一个长度为n的顺序表，当在第i个位置上插入一个元素，元素的移动次数为n-i+1。

19.对于一个头结点为a的单链表，其头指针为head，判断该单链表为空的条件是______。 （分数：2.00）

填空项1:__________________ （正确答案：head-＞next==NULL）

解析：[考点] 单链表为空的判断条件 [解析] 单链表为空的判定条件为head-＞next==NULL。 20.栈是一种特殊的线性表，其操作原则是______。 （分数：2.00）

填空项1:__________________ （正确答案：后进先出） 解析：[考点] 栈的操作原则 [解析] 栈的操作原则是后进先出。

21.假设一个顺序栈存放在S.data[max]中，max-1是其栈底，则判断栈满的条件是______，判断栈空的条件是______。 （分数：2.00）

填空项1:__________________ （正确答案：S.top==0；S.top==max）

解析：[考点] 栈空栈满的判断条件 [解析] 判断栈满的条件是S.top==0，判断栈空的条件是S.top==max。 22.将三角矩阵A[5][5]的上三角部分按行优先存储在起始地址为40的内存单元中，其中每个元素占用3个存储单元，那么A[2][3]的地址为______。 （分数：2.00）

填空项1:__________________ （正确答案：）

解析：[考点] 三角矩阵的存储地址的计算 [解析] 将三角矩阵A[5][5]的上三角部分按行优先存储在起始地址为40的内存单元中，其中每个元素占用3个存储单元，那么A[2][3]的地址为。 23.已知广义表A=(a，(b，(c)，d)，e)，则操作tail(head(tail(A)))的执行结果是______。 （分数：2.00）

填空项1:__________________ （正确答案：((c)，d)）

解析：[考点] 广义表的基本操作 [解析] 若广义表A=(a，(b，(c)，d)，e)，操作tail(head(tail(A)))的执行结果是((c)，d)。

24.下面的程序段执行的功能是链栈的入栈操作，填写空白的地方。 LinkStack Push(LinkStack top, DataType x) { StackNode *p; p=(StackNode*)malloc(sizeof(StackNode)); p-＞data=x; ______ top=p; return top; } （分数：2.00）

填空项1:__________________ （正确答案：p-＞next=top;）

解析：[考点] 链栈的入栈操作的算法 [解析] 根据程序的功能，可填出其空白语句。

25.已知p指向双向链表的中间的某个结点，则操作p-＞prior-＞next=p-＞next；p-＞next-＞prior=p-＞prior; free(p)指的______。 （分数：2.00）

填空项1:__________________ （正确答案：删除p结点）

解析：[考点] 双向链表的操作 [解析] 操作p-＞prior-＞next=p-＞next; p-＞next-＞prior=p-＞prior; free(p)指的是删除p结点。

三、{{B}}解答题{{/B}}(总题数：4，分数：20.00)

26.什么是数据的逻辑结构?什么是数据的物理结构? （分数：5.00）

__________________________________________________________________________________________ 正确答案：(数据的逻辑结构是从逻辑关系上描述数据的，它与数据元素的存储结构无关，是于计算机的。数据的物理结构是数据在计算机中的实际存储形式。) 解析：[考点] 数据的逻辑结构与物理结构的概念 27.给定一个三元组表，写出其对应的稀疏矩阵。

i 0 2 2

（分数：5.00）

j 0 0 2 v 2 -1 6 __________________________________________________________________________________________ 正确答案：([*])

解析：[考点] 三元组表与稀疏矩阵的对应关系

28.给定一个序列a，b，c，当其按此顺序进栈或入队后，其出栈和出队序列分别是什么? （分数：5.00）

__________________________________________________________________________________________ 正确答案：(出栈序列为c，b，a，出队序列为a，b，c。)

解析：[考点] 栈和队列的操作 [解析] 栈的操作原则是先进后出，所以其输出序列为c，b，a；队列的操作原则是先进先出，所以其出队序列为a，b，c。

29.给定一个广义表A=((a)，((a))，A)，请分别求出其表头、表尾、长度以及深度。 （分数：5.00）

__________________________________________________________________________________________ 正确答案：(head(A)=(a) tail(A)=(((a))，A) length(A)=3 depth(A)=∞) 解析：[考点] 广义表的表头、表尾、长度以及深度的计算

四、{{B}}程序阅读题{{/B}}(总题数：2，分数：10.00)

给定如下算法，请回答问题。 void union(List LA, List LB) {

n=ListLength(LA);

for(i=1; i＜=ListLength(LB); i++){ x=GetNode(LB, i); if(LocateNode(LA, x)==0) InsertList(LA, ++n, x); }

}（分数：5.00）

(1).当LA=(a，b，c)，LB=(c，d)，执行上述算法后，LA为多少?（分数：2.50）

__________________________________________________________________________________________ 正确答案：(LA=(a，b，c，d)。) 解析：

(2).请简述该算法的功能。（分数：2.50）

__________________________________________________________________________________________ 正确答案：(该算法执行的是A=A∪B，其中线性表LA和LB分别表示集合A与B。)

解析：[考点] 线性表的应用 [解析] 根据算法，可知其为求线性表的和的运算。

阅读下列算法，回答问题。 void ex(SeqStack *S) {

int A[80], i, n; n=0;

while(!empty(S)){ A[n]=pop(S); n++; }

for(i=0; i＜n; i++) push(S, A[i]); }（分数：5.00）

(1).当S=(a，b，c，d)时，执行上述程序后其为什么?（分数：2.50）

__________________________________________________________________________________________ 正确答案：(S=(d，c，b，a)。) 解析：

(2).简述该算法的功能。（分数：2.50）

__________________________________________________________________________________________ 正确答案：(该算法的功能是通过一个数组将一个栈中的所有元素逆置存放。)

解析：[考点] 栈的操作的应用 [解析] 通过程序可以判断出其为通过一个数组将一个栈中的所有元素逆置存放的算法。

五、{{B}}算法设计题{{/B}}(总题数：1，分数：10.00)

30.将一个非负的十进制数N转换成d进制，也就是数制转换，请写出该算法。 （分数：10.00）

__________________________________________________________________________________________ 正确答案：(void conversion(int N, int d) { SeqStack S; InitStack(&S); while(N){ Push(&S, N%d); N=N/d; } while(!StackEmpty(&S)){ i=Pop(&S); printf(\"%d\解析：[考点] 栈的操作的应用