1、数据结构自考题-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;
2、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.对于一个非空的线性表，以下关于其逻辑结构特征的描述，错误的是_ 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.6.在用 p 访问循环链表(其中，head 为头指针)时，判断不是
3、访问表结束的条件是_ A.p! =head B.p-next! =NULL C.p!=NULL D.p-next!=head（分数：2.00）A.B.C.D.7.对于栈顶指针为 top 的顺序栈 S，判断栈空的条件是_ A.S.top=0 B.S.top0 C.S.top=StackSize-1 D.S.top=StackSize（分数：2.00）A.B.C.D.8.在栈和队列中，存取数据的原则分别是_ A.先进先出；先进先出 B.先进后出；先进先出 C.先进后出；先进后出 D.进出的先后无所谓（分数：2.00）A.B.C.D.9.对于一个顺序队列 Q，若其队头和队尾指针分别是 front 与
4、 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.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.11.对一个二维数组 A(行下标 i 的取值范围是 07，列下标 j 的取值范围是 09)采用按行优先次序存储时，如果 a00的存储地址是 10，并且该数组的每个元素是 5 个字符(每
5、个字符占用一个存储空间)，则a56对应的地址为_ A.280 B.290 C.300 D.275（分数：2.00）A.B.C.D.12.对于对称矩阵 A，为了节省存储空间，将其上三角部分按行存放在一维数组 an(n+1)/2中，对任意的上三角元素 aij(ij)的存储地址是_ A.LOC(a0)=j*(j+1)/2+i B.LOC(a0)+i*(i+1)/2+j C.j*(j+1)/2+i D.i*(i+1)/2+j（分数：2.00）A.B.C.D.13.三维数组 A234按行优先顺序存储在内存中，每个数组元素占用 4 个存储单元，并且起始地址为100，那么数组元素 a111的地址是_ A.1
6、68 B.68 C.100 D.117（分数：2.00）A.B.C.D.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.二、B填空题/B(总题数：10，分数：20.00)16.数据结构是带有结构的数据元素的集合。其中的结构指的是_，即数据的组织形式。（分数：2.00）填空项 1:_17.通常情况下，把对算法所要求解问题的输入量称为_，并用一个正整数 n 来表示。（分数：2.
7、00）填空项 1:_18.对于一个长度为 n 的顺序表，当在第 i 个位置上插入一个元素，元素的移动次数为_。(其中，1in)（分数：2.00）填空项 1:_19.对于一个头结点为 a 的单链表，其头指针为 head，判断该单链表为空的条件是_。（分数：2.00）填空项 1:_20.栈是一种特殊的线性表，其操作原则是_。（分数：2.00）填空项 1:_21.假设一个顺序栈存放在 S.datamax中，max-1 是其栈底，则判断栈满的条件是_，判断栈空的条件是_。（分数：2.00）填空项 1:_22.将三角矩阵 A55的上三角部分按行优先存储在起始地址为 40 的内存单元中，其中每个元素占用
8、3个存储单元，那么 A23的地址为_。（分数：2.00）填空项 1:_23.已知广义表 A=(a，(b，(c)，d)，e)，则操作 tail(head(tail(A)的执行结果是_。（分数：2.00）填空项 1:_24.下面的程序段执行的功能是链栈的入栈操作，填写空白的地方。 LinkStack Push(LinkStack top, DataType x) StackNode *p; p=(StackNode*)malloc(sizeof(StackNode); p-data=x; _ top=p; return top; （分数：2.00）填空项 1:_25.已知 p 指向双向链表的中间的
9、某个结点，则操作 p-prior-next=p-next；p-next-prior=p-prior; free(p)指的_。（分数：2.00）填空项 1:_三、B解答题/B(总题数：4，分数：20.00)26.什么是数据的逻辑结构?什么是数据的物理结构?（分数：5.00）_27.给定一个三元组表，写出其对应的稀疏矩阵。 i j v0 0 22 0 -12 2 6（分数：5.00）_28.给定一个序列 a，b，c，当其按此顺序进栈或入队后，其出栈和出队序列分别是什么?（分数：5.00）_29.给定一个广义表 A=(a)，(a)，A)，请分别求出其表头、表尾、长度以及深度。（分数：5.00）_四、
10、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）_(2).请简述该算法的功能。（分数：2.50）_阅读下列算法，回答问题。void ex(SeqStack *S)int A80, i
11、, n;n=0;while(!empty(S)An=pop(S);n+;for(i=0; in; i+)push(S, Ai); （分数：5.00）(1).当 S=(a，b，c，d)时，执行上述程序后其为什么?（分数：2.50）_(2).简述该算法的功能。（分数：2.50）_五、B算法设计题/B(总题数：1，分数：10.00)30.将一个非负的十进制数 N 转换成 d 进制，也就是数制转换，请写出该算法。（分数：10.00）_数据结构自考题-13 答案解析(总分：90.00，做题时间：90 分钟)一、B单项选择题/B(总题数：15，分数：30.00)1.数据结构是带有结构的数据元素的集合，一般
12、包括三个方面的内容。以下选项中，哪个不是数据结构所包括的内容。 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
13、+)(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. 解析：考点 非空线性表的逻辑结构特征 解析 非空线性表的逻辑结构特
14、征是开始元素没有前趋，终端元素没有后继，内部元素有且仅有一个直接前趋和一个直接后继。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.0
15、0）A. B.C.D.解析：考点 循环链表结束条件的判断 解析 在用 p 访问循环链表(其中，head 为头指针)时，p-next!=NULL，p!=NULL 或者 p-next!=head 是判断表结束的条件。7.对于栈顶指针为 top 的顺序栈 S，判断栈空的条件是_ A.S.top=0 B.S.top0 C.S.top=StackSize-1 D.S.top=StackSize（分数：2.00）A.B. C.D.解析：考点 判断栈空的条件 解析 对于栈顶指针为 top 的顺序栈 S，判断栈空的条件是 S.top0。8.在栈和队列中，存取数据的原则分别是_ A.先进先出；先进先出 B.先进
16、后出；先进先出 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，
17、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 的取值范围是 07，列下标 j 的取值范围是 09)采用按行优先次序存储时，如果 a00的存储地址是 10，并且该数组的每个元素是 5 个字符(每个字符占用一个存储空间)，则a56对应的地址为_ A.280 B.290 C.300 D.275（分数：2.00）A.B
18、. C.D.解析：考点 二维数组地址的计算 解析 根据二维数组的计算公式 a56的计算地址为 a00+(510+6)5=290。12.对于对称矩阵 A，为了节省存储空间，将其上三角部分按行存放在一维数组 an(n+1)/2中，对任意的上三角元素 aij(ij)的存储地址是_ A.LOC(a0)=j*(j+1)/2+i B.LOC(a0)+i*(i+1)/2+j C.j*(j+1)/2+i D.i*(i+1)/2+j（分数：2.00）A. B.C.D.解析：考点 对称矩阵的存储地址的计算解析 对于对称矩阵 A，为了节省存储空间，将其上三角部分按行存放在一维数组 an(n+1)/2中，对任意的上三
19、角元素 aij(ij)的存储地址是 LOC(a0+j*(j+1)/2+i)。13.三维数组 A234按行优先顺序存储在内存中，每个数组元素占用 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.解析：考点 广义表表尾的特征 解析 对于非空的广义表，其表尾一定是子表
20、。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.通常情况下，把对
21、算法所要求解问题的输入量称为_，并用一个正整数 n 来表示。（分数：2.00）填空项 1:_ （正确答案：问题的规模）解析：考点 问题的规模的概念 解析 通常情况下，把对算法所要求解问题的输入量称为问题的规模，并用一个正整数 n 来表示。18.对于一个长度为 n 的顺序表，当在第 i 个位置上插入一个元素，元素的移动次数为_。(其中，1in)（分数：2.00）填空项 1:_ （正确答案：n-i+1）解析：考点 顺序表中插入元素时的移动次数 解析 对于一个长度为 n 的顺序表，当在第 i 个位置上插入一个元素，元素的移动次数为 n-i+1。19.对于一个头结点为 a 的单链表，其头指针为 hea
22、d，判断该单链表为空的条件是_。（分数：2.00）填空项 1:_ （正确答案：head-next=NULL）解析：考点 单链表为空的判断条件 解析 单链表为空的判定条件为 head-next=NULL。20.栈是一种特殊的线性表，其操作原则是_。（分数：2.00）填空项 1:_ （正确答案：后进先出）解析：考点 栈的操作原则 解析 栈的操作原则是后进先出。21.假设一个顺序栈存放在 S.datamax中，max-1 是其栈底，则判断栈满的条件是_，判断栈空的条件是_。（分数：2.00）填空项 1:_ （正确答案：S.top=0；S.top=max）解析：考点 栈空栈满的判断条件 解析 判断栈满
23、的条件是 S.top=0，判断栈空的条件是S.top=max。22.将三角矩阵 A55的上三角部分按行优先存储在起始地址为 40 的内存单元中，其中每个元素占用 3个存储单元，那么 A23的地址为_。（分数：2.00）填空项 1:_ （正确答案：64）解析：考点 三角矩阵的存储地址的计算 解析 将三角矩阵 A55的上三角部分按行优先存储在起始地址为 40 的内存单元中，其中每个元素占用 3 个存储单元，那么 A23的地址为 64。23.已知广义表 A=(a，(b，(c)，d)，e)，则操作 tail(head(tail(A)的执行结果是_。（分数：2.00）填空项 1:_ （正确答案：(c)，
24、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、填出其空白语句。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）_正确答案：(数据的逻辑结构是从逻辑关系上描述数据的，它与数据元素的存储结构无关，是
26、独立于计算机的。数据的物理结构是数据在计算机中的实际存储形式。)解析：考点 数据的逻辑结构与物理结构的概念27.给定一个三元组表，写出其对应的稀疏矩阵。 i j v0 0 22 0 -12 2 6（分数：5.00）_正确答案：(*)解析：考点 三元组表与稀疏矩阵的对应关系28.给定一个序列 a，b，c，当其按此顺序进栈或入队后，其出栈和出队序列分别是什么?（分数：5.00）_正确答案：(出栈序列为 c，b，a，出队序列为 a，b，c。)解析：考点 栈和队列的操作 解析 栈的操作原则是先进后出，所以其输出序列为 c，b，a；队列的操作原则是先进先出，所以其出队序列为 a，b，c。29.给定一个广
27、义表 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)
28、;（分数：5.00）(1).当 LA=(a，b，c)，LB=(c，d)，执行上述算法后，LA 为多少?（分数：2.50）_正确答案：(L A=(a，b，c，d)。)解析：(2).请简述该算法的功能。（分数：2.50）_正确答案：(该算法执行的是 A=AB，其中线性表 LA和 LB分别表示集合 A 与 B。)解析：考点 线性表的应用 解析 根据算法，可知其为求线性表的和的运算。阅读下列算法，回答问题。void ex(SeqStack *S)int A80, i, n;n=0;while(!empty(S)An=pop(S);n+;for(i=0; in; i+)push(S, Ai); （分数：
29、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( while(N) Push(N=N/d; while(!StackEmpty( printf(“%d“, i) )解析：考点 栈的操作的应用
