北科大2003年《数据结构》考研真题答案.pdf

北科大计算机考研全套视频和资料，真题、考点、典型题、命题规律独家视频讲解详见：网学天地();咨询QQ:2696670126参考答案1.线性结构：结构中数据元素是1个对1个。层次结构和网状结构：数据元素是多个对多个。2.可读性、健壮性、效率与低存储量需求。3.Q.front%了子画Q.rear4.2od0=n-1i=15.Llog2nJ+16.数组表示法、邻接表.com7.因为一个结点可以到达多个不同的结点，所以在拓扑排序中可以有不同的结果。8.平衡二叉树9.将所有关键字为同义词的记录存储在同线性链表中，假设某哈希数产生的哈希地址在区间Om1jL,则设立一个指针型向量，chainhash:Array0,m-lof pointer;其中每个分量的初始状态都是空指科，凡哈希地址为的记录都插入到头指针为chainhash(的的链表中在链表命的插入位置可以在表头或表尾，也可以在中间，以保持同义词在同一线性链表中按关键字有序。10.堆排序(1)p!=NULL(2)minp=p(3)q!=NULL(4)minp=q(5)p-dataminp-data(6)p-p-next三、1.k=0-8-D+j北科大计算机考研全套视频和资料，真题、考点、典型题、命题规律独家视频讲解详见：网学天地();咨询QQ:2696670126存储表S001032000015108k=11234567891011121314152.#define MAXN100/体非零元素的最大值*/struct tuple tpinti,j;体非零元所在的行，列号/int value;/体非零元的值*/；体三元组结构*/struct sparmatintm,n,k;/体稀疏矩阵的行数、列数及非零元个数*/struct tuple 3tp dataMAXN;体三元组表*/三元组表结构：ivalue111532334135544155m=5,=5,k=7四、1.1262371428302发测则。CO00B-树是一种平衡的多路查找树一棵m阶的B-树，或为空树或为满足下列特征的m叉树：树中每介结点至多有m棵子树若根结点不是叶子结点，则至少有两棵字树：除根之处的所有非终端结点至少有m2棵子树：所有的非终端结点中包含下列信息数据：（n,A0,KKz,A2,Ka,An)其中，K,n)为关键字，且KK41,A;为指向子树根结点的指针，且指针A:1所指子树中所有结点的关键字均小于K,An所指子树中所有结点的关键字均大北科大计算机考研全套视频和资料，真题、考点、典型题、命题规律独家视频讲解详见：网学天地(www.e-)；咨询QQ:2696670126于Kn,n为关键字的个数。所有的叶子结点都出现在同一层次上，并且不带信息。B+树是应文件系统所需而出的一种B-树的变型树，一棵m阶的B+树和m阶的B-树的差异在于：有n棵子树的结点中含有n个关键字：所有的叶子结点中包含了全部关键字的信息及指向含这些关键字记录的指针，且叶子结点本身按关键字的大小自小而大顺序链接：所有的非终端结点可以看成是索引部分，结点中只含有其子树（根结点）中的最大(或最小)关键字。五、1.DS美2.邻接矩阵：PDSDBos邻接表：DBMDSDBDSEDBDBDSOSOSDB3.深度优先：EMDS DB OS P广度优先：E M DS DB OS P北科大计算机考研全套视频和资料，真题、考点、典型题、命题规律独家视频讲解详见：网学天地(www.e-);咨询QQ:2696670126六、1.26152051140WPL=26+3X6+45+54+123+15X3+20X3+252+26X23132.P取15哈希表15234k25k2661206131415(1526(4(20)(3)(12)(2)25)26(520)(312)(2)02526)(351220)(2)(3451215202526)(2)(23451215202526)七int Btdep(NODE*bt)int current dep,maxdep;分别存放当前访问的层数与最大层数stack s1,s2;ls1存放结点指针；s2中存放s1中对应位置结点的层数NODE*p:max dep=0;push(s1,bt);push(s2,1);while(!Empty Stack(s1)ppop(sl)方currentdep-pop(s2);