中国人民大学1999年数据结构与网络基础试题

http://www.globalsino.com/    



招生专业:计算机应用

考试科目:数据结构与网络基础

第一部份 数据结构(共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)=KEY MOD
7,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的介质访问控制协议和一般Token Ring有何区别?(10分)

一、已知信道的数据率为1Mbps,往返传播时延为4ms,帧长为1000bit,帧号用三位,并假定不采用捎带方式确认且不
占时间,若不考虑出错重发和帧头所造成信道损失,请问采用选择重传协议信道可能达到的最大有效利用率是多少?(10分)

一同轴电缆长20km,上有1000个站,传播时延为5μS/Km,线路的数据率为10Mbps。每个站发送的帧均为10000bit长。
若采用CSMA/CD协议,求每个站发送帧的最大可能速率。(10分)


其他推荐阅读:

如何选择通风好的房子 聪明买房的“6标准3公式”
乙型肝炎病毒相关性肾炎 小儿肾炎
慢性肾炎蛋白尿的中医辨证食疗 急性肾炎容易与哪些疾病相混淆?
冒牌同学现身校友录 网上诈骗又有新招 高考招生诈骗伎俩曝光专家为您一一揭密
不懂时尚就不懂营销 现代业务员的100个必知
2006职场风向标:哪些行业职位多薪水高? 钱尼夫妇超会赚 收入是布希12倍
意大利旅游景点及如何到达 意大利(Italy)的旅游城市名录
怎样吃素菜最健康 家里筷子怎样放细菌最少
保护胃的十种最大禁忌 茶水煮饭可防四种病
 
 
 
【无国界华人网】版权所有。Copyright (C) 2006 GlobalSino, All Rights Reserved