数据结构自学考试

一 单项选择题(本大题共 小题 每小题 分 共 分)

在每小题列出的四个备选项中只有一个是符合题目要求的 请将其代码填写在题后的括号内 错选 多选或未选均无分

在数据结构中 数据的逻辑结构可以分成()

A 内部结构和外部结构 B 线性结构和非线性结构

C 紧凑结构和非紧揍结构 D 动态结构和静态结构

在以单链表为存储结构的线性表中 数据元素之间的逻辑关系用()

A 数据元素的相邻地址表示 B 数据元素在表中的序号表示

C 指向后继元素的指针表示 D 数据元素的值表示

设 p 指向单链表中的一个结点 s 指向待插入的结点 则下述程序段的功能是()

s > next = p > next; p > next = s;

t = p > data; p > data = s > data; s >data = t;

A 结点 *p 与结点 *s 的数据域互换

B 在 p 所指结点的元素之前插入元素

C 在 p 所指结点的元素之后插入元素

D 在结点 *p 之前插入结点 *s

栈和队列都是()

A 限制存取位置的线性结构 B 顺序存储的线性结构

C 链式存储的线性结构 D 限制存取位置的非线性结构

若数组 s[ n ] 为两个栈 s 和 s 的共用存储空间 且仅当 s[ n ] 全满时 各栈才不能进行进栈操作 则为这两个栈分配空间的最佳方案是 s 和 s 的栈顶指针的初值分别为()

A 和 n+ B 和 n/

C 和 n D 和 n+

执行下列程序段后 串 X 的值为()

S= 〞 abcdefgh 〞 ; T= 〞 xyzw 〞 ;

substr (X S strlen(T));

substr (Y S stelen(T) );

strcat (X Y);

A 〞 cdefgh 〞 B 〞 cdxyzw 〞

C 〞 cdefxy 〞 D 〞 cdefef 〞

多维数组之所以有行优先顺序和列优先顺序两种存储方式是因为()

A 数组的元素处在行和列两个关系中 B 数组的元素必须从左到右顺序排列

C 数组的元素之间存在次序关系 D 数组是多维结构 内存是一维结构

从广义表 LS =( (p q) r s )中分解出原子 q 的运算是()

A tail (head (LS)) B head (tail (head (LS)))

C head (tail (LS)) D tail (tail (head (LS)))

在具有 n 个叶子结点的严格二叉树中 结点总数为()

A n+ B n

C n D n

若 是有向图的一条边 则称()

A v i 邻接于 v j B v j 邻接于 v i

C v i 和 v j 相互邻接 D v i 与 v j 不相邻接

在一个带权连通图 G 中 权值最小的边一定包含在 G 的()

A 最小生成树中 B 深度优先生成树中

C 广度优先生成树中 D 深度优先生成森林中

当在二叉排序树中插入一个新结点时 若树中不存在与待插入结点的关键字相同的结点 且新结点的关键字小于根结点的关键字 则新结点将成为()

A 左子树的叶子结点 B 左子树的分支结点

C 右子树的叶子结点 D 右子树的分支结点

希尔排序的增量序列必须是()

A 递增的 B 随机的

C 递减的 D 非递减的

如果在排序过程中 每次均将一个待排序的记录按关键字大小加入到前面已经有序的子表中的适当位置 则该排序方法称为()

A 插入排序 B 归并排序

C 冒泡排序 D 堆排序

设置溢出区的文件是()

A 索引非顺序文件 B ISAM 文件

C VSAM 文件 D 顺序文件

二 填空题(本大题共 小题 每小题 分 共 分)

请在每小题的空格中填上正确答案 错填 不填均无分

下列程序段的时间复杂度为 ________________

product = ;

for (i = n;i> ; i )

for (j = i+ ; j

product *=j;

17 .已知指针 p 指向单链表中某个结点，则语句 p -> next =p -> next -> next 的作用是 ________________ 。WiNGwit.

18 .假设元素只能按 a,b,c,d 的顺序依次进栈，且得到的出栈序列中的第一个元素为 c ，则可能得到的出栈序列为 ________________ ，不可能得到的出栈序列为 ________________ 。

19 .若链串结点中的指针占 4 个字节，每个字符占 1 个字节，则结点大小为 2 的链串的存储密度为 ________________ 。

20 .右图表示的广义表为 ________________ 。

21 .若一棵满三叉树中含有 121 个结点，则该

树的深度为 ________________ 。

22 .若以邻接矩阵表示有向图，则邻接矩阵上

第 i 行中非零元素的个数即为顶点 v i 的 ________________ 。

23 .若希望只进行 8 趟排序便能在 4800 个元素中找出其中值最小的 8 个元素，并且要求排序过程中所进行的关键字比较次数尽可能少，则应该选用 ________________ 排序方法。

24 .在含 20 个关键字的 3 阶 B 树( 2 - 3 树)上查找一个关键字，至多需要访问 ___________ 次外存。

25 .文件上的两类主要操作为 ________________ 和 ________________ 。

三、解答题(本大题共 4 小题，每小题 5 分，共 20 分)

26 .设栈 S1 的入栈序列为 1 2 3 4 (每个数字为 13 个元素)，则不可能得到出栈序列 3142 。但可通过增设栈 S2 来实现。例如，按下图中的箭头指示，依次经过栈 S1 和 S2 ，便可得到序列 3 1 4 2 。

如果用 H1 和 H2 分别表示栈 S1 和 S2 的进栈操作，用 P1 和 P2 分别表示两个栈的出栈操作，则得到 3 1 4 2 的一个操作步骤为

H1 ， H1 ， H1 ， P1 ， H2 ， P2 ， P1 ， H2 ， P1 ， H2 ， P2 ， H1 ， P1 ， H2 ， P2 ， P2

请仿照上例写出利用两个栈从 1 2 3 4 得到 4 1 3 2 的操作步骤。

27 .已知树如右图所示，

( 1 )写出该树的后序序列;

( 2 )画出由该树转换得到的二叉树。

28 .为关键字( 17 ， 33 ， 31 ， 40 ， 48 )构造一个长度为 7 的散列表，设散列函数为 h(key)=key%7, 用开放定址法解决冲突的探查序列是

hi = (h(key) + i(key%5+1))%7 0 ≤ i ≤ 6

( 1 )画出构造所得的散列表;

( 2 )求出在等概率情况下查找成功时的平均查找长度。

29 .已知 R [ 1..8 ]中的元素依次为( 12 ， 5 ， 9 ， 20 ， 6 ， 31 ， 24 ， 27 )，写出按算法 MergeSortDC 对 R 进行自顶向下的二路归并排序过程中，前 5 次调用函数 Merge(R, low, mid, high) 时参数 low, mid 和 high 的值。

void MergeSortDC (int R[], int low, int mid, int high )

{

int mid;

if (low

{

mid = (low +high)/2;

MergeSortDC (R, low, mid);

MergeSortDC (R, mid+1, high);

Merge (R, low, mid, high);

}

} // MergeSortDC

( 1 )第一次调用时的参数值;

( 2 )第二次调用时的参数值;

( 3 )第三次调用时的参数值;

( 4 )第四次调用时的参数值;

( 5 )第五次调用时的参数值;

四、算法阅读题(本大题共 4 小题，每小题 5 分，共 20 分)

30 .下列函数的功能是，对以带头结点的单链表作为存储结构的两个递增有序表(表中不存在值相同的数据元素)进行如下操作：将所有在 Lb 表中存在而 La 表中不存在的结点插入到 La 中，其中 La 和 Lb 分别为两个链表的头指针。请在空缺处填入合适内容，使其成为一个完整的算法。

void union (LinkList La, LinkList Lb)

{

// 本算法的功能是将所有 Lb 表中存在而 La 表中不存在的结点插入到 La 表中

LinkList pre = La, q;

LinkList pa = La -> next;

LinkList pb = Lb -> next;

free (Lb);

while (pa && pd)

{

if (pa -> data data)

{ pre = pa; pa = pa -> next;}

else if (pa -> data > pb ->data)

{

(1) ;

pre = pb;

pb = pb -> next;

(2) ;

}

else

{

q = pb; pb = pb -> next; free (q);

}

}

if (pb)

(3) ;

}

(1)

(2)

(3)

【免费获取学历提升方案和复习资料：https://www.jxjyw.com/tg/?bdlk】自考本科计算机专业的考试科目有计算机操作系统、软件工程、操作系统、计算机应用与技术、概率论、数据库及其应用、数据库系统原理、数据结构、线性代数等。自考本科计算机考试科目有哪些1、必考科目概率论与数理统计(二)、高等数学(工本)、软件工程、计算机及应用毕业设计(实践+考核)、数据库系统原理、数据结构、操作系统、离散数学、英语(二);中国近现代史纲要、C++程序设计、计算机系统结构、计算机及应用课程实验(二)(实践+考核)、计算机网络原理、Java语言程序设计(一)、马原等。2、加考科目计算机组成原理、电子技术基础(三)(笔试+实践考核)、高级语言程序设计(一)(笔试+实践考核)、普通逻辑等。自学考试本科毕业条件是什么1、考完本专业考试计划所规定的理论课程且考试成绩合格。2、完成该专业所规定的实践性环节课程考核，并取得合格成绩。3、思想品德经鉴定符合要求。4、办理本科毕业证书者，必须具有国家承认学历的专科及以上毕业证书。自考本科计算机专业的就业方向有哪些自考本科计算机专业的毕业生们主要面向商业、贸易、金融、网络等企业，从事网络应用、硬件组装与维修、软件开发、系统维护、信息统计分析与处理、数据库系统与应用、管理学基础、网站设计与维护、电子商务等工作，这类专业毕业人员拥有广泛的选择权，能够慢慢挑选一个适合自己长远发展的行业。报考考试有疑问、不知道如何考点内容、不清楚报考考试当地政策，点击底部咨询猎考网，免费领取复习资料：