1、2005 年下半年全国自考（数据结构）真题试卷及答案与解析一、单项选择题1 若将数据结构形式定义为二元组(K,R)，其中 K 是数据元素的有限集合，则 R 是K 上( )（A）操作的有限集合（B）映象的有限集合（C）类型的有限集合（D）关系的有限集合2 在长度为 n 的顺序表中删除第 i 个元素(1in)时，元素移动的次数为 ( )（A）n-i+1（B） i（C） i+1（D）n-i3 若不带头结点的单链表的头指针为 head，则该链表为空的判定条件是 ( )（A）head=NULL（B） headnext=NULL（C） head!=NULL（D）headnext=head4 引起循环队列队
2、头位置发生变化的操作是 ( )（A）出队（B）入队（C）取队头元素（D）取队尾元素5 若进栈序列为 1,2,3,4,5,6，且进栈和出栈可以穿插进行，则不可能出现的出栈序列是( )（A）2,4,3,1,5,6（B） 3,2,4,1,6,5（C） 4,3,2,1,5,6（D）2,3,5,1,6,46 字符串通常采用的两种存储方式是 ( )（A）散列存储和索引存储（B）索引存储和链式存储（C）顺序存储和链式存储（D）散列存储和顺序存储7 设主串长为 n，模式串长为 m(mn)，则在匹配失败情况下，朴素匹配算法进行的无效位移次数为 ( )（A）m（B） n-m（C） n-m+1（D）n8 二维数组
3、A1218采用列优先的存储方法，若每个元素各占 3 个存储单元，且第 1 个元素的地址为 150，则元素 A97的地址为 ( )（A）429（B） 432（C） 435（D）4389 对广义表 L=(a,b)，(c,d) ，(e,f)执行操作 tail(tail(L)的结果是 ( )（A）(e,f)（B） (e,f)（C） (f)（D）()10 下列图示的顺序存储结构表示的二叉树是 ( )（A） while(i L-lengthjLlength;j+) Ldataj-1=Ldataj; Llength-; else for(j=Llength;ji;j-) Ldataj=L dataj-1;
4、Ldatai=x; Llength+; 31 已知图的邻接表表示的形式说明如下： #define MaxNum 50 /图的最大顶点数 typedef struct node int adjvex; /邻接点域 struct node*next; /链指针域 EdgeNode; /边表结点结构描述 typedef struct char vertex; /顶点域 EdgeNode*firstedge;/边表头指针 VertexNode; /顶点表结点结构描述 typedef struet VertexNode adjlistMaxNum;/邻接表 int n,e; /图中当前的顶点数和边数 A
5、LGraph; /邻接表结构描述 下列算法输出图 G 的深度优先生成树(或森林)的边。阅读算法，并在空缺处填入合适的内容，使其成为一个完整的算法。 typedef enumFALSE,TRUEBoolean; Boolean visitedMaxNurn; void DFSForest(ALGraph*G) int i; for(i=0;i Gn;i+)visitedi= (1) ; for(i=0;i Gn;i+)if(!visitedi)DFSTree(G,i); void DFSTree(ALGraph*G,int i) EdgeNode*p; visitedi=TRUE; p=Gadj
6、listi.firstedge; while(p!=NULL) if(!visitedpadjvex) printf(“%c,%c“,Gadjlisti.vertex, Gadjlistpadjvex.vertex); (2) ; (3) ; 32 阅读下列算法，并回答问题： (1)假设数组 L8=3,0,5,1,6,4,2,7，写出执行函数调用 f32(L,8)后的 L； (2)写出上述函数调用过程中进行元素交换操作的总次数。 void fS2(int R,int n) int i,t; for(i=0;in-1;i+) while(Ri!=i) t=RRi-1; RRi=Ri; Ri=t;
7、 33 已知带头结点的单链表中的关键字为整数，为提高查找效率，需将它改建为采用拉链法处理冲突的散列表。设散列表的长度为 m，散列函数为 Hash(key)=key%m。链表的结点结构为： 。请在空缺处填入适当内容，使其成为一个完整算法。 void f33(LinkList L,LinkList H,int m) /由带头结点的单链表 L 生成散列表 H，散列表生成之后原链表不再存在 int i,j; LinkList p,q; for(i=0;im;i+) Hi= (1) ; p=L next; while(p) q=pnext j=p key%m; (2) ; Hj=p; (3) ; fre
8、e(L); 五、算法设计题33 假设以带双亲指针的二叉链表作为-二叉树的存储结构，其结点结构的类型说明如下所示： typedef char DataType; typedef struct node DataType data; struct node*lchild,*rchild; /左右孩子指针 struct node*parent; /指向双亲的指针 BinTNode; typedef BinTNode*BinTree; 若 px 为指向非空二叉树中某个结点的指针，可借助该结构求得 px 所指结点在二叉树的中序序列中的后继。34 1. 就后继的不同情况，简要叙述实现求后继操作的方法；35
9、 2. 编写算法求 px 所指结点的中序序列后继，并在算法语句中加注注释。2005 年下半年全国自考（数据结构）真题试卷答案与解析一、单项选择题1 【正确答案】 D2 【正确答案】 D3 【正确答案】 A4 【正确答案】 A5 【正确答案】 D6 【正确答案】 C7 【正确答案】 C8 【正确答案】 A9 【正确答案】 B10 【正确答案】 A11 【正确答案】 B12 【正确答案】 D13 【正确答案】 C14 【正确答案】 B15 【正确答案】 C二、填空题16 【正确答案】 存储结构17 【正确答案】 pprior=ppriorprior; pprior next=p; (或 pprio
10、rpriornext=p; pprior=ppriorprior;18 【正确答案】 栈空19 【正确答案】 EFGH20 【正确答案】 表尾21 【正确答案】 1122 【正确答案】 入度23 【正确答案】 基数24 【正确答案】 同义词25 【正确答案】 已有 m 个同义词的记录(或：已有 m 个记录；或：已满)三、解答题26 【正确答案】 1.quelen=m2.quelen=03.354.(rear-quelen+1+m)%m27 【正确答案】 28 【正确答案】 该图的强连通分量分别为：29 【正确答案】 1.4 7 1 3 6 5 22.初始关键字 4 7 1 3 6 5 2 一次
11、划分后得 (2 3 1)4(6 5 7) 继续划分后得 (1)2(3) (5)6(7)四、算法阅读题30 【正确答案】 1.(3,7,11,14,15,20,51)2.(4,7,14,20,51)3.当非递减顺序表中存在元素 x 时，从表中删除该元素；否则将 X 保序插入到顺序表中。31 【正确答案】 1.FALSE2.DFSTree(G,Padjvex)3.p=pnext32 【正确答案】 1.L8=0,1,2,3,4,5,6,7,2.共进行 5 次元素交换。33 【正确答案】 1.NULL2.pnext=Hj3.p=q五、算法设计题34 【正确答案】 分两种情况讨论 当*px 的右子树不为
12、空时，则从*px 的右孩子开始，沿其左孩子往下查找，直至找到一个没有左孩子的结点为止，则该结点为*pX 在中序序列中的后继； 当*px 的右子树为空时，则沿*px 的双亲指针链向上查找，直至找到其左子树中包含*px 的最年轻祖先，则该祖先结点为*px 在中序序列中的后继。35 【正确答案】 BinTree f34(BinTree px) BinTree q=pxrchild; if(q!=NULL) /沿左孩子往下查找 px=q; while(pxlchild!=NULL) px=pxlchild; else /沿双亲指针链向上查找 while(px!=NULL px=pxparent; retun px； /返回所找到的中序序列后继结点的指针 /或者无后继结点时返回空指针
