2022年南通大学计算机科学与技术专业《数据结构与算法》科目期末试卷A(有答案).pdf
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空时,