卓越考研

2000年南京理工大学数据结构考研试题，卓越考研特整理南京理工大学考研真题，为广大考生提供有效的信息支持。

一．在所给的A、B、C、D中选择一个最确切的（每题1.5分，共33分）1.下面关于算法说法错误的是
（A）算法最终必须由计算机程序实现
（B）为解决某问题的算法同为该问题编写的程序含义是相同的（C）算法的可行性是指指令不能有二义性（D）以上几个都是错误的2.下面说法错误的是
（1）算法原地工作的含义是指不需要任何额外的辅助空间
（2）在相同的规模n下，复杂度O（n）的算法在时间上总是由于复杂度O（2n）的算法（3）所谓时间复杂度是指最坏情况下，估算算法执行时间的一个上界（4）同一个算法；实现语言的级别越高，执行效率就越低（A）（1）（B）（2）（C）（1），（4）（D）（3）
3.（1）静态链表既有顺序存储的优点，又有动态链表的优点。所以，它存
取表中第i个元素的时间与i无关。
（2）静态链表中能容纳的元素个数的最大数在表定义时就确定了，以后不能增加。
（3）静态链表与动态链表在元素的插入、删除上类似，不需做元素的
移动。以上错误的是（A）（1）、（2）（B）（1）C）（1）（2）（3）（D）（2）4.一棵有n个结点的二叉树，按层次从上到下，同一层从左到右顺序存储在一维组A[1,n]中，则二叉树中第i个结点（）i从1考试用上述方法编号的右孩子在数组A中位置是
（A）A[2i](2i≦n)（B）A[2i+1](2i+1≦n)(C)A[i/2]
(D)条件不充分，无法确定
5.将有关二叉树的概念推广到三叉树，则一棵有244个结点的完全三叉树的高度是（A）4（B）5（C）6（D）76.设栈S和队列Q的初始状态为空，元素e1,e2,e3,e4,e5和e6依次通过栈S，一个元素出栈后即进队列Q，若6个元素出队的序列是e2,e4,e3,e6,e5,e1,则栈S的容量至少应该是（A）6（B）4（C）3（D）2
7.对下列四种排序方法，在排序中关键字比较次数同记录初始排列无关的是（A）直接插入（B）二分法插入（C）快速排序（D）归并排序
8.设树T的度为4，其中度为1,2,3和4的结点个数分别为4,2,1,1，则T中的叶子数位（A）5（B）6（C）7（D）8
9.在有向图G的拓扑序列中，若顶点Vi在Vj之前，则下列情形不可能出现的是（A）G中有弧<Vi,Vj>
（B）G中有一条从Vi到Vj的路径（C）G中没有弧<Vi,Vj>
（D）G中有一条从Vj到Vi的路径
10.有数据{53,30,37,12,45,24,96}，从空二叉树开始逐个插入数据形成二叉排序树，若希望高度最小，则应选择下面那个序列输入（A）45,24,53,12,37,96,30,（B）37,24,12,30,53,45,96（C）12,24,30,37,45,53,96（D）30,24,12,37,45，96,53
11.有关二叉树下列说法正确的是（A）二叉树的度为2
（B）一棵二叉树的度可以小于2
（C）二叉树中至少有一个结点的度为2（D）二叉树中任何一个结点的度都为2
12.设有一个按个元素的值排好序的线性表，且长度大于2，对给定的值k，分别用顺序查找法和二分查找法查找一个与k相等的元素，比较次数分别是s和b，在查找不成功的情况下，正确的s和b的数量关系是（Ａ）总有ｓ＝ｂ（Ｂ）总有ｓ＞ｂ（Ｃ）总有ｓ＜ｂ（Ｄ）与ｋ值大小有关
１３.下面关于Ｂ树和Ｂ＋树的叙述中，不正确的结论是（Ａ）Ｂ树和Ｂ＋树都有能有效的支持顺序查找（Ｂ）Ｂ树和Ｂ＋树都能有效的支持随机查找（Ｃ）Ｂ树和Ｂ＋树都是平衡的多分树（Ｄ）Ｂ树和Ｂ＋树都可用于文件索引结构
１４.某二叉树中序列为Ａ，B，C，D，E，F，G，后序序列为B，D，C，A，F，G，E，则前序序列是（A）E,G,F,A,C,D,B（B）E,A,C,B,D,G,F（C）E,A,G,C,F,B,D（D）上面的都不对15.上题的二叉树对应的森林包括多少棵树
（A）1（B）2（C）3（D）概念是错误的16.关于杂凑查找说法不正确的有几个
（1）采用链地址解决冲突时，查找一个元素的时间是相同的
（2）采用链地址法解决冲突时，若插入规定总是在链首，则插入任一个元素的时间是相同的
（3）用链地址法解决冲突易引起聚集现象（4）再哈希法不易产生聚集
（A）1（B）2（C）3（D）4
17设森林F对应的二叉树为B，它有m个结点，B的跟为p，p的右子树结点个数为n，森林F中第一棵树的结点个数是
（A）m-n（B）m-n-1（C）n+1（D）条件不足，无法确定

18.采用简单选择排序，比较次数和移动次数分别为（A）O(n),O(logn)（B）O(logn),O(n2)（C）O(n2),O(n)（D）O(nlogn),O(n)19.归并排序中，归并的趟数是（A）O(n)（B）（O(logn)（C）O(nlogn)（D）O(n2)

21.（1）求从指定源点到其余各项点的地杰斯特拉（Dijkstra）最短路径算法中弧上权不能为负的原因在实际应用中无意义
（2）利用Dijkstra求每一对不同顶点之间的最短路径的算法时间是O(n3)（图用零接矩阵表示）
（3）Floyed求每对不同顶点对的算法中允许弧上的权为负，但不能有权和为负的回路
上面不正确的是（A）（1），（2），（3）（B）（1）（C）（1），（3）（D）（2），（3）
22.（1）在AOE-网中，减小任一关键活动上的权值后，整个工程的工期也就相应减小
（2）在AOE-网中，工程工期为关键活动上的权之和
（3）在关键路径上的活动都是关键活动，而关键活动也必在关键路径上，上面有错的说法个数是（）A）（1）B）（2）C）（3）D）（1），（2）
二、填空（共33分，每空1.5分，答题时注明填空补缺处的序号，不需注题号）1.计算机执行下面的语句时，语句s的执行次数为（1）。for(i=l:i<n-l;i++)for(j=n:j>=i:j--)s:2.对于双向链表，在两个结点之间插入一个新结点需修改的指针共（2）个，单链表为（3）个。
3.求从某源点到其余各顶点的Dijkstra算法在图的顶点数为10，用邻接矩阵表示图时计算时间约为10ms，则在图的顶点数为40时，计算时间约为
（4）ms。
4.向一棵m阶B-树插入操作时，当结点的关键字数为（5）则要分裂该结点；删除时，结点中关键字数为（6）时，可能需要同左或右兄弟合并。
5.按13，24，37，90，53的次序形成二叉平衡树，则该二叉平衡树的高度是（7），其根为（8），左子树中的数据是（9），右子树中的数据是（10）。
7.已知有序表为（12，18，24，35，47，50，62，83，90，115，134）当用二分法查找90时，需（14）次查找成功，47时（15）成功，查100时，需（16）次才能确定不成功。
8.设一棵后序线索树的高是50，结点x是树中的一个结点，其双亲是结点y,y的右子树高度是31，x是y的左孩子。则确定x的后继最多需经过（17）中间结点（不含后继及x本身）9.设F是由T1、T2、T3三棵树组成的森林，与F对应的二叉树为B，已知T1、T2、T3的结点数分别为n1、n2、n3，则二叉树B的左子树中有（18）个结点，右子树中有（19）个结点。
11.三维数组a[4][5][6]（下标从0开始计，a有4*5*6个元素），每个元素的长度是2，则a[2][3][4]的地址是（22）。（设a[0][0][0]的地址是1000，数据以行为主方式存储）三、将下面的类-C写的程序补充完整，凡未说明的变量均是工作变量（共34分，每空1分，第5小题为3+3分，答题时注明填空补缺处的序号，不需注题号）
1.下面是中序线索树的遍历算法，树有头结点且由指针thr指向。树的结点有五个域，分别为：数据域data，左、右孩子域lchild,rchikd和左、右标志域ltag,rtag，规定，标志域为1是线索，0是指向孩子的指针。
Inordethread(thr){
P=thr->lchild;While((1)
){While((2))P=(3);Printf(p->data);While((4)
){P=(5);Printf(p->data);}P=(6);}
2.用链表表示的数据的简单选择排序，结点的域为数据data，指针域next；链表首指针为head。链无头结点。Selectsort(head){
p=head;while((7)){q=p;r=(8);while((9)){if((10))q=r;r=(11);}tmp=q->data;q->data=p->data;p->data=tmp;p=(12);}}
3.一元稀疏多项式以循环单链表按降幂排列，结点有三个域，系数域coef，指数域exp和指针域next；现对链表求一阶导数，链表的头指针为ha，头结点的exp域为-1.Derivative(ha){q=ha;
pa=ha->next;while((13)){
If((14)){
(15);Free(pa);Pa=(16);}Else
{
Pa->coef(17);Pa->exp(18);q=(19);}pa=(20);}}
4.n个顶点的有向图用邻接矩阵array表示，下面是其拓扑排序算法，试补充完整注：（1）图的顶点号从0开始
（2）indegree是有n个分量的一维数组，放顶点的入度。（3）函数crein用于算顶点入度
5.在前题的基础上进行求关键路径的第一步，即算出各顶点的最早发生时间（记在ve[k]中，0≤k≤n-1）,为此，邻接矩阵定义为
ai,j
G[i,j]
0
其中ai,j是弧<i,j>上的权，若不存在弧<i,j>，则为0（ai,j规定为0）在上述条件下，除了
将数组ve作为topsort的参数，topsort(array,indegree,ve,n)外则（1）crein要否改，如何改（写出修改部分的语句）（3分）
（2）topsort如何修改，写出修改部分语句（3分）注意：若需删去某语句注明语句号；插入语句注明在哪一行后插入；若修给某行，注明行号替换为...