《2016年西安电子科技大学软件学院、校企联合培养9104高级语言程序设计之数据结构复试笔试仿真模拟题.doc》由会员分享，可在线阅读，更多相关《2016年西安电子科技大学软件学院、校企联合培养9104高级语言程序设计之数据结构复试笔试仿真模拟题.doc（4页珍藏版）》请在金锄头文库上搜索。
1、2016年西安电子科技大学软件学院、校企联合培养9104高级语言程序设计之数据结构复试笔试仿真模拟题一、选择题1 对给定的关键字序列110, 119, 007, 911，114，120, 122进行基数排序，则第2趟分配收集后得到的关键字序列是（ ） A.B.C.D.【答案】C【解析】基数排序的第1趟排序是按照个位数字来排序的，第2趟排序是按然十位数字的大小进行排序的，故答案是C 选项。 2 若下图为lOBaseT 网卡接收到的信号波形，则该比特串是（ ） A.00110110B.10101101C.01010010D.11000101【答案】A【解析】以太网采用曼彻斯特编码，其将一个码元分成
2、两个相等的间隔，前一个间隔为高电平而后一个间隔为低电平表示1，反之则表示0。故根据波形图，可得答案为A 。 3 可以用（ ）定义一个完整的数据结构。A. 数据元素B. 数据对象C. 数据关系D 抽象数据类型【答案】D【解析】抽象数据类型可以定义一个完整的数据结构。包括数据元素，数据元素之间的关系，以及可以进行的操作。 4 下列选项中，能缩短程序执行时间的措施是（ ）。I. 提高CPU 时钟频率II. 优化数据通路结构III. 对程序进行编译优化A. 仅I 和IIB. 仅I 和IIIC. 仅II 和IIID.I 、II 和III【答案】D【解析】一般说来，CPU 时钟频率（主频）越高，CPU 的
3、速度就越快；优化数据通路结构，可以有效提高计算机系统的吞吐量；编译优化可得到更优的指令序列。所以I 、II 、III 都是有效措施。 5 已知字符串S 为“abaabaabacacaabaabcc ”，模式串t 为“abaabc ”，采用KMP 算法进行匹配，第一次出现“失配” （A.i=l，j=0B.i=5，j=0C.i=5，j=2D.i=6，j=2【答案】C【解析】模式匹配（KMP ）算法对普通的暴力匹配的改进在于：每当匹配过程中匹配失败时，主串（本题为S ）的指针（i ）不需要回溯，而是利用已经得到的“部分匹配”的结果将模式串（t ）向右“滑动”尽可能远的一段距离后，继续进行比较。模式串
4、“滑动”的距离是由模式串（t ）本身决定的，即t 的子串中前缀串和后缀串相等的最长长度。本题中第一次失配i=5, 字串为“abaab”，其相等且最长的前后缀为“ab”，一次下一个j = 2。 6 4个圆盘的Hanoi 塔，总的移动次数为（ ）。A.7B.-8C.15D.16【答案】C【解析】Hanoi 问题总移动次数为：次。 7 某计算机采用微程序控制器，共有32条指令，公共的取指令微程序包含2条微程序，各指令对应的微程序平均由4条微指令组成，采用断定法（下址字段法）确定下条微指令的地址，则微指令中下址字段的位数至少是：（ ）A.5B.6C.8，i=j = 5，则下次开始匹配时，i 和j 的值
5、分别是（ ）。D.9【答案】C 【解析】所以至少需要8位才能表示完130个地址。8 分别以下列序列构造二叉排序树，与用其他三个序列所构造的结果不同的是（ ）。 【答案】C【解析】二叉排序树：左右子树都是二叉排序树，且保证右子树都比根结点大，左子树都比根结点小。据以上两点建立二叉排序树。 9 FTP 客户和服务器间传递FTP 命令时，使用的连接是（ ）。A. 建立在TCP 之上的控制连接B. 建立在TCP 之上的数据连接C. 建立在UDP 之上的控制连接D. 建立在UDP 之上的数据连接【答案】A【解析】对于FTP , 为了保证可靠性，选择TCP 。FTP 应用需要建立两条TCP 连接：一条为控
6、制连接，另一条为数据连接。FTP 服务器打开21号端口，被动的等待客户的连接建立请求。客户则以主动方式与服务器建立控制连接，客户通过控制连接将命令传给服务器，而服务器则通过控制连接将应答传给客户，命令和响应都是以NVTASCII 形式表示的。 10n 个结点的完全有向图含有边的数目（ ）。A.n*nB.n （n+l）C.n/2D.n*（n-l ）【答案】D【解析】在有向图中，如果任意两个顶点之间都存在边，则称为有向完全图。顶点个数为n 的无向图，最多有为n （n-l ）。条边。如是有向图，需要在无向图的最多边的基础上乘以2，则二、填空题11设有个结点的完全二叉树顺序存放在向量【答案】 中，其下标值最大的分支结点为_。 【解析】最大的分支结点是最后一个叶子结点的父结点。 一、选择题考研试题
