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