如何提升数据构造课程在自学考试中的经过率

数据构造 相当难，不建议读自考，你可以思索 读开放，开放的话是有答案的，文凭也要好拿一些，假如 你报读了，建议置换一下其他科目。15

买本数据构造 的标题 本人 做5

做开发那几个数据构造 还是要会吧；一门言语 也是基础；复杂 的话当然是java复杂 啊3

数据构造 试卷(98年上半年北京市)

一、 单项选择题（在每小题的四个备选答案中选出一个正确的答案，并将其号码填在题干后的号码内，每小题2分，共10分）

1.一个栈的输出 序列为1，2，3，4，下面哪一个序列不可能是这个栈的输入 序列？（ ） A. 1，3，2，4 B. 2，3，4，1 C. 4，3，1，2 D. 3，4，2，1

2.下列排序办法 中，哪一种办法 的比较次数与纪录的初始陈列 形态 无关？（ ） A. 直接插进 排序 B. 起泡排序 C. 疾速 排序 D. 直接选择排序

3.对n个记载 的文件进行二路归并排序，总的时间代价为 A. O（nlog2n） B. O（n2） C. O（log2n） D. O（n）

4.若一棵二叉树具有10个度为2的结点，则该二叉树的度为0的结点个数是（ ） A. 9 B. 11 C. 12 D. 不确定

5.下面关于B树和B+树的叙说 中，不正确的是 A. B树和B+树都是均衡 的多分树 B. B树和B+树都是可用于文件的索引构造 C. B树和B+树都能有效地支持顺序检索 D. B树和B+树都能有效地支持随机检索

二、 填空题（每空2分，共20分）

1.从逻辑构造 看，线性表是典型的 ，树是典型的 。

2.设有二维数组A[0..9,0..19]，其每个元素占两个字节，第一个元素的存储地址为100，若按行优先顺序存储，则元素A[6,6]的存储地址为 ，按列优顺序存储，元素A[6,6]的存储地址为 。

3.若按层次顺序将一棵有n个结点的完全二叉树的一切 结点从1到n编号，那么当i为 且小于n时，结点I的右兄弟是结点 ，否则结点i没有右兄弟。

4.求具有最小带权外部途径 长度的扩大 二叉树的算法称为 算法。堆排序中建堆的办法 称作 。

5.6阶B树中，每个结点至少 包括 个关键码，除根和叶结点外，每个结点至多 包括 个关键码。

三、 简答题（每小题6分，共18分）

1.请简述散列函数在散列法存储中的作用，并举出一个散列函数的例子。

2.请简述散列法存储中处置 碰撞（抵触 ）的两类基本办法 。

3.请简述负载因子的定义，为什么说负载因子是散列法存储的一个重要参数？

四、 求解下列难题 （每小题6分，共30分）

1.设待排序文件的关键码为（512,275,908,677,503,765,612,897,154,170）以第一元素为分界元素进行疾速 排序（按关键码值递增顺序），请给出一趟扫描后的结果。

2.请画出下面的树所对应的二叉树。

3.从一棵空的二叉排序树开始，将以下关键码值顺次 插进 ：25,13,15,31,7,20,37，请画出插进 全部完成后的二叉排序树。

4.请画出下面带权图的一棵最小生成树。

5.关于 下面的稀疏矩阵

1）画出其三元组法存储表示。 2）画出其行—列法（十字链表法）存储表示。 五、 算法题（6分） 有一个链接方式存储的线性表，表中每个结点包括两个指针，其结点用PASCAL言语 描绘 如下： TYPE pointer=↑node; node=RECORD infdatatype; link1,link2:pointer END; 其中link1是指向结点的下一个结点的指针，link2是指向结点的前一个结点的指针,如图所示。 p和q都是pointer类型的变量，现要将q所指的新结点插进 表中p所指结点的前面（阐明 ：p所指的不是链表的第一个结点）。请用PASCAL语句写出该插进 的关键步骤。（部门槛 写完好 的算法，只需 求用几个语句写出关键步骤。） 六、 算法填空和剖析 （共16分） 下面是用PASCAL言语 编写的二分值插进 排序算法，该算法对排序码为整数的线性表进行升序排序。 TYPE node=RECORD key:integer; infdatatype End; list=ARRAY[1..max] OF node; PROCEDURE binarysort (VAR R: list; n: integer); VAR temp :node ; low,m,high,I,j: integer; BEGIN nteger; BEGIN nteger; BEGIN nteger; BEGIN FOR I:=2 TO n DO BEGIN temp := R[ i ]; low :=1; high := i-1; WHILE ① DO BEGIN m :=(low+high) DIV 2; IF ② THEN high :=m-1 ELSE ③ END; FOR j := i-1 DOWNTO ④ DO R[j+1] := R[j]; ⑤ END; END; 1.请将算法的空缺处应填入的正确内容写在下面。（10分） ① ② ③ ④ ⑤

2.设待排序的记载 数n=7，当排序码的初始陈列 顺序辨别 为（15,25,35,45,55,65,75）和（75,65,55,45,35,25,15）时，请说出排序进程 中对排序码所进行的总的比较次数辨别 是多少？（假定算法中取中项的整数除法采用小数截断的办法 。）（6分）这是关于 如何提升 数据构造 课程在自学考试中的经过 率的解答。2

全国2019年10月高等教育自学考试

数据构造 导论题目

课程代码：02142

一、单项选择题(本大题共15小题，每小题2分，共30分)

在每小题列出的四个备选项中只要 一个是契合 标题 门槛 的，请将其代码填写在题后的括号内。错选、多选或未选均无分。

1．下列描绘 中正确的是( )

A.数据元素是数据的最小单位

B.数据构造 是具有构造 的数据对象

C.数据构造 是指相互之间存在一种或多种特定关系的数据元素的集合

D.算法和顺序 准绳 上没有区别，在讨论数据构造 时两者是通用的

2．归并排序的时间复杂度是( )

A．O（n2）

B.O（nlog2n）

C.O（n）

D.O（log2n）

3．二分查找的时间复杂度是( )

A．O（n2）

B.O（nlog2n）

C.O（n）

D.O（log2n）

4．顺序存储的表中有90000个元素，已按关键字值升序陈列 ，假定 对每个元素进行查找的概率相同，且每个元素的关键字值皆不相同，用顺序查找法查找时，需均匀 比较的次数为( )

A．25000

B.30000

C.45000

D.90000

5．散列文件是一种( )

A．顺序文件

B.索引文件

C.链接文件

D.计算寻址文件

6．两个矩阵A：m×n，B：n×p相乘，其时间复杂度为( )

A．O(n)

B.O(mnp)

C.O(n2)

D.O（mp）

7.常用于函数调用的数据构造 是( )

A.栈

B.队列

C.链表

D.数组

8．二维数组A［n］［m］以列优先顺序存储，数组A中每个元素占用1个字节，A［1］［1］为首元素，其地址为0，则元素A［i］［j］的地址为( )

A.（i-1）×m+(j-1)

B.(j-1)×n+(i-1)

C.(j-1)×n+i

D.j×n+i

9.图的广度优先搜索运用 的数据构造 是( )

A．队列

B.树

C.栈

D.集合

10．序列（21,19,37,5,2）经冒泡排序法由小到大排序，在第一次执行交流 后所得结果为( )

A．(19，21，37，5，2)

B.(21，19，5，37，2)

C.(21，19，37，2，5)

D.(2，21，19，37，5)

11．数据在计算机存储器内表示时，依据 结点的关键字直接计算出该结点的存储地址，这种办法 称为( )

A．索引存储办法

B.顺序存储办法

C.链式存储办法

D.散列存储办法

12．在单链表中，存储每个结点有两个域，一个是数据域，另一个是指针域，指针域指向该结点的( )

A．直接前趋

B.直接后继

C.开始结点

D.终端结点

13．在已知头指针的单链表中，要在其尾部插进 一新结点，其算法所需的时间复杂度为( )

A．O（1）

B.O（log2n）

C.O（n）

D.O（n2）

14．在链队列中执行入队操作，( )

A．需判别队能否 空

B.需判别队能否 满

C.限制在链表头p进行

D.限制在链表尾p进行

15．一整数序列26，59，77，31，51，11，19，42，以二路归并排序从小到大排序，第一阶段的归并结果为( )

A.31，51，11，42，26，77，59，19

B.26，59，31，77，11，51，19，42

C.11，19，26，31，42，59，51，77

D.26，11，19，31，51，59，77，42

二、填空题(本大题共13小题，每小题2分，共26分)

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

16．下列顺序 段的时间复杂度为_______。

i=0；s=0；

while（s

{i++；

s=s+i；

}

17．数据的存储构造 被分为顺序存储构造 、_______、散列存储构造 和索引存储构造 4种。

18．从一个长度为n的顺序表中删除第i个元素（1≤i≤n）时，需向前挪动 _______个元素。

19．在单链表中，插进 一个新结点需修正 _______个指针。

20．在队列构造 中，允许插进 的一端称为_______。

21．稀疏矩阵采用的紧缩 存储办法 是_______。

22．向一个栈顶指针为top的链栈中插进 一个新结点*p时，应执行p->next=top和_______操作。

23．有m个叶结点的哈夫曼树所具有的结点数为_______。

24．在一棵具有n个结点的完全二叉树中，从树根起，自上而下、自左至右地给一切 结点编号。设根结点编号为1。若编号为i的结点有右孩子，那么其右孩子的编号为_______。

25．在一棵树中，_______结点没有前驱结点。

26．一个具有n个顶点的有向完全图的弧数是_______。

27．n个顶点的无向图G用邻接矩阵A［n］［n］存储，其中第i列的一切 元素之和等于顶点Vi的_______。

28．选择排序的均匀 时间复杂度为_______。

三、使用 题(本大题共5小题，每小题6分，共30分)

29．在栈的输出 端元素的输出 顺序为1，2，3，4，5，6，进栈进程 中可以退栈，则退栈时能否排成序列3，2，5，6，4，1和1，5，4，6，2，3，若能，写出进栈、退栈进程 ，若不能，简述理由。（用push（x）表示x进栈，pop(x)表示x退栈）

30．已知一棵二叉树的中根遍历序列为CBEDFAGH，后根遍历序列为CEFDBHGA，画出该二叉树。

31．给定表（15，11，8，20，14，13），试按元素在表中的顺序将它们顺次 插进 一棵初始时为空的二叉排序树，画出插进 完成后的二叉排序树，并判别 该二叉排序树能否 为均衡 二叉排序树，若为非均衡 二叉排序树，将它调整为均衡 二叉排序树。

32．如题32图所示无向图，（1）写出其邻接矩阵；（2）写出三种以顶点A为起点的深度优

先搜索顶点序列。

题32图

33．用冒泡排序法对数据序列（49，38，65，97，76，134，27，49）进行排序，写出排序进程 。并阐明 冒泡排序能否 为固定 排序。

四、算法设计题(本大题共2小题，每小题7分，共14分)

34.编写计算二叉树中叶子结点数目的算法。

35.开散列表的类型定义如下：

typedef struct tagnode

{keytype key;

struct tagnode*next;

}*pointer,node;

typedef pointer openhash［n］;

试写出开散列表上的查找算法。这是关于 如何提升 数据构造 课程在自学考试中的经过 率的解答。10

0人赞 添加讨论(0) 回答 举报

你理论考完后 去主考学校参与 实际操作 考试。到时候有教师 会布置实际操作 作业，通常 是在规则 的时间本人 完成。别担忧 通常 很容易过的。7

这两科不是二选一吧，数据构造 是基础啊，就算不选Java也要学的吧。3