2022年南华大学船山学院计算机科学与技术专业《数据结构与算法》科目期末试卷A(有答案)

2022年南华大学船山学院计算机科学与技术专业《数据结构与算法》

科目期末试卷A（有答案）

一、选择题

1、有一个100*90的稀疏矩阵，非0元素有10个，设每个整型数占2字节，则用三元组

表示该矩阵时，所需的字节数是（）。

A.60B.66C.18000D.33

2、将线性表的数据元素进行扩充，允许带结构的线性表是（）。

A.串B树C广义表D栈

3、静态链表中指针表示的是（）。

A.下一元素的地址

B.内存储器的地址

C.下一元素在数组中的位置

D.左链或右链指向的元素的地址

4、最大容量为n的循环队列，队尾指针是rear,队头：front,则队空的条件是（）。

A.（rear+1）MODn=front

B.rear=front

C.rear+l=front

D.（rear-1）MODn=front

5、下面关于串的叙述中，不正确的是（）。

A.串是字符的有限序列

B.空串是由空格构成的串

C.模式匹配是串的一种重要运算

D.串既可以采用顺序存储，也可以采用链式存储

6、循环队列放在一维数组A中，endl指向队头元素，end2指向队尾元素的后一个位置。

假设队列两端均可进行入队和次队操作，队列中最多能容纳M—1个元素。初始时为空，

下列判断队空和队满的条件中，正确的是()。

A.队空：endl==end2;队满：endl==(end2+l)modM

B.队空：endl==end2;队满：end2==(endl+1)mod(M—1)

C.队空：end2==(endl+1)modM;队满：endl==(end2+1)modM

D.队空：endl==(end2+l)modM;队满：end2==(endl+1)mod(M—1)

7、下列叙述中，不符合m阶B树定义要求的是()。

A.根结点最多有m棵子树B.所有叶结点都在同一层上

C.各结点内关键字均升序或降序排列D.叶结点之间通过指针链接

8、设X是树T中的一个非根结点，B是T所对应的二叉树。在B中，X是其双亲的右孩

子，下列结论正确的是()。

A.在树T中，X是其双亲的第一个孩子

B.在树T中，X一定无右兄弟

C.在树T中，X一定是叶结点

D.在树T中，X一定有左兄弟

9、在下述结论中，正确的有()。

①只有一个结点的二叉树的度为0。

②二叉树的度为2。

③二叉树的左右子树可任意交换。④深度为K的完全二叉树的结点个数小于或等于深度相

同的满二叉树。

A.①②③

B.⑦③④

C.②④

D.①④

10、下面给出的四种排序方法中，排序过程中的比较次数与排序方法无关的是()。

A.选择排序法B.插入排序法C.快速排序法D.堆排序法

二、填空题

11、在哈希函数H(key)=key%p中，p值最好取*

12、以下程序的功能是实现带附加头结点的单链表数据结点逆序连接，请填空完善之。

voidreverse(pointerh)

/*h为附加头结点指针*/

{pointerp,q;

p=h->next;h->next=NULL;

while(__LLL_)

(q=p；p=p->next;q->next=h->next;h->next-(2);

)

13、外排序的基本操作过程是和。

14、关键码序列(Q,H,C,Y,Q,A,M,S,R,D,F,X),要按照关键码值递增的

次序进行排序，若采用初始步长为4的希尔排序法，则一趟扫描的结果是；若采用

以第一个元素为分界元素的快速排序法，则扫描一趟的结果是o

15、VSAM(虚拟存储存取方法)文件的优点是：动态地,不需要文件进行并

能较快地____进行查找。

16、设T和P是两个给定的串，在T中寻找等于P的子串的过程称为又称P为

__________0

17、假设一个15阶的上三角矩阵A按行优先顺序压缩存储在一维数组B中，则非零元素

A9.9在B中的存储位置k=。(注：矩阵元素下标从1开始)

18、已知链队列的头尾指针分别是f和r,则将值x入队的操作序列是o

三、判断题

19、倒排文件的目的是为了多关键字查找。()

20、倒排文件是对次关键字建立索引。()

21、栈的输入序列是1,2,n,输出序列是al,a2,an若ai=n(l<i<n)则有:

ai>ai+l>...>ano()

22、设模式串的长度为m,目标串的长度为n,当n“m且处理只匹配一次的模式时，朴

素的匹配(即子串定位函数)算法所花的时间代价可能会更为节省。()

23、树形结构中元素之间存在一对多的关系。()

24、对于有n个结点的二叉树，其高度为log2n。()

25、在任何情况下，归并排序都比简单插入排序快。()

26、归并排序辅助存储为0(1)。()

27、若一个有向图的邻接矩阵对角线以下元素均为零，则该图的拓扑有序序列必定存在。

()

28、在索引顺序表中，实现分块查找，在等概率查找情况下，其平均查找长度不仅与表中

元素个数有关，而且与每块中元素个数有关。

()

四、简答题

29、已知n阶下三角矩阵A(即当i<j时，有aij=O),按照压缩存储的思想，可以将其

主对角线以下所有元素(包括主对角线上元素)依次存放于一维数组B中，请写出从第

一列开始采用列序为主序分配方式时在B中确定元素a.的存放位置的公式。

30、给出一组关键字：29,18,25,47,58,12,51,10,分别写出按下列各种排序方

法进行排序时的变化过程：

(1)归并排序，每归并一次书写一个次序。

(2)快速排序，每划分一次书写一个次序。

(3)堆排序，先建成一个堆，然后每从堆顶取下一个元素后，将堆调整一次。

31、用单链表保存m个整数，节点的结构为(data,link),且|data|<n(n为正整数)。

现要求设计一个时间复杂度尽可能高效地算法，对于链表中绝对值相等的节点，仅保留

第一次出现的节点而删除其余绝对值相等的节点。例如若给定的单链表head如下

HEAD

删除节点后的head为

HEAD

21~15—.J

要求

(1)给出算法的基本思想

(2)使用C或C++语言，给出单链表节点的数据类型定义。

(3)根据设计思想，采用C或C++语言描述算法，关键之处给出注释。说明所涉及算

法的时间复杂度和空间复杂度。

五、算法设计题

32、试编写一算法对二叉树按前序线索化。

33、输入一个字符串，内有数字和非数字字符，如：ak123x4561796073029ef4563o将其

中连续的数字作为一个整体，依次存放到一数组a中，例如123放入a[0],456放入

a[l],……。编程统计其共有多少个整数，并输出这些数。

34、（1）试分别找出满足下列条件的所有二叉树：（a）前序序列和中序序列相同：⑹

前序序列和后序序列相同；（c）中序序列和后序序列相同。（2）已知非空二叉树的结

点结构为（Ichild,data,rchild）,设计算法：从右向左依次将所有叶子的数据值放到向

量（假定向量的空间大于叶子的总个数）中。

35、写出按后序序列遍历中序线索树的算法。

参考答案

一、选择题

1、【答案】B

2、【答案】C

3、【答案】C

4、【答案】B

5、【答案】B

6、【答案］A

7、【答案】D

8、【答案】D

9、【答案】D

10、【答案】A

二、填空题

11、【答案】小于等于表长的最大素数或不包含小于20的质因子的合数

12、【答案】

(1)p!=NULL〃链表未到尾就一直进行

(2)q〃将当前结点作为头结点后的第一元素结点插入

13、【答案】生成有序归并段(顺串)；归并

14、【答案】(Q,A,C,S,Q,D,F,X,R,H,M,Y);(F,H,C,D,a,A,M,

Q,R,S,Y,X)

15、【答案】分配和释放存储空间；重组；对插入的记录@

16、【答案】模式匹配；模式串

17、【答案】93

18、【答案】s=(LinkedList*)malloc(sizeof(LNode));s->data=x;s->next=r-

>next;r->next=s;r=so

三、判断题

19、【答案】「

20、【答案】r

21、【答案】X

22、【答案】，

23、【答案】G

24、【答案】X

25、【答案】X

26、【答案】X

27、【答案】b

28、【答案】:

四、简答题

29、答：2阶下三角矩阵元素(1<，j<n,以)。第1列有n个元素，第j列有n-

j+1个元素，第1列到第j-1列是梯形，元素数为(n+(n-j+2)(j-l)/2,而a.在第j列

上的位置是为i-j+L所以n阶F三角矩阵A按列存储，其元素a,在一维数组B中的存

储位置k与i和j的关系为:

k=(n+(H-(j-1)+1)(j-1)/2+(/-7+1)=(2n-J)(j-l)/2+/

30、答：(1)2一路归并第一趟：18,29,25,47,12,58,10,51o

第二趟：18,25,29,47,10,12,51,580

第三趟:10,12,18,25,29,47,51,580

(2)快速排序第一趟:10,18,25,12,29,58,51,47。

第二趟:10,18,25,12,29,47,51,880

第三趟：10,12,18,25,29,47,51,88。

(3)堆排序

建大堆：58,47,51,29,18,12,25,10。

①51,47,25,29,18,12,10,58。

②47,29,25,10,18,12,51,58。

③29,18,25,10,12,47,51,58o

④25,18,12,10,29,47,51,58。

⑤18,10,12,25,29,47,51,58。

⑥12,10,18,25,29,47,51,580

⑦10,12,18,25,29,47,51,58。

31、答：⑴算法思想：

算法的核心思想是用空间换时间。定义一个大小为n的布尔数组flag,初始时所有的元

素都赋值为false,用来标识遍历过程中是否出现元素绝对值为flag的节点。然后遍历链

表，遍历过程中，每一个当前结点data域的绝对值所对应的flag位：若为真，则删除该

结点；若为假(false),则将flag位置为(true)。

(2)节点的数据结构定义如下：

typedefstructNode

(

intdata:

structNode*next;

};

(3)

boolflag[n];全局数组标志节点的绝对值是否出现过

Node*deleteABSEnqualNode(Node*head)

memset(flag,false:sizeof(flag)):

Node*pre=head;

Node*p=head->next:

while(p!=NULL)

{

if(flag[abs(p->data)])

{如果此绝对值已经在节点值的绝对值中出现过则删除该节点

pre->next=p->next:

deletep;

p=pre->next;

)

else{否则，将flag中对应的位置置为true,并将指针指向下一个元素

flag[abs(p->data)]=true;

p=p->next:

}

)

returnhead;

)

(4)只遍历一次链表，所以时间复杂度为O(m)(m为单链表中元素的个数)，申请大

小为n的数组，所以空间复杂度为O(n)(n为节点绝对值的最大值)。

五、算法设计题

32、答：算法如下：

BiThrTreepre=null;〃设置前驱

voidPreOrderThreat(BiThrTreeBT)

〃对以线索链表为存储结构的二叉树BT进行前序线索化

{if(BTl=null)

{if(BT->lchild==null){BT->ltag=l;BT->lchild=pre;}〃设置左线索

if(pre!=null&&pre->rtag==l)pre->rchild=BT;〃设置前驱的右线索

if(BT->rchild«null)BT->rtag=l;'〃为建立右链做准备

pre=BT;〃前驱后移

if(BT->ltag==0)PreOrderThreat(BT->lchild);//左子树前序线索化

PreOrderThreat(BT->rchild);〃右子树前序线索化

}//if(BT!«null)}〃结束PreOrderThreat

33、答：算法如下：

intCountlnt()

//从键世输入字符串，连续的数字字符算作一个整数,统计其中整数的个数

{charch;inti=0,a[]；//整数存储到数组a,i记整数个数

scanf("%c",&ch);//从左到右读入字符串

while(ch!='#')//'#'是字符小结束标记

if(isdigit(ch))//是数字字符

{num=0;//数初始化

while(isdigit(ch)&&chl='#')//拼数

{num=num*10+"ch'-'0';

scant("%c",&ch)；

)

a[i++]=num;

if(ch!='#')scanf("%c",&ch);//若拼数中输入了则不再输入

}

elsescanf("%c"r&ch);//输入非数字且非#时,继续输入字符

printf(”共有2d个整数，它们是：",i);

for(j=0;j<i;j++)

{printf("%6d",a[j));

if((j+l)%10==0)printfC\n")；}//每10个数输出在一行上

}//算法结束

34、答：(1)满足条件的二叉树如下：

(a)若前序序列与中序序列相同，则或为空树，或为任一结点至多只有右子树

的二叉树。

(b)若前序序列与后序序列相同，则或为空树，或为只有根结点的二叉树。

(c)若中序序列与后序序列相同，则或为空树，或为任一结点至多只有左子树

的二叉树。

(2)算法如下：

ElemTypeafmaxsize];inti=0;〃全局变量

voidInOrder(BiTreebt)

〃从右向左依次将二叉树bt的所有叶子的数据值放到a向比中

{if(bt)(InOrder(bt-rlchild);〃中序遍历右子树

if(!bt->lchild&&lbt->rchild)a[++i]»bt->data；〃叶结点

InOrder(bt->rchild);〃中序遍历左子树

}}//InOrder

35、答：算法如下：

BiThrTreeLeftMost(BiThrTreet)〃求结点tjft左了•孙的左线索

{BiThrTreep,t;

while(p->ltag-«O)pasp->lchild;〃沿左分支向下

if(p->lchild!^null)return(p->lchild);elsereturn(null);

}//LeftMost

BiThrTr