自学考试数据结构试题及答案.pdf

《自学考试数据结构试题及答案.pdf》由会员分享，可在线阅读，更多相关《自学考试数据结构试题及答案.pdf（16页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、自学考试数据结构试题及答案 一、单选题（共 50 题，共 100 分）1.串匹配算法的本质是()。A.串复制 B.串比较 C.子串定位 D.子串链接 ABCD 正确答案：C 2.设有一个 10 阶的对称矩阵 A，采用行优先压缩存储方式，a11 为第一个元素，其存储地址为 1，每个元素占一个字节空间，则 a85 的地址为()。A.13 B.18 C.33 D.40 ABCD 正确答案：C 3.若一棵二叉树的前序遍历序列与后序遍历序列相同，则该二叉树可能的形状是()。A.树中没有度为 2 的结点 B.树中只有一个根结点 C.树中非叶结点均只有左子树 D.树中非叶结点均只有右子树 ABCD 正确答案

2、：B 4.若根结点的层数为 1，则具有 n 个结点的二叉树的最大高度是()。A.n B.LIogn2n_I C.LIogn2n_I+1 D.n/2 ABCD 正确答案：A 5.在图 G 中求两个结点之间的最短路径可以采用的算法是()。A.迪杰斯特拉（Dijkstra）算法 B.克鲁斯卡尔（Kruskal）算法 C.普里姆(Prim)算法 D.广度优先遍历(BFS)算法 ABCD 正确答案：A 6.如果在排序过程中不改变关键字相同元素的相对位置，则认为该排序方法是()。A.不稳定的 B.稳定的 C.基于交换的 D.基于选择的 ABCD 正确答案：B 7.设有一组关键字(19,14,23,1，6，

3、20,4，27,5，11,10,9)，用散列函数 H(key)=key%13 构造散列表，用拉链法解决冲突，散列地址为 1 的链中记录个数为()。A.1 B.2 C.3 D.4 ABCD 正确答案：C 8.若需高效地查询多关键字文件，可以采用的文件组织方式为()。A.顺序文件 B.索引文件 C.散列文件 D.倒排文件 ABCD 正确答案：D 9.在数据的逻辑结构中，树结构和图结构都是()。A.非线性结构 B.线性结构 C.动态结构 D.静态结构 ABCD 正确答案：A 10.在一个长度为 n 的顺序表中插入一个元素的算法的时间复杂度为()。A.O（1）B.（log n）C.O（n）D.O（n）

4、ABCD 正确答案：C 11.设栈的初始状态为空，入栈序列为 1，2，3，4，5，6，若出栈序列为 2，4，3，6，5，1，则操作过程中栈中元素个数最多时为()。A.2 个 B.3 个 C.4 个 D.6 个 ABCD 正确答案：B 本题解析：因为先 2 是 2 到 4 有 3 个栈以此类推 12.指针 p1 和 p2 分别指向两个无头结点的非空单循环链表中的尾结点，要将两个链表链接成一个新的单循环链表，应执行的操作为()。A.p1 next=p2 next;p2 next=p1 next B.p2 next=p1 next;p1 next=p2 next C.p=p2 next;p1 nex

5、t=p;p2 next=p1 next D.p=p1 next;p1 next=p2 next；p2 next=p ABCD 正确答案：D 13.队列的特点是()。A.允许在表的任何位置进行插入和删除 B.只允许在表的一端进行插入和删除 C.允许在表的两端进行插入和删除 D.只允许在表的一端进行插入，在另一端进行删除 ABCD 正确答案：D 14.广义表 A=(a,B,(a,B,(a,B,)的长度为()。A.1 B.2 C.3 D.无限值 ABCD 正确答案：C 15.已知 1012 的二维数组 A，按“行优先顺序”存储，每个元素占 1 个存储单元，已知 A11的存储地址为 420，则 A55

6、的存储地址为()。A.470 B.471 C.472 D.473 ABCD 正确答案：C 16.具有线性结构的数据结构是()线性结构有：顺序表、栈和队列、串。A.树 B.图 C.栈和队列 D.广义表 ABCD 正确答案：C 17.将长度为 n 的单链表连接在长度为 m 的单链表之后，其算法的时间复杂度为()。A.O(1)B.O(m)C.O(n)D.O(m+n)ABCD 正确答案：B 18.在带头结点的双向循环链表中插入一个新结点，需要修改的指针域数量是()。A.2 个 B.3 个 C.4 个 D.6 个 ABCD 正确答案：C 19.假设以数组 A60存放循环队列的元素，其头指针是 front

7、=47，当前队列有 50 个元素，则队列的尾指针值为()。A.3 B.37 C.50 D.97 ABCD 正确答案：B 20.若栈采用链式存储结构，则下列说法中正确的是()。A.需要判断栈满且需要判断栈空 B.不需要判断栈满但需要判断栈空 C.需要判断栈满但不需要判断栈空 D.不需要判断栈满也不需要判断栈空 ABCD 正确答案：B 21.若串 str=”Software”，其子串的数目是()。A.8 B.9 C.36 D.37 ABCD 正确答案：D 22.设有一个 10 阶的下三角矩阵 A，采用行优先压缩存储方式，all 为第一个元素，其存储地址为 1000，每个元素占一个地址单元，则 a8

8、5 的地址为()。A.1012 B.1017 C.1032 D.1039 ABCD 正确答案：C 23.允许结点共享的广义表称为()。A.纯表 B.线性表 C.递归表 D.再入表 ABCD 正确答案：D 24.下列数据结构中，不属于二叉树的是()。A.B 树 B 树是一种平衡的多叉树 B.AVL 树 AVL 树是自平衡二叉查找树 C.二叉排序树 D.哈夫曼树 哈夫曼树是最优二叉树 ABCD 正确答案：A 25.下列排序算法中不稳定的是()。A.快速排序 B.归并排序 C.冒泡排序 D.直接插入排序 ABCD 正确答案：A 26.采用 ISAM 组织文件的方式属于()。A.链组织 B.顺序组织

9、C.散列组织 D.索引组织 ABCD 正确答案：D 27.数据的四种存储结构是()。A.顺序存储结构、链接存储结构、索引存储结构和散列存储结构 B.线性存储结构、非线性存储结构、树型存储结构和图型存储结构 C.集合存储结构、一对一存储结构、一对多存储结构和多对多存储结构 D.顺序存储结构、树型存储结构、图型存储结构和散列存储结构 ABCD 正确答案：A 28.若对某线性表最常用的操作是在最后一个结点之后插入一个新结点或删除最后一个结点，要使操作时间最少，下列选项中，应选择的存储结构是()。A.无头结点的单向链表 B.带头结点的单向链表 C.带头结点的双循环链表 D.带头结点的单循环链表 ABC

10、D 正确答案：C 29.若带头结点的单链表的头指针为 head，则判断链表是否为空的条件是()。A.head=NULL B.head-next=NULL C.head!=NULL D.head-next!=head ABCD 正确答案：B 30.若元素的入栈顺序为 1，2，3.，n，如果第 2 个出栈的元素是 n，则输出的第 i(1=inext=r；q-next=r-next；r-next=q B.p-next=r；r-next=q；q-next=r-next C.r-next=q；q-next=r-next；p-next=r D.r-next=q；p-next=r；q-next=r-next

11、 ABCD 正确答案：A 38.若进栈次序为 a，b，c，且进栈和出栈可以穿插进行，则可能出现的含 3 个元素的出栈序列个数是()。A.3 B.5 C.6 D.7 ABCD 正确答案：B 39.假设以数组 An存放循环队列的元素，其头指针 front 指向队头元素的前一个位置、尾指针rear 指向队尾元素所在的存储位置，则在少用一个元素空间的前提下，队列满的判定条件为()。A.rear=front B.(front+1)n=rear C.rear+1=front D.(rear+1)n=front ABCD 正确答案：D 40.二维数组 A106采用行优先的存储方法，若每个元素占 4 个存储单

12、元，已知元素 A34的存储地址为 1000，则元素 A43的存储地址为()。A.1020 B.1024 C.1036 D.1036 ABCD 正确答案：A 41.已知森林 F=T1，T2，T3，T4，T5，各棵树 Ti(i=1，2，3，4，5)中所含结点的个数分别为 7，3，5，1，2，则与 F 对应的二叉树的右子树中的结点个数为()。A.2 B.3 C.8 D.11 ABCD 正确答案：D 42.对关键字序列(6，1，4，3，7，2，8，5)进行快速排序时，以第 1 个元素为基准的一次划分的结果为()。A.(5，1，4，3，6，2，8，7)B.(5，1，4，3，2，6，7，8)C.(5，1，

13、4，3，2，6，8，7)D.(8，7，6，5，4，3，2，1)ABCD 正确答案：C 43.分块查找方法将表分为多块，并要求()。A.块内有序 B.块间有序 C.各块等长 D.链式存储 ABCD 正确答案：B 44.便于进行布尔查询的文件组织方式是()。A.顺序文件 B.索引文件 C.散列文件 D.多关键字文件 ABCD 正确答案：D 45.若一个算法的时间复杂度用 T(n)表示，其中 n 的含义是()。A.问题规模 B.语句条数 C.循环层数 D.函数数量 ABCD 正确答案：A 46.下列程序段的时间复杂度为()。A.O(1)B.O(n)C.O(2n)D.O(n 22)ABCD 正确答案：

14、D 47.假设某个带头结点的单链表的头指针为 head，则判定该表为空表的条件是()。A.head=NULL B.head-next=NULL C.head!=NULL D.head-next=head ABCD 正确答案：B 48.栈是一种操作受限的线性结构，其操作的主要特征是()。A.先进先出 B.后进先出 C.进优于出 D.出优于进 ABCD 正确答案：B 49.假设以数组 An存放循环队列的元素，其头、尾指针分别为 front 和 rear。若设定尾指针指向队列中的队尾元素，头指针指向队列中队头元素的前一个位置，则当前存于队列中的元素个数为()。A.(rear-front-1)n B.(rear-front)n C.(front-rear+1)n D.(rear-front+n)n ABCD 正确答案：B 50.判断两个串大小的基本准则是()。A.两个串长度的大小 B.两个串中首字符的大小 C.两个串中大写字母的多少 D.对应的第一个不等字符的大小 ABCD 正确答案：D