南通大学2022-2023学年《数据结构》期末考试试卷（B卷）附参考答案

南通大学2022—2023学年期末

《数据结构》考试试卷（B卷）

考试范围：《数据结构》；满分：100分；考试时间：120分钟

院/系：专业：姓名：考号：

题号一二三四五总分

得分

注意事项：

1.答题前填写好自己的姓名、专业、考号等信息

2.本试题所有答案，应按试题顺序写在答题纸上，不必抄题，写清题号。写在试卷上不得

分。

第I卷（选择题）

评卷人得分

一、单项选择题：1〜10小题。下列每题给出的选项中，只有一

个选项是符合题目要求的。

1.将长度为n的单链表链接在长度为m的单链表之后的算法的时间复杂度为（）

A.O（1）

B.0（n）

C.0（m）

D.0（m+n）

2.在一个长度为n（n>l）的带头结点的单链表h上，设有尾指针r（指向尾结点），则执

行（）操作与链表的长度有关。

A.删除单链表中的第一个元素

B.删除单链表中的最后一个元素

C.在单链表第一个元素前插入一个新元素

D.在单链表最后一个元素后插入一个新元素

3.下列选项中，在I/O总线的数据线上传输的信息包括（）

I.1/0接口中的命令字

11.1/0接口中的状态字

III.中断类型号

A.仅I、II

B.仅I、III

C.仅II、III

D.I、II、III

4.已知两个长度分别为m和n的升序链表，若将它们合并为一个长度为m+n的降序链

表，则最坏情况下的时间复杂度是()

A.O(n)

B.O(m*n)

C.O(min(m,n))

D.O(max(m,n))

5.内部异常(内中断)可分为故障(fault)＞陷阱(trap)和终止(abort)三类。下列有

关内部异常的叙述中，错误的()

A.内部异常的产生与当前执行指令相关

B.内部异常的检测由CPU内部逻辑实现

C.内部异常的响应发生在指令执行过程中

D.内部异常处理后返回到发生异常的指令继续执行

6.已知一个线性表为(38,25,74,63,52,48),假定采用H(K)=Kmod7计算散

列地址进行散列存储，若利用线性探测的开放定址法处理冲突，则在该散列表上进行查找

的平均查找长度为()；若利用链地址法处理冲突，则在该散列上进行查找的平均查

找长度为()

A.1.5,1

B.1.7,3/2

C.2,4/3

D.2.3,7/6

7.通过POP3协议接收邮件时，使用的传输层服务类型是()

A.无连接不可靠的数据传输服务

B.无连接可靠的数据传输服务

C.有连接不可靠的数据传输服务

D.有连接可靠的数据传输服务

8.下列选项中，不能构成折半查找中关键字比较序列的是()

A.500,200,450,180

B.500,450,200,180

C.180,500,200,450

D.180,200,500,450

9.在双向链表存储结构中，删除p所指的结点时须修改指针(）O

A.p->prior->next=p->next;p->next->prior=p->prior;

B.p->prior=p->prior->prior;p->prior->next=p;（删Ip的前趋）

C.p->next->prior=p;p->next=p->next->next;

D.p->next=p->prior->prior;p->prior=p->next->next;

10.下列有关浮点数加减运算的叙述中，正确的是（）

1.对阶操作不会引起阶码上溢或下溢

II.右规和尾数舍入都可能引起阶码上溢

III.左规时可能引起阶码下溢

IV.尾数溢出时结果不一定溢出

A.仅II、ni

B.仅I、II、IV

C.仅I、HRIV

D.I、II、III、IV

第n卷(非选择题)

评卷人得分

二、填空题：11〜15小题。请将答案写在答题纸指定位置上。

11.所谓算法(Algorithm)是对特定问题求解步骤的一种描述，它是指令的其中每个指令

表示一个或多个操作。算法的五个重要特性是、、、

和O

12.是数据不可分割的最小单元，是具有独立含义的最小标识单位。例如构成一

个数据元素的字段、域、属性等都可称之为。

13.给定一组数据6,2,7,10,3,12｝以它构造一棵哈夫曼树，则树高为,带权

路径长度WPL的值为0

14.在哈希函数H(key)=key%p中，p值最好取。

15.n个顶点的连通图至少有条边。

评卷人得分

三、判断题：16〜25小题。请将答案写在答题纸指定位置上。

16.完全二叉树一定存在度为1的结点。()

17.有n个数顺序(依次)入栈,出栈序列有Cn种，Cn=[l/(n+1)]*(2n)!/[(n!)*

(n!)]□()

18.数据的逻辑结构是指各元素之间的逻辑关系，是根据用户需要而建立的。()

19.二叉排序树删除一个结点后，仍是二叉排序树。()

20.若输入序列为1,2,3,4,5,6,则通过一个栈可以输出序列1,5,4,6,2,3。

()

21.栈是实现过程和函数等子程序所必需的结构。()

22.拓扑排序的有向图中，最多存在一条环路。()

23.哈希函数越复杂越好，因为这样随机性好，冲突概率小。()

24.若一棵二叉树中的结点均无右孩子，则该二叉树的中根遍历和后根遍历序列正好相

同。()

25.二叉树中每个结点的两棵子树的高度差等于1。()

评卷人得分

----------------四、程序填空：26〜27小题。请将答案写在答题纸指定位置上。

26.完善下面算法。

后缀表达式求值，表达式13/25+61的后缀表达式格式为：13,25/61,+

FUNCcompute(a):real；后缀表达式存储在数组中。

BEGIN

setnull(s)；i:=l；ch:=(1)；

WHILEch<>,@,DO

BEGIN

CASEchOF

x:=0；

WHILEch<>9,'DO

BEGIN

x:=x*10+ord(ch)-ord('O')；

i:=i+l；ch:=(2)；

END

'+':x:=pop(s)+pop(s)；

'-':x:=pop(s)；x:二pop(s)-X;

'*':x:=pop(s)*pop(s)；

79:x:=pop(s)；x:二pop(s)/x；

ENDCASE

push(s,x)；i:=i+l；ch:=a[i]；

END；

comput:=(3)；

END；

27.一线性表存储在带头结点的双向循环链表中，L为头指针，在空缺处填写相应的语

句。

voidunknown(BNODETP*L)

p=L->next;q=p->next;r=q->next；

while(q!=L)

while(p!=L)&&(p->data>q->data)p=p->prior；

q->prior->next=r；(1)；

q->next=p->next；q->prior=p；

(2)；(3)；q=r；p=q->prior；

(4)：

评卷人得分

五、算法设计题：28〜31小题。请将答案写在答题纸指定位置

上。

28.设有一个数组中存放了一个无序的关键序列Kl、K2...Kn„现要求将Kn放在将

元素排序后的正确位置上，试编写实现该功能的算法，要求比较关键字的次数不超过no

（注：用程序实现）

29.设计算法将一个带头结点的单链表A分解为两个具有相同结构的链表B、C,其中B

表的结点为A表中值小于零的结点，而C表的结点为A表中值大于零的结点（链表A的

元素类型为整型，要求B、C表利用A表的结点）

30.设中序穿线二叉树的结点由五个域构成：info:给出结点的数据场之值。LL：当ET为1

时，则给出该结点的左儿子之地址，当LT为。时，则给出按中序遍历的前驱结点的地址。

LT:标志域，为1或为0oRL：当RT为1时，则给出该结点的右儿子的地址；当RT为0

时，则给出按中序遍历的后继结点地址。RT:标志域为0或为1。

请编写程序，在具有上述结点结构的中序穿线二叉树上，求某一结点p的按后序遍历次序

的后继结点的地址q,设该中序穿线二叉树的根结点地址为r。另外，请注意必须满足：

（1）额外空间的使用只能为O（1）,（2）程序为非递归。

31.设记录RI,R2,…，Rn按关键字值从小到大顺序存储在数组r[L.n]中，在r[n+l]处设

立一个监督哨，其关键字值为+oo；试写一查找给定关键字k的算法。

【标准答案】

第I卷(选择题)

一、单项选择题：1〜10小题。下列每题给出的选项中，只有一个选项是符合题目要求

的。

1.C

2.B

3.D

4.D

5.D

6.C

7.D

8.A

9.A

10.D

第II卷(非选择题)

二、填空题：11〜15小题。请将答案写在答题纸指定位置上。

11.有限序列、有穷性、确定性、可行性、输入、输出

12.数据项、数据项

13.5；96

14.小于等于表长的最大素数或不包含小于20的质因子的合数

15.n-1

三、判断题：16〜25小题。请将答案写在答题纸指定位置上。

16.x

17.N

18.Y

19.7

20.x

21.N

22.x

23.x

24.q

25.x

四、程序填空：26〜27小题。请将答案写在答题纸指定位置上。

26.(1)a(或a[l](2)a[i](3)pop(s)或s[l]；

27.(1)r->prior=q->prior;〃将q结点摘下，以便插入到适当位置。

(2)p->next->prior=q;//(2)(3)将q结点插入

(3)p->next=q;

(4)-next;或r=q->next;〃后移指针，再将新结点插入到适当位置。

五、算法设计题：28〜31小题。请将答案写在答题纸指定位置上。

28.intPartition(RecTypeK[],int1,intn)

〃交换记录子序列K[L.n]中的记录，使枢轴记录到位，并返回其所在位置，

〃此时，在它之前(后)的记录均不大(小)于它

inti=l;j=n;K[0]=K[j];x=K[j].key;

while(i<j)

while(i<j&&K[i].key<=x)i++;

if(i<j)K[j]=K[i];

while(i<j&&K[j].key>=x)j—;

if(i<j)K[i]=K[j];

}//while

K[i]=K[0];returni;

}//Partition

29.voidDisCreat1(LinkedListA)

〃人是带头结点的单链表，链表中结点的数据类型为整型。本算法将A分解成两个单链表

B和C,B中结点的数据小于零，C中结点的数据大于零。

B=A;

C=(LinkedList)malloc(sizeof(LNode));〃为C申请结点空间。

C->next=null//C初始化为空表。

p=A->next;〃p为工作指针。

B->next=null;//B表初始化。

while(p!=null)

r=p->next;〃暂存p的后继。

if(p->data<0)〃小于0的放入B表。

p->next=B->next;B->next=p;}〃将小于0的结点链入B表。

elsep->next=C->next;C->next=p;}

p=r;〃p指向新的待处理结点。

)

}〃算法结束。

30.BiThrTreeInThrPostSucc(BiThrTreer,p)

〃在中序线索二叉树r上，求结点p(假定存在)的后序后继结点q)

if(p==r)return(null)〃若p为根结点，后序后继为空

T二p

whil