数据结构期末试卷A-下hqu.doc

数据结构试卷（A）数学科学学院11-12学年下学期学 号： 姓 名： 日期： 题 号一二三四五总 分得 分一、选择题（每小题2分，共30分，请写在答卷纸上）：1.下列程序段的时间复杂度为（ ）。i=0，s=0； while (snext=head; head=p; B. p-next=head-next; head-next=p;C. p-next=head; p=head; D. head=p; p-next=head;4.一个栈的输入序列为a b c，则下列序列中不可能是栈的输出序列的是( )。A. b c a B. c b a C. c a b D. a b c5.无向完全图G有n个结点，则它的边的总数为（ ）。A.n2 B.n(n-1) C.n(n-1)/2 D.(n-1)6.若一棵二叉树有10个度为2的结点，5个度为1的结点，则度为0的结点数是（ ）。A.9 B.11 C.15 D.不确定7.设连通图G中的边集E=(a,b),(a,c),(a,e),(b,e),(d,e),(d,f),(e,f)，则在下面的4个序列中，不符合深度优先遍历的序列是（ ）。A.acfdeb B.aebdfc C.aedfbc D.aefdbc8.队列是一种（ ）的线性表。A.先进先出B.先进后出C.只能插入D.只能删除 9.已知二叉排序树G，要输出其结点的有序序列，则采用的遍历方法是（ ）。A.按层遍历 B.先序遍历 C.中序遍历 D.后序遍历10. 设按照从上到下、从左到右的顺序从1开始对完全二叉树进行顺序编号，则编号为i结点的左孩子结点的编号为（ ）。A. 2i+1B. 2iC. i/2D. 2i-111.对序列(15，9，7，8，20，-1，4)进行排序，第一趟排序后的序列变为(4，9，-1，8，20，7，15)，则采用的排序方法是（ ）。A.选择 B.快速 C.希尔 D.冒泡12.若有18个元素的有序表存放在一维数组A19中，第一个元素放A1中，现进行二分查找，则查找A3的比较序列的下标依次为( )A. 1，2，3 B. 9，5，2，3 C. 9，5，3D. 9，4，2，313.设顺序循环队列QM-1的头指针和尾指针分别为F和R，头指针F总是指向队头元素的当前位置，尾指针R总是指向队尾元素的后一位置，则该循环队列中的元素个数为（ ）。A.R-F B.F-R C.(R-F+M)M D.(F-R+M)M14.设有一个10阶的下三角矩阵A（包括对角线），按照从上到下、从左到右的顺序存储到连续的55个存储单元中，每个数组元素占1个字节的存储空间，则A54地址与A00的地址之差为（ ）。A.10 B.19 C.28 D.5515.在一个以head为头结点指针的非空单循环链表中，指针p指向链尾结点的条件是（ ）。A.p - data = - 1B.p - next = NULLC.p - next - next=headD.p - next = head二填空（每题2分，共22分，请写在答卷纸上）1.数据元素之间的关系在计算机中有两种不同的表示方法: 【 】和【 】。2.线性表L=(a1,a2,，an)用数组表示，假定删除表中任一元素的概率相同，则删除一个元素平均需要移动元素的个数是【 】。3.一个中缀算术表达式为（A+B）/C-D*(E-F)，其对应的后缀表达式为【 】。4.设一棵完全二叉树中有500个结点，则该二叉树的深度为【 】；若用二叉链表作为该完全二叉树的存储结构，则共有【 】个空指针域。5.假定一棵树的广义表表示为A（C，D（E，F，G），H（I，J），则树中所含的结点数为【 】个，树的深度为【 】，树的度为【 】。6.若以(4，5，6，7，8)作为叶子结点的权值构造哈夫曼树，则其带权路径长度是【 】。7.设有向图G中有向边的集合E=,，则该图两个拓扑排序序列分别为【 】和【 】。8.一组记录的关键字为(46，79，56，38，40，84)，则利用快速排序的方法，以第一个记录为基准得到的一次划分结果为【 】。9.已知广义表A=(x，(a，b)，c)，函数GetHead(GetHead(GetTail(A)的运算结果是【 】。10. 一个队列的入队序列是1234，则出队序列是【4】。11. 设无向图G（如右图所示），则其最小生成树上所有边的权值之和为【4】。三、判断题（每小题1 分，共10分，请写在答卷纸上）1不论是入队列操作还是入栈操作，在顺序存储结构上都需要考虑“溢出”情况。（ ）2当向二叉排序树中插入一个结点，则该结点一定成为叶子结点。（ ）3分块查找的基本思想是首先在索引表中进行查找，以便确定给定的关键字可能存在的块号，然后再在相应的块内进行顺序查找。（ ）4带权无向图的最小生成树是唯一的。（ ）5哈夫曼树中没有度数为1的结点。（ ）6对连通图进行深度优先遍历可以访问到该图中的所有顶点。（ ）7稀疏矩阵的压缩存储可以用一个三元组表来表示稀疏矩阵中的非0元素。（ ）8由树转化成二叉树，该二叉树的右子树不一定为空。（ ）9线性表中的所有元素都有一个前驱元素和后继元素。（ ）10. 完全二叉树中的叶子结点只可能在最后两层中出现。（ ）四、应用题（每题6 分，共30分）1.下面程序段的功能是实现冒泡排序算法，请在下划线处填上正确的语句。void bubble(int rn)for(i=1;i=n-1; i+)for(exchange=0,j=0; jrj+1)temp=rj+1;_;rj=temp;exchange=1;if (exchange=0) return；2.对关键字序列(26，18，60，14，7，45，13，32)进行降序的堆排序，写出构建的初始堆(小根堆)及前两趟重建堆之后序列状态。初始堆：第一趟：第二趟：3.设散列函数为H (key)=key 11，散列地址空间为010，对关键字序列(27，13，55，32，18，49，24，38，43)用线性探查法解决冲突，构建散列表。现已有前4个关键字构建的散列表如下所示，请将剩余5个关键字填入表中相应的位置。4.已知一棵二叉树的前序遍历和中序遍历序列分别为：ABCDEFG和CBDAEGF，要求:(1)画出此二叉树;(2)给出后序遍历序列;(3)画出中序前驱线索二叉树。5.下图所示的森林：(1) 求树（a）的先根序列和后根序列； (2) 求森林先序序列和中序序列；(3)将此森林转换为相应的二叉树。 五、算法设计（共8分）1.假设以单链表表示线性表，单链表的类型定义如下：typedef struct node DataType data；Struct node *next； LinkNode，* LinkList；设计判断单链表中元素是否是递增的算法。参考答案一、选择题（每小题2 分，共30分）题号123456789101112131415答案AABCCBAACBCDCBD二、填空题（每小题2分，共22分）1顺序映像非顺序映像2(n-1)/23AB+C/DEF-*-4950059336697V1,V2,V3,V6,V5,V4或V1,V2,V3,V5,V6,V4V1,V3,V2,V6,V5,V4或V1,V3,V2,V5,V6,V4840,38,46,56,79,849(a,b)101234118三、判断题（每小题1分，共10分）题号12345678910答案YYYNYYYNNY四.应用题1.答: n-i rj+1=rj2. 解: 初始堆: 7, 14, 13, 26, 18, 45, 60, 32 第一趟: 32, 14, 13, 26, 18, 45, 60, 7 第二趟: 60, 14, 32, 26, 18, 45, 13, 73. 解: 0 1 2 3 4 5 6 7 8 9 10 55 43 13 24 27 49 18 38 32 4.解: (1) 二叉树如下: ABFDCGE (2) 后序遍历序列为CDBGFEA (3) 中序前驱线索二叉树如下: ABFDCGE 5.解: (1)先根序列：ABCDEF 后跟序列：BDEFCA (2)先序序列： ABCDEFGHIJK 后