【学历类职业资格】数据结构真题2007年下半年及答案解析.doc

1、数据结构真题 2007 年下半年及答案解析(总分：139.99，做题时间：90 分钟)一、B单项选择题/B(总题数：15，分数：30.00)1.下面程序段的时间复杂度为 ( ) s=0; for(i=1;in;i+) for(j=1;ji;j+) s+=i*j;（分数：2.00）A.O(1)B.O(log2C.O(D.O(n3)2.已知指针 p 和 q 分别指向某单链表中第一个结点和最后一个结点。假设指针 s 指向另一个单链表中某个结点，则在 s 所指结点之后插入上述链表应执行的语句为 ( )（分数：2.00）A.qnext=snext;snext=p;B.snext=P;qnext=snex

2、t;C.pnext=snext;snext=q;D.snext=q;pnext=snext;3.在计算机内实现递归算法时所需的辅助数据结构是 ( )（分数：2.00）A.栈B.队列C.树D.图4.假设以数组 Am存放循环队列的元素。已知队列的长度为 length，指针 rear 指向队尾元素的下一个存储位置，则队头元素所在的存储位置为 ( )（分数：2.00）A.(rear-length+m+1)%mB.(rear-length+%mC.(rear-length+m-1)%mD.(rear-lengt%m5.通常将链串的结点大小设置为大于 1 是为了 ( )（分数：2.00）A.提高串匹配效率

3、B.提高存储密度C.便于插入操作D.便于删除操作6.带行表的三元组表是稀疏矩阵的一种 ( )（分数：2.00）A.顺序存储结构B.链式存储结构C.索引存储结构D.散列存储结构7.表头和表尾均为空表的广义表是 ( )（分数：2.00）A.()B.()C.()D.()，()8.用二叉链表表示具有 n 个结点的二叉树时，值为空的指针域的个数为 ( )（分数：2.00）A.n-1B.nC.n+1D.2n9.为便于判别有向图中是否存在回路，可借助于 ( )（分数：2.00）A.广度优先搜索算B.最小生成树算法C.最短路径算D.拓扑排序算法10.连通网的最小生成树是其所有生成树中 ( )（分数：2.00）

4、A.顶点集最小的生成树B.边集最小的生成树C.顶点权值之和最小的生成树D.边的权值之和最小的生成树11.按排序过程中依据的原则分类，快速排序属于 ( )（分数：2.00）A.插入类的排序方法B.选择类的排序方法C.交换类的排序方法D.归并类的排序方法12.下列关键字序列中，构成小根堆的是 ( )（分数：2.00）A.84,46,62,41,28,58,15,37B.84,62,58,46,41,37,28,15C.15,28,46,37,84,41,58,62D.15,28,46,37,84,58,62,4113.在长度为 32 的有序表中进行二分查找时，所需进行的关键字比较次数最多为( )（

5、分数：2.00）A.4B.5C.6D.714.假设在构建散列表时，采用线性探测解决冲突。若连续插入的 n 个关键字都是同义词，则查找其中最后插入的关键字时，所需进行的比较次数为 ( )（分数：2.00）A.n-1B.nC.n+iD.n+215.散列文件也称为 ( )（分数：2.00）A.顺序文件B.索引文件C.直接存取文件D.间接存取文件二、B填空题/B(总题数：10，分数：20.00)16.数据的逻辑结构描述数据元素之间的 1，与存储方式无关。（分数：2.00）填空项 1:_17.在一个长度为 100 的顺序表中删除第 10 个元素时，需移动 1 个元素。（分数：2.00）填空项 1:_18

6、.队列的队尾位置通常是随着 1 操作而变化的。（分数：2.00）填空项 1:_19.两个空串联接得到的串的长度为 1。（分数：2.00）填空项 1:_20.设对称矩阵 A 压缩存储在一维数组 B 中，其中矩阵的第一个元素 a11存储在 B0，元素 a52存储在B11，则矩阵元素 a36存储在B 1中。（分数：2.00）填空项 1:_21.已知一棵哈夫曼树含有 60 个叶子结点，则该树中共有 1 个非叶子结点。（分数：2.00）填空项 1:_22.如图所示的有向图中含有_个强连通分量。 （分数：2.00）填空项 1:_23.已知一组关键字为15,36,28,97,24,78,47,52,13,8

7、6，其中每相邻两个关键字构成一个有序子序列。对这些子序列进行一趟两两归并的结果是 1。（分数：2.00）填空项 1:_24.从空树起，依次插入关键字 11,27,35,48,52,66 和 73 构造所得的二叉排序树，在等概率查找的假设下，查找成功时的平均查找长度为 1。（分数：2.00）填空项 1:_25.控制区间和控制区域是 1 文件的逻辑存储单位。（分数：2.00）填空项 1:_三、B解答题/B(总题数：3，分数：30.00)利用广义表的 head 和 tail 操作，可从广义表 L=(a,b)，(c,d) 中分解得到原子 c，其操作表达式为 head(head(tail(L); 分别写

8、出从下列广义表中分解得到 b 的操作表达式。 (1)L1=(a,b,c,d); (2)L2=(a),(b),(c),(d)。（分数：9.99）(1).（分数：3.33）_(2).（分数：3.33）_已知有向图 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 的全部拓扑序列。（分数：10.00）(1). （分数：5.00）_(2).（分数：5.00）_已知 3 阶 B-树如图所示。 (1)画出将关键字 88 插入之后的 B-树； (2)画出将关键字 47 和 66 依次插入之后的 B

9、 一树。 （分数：10.00）(1). （分数：5.00）_(2).（分数：5.00）_四、B算法阅读题/B(总题数：4，分数：50.00)假设某个不设头指针的无头结点单向循环链表的长度大于 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=sne

10、xt; while(U (1) /U) pre=p; U (2) /U； prenext=U (3) /U; e=pdata; free(p); return e; （分数：15.00）(1).（分数：5.00）填空项 1:_填空项 1:_算法 f31 的功能是清空带头结点的链队列 Q。请在空缺处填入合适的内容，使其成为一个完整的算法。 typedef struct node DataType data; struct node *next; QueueNode; typedef struet QueueNode*front; /队头指针 QueueNode*rear; /队尾指针 LinkQ

11、ueue; void f31(LinkQueue*Q) QueueNode*p,*s; p=U (1) /U; while(P!=NULL) s=p; p=pnext; free(s); U (2) /U=NULL; Qrear=U (3) /U; （分数：15.00）(1).（分数：5.00）填空项 1:_填空项 1:_假设采用动态存储分配的顺序串 HString 作为串的存储结构。该类型实现的串操作函数原型说明如下： void strinit(HString s); /置 s 为空串 int strlen(HString s); /求串 s 的长度 void strcpy(HString

12、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 时， /返回值小于 0，等于 0 或大于 0 HString substr(HString s,int i,int m); /返回串 S 中从第 i(0istrlen(s)-m)个字符起长度为 m 的子串阅读下列算法 f32，并回答问题： (1)设串 S=“abcda

13、bcd“，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); 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(

14、news,substr(S,pos,npos); strcpy(S,news); （分数：10.00）(1).（分数：5.00）(2).（分数：5.00）_假设以二叉链表作为二叉树的存储结构，其类型定义如下： typedef struct node char data; struct node*lchild,*rchild; /左右孩子指针 BinTNode,*BinTree; 阅读下列算法 f33，并回答问题： (1)已知如图所示的二叉树以 T 为指向根结点的指针，画出执行 f33(T)后的二叉树； (2)简述算法 f 33 的功能。 void f 33(BinTtee T) if(T) f

15、 33(Tlchild); f 33(Trchild); if(!Tlchild) Trchild=NULL; （分数：10.00）(1).（分数：5.00）(2).（分数：5.00）_五、B算法设计题/B(总题数：1，分数：10.00)26.假设以带头结点的单链表表示有序表，单链表的类型定义如下： typedef struct node int data; struct node*next; LinkNode,*LinkList; 编写算法，输入 n 个整数构造一个元素值互不相同的递增有序链表(即相同的整数只取一 个)。算法的函数原型给定为 LinkList f 34(int n);（分数：

16、10.00）_数据结构真题 2007 年下半年答案解析(总分：139.99，做题时间：90 分钟)一、B单项选择题/B(总题数：15，分数：30.00)1.下面程序段的时间复杂度为 ( ) s=0; for(i=1;in;i+) for(j=1;ji;j+) s+=i*j;（分数：2.00）A.O(1)B.O(log2C.O(D.O(n3) 解析：2.已知指针 p 和 q 分别指向某单链表中第一个结点和最后一个结点。假设指针 s 指向另一个单链表中某个结点，则在 s 所指结点之后插入上述链表应执行的语句为 ( )（分数：2.00）A.qnext=snext;snext=p; B.snext=P

17、;qnext=snext;C.pnext=snext;snext=q;D.snext=q;pnext=snext;解析：3.在计算机内实现递归算法时所需的辅助数据结构是 ( )（分数：2.00）A.栈 B.队列C.树D.图解析：4.假设以数组 Am存放循环队列的元素。已知队列的长度为 length，指针 rear 指向队尾元素的下一个存储位置，则队头元素所在的存储位置为 ( )（分数：2.00）A.(rear-length+m+1)%mB.(rear-length+%m C.(rear-length+m-1)%mD.(rear-lengt%m解析：5.通常将链串的结点大小设置为大于 1 是为了

18、 ( )（分数：2.00）A.提高串匹配效率B.提高存储密度 C.便于插入操作D.便于删除操作解析：6.带行表的三元组表是稀疏矩阵的一种 ( )（分数：2.00）A.顺序存储结构 B.链式存储结构C.索引存储结构D.散列存储结构解析：7.表头和表尾均为空表的广义表是 ( )（分数：2.00）A.()B.() C.()D.()，()解析：8.用二叉链表表示具有 n 个结点的二叉树时，值为空的指针域的个数为 ( )（分数：2.00）A.n-1B.nC.n+1 D.2n解析：9.为便于判别有向图中是否存在回路，可借助于 ( )（分数：2.00）A.广度优先搜索算B.最小生成树算法C.最短路径算D.拓

19、扑排序算法 解析：10.连通网的最小生成树是其所有生成树中 ( )（分数：2.00）A.顶点集最小的生成树B.边集最小的生成树C.顶点权值之和最小的生成树D.边的权值之和最小的生成树 解析：11.按排序过程中依据的原则分类，快速排序属于 ( )（分数：2.00）A.插入类的排序方法B.选择类的排序方法C.交换类的排序方法 D.归并类的排序方法解析：12.下列关键字序列中，构成小根堆的是 ( )（分数：2.00）A.84,46,62,41,28,58,15,37B.84,62,58,46,41,37,28,15C.15,28,46,37,84,41,58,62D.15,28,46,37,84,5

20、8,62,41 解析：13.在长度为 32 的有序表中进行二分查找时，所需进行的关键字比较次数最多为( )（分数：2.00）A.4B.5C.6 D.7解析：14.假设在构建散列表时，采用线性探测解决冲突。若连续插入的 n 个关键字都是同义词，则查找其中最后插入的关键字时，所需进行的比较次数为 ( )（分数：2.00）A.n-1B.n C.n+iD.n+2解析：15.散列文件也称为 ( )（分数：2.00）A.顺序文件B.索引文件C.直接存取文件 D.间接存取文件解析：二、B填空题/B(总题数：10，分数：20.00)16.数据的逻辑结构描述数据元素之间的 1，与存储方式无关。（分数：2.00）

21、填空项 1:_ （正确答案：逻辑关系(或关系)）解析：17.在一个长度为 100 的顺序表中删除第 10 个元素时，需移动 1 个元素。（分数：2.00）填空项 1:_ （正确答案：90）解析：18.队列的队尾位置通常是随着 1 操作而变化的。（分数：2.00）填空项 1:_ （正确答案：入队）解析：19.两个空串联接得到的串的长度为 1。（分数：2.00）填空项 1:_ （正确答案：0）解析：20.设对称矩阵 A 压缩存储在一维数组 B 中，其中矩阵的第一个元素 a11存储在 B0，元素 a52存储在B11，则矩阵元素 a36存储在B 1中。（分数：2.00）填空项 1:_ （正确答案：17

22、）解析：21.已知一棵哈夫曼树含有 60 个叶子结点，则该树中共有 1 个非叶子结点。（分数：2.00）填空项 1:_ （正确答案：59）解析：22.如图所示的有向图中含有_个强连通分量。 （分数：2.00）填空项 1:_ （正确答案：2）解析：23.已知一组关键字为15,36,28,97,24,78,47,52,13,86，其中每相邻两个关键字构成一个有序子序列。对这些子序列进行一趟两两归并的结果是 1。（分数：2.00）填空项 1:_ （正确答案：15,28,36,97,24,47,52,78,13,86）解析：24.从空树起，依次插入关键字 11,27,35,48,52,66 和 73

23、构造所得的二叉排序树，在等概率查找的假设下，查找成功时的平均查找长度为 1。（分数：2.00）填空项 1:_ （正确答案：4）解析：25.控制区间和控制区域是 1 文件的逻辑存储单位。（分数：2.00）填空项 1:_ （正确答案：VSAM）解析：三、B解答题/B(总题数：3，分数：30.00)利用广义表的 head 和 tail 操作，可从广义表 L=(a,b)，(c,d) 中分解得到原子 c，其操作表达式为 head(head(tail(L); 分别写出从下列广义表中分解得到 b 的操作表达式。 (1)L1=(a,b,c,d); (2)L2=(a),(b),(c),(d)。（分数：9.99）

24、(1).（分数：3.33）_正确答案：()解析：(2).（分数：3.33）_正确答案：()解析：head(head(tail(head(L2)_解析：已知有向图 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 的全部拓扑序列。（分数：10.00）(1). （分数：5.00）_正确答案：()解析：(2).（分数：5.00）_正确答案：()解析：a,b,e,c,d a,e,b,c,d e,a,b,c,d已知 3 阶 B-树如图所示。 (1)画出将关键字 88 插入之后的 B-树； (2

25、)画出将关键字 47 和 66 依次插入之后的 B 一树。 （分数：10.00）(1). （分数：5.00）_正确答案：()解析：(2).（分数：5.00）_正确答案：()解析：四、B算法阅读题/B(总题数：4，分数：50.00)假设某个不设头指针的无头结点单向循环链表的长度大于 1，S 为指向链表中某个结点的指针。算法 f30的功能是，删除并返回链表中指针 S 所指结点的前驱。请在空缺处填入合适的内容，使其成为完整的算法。typedef struct node DataType data; struct node *next; *LinkList; DataType f 30(LinkLis

26、t s) LinkList pre,p; DataType e; pre=s; p=snext; while(U (1) /U) pre=p; U (2) /U； prenext=U (3) /U; e=pdata; free(p); return e; （分数：15.00）(1).（分数：5.00）解析：填空项 1:_ （正确答案：p=pnext）解析：填空项 1:_ （正确答案：s(或 pnext)）解析：算法 f31 的功能是清空带头结点的链队列 Q。请在空缺处填入合适的内容，使其成为一个完整的算法。 typedef struct node DataType data; struct n

27、ode *next; QueueNode; typedef struet QueueNode*front; /队头指针 QueueNode*rear; /队尾指针 LinkQueue; void f31(LinkQueue*Q) QueueNode*p,*s; p=U (1) /U; while(P!=NULL) s=p; p=pnext; free(s); U (2) /U=NULL; Qrear=U (3) /U; （分数：15.00）(1).（分数：5.00）解析：填空项 1:_ （正确答案：Qfrontnext）解析：填空项 1:_ （正确答案：Qfront）解析：假设采用动态存储分配

28、的顺序串 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 时， /返回

29、值小于 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);

30、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); （分数：10.00）(1).（分数：5.00）解析：(2).（分数：5.00）_正确答案：()解析：串的置换操作，用串 V 置换串 S 中的子串 T。假设以二叉链表作为二叉树的存储结构，其类型定义如下： typedef struct node char data

31、; struct node*lchild,*rchild; /左右孩子指针 BinTNode,*BinTree; 阅读下列算法 f33，并回答问题： (1)已知如图所示的二叉树以 T 为指向根结点的指针，画出执行 f33(T)后的二叉树； (2)简述算法 f 33 的功能。 void f 33(BinTtee T) if(T) f 33(Tlchild); f 33(Trchild); if(!Tlchild) Trchild=NULL; （分数：10.00）(1).（分数：5.00）解析：(2).（分数：5.00）_正确答案：()解析：对二叉树的每个结点，如果其左孩子为空(右孩子不空)，则将

32、其右孩子设置为左孩子。五、B算法设计题/B(总题数：1，分数：10.00)26.假设以带头结点的单链表表示有序表，单链表的类型定义如下： typedef struct node int data; struct node*next; LinkNode,*LinkList; 编写算法，输入 n 个整数构造一个元素值互不相同的递增有序链表(即相同的整数只取一 个)。算法的函数原型给定为 LinkList f 34(int n);（分数：10.00）_正确答案：()解析：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;