搜索
南京邮电学院2002年攻读硕士学位研究生入学考试数据结构试题一、回答下列各题（每小题4分，共36分）1、设n是偶数，且有程序段：FORi:=1tonDOIF2*i=nTHENForj:=2*itonDoy:=y+i*j；则语句“y:=y+i*j”的执行次数是多少？要求列出计算公式。2、已知二叉树T的中根旭李是CBEDAGJIFH，后根序列是CEDBJIGHFA；二叉树根结点的左、右孩子分别是何结点？3、设有一个按元素的递增次序排序的有序表（a1，a2，…，a127），现采用对半查找算法在表中查找给定关键字值为K的元素，则当Ka127和K=a32时，查找过程中元素之间比较的次数分别是多少？4、已知字符串P=‘cbcacbcc’，则next(4)和nextval(7)的值分别为多少？5、设A，B，C三个元素依次进栈，进栈后可立即出栈，则不可得到的出栈次序有哪些？列出所有不可能的出栈序列。6、设结点X是树T中的一个非根结点，B是T所对应的二叉树；在B中，结点Y是X的右孩子，则⑴在树T中，结点X和Y是何关系？⑵求二叉树R的根结点的右子树。7、设线形表L=（a1，a2，…，an）采用顺序存储表示。假定在任何一个元素之后以及在第一个元素之前插入的概率相同。请写出进行一次插入操作平均移动元素次数的计算公式，并进行计算。8、在快速排序算法中，每次划分后，将对划分所得的两个长度不等的子表分别排序。为提高排序效率，应对其中哪个子表先排序？为什么？9、说明下图所示的结点是《数据结构》中讨论的何种数据结构的结点，其中，箭头表示指向子树的指针，数据为关键字值。并说明此数据结构一般用作什么用途。9398100126131二、解答下列问题（每小题6分，共30分）1、设有二叉树如图1所示，请画出该树的先序线索树，试说明构造二叉线索树的好处。ABDH2、请给出图2所示的有向图的所有可能的拓扑有序序列。若拓扑排序能顺利列出图中全部顶点后结束，则表明该有向图满足什么条件？CJ图1K524613图23、在如图3所示的二叉平衡树上完成置顶的插入新元素操作，画出插入新元素，并重新平衡后的树⑴在（a）所示的二叉平衡树上插入关键字值为15发新结点；⑵在（b）所示的二叉平衡树上插入关键字值为23的新结点；4528（a）28144512154、采用Prim算法，以顶点1为源点，求图4所示的无向图的一棵最小代价生成树，并计算该声称树的代价。（b）图35215641415105969127图435、设有关键字序列L=（12，2，16，30，8，28，4，10，20，6，18）。写出用下列排序方法从小到大排序时，第一趟处理结束时的序列。⑴快速排序⑵合并排序三、（8分）根据m阶B树的定义，求解下列问题。要求给出计算过程或说明理由。1、计算m阶B树的最大高度（不计叶子结点）；2、从空树出发构造B树，得到一棵有p个非叶结点的B树。求为了得到该树所需的节点分裂的最多次数。四、（12分）设计一个算法将一个带表头结点的单链表Y，连接在另一个带表头结点单链表X之后。单链表的每个节点有两个域：data和link。算法可用PASCAL语言或C语言描述，要求写出类型说明。五、（14分）设计一个递归算法求一棵哈夫曼树的带权路径长度。二叉树的每个结点有三个域：lchild，rchild和element。算法可用PASCAL语言或C语言描述，要求写出类型说明。