1、数据结构-2 及答案解析(总分：100.00，做题时间：90 分钟)一、B单项选择题/B(总题数：15，分数：30.00)1.设 rear是指向非空带头结点的循环单链表的尾指针，则删除起始结点的操作可表示为( )（分数：2.00）A.s=rear;B.rear=rearnext; rear=rearnext; free(rea; free(;C.rear=rearnextnext;D.s=rearnextnext; free(rea; rearnextnext=snext; free(;2.在图的邻接表存储结构上执行深度优先搜索遍历类似于二叉树上的 ( )（分数：2.00）A.先序遍历B.中序
2、遍历C.后序遍历D.按层次遍历3.一个栈的入栈序列为 a1,a2,a3,a4,a5，则此栈不可能的输出序列是 ( )（分数：2.00）A.a5,a4,a3,a2,a1B.a4,a5,a3,a2,a1C.a4,a3,a5,a1,a2D.a1,a2,a3,a4,a54.已知一个向量的第一个元素的存储地址是 loO，每个元素的长度为 2，则第 6个元素的地址是 ( )（分数：2.00）A.120B.112C.110D.1145.设计一个判别表达式中左、右括号是否配对出现的算法，采用( )数据结构最佳。（分数：2.00）A.线性表的顺序存储结构B.栈C.队列D.线性表的链式存储结构6.设二叉树有 n个
3、结点，则其深度为 ( )（分数：2.00）A.n-1B.nC.D.不确定7.在一棵二叉树中，第 k层上最多有( )个结点。（分数：2.00）A.2kB.2k-1C.2kD.2k-18.在图的邻接表存储结构上执行广度优先搜索遍历类似于二叉树上的 ( )（分数：2.00）A.先根遍历B.中根遍历C.后根遍历D.按层次遍历9.以下有关数据结构的叙述，正确的是 ( )（分数：2.00）A.线性表的线性存储结构优于链式存储结构B.二叉树的第 i层上有 2i-1个结点，深度为 K的二叉树上有 2k-1个结点C.二维数组是其数据元素为线性表的线性表D.栈的操作方式是先进先出10.二维数组 Mi,j的元素是
4、4个字符(每个字符占一个存储单元)组成的串，行下标 i的范围从 0到 4，列下标 j的范围从 0到 5。M 按行存储时元素 M3,5的起始地址与 M按列存储时元素( )的起始地址相同。（分数：2.00）A.M2,4B.M3,4C.M3,5D.M4,411.设有一顺序栈 S，元素 s1，s 2，s 3，s 4，s 5，s 6依次进栈，如果 6个元素出栈的顺序是s2，s 3，s 4，s 5，s 6，s 1，则栈的容量至少应该是 ( )（分数：2.00）A.2B.3C.5D.612.一棵二叉树如图所示，其中序遍历的序列为 ( )（分数：2.00）A.ABDGCEFHB.DGBAECHFC.GDBEH
5、FCAD.ABCDEFGH 13.已知一个单链表中有 3000个结点，每个结点存放一个整数，( )可用于解决这 3000个整数的排序问题且不需要对算法作大的变动。（分数：2.00）A.直接插入排序方法B.简单选择排序方法C.快速排序方法D.堆排序方法14.深度为 6(根的层次为 1)的二叉树至多有( )个结点。（分数：2.00）A.31B.32C.63D.6415.在单链表中，删除 p所指结点的直接后继的操作是 ( )（分数：2.00）A.pnext=pnextnext;B.p=pnext;pnext=pnextnext;C.pnext=pnext;D.p=pnextnext;二、B填空题/B
6、(总题数：10，分数：20.00)16.对快速排序来讲，其最好情况下的时间复杂度是_，其最坏情况下的时间复杂度是_。（分数：2.00）填空项 1:_17.假设在线索二叉树中，结点的标志域的值为 0时，表示其指针域是指向孩子的指针，当结点的标志域为 1时，表示其指针域是指向前趋或者后继的线索，则一个结点是叶结点的充要条件是 1。（分数：2.00）填空项 1:_18.散列函数的作用是： 1。（分数：2.00）填空项 1:_19.内部排序的方法可以分为五类：_、_、_、_、_。（分数：2.00）填空项 1:_20.树的结点数目至少为_，二叉树的结点数目至少为_。（分数：2.00）填空项 1:_21.
7、在结点数目相同的二叉树中， 1 的路径长度最短。（分数：2.00）填空项 1:_22.从一个顺序存储的循环队列中删除一个元素时，应该 1。（分数：2.00）填空项 1:_23.对于数组，通常具有的基本操作有_种，它们分别是_。（分数：2.00）填空项 1:_24.设有两个散列函数 H1(k)=k mod 13和 H2(k)=k mod 11+1，散列表为 T012，用双重散列解决冲突。函数 H1用来计算散列地址，当发生冲突时，H2 作为计算下一个探测地址的地址增量，假定在某一时刻表T的状态为 （分数：2.00）填空项 1:_25.无向图的邻接矩阵是 1，并且主对角线上的元素的值为 2。（分数：
8、2.00）填空项 1:_三、B解答题/B(总题数：4，分数：20.00)26.请根据下面所给出的邻接矩阵画出相应的有向图或者是无向图(顶点 vi表示)。 （分数：5.00）_27.对于如下一个有序的关键字序列5,9,12,18,23,31,37,46,59,66,71,78,85)，现在要求用二分法进行查找值为 18的关键字，则经过几次比较之后能查找成功?（分数：5.00）_28.已知有一关键字序列为505,94,512,61,908,170,897,275,653,463)，如果我们采用快速法对此序列进行排序(按照升序排序)，请给出每一趟排序的结果。（分数：5.00）_29.已知数据序列为1
9、2,5,9,20,6,31,24)，对该数据序列进行排序，试写出插入排序和冒泡排序每趟的结果。 （分数：5.00）_四、B算法阅读题/B(总题数：4，分数：20.00)30.以下运算实现在链队上的入队列，请在_处用适当的语句予以填充。 void EnQueue(QueptrTp*lq,DataType x) LqueueTp*P; p=(LqueueTp*)malloc(sizeof(LqueueTp); _=x; pnext=NULL; (1qrear)next=_; _; （分数：5.00）填空项 1:_31.以下运算实现在链栈上的初始化，请在_处用适当的语句予以填充。 void Init
10、Stack(LStackTp*ls)_;)（分数：5.00）填空项 1:_32.以下算法在指针 T所指的二叉排序树上的查找键值等于 K的结点。成功时回送指向该结点的指针；否则回送空指针。请分析程序，并在_上填充合适的语句。 bitreptr search_bst(bitreptr T,keytype K) if(T=NULL)return(NULL); else switch case Tkey=K:_; case_: return(search_bst(Tlchild,K); case_: return(search_bst(Trchild,K); （分数：5.00）填空项 1:_33.以下
11、为顺序表的插入运算，分析算法，请在_处填上正确的语句。 void insert_sqlist(sqlist L,datatype x,int i)*将 X插人到顺序表 L的第 i-1个位置* if(L.1ast=maxsize)error(“表满“); if(i1)|(iL.last+1)error(“非法位置“); for(j=L.last;ji;j-) L.datai-=X; L.last=L.last+1; （分数：5.00）填空项 1:_五、B算法设计题/B(总题数：1，分数：10.00)34.若输入 12000个不同的整数，其值介于 0和 19999之间，采用散列表存储这些数，散列函
12、数为 h(k)=k/2，请设计实现的算法。（分数：10.00）_数据结构-2 答案解析(总分：100.00，做题时间：90 分钟)一、B单项选择题/B(总题数：15，分数：30.00)1.设 rear是指向非空带头结点的循环单链表的尾指针，则删除起始结点的操作可表示为( )（分数：2.00）A.s=rear;B.rear=rearnext; rear=rearnext; free(rea; free(;C.rear=rearnextnext;D.s=rearnextnext; free(rea; rearnextnext=snext; free(; 解析：2.在图的邻接表存储结构上执行深度优先
13、搜索遍历类似于二叉树上的 ( )（分数：2.00）A.先序遍历 B.中序遍历C.后序遍历D.按层次遍历解析：3.一个栈的入栈序列为 a1,a2,a3,a4,a5，则此栈不可能的输出序列是 ( )（分数：2.00）A.a5,a4,a3,a2,a1B.a4,a5,a3,a2,a1C.a4,a3,a5,a1,a2 D.a1,a2,a3,a4,a5解析：4.已知一个向量的第一个元素的存储地址是 loO，每个元素的长度为 2，则第 6个元素的地址是 ( )（分数：2.00）A.120B.112C.110 D.114解析：5.设计一个判别表达式中左、右括号是否配对出现的算法，采用( )数据结构最佳。（分数
14、：2.00）A.线性表的顺序存储结构B.栈 C.队列D.线性表的链式存储结构解析：6.设二叉树有 n个结点，则其深度为 ( )（分数：2.00）A.n-1B.nC.D.不确定 解析：7.在一棵二叉树中，第 k层上最多有( )个结点。（分数：2.00）A.2kB.2k-1C.2kD.2k-1 解析：8.在图的邻接表存储结构上执行广度优先搜索遍历类似于二叉树上的 ( )（分数：2.00）A.先根遍历B.中根遍历C.后根遍历D.按层次遍历 解析：9.以下有关数据结构的叙述，正确的是 ( )（分数：2.00）A.线性表的线性存储结构优于链式存储结构B.二叉树的第 i层上有 2i-1个结点，深度为 K的
15、二叉树上有 2k-1个结点C.二维数组是其数据元素为线性表的线性表 D.栈的操作方式是先进先出解析：10.二维数组 Mi,j的元素是 4个字符(每个字符占一个存储单元)组成的串，行下标 i的范围从 0到 4，列下标 j的范围从 0到 5。M 按行存储时元素 M3,5的起始地址与 M按列存储时元素( )的起始地址相同。（分数：2.00）A.M2,4B.M3,4 C.M3,5D.M4,4解析：11.设有一顺序栈 S，元素 s1，s 2，s 3，s 4，s 5，s 6依次进栈，如果 6个元素出栈的顺序是s2，s 3，s 4，s 5，s 6，s 1，则栈的容量至少应该是 ( )（分数：2.00）A.2
16、B.3 C.5D.6解析：12.一棵二叉树如图所示，其中序遍历的序列为 ( )（分数：2.00）A.ABDGCEFHB.DGBAECHF C.GDBEHFCAD.ABCDEFGH 解析：13.已知一个单链表中有 3000个结点，每个结点存放一个整数，( )可用于解决这 3000个整数的排序问题且不需要对算法作大的变动。（分数：2.00）A.直接插入排序方法B.简单选择排序方法C.快速排序方法D.堆排序方法 解析：14.深度为 6(根的层次为 1)的二叉树至多有( )个结点。（分数：2.00）A.31B.32 C.63D.64解析：15.在单链表中，删除 p所指结点的直接后继的操作是 ( )（分
17、数：2.00）A.pnext=pnextnext; B.p=pnext;pnext=pnextnext;C.pnext=pnext;D.p=pnextnext;解析：二、B填空题/B(总题数：10，分数：20.00)16.对快速排序来讲，其最好情况下的时间复杂度是_，其最坏情况下的时间复杂度是_。（分数：2.00）填空项 1:_ （正确答案：O(nlog 2n) O(n2)）解析：17.假设在线索二叉树中，结点的标志域的值为 0时，表示其指针域是指向孩子的指针，当结点的标志域为 1时，表示其指针域是指向前趋或者后继的线索，则一个结点是叶结点的充要条件是 1。（分数：2.00）填空项 1:_ （
18、正确答案：结点的左右标志都是 1）解析：18.散列函数的作用是： 1。（分数：2.00）填空项 1:_ （正确答案：压缩待处理的下标范围，待处理的|u|个值减少到 m个值，从而降低空间开销）解析：19.内部排序的方法可以分为五类：_、_、_、_、_。（分数：2.00）填空项 1:_ （正确答案：插入排序 选择排序 交换排序 归并排序 分配排序）解析：20.树的结点数目至少为_，二叉树的结点数目至少为_。（分数：2.00）填空项 1:_ （正确答案：1 0）解析：21.在结点数目相同的二叉树中， 1 的路径长度最短。（分数：2.00）填空项 1:_ （正确答案：完全二叉树）解析：22.从一个顺序
19、存储的循环队列中删除一个元素时，应该 1。（分数：2.00）填空项 1:_ （正确答案：先移动队首指针，后取出元素）解析：23.对于数组，通常具有的基本操作有_种，它们分别是_。（分数：2.00）填空项 1:_ （正确答案：两 查找和修改）解析：24.设有两个散列函数 H1(k)=k mod 13和 H2(k)=k mod 11+1，散列表为 T012，用双重散列解决冲突。函数 H1用来计算散列地址，当发生冲突时，H2 作为计算下一个探测地址的地址增量，假定在某一时刻表T的状态为 （分数：2.00）填空项 1:_ （正确答案：位置为 0）解析：25.无向图的邻接矩阵是 1，并且主对角线上的元素
20、的值为 2。（分数：2.00）填空项 1:_ （正确答案：对称零）解析：三、B解答题/B(总题数：4，分数：20.00)26.请根据下面所给出的邻接矩阵画出相应的有向图或者是无向图(顶点 vi表示)。 （分数：5.00）_正确答案：()解析：答：A，B，C 对应的图分别为： 27.对于如下一个有序的关键字序列5,9,12,18,23,31,37,46,59,66,71,78,85)，现在要求用二分法进行查找值为 18的关键字，则经过几次比较之后能查找成功?（分数：5.00）_正确答案：()解析：根据二分查找的过程，我们可以得到如下的比较结果： 第一次比较：5,9,12,18,23,31,37,
21、46,59,66,71,78,85, 第二次比较：5,9,12,18,23,31,37,46,59,66,71,78,85 第三次比较：5,9,1218,23,31,37,46,59,66,71,78,85 第四次比较：5,9,121823,31,37,46,59,66,71,78,85 则从上面的比较过程我们可以看出：经过四次比较之后，就可以查找到值为 18的关键字。28.已知有一关键字序列为505,94,512,61,908,170,897,275,653,463)，如果我们采用快速法对此序列进行排序(按照升序排序)，请给出每一趟排序的结果。（分数：5.00）_正确答案：()解析：快速排序
22、采用分治法进行，其基本思想如下：将原问题分解成为若干个规模更小但结构和原问题相似的子问题，递归地解这些子问题，然后将这些子问题的解的组合为原问题的解，根据上述思想，我们可以得到如下快速排序的各趟结果如下： 初始：505,94,512,61,908,170,897,275,653,432 第 1趟：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,5
23、12 第 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,275,462,505,512653897908 第 9趟：61,94,170,275,462,505,512,653,897908 第 10趟：61,94,170,275,462,505,512,653,897,90829.已知数据序列为12,5,9,20,6,31,24)，对该数据序列进行排序，试写出插入排序和
24、冒泡排序每趟的结果。 （分数：5.00）_正确答案：()解析：初始值键值序列125 9 20 6 31 24 初始键值序列12 5 9 20 6 31 24 第一趟之后5 9 12 6 20 2431 第二趟之后5 9 6 12 2024 31 第三趟之后5 6 9 1220 24 31 第四趟之后 5 6 9 12 20 24 31四、B算法阅读题/B(总题数：4，分数：20.00)30.以下运算实现在链队上的入队列，请在_处用适当的语句予以填充。 void EnQueue(QueptrTp*lq,DataType x) LqueueTp*P; p=(LqueueTp*)malloc(siz
25、eof(LqueueTp); _=x; pnext=NULL; (1qrear)next=_; _; （分数：5.00）填空项 1:_ （正确答案：pdata P lqrear=p）解析：31.以下运算实现在链栈上的初始化，请在_处用适当的语句予以填充。 void InitStack(LStackTp*ls)_;)（分数：5.00）填空项 1:_ （正确答案：ls=NULL）解析：32.以下算法在指针 T所指的二叉排序树上的查找键值等于 K的结点。成功时回送指向该结点的指针；否则回送空指针。请分析程序，并在_上填充合适的语句。 bitreptr search_bst(bitreptr T,ke
26、ytype K) if(T=NULL)return(NULL); else switch case Tkey=K:_; case_: return(search_bst(Tlchild,K); case_: return(search_bst(Trchild,K); （分数：5.00）填空项 1:_ （正确答案：return(T) TkeyK TkeyK）解析：33.以下为顺序表的插入运算，分析算法，请在_处填上正确的语句。 void insert_sqlist(sqlist L,datatype x,int i)*将 X插人到顺序表 L的第 i-1个位置* if(L.1ast=maxsize
27、)error(“表满“); if(i1)|(iL.last+1)error(“非法位置“); for(j=L.last;ji;j-) L.datai-=X; L.last=L.last+1; （分数：5.00）填空项 1:_ （正确答案：L.dataj=L.dataj-1）解析：五、B算法设计题/B(总题数：1，分数：10.00)34.若输入 12000个不同的整数，其值介于 0和 19999之间，采用散列表存储这些数，散列函数为 h(k)=k/2，请设计实现的算法。（分数：10.00）_正确答案：()解析：可利用两个数组来进行。用数组 HT0119993列函数的关键字。数组 R05999存放发生冲突时的关键字，且依次存放。HTi.next 指示发生冲突时存于 R中关键字的地址。 heash(HT,R) linklist HT; seqlist R; int i,j,k,n; for(i=0;i12000;i+) Hi.data=-1; Hi.next=-1；/*初始化*/ n=0; for(k=0;k12000;k+) scanf( j=i/2; if(Hj.data!=-1) Hj.next=n; An=i; n+; else Hj.data=i; /*hash*/
