重庆大学计算机学院2005年考研试题
数据结构部分:
一.单选题
1。若要在O(1)的时间复杂度上实现两个循环连表头尾相连接，则对两个循环链表个设置一个指针，分别指向____.
A.各自的头结点 B。各自的尾结点
C。各自的第一个元素结点 D。一个表的头结点，另一个表的尾结点
2。在一个非空双响链表中指针P所指结点之前插入Q所指结点时，应执行____.
A.q->next=p;q->prior=p->prior;p->prior=q;p->prior->next=q;
B.q->prior=p->prior;q->next=p;p->prior->next==q;p->prior=q;
C.p->prior=q;q->next=p;q->prior=p->prior;p->prior->next=q;
D.q->next=p;p->prior=q;q->prior=p->prior;p->prior->next=q;
3.设有一足够大的栈，入栈序列为X，Y，Z，U，V，下列那一个出栈序列是不可能的。
A。X，Y，Z，U，V B。Y，X，Z，U，V
C。Z，X，Y，U，V D。V，U，Z，Y，X
4.已知循环队列的存储空间为数组a[21],且当前队列的头指针和尾指针的值分别为8和3，则给队列的当前长度为。
A。5 B。6 C。16 D。17
5.对广义表，通常采用的存储结构是。
A。数组 B。链表 C。Hash表 D。三元组
6。在稀疏矩阵An*n的十字链表表示中，表头结点的个数为
A。n B。n+1 C。2n D。2n+1
7.一棵二叉树结点的____可以唯一确定一棵二叉树。
A。先序序列和中序叙列 B。先序序列和后序序列
C。中序序列 D。后序序列
8.已知某二叉树的先序序列为ABDCE，它可能的中序序列为
A.BDAEC B.BCADE C.CBADE D.BEACD
9.设二叉树中有n2个度为2的结点，有n1个度为1的结点，有n0个度为0的结点，则该二叉树中空指针的个数为
A.n2+n1+n0 B.n2+n1+2n2 C.2n2+n1 D.n1+2n0
10.下面二叉树中一定是完全二叉树的是
A。平衡二叉树 B.满二叉树 C。单枝二叉树 D。二叉排序树
11.树的路径长度是从树跟到每一结点的路径长度的
A。总和 B。最小值 C。最大值 D。平均值
12.具有n个结点的连通图，其生成树所具有的边数是
A。n-1 B.n C.n+1 D.n的平方
13.Hash法一般用于____情况下的查找
A。查找表为链表 B。查找表为有序表
C。关键字集合比地址集合大得多
D。关键字集合与表中元素的地址集合存在一一对应关系
14。初始序列有序时，下列排序算法中效率最差的是
A。堆排序 B。基数排序 C。希尔排序 D。快速排序
15.对于序列(32,47,12,8,2,19,30),其堆顶元素最小的初始堆是
A.(2,8,12,32,47,19,30) B.(2,8,12,19,30,32,47)
C.(2,12,8,32,19,47,30) D.(2,12,8,30,19,32,47)
二.填空题（每空1分，共15分）
1.线性结构中元素之间存在____关系，树形结构中元素之间存在____关系，图形结构中元素之间存在____关系。
2.在一个单链表中，若删除P所指结点的后继结点，则执行____.
3.对给定的n个元素，建立一个有序单链表的时间复杂度是____。
4.在头指针为head且表长大于1的循环单链报中，指针P指向表中某个结点，若____，则*p的直接后继是尾结点。
5.判定一个循环队列(其头，尾指针分别为front,rear)为空的条件是____。
6.操作StrDelete(&s,pos,len)从串s(其长度为L)中删除第pos个字符起长度为len的子串，要求pos满足____。
7.二维数组A[10][20]采用列序为主序存储，每个元素占一个存储单元，并且A[0][0]的存储地址为200，则A[6][12]的地址是____。
8.深度为7的二叉树至少有____个结点，至多有____个结点。
9.在无向图的邻接矩阵中，如A[j]=1；则A[j]=____.
10.散列存储中，装填因子的值越大，则发生冲突的可能性越____。
11.设哈希表长m=14,H(key)=key%11,表中已有4个结点:addr(15)=4,addr(38)=5,addr(61)=6,addr(84)=7,其余地址为空。如用线性探测再散列处理冲突，关键字为49的结点地址是____。
12.在对一组记录(4,48,96,23,12,60,45,73)进行直接插入排序时，在表头设置岗哨，当把第6个记录60插入到有序表时，为寻找插入位置需比较____次。
三.简答题(20分)
1.请画出所有的中序遍历序列为abc的二叉树。（5分）
2.对下图，请分别给出采用普里姆算法和克鲁斯卡尔算法构造一棵最小生成树的过程。（6分）
(由于此题不难，图就每画了)
3.请对给定的输入序列R=(7,16,4,8,20,9,6,18,5),构造一棵二叉排序树，然后删除结点16，分别画出该二叉排序及删除结点16后的二叉排序树。（4分）
4.有n个不同的英文单词，他们的长度相等，均为m，若n>>50,m<5，试问用什么排序方法时间复杂性最佳？为什么？
四.分析题（25分）
1。（每空2分，工共10分）以下函数将P所指结点与其后边的结点交换位置，请完成该函数。
typedef struct DuLNode{
ElemType data;
Struct DuLnode *prior;
Struct DuLnode *next;
}DuLNode,*DuLinkList;
void test1(DuLinkList p)
{
DuLinkList q;
q=p->next;
if(q!=NULL&& q->next!=NULL && p->prior!=NULL)
{
p->next=________;
________=p;
________=q;
q->prior=________;
p->prior=________;
q->next=p;
}
}
2.请完成以下“删除字符串r中值为ch的所有字符”的算法:
typedef struct {
char *ch;
int length;
}HString;
HSstring test2(&r,ch)
{
for(i=0;i<r.length;i++)
if( r.ch[j]==ch)
{
for(j=i;____;j++)
r.ch[j]=____;
____;
____;
}
return(r);
}
3.(7分)请写出以下程序执行的结果，输入序列为:ABC~~~DE~~FG~~~（~为空格附）
typedef struct BiTNode{
TElemType data;
Struct BiTNode *lchild;
Struct BiTNode *rchild;
}BiTNode,*BiTree;
void Test3(BiTree T)
{
char ch;
if(ch=getchar()==' ')
T=NULL;
else
{
T=(BiTree)malloc(sizeof(BiTNode));
T->data=ch;
Test3(T->lchild);
Test3(T->rchild);
}
}
计算机网络部分
一.填空题（每空2分）
1。IPV6的地址分配规则充分考虑了对IPV4地址的兼容性，因此，IPV4地址 192.168.0.3转换成IPV6的地址后，可以用零压缩法表示为______.
2.在无线局域网中，由于未能检测出媒体上一存在的信号而导致发送数据不成功，这种现象称为______问题。
3.IEEE 802.1D标准为了避免网桥产生兜圈子问题而采用了______算法。
4.IPV6数据报的______字段是对数据报传输提供QoS控制的依据。
5.HDLC信息帧编号字段长度为3bit，如果采用连续ARQ传输数据帧。滑动窗口大小值为____.
二.单项选择题（每题2分）
1。DHCP协议的用途是:
A。域名解析 B.获取主机配置信息 C.传输HTML网页 D。数据加密传输
2.关于IPv6数据报分片的描述不正确的是:
A.IPv6分片限制由源站和中间路由器来完成
B.如果不改变路由，IPv6数据报在传输过程中不需要分片
C.IPv6允许中间路由器采用隧道技术来传送太长的数据报
D。IPv6不允许中间路由器对数据报进行分片处理
3.传输带宽为11Mbps的无线局域网协议为:
A.IEEE802.11 B.IEEE802.1a C.IEEE802.1b D.IEEE802.1ab
4.一个码元传输率为300Baud的信道，如果采用4元制，则其信道的传输速率为:
A。300bps B.600bps C.1200bps D.2400bps
5.数字签名技术可以基于以下那种算法来实现:
A.RSA算法 B。DES算法 C.IDEA算法 D。Triple-DES算法
6.某单位规划网络需要1024个IP地址，若采用无类型域间路由选择CIDR机制，起始地址为192.24.0.0。请问该网络的掩码为:
A.255.252.0.0 B.255.255.192.0 C.255.255.252.0 D.255.255.255.192
7.在以太网网传输IP数据报，数据报的最大长度为:
A.1500字节 B.1518字节 C.65535字节 D.任意长度
8.OSPF协议用于以下那种情况的路由？
A.自治系统内部 B. 自治系统之间 C。自治系统外部 D.非自治系统
9.PPP协议是哪个层的协议？
A.物理层 B。数据链路层 C.网络层 D.运输层
10.报文鉴别码MAC的作用是:
A.报文数据加密 B。鉴别报文的真伪 C。路由地址信息 D.硬件网卡地址
11.当描述一个物理层接口引脚在处于高电平时的含义时，该描述属于:
A。机械特性 B.电气特性 C.功能特性 D.规程特性
12.10BASE-5标准中的“5”代表的是:
A.5类双绞线 B.第5种标准 C。传输速率为5Mbps D.最大作用距离500米
13.关于网桥的描述哪个是不正确的:
A。可以过滤通信量
B。可以互连不同类型的局域网
C。可以提高网络可靠性
D。可以实现数据的路由
14.采用距离向量算法的协议是:
A.OSPF B.SNMP C.RIP D.SMTP
15.以下哪个IP地址不能作为主机IP地址分配:
A.1.0.0.1 B.1.255.255.254 C.240.0.0.1 D.202.255.255.1
三.简述题
1.请问伪首部的作用？当主机发送到一个数据报时，伪首部将位于该数据报的什么位置？（4分）
2.Karn算法的思想是什么？该算法存在什么缺陷，并如何对该算法进行修正？（6分）
3.请比较虚电路服务和数据报服务。（5分）
四.综合题（每题10分）
1.AB两地相距100km，其间有一条同样长度的光纤链路，带宽为100Mbps。如果采用停止等待协议，每帧最大有效数据长度为4000bit，请问如果要从A向B传输100MB的数据，需要多长时间？该传输方式下，信道的利用率为多少？（已知信号传播速率为2*10的8次方m/s,不考虑数据处理时间、数据重传，忽略帧首部长度）
2.某单位分配了一个B类网络，其net-id为168.240.0.0。如果该单位有16个分支机构，每个机构需要分配一个独立的子网，请给出一个合理的分配方案，并说明子网掩码和每个子网所能容纳的主机数量，以及第1个子网的子网号、最小主机地址和最大主机地址。
重庆大学2004计算机学院考研试题
数据结构部分
一.单选题
1.在数据结构中，从逻辑上可把数据结构分成。
A。动态结构和静态结构 B。数据结构和链式结构
C。线性结构和非线性结构 D。内部结构和外部结构
2.对于一个头指针为head的带头结点的单链表，判定该表为空表的条件是。
A。head==NULL B.head->==NULL
C. head->next==head D.head!=NULL
3.为了防止队列假上溢，应该。
A。定义足够大的存贮空间 B。及时进行出队操作
C。及时进行入队操作 D。采用循环队列
4.设数据K1!=K2，通过散列函数H处理后，有H(K1)=H(K2),则K1，K2称为H的。
A。散列值 B。装填因子 C。基数 D。同义词
5.以中序遍历一棵二叉排序树，得到的序列是。
A。升序 B。降序 C。分块有序 D。无序
6.在一棵高度为h的满三叉树中，结点总数为。
A。3的h次方-1 B。(3的h次方-1)/2
C。(3的h次方-1)/3 D。3的h次方
7.若以顺序表示存储二叉树，每个接点站用1个存贮单元，则深度为k的单枝二叉
树浪费的存储单元个数为。
A。2的k次方-k-1 B.2的k-1次方-k-1
C.2的k次方-k+1 D.2的k-1次方-k+1
8.某二叉树的前序遍历序列是abdgcefh,中序遍历序列是dgbaechf,则其后序遍历
序列是。
A。BDGCEFHA B.GDBECFHA C.BDGAECHF D.GDBEHFCA
9.设图G有n个顶点和e条边，以邻接表作为存储结构时，进行深度优先搜索的时
间复杂度为。
A。O(n*e) B.O(log(n*e)) C.O(n+e) D.O(e)
10.在有向图的邻接表中，顶点Vi在表接点中出现的次数是。
A。顶点Vi的度 B。顶点Vi的出度
C。顶点Vi的入度 D。依附于顶点Vi的边数
11.在遍立图时，依次访问:出发点A->A的所有邻接点Bi->Bi的所有接点的方法
成为。
A。深度优先遍立 B。广度优先遍立
C。前序遍立 D。后序遍立
12.一个无序的顺序表中查找数据最好采用。
A。顺序查找 B。折半查找
C。分块查找 D。B-树查找
13.堆排序在最坏情况下的时间复杂度是。
A。O(log以2为底的n) B.O(log以2为底的n平方)
C。O(nlog以2为底的n) D.O(n的平方)
14.在待排序的元素序列基于有序的前提下，效率最高的排序方法是。
A。插入排序 B。选择排序 C。快速排序 D。归并排序
15.一组记录的关键码为(46,79,56,38,40,84),则利用快速排序的方法，以第一
个记录为基准得到的一次划分结果为。
A。38，40，46，56，79，84 B。40，38，46，79，56，84
C。40，38，46，56，79，84 D。40，38，46，84，56，79
二。填空题（每空1分）
1.以下程序段的时间复杂度为。
x=n; /*n>1*/
y=0;
while (x>=(y+1)*(y+1))
y=y+1;
2.在______的情况下，链队列的出队操作需要修改尾指针。
3.广义表((a),a,(b))的表头是______，表尾是______，长度为______。
4.有一个10阶对称矩阵A，采用压缩存储方式（以行序为主序存储其下三角，且
A[0][0]=1），则A[8][5]的存储地址是______。
5.对于为满二叉树的线索二叉树，只有______结点存有该结点的线索。
6.以权值(4,5,6,7,10)构成的哈拂曼树的结点数有______个；其带权路径长度为
______。
7.设无向图G的顶点数为n,则G最少有______条边，最多有______条边。
8.能够成功完成拓扑排序的图一定是一个______图。
9.假定在有序表R[1...n]上进行折半查找，则比较i次查找成功的元素个数为
______，在查找成功时的最多比较次数为______。
10.当增量d为1时，该趟希而排序与______排序基本一致。
三.简答题
1.（每小题2分）试找出分别满足下面条件的所有二叉树:
（1）前序序列和中序序列相同
（2）中序序列和后序序列相同
（3）前序序列和后序序列相同
2.（5分）已知两个4*5的稀疏矩阵的三元组表分别为:
1 4 16
2 2 18
3 4 -25
4 2 28
1 1 32
2 2 -22
2 5 69
3 4 25
4 2 51
请画出这两个稀疏矩阵之和的三元组表。
3.（每小题3分）对于图示的有向图，试给出其
（1）邻接矩阵
（2）邻接表
（3）强连通分量
四.分析题
1.以下函数的功能是:从一给定的长度为n的线性表A中删除元素值在x到y(x<=y)之间的所有元素，并返回线性表的新长度。请完成该函数。（每空2.5分）
Int del(A,n,x,y)
Typedef ElemType A[n];
ElemType x,y;
{
Int i=0;k=0;
While(______)
{
If(A>=x&&A<=y)k++;
Else
A[i-k]= ______;
______;
}
Return (______);
}
2.以下函数将一棵采用链式结构存储的二叉树的左右子树交换，请完成该函数。（每空2.5分）
BiTree swap(BiTree &b)
{
BiTree &t,&t1,&t2;
If (b==NULL) ______;
Else
{
t=(BiTree *)malloc(sizeof(BiTree));
t->data=______;
t1=______;
t2=______;
t->lchild=t2;
t->rchild=t1;
}
Return (t);
}
3.简述以下算法的功能（5分）
LinkList A(LinkList L)
{
If(L&&L->next)
{
Q=L;
L=L->next;
P=L;
While(P->next) P=P->next;
P->next=Q;
Q->next=NULL;
}
Return P;
}
计算机网络部分
一. 填空题（每空1.5分）
1. 网络协议包括语法、语义和______等三个部分。
2. 在TCP/IP体系结构中用于网络管理的协议是______。
3. TFTP协议依靠______协议传输。
4. MD5算法的功能是______。
5. 理论上，带宽时延积为10Mb的网络要达到充分利用，发送端计算机一次发送的数据量为______Mb。
6. 第一个代表性的网络体系结构是IBM与1974年提出的______。
7. 采用T1线路传输的标准话路数是______。
8. 为了能够在电子邮件中传输汉字或图形，需要在SMTP协议的基础上增加一个附加的协议______。
9. 的、拓扑结构逻辑上环形，物理上是总线的局域网标准是IEEE______。
10. 网络体系结构两层的实体间交换信息的位置称为______。
二.单选（每题2分）
1.网络层无连接的服务类型不包括:
A.数据报 B。虚电路 C。证实交付 D。请求回答
2.曼彻斯特编码的跳变没有以下哪项功能:
A.通过电平的跳变方式不同分别表示0和1。
B.提供接收方时钟同步
C.提高传输速率
D.避免连续0或1信号的误判
3.采用8个相位的调相传输其码元，传输速率为200Baud，则数据传输率为:
A.400bps B.600bps C.800bps D.1600bps
4.以下没有采用存储转发机制的交换方式是
A.电路交换 B。报文交换 C。分组交换 D。信元交换
5.IEEE 802.11协议为提高信道利用率，采用了______协议。
A.CSMA/CD B。ALOHA C。CSMA/CA D。时隙ALOHA
6.以下路由算法中健壮性最好的是:
A.洪泛法 B。距离向量算法 C。链路状态算法 D。固定路由法
7.X.25建议书时CCITT制定标准，用于:
A.物理层 B。数据链路层 C。网络层 D。运输层
8.下列说法不正确的是:
A.EIA-232-E是DTE和DCE之间的接口标准
B.EIA-232-E是数据链路层的接口标准
C.EIA-232-E采用负逻辑，即用负电压表示逻辑1，正电压表示逻辑0
D.EIA-232-E的传输距离和带宽低于RS-449标准
9.TCP协议中发送窗口的大小应该是:
A.通知窗口的大小 B。通知窗口和拥塞窗口的较大一个
C.拥塞敞口的大小 D。通知窗口和拥塞窗口的较小一个
10.以下哪个算法被用于数字签名:
A.SHA B。DES C。IDEA D。RSA
11.TCP和UDP协议使用了16bit来表示端口号，其中用于最常用的应用程序的端口号称为熟知端口，其数值范围是:
A.0~127 B。0~255 C。0~1024 D。0`65535
12.WWW服务依靠的协议是:
A.HTML B。HTTP C。SMTP D。URL
13.IP地址191.201.0.125的标准子网掩码是:
A.255.0.0.0 B.255.255.0.0 C.255.255.255.0 D.255.255.255.255
14.源站选路网桥是工作在网络哪个层次的交换设备:
A.物理层 B。数据链路层 C。网络层 D。路由层
15.采用简单停止等待协议时，应该采用多少位来表示数据帧序号:
A.不需要 B。1bit C。2bit D。8bit
三.简答题（每题5分）
1.什么是伪首部，其组成和作用是什么？
2.请简要叙述物理层协议的四个方面和作用？
3.请问使用网桥有什么优点？（至少答出4个方面）
四.综合计算题
1.已知10Mbps以太网传输的MTU为1518字节，其中18个字节为帧控制信息，网络线缆长度为500m。位于网络两端的站点A和B，其中A和、站点现有5KB的数据需要传输到站点B。如果传输采用简单停止等待协议，忽略数据处理时间和应答帧长度。请问至少需要多长时间，站点B才能接收完数据？网络带宽利用率为多少？（信号传播速度为2*10的8次方m/s）（8分）
2.某公司有4个部门，公司网络号为202.202.0.0，请问如果将4个部门划分到不同子网中，并且要每个部门的主机数量最多，应当如何划分？子网掩码应如何表示？每个部门能容纳的主机数量是多少？（7分） |
收藏
点赞!
反对!