1、2007 年下半年全国自考（数据结构）真题试卷及答案与解析一、单项选择题1 下面程序段的时间复杂度为 ( ) s=0; for(i=1;in;i+) for(j=1;ji;j+) s+=i*j;（A）O(1)（B） O(log2n)（C） O(n)（D）O(n 3)2 已知指针 p 和 q 分别指向某单链表中第一个结点和最后一个结点。假设指针 s 指向另一个单链表中某个结点，则在 s 所指结点之后插入上述链表应执行的语句为 ( )（A）qnext=snext;snext=p;（B） snext=P;qnext=s next;（C） pnext=s next;s next=q;（D）snext=
2、q;p next=snext;3 在计算机内实现递归算法时所需的辅助数据结构是 ( )（A）栈（B）队列（C）树（D）图4 假设以数组 Am存放循环队列的元素。已知队列的长度为 length，指针 rear 指向队尾元素的下一个存储位置，则队头元素所在的存储位置为 ( )（A）(rear-length+m+1)%m（B） (rear-length+m)%m（C） (rear-length+m-1)%m（D）(rear-length)%m5 通常将链串的结点大小设置为大于 1 是为了 ( )（A）提高串匹配效率（B）提高存储密度（C）便于插入操作（D）便于删除操作6 带行表的三元组表是稀疏矩阵的
3、一种 ( )（A）顺序存储结构（B）链式存储结构（C）索引存储结构（D）散列存储结构7 表头和表尾均为空表的广义表是 ( )（A）()（B） ()（C） ()（D）()，()8 用二叉链表表示具有 n 个结点的二叉树时，值为空的指针域的个数为 ( )（A）n-1（B） n（C） n+1（D）2n9 为便于判别有向图中是否存在回路，可借助于 ( )（A）广度优先搜索算（B）最小生成树算法（C）最短路径算（D）拓扑排序算法10 连通网的最小生成树是其所有生成树中 ( )（A）顶点集最小的生成树（B）边集最小的生成树（C）顶点权值之和最小的生成树（D）边的权值之和最小的生成树11 按排序过程中依据的
4、原则分类，快速排序属于 ( )（A）插入类的排序方法（B）选择类的排序方法（C）交换类的排序方法（D）归并类的排序方法12 下列关键字序列中，构成小根堆的是 ( )（A）84,46,62,41,28,58,15,37（B） 84,62,58,46,41,37,28,15（C） 15,28,46,37,84,41,58,62（D）15,28,46,37,84,58,62,4113 在长度为 32 的有序表中进行二分查找时，所需进行的关键字比较次数最多为( )（A）4（B） 5（C） 6（D）714 假设在构建散列表时，采用线性探测解决冲突。若连续插入的 n 个关键字都是同义词，则查找其中最后插入
5、的关键字时，所需进行的比较次数为 ( )（A）n-1（B） n（C） n+i（D）n+215 散列文件也称为 ( )（A）顺序文件（B）索引文件（C）直接存取文件（D）间接存取文件二、填空题16 数据的逻辑结构描述数据元素之间的_，与存储方式无关。17 在一个长度为 100 的顺序表中删除第 10 个元素时，需移动_个元素。18 队列的队尾位置通常是随着_操作而变化的。19 两个空串联接得到的串的长度为_。20 设对称矩阵 A 压缩存储在一维数组 B 中，其中矩阵的第一个元素 a11 存储在B0，元素 a52 存储在 B11，则矩阵元素 a36 存储在 B_中。21 已知一棵哈夫曼树含有 60
6、 个叶子结点，则该树中共有_个非叶子结点。22 如图所示的有向图中含有_个强连通分量。23 已知一组关键字为15,36,28,97,24,78,47,52,13,86 ，其中每相邻两个关键字构成一个有序子序列。对这些子序列进行一趟两两归并的结果是_。24 从空树起，依次插入关键字 11,27,35,48,52,66 和 73 构造所得的二叉排序树，在等概率查找的假设下，查找成功时的平均查找长度为_。25 控制区间和控制区域是_文件的逻辑存储单位。三、解答题26 利用广义表的 head 和 tail 操作，可从广义表 L=(a,b)，(c,d) 中分解得到原子 c，其操作表达式为 head(he
7、ad(tail(L); 分别写出从下列广义表中分解得到 b 的操作表达式。 (1)L1=(a,b,c,d); (2)L2=(a),(b),(c),(d)。27 画出与如图所示森林对应的二叉树。 28 已知有向图 G 的定义如下： G=(V,E) V=a,b,c,d,e E= a,b，a,c， b,c，b,d，c,d，e,c，e,d) (1)画出 G 的图形； (2)写出 G 的全部拓扑序列。29 已知 3 阶 B-树如图所示。 (1)画出将关键字 88 插入之后的 B-树； (2)画出将关键字 47 和 66 依次插入之后的 B 一树。 四、算法阅读题30 假设某个不设头指针的无头结点单向循环
8、链表的长度大于 1，S 为指向链表中某个结点的指针。算法 f30 的功能是，删除并返回链表中指针 S 所指结点的前驱。请在空缺处填入合适的内容，使其成为完整的算法。 typedef struct node DataType data; struct node *next; *LinkList; DataType f 30(LinkList s) LinkList pre,p; DataType e; pre=s; p=snext; while( (1) ) pre=p; (2) ； prenext= (3) ; e=pdata; free(p); return e; 31 算法 f31 的功能
9、是清空带头结点的链队列 Q。请在空缺处填入合适的内容，使其成为一个完整的算法。 typedef struct node DataType data; struct node *next; QueueNode; typedef struet QueueNode*front; /队头指针 QueueNode*rear; /队尾指针 LinkQueue; void f31(LinkQueue*Q) QueueNode*p,*s; p= (1) ; while(P!=NULL) s=p; p=pnext; free(s); (2) =NULL; Qrear= (3) ; 32 假设采用动态存储分配的顺
10、序串 HString 作为串的存储结构。该类型实现的串操作函数原型说明如下： void strinit(HString s); /置 s 为空串 int strlen(HString s); /求串 s 的长度 void strcpy(HString to,HString from); /将串 from 复制到串 to void streat(HString to,HString from); /将串 from 联接到串 to 的末尾 int strcmp(HString s1,HString s2); /比较串 s1 和 s2 的大小，当 s1s2 ，s1=s2 或 s1s2 时， /返回值
11、小于 0，等于 0 或大于 0 HString substr(HString s,int i,int m); /返回串 S 中从第 i(0istrlen(s)-m)个字符起长度为 m 的子串阅读下列算法f32，并回答问题： (1)设串 S=“abcdabcd“，T=“bcd“ ，V=“bcda“ ，写出执行 f32(S,T,V)之后的 S； (2)简述算法 f32 的功能。 void f 32(HString S,HString T,HString V) int m,n,pos,i; HString news; strinit(news); n=strlen(S); m=strlen(T);
12、pos=i=0; while(i=n-m) if(strcmp(substr(S,i,m)，T)!=0)i+; else strcat(news,substr(S,pos,i-pos); strcat(news,V); pos=i=i+m; strcat(news,substr(S,pos,npos); strcpy(S,news); 33 假设以二叉链表作为二叉树的存储结构，其类型定义如下： typedef struct node char data; struct node*lchild,*rchild; /左右孩子指针 BinTNode,*BinTree; 阅读下列算法 f33，并回答问
13、题： (1)已知如图所示的二叉树以 T 为指向根结点的指针，画出执行 f33(T)后的二叉树；(2)简述算法 f 33 的功能。 void f 33(BinTtee T) if(T) f 33(Tlchild); f 33(Trchild); if(!T lchild) Trchild=NULL; 五、算法设计题34 假设以带头结点的单链表表示有序表，单链表的类型定义如下： typedef struct node int data; struct node*next; LinkNode,*LinkList; 编写算法，输入 n 个整数构造一个元素值互不相同的递增有序链表(即相同的整数只取一 个
14、)。算法的函数原型给定为 LinkList f 34(int n);2007 年下半年全国自考（数据结构）真题试卷答案与解析一、单项选择题1 【正确答案】 D2 【正确答案】 A3 【正确答案】 A4 【正确答案】 B5 【正确答案】 B6 【正确答案】 A7 【正确答案】 B8 【正确答案】 C9 【正确答案】 D10 【正确答案】 D11 【正确答案】 C12 【正确答案】 D13 【正确答案】 C14 【正确答案】 B15 【正确答案】 C二、填空题16 【正确答案】 逻辑关系(或关系)17 【正确答案】 9018 【正确答案】 入队19 【正确答案】 020 【正确答案】 1721 【
15、正确答案】 5922 【正确答案】 223 【正确答案】 15,28,36,97,24,47,52,78,13,8624 【正确答案】 425 【正确答案】 VSAM三、解答题26 【正确答案】 1.head(tail(L1)2.head(head(tail(head(L2)27 【正确答案】 28 【正确答案】 1. 2.a,b,e,c,d a,e,b,c,d e,a,b,c,d29 【正确答案】 1. 2.四、算法阅读题30 【正确答案】 1.pnext!=s2.p=pnext3.s(或 pnext)31 【正确答案】 1.Qfrontnext2.Qfront next3.Qfront32
16、 【正确答案】 1.s=“abcdaabeda“2.串的置换操作，用串 V 置换串 S 中的子串 T。33 【正确答案】 1. 2.对二叉树的每个结点，如果其左孩子为空(右孩子不空)，则将其右孩子设置为左孩子。五、算法设计题34 【正确答案】 LinkList f 34(int n) LinkList L,P,q,s; int e,i; L=(LinkList)malloe(sizeof(LinkNode); Lnext=NULL; for(i=1;i=n;i+) seanf(“%d“, p=L; q=pnext; while(q q=qnext; if(!q|qdatae) s=(LinkList)malloc(sizeof(LinkNode); sdata=e; snext=q; pnext=s; return L;
