全国2010年1月自考数据结构导论考试试题,答案,笔记

全国2010年1月高等教育自学考试 数据结构导论试题 课程代码：02142

一、单项选择题(本大题共15小题，每小题2分，共30分) 在每小题列出的四个备选项中只有一个是符合题目要求的，请将其代码填写在题后的括号内。错选、多选或未

选均无分。

1.下述文件中适合于磁带存储的是（ A ） A.顺序文件 B.索引文件 C.散列文件 D.多关键字文件

2.某二叉树的后根遍历序列为dabec，中根遍历序列为debac，则先根遍历序列为（ D ）

A.acbed B.becab C.deabc D.cedba

3.含有n个结点的二叉树用二叉链表表示时，空指针域个数为( C ) A.n-1 B.n C.n+1

D.n+2 注：子域为2n个，有n-1个孩子。

4.在一个图中，所有顶点的度数之和与图的边数的比是( C) A.1∶2 B.1∶1 C.2∶1 D.4∶1

5.长度为n的链队列用单循环链表表示，若只设头指针，则出队操作的时间复杂度为( A)

A.O(1)

B.O(1og2n) 二分法注：若只有尾指针，那么入和出都为O(1) C.O(n) （入队） D.O(n2) -冒泡

6.下述几种排序方法中，要求内存量最大的是( C ) A.插入排序 B.快速排序 C.归并排序 D.选择排序

7.对n个不同值进行冒泡排序，在元素无序的情况下比较的次数为( D)

A.n-1 B.n C.n+1 D.n(n-1)／2

8.对线性表进行二分查找时，要求线性表必须( C) A.以顺序方式存储 B.以链式方式存储

C.以顺序方式存储，且结点按关键字有序排列 D.以链接方式存储，且结点按关键字有序排列

9.在表长为n的顺序表上做删除运算，其平均时间复杂度为( B ) A.O(1)

B.O(n) 注：在双向循环链表中，删除最后一个结点 C.O(nlog2n)

D.O(n2) 的时间复杂度为O(1)

10.当利用大小为n 的数组顺序存储一个队列时，该队列的最大容量为

( B )

A.n-2 B.n-1 C.n

D.n+1 11.有关插入排序的叙述，错误的．．．是( C )

A.插入排序在最坏情况下需要O(n 2

)时间B.插入排序在最佳情况可在O(n)时间内完成 C.插入排序平均需要 O(nlog 2n)时间 -----快速排序需要 o （nlog2n ）

D.插入排序的空间复杂度为O(1) 12.有关树的叙述正确的是 ( C )

A.每一个内部结点至少有一个兄弟 B.每一个叶结点均有父结点 C.有的树没有子树

D.每个树至少有一个根结点与一个叶结点。(有且仅有一个结点) 13.循环队列存储在数组元素A[0]至A[m]中，则入队时的操作为

( D )

A.rear=rear+1

B.rear=(rear+1)％(m-1) C.rear=(rear+1)％m D.rear=(rear+1)％(m+1)

14.关于串的的叙述，不正确．．．的是( B )

A.串是字符的有限序列

B.空串是由空格构成的串注：空格串是只包括空格的串，空格串

是有长度的，，而空串没有长度。

C.替换是串的一种重要运算

D.串既可以采用顺序存储，也可以采用链式存储15.对称矩阵 A[N][N]，A[1][1]为首元素，将下三角

(包括对角线)元素以行优先顺序存储到一维数组元素 T[1]至

T[N(N+1)／2]中，则任一上三角元素A[i][j]存于T[k]中，下标k 为(

B )

A .i (i-1)／2+j B. j(j-1)／2+i C .i (j-i)／2+1 D. j(i-1)／2+l 二、填空题(本大题共13小题，每小题 2分，共26分)

请在每小题的空格中填上正确答案。错填、不填均无分。16.下列程序段的时间复杂度为

____O(n 3 )________。

for(i=1；i<=n ；i++) for(j=1；j<=n ；j++) for(k=1；k<=n ；k++) s=i+j+k ；

17.在数据结构中，各个结点按逻辑关系互相缠绕， 任意两个结点可以邻接的结构称为__图状结构__________。 18.在单链表中，存储每个结点有两个域，

一个是数据域，另一个是指针域，指针域指向该结点___直接后继_____的。

注：数据域---前接前趋，指针域 —直接后继

树：是n 各节点的有限集合。1.当n=0时，称为空树。 2.

当n>0时，有且仅有一个根的结点。 19.在栈结构中，允许插入的一端称为

__栈顶__________。

注：队列允许插入的一端叫队尾。20.从一个长度为

n 的顺序表中删除第i 个元素(1≤i ≤n)时，需向前移动n-i__个元素。

注：向后移动 n-i+1个元素。

21.一个栈的输入序列是1，2，3，…，n ，输出序列的第一个元素是n ，则第i 个输出元素为__n-i+1________。

22.循环队列被定义为结构类型，含有三个域：data 、front 和rear ，则循环队列sq 为空的条件是__sq.rear=sq.front__________。

23.一个10阶对称矩阵A ，采用行优先顺序压缩存储 上三角元素，a 00为第一个元素，其存储地址为 0，每个元素占

有1个存储地址空间，则 a 45的地址为_____35_______。 解；k=0+4（2*10-4+1）/2+5-4=35 24.对于一棵满二叉树，若有

m 个叶子，则树中结点数为___2m-1_________。(2m-1又称为哈夫曼树)

25.含有n 个顶点和n-1条边的连通图G 采用____邻接表________存储结构较省空间。

n*(n-1)为有向图，为稀疏矩阵，采用邻接表。n*（n-1）/2为无向图，为对称矩阵，采用邻接矩阵。

26.在图中，第一个顶点和最后一个顶点相同的路径称为__（简单）回路或（简单）环__________。

27.动态查找中两个元素X ，Y 存入同一个散列表时，X 、Y 键值相同，则这种情况称为______冲突_____。

28.堆排序需_____一_______个记录大小的辅助存储空间。 注：1，使用下列公式必要前提是，矩阵式n*n 的，也就是方矩阵。

上三角情况：

当i ≤J 时（前小于等于后）

所求地址=首元素所占地址+i(20n-i+1)/2+j-i 下三角情况：当i ≥j 时

所求地址=首元素所占地址+i(i+1)/2+j

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

29.有一字符串的次序为-3*y+a／y！2，试利用栈将输出次序改变为3y*-ay！2／+，试写出进栈和退栈的操作步骤。(用push(x)表示x进栈，pop(x)表示x退栈)

30.已知一棵二叉树的先根遍历序列为ABCDEGHF，中根遍历序列为CBEDAGFH，画出该二叉树。

答：由题可知，该二叉树为：○A ○B○G ○C○D○H ○E○F

31.题31图中二叉排序树的各结点的值为32～40，标出各结点的值。

40 题31图36 40 37 38 39 32 35 33

34 解题要点： 1.先确定最高分界点左面有几个圈，然后确定分界点。如

本题，分界点左面有4个圈，则

32 33 34 35 36 37 38 39 40—36为分界点

2.以根节点为界，左孩子小于又孩子。

3.若出现连续左孩子，或连续又孩子，注意左孩子连续减小原则，又

孩子连续增大原则。 4.圈的之间差值最小原则。 解题技巧剖析：

1.根据后进先出原则。3.把原始字符串与要改变次序的字符串写成如下格式。

2.写一点，划一点原则。 2.- 3 * y + a ／y ！ 2 ○A 3 y * - a y ！ 2 ／+ ○B

3.例如：enter-> -,3 exit ->3, 此时，剩下-。对应着，把○A里已输入的– 3，删掉。然后把○B标明已产生排序，然

Push(-)push(3)pop(3) 后以此类推。 注：退的时候，从后往前划。

32.下述矩阵表示一个无向网，画出该无向网，并构造出其最小生成树。

1 2 3 4 5 6 5 1 5 5 3 2 6 4

6 2.最小生成树为： 1 5 3 2 4

33.什么是堆?写出对应于序列(10，20，7，75，41，67，3，9，30，45)的初始堆(堆顶元素取最小值)。

答：1堆是一键值序列{k 1,k 2,…k n },对所有i=1,2,3… n/2 满足 k i ≤k 2i Ki ≤k 2i+1

由题意可以得出如下初始堆 \\

四、算法设计题(本大题共2小题，每小题7分，共14分) 34.二叉树按二叉链表形式存储，编写一个算法判别给定的二叉树是否为完全二叉树。

1 3 2 4 5 0 1 2 3 4 5

答：1连通图为： 0 2 3 5 1 3

解题思路： 1.画连通图时的一个技巧是，数字基本按顺序写，0为最高端。然后根据下标找出路线即可。

2.最小生成树和最优路径选着法

一样，记住两点之间只有一条线连接。注意： 一个点出去的最短不代表到下一个点最短，要 把两条路径加起来比较一下。 3 9 7 20 41 67 10 75 30 3

解题思路：1.先将给出的序列以完全二叉树依次写出。2. 然后从最右边的看起， 若要求

最小根，那么找小的作为根。若要求最大根，那么找最大的作为根。

3.总之，求最大根，从总根开始，结点根依次减小，求最小根，结点根逐渐减大。

4.

调整位置即可。

Int Judgecomplete(Bitree bt) //判断是否是二叉树，是返回1，否返回0

Int tag=0,Bitree p=bt,Q[]; //Q是队列，元素是二叉树的结点指针，容量足够大If (p==null) return (1);

QueueInit(Q),Queuelint(Q,p); //初始化队列，根节点入队 While (!QueueEmpty(Q))

{p=QueueOut(Q); //出队

If（p->lchild&&!tag）QueneIn(Q,p->lchild) //左孩子入队 Else{ if (p->lchild) return 0; //前面已有节点为空，此结点不为空 Else tag=1; //首次出现结点为空

If (p->right&&!tag) QueneIn(Q,p->rchild) //又孩子入队 Else{if (p->rchild) return 0; Else tag=1; }//while return 1 ; }//JudgeComplete

35.试写出直接插入排序算法。 Void StraightInseartSort (list r, int n) //对顺序表直接进行插入排序 { int i , j;

For (i=2,i<=n,i++) //n为表长，从第二个记录起进行插入。 { R[0]=R[i]; //第i个值赋值为岗哨 j=i-1；

while(R[0].key<=\"\">

{R[j+1]=R[j]; //将第J个值赋给第J+1个值 j--; }

R[j+1]=R[0]; //将第i个值插入到系列中 } }