文档详情

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

发布:2024-10-08约5.5千字共11页下载文档
文本预览下载声明

2022年南通大学计算机科学与技术专业《数据结构与算法》科目期末

试卷A(有答案)

一、选择题

1、将线性表的数据元素进行扩充,允许带结构的线性表是()。

A.串B.树C.广义表D.栈

2、用数组r存储静态链表,结点的next域指向后继,工作指针j指向链中结点,使j沿

链移动的操作为()。

A.j=r[j].nextB.j=j+lC.j=j-nextD.j=r[j]-next

3、静态链表中指针表示的是()。

A.下一元素的地址

B.内存储器的地址

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

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

4、向一个栈顶指针为h的带头结点的链栈中插入指针s所指的结点时,应执行()。

A.h-next=s

B.s-next=h

C.s-next=h;h-next=s

D.s-next=h-next;h-next=s

5、已知有向图G=(V,E),其中V={V1,V2,V3,V4,V5,V6,V7},E={V1,V2,

V1,V3,V1,V4,V2,V5,V3,V5,V3,V6,V4,V6,V5,V7,

V6,V7},G的拓扑序列是()。

A.V1,V3,V4,V6,V2,V5,V7B.V1,V3,V2,V6,V4,V5,V7

C.V1,V3,V5,V2,V6,V7D.V1,V2,V5,V3,V4,V6,V7

6、若一棵二叉树的前序遍历序列为a,e,b,d,c,后序遍历序列为b,c,d,e,a,

则根结点的孩子结点()。

A.只有eB.有e、bC.有e、cD.无法确定

7、若元素a,b,c,d,e,f依次进栈,允许进栈、退栈操作交替进行,但不允许连续三

次进行退栈操作,则不可能得到的出栈序列是()。

8、已知一棵二叉树的前序遍历结果为ABCDEF,中序遍历结果为CBAEDF,则后序遍历结

果为()。

A.CBEFDAB.FEDCBAC.CBEDFA不定D.

9、下述二叉树中,哪一种满足性质:从任一结点出发到根的路径上所经过的结点序列按

其关键字有序()。

A.二叉排序树B.哈夫曼树C.AVL树D.堆

10、一组记录的关键码为(46,79,56,38,40,84),则利用快速排序的方法,以第

一个记录为基准得到的一次划分结果为()。

A.(38,40,46,56,79,84)B.(40,38,46,79,56,84)

C.(40,38,46,56,79,84)D.(40,38,46,84,56,79)

二、填空题

11、顺序查找n个元素的顺序表,若查找成功,则比较关键字的次数最多为______次;当

使用监视哨时,若查找失败,则比较关键字的次数为______。

12、在哈希函数H(key)=key%p中,p值最好取______。

13、建立索引文件的目的是______。

14、以下是用类C语言写出的算法,该算法将以二叉链表存储的二叉树中的叶结点按从

左到右的顺序链成一个带头结点的双向循环链表,链接时,结点的Lchild域作为前链域,

指向结点的直接前驱,结点的Rchild域作为后链域,指向结点的直接后继。算法中,使

用一个顺序栈stack,栈顶指针为top,p,t为辅助指针,head为双向循环链表的头指针。

试填充算法中的空格,使算法完整。

15、设有两个算法在同一机器上运行,其执行时闻分别为100n2和2n,要使前者快于后

者,n至少为______。

16、当两个栈共享一存储区时,栈利用一维数组stack(1,n)表示,两栈顶指针为top[1]

与top[2],则当栈1空时,

显示全部
相似文档