1、数据结构自考题-4 及答案解析(总分：103.00，做题时间：90 分钟)一、单项选择题(总题数：14，分数：28.00)1.栈一般情况下常采用以下两种存储方式( ) A顺序结构和散列结构 B散列结构和链式结构 C线性结构和非线性结构 D顺序存储结构和链式结构（分数：2.00）A.B.C.D.2.考虑下列四种排序方法，在排序过程中，关键码比较的次数与记录的初始排列顺序无关的是( ) A直接插入排序和快速排序 B快速排序和归并排序 C直接选择排序和归并排序 D直接插入排序和归并排序（分数：2.00）A.B.C.D.3.在桶排序中，其平均时间复杂度是( ) AO(1) BO(n) CO(n 2)
2、DO(1gn)（分数：2.00）A.B.C.D.4.链栈与顺序栈相比，有一个比较明显的优点即( ) A插入操作更加方便 B通常不会出现栈满的情况 C不会出现栈空的情况 D删除操作更加方便（分数：2.00）A.B.C.D.5.二维数组 A106采用行优先的存储方法，若每个元素占 4 个存储单元，已知元素 A34的存储地址为 1000，则元素 A43的存储地址为 ( ) A1020 B1024 C1036 D1240（分数：2.00）A.B.C.D.6.邻接表存储结构下图的深度优先遍历算法结构类似于于叉树的( ) A先序遍历 B中序遍历 C后序遍历 D按层遍历（分数：2.00）A.B.C.D.7.
3、对采用二分查找法进行查找运算的查找表，要求按( )方式进行存储。 A顺序存储 B链式存储 C顺序存储且结点按关键字有序 D链式存储且结点按关键字有序（分数：2.00）A.B.C.D.8.将上万个一组无序并且互不相等的正整数序列，存放于顺序存储结构中，采用( )方法能够最快地找出其中最大的正整数。 A快速排序 B插入排序 C选择排序 D归并排序（分数：2.00）A.B.C.D.9.已知二叉树的中序序列和后序序列均为 ABCDEF，则该二叉树的先序序列为 ( ) AFEDCBA BABCDEF CFDECBA DFBDCEA（分数：2.00）A.B.C.D.10.设散列函数为 H(k)=k mod
4、7，一组关键码为 23,14,9,6,30,12 和 18，散列表 T 的地址空间为 0.6，用线性探测法解决冲突，依次将这组关键码插入 T 中，得到的散列表为( ) （分数：2.00）A.B.C.D.11.对含有( )个结点的非空二叉树，采用任何一种遍历方式，其结点访问序列均相同。 AO B1 C2 D不存在这样的二叉树（分数：2.00）A.B.C.D.12.若用冒泡排序法对序列 18,14,6,27,8,12,16,52,10,26,47,29,41,24 从小到大进行排序，共要进行( )次比较。 A33 B45 C70 D91（分数：2.00）A.B.C.D.13.下列排序算法中，其时间
5、复杂度和记录的初始排列无关的是 ( ) A插入排序 B堆排序 C快速排序 D冒泡排序（分数：2.00）A.B.C.D.14.在图的邻接表存储结构上执行深度优先搜索遍历类似于二叉树上的 ( ) A先序遍历 B中序遍历 C后序遍历 D按层次遍历（分数：2.00）A.B.C.D.二、填空题(总题数：10，分数：20.00)15.判断一个没有头结点的单链表 head 为空的条件是 1。（分数：2.00）填空项 1:_16.设二维数组 A1020,510按行优先存储，每个元素占 4 个存储单元，A10,5的存储地址是1000，则 A15,10的存储地址是 1。（分数：2.00）填空项 1:_17.对于一
6、个具有 n 条边和 e 个顶点的图来说，如果采用邻接表表示，则其空间复杂度为_，若采用邻接矩阵表示，则其空间复杂度为_。（分数：2.00）填空项 1:_18.在 5 阶 B-树中，每个结点至多含 4 个关键字，除根结点之外，其他结点至少含 1 个关键字。（分数：2.00）填空项 1:_19.设对称矩阵 A 压缩存储在一维数组 B 中，其中矩阵的第一个元素 a11存储在 B0，元素 a52存储在B11，则矩阵元素 a36存储在B 1中。（分数：2.00）填空项 1:_20.设树 T 的度为 4，其中度为 1、2、3 和 4 的结点个数分别是 4、2、1 和 1，则 T 中叶子结点的个数是： 1。
7、（分数：2.00）填空项 1:_21.一个字符串相等的充要条件是_和_。（分数：2.00）填空项 1:_22.在串的链式存储结构中，有一个串 S1=“ejidc“，我们假设存储时结点的大小为 1，并设指针占有 4 个字节，则链串的存储密度为_，又假设串 S2=“abcdefg“在存储时我们设定结点的大小为 4，指针占有4 个字节，则此链串的存储密度为_。（分数：2.00）填空项 1:_23.若对关键字序列(43,02,80,48,26,57,15,73,21,24,66)进行一趟增量为 3 的希尔排序，则得到的结果为 1。（分数：2.00）填空项 1:_24.在线性结构中， 1 决定了它的遍历
8、路线只有一条。（分数：2.00）填空项 1:_三、解答题(总题数：3，分数：25.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）_25.画出与如图所示森林对应的二叉树。 （分数：5.00）_(1)画出对表长为 13 的有序顺序表进行二分查找的判定树； (2)已知关键字序列为(12,14,16,21,24,28,35,43,52,67,71,84,99)，写出在该序列中二分查找 37 时所需进行的比较次数。（分数：10.00）_
9、四、算法阅读题(总题数：3，分数：20.00)26.求下面算法中变量 count 的值：(假设 n 为 2 的乘幂，并且 n2) int Time int n count=0;x=2; while(xn/2) x*=2;count+; return(count) （分数：5.00）_假设学生成绩按学号增序存储在带头结点的单链表中，类型定义如下： typedef struct Node int id; /*学号*/ int score; /*成绩*/ srruct Node*next; LNode,*LinkList; 阅读算法 f31，并回答问题： (1)设结点结构为 ，成绩链表 A 和 B
10、如图所示，画出执行算法 f31(A,B)后 A 所指的链表； （分数：10.00）_27.简述一下算法的功能： status A (1inkedlist L) /L 是无表头结点的单链表 if (LL=Lnext;P=L; while(Pnext)P=Pnext; Pnext=Q;Qnext=NULL; return ok; )/A（分数：5.00）_五、算法设计题(总题数：1，分数：10.00)28.假设以带头结点的单链表表示有序表，单链表的类型定义如下： typedef struct node DataType data; struct node*next LinkNode,*LinkLi
11、st; 编写算法，从有序表 A 中删除所有和有序表 B 中元素相同的结点。（分数：10.00）_数据结构自考题-4 答案解析(总分：103.00，做题时间：90 分钟)一、单项选择题(总题数：14，分数：28.00)1.栈一般情况下常采用以下两种存储方式( ) A顺序结构和散列结构 B散列结构和链式结构 C线性结构和非线性结构 D顺序存储结构和链式结构（分数：2.00）A.B.C.D. 解析：2.考虑下列四种排序方法，在排序过程中，关键码比较的次数与记录的初始排列顺序无关的是( ) A直接插入排序和快速排序 B快速排序和归并排序 C直接选择排序和归并排序 D直接插入排序和归并排序（分数：2.0
12、0）A.B.C. D.解析：3.在桶排序中，其平均时间复杂度是( ) AO(1) BO(n) CO(n 2) DO(1gn)（分数：2.00）A.B. C.D.解析：4.链栈与顺序栈相比，有一个比较明显的优点即( ) A插入操作更加方便 B通常不会出现栈满的情况 C不会出现栈空的情况 D删除操作更加方便（分数：2.00）A.B. C.D.解析：5.二维数组 A106采用行优先的存储方法，若每个元素占 4 个存储单元，已知元素 A34的存储地址为 1000，则元素 A43的存储地址为 ( ) A1020 B1024 C1036 D1240（分数：2.00）A. B.C.D.解析：解析 由题意可知
13、，自 A34的存储地址 1000 起共存放了 5 个元素(即 A34、A35、A40、A41和 A42)后，才开始存放 A43，所以 A43的存储地址为 1000+54=1020。6.邻接表存储结构下图的深度优先遍历算法结构类似于于叉树的( ) A先序遍历 B中序遍历 C后序遍历 D按层遍历（分数：2.00）A. B.C.D.解析：7.对采用二分查找法进行查找运算的查找表，要求按( )方式进行存储。 A顺序存储 B链式存储 C顺序存储且结点按关键字有序 D链式存储且结点按关键字有序（分数：2.00）A.B.C. D.解析：8.将上万个一组无序并且互不相等的正整数序列，存放于顺序存储结构中，采用
14、( )方法能够最快地找出其中最大的正整数。 A快速排序 B插入排序 C选择排序 D归并排序（分数：2.00）A.B.C. D.解析：9.已知二叉树的中序序列和后序序列均为 ABCDEF，则该二叉树的先序序列为 ( ) AFEDCBA BABCDEF CFDECBA DFBDCEA（分数：2.00）A. B.C.D.解析：解析 对于前序遍历、中序遍历和后序遍历，将结点按其访问的先后次序排列起来，所得到的结点序列分别称为前序序列、中序序列和后序序列。10.设散列函数为 H(k)=k mod7，一组关键码为 23,14,9,6,30,12 和 18，散列表 T 的地址空间为 0.6，用线性探测法解决
15、冲突，依次将这组关键码插入 T 中，得到的散列表为( ) （分数：2.00）A.B. C.D.解析：11.对含有( )个结点的非空二叉树，采用任何一种遍历方式，其结点访问序列均相同。 AO B1 C2 D不存在这样的二叉树（分数：2.00）A.B. C.D.解析：12.若用冒泡排序法对序列 18,14,6,27,8,12,16,52,10,26,47,29,41,24 从小到大进行排序，共要进行( )次比较。 A33 B45 C70 D91（分数：2.00）A.B.C. D.解析：13.下列排序算法中，其时间复杂度和记录的初始排列无关的是 ( ) A插入排序 B堆排序 C快速排序 D冒泡排序（
16、分数：2.00）A.B. C.D.解析：14.在图的邻接表存储结构上执行深度优先搜索遍历类似于二叉树上的 ( ) A先序遍历 B中序遍历 C后序遍历 D按层次遍历（分数：2.00）A. B.C.D.解析：二、填空题(总题数：10，分数：20.00)15.判断一个没有头结点的单链表 head 为空的条件是 1。（分数：2.00）填空项 1:_ （正确答案：hcad=NULL）解析：16.设二维数组 A1020,510按行优先存储，每个元素占 4 个存储单元，A10,5的存储地址是1000，则 A15,10的存储地址是 1。（分数：2.00）填空项 1:_ （正确答案：1700）解析：17.对于一
17、个具有 n 条边和 e 个顶点的图来说，如果采用邻接表表示，则其空间复杂度为_，若采用邻接矩阵表示，则其空间复杂度为_。（分数：2.00）填空项 1:_ （正确答案：O(n+c) O(n 2)）解析：18.在 5 阶 B-树中，每个结点至多含 4 个关键字，除根结点之外，其他结点至少含 1 个关键字。（分数：2.00）填空项 1:_ （正确答案：2）解析：19.设对称矩阵 A 压缩存储在一维数组 B 中，其中矩阵的第一个元素 a11存储在 B0，元素 a52存储在B11，则矩阵元素 a36存储在B 1中。（分数：2.00）填空项 1:_ （正确答案：17）解析：20.设树 T 的度为 4，其中
18、度为 1、2、3 和 4 的结点个数分别是 4、2、1 和 1，则 T 中叶子结点的个数是： 1。（分数：2.00）填空项 1:_ （正确答案：8 个）解析：21.一个字符串相等的充要条件是_和_。（分数：2.00）填空项 1:_ （正确答案：两个字符串的长度相等 对应位置的字符相等）解析：22.在串的链式存储结构中，有一个串 S1=“ejidc“，我们假设存储时结点的大小为 1，并设指针占有 4 个字节，则链串的存储密度为_，又假设串 S2=“abcdefg“在存储时我们设定结点的大小为 4，指针占有4 个字节，则此链串的存储密度为_。（分数：2.00）填空项 1:_ （正确答案：20% 5
19、0%）解析：23.若对关键字序列(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）解析：24.在线性结构中， 1 决定了它的遍历路线只有一条。（分数：2.00）填空项 1:_ （正确答案：线性结构中后继的惟一性）解析：三、解答题(总题数：3，分数：25.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 的图形；
20、(2)写出 G 的全部拓扑序列。（分数：10.00）_正确答案：( )解析：_正确答案：(a,b,e,c,d a,e,b,c,d e,a,b,c,d)解析：25.画出与如图所示森林对应的二叉树。 （分数：5.00）_正确答案：( )解析：(1)画出对表长为 13 的有序顺序表进行二分查找的判定树； (2)已知关键字序列为(12,14,16,21,24,28,35,43,52,67,71,84,99)，写出在该序列中二分查找 37 时所需进行的比较次数。（分数：10.00）_正确答案：( )解析：_正确答案：(3)解析：四、算法阅读题(总题数：3，分数：20.00)26.求下面算法中变量 cou
21、nt 的值：(假设 n 为 2 的乘幂，并且 n2) int Time int n count=0;x=2; while(xn/2) x*=2;count+; return(count) （分数：5.00）_正确答案：(count=log 2n)解析：假设学生成绩按学号增序存储在带头结点的单链表中，类型定义如下： typedef struct Node int id; /*学号*/ int score; /*成绩*/ srruct Node*next; LNode,*LinkList; 阅读算法 f31，并回答问题： (1)设结点结构为 ，成绩链表 A 和 B 如图所示，画出执行算法 f31(
22、A,B)后 A 所指的链表； （分数：10.00）_正确答案：()解析：_正确答案：(对于表 A 中成绩低于 60 的学生，如果在表 B 中也有成绩记录，则将表 A 中的成绩修改为其在表 B 中的成绩；但若其在表 B 中的成绩高于 60 分，则只改为 60 分。)解析：27.简述一下算法的功能： status A (1inkedlist L) /L 是无表头结点的单链表 if (LL=Lnext;P=L; while(Pnext)P=Pnext; Pnext=Q;Qnext=NULL; return ok; )/A（分数：5.00）_正确答案：(本程序实现的功能就是：如果 L 的长度不小于 2
23、，则将首元结点删去并插入到表尾。)解析：五、算法设计题(总题数：1，分数：10.00)28.假设以带头结点的单链表表示有序表，单链表的类型定义如下： typedef struct node DataType data; struct node*next LinkNode,*LinkList; 编写算法，从有序表 A 中删除所有和有序表 B 中元素相同的结点。（分数：10.00）_正确答案：(参考答案一： void f34(LinkList ha,LinkList hb) /hb 和 hb 分剐为存放 A 和 B 有序链表的头指针 LinkList p,q,r; p=ha; q=hbnext;
24、while(pnext else if(pnextdata=qdata) r=pnext; pnext=rnext; free(r); /从 A 表删除相同的元素结点 q=qnext; 参考答案二： void f34(LinkList ha,LinkList hb) /hb 和 hb 分别为存放 A 和 B 有序链表的头指针 LinkList p,q,r; r=ha;p=hanext; q=hbnext; while(pp=p-next; else if(pdata=qdata) rnext=pnext; free(p); p=rnext; /从 A 表删除相同的元素结点 q=qnext )解析：
