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

广东工业大学数据结构复习题【适用于双学位】一、 判断题(正确的标记“”，错误的标记“”)：1. 数据结构、数据元素和数据项在计算机中的映象分别为存储结构、结点和数据域。( )2. 顺序表和单链表都可以（按值或按序号）随机存取。 ( )3. 链表结点的物理地址可以不连续也可以连续。 ( )4. 堆排序所需的辅助空间大小与待排序的记录个数无关。 ( )5. 存储稀疏图，邻接矩阵法优于邻接表法。（ ）6. 利用二叉查找树可以对数据进行排序。 （ ）7. 如果对有向图进行拓朴排序成功，则是有环图。（ ）8. 序列(9,8,7,6,4,8,2,1)构成了大顶堆 （ ）。9. 使用链式存储字符串时，存储密度取决于结点大小的设定。( )10. 连通分量是无向图中的极大连通子图。 ( )二、 单选题：1. 组成数据的不可分割的最小单位是（ ）。A) 数据元素 B) 数据项 C) 数据类型 D) 数据变量2. 具有线性结构的数据结构是 ( )。A) 集合 B) 图 C) 队列 D) 二叉树3. 栈的插入和删除操作在（ ）进行。A) 栈底 B) 栈顶 C) 任意位置 D) 指定位置4. 对线性表进行顺序查找时，要求线性表的存储结构为（ ）。A) 压缩存储 B) 散列存储C) 顺序存储或者链式存储 D) 索引存储5. 在一个单链表中,若q所指结点是p所指结点的前驱结点,若在q与p之间插入一个s所指的结点,则执行 ( )。A) s-next=p-next; p-next=s; B) p-next=s; s-next=q;C) p-next=s-next; s-next=p; D) q-next=s; s-next =p;6. 假定一个顺序存储的循环队列的队头和队尾指针分别为front和rear，则判断队空的条件为( )。A) front+1 = rear； B) rear+1 = front；C) front = 0； D) front = rear；7. 串的长度是指（ ）。A) 串中所含不同字母的个数 B) 串中所含字符的个数C) 串中所含不同字符的个数 D) 串中所含非空格字符的个数8. 假设以行序为主序存储二维数组A8080，设每个数据元素占2个存储单元，基地址为10，则元素A56的存储位置是（ ）。A812 B822 C1010 D10209. 在一棵具有n个结点的二叉树的第i层上(假定根结点为第0层，i大于等于0而小于等于树的高度)，最多具有( )个结点。 A) 2i B) 2i+1 C) 2i-1 D) 2n10. 对于具有e条边的无向图，它的邻接表中有 ( ) 个边结点。A) e-1； B) 2e； C) 2(e-1)； D) e；11. 图的深度优先搜索类似于树的（ ）次序遍历。A) 先根； B) 中根； C) 后根；D) 层次；12. 一个对象序列的排序码为46, 79, 56, 38, 40, 84，采用快速排序（以位于最左位置的对象为基准）所得到的第一次划分结果为( )。A) 38, 46, 79, 56, 40, 84 ； B) 38, 79, 56, 46, 40, 84；C) 40, 38, 46, 79, 56, 84 ； D) 38, 46, 56, 79, 40, 84；三、 填空题：1. 在树结构里。非根结点有且仅有一个前驱，称为 ，且存在一条从根到该结点的 。2. 对于顺序存储的栈，因为栈的空间是有限的，在进行 操作时，可能发生栈的上溢；在进行 操作时，可能发生栈的下溢。3. 在以front为头指针的带头结点的单链表中，判断链表为空的条件为_；如果用该链表存储队列，rear指向队尾，则判断队列空的条件为_。4. 由12个结点组成的完全二叉树的深度为_，第3层上的结点数为_。5. 使用_存储结构，可以将一棵树表示成二叉树形式，而该二叉树的根结点_子树为空。6. 动态查找表和静态查找表的重要区别在于前者包含有_和_运算，而后者不包含这两种运算。7. 如果采用邻接矩阵A存储有向图G，那么顶点i的入度等于A中的_；i的出度等于A中的_。四、 简答题：1. 若带权无向图G的邻接矩阵如右图所示，顶点集是V1, V2, V3, V4, V5，画出图G的邻接表，要求每个顶点的表结点序号都是按照从小到大的次序链接；2. 已知一棵二叉树的前序遍历的结果序列是ABECKFGHIJ，中序遍历的结果是EBCDAFHIGJ，试写出这棵二叉树的后序遍历结果。3. 已知森林如右图所示，画出由该森林转换得到的二叉树。ABCDEFGH23436425534. 对于下图所示的无向图，试写出按照普里姆算法从顶点A出发得到最小生成树的过程中，依次选取的各条边（注：每条边的书写格式为“A2B”、“E4F”等）。5. 对序列（49，38，64，97，23，32，51，56，12）执行升序的希尔排序算法，增量序列为（5，3，1），写出排序中第2趟的结果。第1趟：（32，38，56，12，23，49，51，64，97）第2趟：（ ）第3趟：（12，23，32，38，49，51，56，64，97）五、 算法题。1. （6分）阅读算法f1，并回答问题。(1) 设线性表L=(2, 3, 6, 5, 4)，并采用带头结点的单链表储存，写出执行算法f1(L)后的L；(2) 简述算法f1(L)对线性表L的操作意义。void f1(LinkList &L) LinkList p, s;p = L-next; L-next = NULL; while (p!= NULL) s=p-next; p-next=L-next; L-next=p; p=s; 2. 对顺序存储的有序表进行折半查找的算法，请填上遗漏的语句。 typedef struct ElemType * elem;int length;SSTable;int Search_Bin(SSTable ST,keytype K) /升序，折半查找，非递归 low=1;high=ST.le