广东工业大学数据结构(双学位)复习

《广东工业大学数据结构(双学位)复习》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、广东工业大学数据结构复习题【适用于双学位】一、判断题(正确的标记“√”，错误的标记“×”)：1.数据结构、数据元素和数据项在计算机中的映象分别为存储结构、结点和数据域。()2.顺序表和单链表都可以（按值或按序号）随机存取。()3.链表结点的物理地址可以不连续也可以连续。()4.堆排序所需的辅助空间大小与待排序的记录个数无关。()5.存储稀疏图，邻接矩阵法优于邻接表法。（）6.利用二叉查找树可以对数据进行排序。（）7.如果对有向图进行拓朴排序成功，则是有环图。（）8.序列(9,8,7,6,4,8,2,1)构成了大顶堆（）。9.使用链式存储字符串时，存储密度取决于结点大小的设定。(

2、)10.连通分量是无向图中的极大连通子图。()二、单选题：1.组成数据的不可分割的最小单位是（　）。A)数据元素B)数据项C)数据类型D)数据变量11.具有线性结构的数据结构是()。A)集合B)图C)队列D)二叉树12.栈的插入和删除操作在（）进行。A)栈底B)栈顶C)任意位置D)指定位置13.对线性表进行顺序查找时，要求线性表的存储结构为（）。A)压缩存储B)散列存储C)顺序存储或者链式存储D)索引存储14.在一个单链表中,若q所指结点是p所指结点的前驱结点,若在q与p之间插入一个s所指的结点,则执行()。A)s->next=p->next;p->next=s;B)p->ne

3、xt=s;s->next=q;C)p->next=s->next;s->next=p;D)q->next=s;s->next=p;15.假定一个顺序存储的循环队列的队头和队尾指针分别为front和rear，则判断队空的条件为()。A)front+1=rear；B)rear+1=front；C)front=0；D)front=rear；16.串的长度是指（）。A)串中所含不同字母的个数B)串中所含字符的个数C)串中所含不同字符的个数D)串中所含非空格字符的个数1.假设以行序为主序存储二维数组A[80][80]，设每个数据元素占2个存储单元，基地址为10，则元素A[5][6]的存储

4、位置是（）。A．812B．822C．1010D．10202.在一棵具有n个结点的二叉树的第i层上(假定根结点为第0层，i大于等于0而小于等于树的高度)，最多具有()个结点。A)2iB)2i+1C)2i-1D)2n3.对于具有e条边的无向图，它的邻接表中有()个边结点。A)e-1；B)2e；C)2(e-1)；D)e；4.图的深度优先搜索类似于树的（）次序遍历。A)先根；B)中根；C)后根；D)层次；5.一个对象序列的排序码为{46,79,56,38,40,84}，采用快速排序（以位于最左位置的对象为基准）所得到的第一次划分结果为()。A){38,46,79,56,40,84}；B

5、){38,79,56,46,40,84}；C){40,38,46,79,56,84}；D){38,46,56,79,40,84}；一、填空题：1.在树结构里。非根结点有且仅有一个前驱，称为，且存在一条从根到该结点的。6.对于顺序存储的栈，因为栈的空间是有限的，在进行操作时，可能发生栈的上溢；在进行操作时，可能发生栈的下溢。7.在以front为头指针的带头结点的单链表中，判断链表为空的条件为___________；如果用该链表存储队列，rear指向队尾，则判断队列空的条件为___________。8.由12个结点组成的完全二叉树的深度为___________，第3层上的结点数为_

6、__________。9.使用___________存储结构，可以将一棵树表示成二叉树形式，而该二叉树的根结点_________子树为空。10.动态查找表和静态查找表的重要区别在于前者包含有___________和___________运算，而后者不包含这两种运算。11.如果采用邻接矩阵A存储有向图G，那么顶点i的入度等于A中的_________；i的出度等于A中的_________。二、简答题：1.若带权无向图G的邻接矩阵如右图所示，顶点集是{V1,V2,V3,V4,V5}，画出图G的邻接表，要求每个顶点的表结点序号都是按照从小到大的次序链接；1.已知一棵二叉树的前序遍历的结

7、果序列是ABECKFGHIJ，中序遍历的结果是EBCDAFHIGJ，试写出这棵二叉树的后序遍历结果。2.已知森林如右图所示，画出由该森林转换得到的二叉树。ABCDEFGH23436425533.对于下图所示的无向图，试写出按照普里姆算法从顶点A出发得到最小生成树的过程中，依次选取的各条边（注：每条边的书写格式为“A—2—B”、“E—4—F”等）。4.对序列（49，38，64，97，23，32，51，56，12）执行升序的希尔排序算法，增量序列为（5，3，1），写出排序中第2趟的结果。第1趟：