1、数据结构自考题-10 及答案解析(总分：100.00，做题时间：90 分钟)一、单项选择题(总题数：15，分数：30.00)1.当初始序列已经按键值有序时，用直接插入算法进行排序，需要比较的次数为 ( ) An 2 Bnlona n Clog2 n Dn-1（分数：2.00）A.B.C.D.2.长度为 12 的按关键字有序的查找表采用顺序组织方式。若采用二分查找方法，则在等概率情况下，查找失败时的 ASL 值是( ) A37/12 B62/13 C39/12 D49/13（分数：2.00）A.B.C.D.3.对广义表(a)，(b)进行下面的操作 head(head(a)，(b)后的结果是( )
2、 Aa B(a) C( ) D不确定（分数：2.00）A.B.C.D.4.顺序存储结构 ( ) A仅适合于静态查找表的存储 B仅适合干动态查找表的存储 C既适合静态又适合动态查找表的存储 D既不适合静态又不适合动态查找表的存储（分数：2.00）A.B.C.D.5.将含有 83 个结点的完全二叉树从根结点开始编号，根为 1 号，后面按从上到下、从左到右的顺序对结点编号，那么编号为 41 的结点的双亲结点编号为( ) A42 B40 C21 D20（分数：2.00）A.B.C.D.6.非空的单循环链表 L 的尾结点 P，满足( ) AP.next=NULL; BP=NULL; CP.next=L;
3、 DP=L（分数：2.00）A.B.C.D.7.对长度为 n 的关键字序列进行堆排序的空间复杂度为 ( )AO(log 2n) BO(1) CO(n) DO(n*log 2n)（分数：2.00）A.B.C.D.8.堆排序的最坏时间复杂度为( ) AO(n) BO(10g 2n) CO(nlog 2n) DO(n 2)（分数：2.00）A.B.C.D.9.在线性表的下列运算中，不改变数据元素之间结构关系的运算是 ( ) A插入 B删除 C排序 D定位（分数：2.00）A.B.C.D.10.深度为 k 的二叉树，所含叶子的个数最多为( ) A2K BK C2K-1 D2K-1（分数：2.00）A.
4、B.C.D.11.对关键字序列(6,1,4,3,7,2,8,5)进行快速排序时，以第 1 个元素为基准的一次划分的结果为 ( ) A(5,1,4,3,6,2,8,7) B(5,1,4,3,2,6,7,8) C(5,1,4,3,2,6,8,7) D(8,7,6,5,4,3,2,1)（分数：2.00）A.B.C.D.12.一个具有 N 个顶点的有向图最多有( )条边。 AN(N-1)/2 BN(N-1) CN(N+1) DN(N+1)/2（分数：2.00）A.B.C.D.13.通常要求同一逻辑结构中的所有数据元素具有相同的特性，这意味着( ) A数据元素具有同一特点 B不仅数据元素所包含的数据项的
5、个数要相同，而且对应数据项的类型要一致 C每个数据元素都一样 D数据元素所包含的数据项的个数要相等（分数：2.00）A.B.C.D.14.采用分治法进行排序的方法是( ) A快速排序 B插入排序 C堆排序 D希尔排序（分数：2.00）A.B.C.D.15.下列说法中正确的是( ) A二叉树中任何一个结点的度都为 2 B二叉树的度为 2 C任何一棵二叉树中至少有一个结点的度为 2 D一棵二叉树的度可以小于 2（分数：2.00）A.B.C.D.二、填空题(总题数：10，分数：20.00)16.一个字符串相等的充要条件是_和_。（分数：2.00）填空项 1:_17.当所有结点的权值都相等时，用这些结
6、点构造的二叉排序树上只有 1。（分数：2.00）填空项 1:_18.假设散列文件中一个桶能存放 m 个记录，则桶“溢出”的含义是，当需要插入新的记录时，该桶中 1。（分数：2.00）填空项 1:_19.数组的长度是_，线性表的长度是_。（分数：2.00）填空项 1:_20.对表长为 9000 的索引顺序表进行分块查找，假设每一块的长度均为 15，且以顺序查找确定块，则在各记录的查找概率均相等的情况下，其查找成功的平均查找长度为 1。（分数：2.00）填空项 1:_21.多维数组和广义表是一种非常复杂的非线性结构，它们的逻辑特点是 1。（分数：2.00）填空项 1:_22.假设以列优先顺序存储二
7、维数组 A58，其中元素 A00的存储地址为 LOC(a00)，且每个元素占 4个存储单元，则数组元素 Aij的存储地址为 1 。（分数：2.00）填空项 1:_23.一棵含 999 个结点的完全二叉树的深度为 1。（分数：2.00）填空项 1:_24.控制区间和控制区域是 1 文件的逻辑存储单位。（分数：2.00）填空项 1:_25.对于数组，通常具有的基本操作有_种，它们分别是_。（分数：2.00）填空项 1:_三、解答题(总题数：4，分数：20.00)26.对于下面用三元组表示的稀疏矩阵，请分别写出它们所对应的稀疏矩阵。 （分数：5.00）_27.图的邻接表的类型定义如下所示： #def
8、ine MaxVertexNum 50 typedef struct node int adjvex; struct node*next; EdgeNode; typedef struct VertexType vertex; EdgeNode*firstedge; VertexNode; typedef VertexNode A djListMaxVertexNum; typedef struct AdjList adjiist; int n,e; ALGraph; 为便于删除和插入图的顶点的操作，可将邻接表的表头向量定义为链式结构，两种定义的存储表示实例如下图所示，请写出重新定义的类型说明
9、。 （分数：5.00）_28.假设有一个长度为 n 的有序序列，在进行查找时，可以借助二叉树来进行，请结合二叉树的性质来分析二分查找的最坏性能和平均性能。（分数：5.00）_29.某类物品的编号由一个大写英文字母及 2 位数字(09)组成，形如 E32。运用基数排序对下列物品编号序列进行按字典序的排序，写出每一趟(分配和收集)后的结果。 E13,A37,F43,B32,B47,E12,F37,B12 第一趟： 第二趟： 第三耥：（分数：5.00）_四、算法阅读题(总题数：3，分数：20.00)30.求下面算法中变量 count 的值：(假设 n 为 2 的乘幂，并且 n2) int Time
10、int n count=0;x=2; while(xn/2) x*=2;count+; return(count) （分数：5.00）_31.请将下面的程序改成递归的过程。 voide ditui(int n) int i; i=n; while(i1) prinft(i-); （分数：5.00）_阅读下列算法，并回答问题： (1)设串 s=“OneWorldOneDream“，t=“One“，pos 是一维整型数组，写出算法 f32(s,t,pos)执行之后得到的返回值和 pos 中的值； (2)简述算法 f32 的功能。 int strlen(char*s); /*返回串 S 的长度*/
11、int index(char*st，char*t); /*若串 t 在串 st 中出现，则返回在串 st 中首次出现的下标值，否则返回-1*/ int f32(char*s,char*t,int pos) int i,j,k,ls,It; Is=strlen(s); lt=strlen(t); if(ls=0| It=0)return-1; k=0; i=0; do j=index(s+i,t); if(j=0) posk+=i+j; i+=j+it; while(i+it=is return k; （分数：10.00）_五、算法设计题(总题数：1，分数：10.00)32.有两个磁盘文件 A、
12、B，各存放一行字母，要求把这两个文件中的信息按字母顺序排列合并，输出到一个新文件 C 中。（分数：10.00）_数据结构自考题-10 答案解析(总分：100.00，做题时间：90 分钟)一、单项选择题(总题数：15，分数：30.00)1.当初始序列已经按键值有序时，用直接插入算法进行排序，需要比较的次数为 ( ) An 2 Bnlona n Clog2 n Dn-1（分数：2.00）A.B.C.D. 解析：2.长度为 12 的按关键字有序的查找表采用顺序组织方式。若采用二分查找方法，则在等概率情况下，查找失败时的 ASL 值是( ) A37/12 B62/13 C39/12 D49/13（分数
13、：2.00）A.B. C.D.解析：3.对广义表(a)，(b)进行下面的操作 head(head(a)，(b)后的结果是( ) Aa B(a) C( ) D不确定（分数：2.00）A. B.C.D.解析：4.顺序存储结构 ( ) A仅适合于静态查找表的存储 B仅适合干动态查找表的存储 C既适合静态又适合动态查找表的存储 D既不适合静态又不适合动态查找表的存储（分数：2.00）A.B.C. D.解析：5.将含有 83 个结点的完全二叉树从根结点开始编号，根为 1 号，后面按从上到下、从左到右的顺序对结点编号，那么编号为 41 的结点的双亲结点编号为( ) A42 B40 C21 D20（分数：2
14、.00）A.B.C.D. 解析：6.非空的单循环链表 L 的尾结点 P，满足( ) AP.next=NULL; BP=NULL; CP.next=L; DP=L（分数：2.00）A.B.C. D.解析：7.对长度为 n 的关键字序列进行堆排序的空间复杂度为 ( )AO(log 2n) BO(1) CO(n) DO(n*log 2n)（分数：2.00）A.B. C.D.解析：解析 由于建初始堆所需的比较次数较多，所以堆排序不适宜于记录数较少的文件。堆排序是就地排序，辅助空间为 0(1)，但它是不稳定的。8.堆排序的最坏时间复杂度为( ) AO(n) BO(10g 2n) CO(nlog 2n)
15、DO(n 2)（分数：2.00）A.B.C. D.解析：9.在线性表的下列运算中，不改变数据元素之间结构关系的运算是 ( ) A插入 B删除 C排序 D定位（分数：2.00）A.B.C.D. 解析：10.深度为 k 的二叉树，所含叶子的个数最多为( ) A2K BK C2K-1 D2K-1（分数：2.00）A.B.C. D.解析：11.对关键字序列(6,1,4,3,7,2,8,5)进行快速排序时，以第 1 个元素为基准的一次划分的结果为 ( ) A(5,1,4,3,6,2,8,7) B(5,1,4,3,2,6,7,8) C(5,1,4,3,2,6,8,7) D(8,7,6,5,4,3,2,1)
16、（分数：2.00）A.B.C. D.解析：12.一个具有 N 个顶点的有向图最多有( )条边。 AN(N-1)/2 BN(N-1) CN(N+1) DN(N+1)/2（分数：2.00）A.B. C.D.解析：13.通常要求同一逻辑结构中的所有数据元素具有相同的特性，这意味着( ) A数据元素具有同一特点 B不仅数据元素所包含的数据项的个数要相同，而且对应数据项的类型要一致 C每个数据元素都一样 D数据元素所包含的数据项的个数要相等（分数：2.00）A.B. C.D.解析：14.采用分治法进行排序的方法是( ) A快速排序 B插入排序 C堆排序 D希尔排序（分数：2.00）A. B.C.D.解析
17、：15.下列说法中正确的是( ) A二叉树中任何一个结点的度都为 2 B二叉树的度为 2 C任何一棵二叉树中至少有一个结点的度为 2 D一棵二叉树的度可以小于 2（分数：2.00）A.B.C.D. 解析：二、填空题(总题数：10，分数：20.00)16.一个字符串相等的充要条件是_和_。（分数：2.00）填空项 1:_ （正确答案：两个字符串的长度相等 对应位置的字符相等）解析：17.当所有结点的权值都相等时，用这些结点构造的二叉排序树上只有 1。（分数：2.00）填空项 1:_ （正确答案：右子树）解析：18.假设散列文件中一个桶能存放 m 个记录，则桶“溢出”的含义是，当需要插入新的记录时
18、，该桶中 1。（分数：2.00）填空项 1:_ （正确答案：已有 m 个同义词的记录(或：已有 m 个记录；或：已满)）解析：19.数组的长度是_，线性表的长度是_。（分数：2.00）填空项 1:_ （正确答案：固定的 可变的）解析：20.对表长为 9000 的索引顺序表进行分块查找，假设每一块的长度均为 15，且以顺序查找确定块，则在各记录的查找概率均相等的情况下，其查找成功的平均查找长度为 1。（分数：2.00）填空项 1:_ （正确答案：308.5）解析：21.多维数组和广义表是一种非常复杂的非线性结构，它们的逻辑特点是 1。（分数：2.00）填空项 1:_ （正确答案：一个数据元素可能
19、有多个直接前趋和多个直接后继）解析：22.假设以列优先顺序存储二维数组 A58，其中元素 A00的存储地址为 LOC(a00)，且每个元素占 4个存储单元，则数组元素 Aij的存储地址为 1 。（分数：2.00）填空项 1:_ （正确答案：LOC(a 00)+4(5j+i)）解析：23.一棵含 999 个结点的完全二叉树的深度为 1。（分数：2.00）填空项 1:_ （正确答案：10）解析：24.控制区间和控制区域是 1 文件的逻辑存储单位。（分数：2.00）填空项 1:_ （正确答案：VSAM）解析：25.对于数组，通常具有的基本操作有_种，它们分别是_。（分数：2.00）填空项 1:_ （
20、正确答案：两 查找和修改）解析：三、解答题(总题数：4，分数：20.00)26.对于下面用三元组表示的稀疏矩阵，请分别写出它们所对应的稀疏矩阵。 （分数：5.00）_正确答案：(从三元组表还原稀疏矩阵时，首先根据表的第 1 行得出稀疏矩阵的行数和列数，否则，我们无法确定所求的稀疏矩阵的维数，然后根据三元组表所提供的行号和列号在稀疏矩阵的对应位置上写上相应的元素的值，在其他地方补零即可，根据上述原则，此题答案如图(1)，(2)所示。 )解析：27.图的邻接表的类型定义如下所示： #define MaxVertexNum 50 typedef struct node int adjvex; str
21、uct node*next; EdgeNode; typedef struct VertexType vertex; EdgeNode*firstedge; VertexNode; typedef VertexNode A djListMaxVertexNum; typedef struct AdjList adjiist; int n,e; ALGraph; 为便于删除和插入图的顶点的操作，可将邻接表的表头向量定义为链式结构，两种定义的存储表示实例如下图所示，请写出重新定义的类型说明。 （分数：5.00）_正确答案：(typeclef struct ArcNode VNode*adjvex;
22、 /该弧所指向的顶点的位置 struct ArcNode*nextarc; /指向下一条弧的指针 ArcNode; typedef struct VNode VertexType data; /顶点信息 struct VNode*nextVertex; /指向下一个顶点的指针 ArcNode*firstarc; /指向第一条依附该顶点的弧 VNode.*AdjList; typedef struct AdjList adjList; int n,e; ALGraph;)解析：28.假设有一个长度为 n 的有序序列，在进行查找时，可以借助二叉树来进行，请结合二叉树的性质来分析二分查找的最坏性能和
23、平均性能。（分数：5.00）_正确答案：(假设判定树的内部结点的总数为 n=2h-1。则判定树是深度为 h=lg(n+1)的满二叉树，树中第k 层上的结点的个数为 2h-1，查找它们所需要比较的次数是 k。则在等概率下，二分查找成功时的平均查找长度为： )解析：29.某类物品的编号由一个大写英文字母及 2 位数字(09)组成，形如 E32。运用基数排序对下列物品编号序列进行按字典序的排序，写出每一趟(分配和收集)后的结果。 E13,A37,F43,B32,B47,E12,F37,B12 第一趟： 第二趟： 第三耥：（分数：5.00）_正确答案：(第一趟：B32,E12,B12,E13,F43,
24、A37,B47,F37 第二趟：E12,B12,E13,B32,A37,F37,F43,B47 第三趟：A37,B12,B32,B47,E12,E13,F37,F43)解析：四、算法阅读题(总题数：3，分数：20.00)30.求下面算法中变量 count 的值：(假设 n 为 2 的乘幂，并且 n2) int Time int n count=0;x=2; while(xn/2) x*=2;count+; return(count) （分数：5.00）_正确答案：(count=log 2n)解析：31.请将下面的程序改成递归的过程。 voide ditui(int n) int i; i=n;
25、 while(i1) prinft(i-); （分数：5.00）_正确答案：(此递推过程可以改写成如下递归过程： voide dkui(int j) if(i1) prind(j); digui(j-1); )解析：阅读下列算法，并回答问题： (1)设串 s=“OneWorldOneDream“，t=“One“，pos 是一维整型数组，写出算法 f32(s,t,pos)执行之后得到的返回值和 pos 中的值； (2)简述算法 f32 的功能。 int strlen(char*s); /*返回串 S 的长度*/ int index(char*st，char*t); /*若串 t 在串 st 中出
26、现，则返回在串 st 中首次出现的下标值，否则返回-1*/ int f32(char*s,char*t,int pos) int i,j,k,ls,It; Is=strlen(s); lt=strlen(t); if(ls=0| It=0)return-1; k=0; i=0; do j=index(s+i,t); if(j=0) posk+=i+j; i+=j+it; while(i+it=is return k; （分数：10.00）_正确答案：(2；pos0=0，pos1=8)解析：_正确答案：(返回串 t 在 S 中出现的次数，并将每次出现的位置依次存放在数组 pos 中。)解析：五、
27、算法设计题(总题数：1，分数：10.00)32.有两个磁盘文件 A、B，各存放一行字母，要求把这两个文件中的信息按字母顺序排列合并，输出到一个新文件 C 中。（分数：10.00）_正确答案：(可先分别将 A、B 文件的内容读出放到数组 C 中，再对数组 C 排序，最后再将数组内容写到文件 C 中，程序为： #includestdio.h main() /*合并 A、B 文件内容到 C 文件中*/ FILE*fp; int i,j,n,m; char c160,t,ch; if(fp=fopen(“A“,“r“)=Null) printf(“文件 A cant open/n“); exit(0)
28、; else printf(“/n 文件 A 的内容为/n“) for(i=0;(ch=fgetc(fp)!=EOF:i+) Ci=oh; putchar(C-i); fclose(fp); m=i; if(fp=fopen(“B“,“r“)=Null) printf(“B 文件 cant open/n“); exit(0); else printf(“/nB 文件内容是/n“); for(i=m;(ch=fgetc(fp)!=EOF;i+) Ci=ch; putchar(i); fclose(fp); n=i;/*排序*/ for(i=0;in;i+) for(j=i+1;jm,j+) if(Cicj) t=ci; ci=cj; cj=t; printf(“/nC 文件是/n“); fp=fopen(“c“,“w“) /* 写入 C 文件中*/ for(i=0;im;i+) putchar(ci,fp); putchar(ci); fclose(fp); /*main*/)解析：
