1、数据结构自考题-1 及答案解析(总分：103.00，做题时间：90 分钟)一、单项选择题(总题数：14，分数：28.00)1.设串 s1=“Data Structures、with Java“，s2=“it“，则子串定位函数 index(s1，s2)的值为 ( ) A15 B16 C17 D18（分数：2.00）A.B.C.D.2.下列说法中正确的是( ) A任何一棵二叉树中至少有一个结点的度为 2 B任何一棵二叉树中的每个结点的度为 2 C任何一棵二叉树中的度肯定等于 2 D任何一棵二叉树中的度可以小于 2（分数：2.00）A.B.C.D.3.设矩阵 A(aij,1i,ji0)的元素满足：
2、aij0(ij,1i,j10) aij=O(ij,1i,j10) 现将 A 的所有非 0 元素以行序为主序存放在首地址为 2000 的存储区域中，每个元素占 4 个单元，则元素9,5的首地址为( ) A2160 B2164 C2336 D2340（分数：2.00）A.B.C.D.4.下列说法中正确的是( ) A二叉树中任何一个结点的度都为 2 B二叉树的度为 2 C任何一棵二叉树中至少有一个结点的度为 2 D一棵二叉树的度可以小于 2（分数：2.00）A.B.C.D.5.下面的程序在执行时，S 语句共被执行了( )次。 i=1; while(i=n) for(j=i;jn;j+) S ; i=
3、i+1; （分数：2.00）A.B.C.D.6.若进栈序列为 1,2,3,4,5,6，且进栈和出栈可以穿插进行，则可能出现的出栈序列为( ) A3,2,6,1,4,5 B3,4,2,1,6,5 C1,2,5,3,4,6 D5,6,4,2,3,1（分数：2.00）A.B.C.D.7.在一个具有 N 个顶点的无向完全图中，包含的边的总数是( ) AN(N-1)/2 BN(N-1) CN(N+1) DN(N+1)/2（分数：2.00）A.B.C.D.8.在计算机内实现递归算法时所需的辅助数据结构是 ( ) A栈 B队列 C树 D图（分数：2.00）A.B.C.D.9.假设以数组 An存放循环队列的元
4、素，其头指针 front 指向队头元素的前一个位置、尾指针 rear 指向队尾元素所在的存储位置，则在少用一个元素空间的前提下，队列满的判定条件为 ( ) Arear=front B(front+1)%n=rear Crear+1=front D(rear+1)%n=front（分数：2.00）A.B.C.D.10.考虑下列四种排序方法，在排序过程中，关键码比较的次数与记录的初始排列顺序无关的是( ) A直接插入排序和快速排序 B快速排序和归并排序 C直接选择排序和归并排序 D直接插入排序和归并排序（分数：2.00）A.B.C.D.11.C 语言数组 Datam+1作为循环队列 SQ 的存储空
5、间，front 为队头指针，rear 为队尾指针，则执行出队操作的语句为( ) Afront=front+1 Bfront=(front+1)%m Crear=(rear+1)%m Dfront=(front+1)%(m+1)（分数：2.00）A.B.C.D.12.考虑下列四种排序方法，在排序过程中，关键码比较的次数与记录的初始排列顺序无关的是( ) A直接插入排序和快速排序 B快速排序和归并排序 C直接选择排序和归并排序 D直接插入排序和归并排序（分数：2.00）A.B.C.D.13.线索二叉树是一种( )结构。 A物理 B逻辑 C存储 D线性（分数：2.00）A.B.C.D.14.在单链表
6、中，删除 p 所指结点的直接后继的操作是 ( ) Apnext=pnextnext; Bp=pnext;pnext=pnextnext; Cpnext=pnext; Dp=pnextnext;（分数：2.00）A.B.C.D.二、填空题(总题数：10，分数：20.00)15. 1 查找法的平均查找长度与元素个数 n 无关。（分数：2.00）填空项 1:_16.设树 T 的度为 4，其中度为 1、2、3 和 4 的结点个数分别是 4、2、1 和 1，则 T 中叶子结点的个数是： 1。（分数：2.00）填空项 1:_17.N 个顶点的连通图，至少有 1 条边。（分数：2.00）填空项 1:_18.
7、ISAM 文件由主索引、_、_和主文件组成。（分数：2.00）填空项 1:_19.在分块查找法中，首先查找 1，然后再查找相应的 2。（分数：2.00）填空项 1:_20.如果我们定义一个长度为 N 的串空间，则它最多能放 1 个字符。（分数：2.00）填空项 1:_21.若对关键字序列(43,02,80,48,26,57,15,73,21,24,66)进行一趟增量为 3 的希尔排序，则得到的结果为 1。（分数：2.00）填空项 1:_22.内部排序的方法可以分为五类：_、_、_、_、_。（分数：2.00）填空项 1:_23.广义表的深度是指 1。（分数：2.00）填空项 1:_24.产生冲突
8、现象的两个关键字称为该散列函数的 1。（分数：2.00）填空项 1:_三、解答题(总题数：4，分数：20.00)25.已知有一关键字序列为 505,94,512,61,908,170,897,275,653,463)，如果我们采用快速法对此序列进行排序(按照升序排序)，请给出每一趟排序的结果。（分数：5.00）_26.已知有一关键字序列为 486,79,596,34,900,120,789,179,703,307)，如果我们采用基数排序方法对此序列进行排序(按照升序排列)，请给出每一趟的排序结果。（分数：5.00）_27.对于下面用三元组表示的稀疏矩阵，请分别写出它们所对应的稀疏矩阵。 （分数
9、：5.00）_28.假设有一个长度为 n 的有序序列，在进行查找时，可以借助二叉树来进行，请结合二叉树的性质来分析二分查找的最坏性能和平均性能。（分数：5.00）_四、算法阅读题(总题数：3，分数：25.00)29.求下面算法中变量 count 的值：(假设 n 为 2 的乘幂，并且 n2) int Time int n count=0;x=2; while(xn/2) x*=2;count+; return(count) （分数：5.00）_阅读下列算法，并回答问题： (1)设串 s=“OneWorldOneDream“，t=“One“，pos 是一维整型数组，写出算法 f32(s,t,po
10、s)执行之后得到的返回值和 pos 中的值； (2)简述算法 f32 的功能。 int strlen(char*s); /*返回串 S 的长度*/ 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+i
11、t; while(i+it=is return k; （分数：10.00）_阅读下列算法，并回答问题： （分数：10.00）填空项 1:_五、算法设计题(总题数：1，分数：10.00)30.二叉排序树的类型定义如下： typedef struet BSTNode/二叉排序树的结点结构 int data; /数据域 struct BSTNode*lchild,*rchild;/左、右孩子指针 BSTNode,*BSTree; 设计递归算法，统计一棵二叉排序树 T 中值小于 a 的结点个数。（分数：10.00）_数据结构自考题-1 答案解析(总分：103.00，做题时间：90 分钟)一、单项选择题
12、(总题数：14，分数：28.00)1.设串 s1=“Data Structures、with Java“，s2=“it“，则子串定位函数 index(s1，s2)的值为 ( ) A15 B16 C17 D18（分数：2.00）A.B.C. D.解析：2.下列说法中正确的是( ) A任何一棵二叉树中至少有一个结点的度为 2 B任何一棵二叉树中的每个结点的度为 2 C任何一棵二叉树中的度肯定等于 2 D任何一棵二叉树中的度可以小于 2（分数：2.00）A.B.C.D. 解析：3.设矩阵 A(aij,1i,ji0)的元素满足： aij0(ij,1i,j10) aij=O(ij,1i,j10) 现将
13、A 的所有非 0 元素以行序为主序存放在首地址为 2000 的存储区域中，每个元素占 4 个单元，则元素9,5的首地址为( ) A2160 B2164 C2336 D2340（分数：2.00）A. B.C.D.解析：4.下列说法中正确的是( ) A二叉树中任何一个结点的度都为 2 B二叉树的度为 2 C任何一棵二叉树中至少有一个结点的度为 2 D一棵二叉树的度可以小于 2（分数：2.00）A.B.C.D. 解析：5.下面的程序在执行时，S 语句共被执行了( )次。 i=1; while(i=n) for(j=i;jn;j+) S ; i=i+1; （分数：2.00）A. B.C.D.解析：6.
14、若进栈序列为 1,2,3,4,5,6，且进栈和出栈可以穿插进行，则可能出现的出栈序列为( ) A3,2,6,1,4,5 B3,4,2,1,6,5 C1,2,5,3,4,6 D5,6,4,2,3,1（分数：2.00）A.B. C.D.解析：7.在一个具有 N 个顶点的无向完全图中，包含的边的总数是( ) AN(N-1)/2 BN(N-1) CN(N+1) DN(N+1)/2（分数：2.00）A. B.C.D.解析：8.在计算机内实现递归算法时所需的辅助数据结构是 ( ) A栈 B队列 C树 D图（分数：2.00）A. B.C.D.解析：9.假设以数组 An存放循环队列的元素，其头指针 front
15、 指向队头元素的前一个位置、尾指针 rear 指向队尾元素所在的存储位置，则在少用一个元素空间的前提下，队列满的判定条件为 ( ) Arear=front B(front+1)%n=rear Crear+1=front D(rear+1)%n=front（分数：2.00）A.B.C.D. 解析：解析 在循环队列中，在少用一个元素空间的前提下，可约定入队前，测试尾指针在循环意义下加 1 后是否等于头指针，若相等则认为队满。10.考虑下列四种排序方法，在排序过程中，关键码比较的次数与记录的初始排列顺序无关的是( ) A直接插入排序和快速排序 B快速排序和归并排序 C直接选择排序和归并排序 D直接插
16、入排序和归并排序（分数：2.00）A.B.C. D.解析：11.C 语言数组 Datam+1作为循环队列 SQ 的存储空间，front 为队头指针，rear 为队尾指针，则执行出队操作的语句为( ) Afront=front+1 Bfront=(front+1)%m Crear=(rear+1)%m Dfront=(front+1)%(m+1)（分数：2.00）A.B.C.D. 解析：12.考虑下列四种排序方法，在排序过程中，关键码比较的次数与记录的初始排列顺序无关的是( ) A直接插入排序和快速排序 B快速排序和归并排序 C直接选择排序和归并排序 D直接插入排序和归并排序（分数：2.00）A
17、.B.C. D.解析：13.线索二叉树是一种( )结构。 A物理 B逻辑 C存储 D线性（分数：2.00）A. B.C.D.解析：14.在单链表中，删除 p 所指结点的直接后继的操作是 ( ) Apnext=pnextnext; Bp=pnext;pnext=pnextnext; Cpnext=pnext; Dp=pnextnext;（分数：2.00）A. B.C.D.解析：二、填空题(总题数：10，分数：20.00)15. 1 查找法的平均查找长度与元素个数 n 无关。（分数：2.00）填空项 1:_ （正确答案：散列表）解析：16.设树 T 的度为 4，其中度为 1、2、3 和 4 的结点
18、个数分别是 4、2、1 和 1，则 T 中叶子结点的个数是： 1。（分数：2.00）填空项 1:_ （正确答案：8 个）解析：17.N 个顶点的连通图，至少有 1 条边。（分数：2.00）填空项 1:_ （正确答案：N1）解析：18.ISAM 文件由主索引、_、_和主文件组成。（分数：2.00）填空项 1:_ （正确答案：柱面索引 磁道索引）解析：19.在分块查找法中，首先查找 1，然后再查找相应的 2。（分数：2.00）填空项 1:_ （正确答案：索引表块）解析：20.如果我们定义一个长度为 N 的串空间，则它最多能放 1 个字符。（分数：2.00）填空项 1:_ （正确答案：N1）解析：2
19、1.若对关键字序列(43,02,80,48,26,57,15,73,21,24,66)进行一趟增量为 3 的希尔排序，则得到的结果为 1。（分数：2.00）填空项 1:_ （正确答案：15,02,21,24,26,57,43,66,80,48,73）解析：22.内部排序的方法可以分为五类：_、_、_、_、_。（分数：2.00）填空项 1:_ （正确答案：插入排序 选择排序 交换排序 归并排序 分配排序）解析：23.广义表的深度是指 1。（分数：2.00）填空项 1:_ （正确答案：广义表展开后所含括号的最大层数）解析：24.产生冲突现象的两个关键字称为该散列函数的 1。（分数：2.00）填空项
20、 1:_ （正确答案：同义词）解析：三、解答题(总题数：4，分数：20.00)25.已知有一关键字序列为 505,94,512,61,908,170,897,275,653,463)，如果我们采用快速法对此序列进行排序(按照升序排序)，请给出每一趟排序的结果。（分数：5.00）_正确答案：(快速排序采用分治法进行，其基本思想如下：将原问题分解成为若干个规模更小但结构和原问题相似的子问题，递归地解这些子问题，然后将这些子问题的解的组合为原问题的解，根据上述思想，我们可以得到如下快速排序的各趟结果如下： 初始：505,94,512,61,908,170,897,275,653,432 第 1 趟：
21、462,94,295,61,170505897,908,653,512 第 2 趟：170,94,295,61462,505897,908,653,512 第 3 趟：61,94170275462,505897,908,653,512 第 4 趟：6194170275462,505897,908,653,512 第 5 趟：61,94,170,275,462,505897,908,653,512 第 6 趟：61,94,170,275,462,505897,908,653,512 第 7 趟：61,94,170,275,462,505512,653897908 第 8 趟：61,94,170,
22、275,462,505,512653897908 第 9 趟：61,94,170,275,462,505,512,653,897908 第 10 趟：61,94,170,275,462,505,512,653,897,908)解析：26.已知有一关键字序列为 486,79,596,34,900,120,789,179,703,307)，如果我们采用基数排序方法对此序列进行排序(按照升序排列)，请给出每一趟的排序结果。（分数：5.00）_正确答案：(基数排序的基本思想是：从低位到高位依次对 kj(j=d-1，d-20)进行箱排序，根据基数排序法的基本方法，我们得到如下的排序结果： 初始：486,
23、79,596,34,900,120,789,179,703,307 第 1 趟：(按个位进行排序)：120,900,703,34,486,596,307,79,179,389 第 2 趟：(按十位进行排序)：307,703,900,120,34,79,179,486,789,596 第 3 趟：(按百位进行排序)：34,79,120,179,307,486,596,703,789,900)解析：27.对于下面用三元组表示的稀疏矩阵，请分别写出它们所对应的稀疏矩阵。 （分数：5.00）_正确答案：(从三元组表还原稀疏矩阵时，首先根据表的第 1 行得出稀疏矩阵的行数和列数，否则，我们无法确定所求的
24、稀疏矩阵的维数，然后根据三元组表所提供的行号和列号在稀疏矩阵的对应位置上写上相应的元素的值，在其他地方补零即可，根据上述原则，此题答案如图(1)，(2)所示。 )解析：28.假设有一个长度为 n 的有序序列，在进行查找时，可以借助二叉树来进行，请结合二叉树的性质来分析二分查找的最坏性能和平均性能。（分数：5.00）_正确答案：(假设判定树的内部结点的总数为 n=2h-1。则判定树是深度为 h=lg(n+1)的满二叉树，树中第k 层上的结点的个数为 2h-1，查找它们所需要比较的次数是 k。则在等概率下，二分查找成功时的平均查找长度为： )解析：四、算法阅读题(总题数：3，分数：25.00)29
25、.求下面算法中变量 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)解析：阅读下列算法，并回答问题： (1)设串 s=“OneWorldOneDream“，t=“One“，pos 是一维整型数组，写出算法 f32(s,t,pos)执行之后得到的返回值和 pos 中的值； (2)简述算法 f32 的功能。 int strlen(char*s); /*返回串 S 的长度*/ int index(c
26、har*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）_正确答案：(2；pos0=0，pos1=8)解析：_正确答案：(返回串 t 在 S 中出现的次
27、数，并将每次出现的位置依次存放在数组 pos 中。)解析：阅读下列算法，并回答问题： （分数：10.00）填空项 1:_ （正确答案：3）解析：_正确答案：(返回无向图 g 中连通分量的个数。)解析：五、算法设计题(总题数：1，分数：10.00)30.二叉排序树的类型定义如下： typedef struet BSTNode/二叉排序树的结点结构 int data; /数据域 struct BSTNode*lchild,*rchild;/左、右孩子指针 BSTNode,*BSTree; 设计递归算法，统计一棵二叉排序树 T 中值小于 a 的结点个数。（分数：10.00）_正确答案：(P 71)参
28、考答案之一： void count(BSTree T,int a,int*sum) /以 sum 所指单元统计二叉排序树中元素值小于 a 的结点个数，其初值为 0 if(T) count(Tlchild,a,sum); if(Tdataa)(*sum)+; count(Trchild,a,sum); 参考答案之二： int count(BSTree T,int a) /统计二又排序树中元素值小于 a 的结点个数 int sum; if(!T)return 0; else sum=count(Tlchild,a); if(Tdataa) return sum+1+count(Trchild,a); else return sum; )解析：
