本文目录索引

• 1，关于自考《数据结构导论》的疑问！同比C语言(分不多全给，请不啬指点）
• 2，自考中的数据结构导论与高级语言那个更容易考啊？
• 3，自考 学数据结构导论和数据库及其应用都要什么基础
• 4，求试卷和答案,2010年10月自学考试数据结构导论的.
• 5，数据结构导论里的几道题目

1，关于自考《数据结构导论》的疑问！同比C语言(分不多全给，请不啬指点）

你得明确学习的目的，你现在学会数据结构并不能编程，学数据结构好比学建筑的，学设计房屋，而编程好比该房，两者之间还是有一个过度的，所以你现在因为无法编程，或无法将其与编程联系起来而感到很吃力，这是在学习上的误区，要想学好数据结构，要弄明白程序运行的过程（c是面向过成的），多和其他的学员交流，一般情况下，把数据结构学的非常好后都不一定会编程，若你真要严格要求自己，我建议你把c中结构体及链表那块的知识弄懂，要非常懂，还有就是地址和指针那块的知识弄懂就ok了，
再就是看看教学视频，在网上搜一些现成的程序，拷过去运行一下，改改其中的代码，你一下就明白了，
也就是在读程序中领悟算法的实现过程

2，自考中的数据结构导论与高级语言那个更容易考啊？

我朋友是学计算机的，我问他了，他说这两科有很大区别，但从实用的角度讲，数据结构好一些，他建议学这个，因为只要静下心来两个月的时间足够了。高级语言需要语言类基础，可你说没有基础，建议你别考这个了，时间可能来不及了。这只是个建议，具体的还得你自己决定，但不管考哪门，不用心看书肯定不行。所以还是抓紧时间看书吧！

3，自考 学数据结构导论和数据库及其应用都要什么基础

这两本我都学过.

自考的数据结构导论是用C语言来描述的,需要有对应课程高级程序语言(一)的基础,也就是要懂的C..如果有数学基础更好,没有也可以硬着头皮啃,这本比较难.

至于数据库及其应用是作为数据结构导论的后继课程的..不过这门比较简单,不会数据结构问题也不大,也不需要任何的语言基础..用的是access数据库.

兄弟加油!.

4，求试卷和答案,2010年10月自学考试数据结构导论的.

全国2010年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<n）
{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］;
试写出开散列表上的查找算法。

5，数据结构导论里的几道题目

第一题:C
数据的逻辑结构分为：线性结构和非线性结构
数据的存储结构分为：顺序存储结构和链式存储结构

第二题：B

第四题：C我个人可以利用二路归并的排序方法，利用特殊情况L1(low1,high1),L2(low2,high2),且low2>hign1。

第七题：A
若A是一个m*n的二维数组，数组下标从零开始，以列为主序存储，则address(A[i,j])=adderss(A[0,0])+(j*n+i)*L其中L为一个元素所占的存储空间
则在此题目中address(A[5,5])=1000+(5*6+5)*5=1000+175=1175

若以行为主序存储，则adderss(A[i,j])=adderss(A[0,0])+(i*m+j)*L
在此题目中address(A[5,5])=1000+(5*6+5)*5=1000+175=1175
即在此题目中以行为主序存储和以列为主序存储，最终结果相同。

第九题：B
完全二叉树是指除最后一层外，每一层上的结点数都达到最大值，在最后一层上指缺少右边的若干结点。根据定义可以先求出深度为H-1的满二叉树的结点个数为2^（H-1）-1,则继而可以得到深度为H的满二叉树的结点最少为2^(H-1)。


第十题：D
无向图的极大连通子图就叫做连通分量。问题关键在于n个结点的无向图有很多种，所以连通分量数不能确定。

第十一题：D

第十二题：D
二叉排序树的定义为：左子树上的所有结点值均小于根节点的值，右子数上的值均不小于根结点的值。
又因为中序遍历的循序是：先访问左结点，再访问根结点，最后访问右结点。
根据以上两个原则可以得到.对一棵二叉排序树采用中根遍历进行输出的数据一定是递增序列。

第二十二题：
一棵具有n个结点的树，所有非终端结点的度均为k，则此二叉树为K叉树，这棵树只右度为K和度为0的结点，设度为K的结点数为a，度为0的结点数为b，则n=a+b。又设二叉树的所有分支为m,则m=k*a,同样可以得到n=m+1。
综上可以得到b=[(n-1)*(k-1)/k-1]。

以上是我自己对以上题目的解答，如果有什么不妥之处请与我联系继续探讨。