--数据结构b.docVIP

南 京 林 业 大 学 试 卷 课程 数据结构(A卷) 2004~2005学年第一学期 注意：请将正确答案写在答题纸上，答在试卷上不给分。 1 2 3 4 5 6 7 8 9 10 X √ X X X √ √ X √ X 二．选择题：(20分) 1 2 3 4 5 6 7 8 9 10 C A C D C C B A B A 一．是非题：（每小题2分，共20分） 1．数据项是数据的基本单位。（ ） 2．线性表中的元素可以是各种各样的，但同一线性表中的数据元素具有相同的特性，因此是属于同一数据对象。（ ） 3．在线性表的顺序存储结构中，逻辑上相邻的两个元素但在物理位置上并不一定相邻。（ ） 4．顺序存储方式只能用于存储线性结构。（ ） 5．若入队序列为1，2，3，4，则4，3， 2，1是一个出队序列。（ ） 6．设有两个串p和q，其中q是p的子串，把q在p中首次出现的位置作为子串q在p中的位置的算法称为匹配。（ ） 7．使用三元组顺序表表示稀疏矩阵的元素，有时并不能节省存储空间。（T ） 8．先根遍历树和先序遍历与该树对应的二叉树，其结果不同。（F ） 9．哈夫曼树是带权路径长度最短的树，路经上权值较大的结点离根较近。（T ） 10．连通分量是无向图中的极小连通子图。（F ） 二．选择题（本大题共10小题，每小题2分，共20分） 数据结构是研究数据的______以及它们之间的相互关系。A.抽象结构和理想结构 B.物理结构和理想结构 C. 物理结构和逻辑结构 D.物理结构和抽象结构 线性表是________。A. 一个有限序列，可以为空 B. 一个有限序列，不能为空 C. 一个无限序列，可以为空 D. 一个无限序列，不能为空 若已知一个栈的入栈序列是1,2,3,…,n,其输出序列为s1,s2,s3,…sn,若s1=n, 则si为________。A．i B．n=i C．n-i+1 D．以上都不对 将两个各有n1n2个元素的有序表()归并成一个有序表最少的比较次数是________A．n1 B．n2 C．n1+n2-1 D．min (n1,n2) 具有线性结构的数据结构是________。A. 树结构 B.图结构 C.广义表 D.文件结构 按照二叉树的定义，具有3个结点的二叉树有______ 种。A．3 B．4 C．5 D．6  下面哪一个方法可以判断出一个有向图中是否有环（回路）________。A．广度优先遍历 B．拓扑排序C．求最短路径 D．求关键路径 设森林Ｆ对应的二叉树为Ｂ，Ｂ有ｍ个结点，Ｂ的根为ｐ，ｐ的右子树结点个数为ｎ，森林Ｆ中第一棵树的结点个数是______。A．m-n B．m-n+1 C．n+1 D．条件不足，无法确定 一个具有n个顶点的有向图最多有___B___ 条弧。A．n B．n(n-1) C．n(n-1)/2 D．2n  不满足平衡查找树概念的是________。A．BST树 B.AVL树 C.折半查找判定树 D.B+树 三．填空题：（本大题共10小题，每小题2分，共20分） 计算机执行下面语句时，语句S的频度（执行次数）为________。 for(i=1;in-1;i++) for(j=n;j=i;j--) S; 从任何一个结点开始都能成功查找其它结点的单链表是 表。 设n行n列的上三角矩阵A已压缩存储到一维数组B[0..n(n+1)/2-1]中，且按行为主序存储，则aij（i,j=0,1,2,…,n-1）对应的B中的存储位置为 。 n个顶点的连通图用邻接矩阵表示时该矩阵至少有个非零元素 若一个二叉树含有n个结点，则它的二叉链表中必有 个空的链域。  若某二叉树有20个叶子结点，有30个结点仅有一个孩子，则该二叉树的总的结点数是 ____________。 Dijkstra最短路径算法从源点到其余各顶点的最短路径长度按__________次序产生。 设有100个元素，用折半查找方法查找时，若查找成功，则最多的比较次数是__________，最少的比较次数是__________。 若m阶B-树中有n个关键字，则叶子结点即查找不成功的结点数为__________。 对n个不同的元素进行冒泡排序（从小到大排序），在最坏情况下记录