1、数据结构-1 及答案解析(总分：100.00，做题时间：90 分钟)一、B单项选择题/B(总题数：15，分数：30.00)1.设数组 data0m作为循环队列 SQ的存储空间，front 为队头指针，rear 为队尾指针，则执行出队操作的语句为( )（分数：2.00）A.front:=front+1B.front:=(front+1)mod mC.rear:=(rear+1)mod mD.front:=(front+1)mod(m+1)2.在 Hash函数 H(k)=k MOD m中，一般来讲，m 应取( )（分数：2.00）A.奇数B.偶数C.素数D.充分大的数3.实现任意二叉树的后序遍历的
2、非递归算法而不使用栈结构，最佳方案是二叉树采用( )存储结构。（分数：2.00）A.二叉链表B.广义表C.三叉链表D.顺序4.向一个栈顶指针为 Top的链栈中插入一个 s所指结点时，其操作步骤为( )（分数：2.00）A.Topnext=s;B.snext=Topnext;Topnext=s;C.snext=Top;top=s;D.snext=Top; Top=Topnext;5.快速排序在最坏情况下的时间复杂度是( )（分数：2.00）A.O(nlogB.O(n2)C.O(n3)D.都不对6.内部排序的方法有许多种，( )方法是从未排序序列中依次取出元素，与已排序序列中的元素作比较，将其放入
3、已排序序列的正确位置上。（分数：2.00）A.归并排序B.插入排序C.快速排序D.选择排序7.对于一个具有 N个顶点的图，如果我们采用邻接矩阵法表示，则此矩阵的维数应该是( )（分数：2.00）A.(N-1)(N-1)B.NNC.(N+1)(N+1)D.不确定8.在一个长度为 n的顺序表(顺序存储的线性表)中，向第 i个元素(1in+1)之前插入一个新元素时，需向后移动( )个元素。（分数：2.00）A.n-iB.n-i+1C.n-i-1D.i9.下面四种排序方法中，平均查找长度最小的是( )（分数：2.00）A.插入排序B.选择排序C.快速排序D.归并排序10.如果我们采用二分查找法查找一个
4、长度为 n的有序表，则查找每个元素的平均比较次数( )对应的判定树的高度(假设树高 h2)。（分数：2.00）A.大于B.小于C.等于D.无法确定11.在下图中，从顶点 V1出发，按广度优选遍历图的顶点序列是( )（分数：2.00）A.V1 V5 V3 V4 V2 V6 V7B.V1 V5 V3 V4 V2 V7 V6C.V1 V7 V2 V6 V4 V5 V3D.V1 V2 V4 V7 V6 V5 V3 12.线性表 L=(a1，a 2，a 1，a n)，下列说法正确的是( )（分数：2.00）A.每个元素都有一个直接前趋和直接后继B.线性表中至少要有一个元素C.表中诸元素的排列顺序必须是由
5、小到大或由大到小的D.除第一个元素和最后一个元素外，其余每个元素都有一个且仅有一个直接前趋和直接后继13.散列表的目的是( )（分数：2.00）A.插入B.删除C.快速查找D.排序14.设有一个无向图 G=(V,E)和 G=(V,E)，如果 G是 G的生成树，则下面不正确的说法是( )（分数：2.00）A.G为 G的子图B.G为 G的连通分量C.G为 G的极小连通子图且 V=VD.G是 G的一个无环子图15.树最适合用来表示( )（分数：2.00）A.有序数据元素B.无序数据元素C.元素之间具有分支层次关系的数据D.元素之间无联系的数据二、B填空题/B(总题数：10，分数：20.00)16.对
6、于一个具有 n个结点的单链表，在已知 p结点后插入一个新结点的事件的时间复杂性为_，在给定值为 x的结点后插入一个新结点的时间复杂性为_。（分数：2.00）填空项 1:_17.设有两个串 p和 q，求 q在 p中首次出现的位置的运算叫 1。（分数：2.00）填空项 1:_18.对于一个长度为 n的线性表，假设表中各结点的查找概率相同，则在查找成功的情况下，平均查找长度为 1，如果 k不在表中，则需要进行 2 次比较后才能确定查找失败。（分数：2.00）填空项 1:_填空项 1:_19.在二叉排序树中，其左子树中任何一个结点的关键字一定 1 其右子树的各结点的关键字。（分数：2.00）填空项 1
7、:_20.数组 01n表示一个环形队列，设 f的值为队列中第一个元素的位置，r 的值为队列中实际队尾元素的位置加 1，并假定队列中至多只有 n-1个元素，则计算队列中元素个数的公式为 1。（分数：2.00）填空项 1:_21.一般来说，数组中的元素具有_的数据类型，并且数组元素的下标的上界和下界都是_的。（分数：2.00）填空项 1:_22.一个 nn的对称矩阵，如果以行为主序或以列为主序存入内存，则其容量为 1。（分数：2.00）填空项 1:_23.在线性表的顺序存储中，假设每个结点所占用的存储空间为 c，且第一个单元的存储地址则是该结点的存储地址，设开始结点 a1的存储地址是 LOC(a1
8、)，则结点 a1存储地址 LOC(a1)可以通过下式得到 1。（分数：2.00）填空项 1:_24.在具有 n个单元的循环队列中，队满时共有 1 个元素。（分数：2.00）填空项 1:_25.查找表按其所包括的运算的不同分为_查找表和_查找表。（分数：2.00）填空项 1:_三、B解答题/B(总题数：4，分数：20.00)26.已知有一个关键字序列为(99,38,309,08,27,145,67,96,186,122,71,63,59)，假设用散列函数为h(key)=key%13，现在如果采用拉链法解决冲突问题，请画出这组关键字的散列表。（分数：5.00）_27.已知有一关键字序列为486,7
9、9,596,34,900,120,789,179,703,307)，如果我们采用基数排序方法对此序列进行排序(按照升序排列)，请给出每一趟的排序结果。（分数：5.00）_28.写出二分查找的递归算法。（分数：5.00）_29.已知连通图如下： （分数：5.00）_四、B算法阅读题/B(总题数：4，分数：20.00)30.以下运算实现在循环队上取队头，请在_处用适当的语句予以填充。 int GetHead(CycqueueTp sq,DataType*x) if(sq.rear=_return(0); else*x=sq.data_; return(1); （分数：5.00）填空项 1:_31.
10、以下是图的广度优先搜索算法，请在_处填充适当的语句。 Bfs(GraphTp g,int v) QueptrTp Q; ArcNodeTp*P; InitQueue( printf(“%“”,v); visitedv=1; _ while(!EmptyQueue(Q) _; p=g.adjlistv.firstarc; while(p! =NULL) if(! visitedpadjvex) printf(“%“”,padjvex); visitedpadjvex=1); EnQueue( _; （分数：5.00）填空项 1:_32.以下为单链表的定位运算，分析算法，请在_处填上正确的语句。
11、int locate_iklist(1klist head,datatype x) /*求表 head中第一个值等于 x的结点的序号。不存在这种结点时结果为 0*/ p=head;j=O; while(_)p=pnext;j+; if(pdata=x)return(j); elsereturn(0); （分数：5.00）填空项 1:_33.下列算法用于判断带头结点的循环双链表 A是否对称相等，请在算法中的一填上正确的语句。 int dlink_symmetry(dlklist s) j=true; p=snext; q=sprior; while(p!=q) (_); else j=false
12、; return(j); （分数：5.00）填空项 1:_五、B算法设计题/B(总题数：1，分数：10.00)34.设计一个用链表表示的直接选择排序算法。（分数：10.00）_数据结构-1 答案解析(总分：100.00，做题时间：90 分钟)一、B单项选择题/B(总题数：15，分数：30.00)1.设数组 data0m作为循环队列 SQ的存储空间，front 为队头指针，rear 为队尾指针，则执行出队操作的语句为( )（分数：2.00）A.front:=front+1B.front:=(front+1)mod mC.rear:=(rear+1)mod mD.front:=(front+1)m
13、od(m+1) 解析：2.在 Hash函数 H(k)=k MOD m中，一般来讲，m 应取( )（分数：2.00）A.奇数B.偶数C.素数 D.充分大的数解析：3.实现任意二叉树的后序遍历的非递归算法而不使用栈结构，最佳方案是二叉树采用( )存储结构。（分数：2.00）A.二叉链表B.广义表C.三叉链表 D.顺序解析：4.向一个栈顶指针为 Top的链栈中插入一个 s所指结点时，其操作步骤为( )（分数：2.00）A.Topnext=s;B.snext=Topnext;Topnext=s;C.snext=Top;top=s; D.snext=Top; Top=Topnext;解析：5.快速排序在
14、最坏情况下的时间复杂度是( )（分数：2.00）A.O(nlogB.O(n2) C.O(n3)D.都不对解析：6.内部排序的方法有许多种，( )方法是从未排序序列中依次取出元素，与已排序序列中的元素作比较，将其放入已排序序列的正确位置上。（分数：2.00）A.归并排序B.插入排序 C.快速排序D.选择排序解析：7.对于一个具有 N个顶点的图，如果我们采用邻接矩阵法表示，则此矩阵的维数应该是( )（分数：2.00）A.(N-1)(N-1)B.NN C.(N+1)(N+1)D.不确定解析：8.在一个长度为 n的顺序表(顺序存储的线性表)中，向第 i个元素(1in+1)之前插入一个新元素时，需向后移
15、动( )个元素。（分数：2.00）A.n-iB.n-i+1 C.n-i-1D.i解析：9.下面四种排序方法中，平均查找长度最小的是( )（分数：2.00）A.插入排序B.选择排序C.快速排序 D.归并排序解析：10.如果我们采用二分查找法查找一个长度为 n的有序表，则查找每个元素的平均比较次数( )对应的判定树的高度(假设树高 h2)。（分数：2.00）A.大于B.小于 C.等于D.无法确定解析：11.在下图中，从顶点 V1出发，按广度优选遍历图的顶点序列是( )（分数：2.00）A.V1 V5 V3 V4 V2 V6 V7 B.V1 V5 V3 V4 V2 V7 V6C.V1 V7 V2 V
16、6 V4 V5 V3D.V1 V2 V4 V7 V6 V5 V3 解析：12.线性表 L=(a1，a 2，a 1，a n)，下列说法正确的是( )（分数：2.00）A.每个元素都有一个直接前趋和直接后继B.线性表中至少要有一个元素C.表中诸元素的排列顺序必须是由小到大或由大到小的D.除第一个元素和最后一个元素外，其余每个元素都有一个且仅有一个直接前趋和直接后继 解析：13.散列表的目的是( )（分数：2.00）A.插入B.删除C.快速查找 D.排序解析：14.设有一个无向图 G=(V,E)和 G=(V,E)，如果 G是 G的生成树，则下面不正确的说法是( )（分数：2.00）A.G为 G的子图
17、B.G为 G的连通分量 C.G为 G的极小连通子图且 V=VD.G是 G的一个无环子图解析：15.树最适合用来表示( )（分数：2.00）A.有序数据元素B.无序数据元素C.元素之间具有分支层次关系的数据 D.元素之间无联系的数据解析：二、B填空题/B(总题数：10，分数：20.00)16.对于一个具有 n个结点的单链表，在已知 p结点后插入一个新结点的事件的时间复杂性为_，在给定值为 x的结点后插入一个新结点的时间复杂性为_。（分数：2.00）填空项 1:_ （正确答案：O(1) O(n)）解析：17.设有两个串 p和 q，求 q在 p中首次出现的位置的运算叫 1。（分数：2.00）填空项
18、1:_ （正确答案：模式匹配）解析：18.对于一个长度为 n的线性表，假设表中各结点的查找概率相同，则在查找成功的情况下，平均查找长度为 1，如果 k不在表中，则需要进行 2 次比较后才能确定查找失败。（分数：2.00）填空项 1:_ （正确答案：(n+1)/2）填空项 1:_ （正确答案：n+1）解析：19.在二叉排序树中，其左子树中任何一个结点的关键字一定 1 其右子树的各结点的关键字。（分数：2.00）填空项 1:_ （正确答案：小于）解析：20.数组 01n表示一个环形队列，设 f的值为队列中第一个元素的位置，r 的值为队列中实际队尾元素的位置加 1，并假定队列中至多只有 n-1个元素
19、，则计算队列中元素个数的公式为 1。（分数：2.00）填空项 1:_ （正确答案：(n+r-f)mod n）解析：21.一般来说，数组中的元素具有_的数据类型，并且数组元素的下标的上界和下界都是_的。（分数：2.00）填空项 1:_ （正确答案：统一 固定）解析：22.一个 nn的对称矩阵，如果以行为主序或以列为主序存入内存，则其容量为 1。（分数：2.00）填空项 1:_ （正确答案：n(n+1)/2）解析：23.在线性表的顺序存储中，假设每个结点所占用的存储空间为 c，且第一个单元的存储地址则是该结点的存储地址，设开始结点 a1的存储地址是 LOC(a1)，则结点 a1存储地址 LOC(a
20、1)可以通过下式得到 1。（分数：2.00）填空项 1:_ （正确答案：LOC(a 1)=LOC(a1)+(i-1)*c）解析：24.在具有 n个单元的循环队列中，队满时共有 1 个元素。（分数：2.00）填空项 1:_ （正确答案：n1）解析：25.查找表按其所包括的运算的不同分为_查找表和_查找表。（分数：2.00）填空项 1:_ （正确答案：静态 动态）解析：三、B解答题/B(总题数：4，分数：20.00)26.已知有一个关键字序列为(99,38,309,08,27,145,67,96,186,122,71,63,59)，假设用散列函数为h(key)=key%13，现在如果采用拉链法解决
21、冲突问题，请画出这组关键字的散列表。（分数：5.00）_正确答案：()解析：采用散列函数为：h(key)=key%13，得到对应的上述关键字序列的散列地址为(8,2,10,8,1,2,2,5,4,5,6,11,7)，用拉链法解决冲突的问题时，就是将所有关键字为同义词的结点连接在同一个单链表中，且当把 h(key)=i的关键字插入到第 i个单链表中时，既可以插入到单链表的头上，也可以插入到链袁的尾上。根据上述规则，我们可以得到此序列的散列表形式如下图。 27.已知有一关键字序列为486,79,596,34,900,120,789,179,703,307)，如果我们采用基数排序方法对此序列进行排序
22、(按照升序排列)，请给出每一趟的排序结果。（分数：5.00）_正确答案：()解析：基数排序的基本思想是：从低位到高位依次对 kj(j=d-1，d-20)进行箱排序，根据基数排序法的基本方法，我们得到如下的排序结果： 初始：486,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,
23、789,90028.写出二分查找的递归算法。（分数：5.00）_正确答案：()解析：int binlist(datatype an;int s,t;datatype x) /*n 为元素个数，s，t 分别为查找区间的上、下界*/ if(St)return(0); /*查找失败*/ else mid=(s+t)/2; switch(mid)of xamid:return(binlist(a,s,mid-1,x); /*在低端区间上递归*/ x=amid:return(mid); /*查找成功*/ xamid:return(binlist(a,mid+1,t,x); /*在高端区间上递归*/ 29
24、.已知连通图如下： （分数：5.00）_正确答案：()解析： 深度优先搜索顶点序列为： b a d f e c 广度优先搜索顶点序列为： b a c e d f四、B算法阅读题/B(总题数：4，分数：20.00)30.以下运算实现在循环队上取队头，请在_处用适当的语句予以填充。 int GetHead(CycqueueTp sq,DataType*x) if(sq.rear=_return(0); else*x=sq.data_; return(1); （分数：5.00）填空项 1:_ （正确答案：sq.front(sq.front+1)% maxsize）解析：31.以下是图的广度优先搜索算
25、法，请在_处填充适当的语句。 Bfs(GraphTp g,int v) QueptrTp Q; ArcNodeTp*P; InitQueue( printf(“%“”,v); visitedv=1; _ while(!EmptyQueue(Q) _; p=g.adjlistv.firstarc; while(p! =NULL) if(! visitedpadjvex) printf(“%“”,padjvex); visitedpadjvex=1); EnQueue( _; （分数：5.00）填空项 1:_ （正确答案：EnQueue(j=O; while(_)p=pnext;j+; if(pd
26、ata=x)return(j); elsereturn(0); （分数：5.00）填空项 1:_ （正确答案：(pnext!=NULL) p=snext; q=sprior; while(p!=q) (_); else j=false; return(j); （分数：5.00）填空项 1:_ （正确答案：pprior!=q|qnext!=P p=pnext q=qprior。）解析：五、B算法设计题/B(总题数：1，分数：10.00)34.设计一个用链表表示的直接选择排序算法。（分数：10.00）_正确答案：()解析：Void selesort(lklist L) /*设链表 L带头结点*/
27、q=L; /*指向第一数据前趋*/ while(qnext!=NULL) p1=qntxt; minp=p1; /*minp 指向当前已知的最小数*/ while(p1next!=NULL) if(p1nextdataminpdata) minp=p1next; /*找到了更小数*/ p1=p1next; /*继续往下找*/ if(minp!=qnext; /*将最小数交换到第一个位置上*/ r1=minpnext minpnext=r1next; /*删除最小教*/ r2=qnext; qnext=r2next; /*删除当前表中第一个数*/ r1next=qnext; qnext=r1; /*将最小插入到第一位置上*/ r2next=minpnext; minpnext=r2; /*将原第一个数放到最小数原位置上*/ q=qnext; /*选择下一个最小数*/
