1、数据结构-7 及答案解析(总分：99.99，做题时间：90 分钟)一、B单项选择题/B(总题数：15，分数：30.00)1.磁带适合存储的文件类型是( )（分数：2.00）A.索引文件B.顺序文件C.散列文件D.多关键字文件2.假定一棵二叉树的结点为 18个，则此二叉树的最大高度为( )，最小高度为( )（分数：2.00）A.4B.5C.6D.183.下面关于线性表的叙述错误的是( )（分数：2.00）A.线性表采用顺序存储，必须占用一片连续的存储单元B.线性表采用顺序存储，便于进行插入和删除操作C.线性表采用链接存储，不必占用一片连续的存储单元D.线性袁采用链接存储，不便于插入和删除操作4.
2、当初始序列已经按键值有序时，用直接插入算法进行排序，需要比较的次数为 ( )（分数：2.00）A.n2B.nlonanC.log2nD.n-15.线性结构中的一个结点代表一个数据元素，通常要求同一线性结构的所有结点所代表的数据元素具有相同的特性，这意味着( )（分数：2.00）A.每个结点所代表的数据元素都一样B.每个结点所代表的数据元素包含的数据项的个数要相等C.不仅数据元素所包含的数据项的个数要相同，而且对应数据项的类型要一致D.结点所代表的数据元素有同一特点6.静态查找表与动态查找表二者的根本差别在于( )（分数：2.00）A.它们的逻辑结构不一样B.施加在其上的操作不同C.所包含的数据
3、元素的类型不一样D.存储实现不一样7.如果一个队列的入队顺序是 1,2,3,4,5，则此队列的出队顺序是( )（分数：2.00）A.5,4,3,2,1B.4,5,1,2,3C.1,2,3,4,5D.不确定8.考虑下列四种排序方法，在排序过程中，关键码比较的次数与记录的初始排列顺序无关的是( )（分数：2.00）A.直接插入排序和快速排序B.快速排序和归并排序C.直接选择排序和归并排序D.直接插入排序和归并排序9.循环链表的主要优点是( )（分数：2.00）A.不再需要头指针了B.已知某个结点的位置后，能够容易找到它的直接前趋C.在进行插入、删除运算时，能更好地保证链表不断开D.从表中任一结点出
4、发都能扫描到整个链表10.栈一般情况下常采用以下两种存储方式( )（分数：2.00）A.顺序结构和散列结构B.散列结构和链式结构C.线性结构和非线性结构D.顺序存储结构和链式结构11.( )方法是对序列中的元素通过适当的位置交换将有关元素一次性地放置在其最终位置上。（分数：2.00）A.归并排序B.插入排序C.快速排序D.选择排序12.下面的查找方式中，可以对无序表进行查找的是( )（分数：2.00）A.顺序查找B.二分查找C.二叉排序树D.B-树上的查找13.在一个单链表中，已知 q所指结点是 p所指结点的直接前趋，若在 p，q 之间插入 s结点，则执行( )操作。（分数：2.00）A.sn
5、ext=pnext;pnext=s;B.qnext=s;snext=p;C.pnext=snext;snext=p;D.pnext=s;snext=q;14.在一个具有 N个顶点的无向完全图中，包含的边的总数是( )（分数：2.00）A.N(N-1)/2B.N(N-1)C.N(N+1)D.N(N+1)/215.非空的循环单链表 head的尾结点(由指针 p所指)满足( )（分数：2.00）A.pnext=NULLB.p=NULLC.pnext=headD.p=head二、B填空题/B(总题数：10，分数：20.00)16.已知 L是带表头结点的非空单链表，且 P结点既不是首元结点，也不是尾元结
6、点，试从下列提供的答案中选择合适的语句序列。 (1)删除 P结点的语句序列是_； (2)删除尾元结点的语句是_。 a Pnext=Pnextnext b P=Pnextnext c while(Pnext!=Q)P=Pnext d while(Pnext!next!=Q)P=Pnext e while(Pnext!next!=NULL)P=Pnext f Q=P g Q=Pnext h P=L i L=Lnext j free(Q)（分数：2.00）填空项 1:_17.严格地讲，二维数组不是一种线性表，但数组可以看成是线性表在下述含义上的扩展：二维数组的数据元素是 1 的线性表。（分数：2.0
7、0）填空项 1:_18.记录的 1 结构是数据在物理存储器上的存储方式。（分数：2.00）填空项 1:_19.有 m个叶子结点(又称外结点)的哈夫曼树，其结点总数是 1。（分数：2.00）填空项 1:_20.在 B树上进行删除操作分为两个步骤，即：_和_。（分数：2.00）填空项 1:_21.树有三种常用的存储结构，即孩子链表法、孩子兄弟链表法和 1。（分数：2.00）填空项 1:_22.在图的邻接表表示中，每个顶点邻接表中的顶点数，对于有向图来说是_，对于无向图来说是_。（分数：2.00）填空项 1:_23.VSAM文件既可以在_中进行顺序存取，又可以从最高层的索引出发，进行按钮_的随机存取
8、。（分数：2.00）填空项 1:_24.查找表中主关键字指的是_，次关键字指的是_。（分数：2.00）填空项 1:_25.若一棵二叉树中只有叶结点和左、右子树皆非空的结点，设叶结点的个数为 1，则左右子树皆非空的结点个数为 1。（分数：2.00）填空项 1:_三、B解答题/B(总题数：4，分数：20.00)26.设某文件有 14个记录，其关键字分别为25,75,125,93,241,203,19,198,121,173,218，80，214，329。桶的容量 M=3，此时采用除留余数法构造散列函数，且散列函数为 h(k)=k%5，画出该散列文件的结构图，并说明如何对其进行删除或插入、检索等操作
9、。（分数：5.00）_27.对如图所示的有向图 G，请给出其广度优先遍历序列，并画其 DFS子树(以 A为源点)。 （分数：5.00）_28.已知：S=XYZ*+ T=(X+Z)*Y，试利用串的各种基本运算将 S转换为 T。（分数：5.00）_29.令 s=aaab，t=abcabaa，u=abcaabbabcabaacbacba，分别求出它们的 next值。（分数：5.00）_四、B算法阅读题/B(总题数：4，分数：20.00)30.以下算法假定以线性探测法解决冲突，在闭散列表 HL中查找键值为 K的结点，成功时回送该位置；不成功时回送标志-1。请分析程序，并在_上填充合适的语句。 int
10、search_closehash(keyt,ype K,closehash HL) d=H(K); /*计算散列地址*/ i=d; while(HLi.key!=K)/*未成功且未查遍整个 HL时继 续扫描*/ if(_)return(i); /*查找成功*/ else return(-1); /*查找失败*/ （分数：5.00）填空项 1:_31.以下为单链表的删除运算，分析算法，请在_处填上正确的语句。 void delete_lklist(1klist head,int i) p=find_lklist(head,i-1)； if(_) q=_; pnext=qnext; free(q)
11、; else error(“不存在第 i个结点“) （分数：5.00）填空项 1:_32.以下为顺序表的定位运算，分析算法，请在_处用正确的语句予以填充。 int locate_sqlist(sqlist L,datatype X) /*在顺序表 L中查找第一个值等于 X的结点。若找到回传该结点序号；否则回传 0*/_； while(iL.last) if(_)return(i); else return(0); （分数：5.00）填空项 1:_33.以下为单链表的建表算法，分析算法，请在_处填上正确的语句。 lklist create_iklist2() /*直接实现的建表算法。*/ hea
12、d=malloc(size); p=head; scanf(“%“, while(X!=$) q=malloc(size); qdata=x; pnext=q; _; scanf(“%“, _; return(head); 此算法的量级为_。（分数：5.00）填空项 1:_五、B算法设计题/B(总题数：1，分数：10.00)以二叉链表为存储结构，分别实现二叉树的下列运算：（分数：9.99）(1).PARENT(BT,X);（分数：3.33）_(2).CREATE(X,LBT,RBT);（分数：3.33）_(3).DELLEFT(BT,X).（分数：3.33）_数据结构-7 答案解析(总分：99
13、.99，做题时间：90 分钟)一、B单项选择题/B(总题数：15，分数：30.00)1.磁带适合存储的文件类型是( )（分数：2.00）A.索引文件B.顺序文件 C.散列文件D.多关键字文件解析：2.假定一棵二叉树的结点为 18个，则此二叉树的最大高度为( )，最小高度为( )（分数：2.00）A.4B.5 C.6D.18解析：3.下面关于线性表的叙述错误的是( )（分数：2.00）A.线性表采用顺序存储，必须占用一片连续的存储单元 B.线性表采用顺序存储，便于进行插入和删除操作C.线性表采用链接存储，不必占用一片连续的存储单元D.线性袁采用链接存储，不便于插入和删除操作解析：4.当初始序列已
14、经按键值有序时，用直接插入算法进行排序，需要比较的次数为 ( )（分数：2.00）A.n2B.nlonanC.log2nD.n-1 解析：5.线性结构中的一个结点代表一个数据元素，通常要求同一线性结构的所有结点所代表的数据元素具有相同的特性，这意味着( )（分数：2.00）A.每个结点所代表的数据元素都一样B.每个结点所代表的数据元素包含的数据项的个数要相等C.不仅数据元素所包含的数据项的个数要相同，而且对应数据项的类型要一致 D.结点所代表的数据元素有同一特点解析：6.静态查找表与动态查找表二者的根本差别在于( )（分数：2.00）A.它们的逻辑结构不一样B.施加在其上的操作不同 C.所包含
15、的数据元素的类型不一样D.存储实现不一样解析：7.如果一个队列的入队顺序是 1,2,3,4,5，则此队列的出队顺序是( )（分数：2.00）A.5,4,3,2,1B.4,5,1,2,3C.1,2,3,4,5 D.不确定解析：8.考虑下列四种排序方法，在排序过程中，关键码比较的次数与记录的初始排列顺序无关的是( )（分数：2.00）A.直接插入排序和快速排序B.快速排序和归并排序C.直接选择排序和归并排序 D.直接插入排序和归并排序解析：9.循环链表的主要优点是( )（分数：2.00）A.不再需要头指针了B.已知某个结点的位置后，能够容易找到它的直接前趋C.在进行插入、删除运算时，能更好地保证链
16、表不断开D.从表中任一结点出发都能扫描到整个链表 解析：10.栈一般情况下常采用以下两种存储方式( )（分数：2.00）A.顺序结构和散列结构B.散列结构和链式结构C.线性结构和非线性结构D.顺序存储结构和链式结构 解析：11.( )方法是对序列中的元素通过适当的位置交换将有关元素一次性地放置在其最终位置上。（分数：2.00）A.归并排序B.插入排序C.快速排序 D.选择排序解析：12.下面的查找方式中，可以对无序表进行查找的是( )（分数：2.00）A.顺序查找 B.二分查找C.二叉排序树D.B-树上的查找解析：13.在一个单链表中，已知 q所指结点是 p所指结点的直接前趋，若在 p，q 之
17、间插入 s结点，则执行( )操作。（分数：2.00）A.snext=pnext;pnext=s;B.qnext=s;snext=p; C.pnext=snext;snext=p;D.pnext=s;snext=q;解析：14.在一个具有 N个顶点的无向完全图中，包含的边的总数是( )（分数：2.00）A.N(N-1)/2 B.N(N-1)C.N(N+1)D.N(N+1)/2解析：15.非空的循环单链表 head的尾结点(由指针 p所指)满足( )（分数：2.00）A.pnext=NULLB.p=NULLC.pnext=head D.p=head解析：二、B填空题/B(总题数：10，分数：20.
18、00)16.已知 L是带表头结点的非空单链表，且 P结点既不是首元结点，也不是尾元结点，试从下列提供的答案中选择合适的语句序列。 (1)删除 P结点的语句序列是_； (2)删除尾元结点的语句是_。 a Pnext=Pnextnext b P=Pnextnext c while(Pnext!=Q)P=Pnext d while(Pnext!next!=Q)P=Pnext e while(Pnext!next!=NULL)P=Pnext f Q=P g Q=Pnext h P=L i L=Lnext j free(Q)（分数：2.00）填空项 1:_ （正确答案：fhcab egcj）解析：17.
19、严格地讲，二维数组不是一种线性表，但数组可以看成是线性表在下述含义上的扩展：二维数组的数据元素是 1 的线性表。（分数：2.00）填空项 1:_ （正确答案：线性表）解析：18.记录的 1 结构是数据在物理存储器上的存储方式。（分数：2.00）填空项 1:_ （正确答案：物理）解析：19.有 m个叶子结点(又称外结点)的哈夫曼树，其结点总数是 1。（分数：2.00）填空项 1:_ （正确答案：2m-1）解析：20.在 B树上进行删除操作分为两个步骤，即：_和_。（分数：2.00）填空项 1:_ （正确答案：在树上查找被删除关键字 K所在的地点 删除 K）解析：21.树有三种常用的存储结构，即孩
20、子链表法、孩子兄弟链表法和 1。（分数：2.00）填空项 1:_ （正确答案：双亲表示法）解析：22.在图的邻接表表示中，每个顶点邻接表中的顶点数，对于有向图来说是_，对于无向图来说是_。（分数：2.00）填空项 1:_ （正确答案：出度数 度数）解析：23.VSAM文件既可以在_中进行顺序存取，又可以从最高层的索引出发，进行按钮_的随机存取。（分数：2.00）填空项 1:_ （正确答案：顺序集 关键字）解析：24.查找表中主关键字指的是_，次关键字指的是_。（分数：2.00）填空项 1:_ （正确答案：能惟一标识数据元素的数据项 不能惟一标识数据元素的数据项）解析：25.若一棵二叉树中只有叶
21、结点和左、右子树皆非空的结点，设叶结点的个数为 1，则左右子树皆非空的结点个数为 1。（分数：2.00）填空项 1:_ （正确答案：1-1）解析：三、B解答题/B(总题数：4，分数：20.00)26.设某文件有 14个记录，其关键字分别为25,75,125,93,241,203,19,198,121,173,218，80，214，329。桶的容量 M=3，此时采用除留余数法构造散列函数，且散列函数为 h(k)=k%5，画出该散列文件的结构图，并说明如何对其进行删除或插入、检索等操作。（分数：5.00）_正确答案：()解析：由于散列函数 h(k)=k%5，从而可得按散列函数方法组织的文件结构如下
22、(可选桶数为(14/3)(1+10%)=5)； 27.对如图所示的有向图 G，请给出其广度优先遍历序列，并画其 DFS子树(以 A为源点)。 （分数：5.00）_正确答案：()解析：图的广度优先遍历类似于树的按层遍历：首先访问源点，并将其记为访问过，接着访问 vi的所有未被访问的邻接点 vi1，v i2，v it。并将它们均记为已经访问过，然后再按照 vi1，v i2，v it的次序，访问每个顶点的所有未被访问的邻接点，并均记它们为已访问过，按此规则类推，直到图中所有和源点vi有路径相通的顶点都访问过为止。则按照广度优先遍历规则，我们得到此遍历序列为 ABCDEFGHI。相应的子树为： 28.
23、已知：S=XYZ*+ T=(X+Z)*Y，试利用串的各种基本运算将 S转换为 T。（分数：5.00）_正确答案：()解析：STR1=REPLACE(SUBSTR(S,1,1)，X，(X) STR1=(X STR2=CONCAT(STRl SUBSTR(S,5,1) STR2=(X+1) STR3=REPLACE(SUBSTR(S,3,1)，Z，Z) STR3=Z) STR4=CONCAT(STR2,STR3) STR4=(X+Z) STR5=CONCAT(STR4,SUBSTR(S,4,1) STR5=(X+Z)* T=CONCAT(STR5.SUBSTR(S,2,1) T=(X+Z)*Y29
24、.令 s=aaab，t=abcabaa，u=abcaabbabcabaacbacba，分别求出它们的 next值。（分数：5.00）_正确答案：()解析：当位置 j=1时，nextj=0；当位置 j1 时，nextj的值为模式串的位置 1到 j-1构成的串中所出现的首尾相同的子串的最大长度加 l，无首尾相同的子串时 nextj的值为 1。本题答案如下表所示： j 1 2 3 4 5 6 7模式串 s a a a bnextj 0 1 2 3模式串 s a b c a b a anextj 0 1 1 1 2 3 2j 1 2 3 4 5 6 7 8 9 10模式串 u a b c a a b
25、b a b cnextj 0 1 1 1 2 2 3 1 2 3j 11 12 13 14 15 16 17 18 19 20模式串 u a b c a b a anectj 4 5 3 2 2 1 1 2 1 1四、B算法阅读题/B(总题数：4，分数：20.00)30.以下算法假定以线性探测法解决冲突，在闭散列表 HL中查找键值为 K的结点，成功时回送该位置；不成功时回送标志-1。请分析程序，并在_上填充合适的语句。 int search_closehash(keyt,ype K,closehash HL) d=H(K); /*计算散列地址*/ i=d; while(HLi.key!=K)/
26、*未成功且未查遍整个 HL时继 续扫描*/ if(_)return(i); /*查找成功*/ else return(-1); /*查找失败*/ （分数：5.00）填空项 1:_ （正确答案：(i+1)/m HLi.key=K）解析：31.以下为单链表的删除运算，分析算法，请在_处填上正确的语句。 void delete_lklist(1klist head,int i) p=find_lklist(head,i-1)； if(_) q=_; pnext=qnext; free(q); else error(“不存在第 i个结点“) （分数：5.00）填空项 1:_ （正确答案：(p!=NUL
27、L) if(_)return(i); else return(0); （分数：5.00）填空项 1:_ （正确答案：i=1 iL.last)）解析：33.以下为单链表的建表算法，分析算法，请在_处填上正确的语句。 lklist create_iklist2() /*直接实现的建表算法。*/ head=malloc(size); p=head; scanf(“%“, while(X!=$) q=malloc(size); qdata=x; pnext=q; _; scanf(“%“, _; return(head); 此算法的量级为_。（分数：5.00）填空项 1:_ （正确答案：p=q pne
28、xt=NULL O(n)）解析：五、B算法设计题/B(总题数：1，分数：10.00)以二叉链表为存储结构，分别实现二叉树的下列运算：（分数：9.99）(1).PARENT(BT,X);（分数：3.33）_正确答案：()解析：bitreptr parent(bitreptr BT,p; datatype x) /*调用前 P为空指针*/ if(BT!=NULL) if(BTdata=X)return(p) /*找到，返回其父结点*/ elsep=BT; parent(BTlchild,p-,x); /*查找其左子树*/ parent(BTrchild,p,x)； /*查找其右子树*/ (2).C
29、REATE(X,LBT,RBT);（分数：3.33）_正确答案：()解析：Void create(datatype x; bhreptr LBT,LBR) BT=mallloc(size) BTdata=x; BTlchild=LBT; /*赋左子树*/ BTrchild=LBR; /*赋右子树*/ (3).DELLEFT(BT,X).（分数：3.33）_正确答案：()解析：Void delleft(bitreptr BT; datatype x) if(BT!=NULL) if(BTdata=x) BTlchild=NULL; /*删除其左子树*/ return; /*结束*/ else delleft(BTlchild,x)； /*转左子树*/ delleft(BTrchild,x); /*转右子树*/
