招生：计算机应用
第一部份数据结构（50分）
1．填空（每题1分）
（1）若一个栈，输入的顺序是：1，2，…，n，输出的第一个元素是n，则第i（1≤i≤n）个输出元素是。
（2）链接存储的主要优点是。
（3）广义表的每个结点既可以是结点值，也可以是。
（4）一棵树的层号表示为1A，2B，3D，3E，2C，则它对应的括号表示为。
（5）在二叉树的链接存储中，空指针域的数目是（设树中结点个数为N）。
（6）昌泡排序最少的比较次数是。
（7）快排序的最坏效率是。
（8）在堆排序的建堆过程中，首先需要设计一个筛选过程，然后从第个结点到第一个结点逐个调用它。
（9）B 树的特点是。
（10）建立倒排文件的主要目的是为了便于对的查找。
2．设HASH函数H（KEY）=KEYMOD7，HASH表的地址空间为0~6，对关键码序列（32，13，49，18，22，38，21）
分别按拉链法和线性探测法处理砬撞，构造HASH表，试画出它们的存储结构示意图，设每个结点的查找概率相同，
分别计算这两种HASH表中，成功查找的平均查找长度（即平均比较次数）。（10分）
3．有一双向链表，存储结构为：D（1：N，1：2），LR（1：N），LL（1：N），其中，数组D的第一列存结点值，
第二列存查找频度，LR和LL分别存指向结点的后继和前驱的指针，假定P0为链头指针，并有LL（P0）=0，链尾指针
为Q0并有LR（Q0）=0（0代表空指针），假定链表中无重复结点。初始，结点已链接好，每个结点的查找频度均为0。
试设计一算法，输入一数值KEY，查找数组D中等于KEY的D（P，1），并且将D（P，2）累加1，然后修改链表，使之
从P0开始，始终按结点查找频度的降序链接。（15分）
4．有一二叉树，存储结构为：D（1：N）存树结点值，L（1：N），R（1：N）分别存的指向结点左、右子树的指针，
并用0表示空指针，用负数表示中序线索，T为根指针。
试写一过程，利用中序线索，求地址为K的结点在后序遍历中的前驱结点的地址P，并调用该过程对二叉树进行后序遍
历。（15分）
注：第3、4题，要求用SPARKS语言或类PASCAL语言写算法，并要求先用文字描述算法思想。
第二部份网络基础（50分）
一、路由选择一般有哪几种方法？试比较其优缺点。（10分）
二、传输层为用户提供哪些服务？如何描述服务质量？（10分）
三、FDDI的介质访问控制协议和一般TokenRing有何区别？（10分）
一、已知信道的数据率为1Mbps，往返传播时延为4ms，帧长为1000bit，帧号用三位，并假定不采用捎带方式确认且不
占时间，若不虑出错重发和帧头所造成信道损失，请问采用选择重传协议信道可能达到的最大有效利用率是多少？（10分）
一同轴电缆长20km，上有1000个站，传播时延为5μS/Km，线路的数据率为10Mbps。每个站发送的帧均为10000bit长。
若采用CSMA/CD协议，求每个站发送帧的最大可能速率。（10分）