1、2008 年下半年全国自考（数据结构）真题试卷及答案与解析一、单项选择题1 如果在数据结构中每个数据元素只可能有一个直接前驱，但可以有多个直接后继，则该结构是 ( )（A）栈（B）队列（C）树（D）图2 下面程序段的时间复杂度为 ( ) for(i=0;im;i+) for(j=0;jn;j+) Aij=i*j;（A）O(m 2)（B） O(n2)（C） O(m*n)（D）O(m+n)3 在头指针为 head 的非空单循环链表中，指针 p 指向尾结点，下列关系成立的是 ( )（A）pnext=head（B） pnextNext=head（C） pnext=NULL（D）p=head4 若以 S
2、 和 X 分别表示进栈和退栈操作，则对初始状态为空的栈可以进行的栈操作序列是( )（A）SXSSXXXX（B） SXXSXSSX（C） SXSXXSSX（D）SSSXXSXX5 两个字符串相等的条件是 ( )（A）串的长度相等（B）含有相同的字符集（C）都是非空串（D）串的长度相等且对应的字符相同6 如果将矩阵 Ann 的每一列看成一个子表，整个矩阵看成是一个广义表 L，即L=(a11，a 21， ，a n1)，(a 12，a 22，a n2)，(a 1n，a 2n，a nn)，并且可以通过求表头 head 和求表尾 tail 的运算求取矩阵中的每一个元素，则求得 a21 的运算是 ( )（A
3、）head(tail(head(L)（B） head(head(head(L)（C） tail(head(tail(L)（D）head(head(tail(L)7 已知一棵含 50 个结点的二叉树中只有一个叶子结点，则该树中度为 1 的结点个数为( )（A）O（B） 1（C） 48（D）498 在一个具有 n 个顶点的有向图中，所有顶点的出度之和为 Dout，则所有顶点的入度之和为( )（A）D out（B） Dout-1（C） Dout+1（D）n9 如图所示的有向无环图可以得到的拓扑序列的个数是 ( )（A）3（B） 4（C） 5（D）610 如图所示的带权无向图的最小生成树的权为 ( )
4、（A）51（B） 52（C） 54（D）5611 对长度为 n 的关键字序列进行堆排序的空间复杂度为 ( )（A）O(log 2n)（B） O(1)（C） O(n)（D）O(n*log 2n)12 已知用某种排序方法对关键字序列(51,35,93,24,13,68,56,42,77)进行排序时，前两趟排序的结果为 (35,51,24,13,68,56,42,77,93) (35,24,13,51,56,42,68,77,93) 所采用的排序方法是 ( )（A）插入排序（B）冒泡排序（C）快速排序（D）归并排序13 已知散列表的存储空间为 T018，散列函数 H(key)=key%17，并用二次
5、探测法处理冲突。散列表中已插入下列关键字：T5=39，T6=57 和 T7=7，则下一个关键字 23 插入的位置是 ( )（A）T2（B） T4（C） T8（D）T1014 适宜进行批量处理的文件类型是 ( )（A）顺序文件（B）索引顺序文件（C）散列文件（D）多关键字文件15 VSAM 文件的索引结构为 ( )（A）B+树（B）二叉排序树（C） B-树（D）最优二叉树二、填空题16 如果某算法对于规模为 n 的问题的时间耗费为 T(n)=3n3，在一台计算机上运行时间为 t 秒，则在另一台运行速度是其 64 倍的机器上，用同样的时间能解决的问题规模是原问题规模的_倍。17 将两个长度分别为
6、m 和 n 的递增有序单链表，归并成一个按元素递减有序的单链表，可能达到的最好的时问复杂度是_。18 已知循环队列的存储空间大小为 m，队头指针 front 指向队头元素，队尾指针rear 指向队尾元素的下一个位置，则在队列不满的情况下，队列的长度是_。19 字符串“sgabacbadfgbacst“ 中存在有_个与字符串“ba“相同的子串。20 假设以列优先顺序存储二维数组 A58，其中元素 A00的存储地址为LOC(a00)，且每个元素占 4 个存储单元，则数组元素 Aij的存储地址为_ 。21 假设用x,y表示树的边(其中 s 是 y 的双亲)，已知一棵树的边集为b,d ， a,b，c,
7、g，c,f ，c,h，a,c)，该树的度是_。22 n 个顶点且含有环路的无向连通图中，至少含有_条边。23 在一般情况下用直接插入排序、选择排序和冒泡排序的过程中，所需记录交换次数最少的是_。24 和二分查找相比，顺序查找的优点是除了不要求表中数据元素有序之外，对_结构也无特殊要求。25 顺序文件中记录存放的物理顺序和_顺序一致。三、解答题26 由森林转换得到的对应二叉树如图所示，写出原森林中第三棵树的前序序列和后序序列。 前序序列： 后序序列：27 图的邻接表的类型定义如下所示： #define MaxVertexNum 50 typedef struct node int adjvex;
8、 struct node*next; EdgeNode; typedef struct VertexType vertex; EdgeNode*firstedge; VertexNode; typedef VertexNode A djListMaxVertexNum; typedef struct AdjList adjiist; int n,e; ALGraph; 为便于删除和插入图的顶点的操作，可将邻接表的表头向量定义为链式结构，两种定义的存储表示实例如下图所示，请写出重新定义的类型说明。 28 某类物品的编号由一个大写英文字母及 2 位数字(09)组成，形如 E32。运用基数排序对下列
9、物品编号序列进行按字典序的排序，写出每一趟(分配和收集)后的结果。 E13,A37,F43,B32,B47,E12,F37,B12 第一趟： 第二趟： 第三耥：29 (1)画出对表长为 13 的有序顺序表进行二分查找的判定树； (2)已知关键字序列为 (12,14,16,21,24,28,35,43,52,67,71,84,99)，写出在该序列中二分查找 37 时所需进行的比较次数。四、算法阅读题30 已知线性表的存储结构为顺序表，阅读下列算法，并回答问题： (1)设线性表 L=(21,-7,-8,19,0，-11,34,30，-10) ，写出执行 f30( for(i=j=0;iLlengt
10、h;i+) if(Ldatai=0) if(i!=j)Ldataj=Ldatai; j+; Llength=j; 31 阅读下列算法，并回答问题： (1)Q、Q1 和 Q2 都是队列结构，设队列 Q=(1,0,-5,2,-4,-6,9)，其中 1 为队头元素，写出执行 f31( InitQueue(Q1); InitQueue(Q2); while(!QueueEmpty(Q) e=DeQueue(Q); if(e=0)EnQueue(Q 1,e); else EnQueue(Q2,e); 32 阅读下列算法，并回答问题： (1)假设串由合法的英文字母和空格组成，并以0作结束符。设串 ，写出
11、f32(s)的返回值； (2)简述算法 f32 的功能。 int f32(char*s) int i,n,inword; n=inword=0; for(i=0;si!=0;i+) inword=0; return n; 33 阅读下列对正整数关键字序列 L 操作的算法，并回答问题： (1)设 L=(28,19,27,49,56,12,10,25,20,50)，写出 f33(L,4)的返回值； (2)简述函数 f33 的功能。 int Partition(SeqList*L,int low,int high); /对 Llowhigh做划分，返回基准记录的位置，并使左部的关键字 /都小于或等于
12、基准记录的关键字，右部的关键字都大于基准记录的关键字 int f33(SeqList L,int k) int low,high,pivotpos; low=1; high=L.length; if(klow|khigh) return-1; do pivotpos=Partition( else if(pivotposk) high=pivotpos-1; while(pivotpos!=k); return L.datapivotpos; 五、算法设计题34 二叉排序树的类型定义如下： typedef struet BSTNode/二叉排序树的结点结构 int data; /数据域 str
13、uct BSTNode*lchild,*rchild;/左、右孩子指针 BSTNode,*BSTree; 设计递归算法，统计一棵二叉排序树 T 中值小于 a 的结点个数。2008 年下半年全国自考（数据结构）真题试卷答案与解析一、单项选择题1 【正确答案】 C【试题解析】 在树中，除了根结点和叶子结点外，其余结点都仅有一个直接前驱而且有一个或多个直接后继。而根结点没有直接前驱但有一个或多个直接后继，叶子结点有一个直接前驱却没有直接后继。2 【正确答案】 C【试题解析】 此程序的时间复杂度即为程序中循环次数的时间耗费。由程序为嵌套循环，外层循环的时间复杂度 T(n1)=m，内层循环的时间复杂度
14、T(n2)=n，则此程序的时间复杂度 T(n)=m*n，即为 0(m*n)。3 【正确答案】 A【试题解析】 在单链表中，将终端结点的指针域 NULL 改为指向表头结点或开始结点，就得到了单链形式的循环链表，并简单称为单循环链表。故由题目中此单循环锚表的头指针为 head，指针 p 指向尾结点，可得 pnext=head。4 【正确答案】 D【试题解析】 可以按以下两个原则来判断出正确的栈操作序列：(1)操作序列中进栈次数和出栈次数相等；(2)操作序列中任一操作之前的进栈次数大于等于出栈次数。5 【正确答案】 D6 【正确答案】 A【试题解析】 若广义表 LS 非空(n1)，则 a1 是 LS
15、 的表头，其余元素组成的表(a2， ，a n)称为 LS 的表尾。则此题目欲求得元素 a21，则需先进行取表头运算head(L)得子表 1(a11，a 21，a n1)，然后对此子表 1 进行取表尾运算 tail(head(L)得子表 2(a21，a n1)，再对子表 2 进行取表头运算 head(tail(head(L)可得元素a21。7 【正确答案】 D【试题解析】 由此二叉树仅有一个叶子结点，可知此二叉树中除叶子结点外的所有结点都仅有一颗子树，即这些结点的度都为 1，而这些结点的个数为 50-1=49。8 【正确答案】 A【试题解析】 在有向图中，所有顶点的入度之和等于出度之和。9 【正
16、确答案】 C【试题解析】 此有向无环图可以得到的操作序列：(1)2、6、3、5、4；(2)2、6、5、3、4；(3)6 、2、3、5、4；(4)6 、2、5、3、4；(5)6、5、2、3、4。10 【正确答案】 C【试题解析】 根据最小生成树的构造过程，可知在构造本题中无向图的最少生成树时，将选取权值分别为 10、14、12、18 的边，所以此最小生成树的权即各边权值之和即 54。11 【正确答案】 B【试题解析】 由于建初始堆所需的比较次数较多，所以堆排序不适宜于记录数较少的文件。堆排序是就地排序，辅助空间为 0(1)，但它是不稳定的。12 【正确答案】 B【试题解析】 由题目中第一趟排序的
17、结果是将所有关键字中最大的关键字(97)放在了序列最后，第二趟排序的结果是将除 97 以外的所有关键字中最大的关键字放在了序列中倒数第二个位置，可知此排序方法为冒泡排序。13 【正确答案】 D【试题解析】 由题意可得 H(23)=6，而 T6中已有关键字，产生冲突，此时采用二次探测法，则当 i=1 时，h 1=(6+11)%17=7，又 T7中也已有关键字仍然冲突。则选 i=2，此时 h2=(6+22)%17=10，此时可判定此关键字可插入 T10单元中。14 【正确答案】 A【试题解析】 顺序文件采取顺序查找法对于少量的检索是不经济的，但适合于批量检索，即把用户的检索要求先进行积累，一旦待查
18、记录聚集到一定数量之后，便把这批记录按主关键字排序，然后，通过一次顺序扫描文件来完成这一批检索要求。15 【正确答案】 A【试题解析】 VSAM 是 Virtual Storage Access Method(虚拟存储存取方法)的缩写，它是一种索引顺序文件的组织方式，采用 B+树作为动态索引结构。二、填空题16 【正确答案】 4【试题解析】 设在速度快的机器上运行此算法的规模为 n1，则时间耗费为，则由速度快机器是原机器速度的 64 倍，即 ，则n1/n-4，即在同样时间内速度快机器解决问题规模是原机器解决问题规模的 4 倍。17 【正确答案】 O(m+n)【试题解析】 将两个递增有序单链表合
19、并为一个递减有序的单链表，则将这两个单链表都从最后一个元素开始，按照由后至前的顺序，将两单链表中元素进行比较，从而选取较大的元素依次组成新的单链表。18 【正确答案】 (rear-front+m)%m19 【正确答案】 320 【正确答案】 LOC(a 00)+4(5j+i)21 【正确答案】 3【试题解析】 树的度为该树中结点的最大度数，由此树的边集可知结点 c 的度数最大为 3，则此树的度为 3。22 【正确答案】 n【试题解析】 n 个顶点的无向连通图有环路且边最少时，此图仅有一个环路且所有顶点均在此环路中，此时边数为 n。23 【正确答案】 选择排序24 【正确答案】 存储25 【正确
20、答案】 逻辑三、解答题26 【正确答案】 前序序列：G H I J 后序序列：H J I G27 【正确答案】 typeclef struct ArcNode VNode*adjvex; /该弧所指向的顶点的位置 struct ArcNode*nextarc; /指向下一条弧的指针 ArcNode; typedef struct VNode VertexType data; /顶点信息 struct VNode*nextVertex; /指向下一个28 【正确答案】 第一趟：B32,E12,B12,E13,F43,A37,B47,F37 第二趟：E12,B12,E13,B32,A37,F37,
21、F43,B47 第三趟：A37,B12,B32,B47,E12,E13,F37,F4329 【正确答案】 1. 2. 3四、算法阅读题30 【正确答案】 1. L=(21,19,0,34,30)2. 删除顺序表中的负值元素。31 【正确答案】 1. Q=( ) Q 1=(1,0,2,9) Q2=(-5,-4,-6) 2.将队列 Q 的元素依次退队，并将正值及 0 元素入队到 Q1，负值元素入队到 Q2。32 【正确答案】 1. 42. 对字符串内的单词个数进行累加计数。33 【正确答案】 1. 202. 利用快速排序的“ 划分”机制进行查找，以求取序列中排行第 k 小的元素。五、算法设计题34
22、 【正确答案】 (P 71)参考答案之一： void count(BSTree T,int a,int*sum) /以 sum所指单元统计二叉排序树中元素值小于 a 的结点个数，其初值为 0 if(T) count(Tlchild,a,sum); if(Tdata (*sum)+; count(T rchild,a,sum); 参考答案之二：int count(BSTree T,int a) /统计二又排序树中元素值小于 a 的结点个数 int sum; if(!T)return 0; else sum=count(Tlchild,a); if(Tdataa) return sum+1+count(Trchild,a); else return sum;
