自考数据结构模拟题

三、解答题（本大题共4小题，每小题5分，共20分）

1. 已知串S=‘(xyz)*’,t=‘(x+z)*y’,试利用串的基本运算将s串转化为t串，t串转化为s串 。

2. 已知有一关键字序列为{486，79，596，34，900，120，789，179，703，307}，如果我们采用基数排序方法对此序列进行排序(按照升序排列)，请给出每一趟的排序结果。

3.对于散列文件来说，其存储单位是什么?对于一个能存储m个桶，若需要存放的同义词大于m，则需要如何处理?现在假设一个文件有18个记录，其关键字分别为：30，11，27，04，19，86，73，89，32，05，103，58，45，67，77，81，08，48，假设桶的容量m=3，桶数b=7，现在要求用除余法做散列函数H(key)=key%7，请给出该散列文件的表示方法 。

4. 假设在树中，如果结点x是结点y的双亲时，用(x,y)来表示树边，已知一棵树的树边的集合 为｛(i,m),(i,n),(e,i),(b,e),(b,d),(a,b),(g,j),(g,k),(c,g),(c,f),(h,l),(c,h),(a,c)｝,请用树形结构画出此树，并回答下面的问题。 (1)哪个是根结点? (2)哪些是叶结点? (3)哪个是g的双亲? (4)哪些是g的祖先? (5)哪些是g的孩子? (6)哪些是e的子孙? (7)哪些是e的兄弟? (8)树的深度是多少? (9)树的度数是多少?

四、算法阅读题（本大题共4小题，每小题5分，共20分） 1. 请将下面的程序改成递归的过程。 voide ditui (int n) {int i; i=n;

while(i>1) prinft(i--); }

2. 以下为单链表的建表算法，分析算法，请在___处填上正确的语句。 3. lklist create-lklist2()/*直接实现的建表算法。*/ { head=malloc(size); p=head;

scanf(″%f″,&x); while(x!=′$′) { q=malloc(size); q->data=x; p->next=q; ___;

scanf(″%f″,&x); } ___;

return(head); }

此算法的量级为___。

3. 下列算法用于判断带头结点的循环双链表A是否对称相等，请在算法中的___处填上正确的语句。 int dlink_symmetry (dlklist s) ｛ j=true; p=s->next; q=s->prior;

while(p!=q)&(___) if(p->data=q->data)

｛ (___); (___); ｝ else j=false; return(j); ｝

4. 以下将ah,…am,和am+1,…an,两个有序序列(它们相应的关键字值满足Kh≤Km,Km+1≤…Kn,)合并成一个有序序列Rh,…，Rn,(使其关键字值满足Kh,′≤…≤Kn,′)。请分析算法，并在___上填充适当的语句。 void merge(list a,list R,int h,int m,int n) {i=h;k=h;j=m+1;

while((i

{ if(a［i］.key<=a［j］.key){ R［k］=___;___ ;} else{ R［k］=___; ___;} k++; }

while(i<=___){R［k］=a［i］;i++;k++;} while(j<=___){R［k］=a［j］;j++;k++;} }

此算法的执行时间为___。 五、算法设计题（本题10分）

1. 假设在表示一棵二叉树的二叉链表上增加两个域，双亲域用于指示其双亲结点，标志域 flag(可取，0…2)的值，用以区分在遍历过程中到达该结点时继续向左或向右或访问该结点。试 以此存储结构编写不用栈进行后序遍历的递推形式的算法。

2010年全国自考数据结构模拟试卷(九)

一、单项选择题(本大题共15小题,每小题2分,共30分)在每小题列出的四个备选项目中 只有一个是符号题目要求的,请将其代码填写的括号内.错选、多选或未选均无分。 1. 当初始序列已经按键值有序时，用直接插入算法进行排序，需要比较的次数为()

2. 堆(Heap)是()

A. 完全二叉树 B. 线性表 C. 二叉排序树 D. 平衡二叉树 3. 非空的单循环链表L的尾结点P↑，满足()

A. P↑.next＝NULL； B. P＝NULL； C. P↑.next＝L； D. P＝L 4. 在一个链队列中，若f,r分别为队首、队尾指针，则插入s所指结点的操作为() A. f->next=c;f=s; B. r->next=s;r=s; C. s->next=r;r=s D. s->next=f,f=s;

5. 设数组data［0..m］作为循环队列SQ的存储空间，front为队头指针，rear为队尾指针，则 执行出队操作的语句为()

A. front:＝front+1 B. front:＝(front+1)mod m C. rear:＝(rear+1)mod m D. front:＝(front+1)mod (m+1)

6. 设有一个无向图G＝(V，E)和G′＝(V′，E′)，如果G′是G的生成树，则下面不正确的说 法是()

A. G′为G的子图

B. G′为G的连通分量

C. G′为G的极小连通子图且V′＝V D. G′是G的一个无环子图

7. 在图的邻接表存储结构上执行深度优先搜索遍历类似于二叉树上的() A. 先序遍历 B. 中序遍历 C. 后序遍历 D. 按层次遍历

8. 二维数组M［i,j］的元素是4个字符(每个字符占一个存储单元)组成的串，行下标i的范围

从0到4，列下标j的范围从0到5。M按行存储时元素M［3，5］的起始地址与M按列存储时元素()的 起始地址相同。

A. M［2，4］ B. M［3，4］ C. M［3，5］ D. M［4，4］ 9. 含N个顶点的连通图中的任意一条简单路径，其长度不可能超过() A. 1 B. N/2 C. N-1 D. N

10. 在一棵完全二叉树的顺序存储方式中，若编号为t的结点有右孩子，则此结点右孩子的编 号为()

A. 2t B. 2t-1 C. 2t+1 D. t/2

11. 如果T2是由有序树T转换而来的二叉树，那么T中结点的后序就是T2中结点的()前序B.中序 C.后序D.层次序

A. 前序 B. 中序 C. 后序 D. 层次序 12. 串是一种特殊的线性表，其特殊性体现在() A. 可以顺序存储 B. 数据元素是一个字符 C. 可以链接存储 D. 数据元素可以是多个字符 13. 下面四种内排序方法中，要求内存容量最大的是()

A. 插入排序 B. 选择排序 C. 快速排序 D. 归并排序

14. 从一个包含2000个结点的散列表A［1..2000］中查找结点的平均比较次数()从一个包含 200个结点的散列表B［1..200］中查找结点的平均比较次数。 A. 大于 B. 小于 C. 等于 D. 不确定

15. 对一棵非空二叉树进行中序遍历，则根结点的左边() A. 只有左子树上的所有结点 B. 只有右子树上的所有结点 C. 只有左子树上的部分结点 D. 只有右子树上的部分结点

二、填空题（本大题共10小题，每小题2分，共20分）

1. 设树T的度为4，其中度为1、2、3和4的结点个数分别是4、2、1和1，则T中叶子结点的个数 是：___。

2. 任意一棵具有n个结点的二叉树，若它有m个叶子，则该二叉树上度数为1的结点为___个 。 3. 有m个叶子结点(又称外结点)的哈夫曼树，其结点总数是___。

4. 在二叉排序树中，其左子树中任何一个结点的关键字一定___其右子树的各结点的关键字。 5. 从一个顺序存储的循环队列中删除一个元素时，应该___。

6. 对角矩阵中，除了___的元素之外，其余的元素都是零。则对于一个k对角线矩阵(k为奇数 )A是满足下面的条件的矩阵；如果___，则元素aij=0。

7. 在串的链式存储结构中，有一个串S1=″ejidc″，我们假设存储时结点的大小为1，并设指

针占有4个字节，则链串的存储密度为___，又假设串S2=″abcdefg″在存储时我们设定结点的大小为4，指针占有4个字节，则此链串的存储密度为___。

8. 对于一个具有n条边和e个顶点的图来说，如果采用邻接表表示，则其空间复杂度为___，若 采用邻接矩阵表示，则其空间复杂度为___。

9. 数组A［1..10,-2..6,2..8］以行优先顺序存储，设第一个元素的首地址是100，每个元素 占3个存储长度的存储空间，则元素A［5，0，7］的存储地址为___。 10. ___查找法的平均查找长度与元素个数n无关。 三、解答题（本大题共4小题，每小题5分，共20分）

1. 已知有一关键字序列为{97，86，53，108，72，34，215，146，11，68}，如果我们采用直 接选择排序方法对此序列进行排序(按照升序排列)，请给出每一趟的排序结果。

2. 判别下列二序列是否为堆，如不是，按照对序列建堆的思想把它调整为堆，用图表示建堆 的过程。

（1）(1，5，7，25，21，8，8，42) （2）(3，9，5，8，4，17，21，6)

3. 已知散列函数为H(K)=K mod 12,键值序列为

25，37，52，43，84，99，120，15，26，11，70，82，采用拉链法处理冲突，试构造开散列表 ，并计算查找成功的平均查找长度。

4. 已知有如下一个关键字序列{96,47,104,32,73,136,15,38,90,180},按照上述插入顺序构造

一棵二叉排序树，则请给出二叉排序树的构造过程，说明其深度，并在等概率的条件下求出平均查找长度。 ：

四、算法阅读题（本大题共4小题，每小题5分，共20分）

1. 以下算法假定以线性探测法解决冲突，在闭散列表HL中查找键值为K的结点，成功时回送该 位置；不成功时回送标志-1。请分析程序，并在___上填充合适的语句。 int search-closehash(keytype K,closehash HL) { d=H(K);/*计算散列地址*/ i=d;

while(HL［i］.key!=K&&(i! =d-1)i=___;）/*未成功且未查遍整个HL时继续扫描*/ if(___)return(i);/*查找成功*/ else return(-1);/*查找失败*/ }

2. 以下为顺序表的定位运算，分析算法，请在___处用正确的语句予以填充。 int locate-sqlist(sqlist L,datatype X)

/*在顺序表L中查找第一个值等于X的结点。若找到回传该结点序号；否则回传0*/ {___ ;

while((i≤L.last)&&(L.data［i-1］!=X))i++; if(___)return(i); else return(0); }

3. 基于三元组的稀疏矩阵转置的处理方法有两种，以下运算按照矩阵A的列序来进行转置，请 在___处用适当的语句予以填充。

Trans-Sparmat(SpMatrixTp a,SpMatrixTp *b) {(*b).mu=a.nu;(*b).nu=a.mu;(*b).tu=a.tu if(a.tu) {q=1;

for(col=1;___;col++) for(p=1;p<=a.tu;p++) if(___)==col)

{(*b).data［q］.i=a.data［p］.j; (*b).data［q］.j=a.data［p］.i; (*b).data［q］.v=a.data［p］.v; ___; } } }

4. 以下是图的深度优先搜索算法，请在___处填充适当的语句。 Dfs(GraphTp g,int v) { ArcNodeTp *p; printf(″%d″,v); visited［v］=1; p=___;

while(p!=NULL)

{if(!)Dfs(g,p->adjvex); p=___; } }

五、算法设计题（本题10分）

1. 设计一个用链表表示的直接选择排序算法。