数据结构自考题-1
(总分：103.00，做题时间：90分钟)
一、单项选择题(总题数：14，分数：28.00)
1.设串s1="Data Structures、with Java"，s2="it"，则子串定位函数index(s1，s2)的值为 ( )
A．15 B．16 C．17 D．18


（分数：2.00）
 A.
 B.
 C. √
 D.
解析：
2.下列说法中正确的是( )
A．任何一棵二叉树中至少有一个结点的度为2
B．任何一棵二叉树中的每个结点的度为2
C．任何一棵二叉树中的度肯定等于2
D．任何一棵二叉树中的度可以小于2


（分数：2.00）
 A.
 B.
 C.
 D. √
解析：
3.设矩阵A(aij,1≤i,j≤i0)的元素满足：
aij≠0(i≥j,1≤i,j≤10)
aij=O(i＜j,1≤i,j≤10)
现将A的所有非0元素以行序为主序存放在首地址为2000的存储区域中，每个元素占4个单元，则元素[9,5]的首地址为( )
A．2160 B．2164 C．2336 D．2340


（分数：2.00）
 A. √
 B.
 C.
 D.
解析：
4.下列说法中正确的是( )
A．二叉树中任何一个结点的度都为2
B．二叉树的度为2
C．任何一棵二叉树中至少有一个结点的度为2
D．一棵二叉树的度可以小于2


（分数：2.00）
 A.
 B.
 C.
 D. √
解析：
5.下面的程序在执行时，S语句共被执行了( )次。
i=1;
while(i＜=n)
for(j=i;j＜n;j++)
S ;

i=i+1;




（分数：2.00）
 A. √
 B.
 C.
 D.
解析：
6.若进栈序列为1,2,3,4,5,6，且进栈和出栈可以穿插进行，则可能出现的出栈序列为( )
A．3,2,6,1,4,5 B．3,4,2,1,6,5 C．1,2,5,3,4,6 D．5,6,4,2,3,1


（分数：2.00）
 A.
 B. √
 C.
 D.
解析：
7.在一个具有N个顶点的无向完全图中，包含的边的总数是( )
A．N(N-1)/2 B．N(N-1) C．N(N+1) D．N(N+1)/2


（分数：2.00）
 A. √
 B.
 C.
 D.
解析：
8.在计算机内实现递归算法时所需的辅助数据结构是 ( )
A．栈 B．队列 C．树 D．图


（分数：2.00）
 A. √
 B.
 C.
 D.
解析：
9.假设以数组A[n]存放循环队列的元素，其头指针front指向队头元素的前一个位置、尾指针r
ear指向队尾元素所在的存储位置，则在少用一个元素空间的前提下，队列满的判定条件为 ( )
A．rear==front B．(front+1)%n==rear
C．rear+1==front D．(rear+1)%n==front


（分数：2.00）
 A.
 B.
 C.
 D. √
解析：[解析] 在循环队列中，在少用一个元素空间的前提下，可约定入队前，测试尾指针在循环意义下加1后是否等于头指针，若相等则认为队满。
10.考虑下列四种排序方法，在排序过程中，关键码比较的次数与记录的初始排列顺序无关的是( )
A．直接插入排序和快速排序 B．快速排序和归并排序
C．直接选择排序和归并排序 D．直接插入排序和归并排序


（分数：2.00）
 A.
 B.
 C. √
 D.
解析：
11.C语言数组Data[m+1]作为循环队列SQ的存储空间，front为队头指针，rear为队尾指针，则执行出队操作的语句为( )
A．front=front+1 B．front=(front+1)%m
C．rear=(rear+1)%m D．front=(front+1)%(m+1)


（分数：2.00）
 A.
 B.
 C.
 D. √
解析：
12.考虑下列四种排序方法，在排序过程中，关键码比较的次数与记录的初始排列顺序无关的是( )
A．直接插入排序和快速排序 B．快速排序和归并排序
C．直接选择排序和归并排序 D．直接插入排序和归并排序


（分数：2.00）
 A.
 B.
 C. √
 D.
解析：
13.线索二叉树是一种( )结构。
A．物理 B．逻辑 C．存储 D．线性


（分数：2.00）
 A. √
 B.
 C.
 D.
解析：
14.在单链表中，删除p所指结点的直接后继的操作是 ( )
A．p—＞next=p—＞next—＞next;
B．p=p—＞next;p—＞next=p—＞next—＞next;
C．p—＞next=p—＞next;
D．p=p—＞next—＞next;


（分数：2.00）
 A. √
 B.
 C.
 D.
解析：
二、填空题(总题数：10，分数：20.00)
15. 1查法的平均查长度与元素个数n无关。


（分数：2.00）
填空项1:__________________ （正确答案：散列表）
解析：
16.设树T的度为4，其中度为1、2、3和4的结点个数分别是4、2、1和1，则T中叶子结点的个数是： 1。


（分数：2.00）
填空项1:__________________ （正确答案：8个）
解析：
17.N个顶点的连通图，至少有 1条边。


（分数：2.00）
填空项1:__________________ （正确答案：N—1）
解析：
18.ISAM文件由主索引、______、______和主文件组成。


（分数：2.00）
填空项1:__________________ （正确答案：柱面索引 磁道索引）
解析：
19.在分块查法中，首先查 1，然后再查相应的 2。


（分数：2.00）
填空项1:__________________ （正确答案：索引表块）
解析：
20.如果我们定义一个长度为N的串空间，则它最多能放 1个字符。


（分数：2.00）
填空项1:__________________ （正确答案：N—1）
解析：
21.若对关键字序列(43,02,80,48,26,57,15,73,21,24,66)进行一趟增量为3的希尔排序，则得到的结果为 1。


（分数：2.00）
填空项1:__________________ （正确答案：15,02,21,24,26,57,43,66,80,48,73）
解析：
22.内部排序的方法可以分为五类：______、______、______、______、______。


（分数：2.00）
填空项1:__________________ （正确答案：插入排序 选择排序 交换排序 归并排序 分配排序）
解析：
23.广义表的深度是指 1。


（分数：2.00）
填空项1:__________________ （正确答案：广义表展开后所含括号的最大层数）
解析：
24.产生冲突现象的两个关键字称为该散列函数的 1。


（分数：2.00）
填空项1:__________________ （正确答案：同义词）
解析：
三、解答题(总题数：4，分数：20.00)
25.已知有一关键字序列为505,94,512,61,908,170,897,275,653,463)，如果我们采用快速法对此序列进行排序(按照升序排序)，请给出每一趟排序的结果。


（分数：5.00）
__________________________________________________________________________________________
正确答案：(快速排序采用分治法进行，其基本思想如下：将原问题分解成为若干个规模更小但结构和原问题相似的子问题，递归地解这些子问题，然后将这些子问题的解的组合为原问题的解，根据上述思想，我们可以得到如下快速排序的各趟结果如下：
初始：505,94,512,61,908,170,897,275,653,432
第1趟：[462,94,295,61,170]505[897,908,653,512]
第2趟：[170,94,295,61]462,505[897,908,653,512] 二叉树公式
第3趟：[61,94]170[275]462,505[897,908,653,512]
第4趟：61[94]170[275]462,505[897,908,653,512]
第5趟：61,94,170,[275],462,505[897,908,653,512]
第6趟：61,94,170,275,462,505[897,908,653,512]
第7趟：61,94,170,275,462,505[512,653]897[908]
第8趟：61,94,170,275,462,505,512[653]897[908]
第9趟：61,94,170,275,462,505,512,653,897[908]
第10趟：61,94,170,275,462,505,512,653,897,908)

版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。