1、数据结构自考题-7 及答案解析(总分：115.00，做题时间：90 分钟)一、单项选择题(总题数：15，分数：30.00)1.已知一采用开放地址法解决 Hash 表冲突，要从此 Hash 表中删除一个记录，正确的做法是( ) A将该元素所在的存储单元清空 B将该元素用一个特殊的元素替代 C将与该元素有相同 Hash 地址的后继元素顺次前移一个位置 D用与该无素有相同 Hash 地址的最后插入表中的元素替代（分数：2.00）A.B.C.D.2.在任意一棵二叉树的前序序列和后序序列中，各叶子之间的相对次序关系 ( ) A不一定相同 B都相同 C都不相同 D互为逆序（分数：2.00）A.B.C.D.
2、3.对于一棵具有三个结点的二叉树，共有( )种不同的树的形态。 A4 B5 C6 D7（分数：2.00）A.B.C.D.4.栈一般情况下常采用以下两种存储方式( ) A顺序结构和散列结构 B散列结构和链式结构 C线性结构和非线性结构 D顺序存储结构和链式结构（分数：2.00）A.B.C.D.5.考虑下列四种排序方法，在排序过程中，关键码比较的次数与记录的初始排列顺序无关的是( ) A直接插入排序和快速排序 B快速排序和归并排序 C直接选择排序和归并排序 D直接插入排序和归并排序（分数：2.00）A.B.C.D.6.通常要求同一逻辑结构中的所有数据元素具有相同的特性，这意味着( ) A数据元素具
3、有同一特点 B不仅数据元素所包含的数据项的个数要相同，而且对应数据项的类型要一致 C每个数据元素都一样 D数据元素所包含的数据项的个数要相等（分数：2.00）A.B.C.D.7.下列说法中正确的是( ) A任何一棵二叉树中至少有一个结点的度为 2 B任何一棵二叉树中的每个结点的度为 2 C任何一棵二叉树中的度肯定等于 2 D任何一棵二叉树中的度可以小于 2（分数：2.00）A.B.C.D.8.若进栈序列为 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（分数：
4、2.00）A.B.C.D.9.设串 s1=“Data Structures、with Java“，s2=“it“，则子串定位函数 index(s1，s2)的值为 ( ) A15 B16 C17 D18（分数：2.00）A.B.C.D.10.在一个具有 N 个顶点的无向完全图中，包含的边的总数是( ) AN(N-1)/2 BN(N-1) CN(N+1) DN(N+1)/2（分数：2.00）A.B.C.D.11.二维数组 Mi,j的元素是 4 个字符(每个字符占一个存储单元)组成的串，行下标 i 的范围从 0 到 4，列下标 j 的范围从 0 到 5。M 按行存储时元素 M3,5的起始地址与 M
5、按列存储时元素( )的起始地址相同。AM2,4 BM3,4 CM3,5 DM4,4（分数：2.00）A.B.C.D.12.按值可否分解，数据类型通常可分为两类，它们是 ( ) A静态类型和动态类型 B原子类型和表类型 C原子类型和结构类型 D数组类型和指针类型（分数：2.00）A.B.C.D.13.如果我们采用二分查找法查找一个长度为 n 的有序表，则查找每个元素的平均比较次数( )对应的判定树的高度(假设树高 h2)。 A大于 B小于 C等于 D无法确定（分数：2.00）A.B.C.D.14.若采用孩子兄弟链表作为树的存储结构，则树的后序遍历应采用二叉树的 ( ) A层次遍历算法 B前序遍历
6、算法 C中序遍历算法 D后序遍历算法（分数：2.00）A.B.C.D.15.指针 p、q 和 r 依次指向某循环链表中三个相邻的结点，交换结点*q 和结点*r 在表中次序的程序段是 ( ) Apnext=r; qnext=rnext; rnext=q; Bpnext=r; rnext=q; qnext=rnext; Crnext=q; qnext=rnext; pnext=r; Drnext=q; pnext=r; qnext=rnext;（分数：2.00）A.B.C.D.二、填空题(总题数：10，分数：20.00)16.就文件而言，按用户的观点所确定的基本存储单元称为_。按外设的观点所确定的
7、基本存储单元称为_。（分数：2.00）填空项 1:_17.在一般情况下用直接插入排序、选择排序和冒泡排序的过程中，所需记录交换次数最少的是 1。（分数：2.00）填空项 1:_18.多维数组和广义表是一种非常复杂的非线性结构，它们的逻辑特点是 1。（分数：2.00）填空项 1:_19.设 s=“I AM A ATHLETE“，t=“GOOD“，则执行下列串操作序列之后得到的 suhl 为_。 substr(sub1,s,5,2);substr(sub2,s,6,8);strcpy(t1,t); strcat,(t1,sub2);strcat(sub1,t1);（分数：2.00）填空项 1:_2
8、0.从一个顺序存储的循环队列中删除一个元素时，应该 1。（分数：2.00）填空项 1:_21.设二维数组 A1020,510按行优先存储，每个元素占 4 个存储单元，A10,5的存储地址是1000，则 A15,10的存储地址是 1。（分数：2.00）填空项 1:_22.从树的根结点到树中的其余结点之间的路径 1 惟一的。（分数：2.00）填空项 1:_23.如图所示的有向图中含有_个强连通分量。 （分数：2.00）填空项 1:_24.假设以列优先顺序存储二维数组 A58，其中元素 A00的存储地址为 LOC(a00)，且每个元素占 4个存储单元，则数组元素 Aij的存储地址为 1 。（分数：2
9、.00）填空项 1:_25.存储在直接存储器上的顺序文件可以用顺序查找法存取，也可以用_和进行查找。（分数：2.00）填空项 1:_三、解答题(总题数：3，分数：20.00)26.某广义表的表头和表尾均为(a,(b,c)，画出该广义表的图形表示。（分数：5.00）_已知有向图 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）_27.已知有一关键字序列为 97,86,53,108,72,34,215,146,11,68，如果我们采用直接选择排序方法
10、对此序列进行排序(按照升序排列)，请给出每一趟的排序结果。（分数：5.00）_四、算法阅读题(总题数：3，分数：25.00)28.求下面算法中变量 count 的值：(假设 n 为 2 的乘幂，并且 n2) int Time int n count=0;x=2; while(xn/2) x*=2;count+; return(count) （分数：5.00）_29.简述一下算法的功能： status A (1inkedlist L) /L 是无表头结点的单链表 if (LL=Lnext;P=L; while(Pnext)P=Pnext; Pnext=Q;Qnext=NULL; return o
11、k; )/A（分数：5.00）_二叉排序树的存储结构定义为以下类型： typedef int KeyType; typedef struct node KeyType key; /*关键字项*/ InfoType otherinfo; /*其它数据项*/ struet node*lchild,*rchild; /*左、右孩子指针*/ BSTNode,*BSTree; 阅读算法 f33，并回答问题： （分数：15.00）_五、算法设计题(总题数：1，分数：20.00)假设以带双亲指针的二叉链表作为-二叉树的存储结构，其结点结构的类型说明如下所示： typedef char DataType; t
12、ypedef struct node DataType data; struct node*lchild,*rchild; /左右孩子指针 struct node*parent; /指向双亲的指针 BinTNode; typedef BinTNode*BinTree; 若 px 为指向非空二叉树中某个结点的指针，可借助该结构求得 px 所指结点在二叉树的中序序列中的后继。（分数：20.00）(1).就后继的不同情况，简要叙述实现求后继操作的方法；（分数：10.00）_(2).编写算法求 px 所指结点的中序序列后继，并在算法语句中加注注释。（分数：10.00）_数据结构自考题-7 答案解析(总
13、分：115.00，做题时间：90 分钟)一、单项选择题(总题数：15，分数：30.00)1.已知一采用开放地址法解决 Hash 表冲突，要从此 Hash 表中删除一个记录，正确的做法是( ) A将该元素所在的存储单元清空 B将该元素用一个特殊的元素替代 C将与该元素有相同 Hash 地址的后继元素顺次前移一个位置 D用与该无素有相同 Hash 地址的最后插入表中的元素替代（分数：2.00）A.B. C.D.解析：2.在任意一棵二叉树的前序序列和后序序列中，各叶子之间的相对次序关系 ( ) A不一定相同 B都相同 C都不相同 D互为逆序（分数：2.00）A.B. C.D.解析：3.对于一棵具有三
14、个结点的二叉树，共有( )种不同的树的形态。 A4 B5 C6 D7（分数：2.00）A.B. C.D.解析：4.栈一般情况下常采用以下两种存储方式( ) A顺序结构和散列结构 B散列结构和链式结构 C线性结构和非线性结构 D顺序存储结构和链式结构（分数：2.00）A.B.C.D. 解析：5.考虑下列四种排序方法，在排序过程中，关键码比较的次数与记录的初始排列顺序无关的是( ) A直接插入排序和快速排序 B快速排序和归并排序 C直接选择排序和归并排序 D直接插入排序和归并排序（分数：2.00）A.B.C. D.解析：6.通常要求同一逻辑结构中的所有数据元素具有相同的特性，这意味着( ) A数据
15、元素具有同一特点 B不仅数据元素所包含的数据项的个数要相同，而且对应数据项的类型要一致 C每个数据元素都一样 D数据元素所包含的数据项的个数要相等（分数：2.00）A.B. C.D.解析：7.下列说法中正确的是( ) A任何一棵二叉树中至少有一个结点的度为 2 B任何一棵二叉树中的每个结点的度为 2 C任何一棵二叉树中的度肯定等于 2 D任何一棵二叉树中的度可以小于 2（分数：2.00）A.B.C.D. 解析：8.若进栈序列为 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,
16、4,2,3,1（分数：2.00）A.B. C.D.解析：9.设串 s1=“Data Structures、with Java“，s2=“it“，则子串定位函数 index(s1，s2)的值为 ( ) A15 B16 C17 D18（分数：2.00）A.B.C. D.解析：10.在一个具有 N 个顶点的无向完全图中，包含的边的总数是( ) AN(N-1)/2 BN(N-1) CN(N+1) DN(N+1)/2（分数：2.00）A. B.C.D.解析：11.二维数组 Mi,j的元素是 4 个字符(每个字符占一个存储单元)组成的串，行下标 i 的范围从 0 到 4，列下标 j 的范围从 0 到 5。
17、M 按行存储时元素 M3,5的起始地址与 M 按列存储时元素( )的起始地址相同。AM2,4 BM3,4 CM3,5 DM4,4（分数：2.00）A.B. C.D.解析：12.按值可否分解，数据类型通常可分为两类，它们是 ( ) A静态类型和动态类型 B原子类型和表类型 C原子类型和结构类型 D数组类型和指针类型（分数：2.00）A.B.C. D.解析：解析 按“值”是否可分解，可将数据类型划分为两类：原子类型，其值不可分解；结构类型，其值可分解为若干个成分。13.如果我们采用二分查找法查找一个长度为 n 的有序表，则查找每个元素的平均比较次数( )对应的判定树的高度(假设树高 h2)。 A大
18、于 B小于 C等于 D无法确定（分数：2.00）A.B. C.D.解析：14.若采用孩子兄弟链表作为树的存储结构，则树的后序遍历应采用二叉树的 ( ) A层次遍历算法 B前序遍历算法 C中序遍历算法 D后序遍历算法（分数：2.00）A.B.C. D.解析：15.指针 p、q 和 r 依次指向某循环链表中三个相邻的结点，交换结点*q 和结点*r 在表中次序的程序段是 ( ) Apnext=r; qnext=rnext; rnext=q; Bpnext=r; rnext=q; qnext=rnext; Crnext=q; qnext=rnext; pnext=r; Drnext=q; pnext=
19、r; qnext=rnext;（分数：2.00）A. B.C.D.解析：二、填空题(总题数：10，分数：20.00)16.就文件而言，按用户的观点所确定的基本存储单元称为_。按外设的观点所确定的基本存储单元称为_。（分数：2.00）填空项 1:_ （正确答案：逻辑记录 物理记录）解析：17.在一般情况下用直接插入排序、选择排序和冒泡排序的过程中，所需记录交换次数最少的是 1。（分数：2.00）填空项 1:_ （正确答案：选择排序）解析：18.多维数组和广义表是一种非常复杂的非线性结构，它们的逻辑特点是 1。（分数：2.00）填空项 1:_ （正确答案：一个数据元素可能有多个直接前趋和多个直接后
20、继）解析：19.设 s=“I AM A ATHLETE“，t=“GOOD“，则执行下列串操作序列之后得到的 suhl 为_。 substr(sub1,s,5,2);substr(sub2,s,6,8);strcpy(t1,t); strcat,(t1,sub2);strcat(sub1,t1);（分数：2.00）填空项 1:_ （正确答案：“A GOOD ATHLETE/）解析：20.从一个顺序存储的循环队列中删除一个元素时，应该 1。（分数：2.00）填空项 1:_ （正确答案：先移动队首指针，后取出元素）解析：21.设二维数组 A1020,510按行优先存储，每个元素占 4 个存储单元，A
21、10,5的存储地址是1000，则 A15,10的存储地址是 1。（分数：2.00）填空项 1:_ （正确答案：1700）解析：22.从树的根结点到树中的其余结点之间的路径 1 惟一的。（分数：2.00）填空项 1:_ （正确答案：是）解析：23.如图所示的有向图中含有_个强连通分量。 （分数：2.00）填空项 1:_ （正确答案：2）解析：24.假设以列优先顺序存储二维数组 A58，其中元素 A00的存储地址为 LOC(a00)，且每个元素占 4个存储单元，则数组元素 Aij的存储地址为 1 。（分数：2.00）填空项 1:_ （正确答案：LOC(a 00)+4(5j+i)）解析：25.存储在
22、直接存储器上的顺序文件可以用顺序查找法存取，也可以用_和进行查找。（分数：2.00）填空项 1:_ （正确答案：二分查找法 分块查找）解析：三、解答题(总题数：3，分数：20.00)26.某广义表的表头和表尾均为(a,(b,c)，画出该广义表的图形表示。（分数：5.00）_正确答案：( )解析：已知有向图 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）_正确答案：( )解析：_正确答案：(a,b,e,c,d a,e,b,c,d e,a,b,c,
23、d)解析：27.已知有一关键字序列为 97,86,53,108,72,34,215,146,11,68，如果我们采用直接选择排序方法对此序列进行排序(按照升序排列)，请给出每一趟的排序结果。（分数：5.00）_正确答案：(直接选择排序的过程为：从第 i 趟开始时，当前的有序区和无序区分别为 R1i和 R1n(1-1n-1)，则在该趟排序是从当前无序区中选出关键字最小的记录 RK，将它与无序区中的第 1 个记录 Ri交换，使 R1i和 Ri+1n分别变成新的有序区和新的无序区，每次排序都使有序区增加一个记录，无序区减少一个记录，按照以上规则，我们得到各趟结果如下：初始：97,86,53,108,
24、72,34,215,232,11,68 第 1 趟：1186,53,108,72,34,215,232,97,68 第 2 趟：11,3453,108,72,86,215,232,97,68 第 3 趟：11,34,531108,72,86,215,232,97,68 第 4 趟：11,34,53,6872,86,215,232,97,108 第 5 趟：11,34,53,68,7286,215,232,97,108 第 6 趟：11,34,53,68,72,86215,232,97,108 第 7 趟：11,34,53,68,72,86,97232,215,108 第 8 趟：11,34,5
25、3,68,72,86,97,108215,232 第 9 趟：11,34,53,68,72,86,97,108,215,232)解析：四、算法阅读题(总题数：3，分数：25.00)28.求下面算法中变量 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)解析：29.简述一下算法的功能： status A (1inkedlist L) /L 是无表头结点的单链表 if (LL=Lnext;P=L;
26、 while(Pnext)P=Pnext; Pnext=Q;Qnext=NULL; return ok; )/A（分数：5.00）_正确答案：(本程序实现的功能就是：如果 L 的长度不小于 2，则将首元结点删去并插入到表尾。)解析：二叉排序树的存储结构定义为以下类型： typedef int KeyType; typedef struct node KeyType key; /*关键字项*/ InfoType otherinfo; /*其它数据项*/ struet node*lchild,*rchild; /*左、右孩子指针*/ BSTNode,*BSTree; 阅读算法 f33，并回答问题：
27、 （分数：15.00）_正确答案：(10)解析：_正确答案：(T 是空树或 T 中所有结点的关键字均不大于给定值 X 时，返回空指针。)解析：_正确答案：(如果二叉排序树 T 中存在含有关键字大于给定值 X 的结点，则返回指针指向它们中关键字最小的结点，否则返回空指针。)解析：五、算法设计题(总题数：1，分数：20.00)假设以带双亲指针的二叉链表作为-二叉树的存储结构，其结点结构的类型说明如下所示： typedef char DataType; typedef struct node DataType data; struct node*lchild,*rchild; /左右孩子指针 str
28、uct node*parent; /指向双亲的指针 BinTNode; typedef BinTNode*BinTree; 若 px 为指向非空二叉树中某个结点的指针，可借助该结构求得 px 所指结点在二叉树的中序序列中的后继。（分数：20.00）(1).就后继的不同情况，简要叙述实现求后继操作的方法；（分数：10.00）_正确答案：(分两种情况讨论 当*px 的右子树不为空时，则从*px 的右孩子开始，沿其左孩子往下查找，直至找到一个没有左孩子的结点为止，则该结点为*pX 在中序序列中的后继； 当*px 的右子树为空时，则沿*px 的双亲指针链向上查找，直至找到其左子树中包含*px 的最年轻祖先，则该祖先结点为*px 在中序序列中的后继。)解析：(2).编写算法求 px 所指结点的中序序列后继，并在算法语句中加注注释。（分数：10.00）_正确答案：(BinTree f34(BinTree px) BinTree q=pxrchild; if(q!=NULL) /沿左孩子往下查找 px=q; while(pxlchild!=NULL) px=pxlchild; else /沿双亲指针链向上查找 while(px!=NULL px=pxparent; retun px； /返回所找到的中序序列后继结点的指针 /或者无后继结点时返回空指针 )解析：
