资源描述：
《new数据结构复习题.doc》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、数据结构复习题一、填空数据结构按物理结构可分为线性结构、、和集合。在单链表中，要删除某一指定的结点，必须先找到该结点的()结点。对于一个具有n个结点的单链表，在*p结点后插入一个新结点的时间复杂度是()；在给定值x的结点后插入一个新结点的时间复杂度是()。在线性结构、树形结构和图形结构中，直接前驱和直接后继结点之间分别存在着、1：N和的联系。一棵有n个节点的满二叉树有 个度为1的节点。中缀表达式A-(B+C/D)*E的后缀表达式是 。具有n个顶点的完全无向图具有条边，利用邻接矩阵表
2、示的完全无向图具有行，若无向图的邻接矩阵不存在边，则赋值_______。平衡二叉树是每个结点的左、右子树的高度至多相差______。一个有向图G中若有弧、和,图G的拓扑序列为______________。直接插入排序的时间复杂度是 ，它(是/否？) 稳定的。广义表((a,b),c,d)的表头是，表尾是。限定在同一端进行插入、删除的线性表称为 ；该端称为 。内排序算法中空间复杂度最大的算法是 。设顺序栈S为空，若
3、6个元素入栈顺序为a1,a2,a3,a4,a5,a6，出栈顺序为a2,a4,a3,a6,a5,a1，则栈S的容量至少为 。G是一个非连通无向图，共有28条边，则该图至少有________个顶点。一棵有n个结点满二叉树有 个度为1的结点，有 个分支结点和 个叶子结点，该满二叉树的深度为 。深度为6（根的层次为1）的完全二叉树至多有_________结点，至少有_________结点。G是一个非连通无向图，共有28条边，则该图至少有________个顶点。从邻接矩阵A=中可以看出，
4、该图共有________个顶点。如果是有向图，该图共有________条弧，如果是无向图，则共有________条边。一个有向图G中若有弧、和,则在图G的拓扑序列中，顶点vi,vj和vk的相对位置为______________。二、选择题PS将s结点插入到p结点之后， 实现语句为（ ）。A.s->next=p->next;p->next=s;B.(*p).next=s;(*s).next=(*p).next;C.s->next=p->n
5、ext;p->next=s->next;D.s->next=p+1;p->next=s;将一棵有100个节点的完全二叉树从上到下，从左到右编号，根节点的编号为1，则编号为49的节点的右孩子编号是（ ）。A．97 B．98 C．99 D．100带头结点的单链表head为空的判定条件是()。A.head=NULLB.head==NULLC.head->next=NULLD.head->next==NULL（ ）是C语言中”abcd321ABCD”的子串。A. abcd B. 32
6、1ab C. “abcABC” D.“21AB”若广义表A满足head(A)=tail(A)，则A为A.()B.(())C.((),())D.((),(),())有5个顶点的图，若为连通图，则至少有（ ）条边。A．3 B．4 C．5 D．6一组记录的关键码为（46,79,56,38,40,84），则利用快速排序的方法，以第一个记录为基准得到的一次划分结果为（ ）。A. 38，40，46，56，79，84 B. 40，38，46，79，56，84C. 40，38，46，56
7、，79，84 D. 40，38，46，84，56，79有5个顶点的图，若为强连通图，至少有（ ）条边。A．3 B．4 C．5 D．6下列不属于内排序算法的是（ ）。A.归并排序B.基数排序C.拓扑排序D.堆排序已知广义表LS=((a,c),(b,d))，运算head和tail函数取出LS中元素b的运算是（ ）。A．head(tail(LS))B．tail(head(LS))C．head(tail((tail(LS)))D．head(head(tail(LS)))线性链表
8、中各链接点之间的地址（ ）。A. 必须连续 B. 部分地址必须连续 C. 不一定连续 D. 以上答案都错误()是C语言中”abcd321ABCD”的子串。A．abcdB.321ABC.’’abcABC“D.“21AB“若串s=“software“，其子串的个数是()。A．8B.9C.36D.37在一个单链表中，删除*p结点的直接后继结点，则执行（ ）。A.p=p->nextB.p=p->next->ne
