数据结构复习题四.docxVIP

数据结构试题（四）一、选择题（共20分，每题1分）1．线性表（ a1,a2,…,an）以链接方式存储时，访问第i位置元素的时间复杂性为（ ）。A．O（i） B．O（1）C．O（n） D．O（i-1）2.设森林F对应的二叉树为B，它有m个结点，B的根为p,p的右子树结点个数为n,森林F中第一棵树的结点个数是（ ）。A. m-n B.m-n-1 C.n+1 D. 条件不足，无法确定3.非空的循环单链表head的尾结点p满足（ ）。A．p.link==head B．p.link==NIL C．p==NIL D．p==head4.一个长度为n的顺序存储的线性表中，向第i个元素(1≤i≤n+1)位置插入一个新元素时，需要从后面向前依次后移（）个元素。A． n-i B．n-i+1 C．n-i-1 D．i5.在一个单链表中，若要在p所指向的结点之后插入一个新结点，则需要相继修改（ ）个指针域的值。A．1 B．2 C．3 D．46. 在一个带有头结点的双向循环链表中，若要在p所指向的结点之后插入一个q指针所指向的结点，则需要对q-next赋值为（）。A. p-prior B. p-next C. p-next-next D. p-prior -prior7. 由3 个结点可以构造出多少种不同的二叉树？( )A．2 B．3 C．4 D．58.关键路径是事件结点网络中（ ）。A.从源点到汇点的最长路径 B.从源点到汇点的最短路径C 最长回路D 最短回路 9．n个结点的完全有向图含有边的数目（）。A. n*n B. n（n＋１）C.n／2 D.n*（n－l）10.链栈与顺序栈相比，一个较为明显的优点是( )。A. 通常不会出现栈空的情形 B. 插入操作更加便利 C.删除操作更加便利 D.通常不会出现栈满的情形11．若已知一个栈的入栈序列是1,2,3,…,n，其输出序列为p1,p2,p3，…，pN,若pN是n，则pi是（）。A．i B．n-i C．n-i+1 D．不确定12．最大容量为n的循环队列，队尾指针是rear，队头是front，则队空的条件是 （ ）。A．(rear+1) MOD n=front B．rear=frontC．rear+1=front D．(rear-l) MOD n=front13. 设有两个串 p 和 q ，其中 q 是 p 的子串，求 q 在 p 中首次出现的位置的算法称为（）。A．求子串 B．联接 C．匹配 D．求串长14. 下面关于串的的叙述中，哪一个是不正确的？（）。A．串是字符的有限序列 B．空串是由空格构成的串 C．模式匹配是串的一种重要运算 D．串既可以采用顺序存储，也可以采用链式存储15. 已知串 S= ‘aaab , 其 Next 数组值为（）。A．0123 B．1123 C．1231 D．121116.有一个长度为12的有序表,按二分查找法对该表进行查找,在表内各元素等概率情况下查找成功所需的平均比较次数为（ ）/12。A.35B. 37 C. 39 D.4317. 数列（21, 19, 37, 5, 2）经由冒泡排序法（bubble sort）由小到大排序，在第一次执行交换（swap）的后所得结果为( )。A．(19，21，37，5，2) B．(21，19，5，37，2) C．(21，19，37，2，5) D．(2，21，19，37，5)18.对于一个头指针为head的带头结点的单链表，判定该表为空表的条件是（）。A．head==NULL B．head→next==NULLC．head→next==head D．head!=NULL19.在下列存储形式中，哪一个不是树的存储形式？（ ） A．双亲表示法 B．孩子链表表示法 C．孩子兄弟表示法 D．顺序存储表示法20. 已知一棵二叉树的前序遍历结果为ABCDEF,中序遍历结果为CBAEDF,则后序遍历的结果为( )。A．CBEFDA B．FEDCBA C．CBEDFA D．不定二、填空题（共30分，每空2分）1. 通常从四个方面评价算法的质量：__（ 1 ）__、_（ 2 ） 、（ 3 ）和（ 4 ）_。2. 一个算法的时间复杂度为(n3+n2log2n+14n)/n2，其数量级表示为_（ 5 ）。3. 假定一棵树的广义表表示为A（C，D（E，F，G），H（I，J）），则树中所含的结点数为_（ 6 ）个，树的深度为_（ 5 ），树的度