北京理工大学计算机专业考研课程模拟试题.doc

北京理工大学计算机专业考研课程模拟试题集北京理工大学远程教育学院32 北京理工大学专业课程模拟试题集 目 录目 录010020计算机网络3模拟试题一3模拟试题二5模拟试题三7模拟试题四9模拟试题五11010046数据结构与算法13模拟试题一13模拟试题二17模拟试题三21模拟试题四24模拟试题五28010048计算机组成原理32模拟试题一32模拟试题二36模拟试题三41模拟试题四45模拟试题五49070003线性代数54模拟试题一54模拟试题二56模拟试题三58模拟试题四59模拟试题五61090008中国近现代史纲要64模拟试题一64模拟试题二67模拟试题三70模拟试题四74模拟试题五77070001高等数学81模拟试题一A81模拟试题二A83模拟试题三A85模拟试题四A87模拟试题五A89模拟试题一B91模拟试题二B93模拟试题三B95模拟试题四B97模拟试题五B99090006马克思主义基本原理101模拟试题一101模拟试题二102模拟试题三103北京理工大学专业课程模拟试题集 计算机网络010020计算机网络模拟试题一一、单选题 （共6题,共12分）1.下列_属于TCP/IP应用层协议 （2分）A.HTTP TCP IP B.FTP UDP ARP C.HTTP FTP DNS D.SMTP RARP ICMP 2.子网/25的子网掩码是_。 （2分）A. B. C.28 D.92 3.Socket中包含_。 （2分）A.主机名 B.IP地址及MAC地址 C.MAC地址及端口号 D.IP地址及端口号 4.用于防止源节点发送分组速度快于目的节点接收分组速度的算法是_。 （2分）A.差错控制算法 B.拥塞控制算法 C.路由选择算法 D.流量控制算法 5.在客户/服务器模式中，客户指的是_。 （2分）A.请求方 B.响应方 C.硬件 D.软件 6.下列关于UDP协议的说法中正确的是_。 （2分）A.UDP协议可以提供可靠的数据流传输服务B.UDP协议可以提供面向连接的数据流传输服务C.UDP协议可以提供无连接的数据报传输服务D.UDP协议可以提供数据报传输的时延保证二、填空题 （共4题,共8分）1.双绞线可分为_和_两大类。 （2分）2.在TCP/IP网络中，通过_把映射到它的IP地址，通过_把它的IP地址映射到MAC地址。 （2分）3.根据线路中信号在某一时间传输的方向和特点，线路通信方式分为_、_和_。 （2分）4.利用FTP传输文件，客户与服务器之间需要建立的两个连接分别是_和_。 （2分）三、简答题 （共1题,共20分）1.Internet中有哪些服务（至少给出4个）？它们实现何种功能？分别使用哪些协议？ （20分）四、计算题 （共1题,共20分）1.某二进制数据序列为0 0 0 1 1 1 0 1 0 1，请分别画出不归零编码、曼彻斯特编码和差分曼彻斯特编码的信号波形。 （20分）五、问答题 （共4题,共40分）1.什么是网络拓扑结构？ （10分）2.TCP/IP的中文含义是什么？ （10分）3.数据链路层的最基本功能是什么？ （10分）4.什么是频分多路复用？ （10分）模拟试题二一、单选题 （共6题,共12分）1.下列说法中，_是正确的。 （2分）A.当码元的离散值个数N=2，则波特率等于比特率B.600波特和600bps是一个意思C.每秒传送l00个码元也就是每秒传送100个比特D.每秒50波特的传输速率是很低的2.属于网络/21的地址是_。 （2分）A. B. C. D. 3._是通过点对点方式接入Internet的数据链路层协议。 （2分）A.POP B.PPP C.HTTP D.SMTP 4.以下选项中，属于数据报操作特点的是_。 （2分）A.每个分组只需携带简单的目的地址信息，开销小B.在整个传送过程中，需建立到达目的地的专用通路C.使所有分组按顺序到达目的系统D.网络节点要为每个分组做出路由选择5.下列关于UDP协议的说法中正确的是_。 （2分）A.UDP协议可以提供可靠的数据流传输服务B.UDP协议可以提供面向连接的数据流传输服务C.UDP协议可以提供无连接的数据报传输服务D.UDP协议可以提供数据报传输的时延保证6.把模拟信号变换成数字信号的过程叫_。 （2分）A.调制 B.解调 C.量化 D.调制解调 二、填空题 （共4题,共8分）1.局域网通常采用_、_和_拓扑结构。目前应用最普遍的、采用CSMA/CD的局域网是_。 （2分）2.从逻辑功能上看，计算机网络分为_和_两个子网。（2分）3.把一条物理传输线路按时间分为若干片，多路信号轮转使用的技术称为_多路复用技术。 （2分）4.在Internet邮件系统中，用户从邮件服务器读取信件时使用_协议，发送邮件时使用_协议。 （2分）三、简答题 （共1题,共20分）TELNET FTP SMTP DNS 其它 Ethernet ARPANET PDN 其它 在上面给出的TCP/IP层次模型图示中填写的协议名称。 （20分）四、计算题 （共1题,共20分）1.某二进制数据序列为0 0 0 1 1 1 0 1 0 1，请分别画出不归零编码、曼彻斯特编码和差分曼彻斯特编码的信号波形。 （20分）五、问答题 （共4题,共40分）1.什么是网络体系结构？ （10分）2.WWW的中文含义是什么？ （10分）3.ATM的中文含义是什么？ （10分）4.什么是数据通信？ （10分）模拟试题三一、单选题 （共6题,共12分）1.在Web服务器和Web客户之间通信的协议为_。 （2分）A.SLIP B.FTP C.HTTP D.SNMP 2.在客户/服务器模式中，客户指的是_。 （2分）A.请求方 B.响应方 C.硬件 D.软件 3.一个分组被传送到错误的目的站，这种差错发生在OSI/RM中的_。 （2分）A.运输层 B.网络层 C.数据链路层 D.会话层 4.Socket中包含_。 （2分）A.主机名 B.IP地址及MAC地址 C.MAC地址及端口号 D.IP地址及端口号 5.在下列功能中，属于物理层的功能是_。 （2分）A.端端通信 B.路由选择 C.比特流传输 D.链路控制 6.下列关于UDP协议的说法中正确的是_。 （2分）A.UDP协议可以提供可靠的数据流传输服务B.UDP协议可以提供面向连接的数据流传输服务C.UDP协议可以提供无连接的数据报传输服务D.UDP协议可以提供数据报传输的时延保证二、填空题 （共4题,共8分）1某子网的IP地址范围为到54，该子网的掩码为_。 （2分）2.按覆盖的地理范围大小，计算机网络分为_、_和_。（2分）3.LAN参考模型分为三层，它们是物理层、_和_。 （2分）4.内部网关协议RIP是一种广泛使用的、基于_的协议。RIP规定一条通路上最多可包含的路由器数量是_。 （2分）三、简答题 （共1题,共20分）TELNET FTP SMTP DNS 其它 Ethernet ARPANET PDN 其它 在上面给出的TCP/IP层次模型图示中填写的协议名称。 （20分）四、计算题 （共1题,共20分）1.一个信道的带宽为3KHz，能传输具有8级电平的脉冲信号。（1）该信道的最大码元速率为多少？（2）该信道的最大数据速率为多少？（3）如果要在该信道上以30Kbps的速率传输数据，该信道的信噪比应达到多少？（20分）五、问答题 （共4题,共40分）1.WWW的中文含义是什么？ （10分）2.什么是网络体系结构？ （10分）3.什么是频分多路复用？ （10分）4.ISO/OSI的中文含义是什么？ （10分）模拟试题四一、单选题 （共6题,共12分）1.以下选项中，属于虚电路操作特点的是_。 （2分）A.每个分组自身携带有足够的信息，它的传送是自寻址的B.在整个传送过程中，不需建立虚电路C.使所有分组按顺序到达目的系统D.网络节点要为每个分组做出路由选择2.一个分组被传送到错误的目的站，这种差错发生在OSI/RM中的_。 （2分）A.运输层 B.网络层 C.数据链路层 D.会话层 3.在下列功能中，属于物理层的功能是_。 （2分）A.端端通信 B.路由选择 C.比特流传输 D.链路控制 4.如果网络传输速度为28.8Kb/s，要传输2M字节的数据大约需要_。 （2分）A.5分钟 B.10分钟 C.20分钟 D.30分钟 5.把模拟信号变换成数字信号的过程叫_。 （2分）A.调制 B.解调 C.量化 D.调制解调 6.10Base-T中的T代表的是_。 （2分）A.同轴电缆 B.屏蔽双绞线 C.光纤 D.无屏蔽双绞线 二、填空题 （共4题,共8分）1.根据线路中信号在某一时间传输的方向和特点，线路通信方式分为_、_和_。 （2分）2发送邮件服务器与接收邮件服务器之间的通信协议是_。 （2分）3.LAN参考模型分为三层，它们是物理层、_和_。 （2分）4.从逻辑功能上看，计算机网络分为_和_两个子网。（2分）三、简答题 （共1题,共20分）.有一个如图1所示的网络，该网络使用距离矢量算法计算路由。设路由器C刚收到来自B的矢量为（5, 0, 8, 12, 6, 2），来自D的矢量为（16, 12, 6, 0, 9, 10），来自E的矢量为（7, 6, 3, 9, 0, 4）。经测量C到B、D、E的延迟分别为6、3、5，试计算C更新后的路由表，并把结果填入下表的适当位置。 （20分）C更新后的路由表延迟 下一跳 A B B C 0 / D E F 四、计算题 （共1题,共20分）1.某二进制数据序列为0 0 0 1 1 1 0 1 0 1，请分别画出不归零编码、曼彻斯特编码和差分曼彻斯特编码的信号波形。 （20分）五、问答题 （共4题,共40分）1.什么是频分多路复用？ （10分）2.WWW的中文含义是什么？ （10分）3.运输层的主要功能是什么？ （10分）4.什么是数据通信？ （10分）模拟试题五一、单选题 （共6题,共12分）1.用于防止源节点发送分组速度快于目的节点接收分组速度的算法是_。 （2分）A.差错控制算法 B.拥塞控制算法 C.路由选择算法 D.流量控制算法 2.在下列功能中，属于物理层的功能是_。 （2分）A.端端通信 B.路由选择 C.比特流传输 D.链路控制 3.以下选项中，属于数据报操作特点的是_。 （2分）A.每个分组只需携带简单的目的地址信息，开销小B.在整个传送过程中，需建立到达目的地的专用通路C.使所有分组按顺序到达目的系统D.网络节点要为每个分组做出路由选择4.如果网络传输速度为28.8Kb/s，要传输2M字节的数据大约需要_。 （2分）A.5分钟 B.10分钟 C.20分钟 D.30分钟 5.属于网络/21的地址是_。 （2分）A. B. C. D. 6._是通过点对点方式接入Internet的数据链路层协议。 （2分）A.POP B.PPP C.HTTP D.SMTP 三、简答题 （共1题,共20分）TELNET FTP SMTP DNS 其它 Ethernet ARPANET PDN 其它 在上面给出的TCP/IP层次模型图示中填写的协议名称。 （20分）四、计算题 （共1题,共20分）1.某二进制数据序列为0 0 0 1 1 1 0 1 0 1，请分别画出不归零编码、曼彻斯特编码和差分曼彻斯特编码的信号波形。 （20分）五、问答题 （共4题,共40分）1.什么是频分多路复用？ （10分）2.什么是数据通信？ （10分）3.网络层的主要功能是什么？ （10分）4.什么是局域网？ （10分）北京理工大学专业课程模拟试题集 数据结构与算法010046数据结构与算法模拟试题一一、单选题 （共12题,共24分）1.计算机算法必须具有输入、输出和( )这五个特征。 （2分）A.可行性 可移植性和可扩充性B.可行性 确定性和有穷性C.确定性 有穷性和稳定性D.易读性 稳定性和安全性2.设非空单循环链表的头结点为head，p所指结点为最后结点，则p应满足( )。 （2分）A.p-next=NULL B.p=NULL C.p=head D.p-next=head 3.若要从3000个元素中得到20个最小值元素，最好采用( )方法。 （2分）A.直接插入排序 B.简单选择排序 C.起泡排序 D.快速排序 4.线性表中的链式存储结构是通过( )来表示元素之间的关系。 （2分）A.后继元素地址 B.元素的存储顺序 C.左、右孩子地址 D.后继元素的数组下标 5.在顺序栈中插入元素时，是( )。 （2分）A.先存入元素，再移动栈顶指针B.先移动栈顶指针，再存入元素C.不分先后，同时进行D.谁先谁后都可以6.在二叉树的先序遍历序列、中序遍历序列、后序遍历序列中，所有叶子结点的先后顺序( )。 （2分）A.都不相同 B.完全相同C.先序和中序相同，而与后序不同 D.中序和后序相同，而与先序不同7.设有一个二维数组A1020，采用以行序为主序的存储结构，每个元素占两个空间，第一个元素的存放位置为100(十进制)，则元素A66的存放位置为( )。 （2分）A.320(十进制) B.232(十进制) C.300(十进制) D.352(十进制) 8.设有一个顺序栈S，元素a,b,c,d,e,f依次入栈，如果6个元素的出栈顺序为b,c,a,d,f,e，则顺序栈的容量至少为( )。 （2分）A.1 B.2 C.3 D.4 9.对于稀疏矩阵的压缩存储只需存储( )。 （2分）A.零元素 B.非零元素 C.对角线上的元素 D.所有元素 10.快速排序方法在( )情况下最不利于发挥其长处。 （2分）A.被排序的数据量太大B.被排序数据中含有多个相同值C.被排序数据已基本有序D.被排序数据数目为奇数11.如果表中有100000个元素，前99999个元素递增有序，则采用( )排序方法比较次数较少。 （2分）A.快速排序 B.直接选择排序 C.冒泡排序 D.直接插入排序 12.在以下的叙述中，正确的是( )。 （2分）A.线性表的线性存储结构优于链式存储结构B.数据元素是数据的最小单位C.二维数组是它的每个数据元素为一个线性表的线性表D.数据项是数据的基本单位二、填空题 （共12题,共24分）1.设广义表为(a, (b), (c, (d)，则表长为_。 （2分）2.设有循环队列Q，已知MAXQSIZE=18，Q.front=12，Q.rear=14，在连续执行了3次入队，2次出队，3次入队操作之后，(Q.front, Q.rear)的值为_。 （2分）3.深度为5的满二叉树的结点数为_。 （2分）4.广义表(a)的表尾是_。 （2分）5.有5个元素，其入栈次序为A，B，C，D，E，在各种可能的出栈次序中，以C第一个出栈、D第二个出栈的次序有_种。 （2分）6.若无向图中有n个结点，e条边，则它的邻接表需要_个表结点。 （2分）7.设L是带有头结点的单链表的头指针，则判断单链表为空的条件是_。 （2分）8.二维数组A中，每个元素的长度为4个字节，行下标从0到4，列下标从0到5，A按行序为主序存储时元素A3, 5的地址与A按列序为主序存储时元素_的地址相同。 （2分）9.数组的逻辑结构是_的推广。 （2分）10.在一个单链表中，若p所指结点不是最后结点，在p之后插入s所指结点，_。 （2分）11.在队列中，可进行删除操作的一端称为_。 （2分）12.在待排序数据已基本有序的情况下，最佳的排序方法是_。 （2分）三、问答题 （共6题,共36分）1.请用C语言给出顺序表(线性表的顺序存储结构)的类型定义。（6分）2.哈希查找算法与其他查找方法对比有何特点？何谓冲突？请写出两种解决冲突方法的名称。 （6分）3.对于线性表的顺序存储结构，设起始地址为66，每个元素占5个存储单元，求第12个元素的内容存储在哪几个存储单元中。（6分）4.对于n个顶点的无向图G，采用邻接矩阵A表示，如何判断下列问题：a.图中有多少边？b.任意两个顶点i和j是否有边相连？c.任意一个顶点的度是多少？ （6分）5.用一维数组存放的一棵完全二叉树如下：ABCDEFGHIJK。请画出这棵完全二叉树，并写出后序遍历该二叉树的访问结点序列。 （6分）6.用3，6，7，8，30作为叶子结点的值生成一棵赫夫曼树，并计算该树的带权路径长度。 （6分）四、算法题 （共2题,共16分）1.试写出下面无头结点线性表操作算法的功能。（8分）2.下面算法的功能是：在双向循环链表p所指结点之后插入s所指结点，所插入的元素为e。（8分）Status ListInsert_Dul(DuLinkList &L, ElemType e) if(!(s=(DuLinkList)malloc(sizeof(DuLNode) return ERROR;s-data = e;(1)_;(2)_;(3)_;(4)_;return OK;模拟试题二一、单选题 （共12题,共24分）1.对顺序表上的插入、删除算法的时间复杂度分析来说，通常以( )为标准操作。 （2分）A.条件判断 B.元素移动 C.算术表达式 D.赋值语句 2.对二叉树从1开始编号，要求每个结点的编号大于其左右孩子的编号，同一结点的左右孩子中，其左孩子的编号小于其右孩子的编号，则可采用( )。 （2分）A.先序遍历 B.中序遍历 C.后序遍历 D.从根结点开始的层次遍历 3.稀疏矩阵一般的压缩存储方法有两种，即( )。 （2分）A.二维数组和三维数组 B.三元组表和散列表 C.三元组表和十字链表 D.散列表和十字链表 4.设有一个顺序栈S，元素a,b,c,d,e,f依次入栈，如果6个元素的出栈顺序为b,c,a,d,f,e，则顺序栈的容量至少为( )。 （2分）A.1 B.2 C.3 D.4 .5.线性表中的顺序存储结构是通过何种方式表示元素之间的关系( )。 （2分）A.后继元素地址 B.元素的存储顺序 C.左、右孩子地址 D.后继元素的数组下标 6.( )不是队列的基本运算。 （2分）A.判断一个队列是否为空 B.从队头删除一个元素C.在队列第i个元素之后插入一个元素 D.读取队头元素的值7.在数据结构中，从逻辑上可以把数据结构分为( )。 （2分）A.动态结构和静态结构 B.紧凑结构和非紧凑结构 C.线性结构和非线性结构 D.内部结构和外部结构 8.对一个有127个元素的顺序表中删除一个元素，平均要移动( )个元素。 （2分）A.62 B.63 C.63.5 D.64 9.在以下的叙述中，正确的是( )。 （2分）A.线性表的线性存储结构优于链式存储结构B.数据元素是数据的最小单位C.二维数组是它的每个数据元素为一个线性表的线性表D.数据项是数据的基本单位10.若顺序存储的循环队列的MAXQSIZE=n，则该队列最多可存储( )个元素。 （2分）A.n B.n-1 C.n +1 D.不确定 11.对于顺序表的优缺点，以下说法错误的是( )。 （2分）A.插入和删除操作较方便B.可以方便地随机存取表中的任一结点C.无需为表示结点间的逻辑关系而增加额外的存储空间D.由于顺序表要求占用连续的空间，存储分配只能预先进行12.在一个单链表中，若删除p所指结点的后继结点，则执行( )。 （2分）A.q = p-next; p-next = q-next; free(q);B.p = p-next; p-next = p-next-next; free(p);C.p-next = p-next; free(p-next);D.p = p-next-next; free(p-next);二、填空题 （共12题,共24分）1.栈又称为_的线性表。 （2分）2._可以作为实现递归函数的一种数据结构。 （2分）3.在单链表中，头指针的作用是_。 （2分）4.设L是带有头结点的单链表的头指针，则判断单链表为空的条件是_。 （2分）5.已知一个有向图的邻接矩阵表示，则计算第i个结点的入度的方法是_。 （2分）6.深度为5的满二叉树的结点数为_。 （2分）7.线性表的顺序存储结构称为_。 （2分）8.折半查找的存储结构仅限于_存储结构。 （2分）9.具有20个记录的序列，采用起泡排序最少的比较次数为_。 （2分）10. _排序方法能够每次从无序表中顺序查找出一个最小值。 （2分）11.广义表(a)的表尾是_。 （2分）12.在顺序表中插入或者删除一个元素，平均需要移动_元素。 （2分）三、问答题 （共6题,共36分）1.请用C语言给出单链表(线性表的链式存储结构)的类型定义。（6分）2.设有如图所示的逻辑结构图，请给出数据结构形式。（6分）12343.何谓哈希查找中的冲突？请写出两种解决冲突方法的名称。 （6分）4.设哈希表表长为11，哈希函数（用除留余数法）H(key) = key mod 11，解决冲突的方法为开放定址法Hi(key)=(H(key)+di)mod11，对下列关键字序列19，13，33，02，16，24，7，给出计算过程并构造哈希表。（6分）5.以关键字序列12，2，16，9，10，8，20为例，写出执行直接插入排序算法的各趟排序结束时，关键字序列的状态。（6分）6.设一个有序表为1，3，9，12，32，41，62，75，77，82，100，当采用折半查找值为82的结点时，几次比较后查找结束？请给出具体查找过程。（6分）四、算法题 （共2题,共16分）1.下面算法的功能是：将一个带头结点并且头指针为A的单链表分解成两个单链表，其中分别含有原链表中序号为奇数和偶数的元素且保持原来的相对顺序。请在空缺处填入相应的语句。（8分）void Decompose(LinkList A) p = A-next;B =（LinkList）malloc(sizeof (LNode);r = B;while(p!=NULL & p-next!= NULL)q = p-next;(1)_;(2)_;(3)_;(4)_;r-next=NULL;2.阅读如下算法，给出该算法的功能。 （6分）void Unknown(LinkList &L, int n)L=（LinkList）malloc(sizeof (LNode);L-next=NULL;s=L;for (i = n; i0;-i)p = (LinkList)malloc(sizeof(LNode);p-data=i;s-next = p;s = p;s-next = NULL;模拟试题三一、单选题 （共12题,共24分）1.在顺序栈中删除元素时，是( )。 （2分）A.先删除元素，再移动栈顶指针B.先移动栈顶指针，再删除元素C.不分先后，同时进行D.谁先谁后都可以2.在哈希函数H(key) = key%m中，一般来说，m应取( )。 （2分）A.奇数 B.偶数 C.素数 D.充分大的数 3.广义表(a)的表尾是( )。 （2分）A.a B.(a) C.( ) D.(a) 4.线性表若采用链式存储结构，要求内存中可用存储单元的地址( )。 （2分）A.必须是连续的 B.部分必须是连续的 C.一定是不连续的 D.连续不连续都可以 5.在算法的分析中，我们主要考虑算法的( )。 （2分）A.空间复杂性 B.易读性 C.时间复杂性 D.可行性 6.( )中任何两个结点之间没有逻辑关系。 （2分）A.树形结构 B.线性结构 C.图结构 D.集合 7.对一个有127个元素的顺序表中删除一个元素，平均要移动( )个元素。 （2分）A.62 B.63 C.63.5 D.64 8.对于稀疏矩阵的压缩存储只需存储( )。 （2分）A.零元素 B.非零元素 C.对角线上的元素 D.所有元素 9.设有6个结点的无向图，该图至少应有( )条边才能确保是一个连通图。 （2分）A.5 B.6 C.7 D.8 10.设有一个顺序栈S，元素a,b,c,d,e,f依次入栈，如果6个元素的出栈顺序为b,c,a,d,f,e，则顺序栈的容量至少为( )。 （2分）A.1 B.2 C.3 D.4 11.连通图的生成树是( )。 （2分）A.连通子图 B.顶点间可以无路径 C.边数为顶点数 D.极小连通子图 12.线性表中的链式存储结构是通过( )来表示元素之间的关系。 （2分）A.后继元素地址 B.元素的存储顺序 C.左、右孩子地址 D.后继元素的数组下标 二、填空题 （共12题,共24分）1.已知一个有向图的邻接矩阵表示，则计算第i个结点的入度的方法是_。 （2分）2.广义表(a)的表尾是_。 （2分） 3.在单链表中，头结点的作用是_。 （2分）4.在图形结构中，每个结点的前驱结点和后继结点可以有_。 （2分）5.在队列中，可进行插入操作的一端称为_。 （2分）6.若由4，6，8，10，12作为叶子结点的值生成一棵赫夫曼树，则该树的带权路径长度为_。 （2分）7.设有一个顺序栈S，元素a,b,c,d,e,f依次入栈，如果6个元素的出栈顺序为b,c,a,d,f,e，则顺序栈的容量至少为_。 （2分）8.在待排序数据已基本有序的情况下，最佳的排序方法是_。 （2分）9.设无向图G的顶点数为n，则G最少有_条边。 （2分）10.如一个结构中的数据中的数据元素之间存在一个对多个的关系，则称此结构为_。 （2分）11.实现递归调用属于_的应用。 （2分）12.数据的存储结构包括顺序、链式、索引和_四种基本类型。 （2分）三、问答题 （共6题,共36分）1.请用C语言给出顺序栈(栈的顺序存储结构)的类型定义。 （6分）2.用4，6，7，8，9作为叶子结点的值生成一棵赫夫曼树。 （6分）3.在栈的输入端有5个元素，顺序为a,b,c,d,e。能否在栈的输出端得到序列cbdae和dcabe？若能，请给出栈操作的过程，若不能，简述其理由。（6分）4.按中序序列遍历二叉树的结果为123，请画出满足此条件的所有不同形态的二叉树。（6分）5.以关键字序列12，2，16，9，10，8，20为例，写出执行起泡排序算法的各趟排序结束时，关键字序列的状态。（6分）6.将如下树转换成二叉树。（6分）ABEFCGD四、算法题 （共2题,共16分）1.阅读如下算法，给出该算法的功能。（8分）void Unknown(Queue &Q) InitStack(S);while(!QueueEmpty(Q) i=Dequeue(Q);Push(S,i);while(!StackEmpty(S) i=Pop(S);Enqueue(Q,i);2.下面算法的功能是：在带头结点并且设立尾指针L的单向循环链表中第i个位置之前插入新的数据元素e。请在空缺处填入相应的语句。（8分）Status ListInsert(LinkList &L, int i, ElemType e)LinkList p=L-next,s;int j=0;if(iListLength(L)+1)return ERROR;while (jdata=e;(2)_;(3)_;if( (4)_)L=s;return OK;模拟试题四一、单选题 （共12题,共24分）1.计算机算法必须具有输入、输出和( )这五个特征。 （2分）A.可行性 可移植性和可扩充性B.可行性 确定性和有穷性C.确定性 有穷性和稳定性D.易读性 稳定性和安全性2.广义表(a), (b)的表尾是( )。 （2分）A.( ) B.b C.(b) D.(b) 3.广义表(a)的表尾是( )。 （2分）A.a B.(a) C.( ) D.(a) 4.下列数据结构中( )是线性数据结构。 （2分）A.二叉树 B.队列 C.赫夫曼树 D.无向图 5.在顺序栈中插入元素时，是( )。 （2分）A.先存入元素，再移动栈顶指针B.先移动栈顶指针，再存入元素C.不分先后，同时进行D.谁先谁后都可以6.若顺序存储的循环队列的MAXQSIZE=n，则该队列最多可存储( )个元素。 （2分）A.n B.n-1 C.n +1 D.不确定 7.数据结构可形式地定义为(D, S)，其中S是D上( )的有限集。 （2分）A.操作 B.存储映像 C.关系 D.数据元素 8.在哈希函数H(key) = key%m中，一般来说，m应取( )。 （2分）A.奇数 B.偶数 C.素数 D.充分大的数 9.在顺序栈中删除元素时，是( )。 （2分）A.先删除元素，再移动栈顶指针B.先移动栈顶指针，再删除元素C.不分先后，同时进行D.谁先谁后都可以10.设p指向双链表的某一结点，则双链表结构的对称性可以用( )式来刻画。 （2分）A.p-next-next= =p-prior-prior; B.p-prior-prior= =p-next-prior;C.p-prior-next= =p-next-next; D.p-prior-next= =p-next-prior;11.对顺序表上的插入、删除算法的时间复杂度分析来说，通常以( )为标准操作。 （2分）A.条件判