1、数据结构自考题-5 及答案解析(总分：110.00，做题时间：90 分钟)一、单项选择题(总题数：15，分数：30.00)1.对含有( )个结点的非空二叉树，采用任何一种遍历方式，其结点访问序列均相同。 AO B1 C2 D不存在这样的二叉树（分数：2.00）A.B.C.D.2.以下有关数据结构的叙述，正确的是 ( ) A线性表的线性存储结构优于链式存储结构 B二叉树的第 i 层上有 2i-1个结点，深度为 K 的二叉树上有 2k-1个结点 C二维数组是其数据元素为线性表的线性表 D栈的操作方式是先进先出（分数：2.00）A.B.C.D.3.对一棵非空二叉树进行中序遍历，则根结点的左边( )
2、A只有左子树上的所有结点 B只有右子树上的所有结点 C只有左子树上的部分结点 D只有右子树上的部分结点（分数：2.00）A.B.C.D.4.已知二叉树的中序序列和后序序列均为 ABCDEF，则该二叉树的先序序列为 ( ) AFEDCBA BABCDEF CFDECBA DFBDCEA（分数：2.00）A.B.C.D.5.树最适合用来表示( ) A有序数据元素 B无序数据元素 C元素之间具有分支层次关系的数据 D元素之间无联系的数据（分数：2.00）A.B.C.D.6.设 rear 是指向非空带头结点的循环单链表的尾指针，则删除起始结点的操作可表示为( ) As=rear; Brear=rear
3、next; rear=rearnext; free(rear); free(s); Crear=rearnextnext; Ds=rearnextnext; free(rear); rearnextnext=snext; free(s);（分数：2.00）A.B.C.D.7.判断一个有向图是否存在回路，除了可以利用拓扑排序方法，还可以利用( ) A求关键路径的方法 B求最短路径的 Dijkstra 方法 C广度优先遍历方法 D深度优先遍历方法（分数：2.00）A.B.C.D.8.线索二叉树是一种( )结构。 A物理 B逻辑 C存储 D线性（分数：2.00）A.B.C.D.9.用二叉链表表示具有
4、 n 个结点的二叉树时，值为空的指针域的个数为 ( ) An-1 Bn Cn+1 D2n（分数：2.00）A.B.C.D.10.对关键字序列(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.11.如果我们采用二分查找法查找一个长度为 n 的有序表，则查找每个元素的平均比较次数( )对应的判定树的高度(假设树高 h2)。 A大于 B小于 C等于 D无法确定（分数：2
5、.00）A.B.C.D.12.在一个单链表中，已知 q 所指结点是 p 所指结点的直接前趋，若在 p，q 之间插入 s 结点，则执行( )操作。 Asnext=pnext;pnext=s; Bqnext=s;snext=p; Cpnext=snext;snext=p; Dpnext=s;snext=q;（分数：2.00）A.B.C.D.13.用数组 A0N-1存放循环队列的元素值，若其头尾指针分别为 front 和 rear，则循环队列中当前元素的个数为( ) A(rear-front+m)mod m B(rear-front+1)mod m C(rear-front-1+m)mod m D(
6、rear-front)mod m（分数：2.00）A.B.C.D.14.若用邻接矩阵表示一个有向图，则其中每一列包含的“1“的个数为 ( ) A图中每个顶点的入度 B图中每个顶点的出度 C图中弧的条数 D图中连通分量的数目（分数：2.00）A.B.C.D.15.下面程序段的时间复杂度为 ( ) for(i=0;im;i+) for(j=0;jn;j+) Aij=i*j; AO(m 2) BO(n 2) CO(m*n) DO(m+n)（分数：2.00）A.B.C.D.二、填空题(总题数：10，分数：20.00)16.广义表的深度是指 1。（分数：2.00）填空项 1:_17.有 m 个叶子结点(
7、又称外结点)的哈夫曼树，其结点总数是 1。（分数：2.00）填空项 1:_18.带有一个头结点的单链表 head 为空的条件是 1。（分数：2.00）填空项 1:_19.常用的索引顺序文件是_文件和_文件。（分数：2.00）填空项 1:_20.任意一棵具有 n 个结点的二叉树，若它有 m 个叶子，则该二叉树上度数为 1 的结点为 1 个。（分数：2.00）填空项 1:_21.散列函数的作用是： 1。（分数：2.00）填空项 1:_22.在按照顺序存储方式存储的数组中，元素 aij的存储地址应该是数组的 1 加上排在 aij前面的元素所占用的单元数。（分数：2.00）填空项 1:_23.广义表的
8、深度是指 1。（分数：2.00）填空项 1:_24.从树的根结点到树中的其余结点之间的路径 1 惟一的。（分数：2.00）填空项 1:_25.设二维数组 A1020,510按行优先存储，每个元素占 4 个存储单元，A10,5的存储地址是1000，则 A15,10的存储地址是 1。（分数：2.00）填空项 1:_三、解答题(总题数：3，分数：20.00)26.对序列(48,37,63,96,22,31,50,55,11)进行升序的堆排序，写出构建的初始(大根)堆及前两趟重建堆之后的序列状态。 初始堆： 第 1 趟： 第 2 趟：（分数：5.00）_(1)画出对表长为 13 的有序顺序表进行二分查
9、找的判定树； (2)已知关键字序列为(12,14,16,21,24,28,35,43,52,67,71,84,99)，写出在该序列中二分查找 37 时所需进行的比较次数。（分数：10.00）_27.试分别画出具有 3 个结点的树和具有 3 个结点的二叉树的所有不同的形态。（分数：5.00）_四、算法阅读题(总题数：3，分数：30.00)28.写出下列程序段的输出结果。(假设此栈中元素的类型是 char) voide main( ) stack s; char x,y; InitStack(s) x=1,y=0 push(s,x); push(s,x); push(s,y); push(s,x)
10、； push(s,e); push(s,x); pop(s,x); push(s,h); while(!stackEmpty(s) pop(s,y); printf(y); prinft(x) （分数：5.00）_阅读下列算法，并回答问题： (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 中出现
11、，则返回在串 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）_二叉排序树的存储结构定义为以下类型： typedef int KeyType; typedef struct node KeyType key; /*关键字项
12、*/ InfoType otherinfo; /*其它数据项*/ struet node*lchild,*rchild; /*左、右孩子指针*/ BSTNode,*BSTree; 阅读算法 f33，并回答问题： （分数：15.00）填空项 1:_五、算法设计题(总题数：1，分数：10.00)29.写出向某个有序文件中插入一个记录的程序。（分数：10.00）_数据结构自考题-5 答案解析(总分：110.00，做题时间：90 分钟)一、单项选择题(总题数：15，分数：30.00)1.对含有( )个结点的非空二叉树，采用任何一种遍历方式，其结点访问序列均相同。 AO B1 C2 D不存在这样的二叉树
13、（分数：2.00）A.B. C.D.解析：2.以下有关数据结构的叙述，正确的是 ( ) A线性表的线性存储结构优于链式存储结构 B二叉树的第 i 层上有 2i-1个结点，深度为 K 的二叉树上有 2k-1个结点 C二维数组是其数据元素为线性表的线性表 D栈的操作方式是先进先出（分数：2.00）A.B.C. D.解析：3.对一棵非空二叉树进行中序遍历，则根结点的左边( ) A只有左子树上的所有结点 B只有右子树上的所有结点 C只有左子树上的部分结点 D只有右子树上的部分结点（分数：2.00）A. B.C.D.解析：4.已知二叉树的中序序列和后序序列均为 ABCDEF，则该二叉树的先序序列为 (
14、) AFEDCBA BABCDEF CFDECBA DFBDCEA（分数：2.00）A. B.C.D.解析：解析 对于前序遍历、中序遍历和后序遍历，将结点按其访问的先后次序排列起来，所得到的结点序列分别称为前序序列、中序序列和后序序列。5.树最适合用来表示( ) A有序数据元素 B无序数据元素 C元素之间具有分支层次关系的数据 D元素之间无联系的数据（分数：2.00）A.B.C. D.解析：6.设 rear 是指向非空带头结点的循环单链表的尾指针，则删除起始结点的操作可表示为( ) As=rear; Brear=rearnext; rear=rearnext; free(rear); free
15、(s); Crear=rearnextnext; Ds=rearnextnext; free(rear); rearnextnext=snext; free(s);（分数：2.00）A.B.C.D. 解析：7.判断一个有向图是否存在回路，除了可以利用拓扑排序方法，还可以利用( ) A求关键路径的方法 B求最短路径的 Dijkstra 方法 C广度优先遍历方法 D深度优先遍历方法（分数：2.00）A.B.C.D. 解析：8.线索二叉树是一种( )结构。 A物理 B逻辑 C存储 D线性（分数：2.00）A. B.C.D.解析：9.用二叉链表表示具有 n 个结点的二叉树时，值为空的指针域的个数为 (
16、 ) An-1 Bn Cn+1 D2n（分数：2.00）A.B.C. D.解析：10.对关键字序列(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.解析：11.如果我们采用二分查找法查找一个长度为 n 的有序表，则查找每个元素的平均比较次数( )对应的判定树的高度(假设树高 h2)。 A大于 B小于 C等于 D无法确定（分数：2.00）A.B. C.D.解析：1
17、2.在一个单链表中，已知 q 所指结点是 p 所指结点的直接前趋，若在 p，q 之间插入 s 结点，则执行( )操作。 Asnext=pnext;pnext=s; Bqnext=s;snext=p; Cpnext=snext;snext=p; Dpnext=s;snext=q;（分数：2.00）A.B. C.D.解析：13.用数组 A0N-1存放循环队列的元素值，若其头尾指针分别为 front 和 rear，则循环队列中当前元素的个数为( ) A(rear-front+m)mod m B(rear-front+1)mod m C(rear-front-1+m)mod m D(rear-fron
18、t)mod m（分数：2.00）A. B.C.D.解析：14.若用邻接矩阵表示一个有向图，则其中每一列包含的“1“的个数为 ( ) A图中每个顶点的入度 B图中每个顶点的出度 C图中弧的条数 D图中连通分量的数目（分数：2.00）A. B.C.D.解析：15.下面程序段的时间复杂度为 ( ) for(i=0;im;i+) for(j=0;jn;j+) Aij=i*j; AO(m 2) BO(n 2) CO(m*n) DO(m+n)（分数：2.00）A.B.C. D.解析：解析 此程序的时间复杂度即为程序中循环次数的时间耗费。由程序为嵌套循环，外层循环的时间复杂度 T(n1)=m，内层循环的时间
19、复杂度 T(n2)=n，则此程序的时间复杂度 T(n)=m*n，即为 0(m*n)。二、填空题(总题数：10，分数：20.00)16.广义表的深度是指 1。（分数：2.00）填空项 1:_ （正确答案：广义表展开后所含括号的最大层数）解析：17.有 m 个叶子结点(又称外结点)的哈夫曼树，其结点总数是 1。（分数：2.00）填空项 1:_ （正确答案：2m-1）解析：18.带有一个头结点的单链表 head 为空的条件是 1。（分数：2.00）填空项 1:_ （正确答案：Jaeadnext=NULL）解析：19.常用的索引顺序文件是_文件和_文件。（分数：2.00）填空项 1:_ （正确答案：I
20、SAM VSAM）解析：20.任意一棵具有 n 个结点的二叉树，若它有 m 个叶子，则该二叉树上度数为 1 的结点为 1 个。（分数：2.00）填空项 1:_ （正确答案：n-2m+1）解析：21.散列函数的作用是： 1。（分数：2.00）填空项 1:_ （正确答案：压缩待处理的下标范围，待处理的|u|个值减少到 m 个值，从而降低空间开销）解析：22.在按照顺序存储方式存储的数组中，元素 aij的存储地址应该是数组的 1 加上排在 aij前面的元素所占用的单元数。（分数：2.00）填空项 1:_ （正确答案：基地址）解析：23.广义表的深度是指 1。（分数：2.00）填空项 1:_ （正确答
21、案：广义表展开后所含括号的最大层数）解析：24.从树的根结点到树中的其余结点之间的路径 1 惟一的。（分数：2.00）填空项 1:_ （正确答案：是）解析：25.设二维数组 A1020,510按行优先存储，每个元素占 4 个存储单元，A10,5的存储地址是1000，则 A15,10的存储地址是 1。（分数：2.00）填空项 1:_ （正确答案：1700）解析：三、解答题(总题数：3，分数：20.00)26.对序列(48,37,63,96,22,31,50,55,11)进行升序的堆排序，写出构建的初始(大根)堆及前两趟重建堆之后的序列状态。 初始堆： 第 1 趟： 第 2 趟：（分数：5.00）
22、_正确答案：(初始堆：(96,55,63,48,22,31,50,37,11) 第 1 趟：(63,55,50,48,22,3l,11,37,96) 第 2 趟：(55,48,50,37,22,31,11,63,96)解析：(1)画出对表长为 13 的有序顺序表进行二分查找的判定树； (2)已知关键字序列为(12,14,16,21,24,28,35,43,52,67,71,84,99)，写出在该序列中二分查找 37 时所需进行的比较次数。（分数：10.00）_正确答案：( )解析：_正确答案：(3)解析：27.试分别画出具有 3 个结点的树和具有 3 个结点的二叉树的所有不同的形态。（分数：5
23、.00）_正确答案：(含有三个结点的树只有两种形式见(1)和(2)；含有 3 个结点的二叉树有 5 种形态见(3)，(4)，(5)，(6)，(7) )解析：四、算法阅读题(总题数：3，分数：30.00)28.写出下列程序段的输出结果。(假设此栈中元素的类型是 char) voide main( ) stack s; char x,y; InitStack(s) x=1,y=0 push(s,x); push(s,x); push(s,y); push(s,x)； push(s,e); push(s,x); pop(s,x); push(s,h); while(!stackEmpty(s) po
24、p(s,y); printf(y); prinft(x) （分数：5.00）_正确答案：(此题的输出结果是 hello。)解析：阅读下列算法，并回答问题： (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 中出现，则返回在串 st 中首次出现的下标值，否则返回-1*/ int f32(char*s
25、,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 中。)解析：二叉排序树的存储结构定义为以下类型： typedef int KeyType; typede
26、f struct node KeyType key; /*关键字项*/ InfoType otherinfo; /*其它数据项*/ struet node*lchild,*rchild; /*左、右孩子指针*/ BSTNode,*BSTree; 阅读算法 f33，并回答问题： （分数：15.00）填空项 1:_ （正确答案：10）解析：_正确答案：(T 是空树或 T 中所有结点的关键字均不大于给定值 X 时，返回空指针。)解析：_正确答案：(如果二叉排序树 T 中存在含有关键字大于给定值 X 的结点，则返回指针指向它们中关键字最小的结点，否则返回空指针。)解析：五、算法设计题(总题数：1，分数
27、：10.00)29.写出向某个有序文件中插入一个记录的程序。（分数：10.00）_正确答案：(所谓有序文件是指文件的记录按关键字由小到大(或由大到小)顺序存放。为方便起见，可设文件的每一个记录是一个整数，文件上数据是按由小到大顺序存放。设插入数据是命令行的第 3 个参数，且设为 d。若原文件中没有数据，则 d 写入文件；若有数据，则找到第 1 个比 d 大的数据 i，先写入 d，再将 i 和其后各数据写回文件中，可通过调用 fseek 函数采实现插入。相应程序为： #includestdio.h #includestdlib.h #includeio.h #includefcntl.h #de
28、fine LEN sizeof(int) void main(int argi,char*argc) int fp,i,d; if(argi3) printf(“filename int/11“) exit(0); d=atoi(argc2); fp=open(argc1,O_GREAT| O_RDWRI O_BINARY,s_IREAD| S_IWRITE); while(1) if( read(fp,) if(i=d) /*文件中读出数据 i，若 i=d，则先存 d*/ do fseek(fp,-1L*lan,SEEK_CUR); /*文件指针后退 1 个记录*/ write(fp, /*d 写到文件中*/ d=i; /*原 i 作 d，以便处理其他数据*/ while(read(fp, write(fp，/*继续读数据，并判别文件是否结束*/ break; close(fp); /*main*/)解析：
