数据结构自考题-13

1、数据结构自考题-13(总分：90.00，做题时间：90分钟)一、B单项选择题/B(总题数：15,分数：30.00)1. 数据结构是带有结构的数据元素的集合，一般包括三个方面的内容。以下选项中，哪个不是数据结构所 包括的内容。« A.数据的存储结构* B.数据的运算C.数据的逻辑结构D.数据的来源(分数：2.00)A.B.C.D. V解析：考点数据结构所包含的内容解析数据结构是带有结构的数据元素的集合，一般包括数据的存 储结构、数据的运算、数据的逻辑结构。2. 以下选项中，哪一项不属于算法需要满足的准则。* A.输入和输岀数据* B.可行性C.无限性« D.确定性(分数：2.

2、00 )A.B.C. VD.解析：考点算法满足的准则解析任何算法都要满足有限性，也就是要在有限次执行后终止。3. 对于如下程序段，语句(4)的频度为(1) for(i=1; iv =n; i+)(2) x=x+1;(3) for(j=1; jv =2n; j+)y=y+1;（分数:2.00 ）A.B. VC.D.解析：考点算法中语句的频度求解解析语句的频度也就是语句执行的次数，所以语句（4）执行的次数为2*n*n，也就是其频度为2*n*n。4. 对于一个非空的线性表，以下关于其逻辑结构特征的描述，错误的是« A.开始元素没有前趋B.终端元素没有后继C.内部元素有且仅有一个直接前趋和一

3、个直接后继« D.所有数据元素都既有前趋和后继（分数：2.00）A.B.C.D. V解析：考点非空线性表的逻辑结构特征解析非空线性表的逻辑结构特征是开始元素没有前趋，终端元素没有后继，内部元素有且仅有一个直接前趋和一个直接后继。5. 若一个线性表中，第一个元素的地址为200,第六个元素的地址为 220,那么该数据表中的每个元素占个地址单元。«A.3* B.4«C.5* D.以上都不对（分数：2.00 ）A.B. VC.D.解析：考点线性表的地址的求解解析根据公式220=200+（6- 1） X4,可知该数据表中的每个元素占4个地址单元。6. 在用p访问循环链表（其

4、中，head为头指针）时，判断不是访问表结束的条件是 * A.p! =head* B.p- > next! =NULL* C.p!=NULL* D.p- > next!=head（分数：2.00 ）A. VB.C.D.解析：考点循环链表结束条件的判断解析在用p访问循环链表（其中，head为头指针）时，p- > next!=NULL , p!=NULL或者p- > next!=head 是判断表结束的条件。7. 对于栈顶指针为top的顺序栈S,判断栈空的条件是 * < 0« « （分数：2.00 ）A.B. VC.D.解析：考点判断栈空的条件解析

5、对于栈顶指针为top的顺序栈S,判断栈空的条件是 S.top < 0。8. 在栈和队列中，存取数据的原则分别是 « A.先进先出； 先进先出* B.先进后出；先进先出« C.先进后岀；先进后岀«D.进出的先后无所谓（分数：2.00 ）A.B. VC.D.解析：考点栈和队列的操作原则解析栈的操作原则是先进后出，队列的操作原则是先进先出。9. 对于一个顺序队列 Q,若其队头和队尾指针分别是front与rear，如果该顺序队列为空，那么 * 叶1*（分数：2.00 ）A. VB.C.D.解析：考点顺序队列为空的条件解析顺序队列为空的条件是 Q.front=Q.re

6、ar 。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. VB.C.D.解析：考点队列的应用解析根据队列先进先出的操作原则，按照A, B, C, D, E的顺序入队，那么其出队的序列为 A, B, C, D, E。11. 对一个二维数组 A(行下标i的取值范围是07,列下标j的取值范围是09)采用按行优先次序存储时，如果a00的存储地址是10,并且该数组的每个元素是5个字符(每个字符占用一个存储空间)，则a56 对应的地址为«A.

7、280«B.290«C.300«D.275(分数：2.00 )A.B. VC.D.解析：考点二维数组地址的计算解析根据二维数组的计算公式a56的计算地址为a00+(5 X 10+6)X5=29012. 对于对称矩阵A,为了节省存储空间，将其上三角部分按行存放在一维数组an(n+1)/2中，对任意的上三角元素ay (i <j)的存储地址是 «A.L OC(a0)=j*(j+1)/2+i* B.L OC(a0)+i*(i+1)/2+j«C.j*(j+1)/2+i* D.i*(i+1)/2+j(分数：2.00 )A. VB.C.D.解析：考点对

8、称矩阵的存储地址的计算解析对于对称矩阵A,为了节省存储空间，将其上三角部分按行存放在一维数组an(n+1)/2中，对任意的上三角元素 aij (i <j)的存储地址是LOC(a0+j*(j+1)/2+i)。13. 三维数组AX3X4按行优先顺序存储在内存中，每个数组元素占用4个存储单元，并且起始地址为100,那么数组元素am的地址是«A.168«B.68«C.100«D.117（分数:2.00 ）A. VB.C.D.解析：考点三维数组中元素的计算公式解析根据数组的计算公式，数组元素am的地址是16814. 对于一个非空的广义表，其表尾 «

9、 A. 一定是原子* B. 一定是子表« C.可能是原子« D.可能是子表（分数：2.00 ）A.B. VC.D.解析：考点广义表表尾的特征解析对于非空的广义表，其表尾一定是子表。15. 广义表（）和（）的长度分别是 和（）的长度分别是 «A.0; 1«B.1 ; 1«C.0; 0«D.1 ; 0（分数：2.00 ）A. VB.C.D.解析：考点广义表的长度的计算解析根据广义表长度的计算公式，广义表（）和（）的长度分别是0和1。二、B填空题/B（ 总题数：10,分数：20.00）16. 数据结构是带有结构的数据元素的集合。其中的结构指

10、的是 ，即数据的组织形式。（分数：2.00 ）填空项1： （正确答案：数据元素之间的相互关系）解析：考点数据结构中结构的概念解析数据结构是带有结构的数据元素的集合。其中结构指的是数据元素之间的相互关系，即数据的组织形式。17. 通常情况下，把对算法所要求解问题的输入量称为 ，并用一个正整数n来表示。（分数： 2.00 ）填空项 1: （正确答案：问题的规模）解析： 考点 问题的规模的概念 解析 通常情况下，把对算法所要求解问题的输入量称为问题的规模， 并用一个正整数 n 来表示。18. 对于一个长度为n的顺序表，当在第i个位置上插入一个元素，元素的移动次数为 。（其中,1<i <n

11、）（分数： 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: （正确答案：后进先出）解析： 考点 栈的操作原则

12、 解析 栈的操作原则是后进先出。21. 假设一个顺序栈存放在 S.datamax 中， max-1 是其栈底，则判断栈满的条件是 ，判断栈空的条件是 。（分数： 2.00 ）填空项 1: （正确答案： S.top=0 ；S.top=max）解析： 考点 栈空栈满的判断条件 解析 判断栈满的条件是 S.top=0 ，判断栈空的条件是 S.top=max。22. 将三角矩阵 A55 的上三角部分按行优先存储在起始地址为 40 的内存单元中，其中每个元素占用 3个存储单元，那么 A23 的地址为 。（分数： 2.00 ）填空项 1: （正确答案： 64）解析： 考点 三角矩阵的存储地址的计算 解析

13、将三角矩阵 A55 的上三角部分按行优先存储在起始 地址为 40 的内存单元中，其中每个元素占用 3 个存储单元，那么 A23 的地址为 64。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,Data

14、Type 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

15、）填空项1: （正确答案：删除 p结点）解析： 考点 双向链表的操作 解析 操作 p->prior- >next=p- >next; p->next- >prior=p- >prior; free（p） 指的是删除 p 结点。三、B 解答题 /B（ 总题数： 4，分数： 20.00）26. 什么是数据的逻辑结构 ?什么是数据的物理结构 ?（分数： 5.00 ）ijv00220-1226正确答案：(数据的逻辑结构是从逻辑关系上描述数据的, 的。数据的物理结构是数据在计算机中的实际存储形式。 解析：考点数据的逻辑结构与物理结构的概念27. 给定一个三元组表，写岀

16、其对应的稀疏矩阵。它与数据元素的存储结构无关，是独立于计算机)(分数：5.00 ) 正确答案：(*)解析：考点三元组表与稀疏矩阵的对应关系28. 给定一个序列a, b, c,当其按此顺序进栈或入队后，其岀栈和岀队序列分另U是什么 (分数：5.00 )正确答案：(出栈序列为c, b, a,出队序列为a, b, c。)解析：考点栈和队列的操作解析栈的操作原则是先进后出，所以其输出序列为c, b, a;队列的操作原则是先进先出，所以其出队序列为a, b, c。29. 给定一个广义表 A=(a) , (a) , A)，请分别求出其表头、表尾、长度以及深度。(分数：5.00 )正确答案：(head(A)

17、=(a) tail(A)=(a), A) length(A)=3 depth(A)=解析：考点广义表的表头、表尾、长度以及深度的计算四、B程序阅读题/B(总题数：2,分数：10.00)给定如下算法，请回答问题。void union( List LA, List LB)n=ListLe ngth(LA);for(i=1; iv =ListLength(LB); i+)x=GetNode(LB, i);if(LocateNode(LA, x)=0)In sertList(LA, +n, x);(分数：5.00 )(1) .当LA=(a , b, c) , LB=(c , d)，执行上述算法后，LA

18、为多少？(分数：2.50 )正确答案：(L A=(a , b , c , d) o )解析：(2) .请简述该算法的功能。(分数：2.50 ) 正确答案：(该算法执行的是 A=AJB,其中线性表 La和Lb分别表示集合A与Bo ) 解析： 考点 线性表的应用 解析 根据算法，可知其为求线性表的和的运算。阅读下列算法，回答问题。void ex(SeqStack *S)int A80, i, n;n=0;while(!empty(S)An=pop(S);n+;for(i=0; i v n; i+)push(S, Ai); (分数： 5.00 )(1) .当S=(a , b, c, d)时，执行上述程序后其为什么 ？(分数：2.50 )正确答案： (S=(d ， c， b， a) 。) 解析：(2) . 简述该算法的功能。(分数： 2.50)正确答案： ( 该算法的功能是通过一个数组将一个栈中的所有元素逆置存放。 )解析： 考点 栈的操作的应用 解析 通过程序可以判断出其为通过一个数组将一个栈中的所有元素逆置 存放的算法。五、B 算